このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。
GlobalSearchとMultiStartの仕組み
ローカルソルバーの複数回実行
GlobalSearch
と MultiStart
は、グローバル最小値または複数の最小値を見つけるための同様のアプローチを採用しています。どちらのアルゴリズムも、複数の開始点からローカル ソルバー (fmincon
など) を開始します。アルゴリズムは複数の開始点を使用して、複数の吸引域をサンプリングします。詳細については、引き込み領域を参照してください。
ソルバーオブジェクトの違い
GlobalSearch と MultiStart アルゴリズムの概要 には、GlobalSearch
および MultiStart
アルゴリズムのスケッチが含まれています。
GlobalSearch と MultiStart アルゴリズムの概要
GlobalSearch
と MultiStart
の主な違いは次のとおりです。
GlobalSearch
は、開始点を生成するために散布検索メカニズムを使用します。MultiStart
は、境界内に均一に分散された開始点、またはユーザーが指定した開始点を使用します。GlobalSearch
は開始点を分析し、これまでに見つかった最良の局所最小値を改善する可能性が低い開始点を拒否します。MultiStart
はすべての開始点 (または、オプションで、境界または不等式制約に関して実行可能なすべての開始点) を実行します。MultiStart
は、ローカル ソルバーの選択肢を提供します:fmincon
、fminunc
、lsqcurvefit
、またはlsqnonlin
。GlobalSearch
アルゴリズムはfmincon
を使用します。MultiStart
は並列実行が可能で、ローカル ソリューションのために開始ポイントを複数のプロセッサに分散します。MultiStart
を並列で実行するには、 Global Optimization Toolbox で並列処理を使用する方法 を参照してください。
使用するソルバーの決定
これらのソルバー オブジェクト間の違いは、どちらを使用するかという次の決定に要約されます。
GlobalSearch
を使用して、単一のプロセッサ上で単一のグローバル最小値を最も効率的に見つけます。MultiStart
を使用して次を行います。複数の局所最小値を見つけます。
並行して実行します。
fmincon
以外のソルバーを使用してください。全体的な最小値を徹底的に検索します。
あなた自身の出発点を探索してください。
グローバルサーチアルゴリズム
アルゴリズムの説明については、Ugray et al. [1] を参照してください。
GlobalSearch
オブジェクトを run
すると、アルゴリズムは次の手順を実行します。
x0からfminconを実行する
GlobalSearch
は、problem
構造で指定した開始点から fmincon
を実行します。この実行が収束すると、GlobalSearch
は、吸引域の半径の初期推定値の開始点と終了点を記録します。さらに、GlobalSearch
は、スコア 関数で使用するための最終的な目的関数値を記録します (ステージ1スタートポイントを取得して実行 を参照)。
スコア関数は、ある時点での目的関数値の合計と制約違反の合計の倍数です。したがって、実行可能なポイントのスコアはその目的関数の値に等しくなります。制約違反の倍数は最初は 1000 です。GlobalSearch
は実行中に倍数を更新します。
トライアルポイントを生成する
GlobalSearch
は、散布検索アルゴリズムを使用して、NumTrialPoints
試行ポイントのセットを生成します。トライアルポイントは潜在的な開始点です。散布検索アルゴリズムの説明については、Glover [2] を参照してください。GlobalSearch
は、設定した有限境界内で試行ポイントを生成します (lb
および ub
)。無制限のコンポーネントには人工的な境界が課せられます: lb = -1e4 + 1
、ub = 1e4 + 1
。この範囲は原点を中心に対称ではないため、原点は散布検索に含まれません。片側境界を持つコンポーネントには、無限側に課された人工境界があり、lb < ub
を維持するために有限境界によってシフトされます。
ステージ1スタートポイントを取得して実行
GlobalSearch
は、NumStageOnePoints
個の試行ポイントのセットのスコア関数を評価します。次に、最高スコアのポイントを取得し、そのポイントから fmincon
を実行します。GlobalSearch
は、検査するポイントのリストから NumStageOnePoints
試行ポイントのセットを削除します。
流域、カウンター、しきい値を初期化する
localSolverThreshold
は、最初はソリューション ポイントにおける 2 つの目的関数値のうち小さい方です。解決ポイントは、x0
から始まる fmincon
ソリューションと、ステージ 1 の開始ポイントです。これらのソリューション ポイントが両方とも存在しないか実行不可能な場合、localSolverThreshold
は最初はステージ 1 の開始ポイントのペナルティ関数値になります。
GlobalSearch
ヒューリスティック仮定は、吸引盆地が球形であるというものです。x0
からの解点とステージ 1 からの解点の吸引域の初期推定値は、解点を中心とした球体です。各球の半径は、初期点から解点までの距離です。これらの推定流域は重複する可能性があります。
アルゴリズムに関連付けられたカウンターのセットが 2 つあります。各カウンターは、次の連続した試行ポイントの数です。
引力の盆地内に横たわる。各洗面台にカウンターが1つずつあります。
スコア関数が
localSolverThreshold
より大きい。スコアの定義については、x0からfminconを実行する を参照してください。
すべてのカウンターは最初は 0 です。
メインループの開始
GlobalSearch
はリストから残りの試行ポイントを繰り返し調べ、次の手順を実行します。時間を継続的に監視し、経過時間が MaxTime
秒を超えると検索を停止します。
ステージ2のトライアルポイントを調べてfminconが実行されるかどうかを確認します
試行ポイントを p
と呼び出します。次の条件が満たされる場合は、p
から fmincon
を実行します。
p
は既存の流域内に存在しません。各流域i
の基準は次のとおりです。|p - center(i)| > DistanceThresholdFactor * radius(i).
DistanceThresholdFactor
はオプションです (デフォルト値は0.75
)。radius
は、流域の半径としきい値の更新および 大きなカウンター値への反応で更新される推定半径です。スコア(
p
) <localSolverThreshold
。(オプション)
p
は、境界制約および/または不等式制約を満たします。このテストは、GlobalSearch
オブジェクトのStartPointsToRun
プロパティを'bounds'
または'bounds-ineqs'
に設定した場合に発生します。
fmincon の実行時
カウンターをリセット
流域としきい値のカウンターを 0 に設定します。
ソリューションセットの更新
fmincon
がp
から開始して実行される場合、収束を示す肯定的な終了フラグが生成される可能性があります。その場合、GlobalSearch
はGlobalOptimSolution
オブジェクトのベクトルを更新します。解点をxp
、目的関数値をfp
と呼びます。2つのケースがあります:目的関数値
fq
を持つ他のすべての解点xq
については、|xq - xp| > XTolerance * max(1,|xp|)
または
|fq - fp| > FunctionTolerance * max(1,|fp|)
.この場合、
GlobalSearch
はGlobalOptimSolution
オブジェクトのベクトルに新しい要素を作成します。各オブジェクトに含まれる情報の詳細については、GlobalOptimSolution
を参照してください。目的関数値
fq
を持つ他の解点xq
については、|xq - xp| <= XTolerance * max(1,|xp|)
と
|fq - fp| <= FunctionTolerance * max(1,|fp|)
.この場合、
GlobalSearch
はxp
をxq
と同等とみなします。GlobalSearch
アルゴリズムは、X0
ポイントのセル配列にp
を追加して、xq
のGlobalOptimSolution
を変更します。このアップデートでは、小さな調整が 1 つ行われる可能性があります。
xq
の終了フラグが1
より大きく、xp
の終了フラグが1
の場合、xp
がxq
に置き換えられます。この置き換えにより、同じ流域内のいくつかのポイントがxp
からXTolerance
以上の距離になることがあります。
流域半径と閾値の更新
現在の
fmincon
実行の終了フラグが正の場合:開始点
p
のスコア値にしきい値を設定します。xp
の流域半径を、既存の半径(存在する場合)とp
とxp
の間の距離の最大値に設定します。
反復表示へのレポート
GlobalSearch
Display
プロパティが'iter'
の場合、fmincon
が実行するすべてのポイントによって、GlobalSearch
反復表示に 1 行が作成されます。
fmincon が実行されない場合
カウンターの更新
p
を含むすべてのベイスンのカウンターを増分します。他のすべての盆地のカウンターを0
にリセットします。score(
p
) >=localSolverThreshold
の場合、しきい値カウンターを増分します。それ以外の場合は、カウンターを0
にリセットします。大きなカウンター値に反応する
カウンターが
MaxWaitCycle
に等しい各盆地については、盆地の半径に1
–BasinRadiusFactor
を掛けます。カウンターを0
にリセットします。(MaxWaitCycle
とBasinRadiusFactor
は両方ともGlobalSearch
オブジェクトの設定可能なプロパティです。)しきい値カウンターが
MaxWaitCycle
に等しい場合は、しきい値を増やします。新しいしきい値 = しきい値 +
PenaltyThresholdFactor
*(1
+ abs(しきい値)).カウンターを
0
にリセットします。反復表示へのレポート
200 番目の試行ポイントごとに、
GlobalSearch
反復表示に 1 行が作成されます。
GlobalOptimSolutionを作成する
MaxTime
秒に達するか試行ポイントがなくなると、GlobalSearch
は GlobalOptimSolution
オブジェクトのベクトルを作成します。(これらのポイントは、正の fmincon
終了フラグに対応します。) GlobalSearch
は、ベクトルを目的関数の値によって、最低 (最良) から最高 (最悪) の順に並べます。これでアルゴリズムは終了です。
マルチスタートアルゴリズム
MultiStart
オブジェクトを run
すると、アルゴリズムは次の手順を実行します。
入力の検証
MultiStart
は入力引数の有効性をチェックします。チェックには、問題の入力に対してローカル ソルバーを 1 回実行することが含まれます。並列で実行する場合でも、MultiStart
はこれらのチェックをシリアルで実行します。
開始点を生成する
MultiStart
を次の構文で呼び出すと
[x,fval] = run(ms,problem,k)
整数 k
の場合、MultiStart
は、RandomStartPointSet
オブジェクトを使用した場合とまったく同じように k - 1
開始点を生成します。このアルゴリズムは、problem
構造の x0
開始点も使用するため、合計 k
開始点になります。
RandomStartPointSet
オブジェクトには、オブジェクト内に保存されるポイントがありません。代わりに、MultiStart
は list
を呼び出し、problem
構造によって指定された境界内でランダムなポイントを生成します。無制限のコンポーネントが存在する場合、list
は RandomStartPointSet
オブジェクトの ArtificialBound
プロパティによって指定された人工的な境界を使用します。
CustomStartPointSet
オブジェクトを指定した場合、MultiStart
は開始点を生成せず、オブジェクト内の点を使用します。
フィルター開始点(オプション)
MultiStart
オブジェクトの StartPointsToRun
プロパティを 'bounds'
または 'bounds-ineqs'
に設定すると、MultiStart
は実行不可能な開始点からローカル ソルバーを実行しません。この文脈では、「実行不可能」とは、境界を満たさない開始点、または境界と不等式制約の両方を満たさない開始点を意味します。
StartPointsToRun
のデフォルト設定は 'all'
です。この場合、MultiStart
は実行不可能な開始点を破棄しません。
ローカルソルバーを実行する
MultiStart
は、StartPointsToRun
フィルターを通過するポイントから開始して、problem.solver
で指定されたローカル ソルバーを実行します。MultiStart
が並列で実行されている場合、開始点がワーカー プロセッサに 1 つずつ送信され、ワーカー プロセッサがローカル ソルバーを実行します。
ローカル ソルバーは、各反復で、MultiStart
が計算を開始してから MaxTime
秒が経過したかどうかを確認します。そうであれば、MultiStart
は解決策を報告せずにその反復を終了します。
ローカル ソルバーが停止すると、MultiStart
は正のローカル ソルバー終了フラグに対応する結果を保存し、次のステップに進みます。
反復表示へのレポート. MultiStart
Display
プロパティが 'iter'
の場合、ローカル ソルバーが実行するすべてのポイントによって、MultiStart
反復表示に 1 行が作成されます。
停止条件を確認する
MultiStart
は開始ポイントがなくなると停止します。また、合計実行時間が MaxTime
秒を超えると停止します。
GlobalOptimSolution オブジェクトを作成する
MultiStart
が停止条件に達すると、アルゴリズムは次のように GlobalOptimSolution
オブジェクトのベクトル (すべて正のローカル ソルバー終了フラグに対応) を作成します。
ローカル ソリューションを目的関数値 (
Fval
) で最低から最高の順に並べ替えます。lsqnonlin
およびlsqcurvefit
ローカル ソルバーの場合、目的関数は残差のノルムです。最も低い(最良)
Fval
から始めて、ローカル ソリューションj
をループします。両方を満たす
k
のすべての解を見つけます。|Fval(k) - Fval(j)| <= FunctionTolerance*max(1,|Fval(j)|)
|x(k) - x(j)| <= XTolerance*max(1,|x(j)|)
j
、Fval(j)
、j
のローカル ソルバーoutput
構造、およびj
とすべてのk
の開始点のセル配列を記録します。これらのポイントk
をローカル ソリューションのリストから削除します。この点は、GlobalOptimSolution
オブジェクトのベクトル内の 1 つのエントリです。
結果として得られる GlobalOptimSolution
オブジェクトのベクトルは、Fval
によって最低 (最良) から最高 (最悪) の順に並べられます。
反復表示へのレポート. すべてのローカルソリューションを検査した後、MultiStart
は反復表示に要約を表示します。この概要には、収束したローカル ソルバー実行の数、収束に失敗した数、およびエラーが発生した数が含まれます。
参考文献
[1] Ugray, Zsolt, Leon Lasdon, John C. Plummer, Fred Glover, James Kelly, and Rafael Martí. Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization. INFORMS Journal on Computing, Vol. 19, No. 3, 2007, pp. 328–340.
[2] Glover, F. “A template for scatter search and path relinking.” Artificial Evolution (J.-K. Hao, E.Lutton, E.Ronald, M.Schoenauer, D.Snyers, eds.). Lecture Notes in Computer Science, 1363, Springer, Berlin/Heidelberg, 1998, pp. 13–54.
[3] Dixon, L. and G. P. Szegö. “The Global Optimization Problem: an Introduction.” Towards Global Optimisation 2 (Dixon, L. C. W. and G. P. Szegö, eds.). Amsterdam, The Netherlands: North Holland, 1978.