このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。
投票の種類
一般化パターン検索における完全投票の使用
例として、次の関数を考えてみましょう。
次の図は関数のプロットを示しています。
関数のグローバル最小値は (0, 0) で発生し、その値は -25 です。ただし、この関数は (0, 9) で極小値を持ち、その値は -16 になります。
関数を計算するファイルを作成するには、次のコードをコピーして、MATLAB® エディターの新しいファイルに貼り付けます。
function z = poll_example(x) if x(1)^2 + x(2)^2 <= 25 z = x(1)^2 + x(2)^2 - 25; elseif x(1)^2 + (x(2) - 9)^2 <= 16 z = x(1)^2 + (x(2) - 9)^2 - 16; else z = 0; end
MATLAB パス上のフォルダーにファイル名を poll_example.m
としてファイルを保存します。
関数に対してパターン検索を実行するには、次のように入力します。
options = optimoptions('patternsearch','Display','iter'); [x,fval] = patternsearch(@poll_example,[0,5],... [],[],[],[],[],[],[],options)
MATLAB は反復と解のテーブルを返します。
x = 0 9 fval = -16
アルゴリズムは、初期点 f(0, 5) = 0. で関数を評価することから始まります。投票は、最初の反復中に以下を評価します。
f((0, 5) + (1, 0)) = f(1, 5) = 0
f((0, 5) + (0, 1)) = f(0, 6) = -7
検索は、目的関数の値が初期点よりも小さいメッシュ ポイント (0, 6) をポーリングするとすぐに、現在のメッシュのポーリングを停止し、次の反復で現在のポイントを (0, 6) に設定します。その結果、最初の反復では、探索は(0、9)の局所最小値に向かって移動します。これは、コマンド ライン表示の最初の 2 行を見るとわかります。
Iter f-count f(x) MeshSize Method 0 1 0 1 1 3 -7 2 Successful Poll
パターン検索では、最初の反復で目的関数の評価が 2 回のみ実行されるため、関数の合計数が 1 から 3 に増加することに注意してください。
次に、UseCompletePoll
を true
に設定して最適化を再実行します。
options.UseCompletePoll = true;
[x,fval] = patternsearch(@poll_example,[0,5],...
[],[],[],[],[],[],[],options);
今回は、パターン検索により (0, 0) でグローバル最小値が見つかります。この実行と前回の実行の違いは、UseCompletePoll
が true
に設定されている場合、最初の反復でパターン検索が 4 つのメッシュ ポイントすべてをポーリングすることです。
f((0, 5) + (1, 0)) = f(1, 5) = 0
f((0, 5) + (0, 1)) = f(0, 6) = -6
f((0, 5) + (-1, 0)) = f(-1, 5) = 0
f((0, 5) + (0, -1)) = f(0, 4) = -9
最後のメッシュ ポイントの目的関数値が最も低いため、パターン検索では次の反復でそのポイントが現在のポイントとして選択されます。コマンドライン表示の最初の 2 行にこれが表示されます。
Iter f-count f(x) MeshSize Method 0 1 0 1 1 5 -9 2 Successful Poll
この場合、目的関数は最初の反復で 4 回評価されます。その結果、パターン検索は (0, 0) のグローバル最小値に向かって移動します。
次の図は、Complete poll が Off
に設定されている場合に返されるポイントのシーケンスと、Complete poll が On
の場合に返されるポイントのシーケンスを比較しています。
投票オプションの効率を比較する
この例では、反復と合計関数評価の観点から、複数のポーリング オプションがどのように相互作用するかを示します。主な結果は次のとおりです。
線形制約の問題の場合、GSS は GPS や MADS よりも効率的です。
UseCompletePoll
をtrue
に設定すると、反復回数に影響しますが、効率が向上するか低下するかは不明です。同様に、
2N
投票を行うことがNp1
投票を行うことよりも効率的であるかどうかも不明です。最も効率的なポーリングは、GSS Positive Basis Np1
で Complete poll をon
に設定することです。最も効率が悪いのは、MADS Positive Basis Np1
で Complete poll をon
に設定することです。
メモ
アルゴリズムの効率は問題によって異なります。GSS は線形制約の問題に効率的です。ただし、他の投票オプションの効率性への影響を予測することは困難であり、他の制約に対してどの投票タイプが最も効果的であるかを知ることも困難です。
問題の設定
問題は最適化ライブエディタータスクでpatternsearchを使用して解決すると同じです。この線形制約問題には二次目的関数があります。
MATLAB ワークスペースに以下を入力します。
x0 = [2 1 0 9 1 0]; Aineq = [-8 7 3 -4 9 0]; bineq = 7; Aeq = [7 1 8 3 3 3; 5 0 -5 1 -5 8; -2 -6 7 1 1 9; 1 -1 2 -2 3 -3]; beq = [84 62 65 1]; H = [36 17 19 12 8 15; 17 33 18 11 7 14; 19 18 43 13 8 16; 12 11 13 18 6 11; 8 7 8 6 9 8; 15 14 16 11 8 29]; f = [ 20 15 21 18 29 24 ]'; fun = @(x)0.5*x'*H*x + f'*x;
初期オプションと目的関数を設定します。
options = optimoptions('patternsearch',... 'PollMethod','GPSPositiveBasis2N',... 'PollOrderAlgorithm','consecutive',... 'UseCompletePoll',false);
output
構造にoutputgps2noff
という名前を付けて最適化を実行します。[x,fval,exitflag,outputgps2noff] = patternsearch(fun,x0,... Aineq,bineq,Aeq,beq,[],[],[],options);
完全な投票を使用するためのオプションを設定します。
options.UseCompletePoll = true;
output
構造にoutputgps2non
という名前を付けて最適化を実行します。[x,fval,exitflag,outputgps2non] = patternsearch(fun,x0,... Aineq,bineq,Aeq,beq,[],[],[],options);
同様の方法で、
UseCompletePoll
にtrue
とfalse
をセットした他のポーリング メソッドの出力構造を作成します:outputgss2noff
、outputgss2non
、outputgssnp1off
、outputgssnp1on
、outputmads2noff
、outputmads2non
、outputmadsnp1off
、およびoutputmadsnp1on
。
結果を調べる
12 回の最適化実行の結果があります。次の表は、関数の合計数と反復回数で測定された実行の効率を示しています。MADS は確率的アルゴリズムであるため、MADS の結果は異なる可能性があります。
アルゴリズム | 関数数 | Iterations |
---|---|---|
GPS2N、投票完了 | 1462 | 136 |
GPS2N、投票完了 | 1396 | 96 |
GPSNp1、投票完了 | 864 | 118 |
GPSNp1、投票完了 | 1007 | 104 |
GSS2N、投票完了 | 758 | 84 |
GSS2N、投票完了 | 889 | 74 |
GSSNp1、投票完了 | 533 | 94 |
GSSNp1、投票完了 | 491 | 70 |
MADS2N、投票終了 | 922 | 162 |
MADS2N、投票完了 | 2285 | 273 |
MADSNp1、投票完了 | 1155 | 201 |
MADSNp1、投票完了 | 1651 | 201 |
たとえば、表の最初の行を取得するには、「gps2noff.output.funccount
」と「gps2noff.output.iterations
」と入力します。ワークスペース ブラウザでオプションをダブルクリックし、次に output
構造をダブルクリックして、変数エディタでオプションを調べることもできます。
あるいは、出力構造からデータにアクセスすることもできます。
[outputgps2noff.funccount,outputgps2noff.iterations]
ans = 1462 136
表から得られる主な結果は次のとおりです。
UseCompletePoll
をtrue
に設定すると、通常、GPS と GSS の反復回数は減りますが、関数評価回数の変化は予測できません。UseCompletePoll
をtrue
に設定しても、MADS の反復回数は必ずしも変更されませんが、関数評価の回数は大幅に増加します。最も効率的なアルゴリズム/オプション設定。効率とは関数の数が最も少ないことを意味します。
'GSSPositiveBasisNp1'
でUseCompletePoll
をtrue
に設定 (関数数 491)'GSSPositiveBasisNp1'
でUseCompletePoll
をfalse
に設定 (関数数 533)'GSSPositiveBasis2N'
でUseCompletePoll
をfalse
に設定 (関数数 758)'GSSPositiveBasis2N'
とUseCompletePoll
をtrue
に設定 (関数数 889)
他のポーリング方法では関数の数が 900 を超えていました。
この問題の場合、最も効率的なポーリングは
'GSSPositiveBasisNp1'
でUseCompletePoll
をtrue
に設定することですが、UseCompletePoll
設定ではわずかな違いしか生じません。最も効率の悪いポーリングは、UseCompletePoll
をtrue
に設定した'MADSPositiveBasis2N'
です。この場合、UseCompletePoll
設定によって大きな違いが生じます。