比较几种基于问题的全局求解器

这个例子展示了如何用几个求解器来最小化拉斯特里金函数。每个求解器都有自己的特点。这些特点导致不同的解和运行时间。比较求解器和解决方案中总结的结果可以帮助您为自己的问题选择合适的求解器。

拉斯特里金函数具有许多局部极小值，在 (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` 求解器

要使用默认的 fminunc Optimization Toolbox™ 求解器解决优化问题，请输入：

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.

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....'
    objectivederivative: "reverse-AD"
                 solver: 'fminunc'

fminunc 通过极少的几次函数计算（仅五次，如 outputf 结构体所示）解决了该问题，并在起点附近达到局部最小值。退出标志表明该解是一个局部最小值。

`patternsearch` 求解器

要使用 patternsearch Global Optimization Toolbox 求解器解决优化问题，请输入：

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: [1x1 struct]
          message: 'patternsearch stopped because the mesh size was less than options.MeshTolerance.'
           solver: 'patternsearch'

与 fminunc 一样，patternsearch 也达到了局部最优，如退出标志 exitflagp 所示。该解比 fminunc 解更好，因为它具有较低的目标函数值。但是，patternsearch 需要更多的函数计算，如输出结构体所示。

`ga` 求解器

要使用 ga Global Optimization Toolbox 求解器解决优化问题，请输入：

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: [1x1 struct]
      generations: 200
        funccount: 9453
          message: 'ga stopped because it exceeded options.MaxGenerations.'
    maxconstraint: []
       hybridflag: []
           solver: 'ga'

ga 比以前的求解器进行了更多的函数计算，并得出了接近全局最小值的解。该求解器是随机的，并且可以达到次优解。

`particleswarm` 求解器

要使用 particleswarm Global Optimization Toolbox 求解器解决优化问题，请输入：

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: [1x1 struct]
    iterations: 120
     funccount: 2420
       message: 'Optimization ended: relative change in the objective value ...'
    hybridflag: []
        solver: 'particleswarm'

与 ga 相比，求解器需要更少的函数计算，并得出更精确的解。再次强调，求解器是随机的，可能无法找到全局解。

`simulannealbnd` 求解器

要使用 simulannealbnd Global Optimization Toolbox 求解器解决优化问题，请输入：

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: [1x1 struct]
    problemtype: 'unconstrained'
    temperature: [2x1 double]
      totaltime: 0.8019
         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: 4.0910
          funccount: 200
    constrviolation: 0
               ineq: [1x1 struct]
           rngstate: [1x1 struct]
            message: 'surrogateopt stopped because it exceeded the function evaluation limit set by ...'
             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 作为其算法的一部分执行许多辅助计算。