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

開始点を絞り込む

開始点の絞り込みについて

問題の一部のコンポーネントが制約されていない場合、GlobalSearch と MultiStart は人工的な境界を使用して、各コンポーネントで均一にランダムな開始点を生成します。ただし、問題の最小値が広範囲にわたる場合は、これらの最小値を見つけるために広範囲に分散した開始点が必要になります。

広範囲に分散した開始点を取得するには、次の方法を使用します。

• problem 構造で広く離れた境界を指定します。

• MultiStart アルゴリズムで RandomStartPointSet オブジェクトを使用します。RandomStartPointSet オブジェクトの ArtificialBound プロパティに大きな値を設定します。

• MultiStart アルゴリズムで CustomStartPointSet オブジェクトを使用します。広範囲に分散した開始点を使用します。

それぞれの方法には長所と短所があります。

メソッド	長所	欠点
problem で境界を与える	自動ポイント生成	より複雑なヘッセン行列を作成する
	GlobalSearch と一緒に使用できます	境界をどの程度大きく設定するか不明
	簡単にできる	変更点 problem
	境界は非対称になることがある	均一なポイントのみ
RandomStartPointSet の大きな ArtificialBound	自動ポイント生成	MultiStart のみ
	problemは変更されません	対称で均一な点のみ
	簡単にできる	ArtificialBound をどのくらいの大きさに設定すればよいか不明
CustomStartPointSet	カスタマイズ可能	MultiStart のみ
	problemは変更されません	ポイントを生成するためのプログラミングが必要

開始点を生成する方法

• 等間隔グリッド

• 乱れたグリッド

• 制約のないコンポーネントの広範囲に分散したポイント

等間隔グリッド

開始点の均一なグリッドを生成するには:

1. ndgrid を使用して多次元配列を生成します。各コンポーネントの下限、間隔、上限を指定します。

   例えば、3次元配列のセットを生成するには、

   • 最初の成分は -2 から 0、間隔は 0.5

   • 2 番目のコンポーネントは 0 から 2、間隔は 0.25

   • 3番目の要素は-10から5まで、間隔は1

   [X,Y,Z] = ndgrid(-2:.5:0,0:.25:2,-10:5);

2. 配列を 1 つのマトリックスに配置し、各行が 1 つの開始点を表します。以下に例を示します。

   W = [X(:),Y(:),Z(:)];

   この例では、W は 720 行 3 列の行列です。

3. 行列を CustomStartPointSet オブジェクトに格納します。以下に例を示します。

   custpts = CustomStartPointSet(W);

CustomStartPointSet オブジェクトを 3 番目の入力として run を呼び出します。以下に例を示します。

% Assume problem structure and ms MultiStart object exist
[x,fval,flag,outpt,manymins] = run(ms,problem,custpts);

乱れたグリッド

整数の開始点では、わずかに変動した開始点よりも堅牢性の低いソリューションが生成される可能性があります。

開始点の乱れたセットを取得するには:

1. 等間隔グリッド の手順 1 ～ 2 のように開始点のマトリックスを生成します。

2. 平均が 0 で分散が比較的小さいランダム正規行列を追加して、開始点を乱します。

   等間隔グリッド の例では、W 行列を作成した後、摂動を追加します。

   [X,Y,Z] = ndgrid(-2:.5:0,0:.25:2,-10:5);
   W = [X(:),Y(:),Z(:)];
   W = W + 0.01*randn(size(W));

3. 行列を CustomStartPointSet オブジェクトに格納します。以下に例を示します。

   custpts = CustomStartPointSet(W);

CustomStartPointSet オブジェクトを 3 番目の入力として run を呼び出します。以下に例を示します。

% Assume problem structure and ms MultiStart object exist
[x,fval,flag,outpt,manymins] = run(ms,problem,custpts);

制約のないコンポーネントの広範囲に分散したポイント

問題の一部のコンポーネントには上限または下限がない可能性があります。以下に例を示します。

• 明確な境界は存在しませんが、コンポーネントが達成できないレベルが存在します。たとえば、1 つのコンポーネントが 1 個のダイヤモンドの重量を表す場合、暗黙の上限は 1 kg になります (ホープ ダイヤモンドは 10 g 未満です)。このような場合は、暗黙の境界を上限として指定します。

• 本当に上限はありません。たとえば、コンピュータ ファイルのサイズ (バイト単位) には有効な上限はありません。現在、最大サイズはギガバイトまたはテラバイトですが、10 年後はどうなっているかは誰にもわかりません。

完全に無制限のコンポーネントの場合は、次のサンプリング方法を使用できます。各領域に約 1/n 個のポイント (exp(n),exp(n+1)) を生成するには、次の式を使用します。u がランダムで 0 から 1 まで均一に分布している場合、r = 2u – 1 は -1 から 1 まで均一に分布します。取る

$$y=\mathrm{sgn}(r)\left(\exp \left(1/\left|r\right|\right)-e\right).$$

y は対称かつランダムです。lb で下方に境界が定められた変数の場合、

$$y=\text{lb}+\left(\exp \left(1/u\right)-e\right).$$

同様に、ubで上界となる変数については、

$$y=\text{ub}-\left(\exp \left(1/u\right)-e\right).$$

例えば、3次元の問題があるとします。

• x(1) > 0

• x(2) 100未満

• x(3) 制約なし

これらの制約を満たす 150 個の開始点を作成するには:

u = rand(150,3);
r1 = 1./u(:,1);
r1 = exp(r1) - exp(1);
r2 = 1./u(:,2);
r2 = -exp(r2) + exp(1) + 100;
r3 = 1./(2*u(:,3)-1);
r3 = sign(r3).*(exp(abs(r3)) - exp(1));
custpts = CustomStartPointSet([r1,r2,r3]);

以下はこのアルゴリズムのバリエーションです。下限値の方法で 0 から無限大までの数を生成します。この数値を点の半径として使用します。各コンポーネントに対して乱数を取得し、半径を掛けて、ポイントの他のコンポーネントを生成します。半径を掛ける前に乱数を正規化して、そのノルムを 1 にすることができます。この方法の実例については、境界のないマルチスタート、広範囲に分散したスタートポイント を参照してください。

例: より良い解決策を求めて

MultiStart は 全体的または複数の局所的最小値を見つける のグローバル最小値を見つけることができません。より良い解決策を探すには、2 つの簡単な方法があります。

• より多くのスタートポイントを使用する

• 検索空間の境界を狭める

問題の構造と MultiStart オブジェクトを設定します。

problem = createOptimProblem('fminunc',...
    'objective',@(x)sawtoothxy(x(1),x(2)),...
    'x0',[100,-50],'options',...
    optimoptions(@fminunc,'Algorithm','quasi-newton'));
ms = MultiStart;

より多くのスタートポイントを使用する

50 ではなく 200 の開始ポイントの問題に対して MultiStart を実行します。

rng(14,'twister') % for reproducibility
[x,fval,exitflag,output,manymins] = run(ms,problem,200)

MultiStart completed some of the runs from the start points.

53 out of 200 local solver runs converged with a positive local solver exit flag.

x =

   1.0e-06 *

   -0.2284   -0.5567


fval =

   2.1382e-12


exitflag =

     2


output = 

  struct with fields:

                funcCount: 32670
         localSolverTotal: 200
       localSolverSuccess: 53
    localSolverIncomplete: 147
    localSolverNoSolution: 0
                  message: 'MultiStart completed some of the runs from the start points.↵↵53 out of 200 local solver runs converged with a positive local solver exit flag.'

manymins = 
  1x53 GlobalOptimSolution

  Properties:
    X
    Fval
    Exitflag
    Output
    X0

今回、MultiStart はグローバル最小値を発見し、51 個のローカル最小値を発見しました。

局所解の範囲を確認するには、「histogram([manymins.Fval],10)」と入力します。

開始点のより厳密な境界

興味深いローカル ソリューションのすべてのコンポーネントの絶対値が 100 未満であると考えているとします。開始点の境界のデフォルト値は 1000 です。境界の異なる値を使用するには、ArtificialBound プロパティを 100 に設定した RandomStartPointSet を生成します。

startpts = RandomStartPointSet('ArtificialBound',100,...
    'NumStartPoints',50);
[x,fval,exitflag,output,manymins] = run(ms,problem,startpts)

MultiStart completed some of the runs from the start points.

29 out of 50 local solver runs converged with a positive local solver exit flag.

x =

   1.0e-08 *

    0.9725   -0.6198


fval =

   1.4955e-15


exitflag =

     2


output = 

  struct with fields:

                funcCount: 7431
         localSolverTotal: 50
       localSolverSuccess: 29
    localSolverIncomplete: 21
    localSolverNoSolution: 0
                  message: 'MultiStart completed some of the runs from the start points.↵↵29 out of 50 local solver runs converged with a positive local solver exit flag.'

manymins = 
  1x25 GlobalOptimSolution

  Properties:
    X
    Fval
    Exitflag
    Output
    X0

MultiStart はグローバル最小値を見つけ、22 個の異なるローカル解を見つけました。局所解の範囲を確認するには、「histogram([manymins.Fval],10)」と入力します。

より多くのスタートポイントを使用する で見つかった最小値と比較すると、この実行ではより良い (より小さい) 最小値が見つかり、成功した実行の割合が高くなりました。

関連するトピック

• グローバルまたは複数の開始点検索
• 孤立したグローバル最小値