ローカル検索（最適化）

コンピュータサイエンスにおいて、局所探索は計算困難な最適化問題を解決するためのヒューリスティックな方法です。局所探索は、候補となる多数の解の中から基準を最大化する解を見つけるという定式化が可能な問題に使用できます。局所探索アルゴリズムは、最適と判断される解が見つかるか、制限時間が経過するまで、局所的な変更を適用することで、候補となる解の空間 (探索空間) 内で解から解へと移動します。

局所探索アルゴリズムは、コンピュータサイエンス（特に人工知能）、数学、オペレーションズリサーチ、エンジニアリング、バイオインフォマティクスなどの多くの難しい計算問題に広く適用されています。局所探索アルゴリズムの例としては、WalkSAT、巡回セールスマン問題の2-optアルゴリズム、メトロポリス・ヘイスティングスアルゴリズムなどがあります。^[1]

局所探索アルゴリズムの代わりに勾配降下法を使用できる場合もありますが、勾配降下法は同じファミリーではありません。勾配降下法は局所最適化のための反復的な手法ですが、ソリューション空間の明示的な探索ではなく、 目的関数の勾配に依存します。

ローカル検索が適用された問題には次のようなものがあります。

1. 頂点被覆問題。グラフの頂点被覆を解とし、最小数のノードを持つ解を見つけることを目的とする。
2. 巡回セールスマン問題。グラフのすべてのノードを含むサイクルが解となり、サイクルの合計の長さを最小化することが目標となる。
3. ブール充足可能性問題。この問題では、候補解は真理値割り当てであり、目標は割り当てによって満たされる節の数を最大化することです。この場合、最終解はすべての節を満たす場合にのみ有用です。
4. 看護師のスケジュール問題。解決策は、すべての既存の制約を満たすシフトへの看護師の割り当てである。
5. k -medoidクラスタリング問題と、最悪のケースの観点から局所探索が既知の最良の近似比を提供するその他の関連施設配置問題
6. ホップフィールド ニューラル ネットワークの問題は、ホップフィールド ネットワーク内の安定した構成を見つけることです。

ほとんどの問題は、探索空間とターゲットという観点から、いくつかの異なる方法で定式化できます。たとえば、巡回セールスマン問題の場合、解決策はすべての都市を訪問するルートであり、目標は最短ルートを見つけることです。ただし、解決策はパスである場合もあり、サイクルであることがターゲットの一部となります。

局所探索アルゴリズムは、候補解から開始し、反復的に近傍解へと移動します。近傍とは、現在の解と可能な限り最小の範囲で異なるすべての潜在的な解の集合です。これには、探索空間で近傍関係を定義する必要があります。たとえば、頂点カバーの近傍は、1 つのノードだけが異なる別の頂点カバーです。ブール充足可能性の場合、ブール割り当ての近傍は、反対の状態にある単一の変数を持つものです。同じ問題に複数の異なる近傍が定義されている場合があります。解の最大k個のコンポーネントの変更を伴う近傍による局所最適化は、 k-optと呼ばれることがよくあります。

通常、すべての候補解には複数の近傍解があります。選択する解は、現在の割り当ての近傍にある解に関する情報のみを使用して行われます。そのため、局所探索と呼ばれます。近傍解の選択が、基準を局所的に最大化する解を選択することによって行われる場合、つまり貪欲探索の場合、メタヒューリスティックは山登りと呼ばれます。改善する近傍が存在しない場合は、局所探索は局所最適点で行き詰まります。この局所最適問題は、再開（異なる初期条件での反復局所探索）、ランダム化、または反復局所探索などの反復に基づくより複雑なスキーム、リアクティブ探索最適化などのメモリに基づくスキーム、シミュレーテッドアニーリングなどのメモリを使用しない確率的修正に基づくスキームを使用することで解決できます。

ローカル検索では、特定のソリューションが最適であるという保証はありません。検索は、指定された時間制限の後、またはこれまでに見つかった最適なソリューションが指定された数のステップで改善されなかった場合に終了することがあります。ローカル検索はいつでも実行できるアルゴリズムです。最初の有効なソリューションが見つかった後、いつでも中断されても、有効なソリューションを返すことができます。ローカル検索は、現在見つかった最適なソリューションが最適でなくても検索が停止する可能性があるため、通常、近似または不完全なアルゴリズムです。これは、現在の最適なソリューションを改善できなかったために終了が発生した場合でも発生する可能性があります。最適なソリューションは、アルゴリズムが通過するソリューションの近傍から遠く離れている可能性があるためです。

シュールマンとサウジーは、ローカルサーチの有効性を評価する3つの指標（深さ、モビリティ、カバレッジ）を提案している。^[2]

• 深さ: 現在の（最良）ソリューションのコスト。
• 機動性: 検索空間のさまざまな領域に迅速に移動する能力 (コストを低く抑えながら)。
• カバレッジ: 検索が検索空間をどの程度体系的にカバーするか、未探索の割り当てとすべての訪問済み割り当て間の最大距離。

彼らは、ローカル検索アルゴリズムがうまく機能するのは、検索空間をある程度理解しているからではなく、有望な領域に素早く移動し、できるだけ迅速かつ広範囲に、体系的に低深度の検索空間を探索するためだと仮説を立てています。

ローカル検索は以下のサブフィールドです:

• メタヒューリスティック
• 確率的最適化
• 最適化

ローカル検索内のフィールドには以下が含まれます。

• ヒルクライミング
• シミュレーテッドアニーリング（ローカルまたはグローバル検索のどちらにも適しています）
• タブー検索
• 遅れて受け入れたヒルクライム
• リアクティブ検索最適化（機械学習とローカル検索ヒューリスティックの組み合わせ）

実数値検索空間 のローカル検索を実行する方法はいくつかあります。

• Luus-Jaakola は、均一分布と指数関数的に減少する検索範囲を使用して局所的に検索します。
• ランダム最適化は、正規分布を使用して局所的に検索します。
• ランダム検索は、現在の位置を囲む超球をサンプリングしてローカルに検索します。
• パターン検索は、指数関数的に減少するステップ サイズを使用して、検索空間の軸に沿ってステップを実行します。

• バッティティ、ロベルト。マウロ・ブルナート;フランコ・マシア (2008)。リアクティブ検索とインテリジェントな最適化。スプリンガー・フェルラーグ。ISBN 978-0-387-09623-02012年3月16日時点のオリジナルよりアーカイブ。
• Hoos, HHおよび Stutzle, T. (2005) 確率的局所探索: 基礎と応用、Morgan Kaufmann。
• Vijay Arya、Naveen Garg、Rohit Khandekar、Adam Meyerson、Kamesh Munagala、Vinayaka Pandit、(2004):k-Medianおよび施設配置問題のための局所探索ヒューリスティック、SIAM Journal of Computing 33(3)。
• ユライ・フロムコビッチ：難問のためのアルゴリズム：組み合わせ最適化、ランダム化、近似、ヒューリスティックス入門（Springer）
• Wil Michaels、Emile Aarts、Jan Korst: ローカル検索の理論的側面 (Springer)