shgo#
- scipy.optimize.shgo(func, bounds, args=(), constraints=None, n=100, iters=1, callback=None, minimizer_kwargs=None, options=None, sampling_method='simplicial', *, workers=1)[source]#
使用 SHG 最佳化演算法尋找函數的全域最小值。
SHGO 代表 “單純同調全域最佳化 (simplicial homology global optimization)”。
- 參數:
- funccallable
要最小化的目標函數。 形式必須為
f(x, *args)，其中x是 1-D 陣列形式的引數，而args是一個元組，包含完整指定函數所需的任何其他固定參數。- boundssequence 或
Bounds 變數的邊界。 有兩種方式可以指定邊界
Bounds類別的實例。每個 x 元素的
(min, max)配對序列。
- argstuple，選用
完整指定目標函數所需的任何其他固定參數。
- constraints{Constraint, dict} 或 {Constraint, dict} 列表，選用
約束條件定義。 僅適用於 COBYLA、COBYQA、SLSQP 和 trust-constr。 有關指定約束條件的更多詳細資訊，請參閱教學文件 [5]。
注意
目前只有 COBYLA、COBYQA、SLSQP 和 trust-constr 本地最小化方法支援約束條件引數。 如果本地最佳化問題中使用的
constraints序列未在minimizer_kwargs中定義，並且使用了約束方法，則將使用全域constraints。（在minimizer_kwargs中定義constraints序列表示不會新增constraints，因此如果需要新增等式約束等等，則constraints中的不等式函數也需要新增到minimizer_kwargs中）。 COBYLA 僅支援不等式約束。在版本 1.11.0 中變更:
constraints接受NonlinearConstraint、LinearConstraint。- nint，選用
用於建構單純複形的取樣點數量。 對於預設的
simplicial取樣方法，將產生 2**dim + 1 個取樣點，而不是預設的n=100。 對於所有其他指定值，將產生 n 個取樣點。 對於sobol、halton和其他任意 sampling_methods，將產生n=100或其他指定數量的取樣點。- itersint，選用
用於建構單純複形的迭代次數。 預設值為 1。
- callbackcallable，選用
在每次迭代後呼叫，形式為
callback(xk)，其中xk是目前的參數向量。- minimizer_kwargsdict，選用
要傳遞給最小化器
scipy.optimize.minimize的額外關鍵字引數。 一些重要的選項可能是- methodstr
最小化方法。 如果未給定，則根據問題是否具有約束條件或邊界，選擇 BFGS、L-BFGS-B、SLSQP 之一。
- argstuple
傳遞給目標函數 (
func) 及其導數（雅可比矩陣、黑塞矩陣）的額外引數。- optionsdict，選用
請注意，預設情況下，容差指定為
{ftol: 1e-12}
- optionsdict，選用
求解器選項的字典。 為全域常式指定的許多選項也會傳遞給
scipy.optimize.minimize常式。 也傳遞給本地常式的選項標記為 “(L)”。停止條件，如果滿足任何指定的條件，演算法將終止。 但是，預設演算法不需要指定任何條件
- maxfevint (L)
可行域中函數評估的最大次數。（請注意，只有支援此選項的方法才能在精確指定的確切值處終止常式。 否則，條件僅會在全域迭代期間終止）
- f_minfloat
指定最小目標函數值（如果已知）。
- f_tolfloat
停止條件中 f 值的精確度目標。 請注意，如果全域常式中的取樣點在此容差範圍內，全域常式也會終止。
- maxiterint
要執行的最大迭代次數。
- maxevint
要執行的最大取樣評估次數（包括在不可行點中搜尋）。
- maxtimefloat
允許的最大處理執行時間
- minhgrdint
最小同調群秩差。 目標函數的同調群在每次迭代期間（近似地）計算。 此群的秩與目標函數中局部凸子域的數量具有一對一的對應關係（在足夠的取樣點之後，每個子域都包含唯一的全域最小值）。 如果 hgr 的差異在指定的
maxhgrd次迭代之間為 0，則演算法將終止。
目標函數知識
- symmetrylist 或 bool
指定目標函數是否包含對稱變數。 在完全對稱的情況下，搜尋空間（以及效能）最多可減少 O(n!) 倍。 如果指定 True，則所有變數都將設定為與第一個變數對稱。 預設設定為 False。
例如 f(x) = (x_1 + x_2 + x_3) + (x_4)**2 + (x_5)**2 + (x_6)**2
在此方程式中，x_2 和 x_3 與 x_1 對稱，而 x_5 和 x_6 與 x_4 對稱，這可以指定給求解器為
symmetry = [0, # Variable 1 0, # symmetric to variable 1 0, # symmetric to variable 1 3, # Variable 4 3, # symmetric to variable 4 3, # symmetric to variable 4 ]
- jacbool 或 callable，選用
目標函數的雅可比矩陣（梯度）。 僅適用於 CG、BFGS、Newton-CG、L-BFGS-B、TNC、SLSQP、dogleg、trust-ncg。 如果
jac是布林值且為 True，則假定fun除了目標函數外還會傳回梯度。 如果為 False，則將以數值方式估計梯度。jac也可以是傳回目標函數梯度的 callable。 在這種情況下，它必須接受與fun相同的引數。（自動傳遞給scipy.optimize.minimize）- hess, hesspcallable，選用
目標函數的黑塞矩陣（二階導數矩陣）或目標函數的黑塞矩陣乘以任意向量 p。 僅適用於 Newton-CG、dogleg、trust-ncg。 只需要給定
hessp或hess之一。 如果提供了hess，則將忽略hessp。 如果既未提供hess也未提供hessp，則將使用jac上的有限差分來近似黑塞矩陣乘積。hessp必須計算黑塞矩陣乘以任意向量。（自動傳遞給scipy.optimize.minimize）
演算法設定
- minimize_every_iterbool
如果為 True，則有希望的全域取樣點將在每次迭代時傳遞給本地最小化常式。 如果為 True，則僅執行最終最小化器池。 預設值為 True。
- local_iterint
僅在每次迭代時評估一些最佳最小化器池候選者。 如果為 False，則所有潛在點都將傳遞給本地最小化常式。
- infty_constraintsbool
如果為 True，則任何在可行域之外產生的取樣點都將被儲存，並給定目標函數值
inf。 如果為 False，則將丟棄這些點。 使用此功能可能會提高在找到全域最小值之前函數評估方面的效能，指定 False 將使用較少的記憶體，但效能會略有下降。 預設值為 True。
回饋
- dispbool (L)
設定為 True 以列印收斂訊息。
- sampling_methodstr 或 function，選用
目前內建的取樣方法選項有
halton、sobol和simplicial。 預設的simplicial提供在有限時間內收斂到全域最小值的理論保證。halton和sobol方法在取樣點產生方面更快，但會損失保證收斂性。 它更適合大多數「較容易」的問題，在這些問題中，收斂速度相對較快。 使用者定義的取樣函數必須接受每個呼叫的n個維度為dim的取樣點的兩個引數，並輸出形狀為 n x dim 的取樣點陣列。- workersint 或類似 map 的 callable，選用
並行取樣和執行本地序列最小化。 提供 -1 以使用所有可用的 CPU 核心，或提供 int 以使用那麼多 Processes（使用
multiprocessing.Pool）。或者，提供類似 map 的 callable，例如 multiprocessing.Pool.map 用於並行評估。 此評估作為
workers(func, iterable)執行。 要求 func 可 pickle 化。在版本 1.11.0 中新增。
- 傳回值:
- resOptimizeResult
最佳化結果表示為
OptimizeResult物件。 重要屬性包括：x對應於全域最小值的解陣列、fun全域解的函數輸出、xl本地最小值解的排序列表、funl對應本地解的函數輸出、success布林值旗標，指示最佳化器是否成功退出、message描述終止原因、nfev目標函數評估的總次數，包括取樣呼叫、nlfev所有本地搜尋最佳化累積的目標函數評估總次數、nit全域常式執行的迭代次數。
註解
使用單純同調全域最佳化 [1] 的全域最佳化。 適用於解決通用 NLP 和黑箱最佳化問題以達到全域最佳性（低維度問題）。
一般來說，最佳化問題的形式為
minimize f(x) subject to g_i(x) >= 0, i = 1,...,m h_j(x) = 0, j = 1,...,p
其中 x 是一個或多個變數的向量。
f(x)是目標函數R^n -> R，g_i(x)是不等式約束，而h_j(x)是等式約束。或者，也可以使用 bounds 引數指定 x 中每個元素的下限和上限。
雖然 SHGO 的大多數理論優勢僅在
f(x)是 Lipschitz 光滑函數時才得到證明，但如果使用預設取樣方法 [1]，則該演算法也被證明可以收斂到更一般情況下的全域最佳值，其中f(x)是非連續、非凸和非光滑的。可以使用傳遞給
scipy.optimize.minimize的minimizer_kwargs參數來指定本地搜尋方法。 預設情況下，使用SLSQP方法。 一般來說，如果問題定義了不等式約束，建議使用SLSQP、COBYLA或COBYQA本地最小化，因為其他方法不使用約束。halton和sobol方法點是使用scipy.stats.qmc產生的。 可以使用任何其他 QMC 方法。參考文獻
[1] (1,2)Endres, SC, Sandrock, C, Focke, WW (2018) “A simplicial homology algorithm for lipschitz optimisation”, Journal of Global Optimization.
[2]Joe, SW and Kuo, FY (2008) “Constructing Sobol’ sequences with better two-dimensional projections”, SIAM J. Sci. Comput. 30, 2635-2654.
[3] (1,2)Hock, W and Schittkowski, K (1981) “Test examples for nonlinear programming codes”, Lecture Notes in Economics and Mathematical Systems, 187. Springer-Verlag, New York. http://www.ai7.uni-bayreuth.de/test_problem_coll.pdf
[4]Wales, DJ (2015) “Perspective: Insight into reaction coordinates and dynamics from the potential energy landscape”, Journal of Chemical Physics, 142(13), 2015.
範例
首先考慮最小化 Rosenbrock 函數的問題，
rosen>>> from scipy.optimize import rosen, shgo >>> bounds = [(0,2), (0, 2), (0, 2), (0, 2), (0, 2)] >>> result = shgo(rosen, bounds) >>> result.x, result.fun (array([1., 1., 1., 1., 1.]), 2.920392374190081e-18)
請注意，邊界決定了目標函數的維度，因此是必要的輸入，但是您可以使用
None或類似np.inf的物件來指定空邊界，這些物件將轉換為大型浮點數。>>> bounds = [(None, None), ]*4 >>> result = shgo(rosen, bounds) >>> result.x array([0.99999851, 0.99999704, 0.99999411, 0.9999882 ])
接下來，我們考慮 Eggholder 函數，這是一個具有多個本地最小值和一個全域最小值的問題。 我們將示範引數的使用和
shgo的功能。 (https://en.wikipedia.org/wiki/Test_functions_for_optimization)>>> import numpy as np >>> def eggholder(x): ... return (-(x[1] + 47.0) ... * np.sin(np.sqrt(abs(x[0]/2.0 + (x[1] + 47.0)))) ... - x[0] * np.sin(np.sqrt(abs(x[0] - (x[1] + 47.0)))) ... ) ... >>> bounds = [(-512, 512), (-512, 512)]
shgo具有內建的低差異取樣序列。 首先，我們將輸入 64 個 Sobol’ 序列的初始取樣點>>> result = shgo(eggholder, bounds, n=64, sampling_method='sobol') >>> result.x, result.fun (array([512. , 404.23180824]), -959.6406627208397)
shgo也會傳回找到的任何其他本地最小值，這些可以使用以下方式呼叫>>> result.xl array([[ 512. , 404.23180824], [ 283.0759062 , -487.12565635], [-294.66820039, -462.01964031], [-105.87688911, 423.15323845], [-242.97926 , 274.38030925], [-506.25823477, 6.3131022 ], [-408.71980731, -156.10116949], [ 150.23207937, 301.31376595], [ 91.00920901, -391.283763 ], [ 202.89662724, -269.38043241], [ 361.66623976, -106.96493868], [-219.40612786, -244.06020508]])
>>> result.funl array([-959.64066272, -718.16745962, -704.80659592, -565.99778097, -559.78685655, -557.36868733, -507.87385942, -493.9605115 , -426.48799655, -421.15571437, -419.31194957, -410.98477763])
這些結果在以下應用中很有用：存在許多全域最小值，並且需要其他全域最小值的值，或者本地最小值可以提供對系統的深入了解（例如物理化學中的形態 [4]）。
如果我們想要找到更多數量的本地最小值，我們可以增加取樣點的數量或迭代次數。 我們將取樣點的數量增加到 64，並將迭代次數從預設的 1 增加到 3。 使用
simplicial這將給我們 64 x 3 = 192 個初始取樣點。>>> result_2 = shgo(eggholder, ... bounds, n=64, iters=3, sampling_method='sobol') >>> len(result.xl), len(result_2.xl) (12, 23)
請注意
n=192, iters=1和n=64, iters=3之間的差異。 在第一種情況下，最小化器池中包含的有希望的點僅處理一次。 在後一種情況下，每 64 個取樣點處理一次，總共處理 3 次。為了示範解決具有非線性約束的問題，請考慮以下 Hock 和 Schittkowski 問題 73（牛飼料）中的範例 [3]
minimize: f = 24.55 * x_1 + 26.75 * x_2 + 39 * x_3 + 40.50 * x_4 subject to: 2.3 * x_1 + 5.6 * x_2 + 11.1 * x_3 + 1.3 * x_4 - 5 >= 0, 12 * x_1 + 11.9 * x_2 + 41.8 * x_3 + 52.1 * x_4 - 21 -1.645 * sqrt(0.28 * x_1**2 + 0.19 * x_2**2 + 20.5 * x_3**2 + 0.62 * x_4**2) >= 0, x_1 + x_2 + x_3 + x_4 - 1 == 0, 1 >= x_i >= 0 for all i
[3] 中給出的近似答案是
f([0.6355216, -0.12e-11, 0.3127019, 0.05177655]) = 29.894378
>>> def f(x): # (cattle-feed) ... return 24.55*x[0] + 26.75*x[1] + 39*x[2] + 40.50*x[3] ... >>> def g1(x): ... return 2.3*x[0] + 5.6*x[1] + 11.1*x[2] + 1.3*x[3] - 5 # >=0 ... >>> def g2(x): ... return (12*x[0] + 11.9*x[1] +41.8*x[2] + 52.1*x[3] - 21 ... - 1.645 * np.sqrt(0.28*x[0]**2 + 0.19*x[1]**2 ... + 20.5*x[2]**2 + 0.62*x[3]**2) ... ) # >=0 ... >>> def h1(x): ... return x[0] + x[1] + x[2] + x[3] - 1 # == 0 ... >>> cons = ({'type': 'ineq', 'fun': g1}, ... {'type': 'ineq', 'fun': g2}, ... {'type': 'eq', 'fun': h1}) >>> bounds = [(0, 1.0),]*4 >>> res = shgo(f, bounds, n=150, constraints=cons) >>> res message: Optimization terminated successfully. success: True fun: 29.894378159142136 funl: [ 2.989e+01] x: [ 6.355e-01 1.137e-13 3.127e-01 5.178e-02] # may vary xl: [[ 6.355e-01 1.137e-13 3.127e-01 5.178e-02]] # may vary nit: 1 nfev: 142 # may vary nlfev: 35 # may vary nljev: 5 nlhev: 0
>>> g1(res.x), g2(res.x), h1(res.x) (-5.062616992290714e-14, -2.9594104944408173e-12, 0.0)