局所探索アルゴリズムと最適解へのアプローチ：ヒルクライミング、ランダムリスタート、焼きなまし法の実践
最適化問題を解く際、完全な解空間を探索するのは時間がかかりすぎる場合があります。この記事では、局所探索アルゴリズムを使って効率的に「かなり良い解」を見つける方法を紹介します。特に以下の3つの手法に焦点を当てます：
- ヒルクライミング（Hill Climbing）
- ランダムリスタート（Random Restart）
- 焼きなまし法（Simulated Annealing）
1. 局所探索の限界：局所最適解と大域最適解
局所探索では、現在の状態とその隣接状態（近い配置）を基にコスト関数や目的関数を評価します。しかし、局所最適解に陥る可能性があります。局所最適解はその近隣では最善ですが、全体の中で最善ではない場合もあります。
例として、病院の配置問題を考えます：
- 目標: 各家から最寄りの病院までの距離の合計（コスト）を最小化する。
- 課題: 隣接する状態のみを探索すると、大域最適解（最良の配置）を見つけられない可能性がある。
2. ランダムリスタート：局所最適解からの脱出
ランダムリスタートは、ヒルクライミングの欠点を克服するための手法です。単に探索を1回行うのではなく、複数回ランダムに初期状態を生成し、それぞれでヒルクライミングを実行します。
ランダムリスタートの手順
- ランダムに初期状態を生成。
- ヒルクライミングを実行して局所最適解を見つける。
- 結果を記録し、次の初期状態で再び探索。
- 全探索が終了したら、最良の解を選択。
実例
- 初期状態のコスト: 56
- 20回のリスタートで以下の結果を得る：
- 最良コスト: 41（3回目の試行）
- 他の試行では41より良い結果は得られなかった。
ランダムリスタートは計算時間が増加するものの、局所最適解に囚われるリスクを減らす効果があります。
3. 焼きなまし法：悪い選択を許容して大域最適解を目指す
焼きなまし法（Simulated Annealing）は、物理学の「焼きなまし」プロセスに基づいた手法です。このアルゴリズムは、高温の状態ではランダムな探索を許容し、低温になるにつれて探索範囲を狭めるという特性を持ちます。
焼きなまし法の基本概念
-
高温の状態:
- より悪い状態（コストが高い状態）への移動を許容。
- ランダム性が高く、探索範囲が広い。
-
低温の状態:
- より悪い状態への移動を抑制。
- 解が収束し、大域最適解に近づく。
焼きなまし法の擬似コード
def simulated_annealing(problem, max_iterations):
current = problem.initial_state()
for t in range(1, max_iterations + 1):
temperature = calculate_temperature(t, max_iterations)
neighbor = random_neighbor(current)
delta_e = problem.evaluate(neighbor) - problem.evaluate(current)
if delta_e > 0 or random.uniform(0, 1) < math.exp(delta_e / temperature):
current = neighbor
return current
-
temperature: 温度スケジュール。初期では高温、後半で低温。 -
delta_e: 状態の改善量。正の値なら移動。負の場合も確率で移動。
焼きなまし法の効果
焼きなまし法は、局所最適解から抜け出すために時折「悪い選択」を許容するため、大域最適解を見つける可能性を高めます。
4. 応用例：巡回セールスマン問題
巡回セールスマン問題（TSP）は、複数の都市を最短距離で巡回するルートを見つける問題です。
TSPの定式化
- 目標: 総移動距離を最小化。
- 隣接状態: ルート内の2辺を選び、それらを交換。
焼きなまし法を適用すると、ルートをランダムに変更しながら最良のルートを探索できます。例として、次のような改善が可能です：
- ルートの2辺を選んで接続を変更。
- 新ルートが改善されれば採用。悪化しても確率で採用。
5. まとめ
局所探索アルゴリズムは、最適解を効率的に近似する強力な手法です：
- ヒルクライミング: 単純かつ高速だが局所最適解に陥る可能性あり。
- ランダムリスタート: 複数回試行することで局所最適解からの脱出を図る。
- 焼きなまし法: ランダム性を活用し、大域最適解を目指す。
これらの手法を問題に応じて適切に選択することで、効果的な解を得ることが可能です。