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

6 つのソルバーの比較

最適化する機能

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

ラストリジン関数には多くの局所最小値があり、大域的最小値は(0,0)にあります。関数は $R a s (x)$ として定義されます:

$R a s (x) = 20 + x_{1}^{2} + x_{2}^{2} - 10 (\cos 2 π x_{1} + \cos 2 π x_{2}) .$

この例を実行すると、Rastrigin 関数の値を計算する rastriginsfcn.m ファイルが利用できます。この例では、より大きな引き込み領域を持つ Rastrigin 関数のスケールバージョンを使用します。詳細については、引き込み領域を参照してください。スケーリングされた関数の表面プロットを作成します。

rf2 = @(x)rastriginsfcn(x/10);
rf3 = @(x,y)reshape(rastriginsfcn([x(:)/10,y(:)/10]),size(x));
fsurf(rf3,[-30 30],'ShowContours','on')
title('rastriginsfcn([x/10,y/10])')
xlabel('x')
ylabel('y')

Figure contains an axes object. The axes object with title rastriginsfcn([x/10,y/10]), xlabel x, ylabel y contains an object of type functionsurface.

通常、目的関数の大域的最小値の位置はわかりません。ソルバーがどのように大域解を探すかを示すために、この例では、大域的最小値から遠いポイント [20,30] の周囲ですべてのソルバーを開始します。

この例では、fminunc (Optimization Toolbox ™ ソルバー)、patternsearch、および GlobalSearch のデフォルト設定を使用して、rf2 を最小化します。この例では、ga と particleswarm をデフォルト以外のオプションとともに使用して、ポイント [20,30] の周囲に初期母集団を開始しています。surrogateopt には有限の境界が必要であるため、例では各変数の下限が -70、上限が 130 の surrogateopt を使用します。

6つの解決方法

`fminunc`

fminunc Optimization Toolbox ソルバーを使用して最適化問題を解くには、次のように入力します。

rf2 = @(x)rastriginsfcn(x/10); % objective
x0 = [20,30]; % start point away from the minimum
[xf,ff,flf,of] = fminunc(rf2,x0)

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

<stopping criteria details>

xf = 1×2

   19.8991   29.8486

ff = 
12.9344

flf = 
1

of = struct with fields:
       iterations: 3
        funcCount: 15
         stepsize: 1.7776e-06
     lssteplength: 1
    firstorderopt: 5.9907e-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, 3.744173e-09, is less ↵than options.OptimalityTolerance = 1.000000e-06.'

xf は最小化点です。
ff は、xf における目標値 rf2 の値です。
flf は終了フラグです。終了フラグが 1 の場合、xf が局所的最小値であることを示します。
of は出力構造であり、ソリューションにつながる fminunc 計算を記述します。

`patternsearch`

patternsearch Global Optimization Toolbox ソルバーを使用して最適化問題を解くには、次のように入力します。

rf2 = @(x)rastriginsfcn(x/10); % objective
x0 = [20,30]; % start point away from the minimum
[xp,fp,flp,op] = patternsearch(rf2,x0)

patternsearch stopped because the mesh size was less than options.MeshTolerance.

xp = 1×2

   19.8991   -9.9496

fp = 
4.9748

flp = 
1

op = struct with fields:
         function: @(x)rastriginsfcn(x/10)
      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.'

xp は最小化点です。
fp は、xp における目標値 rf2 の値です。
flp は終了フラグです。終了フラグが 1 の場合、xp が局所的最小値であることを示します。
op は出力構造であり、解に至る patternsearch 計算を記述します。

`ga`

ga Global Optimization Toolbox ソルバーを使用して最適化問題を解くには、次のように入力します。

rng default % for reproducibility
rf2 = @(x)rastriginsfcn(x/10); % objective
x0 = [20,30]; % start point away from the minimum
initpop = 10*randn(20,2) + repmat(x0,20,1);
opts = optimoptions('ga','InitialPopulationMatrix',initpop);

initpop は 20 行 2 列の行列です。initpop の各行の平均は [20,30] であり、各要素は標準偏差 10 で正規分布しています。initpop の行は、ga ソルバーの初期母集団行列を形成します。
opts は、initpop を初期母集団として設定するオプションです。
ga は乱数を使用し、ランダムな結果を生成します。
次の行はオプションを使用して ga を呼び出します。

[xga,fga,flga,oga] = ga(rf2,2,[],[],[],[],[],[],[],opts)

ga stopped because it exceeded options.MaxGenerations.

xga = 1×2

   -0.0042   -0.0024

fga = 
4.7054e-05

flga = 
0

oga = struct with fields:
      problemtype: 'unconstrained'
         rngstate: [1×1 struct]
      generations: 200
        funccount: 9453
          message: 'ga stopped because it exceeded options.MaxGenerations.'
    maxconstraint: []
       hybridflag: []

xga は最小化点です。
fga は、xga における目標値 rf2 の値です。
flga は終了フラグです。終了フラグ 0 は、ga が関数評価制限または反復制限に達したことを示します。この場合、ga は反復制限に達します。
oga は出力構造であり、ソリューションにつながる ga 計算を記述します。

`particleswarm`

ga と同様に、particleswarm は母集団ベースのアルゴリズムです。したがって、ソルバーを公平に比較するには、粒子群を ga と同じ母集団に初期化します。

rng default % for reproducibility
rf2 = @(x)rastriginsfcn(x/10); % objective
opts = optimoptions('particleswarm','InitialSwarmMatrix',initpop);
[xpso,fpso,flgpso,opso] = particleswarm(rf2,2,[],[],opts)

Optimization ended: relative change in the objective value 
over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.

xpso = 1×2

    9.9496    0.0000

fpso = 
0.9950

flgpso = 
1

opso = struct with fields:
      rngstate: [1×1 struct]
    iterations: 56
     funccount: 1140
       message: 'Optimization ended: relative change in the objective value ↵over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.'
    hybridflag: []

`surrogateopt`

surrogateopt には開始点は必要ありませんが、有限の境界は必要です。各コンポーネントの境界を -70 ～ 130 に設定します。他のソルバーと同じ種類の出力を得るには、デフォルトのプロット機能を無効にします。

rng default % for reproducibility
lb = [-70,-70];
ub = [130,130];
rf2 = @(x)rastriginsfcn(x/10); % objective
opts = optimoptions('surrogateopt','PlotFcn',[]);
[xsur,fsur,flgsur,osur] = surrogateopt(rf2,lb,ub,opts)

surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

xsur = 1×2

    9.9494   -9.9502

fsur = 
1.9899

flgsur = 
0

osur = struct with fields:
        elapsedtime: 1.9231
          funccount: 200
    constrviolation: 0
               ineq: [1×0 double]
           rngstate: [1×1 struct]
            message: 'surrogateopt stopped because it exceeded the function evaluation limit set by ↵'options.MaxFunctionEvaluations'.'

xsur は最小化点です。
fsur は、xsur における目標値 rf2 の値です。
flgsur は終了フラグです。終了フラグ 0 は、関数評価または時間が不足したために surrogateopt が停止したことを示します。
osur は出力構造であり、解に至る surrogateopt 計算を記述します。

`GlobalSearch`

GlobalSearch ソルバーを使用して最適化問題を解くには、次のように入力します。

rf2 = @(x)rastriginsfcn(x/10); % objective
x0 = [20,30]; % start point away from the minimum
problem = createOptimProblem('fmincon','objective',rf2,...
    'x0',x0);
gs = GlobalSearch;

problem は最適化問題の構造です。problem は fmincon ソルバー、rf2 目的関数、および x0=[20,30] を指定します。createOptimProblem の使用に関する詳細については、問題構造を作成するを参照してください。

メモ: 制約のない問題の場合でも、GlobalSearch のソルバーとして fmincon を指定する必要があります。

gs はデフォルトの GlobalSearch オブジェクトです。オブジェクトには問題を解決するためのオプションが含まれています。run(gs,problem) を呼び出すと、複数の開始点から問題が実行されます。開始点はランダムなので、その後の結果もランダムになります。

[xg,fg,flg,og] = run(gs,problem)

GlobalSearch stopped because it analyzed all the trial points.

All 7 local solver runs converged with a positive local solver exit flag.

xg = 1×2
10^-7 ×

   -0.1405   -0.1405

fg = 
0

flg = 
1

og = struct with fields:
                funcCount: 2217
         localSolverTotal: 7
       localSolverSuccess: 7
    localSolverIncomplete: 0
    localSolverNoSolution: 0
                  message: 'GlobalSearch stopped because it analyzed all the trial points.↵↵All 7 local solver runs converged with a positive local solver exit flag.'

xg は最小化点です。
fg は、xg における目標値 rf2 の値です。
flg は終了フラグです。終了フラグが 1 の場合、すべての fmincon 実行が適切に収束したことを示します。
og は出力構造であり、解に至る GlobalSearch 計算を記述します。

構文とソリューションを比較する

一方のソリューションの目的関数の値がもう一方のソリューションよりも小さい場合、そのソリューションはもう一方のソリューションよりも優れています。次の表に結果をまとめます。

sols = [xf;
    xp;
    xga;
    xpso;
    xsur;
    xg];
fvals = [ff;
    fp;
    fga;
    fpso;
    fsur;
    fg];
fevals = [of.funcCount;
    op.funccount;
    oga.funccount;
    opso.funccount;
    osur.funccount;
    og.funcCount];
stats = table(sols,fvals,fevals);
stats.Properties.RowNames = ["fminunc" "patternsearch" "ga" "particleswarm" "surrogateopt" "GlobalSearch"];
stats.Properties.VariableNames = ["Solution" "Objective" "# Fevals"];
disp(stats)

                              Solution             Objective     # Fevals
                     __________________________    __________    ________

    fminunc               19.899         29.849        12.934        15  
    patternsearch         19.899        -9.9496        4.9748       174  
    ga                -0.0042178     -0.0024347    4.7054e-05      9453  
    particleswarm         9.9496       6.75e-07       0.99496      1140  
    surrogateopt          9.9494        -9.9502        1.9899       200  
    GlobalSearch     -1.4046e-08    -1.4046e-08             0      2217

典型的な結果は次の通りです:

fminunc は開始領域内の局所解にすぐに到達しますが、この領域の外側を探索することはありません。fminunc の呼び出し構文は単純です。
patternsearch は fminunc よりも多くの関数評価を行い、複数の領域を探索して、fminunc よりも優れたソリューションに到達します。patternsearch 呼び出し構文は fminunc と同じです。
ga は、patternsearch よりも多くの関数評価を実行します。偶然にも、より良い解決策にたどり着きます。この場合、ga はグローバル最適値に近い点を見つけます。ga は確率的であるため、実行ごとに結果が変わります。ga の呼び出し構文は単純ですが、初期母集団を [20,30] の近くに配置するための追加手順があります。
particleswarm は ga よりも関数評価が少なくなりますが、patternsearch よりも多くなります。この場合、particleswarm は、patternsearch よりも目的関数の値が低いが、ga よりも高いポイントを見つけます。particleswarm は確率的であるため、実行ごとに結果が変わります。particleswarm の呼び出し構文は単純ですが、初期母集団を [20,30] の近くに配置するための追加手順があります。
surrogateopt は関数評価の制限に達すると停止します。デフォルトでは、2 変数の問題の場合、関数評価の制限は 200 です。surrogateopt の呼び出し構文は単純ですが、有限の境界が必要です。surrogateopt は大域解を見つけようとしますが、この場合は成功しません。surrogateopt はアルゴリズムの一部として多くの補助計算を実行するため、surrogateopt での各関数評価には、他のほとんどのソルバーよりも長い時間がかかります。
GlobalSearch run は、ga および particleswarm と同じ大きさの関数評価を実行し、多くの領域を探索して、適切な解に到達します。この場合、GlobalSearch はグローバル最適値を見つけます。GlobalSearch の設定は、他のソルバーの設定よりも複雑です。例に示すように、GlobalSearch を呼び出す前に、GlobalSearch オブジェクト (例では gs) と問題構造 (problem) の両方を作成する必要があります。次に、gs と problem を使用して run メソッドを呼び出します。GlobalSearch の実行方法の詳細については、GlobalSearchとMultiStartのワークフローを参照してください。

参考

6 つのソルバーの比較

最適化する機能

6つの解決方法

fminunc

patternsearch

ga

particleswarm

surrogateopt

GlobalSearch