局所探索法とは、組合せ最適化問題などの難しい問題に対して、近似最適解を効率的に求めるための探索アルゴリズムの一種です。
現在得られている解の近傍を探索し、より良い解が見つかればそちらへ移動するという操作を繰り返すことで、徐々に解を改善していきます。
局所探索法の基本的な考え方
局所探索法の基本的な考え方は、以下の通りです。
- 初期解の設定: まず、適当な初期解を設定します。
- 近傍の探索: 現在の解の近傍（少しだけ変更を加えた解の集合）を探索します。
- 解の更新: 近傍に現在の解よりも良い解があれば、そちらへ移動します。
- 終了条件の判定: 終了条件（決められた回数の繰り返し、改善が見られなくなったなど）を満たせば終了し、そうでなければ2に戻ります。
局所探索法のメリットとデメリット
局所探索法は、比較的単純なアルゴリズムでありながら、多くの場合に良い解を効率的に見つけられるというメリットがあります。しかし、局所最適解（近傍にはより良い解がないが、全体としては最適ではない解）に陥りやすいというデメリットもあります。
局所探索法の種類
局所探索法には、様々なバリエーションが存在します。代表的なものを以下に示します。
- 山登り法:
- 近傍の中で最も良い解へ常に移動する最も基本的な局所探索法です。
- 単純なため実装が容易ですが、局所最適解に陥りやすいという欠点があります。
- 焼きなまし法 (Simulated Annealing):
- 確率的に悪い解への移動も許容することで、局所最適解からの脱出を試みる手法です。
- 徐々に確率を下げていくことで、最終的には最適解に近い解を得られる可能性が高まります。
- タブーサーチ (Tabu Search):
- 過去に訪れた解をタブーリストに記録し、一定期間は再訪しないようにすることで、探索の多様性を高める手法です。
- 局所最適解からの脱出と、効率的な探索の両立を目指します。
局所探索法の応用例
局所探索法は、様々な分野で応用されています。以下に代表的な例を示します。
- 巡回セールスマン問題 (TSP):
- 都市の訪問順序を少しずつ変更しながら、より短い経路を探索します。
- スケジューリング問題:
- タスクの実行順序や割り当てを少しずつ変更しながら、より効率的なスケジュールを探索します。
- 画像処理:
- 画像のノイズ除去や最適化などに応用されます。
局所探索法は、難しい組合せ最適化問題に対して、効率的に近似最適解を求めるための強力なツールです。適切な近傍の定義やパラメータ設定を行うことで、様々な問題に対して有効な解法となり得ます。
