Ctrl+K
scipy.optimize.

basinhopping#

scipy.optimize.basinhopping(func, x0, niter=100, T=1.0, stepsize=0.5, minimizer_kwargs=None, take_step=None, accept_test=None, callback=None, interval=50, disp=False, niter_success=None, rng=None, *, target_accept_rate=0.5, stepwise_factor=0.9)[原始碼]#

使用盆地跳躍演算法尋找函數的全域最小值。

盆地跳躍是一種雙階段方法，它結合了全域步進演算法和每一步的局部最小化。它旨在模仿原子簇能量最小化的自然過程，對於具有「漏斗狀但崎嶇」能量地形的類似問題效果良好 [5]。

由於步進、步進接受和最小化方法都是可自訂的，因此此函數也可用於實現其他雙階段方法。

參數:
func可呼叫物件 f(x, *args)

要最佳化的函數。args 可以作為選用項目在 minimizer_kwargs 字典中傳遞

x0array_like

初始猜測值。

niterinteger，選用項目

盆地跳躍迭代的次數。將總共有 niter + 1 次局部最小化器的執行。

Tfloat，選用項目

接受或拒絕標準的「溫度」參數。較高的「溫度」表示將接受函數值中較大的跳躍。為了獲得最佳結果，T 應與局部最小值之間的間隔（以函數值表示）相當。

stepsizefloat，選用項目

隨機位移中使用的最大步長。

minimizer_kwargsdict，選用項目

要傳遞給局部最小化器的額外關鍵字引數 scipy.optimize.minimize 一些重要的選項可能是

methodstr

最小化方法（例如 "L-BFGS-B"）

argstuple

傳遞給目標函數 (func) 及其導數（Jacobian，Hessian）的額外引數。

take_step可呼叫物件 take_step(x)，選用項目

用此常式替換預設的步進常式。預設的步進常式是座標的隨機位移，但其他步進演算法可能更適合某些系統。take_step 可以選擇性地具有屬性 take_step.stepsize。如果此屬性存在，則 basinhopping 將調整 take_step.stepsize 以嘗試最佳化全域最小值搜尋。

accept_test可呼叫物件，accept_test(f_new=f_new, x_new=x_new, f_old=fold, x_old=x_old)，選用項目

定義一個測試，該測試將用於判斷是否接受該步驟。這將與基於「溫度」T 的 Metropolis 測試一起使用。可接受的回傳值為 True、False 或 "force accept"。如果任何測試回傳 False，則拒絕該步驟。如果是後者，則這將覆蓋任何其他測試，以便接受該步驟。例如，這可用於強制從 basinhopping 陷入的局部最小值中逃脫。

callback可呼叫物件，callback(x, f, accept)，選用項目

一個回呼函數，將為找到的所有最小值呼叫。 x 和 f 是試驗最小值的座標和函數值，而 accept 是該最小值是否被接受。例如，這可用於儲存找到的最低 N 個最小值。此外，callback 可用於透過選擇性地回傳 True 來指定使用者定義的停止條件，以停止 basinhopping 常式。

intervalinteger，選用項目

更新 stepsize 頻率的間隔

dispbool，選用項目

設定為 True 以列印狀態訊息

niter_successinteger，選用項目

如果全域最小值候選者在此迭代次數內保持不變，則停止執行。

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

產生的隨機數僅影響預設的 Metropolis accept_test 和預設的 take_step。如果您提供自己的 take_step 和 accept_test，並且這些函數使用隨機數生成，則這些函數負責其隨機數生成器的狀態。

target_accept_ratefloat，選用項目

用於調整 stepsize 的目標接受率。如果目前的接受率大於目標，則 stepsize 會增加。否則，它會減少。範圍是 (0, 1)。預設值為 0.5。

在 1.8.0 版本中新增。

stepwise_factorfloat，選用項目

每次更新時，stepsize 都會乘以或除以這個逐步因子。範圍是 (0, 1)。預設值為 0.9。

在 1.8.0 版本中新增。

回傳值:
resOptimizeResult

最佳化結果表示為 OptimizeResult 物件。重要的屬性包括：x 解答陣列，fun 解答處的函數值，以及 message 描述終止原因。最低最小值處選定的最小化器回傳的 OptimizeResult 物件也包含在此物件中，並且可以透過 lowest_optimization_result 屬性存取。請參閱 OptimizeResult 以取得其他屬性的描述。

另請參閱

minimize

為每個盆地跳躍步驟呼叫一次的局部最小化函數。minimizer_kwargs 會傳遞給此常式。

註解

盆地跳躍是一種隨機演算法，它嘗試尋找一個或多個變數的光滑純量函數的全域最小值 [1] [2] [3] [4]。目前形式的演算法由 David Wales 和 Jonathan Doye 描述 [2] http://www-wales.ch.cam.ac.uk/。

該演算法是迭代的，每個週期都由以下特徵組成

  1. 座標的隨機擾動

  2. 局部最小化

  3. 根據最小化的函數值接受或拒絕新座標

此處使用的接受測試是標準蒙地卡羅演算法的 Metropolis 標準，儘管還有許多其他可能性 [3]。

這種全域最小化方法已被證明對於物理和化學中的各種問題非常有效。當函數具有許多被大障礙分隔的最小值時，它特別有用。請參閱 劍橋叢集資料庫，以取得主要使用盆地跳躍最佳化的分子系統資料庫。此資料庫包含超過 300 個自由度的最小化問題。

請參閱免費軟體程式 GMIN，以取得盆地跳躍的 Fortran 實作。此實作具有上述程序的許多變體，包括更進階的步進演算法和替代接受標準。

對於隨機全域最佳化，無法確定是否真的找到了真正的全域最小值。相反地，作為一致性檢查，可以從許多不同的隨機起點執行該演算法，以確保每個範例中找到的最低最小值已收斂到全域最小值。因此，預設情況下，basinhopping 將僅執行迭代次數 niter 並回傳找到的最低最小值。使用者有責任確保這實際上是全域最小值。

選擇 stepsize：這是 basinhopping 中的關鍵參數，並且取決於要解決的問題。步長在每個維度中從 x0-stepsize 到 x0+stepsize 的區域均勻選擇。理想情況下，它應與要最佳化的函數的局部最小值之間的典型間隔（以引數值表示）相當。預設情況下，basinhopping 將調整 stepsize 以尋找最佳值，但這可能需要多次迭代。如果您為 stepsize 設定合理的初始值，您將獲得更快的結果。

選擇 T：參數 T 是 Metropolis 標準中使用的「溫度」。如果 func(xnew) < func(xold)，則始終接受盆地跳躍步驟。否則，它們以機率被接受

exp( -(func(xnew) - func(xold)) / T )

因此，為了獲得最佳結果，T 應與局部最小值之間典型差異（以函數值表示）相當。（局部最小值之間「牆」的高度無關緊要。）

如果 T 為 0，則演算法變為單調盆地跳躍，其中所有增加能量的步驟都被拒絕。

在 0.12.0 版本中新增。

參考文獻

[1]

Wales, David J. 2003, Energy Landscapes, Cambridge University Press, Cambridge, UK.

[2] (1,2)

Wales, D J, 和 Doye J P K, Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms. Journal of Physical Chemistry A, 1997, 101, 5111.

[3] (1,2)

Li, Z. 和 Scheraga, H. A., Monte Carlo-minimization approach to the multiple-minima problem in protein folding, Proc. Natl. Acad. Sci. USA, 1987, 84, 6611.

[4]

Wales, D. J. 和 Scheraga, H. A., Global optimization of clusters, crystals, and biomolecules, Science, 1999, 285, 1368.

[5]

Olson, B., Hashmi, I., Molloy, K., 和 Shehu1, A., Basin Hopping as a General and Versatile Optimization Framework for the Characterization of Biological Macromolecules, Advances in Artificial Intelligence, Volume 2012 (2012), Article ID 674832, DOI:10.1155/2012/674832

範例

以下範例是一個一維最小化問題，在拋物線上疊加了許多局部最小值。

>>> import numpy as np
>>> from scipy.optimize import basinhopping
>>> func = lambda x: np.cos(14.5 * x - 0.3) + (x + 0.2) * x
>>> x0 = [1.]

Basinhopping 在內部使用局部最小化演算法。我們將使用參數 minimizer_kwargs 來告訴 basinhopping 要使用哪個演算法以及如何設定該最小化器。此參數將傳遞給 scipy.optimize.minimize。

>>> minimizer_kwargs = {"method": "BFGS"}
>>> ret = basinhopping(func, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200)
>>> # the global minimum is:
>>> ret.x, ret.fun
-0.1951, -1.0009

接下來考慮一個二維最小化問題。此外，這次我們將使用梯度資訊來顯著加速搜尋。

>>> def func2d(x):
...     f = np.cos(14.5 * x[0] - 0.3) + (x[1] + 0.2) * x[1] + (x[0] +
...                                                            0.2) * x[0]
...     df = np.zeros(2)
...     df[0] = -14.5 * np.sin(14.5 * x[0] - 0.3) + 2. * x[0] + 0.2
...     df[1] = 2. * x[1] + 0.2
...     return f, df

我們也將使用不同的局部最小化演算法。此外，我們必須告訴最小化器我們的函數回傳能量和梯度 (Jacobian)。

>>> minimizer_kwargs = {"method":"L-BFGS-B", "jac":True}
>>> x0 = [1.0, 1.0]
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200)
>>> print("global minimum: x = [%.4f, %.4f], f(x) = %.4f" % (ret.x[0],
...                                                           ret.x[1],
...                                                           ret.fun))
global minimum: x = [-0.1951, -0.1000], f(x) = -1.0109

這是一個使用自訂步進常式的範例。想像一下，您希望第一個座標的步長大於其餘座標的步長。這可以像這樣實作

>>> class MyTakeStep:
...    def __init__(self, stepsize=0.5):
...        self.stepsize = stepsize
...        self.rng = np.random.default_rng()
...    def __call__(self, x):
...        s = self.stepsize
...        x[0] += self.rng.uniform(-2.*s, 2.*s)
...        x[1:] += self.rng.uniform(-s, s, x[1:].shape)
...        return x

由於 MyTakeStep.stepsize 存在，basinhopping 將調整 stepsize 的大小以最佳化搜尋。我們將使用與之前相同的二維函數

>>> mytakestep = MyTakeStep()
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200, take_step=mytakestep)
>>> print("global minimum: x = [%.4f, %.4f], f(x) = %.4f" % (ret.x[0],
...                                                           ret.x[1],
...                                                           ret.fun))
global minimum: x = [-0.1951, -0.1000], f(x) = -1.0109

現在，讓我們做一個使用自訂回呼函數的範例，該函數列印找到的每個最小值的值

>>> def print_fun(x, f, accepted):
...         print("at minimum %.4f accepted %d" % (f, int(accepted)))

這次我們將僅執行 10 個 basinhopping 步驟。

>>> rng = np.random.default_rng()
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=10, callback=print_fun, rng=rng)
at minimum 0.4159 accepted 1
at minimum -0.4317 accepted 1
at minimum -1.0109 accepted 1
at minimum -0.9073 accepted 1
at minimum -0.4317 accepted 0
at minimum -0.1021 accepted 1
at minimum -0.7425 accepted 1
at minimum -0.9073 accepted 1
at minimum -0.4317 accepted 0
at minimum -0.7425 accepted 1
at minimum -0.9073 accepted 1

在 -1.0109 處的最小值實際上是全域最小值，已在第 8 次迭代中找到。

在本頁中