原文：
towardsdatascience.com/hands-on-global-optimization-methods-with-python-07bff0e584a9
想象一下和你的最佳朋友出去。你决定去一个你从未去过但你的朋友去过的地方。
此外，想象一下你在一个交通有点问题的城市，比如罗马（因为我来自那里，这很痛苦），考虑一下你和你的最佳朋友将在那里见面，但带着两辆不同的车离开同一所房子。
你和你的最佳朋友同时离开家，由于你们从未去过那个地方，你们使用GPS导航到达那里。
当你到达那里时，你发现你的朋友已经在点饮料了，并告诉你他已经在等你 10 分钟了。假设你和你的朋友都没有超速，这个故事告诉我们两件事：
你应该对你最好的朋友感到愤怒，因为他本可以告诉你更快的路线，而不是让你使用 GPS。他为什么还是没给你打电话呢？😡
你刚刚遇到了一个局部最小值问题
在这篇文章中，我们将重点关注问题 2，我会让你自己处理你的最佳朋友。
为什么局部最小值在这个例子中很重要？
让我们退一步。
类似于 Google Maps（或通常所说的地图）这样的服务已经是非常知名的优化算法。你需要从 A 点去 B 点，并且你希望最小化完成这一过程所需的时间。这正是我们所说的“优化”的含义：在给定一组参数的情况下，优化目标函数的过程。
每个人都依赖 Google Maps 去往我们从未去过的地方，我们之所以这样做，是因为我们相当自信 Google Maps 不会浪费你很多时间，并且会带你到达你想要的目的地，而不会出现大的延误或问题。然而，当我们确实知道位置时，大多数情况下我们相信如果我们选择另一条路线，我们会更快到达目的地。这是因为我们可能知道在一天中的某个特定时间会有计划的道路施工，因为交通会在你离开家之后开始涌现（而且它不会给 Google Maps 时间重新计算），因为那里有很多测速陷阱，汽车往往会猛踩刹车，减缓整个车流，等等。
换句话说，我们认为我们拥有的数据比谷歌地图（有时确实如此）更多。随着数据的增加，我们最终达到的极小值比谷歌地图的极小值还要低。但是等等，我们不是说谷歌地图也在运行优化吗？是的，确实如此！这是一个我们可以说是其极小值是局部的情况。那么我们的极小值也是局部的吗？也许，也许不是，可能。也许这是一个比谷歌地图的局部极小值还要低的另一个局部极小值。或者也许这确实是迄今为止最快的路线（全局极小值）。可以确定的是，找到全局优化的任务，即“所有极小值中的最低点”或“所有极大值中的最大点”，是一个非常迷人的练习。
希望通过我给出的这个简介，你对我这个关于全局优化的文章足够感兴趣，愿意继续阅读。我们将从给出全局优化问题的形式化开始，然后我们将找到多种方法（或算法）来达到全局最优解。特别是，我们将从最简单的方法到最复杂的方法列出这些方法。
让我们开始吧！🚀
0. 形式化问题
那么，全局最优解。我们这是什么意思？
让我们从可能稍微有些平凡但非常关键的一点开始。我们所说的所有这些（以及已经说过的）都是与黑盒函数一起工作并且有意义的。当我这么说的时候，我的意思是，我给函数输入，后台发生一个数值过程，函数“吐出”一个数字。换句话说，我们必须假设我们没有任何关于函数外观的解析估计。
为什么是这样呢？因为如果我知道了解析函数，我就可以通过求导数，看到它何时为 0，二阶导数的符号是“-”或“+”，取决于最大值或最小值，并找到最优解值。
例如，让我们考虑 argmax（最优解=最大值）的情况。我们有一个这样的方程：
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/65473efd4aba1a171dee8e5d7a1e8886.png
作者制作的照片
所以，再次强调，在我们已知 f(x) 的解析形式的情况下，我们得到的结果类似于：
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/586610eed8a32797609106b7ca95bb05.png
作者制作的照片
但在现实中，我们没有 f’(x)，因为你一开始就没有 f(x) 的解析表达式，所以你实际上无法通过解析方法得到 X_opt。
但问题中还有更多因素。在现实中，X是一个连续集合，所以我们实际上无法“检查它们所有”，这意味着我们无法真正看到所有可能的 X 的 f(x) 的值。
这是我们进行全局优化时面临的问题概述，这也是为什么我们使用数值方法来解决它们的原因。这意味着我们放弃了导数的解析定义，并试图用算法来接近这个问题。当然，我们仍然会使用解析表达式来测试它（发明黑盒），但之后我们不会在我们的优化中使用任何解析操作。
你同意吗？我希望你能同意。让我们开始吧！
*请注意，X是一个 k 维空间。在你的问题中可以考虑多个参数。
1. 粗暴力方法（们）
1.1 理念
当你想找到一个数据集的最小值时，最合理的事情，即使是非技术人员也会建议的事情是这样做：
让我们探索所有可能性！
现在这仅仅适用于非常有限的情况。例如，如果我们只有一个参数有四种不同的选择，或者三个参数有两种选择，或者两个参数有三种选择。我想你已经明白了这个要点。
如果你只有几个选择，尝试探索它们是值得的。但如果你的参数空间是连续的，你就已经无计可施了（你无法探索一个封闭无限空间的全部可能性）。尽管如此，你仍然可以使用这种逻辑。一个简单的事情就是通过将其分成多个步骤（网格方法）来采样你的参数空间（X）。然而，文献清楚地表明，当你想要进行一些模拟时，添加一些随机性会更明智。**拉丁超立方采样**是一个非常好的替代方案。
我担心这会变得过于技术化，进展得太快。我想通过一些编码来使其变得平缓，这样我们就有机会进行解释。
1.2 代码
让我们考虑一维输入的直线：y = mx+c。假设我们固定 m 和 c 为 m = 5 和 c = 3。假设我们想要识别 m 和 c。当然，你可以直接拟合这条线并结束，但我们可以也将这（为了教学目的）视为一个优化问题。
好了，说够了，让我们导入一些库。我们将使用超级知名的库：numpy 和 scipy。
Jovian 优化过程
现在，目标目标是通过这个函数定义的：
Jovian 优化过程
我们还添加了“compute_error”函数，该函数计算目标行与新行（方程 y = mx + c）之间的差异。
这些是一些随机行和目标行：
cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fjovian.com%2Fembed%3Furl%3Dhttps%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D5&dntp=1&display_name=Jovian&url=https%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D5&image=https%3A%2F%2Fapi.jovian.com%2Fapi%2Fgist%2Ff0dc8e2716c7408d9d263144d3a979d4%2Fpreview%2F182fc648dc2443ba8b165bd9e7556eb8%3Fts%3D1725295093219&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&scroll=auto&schema=jovian
现在我们从1 条随机红色线开始，计算误差，它可能非常高。然后，我们继续添加模拟。模拟的数量会越来越大。通过比较越来越多的线条，我们将得到越来越准确的估计。
我们可以从这里清楚地看到：
cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fjovian.com%2Fembed%3Furl%3Dhttps%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D6&dntp=1&display_name=Jovian&url=https%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D6&image=https%3A%2F%2Fapi.jovian.com%2Fapi%2Fgist%2Ff0dc8e2716c7408d9d263144d3a979d4%2Fpreview%2F182fc648dc2443ba8b165bd9e7556eb8%3Fts%3D1725295093219&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&scroll=auto&schema=jovian
这意味着我们正在收敛，使用 100,000 个样本，对 m 和 c 的估计非常好。以下是如果我们绘制它的情况：
cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fjovian.com%2Fembed%3Furl%3Dhttps%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D7&dntp=1&display_name=Jovian&url=https%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D7&image=https%3A%2F%2Fapi.jovian.com%2Fapi%2Fgist%2Ff0dc8e2716c7408d9d263144d3a979d4%2Fpreview%2F182fc648dc2443ba8b165bd9e7556eb8%3Fts%3D1725295093219&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&scroll=auto&schema=jovian
在这个特定情况下：
代价函数是目标线和新（候选）线之间的差异
我们正在用来自拉丁超立方体的“num”次模拟填充 2 维参数空间（m,c）。
我们在目标线和“num”行之间计算代价函数，并提取最佳结果
现在这相当于“枚举可能性”，但它们并不完全是所有可能性，因为我们处于连续空间中。这是一个非常简单的方法，并且容易受到局部最小值的存在的影响。另一方面，当模拟次数增加时，处于局部最小值的概率会降低（你可能已经探索了所有最小值，并达到了其中最低的一个）。
这被称为暴力法，因为它完全依赖于模拟次数和错误计算。没有任何复杂性，计算量非常大。暴力法在所应用的采样方法上有所不同。正如之前所说，我们应用了拉丁超立方体。
2. 梯度下降
2.1 概念
我将要展示的方法在机器学习社区中非常知名，因为它是用作训练神经网络的方法。
我们开始涉及更复杂的算法。这个想法如下：
我们从一个随机参数向量 x_start开始。在任何感兴趣的 k 维空间中。
我们计算随机参数x_start的损失。
我们计算特定x_start的损失梯度，并朝相反方向移动*
*请注意，如果我们想要最大值，这个方法的工作方式完全相同，但你需要遵循梯度的方向（而不是相反）。
如你所见，这个想法本身非常简单。让我们看看代码。
整个想法非常简单，可以用几行代码实现
cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fjovian.com%2Fembed%3Furl%3Dhttps%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D9&dntp=1&display_name=Jovian&url=https%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D9&image=https%3A%2F%2Fapi.jovian.com%2Fapi%2Fgist%2Ff0dc8e2716c7408d9d263144d3a979d4%2Fpreview%2F182fc648dc2443ba8b165bd9e7556eb8%3Fts%3D1725295093219&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&scroll=auto&schema=jovian
现在，正如您所知，这个问题中仍然存在局部最小值的问题：
cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fjovian.com%2Fembed%3Furl%3Dhttps%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D10&dntp=1&display_name=Jovian&url=https%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D10&image=https%3A%2F%2Fapi.jovian.com%2Fapi%2Fgist%2Ff0dc8e2716c7408d9d263144d3a979d4%2Fpreview%2F182fc648dc2443ba8b165bd9e7556eb8%3Fts%3D1725295093219&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&scroll=auto&schema=jovian
如您从上面的示例中可以看出，如果我们从一个错误区域开始的随机参数，我们就会陷入局部最小值。现在，有几种方法可以使这种梯度下降方法更有效，并避免局部最小值。这些方法包括随机梯度下降（SGD）（在 Keras 中经常用作“优化器”），添加动量，以及进行随机重启。一篇很好地总结了所有这些可能性的文章是由Mohit Mishra提供的。
这些方法并不完美，因为它们只是尝试逃离局部最小值的数值方法：你仍然不能确定最小值是全局的，就像总是那样。尽管如此，像 SGD 和动量这样的技术因其是逃离梯度下降中局部最小值的好方法而闻名，并且在训练神经网络时通常被使用。
3. 贝叶斯优化
3.1 想法
现在我们进入代理模型的业务领域，这恰好也是我的博士论文主题。当黑盒函数实际上计算密集时，使用贝叶斯优化，你可能需要等待很长时间（数十秒）才能得到输入 x 对应的输出 f(x)。
策略如下：
你选取一小部分点，并在这些小部分点上计算你的损失函数**。
这些点的配对（x,f(x)）用于训练高斯过程回归（Gaussian Process Regression, GPR）。
训练好的 GPR 用于密集采样参数空间。
期望改进（EI）告诉你GPR 不确定的地方。换句话说，使用 EI，我们可以选择可能存在全局最小值或最大值的地方
你选择具有最大 EI 的点。计算(x_new, f(x_new)）并重新训练 GPR。然后重新运行 3、4 和 5。
如果你想了解所有这些数学，你可以看看我的文章这里，其中我花了 10 分钟的时间深入讨论它。
3.2 代码
好吧，让我们考虑这个函数*：
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/b3ddd268c591d69aaba5ae485ec908c2.png
由作者制作的照片
Jovian
正如我说的，让我们取一小部分数据作为训练集：
Jovian 上的优化过程
我们训练我们的 GPR：
Jovian 上的优化过程
然后我们选择 EI 值最大的区域，并重新训练 GPR。我们重复进行这个过程。这是结果：
cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fjovian.com%2Fembed%3Furl%3Dhttps%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D16&dntp=1&display_name=Jovian&url=https%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D16&image=https%3A%2F%2Fapi.jovian.com%2Fapi%2Fgist%2Ff0dc8e2716c7408d9d263144d3a979d4%2Fpreview%2F182fc648dc2443ba8b165bd9e7556eb8%3Fts%3D1725295093219&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&scroll=auto&schema=jovian
我对这种方法有着爱恨交加的关系。我发现它极其吸引人、优雅且有用，但实际上要训练一个用于大型数据集的 GPR 需要很多工作，尤其是在维度很大（k>>0）的情况下。简而言之，我尽一切可能使用 GPR，并希望有更多机会使用它。🙁
4. 遗传算法
4.1 想法
遗传算法是另一种寻找黑盒函数全局最优解的极其吸引人的方法。其逻辑是选择一组随机候选人，根据你的成本函数选择最好的，将它们配对，并将它们进化成新的候选人。更精确地说，这些步骤是：
你从一个随机生成的可能解决方案种群开始。
你使用预定义的成本（或适应度）函数评估每个候选人的适应度。适应度函数告诉你解决方案有多“好”。
你将选定的候选人（父母）配对以产生新的候选人（后代）。这个过程通过交换父母解决方案的部分来创建后代的多样性，通常被称为交配。
你可以（并且通常这样做）引入随机变化到一些后代基因（解决方案的个体部分）以保持种群内的多样性。这只是为了引入一些随机性（实际上这有助于避免局部最小值）
你替换旧种群为新的一组候选人，并在多代中重复此过程。
停止（终止）是通过预定义的标准（例如最大迭代次数=1000）获得的
4.2 代码
PyGAD 的出色人员使遗传算法（GA）的使用变得极其简单。安装方法如下：
pip install pygad现在让我们考虑这个损失函数来最大化。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/29c35b94048e3f3a48052806f0d50584.png
*注意：PyGAD 用于最小化-f(x)，这与最大化 f(x)相同
让我们以 x 在 [0,10] 和 y 在 [0,10] 的范围内运行 GA。这就是它的样子*：
cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fjovian.com%2Fembed%3Furl%3Dhttps%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D19&dntp=1&display_name=Jovian&url=https%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D19&image=https%3A%2F%2Fapi.jovian.com%2Fapi%2Fgist%2Ff0dc8e2716c7408d9d263144d3a979d4%2Fpreview%2F182fc648dc2443ba8b165bd9e7556eb8%3Fts%3D1725295093219&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&scroll=auto&schema=jovian
注意：有很多参数需要考虑。幸运的是，PyGAD 解释得非常清楚。请参阅文档以了解更多信息！
正如我们所见，我们收敛到全局最小值：
cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fjovian.com%2Fembed%3Furl%3Dhttps%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D21&dntp=1&display_name=Jovian&url=https%3A%2F%2Fjovian.ml%2Fpiero-paialunga%2Foptimization-process%2Fv%2F4%26cellId%3D21&image=https%3A%2F%2Fapi.jovian.com%2Fapi%2Fgist%2Ff0dc8e2716c7408d9d263144d3a979d4%2Fpreview%2F182fc648dc2443ba8b165bd9e7556eb8%3Fts%3D1725295093219&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&scroll=auto&schema=jovian
GAs 在检测全局最优解方面非常出色，但在处理大维度（k>>0）时，时间和资源消耗略高
5. 结论
非常感谢您花时间与我一起探讨全局最优解的旅程。让我们看看我们做了什么：
我们使用 GPS 和到达目的地的最短时间示例引入了全局最优解的问题
我们形式化了全局最优解的问题，并解释了为什么我们需要数值方法来解决它们
我们讨论了暴力法：在参数空间中进行采样并计算损失。简单但效率不高。
我们描述了梯度下降法：在机器学习中臭名昭著，用于处理高维问题。您可以通过使用随机梯度下降（SGD）或动量来尝试避免陷入局部最小值。
我们讨论了代理建模（贝叶斯优化）：您可以使用代理模型来模拟损失函数，并使用期望改进来引导您找到全局最小值。极其优雅，但计算量大。
我们描述了遗传算法：一种基于修改一组可能的随机解的优雅算法类。我们在一个二维问题上尝试了它，并取得了成功。这种方法不适用于高维，但它是对抗局部最小值/最大值的一个非常好的方法。
6. 关于我！
再次感谢您抽出宝贵时间。这对您来说意义重大 ❤
我叫 Piero Paialunga，就是这里这位：
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d9ed061b17ef8293f7fe9b102bd96c78.png
图片由作者制作
我是美国辛辛那提大学航空航天工程系的博士候选人，同时也是 Gen Nine 的机器学习工程师。我在博客文章和领英上谈论人工智能和机器学习。如果您喜欢这篇文章，并想了解更多关于机器学习的内容，以及跟随我的研究，您可以：
A. 在**领英上关注我，我在那里发布所有故事。B. 订阅我的通讯。这将让您了解新故事，并有机会给我发信息，以便接收您可能有的所有更正或疑问。C. 成为推荐会员，这样您就不会有“每月故事数量上限”的限制，您可以阅读我（以及成千上万的机器学习和数据科学顶级作家）关于最新技术的所有文章。D. 想和我合作？请查看我的收费和项目Upwork**！
如果您想向我提问或开始合作，请在这里或**领英**上留言：
[email protected]
