MCSアルゴリズム

数学的最適化において、マルチレベル座標探索（MCS）は、関数値のみを用いた境界制約付きグローバル最適化のための効率的な^[1] アルゴリズムである。^[2]

これを行うには、n 次元の検索空間を交差しない超立方体 (ボックス) のセットで表します。次に、ボックス (およびその近傍) の代表点における関数の値とボックスのサイズに応じて、軸平面に沿ってボックスを繰り返し分割します。これらの 2 つの分割基準を組み合わせることで、大きなボックスを分割するグローバル検索と、関数値が適切な領域を分割するローカル検索が形成されます。

さらに、関数の（多次元）二次補間と直線探索を組み合わせた局所探索を使用して、アルゴリズムのパフォーマンスを増強することができます（局所探索を使用した MCS）。この場合、単純なMCS を使用して開始（初期）ポイントが提供されます。局所探索によって提供される情報（目的関数の局所最小値）は、その後、オプティマイザーにフィードバックされ、分割基準に影響します。その結果、局所最小値周辺のサンプルのクラスタリングが削減され、収束が速くなり、精度が向上します。

MCS ワークフローは図 1 と 2 に示されています。アルゴリズムの各ステップは 4 つの段階に分けられます。

1. 分割の候補となる可能性のある部分を特定します (マゼンタ、太字)。
2. 最適な分割方向と分割点の予想される最適位置 (緑) を特定します。
3. 分割ポイントで目的関数を評価するか、すでに計算されたセットから目的関数を回復します。後者は、隣接するボックスを分割するときに現在の分割ポイントにすでに到達している場合に適用されます。
4. 分割ポイントでの目的関数の値に基づいて、新しいボックス (マゼンタ、細い) を生成します。

各ステップで、一時的に黄色のハローが付いた緑色の点は、ボックスの 一意のベース ポイントです。各ボックスには、目的の関連付けられた値、つまりボックスのベース ポイントでの値があります。

ボックスを分割するかどうかを決定するために、2 つの分割基準が使用されます。1 つ目はランクによる分割で、あまり分割されていない大きなボックスが最終的に分割されることが保証されます。これが適用される場合、分割ポイントは分割される辺の長さの固定分数で簡単に決定されます。2 つ目は期待ゲインによる分割で、単一の座標に沿ってローカル 1 次元放物線二次モデル (サロゲート) を使用します。この場合、分割ポイントは線分に沿ったサロゲートの最小値として定義され、補間値 (目的関数の真の値のプロキシとして機能) が現在の最適サンプリング関数値よりも低い場合にのみボックスが分割されます。

目的関数がグローバル最小値近傍で連続している場合、アルゴリズムは長期的にはグローバル最小値に収束することが保証されます (つまり、関数評価の数と検索の深さが任意に大きい場合)。これは、どのボックスも最終的には任意に小さくなるため、関数評価の数が無限大に近づくにつれてサンプル間の間隔がゼロに近づくという事実に由来します。

MCS は、ツリーの助けを借りて効率的な再帰的な方法で実装されるように設計されています。このアプローチでは、サンプリング ポイントが明示的に保存されないため、必要なメモリの量は問題の次元に依存しません。代わりに、各サンプルの 1 つの座標のみが保存され、残りの座標はボックスの履歴をルート (最初のボックス) まで遡って復元できます。この方法は著者によって提案され、元の実装で使用されました。^[2]

• アルゴリズムのホームページ
• 他のアルゴリズムと比較したアルゴリズムのパフォーマンス