scipy.optimize.

差分进化

scipy.optimize.differential_evolution(func, bounds, args=(), strategy='best1bin', maxiter=1000, popsize=15, tol=0.01, mutation=(0.5, 1), recombination=0.7, seed=None, callback=None, disp=False, polish=True, init='latinhypercube', atol=0, updating='immediate', workers=1, constraints=(), x0=None, *, integrality=None, vectorized=False)

找到多元函数的全局最小值。

差分进化方法 [1] 本质上是一种随机方法。它不使用梯度方法来寻找最小值，并且可以搜索大量候选空间，但通常比传统的基于梯度的技术需要更多的函数评估。

该算法归功于 Storn 和 Price [2]。

参数:

函数可调用

要最小化的目标函数。必须以 f(x, *args) 的形式，其中 x 是以 1-D 数组形式的参数，args 是任何额外固定参数的元组，这些参数是完整指定函数所需的。参数的数量 N 等于 len(x)。

bounds : 序列 或 Bounds序列或

变量的边界。有两种指定边界的方式：

1. Bounds 类的实例。

2. (min, max) 对 x 中的每个元素，定义了 func 优化参数的有限下限和上限。

总的边界数量用于确定参数的数量，N。如果存在边界相等的参数，自由参数的总数为 N - N_equal。

参数tuple, 可选

完全指定目标函数所需的任何额外固定参数。

策略{str, callable}, 可选

要使用的差分进化策略。应该是以下之一：

• ‘best1bin’

• ‘最佳1实验’

• ‘rand1bin’

• ‘rand1exp’

• ‘rand2bin’

• ‘rand2exp’

• ‘randtobest1bin’

• ‘randtobest1exp’

• ‘currenttobest1bin’

• ‘currenttobest1exp’

• ‘best2exp’

• ‘best2bin’

默认值为 ‘best1bin’。可能实现的策略在 ‘Notes’ 中概述。或者，可以通过提供一个可调用对象来自定义差分进化策略，该对象构造一个试验向量。可调用对象必须具有 strategy(candidate: int, population: np.ndarray, rng=None) 的形式，其中 candidate 是一个整数，指定正在进化的种群条目，population 是一个形状为 (S, N) 的数组，包含所有种群成员（其中 S 是总种群大小），rng 是求解器中使用的随机数生成器。candidate 将在范围 [0, S) 内。strategy 必须返回一个形状为 (N,) 的试验向量。该试验向量的适应度将与 population[candidate] 的适应度进行比较。

在 1.12.0 版本发生变更: 通过可调用对象自定义进化策略。

maxiterint, 可选

整个种群进化的最大代数。在没有抛光的情况下，最大函数评估次数为：(maxiter + 1) * popsize * (N - N_equal)

popsizeint, 可选

用于设置总人口规模的乘数。人口有 popsize * (N - N_equal) 个个体。如果通过 init 关键字提供了初始人口，则此关键字将被覆盖。当使用 init='sobol' 时，人口规模计算为 popsize * (N - N_equal) 之后的下一个2的幂。

tolfloat, 可选

收敛的相对容差，当 np.std(pop) <= atol + tol * np.abs(np.mean(population_energies)) 时停止求解，其中 atol 和 tol 分别是绝对容差和相对容差。

变异浮点数或元组(浮点数, 浮点数), 可选

变异常数。在文献中，这也被称为差分权重，通常用 F 表示。如果指定为浮点数，它应在范围 [0, 2] 内。如果指定为元组 (min, max)，则使用抖动。抖动会在每一代之间随机改变变异常数。该代的变异常数从 U[min, max) 中取值。抖动可以显著加快收敛速度。增加变异常数会增加搜索半径，但会减慢收敛速度。

重组float, 可选

重组常数应在范围 [0, 1] 内。在文献中，这也被称为交叉概率，通常用 CR 表示。增加此值允许更多变异体进入下一代，但会增加种群不稳定的危险。

seed : {None, int, numpy.random.Generator, numpy.random.RandomState}, 可选{None, int,}

如果 seed 是 None（或 np.random），则使用 numpy.random.RandomState 单例。如果 seed 是 int，则使用一个新的 RandomState 实例，并使用 seed 进行种子设定。如果 seed 已经是 Generator 或 RandomState 实例，则使用该实例。指定 seed 以实现可重复的最小化。

dispbool, 可选

在每次迭代中打印评估的 func。

回调可调用，可选

在每次迭代后调用的可调用对象。具有以下签名：

callback(intermediate_result: OptimizeResult)

其中 intermediate_result 是一个包含 OptimizeResult 的关键字参数，该 OptimizeResult 具有属性 x 和 fun，分别表示迄今为止找到的最佳解决方案和目标函数。请注意，参数名称必须为 intermediate_result，以便回调函数传递 OptimizeResult。

回调函数也支持以下签名：

callback(x, convergence: float=val)

val 表示种群收敛的分数值。当 val 大于 1.0 时，函数停止。

内省用于确定调用哪个签名。

如果回调函数引发 StopIteration 或返回 True，全局最小化将停止；任何抛光操作仍将执行。

在 1.12.0 版本发生变更: 回调接受 intermediate_result 关键字。

抛光bool, 可选

如果为 True（默认），则在最后使用 L-BFGS-B 方法的 scipy.optimize.minimize 来优化最佳种群成员，这可以稍微改善最小化效果。如果研究的是约束问题，则改为使用 trust-constr 方法。对于具有许多约束的大型问题，由于雅可比计算，优化可能需要很长时间。

初始化str 或 array-like, 可选

指定执行哪种类型的人口初始化。应该是以下之一：

• ‘拉丁超立方’

• ‘sobol’

• ‘halton’

• ‘随机’

• 指定初始种群的数组。该数组应具有形状 (S, N)，其中 S 是总人口大小，N 是参数的数量。init 在使用前会被裁剪到 bounds。

默认值是 ‘latinhypercube’。拉丁超立方采样试图最大化覆盖可用参数空间。

‘sobol’ 和 ‘halton’ 是更优越的替代方案，并且能更充分地利用参数空间。’sobol’ 将强制初始种群大小，该大小计算为 popsize * (N - N_equal) 之后的下一个2的幂。’halton’ 没有要求，但效率稍低。更多详情请参见 scipy.stats.qmc。

‘random’ 随机初始化种群 - 这有一个缺点，即可能会发生聚类，从而阻止覆盖整个参数空间。可以使用数组来指定种群，例如，在已知存在解的位置创建一组紧密的初始猜测，从而减少收敛时间。

atolfloat, 可选

收敛的绝对容差，当 np.std(pop) <= atol + tol * np.abs(np.mean(population_energies)) 时停止求解，其中 atol 和 tol 分别是绝对容差和相对容差。

更新{‘立即’, ‘延迟’}, 可选

如果 'immediate' ，最佳解向量会在单个世代内持续更新 [4] 。这可以导致更快的收敛，因为试验向量可以利用最佳解的持续改进。使用 'deferred' ，最佳解向量每代更新一次。只有 'deferred' 与并行化或向量化兼容，并且 workers 和 vectorized 关键字可以覆盖此选项。

Added in version 1.2.0.

工人int 或类似映射的可调用对象，可选

如果 workers 是一个整数，种群将被细分为 workers 部分并在并行中进行评估（使用 multiprocessing.Pool）。提供 -1 以使用所有可用的 CPU 核心。或者提供一个类似映射的可调用对象，例如 multiprocessing.Pool.map 用于并行评估种群。此评估按 workers(func, iterable) 进行。如果 workers != 1，此选项将覆盖 updating 关键字为 updating='deferred'。如果 workers != 1，此选项将覆盖 vectorized 关键字。需要 func 是可序列化的。

Added in version 1.2.0.

约束{非线性约束, 线性约束, 边界}

对求解器的约束，除了由 bounds kwd 应用的那些之外。使用 Lampinen 的方法 [5]。

Added in version 1.4.0.

x0None 或类数组，可选

提供一个最小化的初始猜测。一旦种群被初始化，这个向量将替换第一个（最好的）成员。即使 init 给出了初始种群，这种替换也会进行。 x0.shape == (N,)。

Added in version 1.7.0.

完整性1-D 数组，可选

对于每个决策变量，一个布尔值指示该决策变量是否被限制为整数值。该数组被广播到 (N,)。如果任何决策变量被限制为整数，它们在抛光过程中不会被改变。仅使用位于上下限之间的整数值。如果上下限之间没有整数值，则引发 ValueError。

Added in version 1.9.0.

矢量化bool, 可选

如果 vectorized 为 True，func 会被传递一个 x 数组，其 x.shape == (N, S)，并且期望返回一个形状为 (S,) 的数组，其中 S 是要计算的解向量的数量。如果应用了约束，用于构建 Constraint 对象的每个函数都应该接受一个 x 数组，其 x.shape == (N, S)，并返回一个形状为 (M, S) 的数组，其中 M 是约束组件的数量。此选项是 workers 提供的并行化的替代方案，并且通过减少多次函数调用带来的解释器开销，可能有助于优化速度。如果 workers != 1，则忽略此关键字。此选项将覆盖 updating 关键字为 updating='deferred'。请参阅注释部分，以进一步讨论何时使用 'vectorized'，以及何时使用 'workers'。

Added in version 1.9.0.

返回:

res优化结果

优化结果表示为一个 OptimizeResult 对象。重要的属性包括：x 解数组，success 一个布尔标志，指示优化器是否成功退出，message 描述终止原因，population 种群中的解向量，以及 population_energies 目标函数在 population 中每个条目的值。参见 OptimizeResult 了解其他属性的描述。如果使用了 polish，并且通过抛光获得了更低的最低值，那么 OptimizeResult 还包含 jac 属性。如果最终解不满足应用的约束条件，success 将为 False。

注释

差分进化是一种基于随机种群的方法，适用于全局优化问题。在每次遍历种群时，算法通过与其他候选解混合来变异每个候选解，以创建一个试验候选解。有几种策略 [3] 用于创建试验候选解，这些策略在不同问题上表现不同。’best1bin’ 策略是许多系统的良好起点。在这种策略中，随机选择种群中的两个成员。它们的差异用于变异迄今为止的最佳成员（’best1bin’ 中的 ‘best’），即 \(x_0\)。

\[b' = x_0 + mutation * (x_{r_0} - x_{r_1})\]

然后构建一个试验向量。从随机选择的第 i 个参数开始，试验按模顺序填充参数，这些参数来自 b' 或原始候选者。选择使用 b' 还是原始候选者的参数是通过二项分布（’bin’ 在 ‘best1bin’ 中）进行的 - 生成一个 [0, 1) 范围内的随机数。如果这个数小于 recombination 常数，则从 b' 加载参数，否则从原始候选者加载。最后一个参数总是从 b' 加载。一旦构建了试验候选者，就会评估其适应度。如果试验比原始候选者更好，则取代其位置。如果它也比总体最佳候选者更好，则也会取代那个。

其他可用的策略在 Qiang 和 Mitchell (2014) [3] 中有概述。

\[ \begin{align}\begin{aligned}rand1* : b' = x_{r_0} + mutation*(x_{r_1} - x_{r_2})\\rand2* : b' = x_{r_0} + mutation*(x_{r_1} + x_{r_2} - x_{r_3} - x_{r_4})\\best1* : b' = x_0 + mutation*(x_{r_0} - x_{r_1})\\best2* : b' = x_0 + mutation*(x_{r_0} + x_{r_1} - x_{r_2} - x_{r_3})\\currenttobest1* : b' = x_i + mutation*(x_0 - x_i + x_{r_0} - x_{r_1})\\randtobest1* : b' = x_{r_0} + mutation*(x_0 - x_{r_0} + x_{r_1} - x_{r_2})\end{aligned}\end{align} \]

其中整数 \(r_0, r_1, r_2, r_3, r_4\) 是从区间 [0, NP) 中随机选择的，NP 是总人口大小，原始候选者的索引为 i。用户可以通过向 strategy 提供一个可调用对象来完全自定义试验候选者的生成。

为了提高找到全局最小值的机会，请使用更高的 popsize 值，以及更高的 mutation 值（和抖动），但降低 recombination 值。这会扩大搜索半径，但会减慢收敛速度。

默认情况下，最佳解向量在单次迭代中持续更新（updating='immediate'）。这是对原始差分进化算法的修改 [4]，可以使试验向量立即从改进的解中受益，从而加快收敛速度。要使用Storn和Price的原始行为，即每迭代一次更新最佳解一次，请设置 updating='deferred'。'deferred' 方法与并行化和向量化（'workers' 和 'vectorized' 关键字）兼容。这些方法可以通过更有效地利用计算机资源来提高最小化速度。'workers' 将计算分布到多个处理器上。默认情况下使用Python的 multiprocessing 模块，但也可以使用其他方法，例如在集群上使用的消息传递接口（MPI） [6] [7]。这些方法的开销（创建新进程等）可能很大，这意味着计算速度不一定随使用的处理器数量而线性增加。并行化最适合计算量大的目标函数。如果目标函数计算量较小，那么 'vectorized' 可能会有所帮助，因为它每迭代只调用一次目标函数，而不是多次调用所有种群成员；这样可以减少解释器的开销。

Added in version 0.15.0.

参考文献

[1]

差分进化，维基百科，http://en.wikipedia.org/wiki/Differential_evolution

[2]

Storn, R 和 Price, K, 差分进化 - 一种简单且高效的连续空间全局优化启发式方法, 《全局优化杂志》, 1997, 11, 341 - 359.

[3] (1,2)

Qiang, J., Mitchell, C., 一种用于全局优化的统一差分进化算法, 2014, https://www.osti.gov/servlets/purl/1163659

[4] (1,2)

Wormington, M., Panaccione, C., Matney, K. M., Bowen, D. K., - 使用遗传算法从X射线散射数据中表征结构, Phil. Trans. R. Soc. Lond. A, 1999, 357, 2827-2848

[5]

Lampinen, J., 差分进化算法的约束处理方法。2002年进化计算大会论文集。CEC’02（编号：02TH8600）。第2卷。IEEE, 2002年。

[6]

https://mpi4py.readthedocs.io/zh_CN/stable/

[7]

https://schwimmbad.readthedocs.io/en/latest/

示例

Try it in your browser!

让我们考虑最小化Rosenbrock函数的问题。该函数在 scipy.optimize 中的 rosen 中实现。

>>> import numpy as np
>>> from scipy.optimize import rosen, differential_evolution
>>> bounds = [(0,2), (0, 2), (0, 2), (0, 2), (0, 2)]
>>> result = differential_evolution(rosen, bounds)
>>> result.x, result.fun
(array([1., 1., 1., 1., 1.]), 1.9216496320061384e-19)

现在重复，但使用并行化。

>>> result = differential_evolution(rosen, bounds, updating='deferred',
...                                 workers=2)
>>> result.x, result.fun
(array([1., 1., 1., 1., 1.]), 1.9216496320061384e-19)

让我们进行一个约束最小化。

>>> from scipy.optimize import LinearConstraint, Bounds

我们添加约束，使得 x[0] 和 x[1] 的和必须小于或等于 1.9。 这是一个线性约束，可以写成 A @ x <= 1.9，其中 A = array([[1, 1]])。 这可以编码为一个 LinearConstraint 实例：

>>> lc = LinearConstraint([[1, 1]], -np.inf, 1.9)

使用 Bounds 对象指定限制。

>>> bounds = Bounds([0., 0.], [2., 2.])
>>> result = differential_evolution(rosen, bounds, constraints=lc,
...                                 seed=1)
>>> result.x, result.fun
(array([0.96632622, 0.93367155]), 0.0011352416852625719)

接下来找到Ackley函数（https://en.wikipedia.org/wiki/Test_functions_for_optimization）的最小值。

>>> def ackley(x):
...     arg1 = -0.2 * np.sqrt(0.5 * (x[0] ** 2 + x[1] ** 2))
...     arg2 = 0.5 * (np.cos(2. * np.pi * x[0]) + np.cos(2. * np.pi * x[1]))
...     return -20. * np.exp(arg1) - np.exp(arg2) + 20. + np.e
>>> bounds = [(-5, 5), (-5, 5)]
>>> result = differential_evolution(ackley, bounds, seed=1)
>>> result.x, result.fun
(array([0., 0.]), 4.440892098500626e-16)

Ackley 函数是以向量化方式编写的，因此可以使用 'vectorized' 关键字。注意函数评估次数的减少。

>>> result = differential_evolution(
...     ackley, bounds, vectorized=True, updating='deferred', seed=1
... )
>>> result.x, result.fun
(array([0., 0.]), 4.440892098500626e-16)

以下自定义策略函数模仿了 ‘best1bin’：

>>> def custom_strategy_fn(candidate, population, rng=None):
...     parameter_count = population.shape(-1)
...     mutation, recombination = 0.7, 0.9
...     trial = np.copy(population[candidate])
...     fill_point = rng.choice(parameter_count)
...
...     pool = np.arange(len(population))
...     rng.shuffle(pool)
...
...     # two unique random numbers that aren't the same, and
...     # aren't equal to candidate.
...     idxs = []
...     while len(idxs) < 2 and len(pool) > 0:
...         idx = pool[0]
...         pool = pool[1:]
...         if idx != candidate:
...             idxs.append(idx)
...
...     r0, r1 = idxs[:2]
...
...     bprime = (population[0] + mutation *
...               (population[r0] - population[r1]))
...
...     crossovers = rng.uniform(size=parameter_count)
...     crossovers = crossovers < recombination
...     crossovers[fill_point] = True
...     trial = np.where(crossovers, bprime, trial)
...     return trial

Go BackOpen In Tab