scipy.optimize.

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 是 1 維陣列形式的引數，而 args 是完全指定函數所需的任何其他固定參數的元組。 參數的數量 N 等於 len(x)。

bounds序列或 Bounds

變數的邊界。 有兩種指定邊界的方式

1. Bounds 類別的實例。

2. 每個 x 元素的 (min, max) 對，定義 func 最佳化引數的有限下限和上限。

邊界的總數用於確定參數的數量 N。 如果有邊界相等的參數，則自由參數的總數為 N - N_equal。

args元組，選用

完全指定目標函數所需的任何其他固定參數。

strategy{字串, 可呼叫物件}, 選用

要使用的差分進化策略。 應為下列其中之一

• ‘best1bin’

• ‘best1exp’

• ‘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 版本中變更：透過可呼叫物件自訂進化策略。

maxiter整數，選用

整個族群演化的最大世代數。 函數評估的最大次數（不含 polishing）為： (maxiter + 1) * popsize * (N - N_equal)

popsize整數，選用

用於設定總族群大小的乘數。 族群有 popsize * (N - N_equal) 個個體。 如果透過 init 關鍵字提供初始族群，則會覆寫此關鍵字。 當使用 init='sobol' 時，族群大小會計算為 popsize * (N - N_equal) 之後的下一個 2 的次方。

tol浮點數，選用

收斂的相對容差，當 np.std(population_energies) <= atol + tol * np.abs(np.mean(population_energies)) 時，求解停止，其中 atol 和 tol 分別是絕對和相對容差。

mutation浮點數或元組(浮點數, 浮點數)，選用

突變常數。 在文獻中，這也稱為差分權重，以 \(F\) 表示。 如果指定為浮點數，則應在 [0, 2) 範圍內。 如果指定為元組 (min, max)，則採用顫動。 顫動會在逐代基礎上隨機變更突變常數。 該世代的突變常數取自 U[min, max)。 顫動可以顯著加快收斂速度。 增加突變常數會增加搜尋半徑，但會減慢收斂速度。

recombination浮點數，選用

重組常數，應在 [0, 1] 範圍內。 在文獻中，這也稱為交叉機率，以 CR 表示。 增加此值允許更多突變體進入下一個世代，但有族群穩定性的風險。

rng{None, 整數, 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 版本中變更：作為從使用 numpy.random.RandomState 過渡到 numpy.random.Generator 的 SPEC-0007 過渡的一部分，此關鍵字已從 seed 變更為 rng。 在過渡期間，這兩個關鍵字將繼續運作，但一次只能指定一個。 在過渡期之後，使用 seed 關鍵字的函數呼叫將發出警告。 上面概述了 seed 和 rng 的行為，但在新程式碼中應僅使用 rng 關鍵字。

disp布林值，選用

在每次迭代時印出評估的 func。

callback可呼叫物件，選用

在每次迭代後呼叫的可呼叫物件。 具有簽名

callback(intermediate_result: OptimizeResult)

其中 intermediate_result 是一個關鍵字參數，包含一個 OptimizeResult，其屬性為 x 和 fun，即目前找到的最佳解和目標函數。 請注意，參數的名稱必須為 intermediate_result，才能將 OptimizeResult 傳遞至 callback。

callback 也支援類似以下的簽名

callback(x, convergence: float=val)

val 代表族群收斂的分數值。 當 val 大於 1.0 時，函數會停止。

內省用於判斷呼叫哪個簽名。

如果 callback 引發 StopIteration 或傳回 True，則全域最小化將會停止； 任何 polishing 仍會執行。

在 1.12.0 版本中變更：callback 接受 intermediate_result 關鍵字。

polish布林值，選用

如果為 True（預設值），則會使用 L-BFGS-B 方法的 scipy.optimize.minimize 在最後 polish 最佳族群成員，這可以稍微改善最小化。 如果正在研究受約束的問題，則會改用 trust-constr 方法。 對於具有許多約束的大型問題，由於 Jacobian 計算，polishing 可能需要很長時間。

在 1.15.0 版本中變更：如果指定了 workers，則會將包裝 func 的類別 map 的可呼叫物件提供給 minimize，而不是直接使用 func。 這可讓呼叫者控制調用實際執行的位置和方式。

init字串或類陣列，選用

指定要執行的族群初始化類型。 應為下列其中之一

• ‘latinhypercube’

• ‘sobol’

• ‘halton’

• ‘random’

• 指定初始族群的陣列。 陣列的形狀應為 (S, N)，其中 S 是總族群大小，N 是參數數量。

init 在使用前會被裁剪到 bounds。

預設值為 ‘latinhypercube’。 拉丁超立方取樣嘗試最大化可用參數空間的覆蓋率。

‘sobol’ 和 ‘halton’ 是更優越的替代方案，並且更能最大化參數空間。 ‘sobol’ 將強制執行初始族群大小，該大小計算為 popsize * (N - N_equal) 之後的下一個 2 的次方。 ‘halton’ 沒有任何要求，但效率稍低。 有關更多詳細資訊，請參閱 scipy.stats.qmc。

‘random’ 隨機初始化族群 - 這有一個缺點，即可能會發生叢集，從而阻止覆蓋整個參數空間。 例如，使用陣列指定族群可用於在已知解存在的位置建立一組密集的初始猜測，從而減少收斂時間。

atol浮點數，選用

收斂的絕對容差，當 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 版本中新增。

workers整數或類別 map 的可呼叫物件，選用

如果 workers 是整數，則族群會細分為 workers 個部分並行評估（使用 multiprocessing.Pool）。 提供 -1 以使用所有可用的 CPU 核心。 或者，提供類別 map 的可呼叫物件，例如 multiprocessing.Pool.map，以並行評估族群。 此評估會以 workers(func, iterable) 的形式執行。 如果 workers != 1，則此選項會將 updating 關鍵字覆寫為 updating='deferred'。 如果 workers != 1，則此選項會覆寫 vectorized 關鍵字。 需要 func 是可 pickle 的。

在 1.2.0 版本中新增。

constraints{NonLinearConstraint, LinearConstraint, Bounds}

求解器的約束，超出 bounds kwd 套用的約束。 使用 Lampinen 的方法 [5]。

在 1.4.0 版本中新增。

x0None 或類陣列，選用

為最小化提供初始猜測。 一旦初始化族群，此向量會取代第一個（最佳）成員。 即使 init 獲得初始族群，也會執行此取代。x0.shape == (N,)。

在 1.7.0 版本中新增。

integrality1 維陣列，選用

對於每個決策變數，一個布林值，指示決策變數是否受限於整數值。 陣列會廣播到 (N,)。 如果任何決策變數受限於整數，則在 polishing 期間不會變更它們。 僅使用介於下限和上限之間的整數值。 如果邊界之間沒有整數值，則會引發 ValueError。

在 1.9.0 版本中新增。

vectorized布林值，選用

如果 vectorized is True，則會將形狀為 x.shape == (N, S) 的 x 陣列傳送至 func，並且預期傳回形狀為 (S,) 的陣列，其中 S 是要計算的解向量的數量。 如果套用了約束，則用於建構 Constraint 物件的每個函數都應接受形狀為 x.shape == (N, S) 的 x 陣列，並傳回形狀為 (M, S) 的陣列，其中 M 是約束元件的數量。 此選項是 workers 提供的平行化的替代方案，並且可以透過減少多次函數呼叫的解譯器額外負荷來幫助提高最佳化速度。 如果 workers != 1，則會忽略此關鍵字。 此選項會將 updating 關鍵字覆寫為 updating='deferred'。 有關何時使用 'vectorized' 以及何時使用 'workers' 的更多討論，請參閱 notes 章節。

在 1.9.0 版本中新增。

傳回值:

resOptimizeResult

最佳化結果表示為 OptimizeResult 物件。 重要屬性包括： x 解陣列、success 布林值旗標，指示最佳化器是否成功退出、message 描述終止原因、population 族群中存在的解向量，以及 population_energies population 中每個條目的目標函數值。 有關其他屬性的描述，請參閱 OptimizeResult。 如果採用了 polish，並且透過 polishing 獲得了較低的最小值，則 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]

Differential evolution, Wikipedia, 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.

[6]

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

[7]

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

範例

在瀏覽器中試試看！

讓我們考慮最小化 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

返回在新分頁中開啟