MCSアルゴリズム

MCS_algorithm

 「MCSアルゴリズム」  
マルチレベル座標検索(MCS)は、関数値のみを使用する境界制約付き大域最適化のための効率的なアルゴリズムです。
図1: 2次元Rosenbrock関数に適用されたMCSアルゴリズム(ローカル検索なし) 。グローバルミニマム f m私 n = 0{ f_ {min} = 0}
にあります
(( X y
)。 = (( 1 1 )。 {(x、y)=(1,1)}
。MCSはポジションを次のように識別します f ≈ 0.002 { f upperx 0.002}
21の機能評価内。追加の21回の評価の後、最適値は改善されず、アルゴリズムは終了します。潜在的な最小値の周りのサンプルの密なクラスタリングを観察します。この影響は、ローカル検索を適切に使用することで大幅に減らすことができます。
そのために、n次元の探索空間は、交差しない超立方体(ボックス)のセットで表されます。次に、ボックスは、ボックス(およびその隣接点)の代表点での関数の値とボックスのサイズに従って、軸平面に沿って繰り返し分割されます。これらの2つの分割基準を組み合わせて、大きなボックスを分割することによるグローバル検索と、関数値が適切な領域を分割することによるローカル検索を形成します。
さらに、関数の(多次元)2次補間とライン検索を組み合わせたローカル検索を使用して、アルゴリズムのパフォーマンスを向上させることができます(MCSとローカル検索)。この場合、プレーンMCSを使用して開始(初期)ポイントを提供します。ローカル検索によって提供された情報(つまり、目的関数のローカル最小値)は、オプティマイザーにフィードバックされ、分割基準に影響を与えます。その結果、ローカル最小値の周りのサンプルクラスタリングが減少し、収束が速くなります。
内容
1 簡素化されたワークフロー
2 収束
3 再帰的な実装
4 参考文献
5 外部リンク
簡素化されたワークフロー
基本的なワークフローを図1に示します。一般に、各ステップは次の3つの段階で特徴付けることができます。
分割の潜在的な候補を特定します(マゼンタ、厚い)。
最適な分割方向と分割ポイントの予想される最適な位置(緑)を特定します。
これまで考慮されていなかった分割点で目的関数を評価します。分割(緑)ポイントでの目的関数の値に基づいて、新しいボックス(マゼンタ、シン)を生成します。
すべてのステップで、少なくとも1つの分割点(黄色)が既知の関数サンプル(赤)であるため、目的がそこで再度評価されることはありません。
ボックスが分割されるかどうかを決定するために、2つの別々の分割基準が使用されます。最初のランクによる分割は、あまり頻繁に分割されていない大きなボックスが最終的に分割されることを保証します。それが当てはまる場合、分割点は事前に決定することができます。2つ目は、期待ゲインで分割し、単一の座標に沿ったローカル1次元2次モデル(代理)を使用します。この場合、分割点はサロゲートの最小値として定義され、ボックスは、そこにある補間値が現在の最良のサンプリングされた関数値よりも低い場合にのみ分割されます。
収束
目的関数がグローバル最小化器の近傍で連続である場合、アルゴリズムは長期的に(つまり、関数評価の数と検索深度が任意に大きい場合)グローバル最小値に収束することが保証されます。これは、ボックスが最終的に任意に小さくなるため、関数評価の数が無限大になる傾向があるため、サンプル間の間隔がゼロになる傾向があるためです。
再帰的な実装
MCSは、ツリーを使用して効率的な再帰的な方法で実装されるように設計されています。このアプローチでは、サンプリングポイントが明示的に保存されないため、必要なメモリの量は問題の次元に依存しません。代わりに、各サンプルの1つの座標のみが保存され、ボックスの履歴をルート(最初のボックス)までさかのぼってトレースすることにより、残りの座標を復元できます。この方法は、著者によって提案され、元の実装で使用されました。
注意深く実装すると、これにより、関数評価の繰り返しを回避することもできます。より正確には、サンプリングポイントが2つの隣接するボックスの境界に沿って配置されている場合、この情報は、ポイントの履歴を少数のステップでバックトレースすることで抽出できることがよくその結果、(潜在的に高価な)目的関数を評価せずに新しいサブボックスを生成できます。このシナリオは、緑(黄色ではない)と赤の点が一致するときはいつでも、図1に視覚化されています。
(( −
0.5 0.5 )。 {(-0.5,0.5)}

  そして
(( 1.0 3.5 )。 {(1.0,3.5)}

  分割されます。
参考文献
外部リンク
アルゴリズムのホームページ
他と比較したアルゴリズムのパフォーマンス

投稿日:
カテゴリー: M