差分进化 (Differential Evolution) 是一种全局优化算法。
它是一种演化算法，与其他演化算法（如遗传算法）相关。
与遗传算法不同，它专门设计用于处理实值向量而不是位串。也与遗传算法不同的是，它使用向量减法和加法等向量运算来导航搜索空间，而不是受遗传学启发的变换。
在本教程中，您将了解差分进化全局优化算法。
完成本教程后，您将了解：
- 差分进化优化是一种演化算法，旨在处理实值候选解。
- 如何在 Python 中使用差分进化优化算法 API。
- 使用差分进化解决具有多个最优解的全局优化问题的示例。
通过我的新书 《机器学习优化》 启动您的项目，其中包括所有示例的分步教程和 Python 源代码文件。
让我们开始吧。
使用 Python 进行差分进化全局优化
照片由 Gergely Csatari 拍摄，保留部分权利。
教程概述
本教程分为三个部分；它们是：
- 差分进化
- 差分进化 API
- 差分进化实践示例
差分进化
差分进化（Differential Evolution，简称 DE）是一种随机全局搜索优化算法。
它是一种演化算法，与遗传算法等其他演化算法相关。与使用位序列表示候选解的遗传算法不同，差分进化旨在处理用于连续目标函数的多维实值候选解。
差分进化 (DE) 可谓是目前使用的最强大的随机实参数优化算法之一。
— 《差分进化：最新技术综述》，2011年。
该算法在搜索中不使用梯度信息，因此非常适合于不可微的非线性目标函数。
该算法通过维护一个由实值向量表示的候选解种群来工作。新的候选解是通过创建现有解的修改版本来生成的，这些新解在算法的每次迭代中会替换掉大部分种群。
新的候选解是使用一种“策略”创建的，该策略涉及选择一个基准解，并向其添加一个变异，同时从种群中选择其他候选解来计算变异的数量和类型，这被称为差分向量。例如，一种策略可能会选择最佳候选解作为基准，并选择随机解来形成变异中的差分向量。
DE 通过将两个种群向量之间的加权差值加到第三个向量上来生成新的参数向量。
— 《差分进化：一种简单高效的连续空间全局优化启发式算法》，1997年。
如果子代的目标函数评估结果更优，那么基准解将被其子代替换。
最后，在我们建立了一组新的子代之后，我们将每个子代与创建它的父代进行比较（每个父代创建了一个子代）。如果子代比父代更好，它就会在原始种群中取代父代。
— 第 51 页，《元启发式算法精要》，2011年。
变异被计算为候选解对之间的差值，从而产生一个差分向量，然后将其加到基准解上，并通过一个设置在 [0,2] 范围内的变异因子超参数进行加权。
并非基准解的所有元素都会发生变异。这由一个重组超参数控制，并且通常设置得较大，例如 80%，这意味着基准解中的大多数（但不是全部）变量都会被替换。保留还是替换基准解中某个位置的值，是根据采样概率分布（如二项分布或指数分布）为每个位置单独决定的。
一种标准术语用于描述差分策略，其形式为：
- DE/x/y/z
其中 DE 代表“差分进化”，x 定义了要进行变异的基准解，例如“rand”表示随机，或“best”表示种群中的最佳解。y 代表添加到基准解上的差分向量的数量，例如 1。z 定义了用于确定每个解在种群中是被保留还是被替换的概率分布，例如“bin”表示二项分布，或“exp”表示指数分布。
上面使用的一般约定是 DE/x/y/z，其中 DE 代表“差分进化”，x 代表一个字符串，表示要扰动的基准向量，y 是用于扰动 x 的差分向量的数量，z 代表所使用的交叉类型（exp：指数；bin：二项）。
— 《差分进化：最新技术综述》，2011年。
DE/best/1/bin 和 DE/best/2/bin 是流行的配置，因为它们在许多目标函数上表现良好。
Mezura-Montes 等人进行的实验表明，无论待解决问题的特性如何，DE/best/1/bin（总是使用最佳解来寻找搜索方向并使用二项交叉）在最终准确性和结果稳健性方面，仍然是最具竞争力的方案。
— 《差分进化：最新技术综述》，2011年。
现在我们熟悉了差分进化算法，让我们看看如何使用 SciPy API 的实现。
想要开始学习优化算法吗？
立即参加我为期7天的免费电子邮件速成课程（附示例代码）。
点击注册，同时获得该课程的免费PDF电子书版本。
差分进化 API
差分进化全局优化算法可通过 SciPy 的 `differential_evolution()` 函数在 Python 中使用。
该函数将目标函数的名称和每个输入变量的边界作为搜索的最小参数。
|
1 2 3 |
... # 执行差分进化搜索 result = differential_evolution(objective, bounds) |
搜索还有许多额外的超参数，它们有默认值，不过您可以配置它们来自定义搜索。
一个关键的超参数是 “strategy” 参数，它控制执行的差分进化搜索类型。默认情况下，它设置为“best1bin”（DE/best/1/bin），这对于大多数问题来说是一个很好的配置。它通过从种群中选择随机解，将一个从另一个中减去，然后将差值的缩放版本加到种群中的最佳候选解上来创建新的候选解。
- 新解 = 最佳解 + (变异因子 * (随机解1 - 随机解2))
“popsize” 参数控制种群中维护的候选解的大小或数量。它是候选解维数的倍数，默认设置为 15。这意味着对于一个二维目标函数，将维护一个大小为 (2 * 15) 或 30 的候选解种群。
算法的总迭代次数由“maxiter”参数控制，默认为 1,000。
“mutation” 参数控制每次迭代中对候选解进行的改变数量。默认情况下，该值设置为 0.5。重组量由“recombination”参数控制，默认设置为 0.7（即给定候选解的 70%）。
最后，在搜索结束时，会对找到的最佳候选解应用局部搜索。这由 “polish” 参数控制，默认设置为 True。
搜索的结果是一个 OptimizeResult 对象，其属性可以像字典一样访问。搜索是否成功可以通过 ‘success’ 或 ‘message’ 键来访问。
函数评估的总次数可以通过 ‘nfev’ 访问，搜索找到的最优输入可以通过 ‘x’ 键访问。
现在我们已经熟悉了 Python 中的差分进化 API，让我们来看一些实际的例子。
差分进化实践示例
在本节中，我们将看一个在具有挑战性的目标函数上使用差分进化算法的例子。
Ackley 函数是一个目标函数的例子，它有一个全局最优解和多个局部最优解，局部搜索可能会陷入其中。
因此，需要一种全局优化技术。它是一个二维目标函数，在 [0,0] 处有全局最优解，其值为 0.0。
下面的例子实现了 Ackley 函数并创建了一个三维曲面图，显示了全局最优解和多个局部最优解。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
# ackley 多峰函数 from numpy import arange from numpy import exp from numpy import sqrt from numpy import cos from numpy import e from numpy import pi from numpy import meshgrid from matplotlib import pyplot from mpl_toolkits.mplot3d import Axes3D # 目标函数 def objective(x, y): return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20 # 定义输入范围 r_min, r_max = -5.0, 5.0 # 以 0.1 为增量均匀采样输入范围 xaxis = arange(r_min, r_max, 0.1) yaxis = arange(r_min, r_max, 0.1) # 从坐标轴创建网格 x, y = meshgrid(xaxis, yaxis) # 计算目标值 results = objective(x, y) # 使用 jet 配色方案创建曲面图 figure = pyplot.figure() axis = figure.gca(projection='3d') axis.plot_surface(x, y, results, cmap='jet') # 显示绘图 pyplot.show() |
运行该示例会创建 Ackley 函数的曲面图，显示大量的局部最优解。
Ackley 多峰函数的三维曲面图
我们可以将差分进化算法应用于 Ackley 目标函数。
首先，我们可以将搜索空间的边界定义为函数在每个维度上的限制。
|
1 2 3 |
... # 定义搜索的边界 bounds = [[r_min, r_max], [r_min, r_max]] |
然后我们可以通过指定目标函数的名称和搜索边界来应用搜索。在这种情况下，我们将使用默认的超参数。
|
1 2 3 |
... # 执行差分进化搜索 result = differential_evolution(objective, bounds) |
搜索完成后，它将报告搜索的状态和执行的迭代次数，以及找到的最佳结果及其评估值。
|
1 2 3 4 5 6 7 8 |
... # 总结结果 print('状态 : %s' % result['message']) print('总评估次数: %d' % result['nfev']) # 评估解 solution = result['x'] evaluation = objective(solution) print('解: f(%s) = %.5f' % (solution, evaluation)) |
将这些内容整合在一起，下面列出了将差分进化应用于 Ackley 目标函数的完整示例。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
# 用于 ackley 多峰目标函数的差分进化全局优化 from scipy.optimize import differential_evolution from numpy.random import rand from numpy import exp from numpy import sqrt from numpy import cos from numpy import e from numpy import pi # 目标函数 def objective(v): x, y = v return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20 # 定义输入范围 r_min, r_max = -5.0, 5.0 # 定义搜索的边界 bounds = [[r_min, r_max], [r_min, r_max]] # 执行差分进化搜索 result = differential_evolution(objective, bounds) # 总结结果 print('状态 : %s' % result['message']) print('总评估次数: %d' % result['nfev']) # 评估解 solution = result['x'] evaluation = objective(solution) print('解: f(%s) = %.5f' % (solution, evaluation)) |
运行该示例会执行优化，然后报告结果。
注意：鉴于算法或评估过程的随机性，或数值精度的差异，您的结果可能会有所不同。考虑多次运行该示例并比较平均结果。
在这种情况下，我们可以看到算法找到了输入等于零、目标函数评估值等于零的最优解。
我们可以看到总共执行了 3,063 次函数评估。
|
1 2 3 |
状态：优化成功终止。 总评估次数：3063 解: f([0. 0.]) = 0.00000 |
进一步阅读
如果您想深入了解，本节提供了更多关于该主题的资源。
论文
- 差分进化 – 一种简单高效的连续空间全局优化启发式算法, 1997.
- 差分进化：最新技术综述, 2011.
书籍
API
文章
总结
在本教程中，您了解了差分进化全局优化算法。
具体来说，你学到了：
- 差分进化优化是一种演化算法，旨在处理实值候选解。
- 如何在 Python 中使用差分进化优化算法 API。
- 使用差分进化解决具有多个最优解的全局优化问题的示例。
你有什么问题吗？
在下面的评论中提出你的问题，我会尽力回答。
感谢 Brownlee 博士，
我希望能看到一本以如此实用的方式介绍这些主题的书。
谢谢！我也希望！
谢谢 Brownlee 博士
不客气。
很棒的教程！希望看到这个算法在更具挑战性问题上的实现！
谢谢。
我能在这个函数中应用约束吗？
当然可以。
我可以使用现有的多个等式和不等式约束进行多目标优化吗？
我不确定，我想您需要直接使用多目标算法/API。
是否可以使用差分进化算法来寻找机器学习模型的多元函数的全局最小值/最大值？
当然可以。这将取决于函数的复杂性和优化算法的配置。
是的。使用 `optimize.NonLinearConstraint` 来实现。
太棒了！
谢谢 Jason！这是一个很好的例子，展示了如何设置它。
如何向输入函数传递一个不应被优化的输入参数？我之所以这样问，是因为在我的情况下，我会事先计算好其他参数，这些参数将在目标函数中使用，但不会被优化。
祝好，
Thomas
抱歉，我没有仔细阅读文档。我找到了 🙂