投票の種類

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

一般化パターン検索における完全投票の使用

例として、次の関数を考えてみましょう。

$f (x_{1}, x_{2}) = {\begin{array}{l} x_{1}^{2} + x_{2}^{2} - 25 & for x_{1}^{2} + x_{2}^{2} \leq 25 \\ x_{1}^{2} + {(x_{2} - 9)}^{2} - 16 & for x_{1}^{2} + {(x_{2} - 9)}^{2} \leq 16 \\ 0 & otherwise . \end{array}$

次の図は関数のプロットを示しています。

図を生成するコード

関数のグローバル最小値は (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 の反復回数は必ずしも変更されませんが、関数評価の回数は大幅に増加します。
最も効率的なアルゴリズム/オプション設定。効率とは関数の数が最も少ないことを意味します。
1. 'GSSPositiveBasisNp1' で UseCompletePoll を true に設定 (関数数 491)
2. 'GSSPositiveBasisNp1' で UseCompletePoll を false に設定 (関数数 533)
3. 'GSSPositiveBasis2N' で UseCompletePoll を false に設定 (関数数 758)
4. 'GSSPositiveBasis2N' と UseCompletePoll を true に設定 (関数数 889)
他のポーリング方法では関数の数が 900 を超えていました。
この問題の場合、最も効率的なポーリングは 'GSSPositiveBasisNp1' で UseCompletePoll を true に設定することですが、UseCompletePoll 設定ではわずかな違いしか生じません。最も効率の悪いポーリングは、UseCompletePoll を true に設定した 'MADSPositiveBasis2N' です。この場合、UseCompletePoll 設定によって大きな違いが生じます。