Main Content

このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

複数のグローバルソルバーを比較する、問題ベース

ライブ スクリプトを開く

この例では、複数のソルバーを使用して Rastrigin 関数を最小化する方法を示します。各ソルバーには独自の特性があります。特性によってソリューションと実行時間が異なります。ソルバーとソリューションの比較にまとめられた結果は、自分の問題に適したソルバーを選択するのに役立ちます。

ラストリギン関数には多くの局所最小値があり、大域最小値は (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 構造に示されているように、5 回のみ) で問題を解決し、開始点の近くで局所的最小値に到達します。終了フラグは、解が局所最小値であることを示します。

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.9343
         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: 5.5646
          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 は関数評価の制限に達すると停止します。デフォルトでは、2 変数の問題の場合、制限は 200 です。surrogateopt には有限の境界が必要です。surrogateopt はグローバル ソリューションを見つけようとし、この場合は成功します。surrogateopt はアルゴリズムの一部として多くの補助計算を実行するため、surrogateopt の各関数の評価には他のほとんどのソルバーよりも長い時間がかかります。

参考

| | | | |

関連するトピック