焼きなましと遺伝的アルゴリズム — 厳密に解けない時の実務

最適解を保証しない探索法が、なぜ現場の配送計画やスケジューリングを支えているのか。局所探索の3点セットから、焼きなましの温度、遺伝的アルゴリズムの集団、そして「これを使ってはいけない場面」の見分け方までを積み上げます。

比喩: 霧の山で、いちばん高い場所を探す

濃い霧の山にいると想像してください。見えるのは足元だけ。分かるのは「一歩踏み出したら上りか下りか」だけです。目的は、いちばん高い場所に立つこと。

いちばん素直な戦略は「上りの方向へ進み続け、どちらへ動いても下りになったら止まる」でしょう。これを山登り法と呼びます。一歩ごとに確実に高くなり、実装は数行で済みます。ところが霧の山にはたいてい小さな丘がいくつもあり、この戦略はそのうちの一つの頂上で止まります。本当の頂上が隣の谷の向こうにあっても、そこへ行くには一度下らなければならない。上りしか許さない戦略は原理的にたどり着けません。

メタヒューリスティクスとは、この「一度下る」を計画的に許すための道具立てです。焼きなまし（Simulated Annealing）は下る動きを確率で許し、遺伝的アルゴリズム（Genetic Algorithm）は登山者を大勢ばらまいて成績の良い者同士を掛け合わせます。どちらも最適解を保証しません。保証がないのになぜ使うのか、そこから始めます。

なぜ「厳密に解く」が破綻するのか

配送車が30か所を回る順番を決めたいとします。候補は30個の並べ替え、つまり $30!$ 通りで、これは約 $2.6 \times 10^{32}$。1秒に1兆通りを試せる計算機があっても、8兆年ほどかかります。

やっかいなのは、この爆発が「箱の数」に対して起きることです。20か所なら手に負えそうに見えても、30か所で天文学的になる。指数・階乗のオーダーが多項式とどれだけ違うかは、感覚では掴めません。数字を動かして確かめるのが確実です。

ただし短絡してはいけません。「規模が大きい＝厳密解法は無理」は誤りです。巡回セールスマン問題では、分枝限定法と切除平面法を組み合わせた厳密解法が数万都市規模で最適性を証明した例があります。境目は「解の候補数」ではなく、問題の構造をソルバが使えるかどうかです。この線引きは後半で判断表の形に戻ってきます。

局所探索 — すべての土台

焼きなましも遺伝的アルゴリズムも、土台は局所探索です。局所探索は3つを決めれば動きます。

1. 解の表現: 配送順なら「都市番号の並べ替え」、シフト表なら「人×コマの割当行列」
2. 近傍: いまの解から1手で行ける解の集合
3. 目的関数: 解の良し悪しを1つの数値にする関数（最小化として書きます）

このうち設計の勝負どころは近傍です。配送順なら、経路から2本の辺を選んで間の区間をまるごと逆向きにする「2-opt」。シフト表なら「1人の担当コマを別のコマへ移す」「2人の担当を入れ替える」。ナップサックなら「入れた品物1個を、入れていない1個と交換する」。

山登り法は、この近傍から良くなる手を選び続けるだけです。

def hill_climb(x, energy, neighbors):
    while True:
        best = min(neighbors(x), key=energy)   # 近傍でいちばん良い解
        if energy(best) >= energy(x):
            return x                            # どこへ動いても悪化 = 局所最適
        x = best

ここで止まった点を局所最適解と呼びます。大事なのは、局所最適が近傍の定義に依存する相対的な概念だという点です。同じ解でも、近傍を「1手の交換」と定めれば局所最適、「2手の同時交換」まで広げればそうでなくなる。近傍を広げるほど罠は減りますが、1手が重くなり、同じ時間で試せる手数が減ります。

焼きなまし: 悪い方へも動く許可

金属を高温に熱してゆっくり冷やすと、原子が低エネルギーの規則正しい配置に落ち着きます。急冷すると歪みが残ったまま固まる。この物理の手続き（焼きなまし）を最適化に持ち込んだのが Kirkpatrick らの1983年の仕事で、当初の応用先は計算機の回路配置でした。

手順は山登り法にひとつ足すだけです。現在の解 $x$ の近傍から候補 $x'$ をランダムに引き、目的関数の差 $\Delta = f(x') - f(x)$ を見る。$\Delta \le 0$（良くなる）なら必ず受け入れる。$\Delta > 0$（悪くなる）でも、確率つきで受け入れる。その確率がこれです。

記号は2つです。$\Delta$ は「どれだけ悪くなるか」の幅、$T$ は温度と呼ぶ正の数。式(1)が言っているのは、悪化の幅が小さいほど受け入れやすく、温度が高いほど受け入れやすいということだけ。少しの悪化なら目をつぶるが、大幅な悪化は温度が高いときしか許さない、という話です。