局所最適から逃げる 5 つの流派
山登り法で「もう動けない」場所に来てしまった。
谷の底だが、地図を見ると遠くにもっと深い谷がある気がする。
さあ、どう逃げる?
この問いに、研究者たちは半世紀かけて 5 つの流派を編み出した。
それぞれ性格がまるで違って、登場人物として読めるくらい個性がある。
5 つの流派、性格でひとことに:
- 🌡 焼きなまし: 「酔っ払いほど自由」。確率的に悪い方にも進む
- 📝 タブー: 「メモ魔」。最近行ったところは禁止
- 💢 反復局所探索: 「ちゃぶ台返し」。固まったら部屋ごとシャッフル
- 🔭 可変近傍: 「望遠鏡」。視界を広げて再挑戦
- 🎲 GRASP: 「毎日違うスタート」。多数決で勝つ
順番に会いに行こう。
4.1 焼きなまし法 — 酔っ払いほど自由
鍛冶屋を想像してほしい。
金属を高温に熱したあと、ゆっくり冷ますと、内部の歪みが取れて美しい結晶構造になる。
これが「焼きなまし」。
1983 年、物理学者 Kirkpatrick はこれを最適化に持ち込んだ。
アイデア
山登り法は「改善する移動」しか許さない。
焼きなまし法 (Simulated Annealing, SA) は、悪化する移動も確率で許す。
ただし、温度 T が高いときほど許しやすい。
悪化量 Δ (Δ > 0) の移動を受け入れる確率:
P(受入) = exp(−Δ / T)
最初は T が高くて「酔っ払い」みたいに自由に動く。 徐々に T を下げると、しだいにシラフに戻り、最後は完全な山登りになる。
これで「序盤に景観全体を把握 → 終盤に細部を磨く」が両立する。
def simulated_annealing(x, T0, T_min, alpha):
best = x
T = T0
while T > T_min:
x_new = random_neighbor(x)
delta = f(x_new) - f(x)
if delta < 0 or random() < exp(-delta / T):
x = x_new
if f(x) < f(best): best = x
T *= alpha # 幾何冷却
return bestSA の使いどころ
- 実装が 20 行で済む。新規問題の最初のメタヒューリスティクスとして優秀。
- パラメータは 3 つだけ (T₀, T_min, α)。直感的に調整可能。
- 近傍と差分計算さえあれば、どんな問題にも適用できる。
落とし穴T₀ の決め方を雰囲気でやると、ほぼ確実にハマる。
「初期解からランダム移動 100 回」して平均 Δ を測り、 受入確率 50〜80% になるよう T₀ を逆算する、を必ずやる。
4.2 タブー探索 — メモ魔の決定論
迷子になったとき、地面に小石を置いていけば「同じ場所に戻ってない」のがわかる。
Glover (1989) は「最近やった操作を、しばらく禁止する」というアイデアを提案した。
アイデア
山登り法で局所最適に達したら、近傍で最も悪化の小さい解に移る。
それでは元に戻ってしまうので、「直近 t 回でやった操作の逆」を禁止する。
これで「悪化 → 逆戻り → ループ」を防げる。
def tabu_search(x, tabu_length, max_iter):
best = x
tabu = deque(maxlen=tabu_length)
for _ in range(max_iter):
candidates = [n for n in neighbors(x) if move(x, n) not in tabu]
x_new = min(candidates, key=f) # 悪化してもベスト候補を採用
tabu.append(move(x, x_new))
x = x_new
if f(x) < f(best): best = x
return best「アスピレーション基準」という妙技
「禁止だけど、もしそれを採用したら過去最高記録を更新するなら、特別に許可」。
これがアスピレーション基準 (aspiration criterion)。ルールに例外を持たせるエレガントな設計だ。
SA は確率で悪化を許す。
タブー探索は決定論で悪化を許す。
正反対のアプローチで同じ問題 (局所最適トラップ) を解いている。
4.3 反復局所探索 (ILS) — ちゃぶ台返し
プラモを組み立てていて、どうしても完成しない。
あるとき思い切って、半分壊して組み直す。
すると突然、すっと組める。
これが ILS (Iterated Local Search)。
- 局所探索で谷の底に達する
- 解をがっと壊す (摂動)
- そこからまた局所探索
- 改善したら採用、ダメなら捨てる
- 1 に戻る
ILS の核心は 「摂動の強さ」。
弱すぎる → 同じ局所最適に戻る (意味なし)
強すぎる → ランダム再開と一緒 (せっかくの構造を捨てる)
ちょうどよく、**「現解の半分くらいは残す」**のがコツ。
TSP では「ダブルブリッジ」(4 本の辺を切って繋ぎ直す) が経験的に最強の摂動として知られている。 2-opt や 3-opt の局所最適から確実に逃げ出せる。
4.4 可変近傍探索 (VNS) — 望遠鏡を取り換える
近視の人がスーパーで欲しい商品を探すとき、まず近い棚を見て、なければ少し離れて見て、それでもなければ店内全体を見渡す。
これが VNS。
VNS (Variable Neighborhood Search) は複数の近傍 N₁, N₂, N₃ を用意し、 段階的に大きくして使う。
ILS の摂動がランダムにかき乱すのに対し、VNS は近傍そのものを取り替える。
似ているけど思想が違う。
4.5 GRASP — 毎日違うスタートで多数決
試験勉強で「最後の山かけ」をするとき、同じ範囲だけ繰り返し勉強しても点は上がらない。 違うアプローチを並列に試す方がいい。
GRASP (Greedy Randomized Adaptive Search Procedure) の発想はこう:
1. ランダム化貪欲で初期解を作る (毎回違う解) 2. 局所探索で磨く 3. これを 100 回繰り返して、最良を採用
キモは「ランダム化貪欲」。
普通の貪欲は最良の候補だけ取るが、GRASP は上位 α% からランダムに取る。
だから毎回違う解が出る。
他の手法と違って、各反復が完全に独立なので並列化が爆速。 クラウドで 100 コア並べたら 100 倍速。
4.6 5 つの流派、横に並べる
| 流派 | 悪化の許容 | 記憶 | 近傍 | 性格 |
|---|---|---|---|---|
| 山登り (比較用) | なし | なし | 固定 | 真面目で諦め早い |
| 🌡 SA | 確率で許す | なし | 固定 | 序盤は酔っ払い、終盤はシラフ |
| 📝 Tabu | 決定論的に許す | 短期+長期 | 固定 | メモ魔、合理派 |
| 💢 ILS | 採用基準による | 最良解 | 局所 + 摂動 | 固まるとちゃぶ台返し |
| 🔭 VNS | 採用基準による | 最良 + 近傍 idx | 複数切替 | 視野を広げては戻る |
| 🎲 GRASP | (反復内では) なし | 最良解 | 局所探索 | 多数決で勝つ |
4.7 で、どれを最初に試すべき?
新しい問題に向き合うとき、私 (筆者) なら次の順序で試す。
- まず CP-SAT で問題を書いてみる (第6章)。サイズが小さければそれで終わる。
- 解けないと分かったら、貪欲 + SA の粗い実装で基準線を作る (半日)。
- SA が頭打ちになったら、ALNS (第5章) に移行する。
- 本気を出すなら、CP-SAT × ALNS のハイブリッド。
忠告「Whale Optimization」「Firefly Algorithm」「Salp Swarm」などの動物名アルゴリズム論文に出会っても、 すぐに飛びつかないこと。多くは PSO や SA の表面的な変種で、 ベンチマークも著者陣の身内同士の比較。
本物のチャンピオンは古典 (SA, Tabu, ILS, ALNS, LK) の改良の中にいる。
4.8 ここで一旦立ち止まる
5 つの流派は全部「解を 1 つ持って動かす」アプローチだ。
だが、別の発想もある。
「解をたくさん持って、一斉に動かす」 → 集団型 (GA など)
「解を大胆に壊して作り直す」 → LNS / ALNS
次の章でこの 2 系統に行く。特に ALNS は現代の主役、ぜひ味わってほしい。
4.9 この章の振り返り
- 局所最適から逃げる工夫が、本書の主役メタヒューリスティクス。
- 5 つの流派: SA (確率)、Tabu (記憶)、ILS (摂動)、VNS (近傍切替)、GRASP (多重スタート)。
- どれも「探索 vs 活用」のバランスを取るための工夫として理解できる。
- 銀の弾丸はない。問題に合うものを選び、調整する。