使用基于问题的方法比较全局求解器
此示例说明如何使用几个求解器最小化拉斯特里金函数。每个求解器都有自己的特征。这些特征会得到不同的解和运行时间。比较求解器和解中总结的结果可以帮助您为自己的问题选择合适的求解器。
拉斯特里金函数有许多局部最小值,全局最小值位于 (0,0):
ras = @(x, y) 20 + x.^2 + y.^2 - 10*(cos(2*pi*x) + cos(2*pi*y));
绘制在每个方向上缩放 10 倍的函数。
rf3 = @(x, y) ras(x/10, y/10); fsurf(rf3,[-30 30],"ShowContours","on") title("rastriginsfcn([x/10,y/10])") xlabel("x") ylabel("y")
通常您不知道目标函数的全局最小值的位置。为了展示求解器如何寻找全局解,此示例将围绕远离全局最小值的点 [20,30] 启动所有求解器。
fminunc
求解器
要使用默认 Optimization Toolbox™ 求解器 fminunc
求解优化问题,请输入:
x = optimvar("x"); y = optimvar("y"); prob = optimproblem("Objective",rf3(x,y)); x0.x = 20; x0.y = 30; [solf,fvalf,eflagf,outputf] = solve(prob,x0)
Solving problem using fminunc. Local minimum found. Optimization completed because the size of the gradient is less than the value of the optimality tolerance. <stopping criteria details>
solf = struct with fields:
x: 19.8991
y: 29.8486
fvalf = 12.9344
eflagf = OptimalSolution
outputf = struct with fields:
iterations: 3
funcCount: 5
stepsize: 1.7773e-06
lssteplength: 1
firstorderopt: 2.0461e-09
algorithm: 'quasi-newton'
message: 'Local minimum found.↵↵Optimization completed because the size of the gradient is less than↵the value of the optimality tolerance.↵↵<stopping criteria details>↵↵Optimization completed: The first-order optimality measure, 1.278784e-09, is less ↵than options.OptimalityTolerance = 1.000000e-06.'
objectivederivative: "reverse-AD"
solver: 'fminunc'
fminunc
经过很少的函数计算(只有五次,如 outputf
结构体中所示)就完成了问题求解,并且在起点附近达到局部最小值。此退出标志表示该解是局部最小值。
patternsearch
求解器
要使用 Global Optimization Toolbox 求解器 patternsearch
求解优化问题,请输入:
x0.x = 20; x0.y = 30; [solp,fvalp,eflagp,outputp] = solve(prob,x0,"Solver","patternsearch")
Solving problem using patternsearch. patternsearch stopped because the mesh size was less than options.MeshTolerance.
solp = struct with fields:
x: 19.8991
y: -9.9496
fvalp = 4.9748
eflagp = SolverConvergedSuccessfully
outputp = struct with fields:
function: @(x)fun(x,extraParams)
problemtype: 'unconstrained'
pollmethod: 'gpspositivebasis2n'
maxconstraint: []
searchmethod: []
iterations: 48
funccount: 174
meshsize: 9.5367e-07
rngstate: [1×1 struct]
message: 'patternsearch stopped because the mesh size was less than options.MeshTolerance.'
solver: 'patternsearch'
与 fminunc
一样,patternsearch
找到局部最优,如退出标志 exitflagp
所示。该解优于 fminunc
解,因为其目标函数值更低。不过,patternsearch
需要更多的函数计算,如输出结构体中所示。
ga
求解器
要使用 Global Optimization Toolbox 求解器 ga
求解优化问题,请输入:
rng default % For reproducibility x0.x = 10*randn(20) + 20; x0.y = 10*randn(20) + 30; % Random start population near [20,30]; [solg,fvalg,eflagg,outputg] = solve(prob,"Solver","ga")
Solving problem using ga. ga stopped because it exceeded options.MaxGenerations.
solg = struct with fields:
x: 0.0064
y: 7.7057e-04
fvalg = 8.1608e-05
eflagg = SolverLimitExceeded
outputg = struct with fields:
problemtype: 'unconstrained'
rngstate: [1×1 struct]
generations: 200
funccount: 9453
message: 'ga stopped because it exceeded options.MaxGenerations.'
maxconstraint: []
hybridflag: []
solver: 'ga'
ga
比上述求解器执行更多的函数计算,并得到接近全局最小值的解。该求解器是随机求解器,可以得到次优解。
particleswarm
求解器
要使用 Global Optimization Toolbox 求解器 particleswarm
求解优化问题,请输入:
rng default % For reproducibility [solpso,fvalpso,eflagpso,outputpso] = solve(prob,"Solver","particleswarm")
Solving problem using particleswarm. Optimization ended: relative change in the objective value over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.
solpso = struct with fields:
x: 7.1467e-07
y: 1.4113e-06
fvalpso = 4.9631e-12
eflagpso = SolverConvergedSuccessfully
outputpso = struct with fields:
rngstate: [1×1 struct]
iterations: 120
funccount: 2420
message: 'Optimization ended: relative change in the objective value ↵over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.'
hybridflag: []
solver: 'particleswarm'
与 ga
相比,该求解器执行的函数计算次数更少,并得到更准确的解。同样,该求解器是随机求解器,可能无法得到全局解。
simulannealbnd
求解器
要使用 Global Optimization Toolbox 求解器 simulannealbnd
求解优化问题,请输入:
rng default % For reproducibility x0.x = 20; x0.y = 30; [solsim,fvalsim,eflagsim,outputsim] = solve(prob,x0,"Solver","simulannealbnd")
Solving problem using simulannealbnd. simulannealbnd stopped because the change in best function value is less than options.FunctionTolerance.
solsim = struct with fields:
x: 0.0025
y: 0.0018
fvalsim = 1.8386e-05
eflagsim = SolverConvergedSuccessfully
outputsim = struct with fields:
iterations: 1967
funccount: 1986
message: 'simulannealbnd stopped because the change in best function value is less than options.FunctionTolerance.'
rngstate: [1×1 struct]
problemtype: 'unconstrained'
temperature: [2×1 double]
totaltime: 0.4597
solver: 'simulannealbnd'
求解器执行与 particleswarm
相同的函数计算次数,并得到一个良解。此求解器也是随机求解器。
surrogateopt
求解器
surrogateopt
不需要起点,但需要有限边界。在每个分量中将边界设置为 -70 到 130。要获得与其他求解器相同的输出,请禁用默认绘图函数。
rng default % For reproducibility x = optimvar("x","LowerBound",-70,"UpperBound",130); y = optimvar("y","LowerBound",-70,"UpperBound",130); prob = optimproblem("Objective",rf3(x,y)); options = optimoptions("surrogateopt","PlotFcn",[]); [solsur,fvalsur,eflagsur,outputsur] = solve(prob,... "Solver","surrogateopt",... "Options",options)
Solving problem using surrogateopt. surrogateopt stopped because it exceeded the function evaluation limit set by 'options.MaxFunctionEvaluations'.
solsur = struct with fields:
x: 9.9494
y: -9.9502
fvalsur = 1.9899
eflagsur = SolverLimitExceeded
outputsur = struct with fields:
elapsedtime: 2.0956
funccount: 200
constrviolation: 0
ineq: [1×1 struct]
rngstate: [1×1 struct]
message: 'surrogateopt stopped because it exceeded the function evaluation limit set by ↵'options.MaxFunctionEvaluations'.'
solver: 'surrogateopt'
该求解器执行相对较少的函数计算即可得到接近全局最优的解。然而,每次函数计算都比其他求解器花费更多时间。
比较求解器和解
如果一个解的目标函数值小于另一个解的目标函数值,则此解优于另一个解。下表对结果进行了总结。
sols = [solf.x solf.y; solp.x solp.y; solg.x solg.y; solpso.x solpso.y; solsim.x solsim.y; solsur.x solsur.y]; fvals = [fvalf; fvalp; fvalg; fvalpso; fvalsim; fvalsur]; fevals = [outputf.funcCount; outputp.funccount; outputg.funccount; outputpso.funccount; outputsim.funccount; outputsur.funccount]; stats = table(sols,fvals,fevals); stats.Properties.RowNames = ["fminunc" "patternsearch" "ga" "particleswarm" "simulannealbnd" "surrogateopt"]; stats.Properties.VariableNames = ["Solution" "Objective" "# Fevals"]; disp(stats)
Solution Objective # Fevals ________________________ __________ ________ fminunc 19.899 29.849 12.934 5 patternsearch 19.899 -9.9496 4.9748 174 ga 0.0063672 0.00077057 8.1608e-05 9453 particleswarm 7.1467e-07 1.4113e-06 4.9631e-12 2420 simulannealbnd 0.002453 0.0018028 1.8386e-05 1986 surrogateopt 9.9494 -9.9502 1.9899 200
以下这些结果非常典型:
fminunc
很快得到其起始盆内的局部解,但根本不探索该盆以外的区域。由于目标函数具有解析导数,因此fminunc
使用自动微分,并且只需执行很少次数的函数计算就得到精确的局部最小值。patternsearch
比fminunc
执行更多的函数计算次数并且搜索几个盆,因此得到的解优于fminunc
。ga
比patternsearch
执行更多的函数计算次数。它会偶然找到一个更好的解。在本例中,ga
找到接近全局最优的点。ga
是随机求解器,其结果随着每次运行而变化。ga
需要额外的步骤才能使初始种群接近 [20,30]。particleswarm
执行的函数计算次数比ga
少,但比patternsearch
多。在本例中,particleswarm
找到一个其目标函数值比patternsearch
或ga
低的点。由于particleswarm
是随机求解器,其结果随着每次运行而变化。particleswarm
需要额外的步骤来使初始种群接近 [20,30]。simulannealbnd
执行的函数计算次数与particleswarm
大致相同。在本例中,simulannealbnd
找到一个良解,但不如particleswarm
找到的解。该求解器是随机求解器,可以得到次优解。surrogateopt
在达到函数计算限制时停止,对于二变量问题,默认为 200 次。surrogateopt
需要有限边界。surrogateopt
尝试求全局解,在本例中已成功。surrogateopt
中执行的每次函数计算都比大多数其他求解器花费更长的时间,因为surrogateopt
在其算法中执行许多辅助计算。
另请参阅
solve
| patternsearch
| ga
| particleswarm
| simulannealbnd
| surrogateopt