Chapter 3

解を磨く — 局所探索

配達ルートを作った。だが地図を眺めると、何かおかしい。
中央で経路がクロスしている。
どう見ても、ここをほどけば短くなりそうだ。

じゃあほどこう。これが **局所探索 (Local Search)**だ。

前章で作った貪欲解は「終盤詰み」だった。これを少しずつ磨いて良くする。これが組合せ最適化の本当に強力な道具、局所探索。

この章で身につけてほしいのは、次の4 つの設計問題を意識的に考える癖だ:

📦 解の表現: 解をどんなデータで持つか
🔄 近傍: その解の「ちょっと違うバージョン」とは何か
🎯 評価: 良くなったかどうかをどう測るか
🚦 選び方: 良いものが見つかったらどうするか

このどれかをサボると、どんなに高級なメタヒューリスティクスを乗せても刺さらない。

3.1 2-opt — TSP の魔法の入れ替え

具体例から始めよう。前章の 5 軒経路。あれを良くする。

TSP の局所探索でいちばん有名なのが 2-opt。
やることは超シンプル: 「経路の 2 本の辺を選んで、入れ替える」。

図 3.1 — 2-opt: 「交差している2辺」を取り除き、間の区間を反転して張り直す。経路の総距離が必ず短くなる。

左のクロスがほどけて、右ではスッキリしている。
これだけ。たった「2 辺を選んで張り替える」。

3.2 「良くなったか」を 1 行で計算する

ここで大事な裏ワザがある。
2-opt をしたあと、新しい経路の総距離を最初から計算する必要はない。

変わるのは、外した 2 辺と、足した 2 辺だけ。
だから差分はたった 4 つの足し算で計算できる:

Δ = d(b, c) + d(x, d) − d(b, x) − d(c, d)

Δ が負なら「改善した」。即採用。
n=1000 の経路でも、評価が O(n) から O(1) に落ちる。

これが 差分計算 (delta evaluation)。
平凡な実装と最強の実装を分ける最大の要素はここ。
タブー長を調整するより、近傍を 10 種類試すより、これを徹底するほうが速い。

3.3 山登り法 — ひたすら良くなる方向に進む

2-opt を「改善が見つかる限り繰り返す」アルゴリズムが、最も素朴な局所探索 —— 山登り法 (Hill Climbing)。

def hill_climb(tour):
    while True:
        for (i, j) in all_2opt_pairs(tour):
            delta = compute_delta(tour, i, j)
            if delta < 0:
                tour = apply_2opt(tour, i, j)
                break          # 改善あり → やり直し
        else:
            return tour        # 全ペア試して改善なし = 局所最適

最初に見つかった改善でやり直すスタイル (first improvement) と、近傍全体を見て一番良い改善を採るスタイル (best improvement) がある。経験的には first のほうが速いことが多い。

3.4 そして山登りは壁にぶつかる

山登りは必ず止まる。
止まるのは ——「近傍を見ても改善がない」場所。
これを 局所最適 (local optimum) と呼ぶ。

だが、局所最適は全体の最適とは限らない。

図 3.2 — 山登りの宿命: 最初の谷に落ちたら抜け出せない。「下る方向がない」とそこが終点。

これが組合せ最適化の永遠の難題、局所最適のトラップ。
ここから先、本書のほとんどの章は「どうやってこの谷から逃げるか」の話だ。
本書のあらゆるメタヒューリスティクスは、結局この一つの問いへの答えなのだ。

3.5 近傍をどう設計するか

2-opt は「2 辺の入れ替え」。
じゃあ別の近傍はないの? もちろんある。

近傍	動き	大きさ
swap	2 つの位置を入れ替える	O(n²)
2-opt	2 本の辺を張り替える (= 1 区間を反転)	O(n²)
or-opt	長さ k (1〜3) の区間を別の位置に挿入	O(n²)
3-opt	3 本の辺を張り替える	O(n³)
Lin-Kernighan	「改善が続く限り辺を連鎖的に交換」	動的

近傍が大きいほど「より遠くに行ける」けど、1 反復が重くなる。
このトレードオフこそ近傍設計の核心。

そして本書を通じて何度も登場する Lin-Kernighan (LK)。 1973 年の論文だが、今でも TSP の世界記録は LK の改良版 (LKH-3) が独占している。「改善が続く限り辺を交換し続ける可変長近傍」というアイデアで、固定の 2-opt や 3-opt を遥かに超える。

3.6 スケジューリングの近傍

TSP の話ばかりだと飽きるので、スケジューリングに戻ろう。
JSP の解は「機械ごとのジョブ順序」だ。じゃあ近傍は?

何でも入れ替えればいいわけじゃない。 クリティカルパス上のジョブ順序だけが makespan に効く。それ以外を動かしても f は変わらない (プラトーになる)。

図 3.3 — JSP の近傍は「クリティカルパス上の隣接ジョブの入れ替え」に絞る。他はプラトー。

こうしてクリティカルパスだけを攻めると、無駄な探索が消えて何倍も速くなる。これが Nowicki–Smutnicki (1996) の有名な近傍で、JSP の局所探索の標準になった。

3.7 近傍を設計するときの 4 つの問い

新しい問題に出会ったとき、近傍設計のためにあなたが聞くべき問い:

連結性: 「ある解からどの解にも辿り着けるか?」 (近傍を辺と見たグラフが連結か)
サイズと差分: 「近傍サイズと、差分計算のコストはバランスしてるか?」
制約違反の扱い: 「近傍内が制約違反になる場合、ペナルティ化 / 修復 / 弾く?」
表現との相性: 「解の表現を変えると、もっと自然な近傍ができないか?」

3.8 プラトーとどう付き合うか

組合せ最適化の景観は、滑らかな谷より広いペッタンコの平地 (プラトー) がはびこっている。特に JSP の makespan を最小化するときは、ほとんどの動きが f を変えない。

プラトーは局所最適より厄介だ。「どっちに進んでいいかすらわからない」。対処は 3 つ:

横移動を許す: 同じ f の解にも動く。ループ防止のため履歴は持つ。
第二目的: 同じ f なら、より「自由度の高い解」を選ぶ。
ランダム再開: 諦めて別の初期解からやり直す。

3.9 ここで一旦立ち止まる

ここまでで、局所探索の全要素を見た。

近傍を定義する → 2-opt、swap、クリティカルパス
差分計算で爆速にする
山登りで磨く
局所最適 / プラトーにぶつかる

そして残った大問題は: 「局所最適から逃げ出すにはどうするか」。

この問いへの答えは、大きく 3 系統。

🎲 確率で悪化を許す → Simulated Annealing
📝 過去を覚えて同じ局所最適を避ける → Tabu Search
💥 大きく壊して再出発 → ILS / VNS / GRASP / ALNS

次の章で、この 3 系統を順番に触っていく。それぞれ、登山技術の流派みたいなものだ。

3.10 この章の振り返り

局所探索は「解 → 近傍 → 改善方向に移動」のシンプルな反復。
2-opt やクリティカルパス近傍は基本道具。差分計算が命。
山登りは局所最適で停止。これがメタヒューリスティクスを呼ぶ動機。
近傍の設計は「連結性」「サイズ」「制約」「表現」の 4 軸で考える。
プラトーは局所最適より厄介。横移動・第二目的・再開で凌ぐ。