局所探索アルゴリズムと最適解へのアプローチ：ヒルクライミング、ランダムリスタート、焼きなまし法の実践

最適化問題を解く際、完全な解空間を探索するのは時間がかかりすぎる場合があります。この記事では、局所探索アルゴリズムを使って効率的に「かなり良い解」を見つける方法を紹介します。特に以下の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. まとめ

局所探索アルゴリズムは、最適解を効率的に近似する強力な手法です：

ヒルクライミング: 単純かつ高速だが局所最適解に陥る可能性あり。
ランダムリスタート: 複数回試行することで局所最適解からの脱出を図る。
焼きなまし法: ランダム性を活用し、大域最適解を目指す。

これらの手法を問題に応じて適切に選択することで、効果的な解を得ることが可能です。