scipy.optimize.

direct#

scipy.optimize.direct(func, bounds, *, args=(), eps=0.0001, maxfun=None, maxiter=1000, locally_biased=True, f_min=-inf, f_min_rtol=0.0001, vol_tol=1e-16, len_tol=1e-06, callback=None)[source]#

使用 DIRECT 演算法尋找函數的全域最小值。

參數:

func可呼叫物件 (callable)

要最小化的目標函數。 func(x, *args) -> float 其中 x 是一個形狀為 (n,) 的 1 維陣列，而 args 是一個 tuple，包含完整指定函數所需的固定參數。

bounds序列或 Bounds

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

Bounds 類別的實例。
用於 x 中每個元素的 (min, max) 配對。

argstuple，選用

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

epsfloat，選用

目前最佳超矩形與下一個可能最佳的待分割超矩形之間，目標函數值的最小所需差異。因此，eps 作為局部搜尋和全域搜尋之間的權衡：值越小，搜尋越局部。預設值為 1e-4。

maxfunint 或 None，選用

目標函數評估次數的近似上限。如果為 None，將自動設定為 1000 * N，其中 N 代表維度數量。如有必要，將會限制上限，以將 DIRECT 的 RAM 使用量限制在大約 1GiB。這只會在非常高維度的問題和過大的 max_fun 時發生。預設值為 None。

maxiterint，選用

最大迭代次數。預設值為 1000。

locally_biasedbool，選用

如果為 True (預設值)，則使用演算法的局部偏差變體，稱為 DIRECT_L。如果為 False，則使用原始的無偏差 DIRECT 演算法。對於具有許多局部最小值 (local minima) 的困難問題，建議使用 False。

f_minfloat，選用

全域最佳解的函數值。僅在已知全域最佳解時才設定此值。預設值為 -np.inf，因此停用此終止條件。

f_min_rtolfloat，選用

一旦目前最佳最小值 f 與提供的全域最小值 f_min 之間的相對誤差小於 f_min_rtol，則終止最佳化。此參數僅在也設定了 f_min 時使用。必須介於 0 和 1 之間。預設值為 1e-4。

vol_tolfloat，選用

一旦包含最低函數值的超矩形的體積小於完整搜尋空間的 vol_tol，則終止最佳化。必須介於 0 和 1 之間。預設值為 1e-16。

len_tolfloat，選用

如果 locally_biased=True，則一旦包含最低函數值的超矩形的標準化最大邊長的一半小於 len_tol，則終止最佳化。如果 locally_biased=False，則一旦包含最低函數值的超矩形的標準化對角線的一半小於 len_tol，則終止最佳化。必須介於 0 和 1 之間。預設值為 1e-6。

callback可呼叫物件 (callable)，選用

簽名為 callback(xk) 的回呼函數，其中 xk 代表目前為止找到的最佳函數值。

回傳值:

resOptimizeResult: 最佳化結果，表示為 OptimizeResult 物件。重要的屬性包括：x 解答陣列，success 布林值旗標，指示最佳化器是否成功退出，以及 message，描述終止的原因。請參閱 OptimizeResult 以取得其他屬性的描述。

註解

DIviding RECTangles (DIRECT) 是一種確定性的全域最佳化演算法，能夠最小化黑箱函數，其變數受限於下限和上限約束，方法是在搜尋空間中對潛在解進行採樣 [1]。該演算法首先將搜尋空間正規化為 n 維單位超立方體。它在這個超立方體的中心以及另外 2n 個點（n 是變數的數量）對函數進行採樣，每個座標方向上有 2 個點。使用這些函數值，DIRECT 然後將域劃分為超矩形，每個超矩形都恰好有一個採樣點作為其中心。在每次迭代中，DIRECT 使用 eps 參數（預設值為 1e-4）選擇一些現有的超矩形以進一步劃分。此劃分過程會持續進行，直到超過允許的最大迭代次數或最大函數評估次數，或者包含目前為止找到的最小值的超矩形變得足夠小。如果指定了 f_min，則一旦在此函數值達到相對容差範圍內，最佳化將停止。預設情況下使用 DIRECT 的局部偏差變體（最初稱為 DIRECT_L）[2]。它使搜尋更偏向局部，並且對於只有少數局部最小值的情況更有效率。

關於終止條件的註解：vol_tol 指的是包含目前為止找到的最低函數值的超矩形的體積。此體積隨著問題維度的增加呈指數級下降。因此，應減小 vol_tol 以避免在較高維度時演算法過早終止。這不適用於 len_tol：它指的是最大邊長的一半（對於 locally_biased=True）或超矩形的對角線的一半（對於 locally_biased=False）。

此程式碼基於 Gablonsky 等人在 https://ctk.math.ncsu.edu/SOFTWARE/DIRECTv204.tar.gz 提供的 DIRECT 2.0.4 Fortran 程式碼。此原始版本最初透過 f2c 轉換，然後由 Steven G. Johnson 於 2007 年 8 月為 NLopt 專案清理和重組。direct 函數包裝了 C 實作。

在 1.9.0 版本中加入。

參考文獻

[1]

Jones, D.R., Perttunen, C.D. & Stuckman, B.E. Lipschitzian optimization without the Lipschitz constant. J Optim Theory Appl 79, 157-181 (1993).

[2]

Gablonsky, J., Kelley, C. A Locally-Biased form of the DIRECT Algorithm. Journal of Global Optimization 21, 27-37 (2001).

範例

以下範例是一個具有四個局部最小值的 2 維問題：最小化 Styblinski-Tang 函數 (https://en.wikipedia.org/wiki/Test_functions_for_optimization)。

>>> from scipy.optimize import direct, Bounds
>>> def styblinski_tang(pos):
...     x, y = pos
...     return 0.5 * (x**4 - 16*x**2 + 5*x + y**4 - 16*y**2 + 5*y)
>>> bounds = Bounds([-4., -4.], [4., 4.])
>>> result = direct(styblinski_tang, bounds)
>>> result.x, result.fun, result.nfev
array([-2.90321597, -2.90321597]), -78.3323279095383, 2011

已找到正確的全域最小值，但函數評估次數非常多 (2011)。放寬終止容差 vol_tol 和 len_tol 可用於更早停止 DIRECT。

>>> result = direct(styblinski_tang, bounds, len_tol=1e-3)
>>> result.x, result.fun, result.nfev
array([-2.9044353, -2.9044353]), -78.33230330754142, 207