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

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')

通常、目的関数のグローバル最小値の位置はわかりません。ソルバーがどのようにグローバルソリューションを探すかを示すために、この例では、グローバル最小値から遠いポイント [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.

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....'

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: [1x1 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: [1x1 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: [1x1 struct]
    iterations: 56
     funccount: 1140
       message: 'Optimization ended: relative change in the objective value ...'
    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: 4.1985
          funccount: 200
    constrviolation: 0
               ineq: [1x0 double]
           rngstate: [1x1 struct]
            message: 'surrogateopt stopped because it exceeded the function evaluation limit set by ...'

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....'

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