differential_evolution#
- scipy.optimize.differential_evolution(func, bounds, args=(), strategy='best1bin', maxiter=1000, popsize=15, tol=0.01, mutation=(0.5, 1), recombination=0.7, rng=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]。
- 参数:
- func可调用对象
要最小化的目标函数。必须是 `
f(x, *args)` 的形式,其中 `
x
` 是一个一维数组形式的参数,`args
` 是一个元组,包含完全指定函数所需的任何额外固定参数。参数的数量 N 等于 `len(x)
`。- bounds序列或
Bounds
变量的边界。有两种指定边界的方式:
Bounds
类的实例。`
(min, max)
` 对,用于 `x
` 中的每个元素,定义了 `func` 优化参数的有限下限和上限。
边界的总数用于确定参数的数量 N。如果存在边界相等的参数,则自由参数的总数是 `
N - N_equal
`。- args元组, 可选
完全指定目标函数所需的任何额外固定参数。
- strategy{str, 可调用对象}, 可选
要使用的差分进化策略。应为以下之一:
‘best1bin’
‘best1exp’
‘rand1bin’
‘rand1exp’
‘rand2bin’
‘rand2exp’
‘randtobest1bin’
‘randtobest1exp’
‘currenttobest1bin’
‘currenttobest1exp’
‘best2exp’
‘best2bin’
默认值为 'best1bin'。可能实现的策略在“注释”中列出。另外,可以通过提供一个构造试验向量的可调用对象来定制差分进化策略。该可调用对象必须具有 `
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(population_energies) <= atol + tol * np.abs(np.mean(population_energies))
` 时停止求解,其中 `atol` 和 `tol` 分别是绝对容差和相对容差。- mutationfloat 或 tuple(float, float), 可选
变异常数。在文献中,这也被称为差分权重,表示为 \(F\)。如果指定为浮点数,它应该在 [0, 2) 范围内。如果指定为元组 `
(min, max)`,则采用抖动。抖动会逐代随机改变变异常数。该代次的变异常数取自 `
U[min, max)
`。抖动可以显著加快收敛速度。增加变异常数会增加搜索半径,但会减慢收敛。- recombinationfloat, 可选
重组常数,应在 [0, 1] 范围内。在文献中,这也被称为交叉概率,表示为 CR。增加此值允许更多变异体进入下一代,但存在种群稳定性的风险。
- rng{None, int,
numpy.random.Generator
}, 可选 如果 `rng` 作为关键字参数传入,则除 `
numpy.random.Generator
` 之外的类型将传递给 `numpy.random.default_rng
` 以实例化一个 `Generator
`。如果 `rng` 已经是 `Generator
` 实例,则使用所提供的实例。指定 `rng` 可获得可重复的函数行为。如果此参数按位置传递,或者 `seed` 作为关键字参数传递,则应用参数 `seed` 的传统行为
如果 `seed` 为 None(或 `
numpy.random
`),则使用 `numpy.random.RandomState
` 单例。如果 `seed` 是一个整数,则使用一个新的 `
RandomState
` 实例,以 `seed` 作为种子。如果 `seed` 已经是 `
Generator
` 或 `RandomState
` 实例,则使用该实例。
版本 1.15.0 中的变化: 作为 SPEC-007 从使用 `
numpy.random.RandomState
` 转换为 `numpy.random.Generator
` 的一部分,此关键字已从 `seed` 更改为 `rng`。在过渡期内,两个关键字将继续有效,但一次只能指定一个。过渡期后,使用 `seed` 关键字的函数调用将发出警告。上面概述了 `seed` 和 `rng` 的行为,但在新代码中只应使用 `rng` 关键字。- dispbool, 可选
在每次迭代时打印评估的 `func`。
- callback可调用对象, 可选
每次迭代后调用的可调用对象。具有以下签名:
callback(intermediate_result: OptimizeResult)
其中 `
intermediate_result
` 是一个关键字参数,包含一个 `OptimizeResult
` 对象,其属性 `x
` 和 `fun
` 分别表示到目前为止找到的最佳解和目标函数。请注意,参数名称必须是 `intermediate_result
`,以便将 `OptimizeResult
` 传递给回调。回调也支持以下签名:
callback(x, convergence: float=val)
`
val
` 表示种群收敛的分数值。当 `val
` 大于 `1.0
` 时,函数停止。通过自省来确定调用哪个签名。
如果回调引发 `
StopIteration
` 或返回 `True
`,全局最小化将停止;任何精修仍将进行。版本 1.12.0 中的变化: 回调接受 `
intermediate_result
` 关键字。- polishbool, 可选
如果为 True(默认值),则使用 `
scipy.optimize.minimize
` 的 `L-BFGS-B` 方法在结束时对最佳种群成员进行精修,这可以稍微改善最小化结果。如果正在研究一个受约束的问题,则改用 `trust-constr` 方法。对于具有许多约束的大问题,由于雅可比计算,精修可能需要很长时间。版本 1.15.0 中的变化: 如果指定了 `workers`,则将包装 `func` 的类 map 可调用对象提供给 `
minimize
`,而不是直接使用 `func`。这允许调用者控制实际运行调用的方式和位置。- initstr 或 类数组对象, 可选
指定执行哪种类型的种群初始化。应为以下之一:
‘latinhypercube’
‘sobol’
‘halton’
‘random’
指定初始种群的数组。该数组的形状应为 `
(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` 分别是绝对容差和相对容差。- updating{‘immediate’, ‘deferred’}, 可选
如果为 `
'immediate'
`,则在单代内连续更新最佳解向量[4]。这可以加快收敛速度,因为试验向量可以利用最佳解的持续改进。如果为 `'deferred'
`,则每代更新一次最佳解向量。只有 `'deferred'
` 兼容并行化或向量化,并且 `workers` 和 `vectorized` 关键字可以覆盖此选项。版本 1.2.0 新增。
- workersint 或 类 map 可调用对象, 可选
如果 `workers` 是一个整数,则种群被细分为 `workers` 个部分并并行评估(使用 `
multiprocessing.Pool
`)。提供 -1 以使用所有可用的 CPU 核心。或者提供一个类 map 可调用对象,例如 `multiprocessing.Pool.map` 来并行评估种群。此评估以 `workers(func, iterable)
` 的形式执行。如果 `workers != 1
`,此选项将覆盖 `updating` 关键字,使其变为 `updating='deferred'
`。如果 `workers != 1
`,此选项将覆盖 `vectorized` 关键字。要求 `func` 可序列化(pickleable)。版本 1.2.0 新增。
- constraints{NonLinearConstraint, LinearConstraint, Bounds}
求解器的约束,超出 `bounds` 关键字应用的约束。使用 Lampinen 的方法 [5]。
版本 1.4.0 新增。
- x0None 或 类数组对象, 可选
为最小化提供初始猜测。种群初始化后,此向量将替换第一个(最佳)成员。即使 `init` 给出了初始种群,也会进行此替换。`
x0.shape == (N,)
`。版本 1.7.0 新增。
- integrality一维数组, 可选
对于每个决策变量,一个布尔值指示该决策变量是否被约束为整数值。该数组被广播为 `
(N,)
`。如果任何决策变量被约束为整数,它们在精修过程中不会改变。只使用位于下限和上限之间的整数值。如果边界之间没有整数值,则会引发 `ValueError`。版本 1.9.0 新增。
- vectorizedbool, 可选
如果 `
vectorized is True
`,则 `func` 将接收一个形状为 `x.shape == (N, S)
` 的 `x` 数组,并期望返回一个形状为 `(S,)
` 的数组,其中 `S` 是要计算的解向量的数量。如果应用了约束,则用于构建 `Constraint` 对象的每个函数都应接受一个形状为 `x.shape == (N, S)
` 的 `x` 数组,并返回一个形状为 `(M, S)
` 的数组,其中 `M` 是约束组件的数量。此选项是 `workers` 提供的并行化的替代方案,通过减少多次函数调用带来的解释器开销,可能有助于提高优化速度。如果 `workers != 1
`,则此关键字将被忽略。此选项将覆盖 `updating` 关键字,使其变为 `updating='deferred'
`。有关何时使用 `'vectorized'
` 以及何时使用 `'workers'
` 的进一步讨论,请参见注释部分。版本 1.9.0 新增。
- 返回:
- resOptimizeResult
优化结果表示为 `
OptimizeResult
` 对象。重要属性包括:`x
` 解数组,`success
` 一个布尔标志,指示优化器是否成功退出,`message
` 描述终止原因,`population
` 种群中存在的解向量,以及 `population_energies
` 种群中每个成员的目标函数值。有关其他属性的描述,请参见 `OptimizeResult
`。如果采用了 `polish` 并且通过精修获得了更低的最小值,则 OptimizeResult 还包含 `jac
` 属性。如果最终解不满足所施加的约束,则 `success
` 将为 `False`。
注释
差分进化是一种基于随机种群的方法,适用于全局优化问题。在每次遍历种群时,算法通过与其它候选解混合来变异每个候选解,从而创建一个试验候选解。有几种策略[3]用于创建试验候选解,其中一些更适合某些问题。'best1bin' 策略是许多系统的良好起点。在此策略中,随机选择两个种群成员。它们的差值用于变异迄今为止的最佳成员('best1bin' 中的 'best'),即 \(x_0\):
\[b' = x_0 + F \cdot (x_{r_0} - x_{r_1})\]其中 \(F\) 是 `mutation` 参数。然后构造一个试验向量。从一个随机选择的第 i 个参数开始,试验向量按顺序(取模)填充来自 `
b'
` 或原始候选的参数。选择使用 `b'
` 还是原始候选是基于二项式分布('best1bin' 中的 'bin')——生成一个 [0, 1) 之间的随机数。如果这个数小于 `recombination` 常数,则参数从 `b'
` 加载,否则从原始候选加载。最后一个参数总是从 `b'
` 加载。一旦构建了试验候选,就会评估其适应度。如果试验优于原始候选,则它取代原始候选。如果它也优于最佳的整体候选,它也会取代该候选。其他可用策略在 Qiang 和 Mitchell (2014) [3] 中概述。
rand1
: \(b' = x_{r_0} + F \cdot (x_{r_1} - x_{r_2})\)rand2
: \(b' = x_{r_0} + F \cdot (x_{r_1} + x_{r_2} - x_{r_3} - x_{r_4})\)best1
: \(b' = x_0 + F \cdot (x_{r_0} - x_{r_1})\)best2
: \(b' = x_0 + F \cdot (x_{r_0} + x_{r_1} - x_{r_2} - x_{r_3})\)currenttobest1
: \(b' = x_i + F \cdot (x_0 - x_i + x_{r_0} - x_{r_1})\)randtobest1
: \(b' = x_{r_0} + F \cdot (x_0 - x_{r_0} + x_{r_1} - x_{r_2})\)
其中整数 \(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'
` 可能有助于通过每迭代只调用一次目标函数,而不是对所有种群成员多次调用,从而减少解释器开销。版本 0.15.0 新增。
参考文献
[1]差分进化,维基百科,http://en.wikipedia.org/wiki/Differential_evolution
[2]Storn, R and Price, K, Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, 1997, 11, 341 - 359。
[3] (1,2)Qiang, J., Mitchell, C., A Unified Differential Evolution Algorithm for Global Optimization, 2014, https://www.osti.gov/servlets/purl/1163659
[4] (1,2)Wormington, M., Panaccione, C., Matney, K. M., Bowen, D. K., - Characterization of structures from X-ray scattering data using genetic algorithms, Phil. Trans. R. Soc. Lond. A, 1999, 357, 2827-2848
[5]Lampinen, J., A constraint handling approach for the differential evolution algorithm. Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No. 02TH8600). Vol. 2. IEEE, 2002。
示例
让我们考虑最小化 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, ... rng=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, rng=1) >>> result.x, result.fun (array([0., 0.]), 4.440892098500626e-16)
Ackley 函数以向量化方式编写,因此可以使用 `
'vectorized'
` 关键字。请注意函数评估次数减少了。>>> result = differential_evolution( ... ackley, bounds, vectorized=True, updating='deferred', rng=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