ポイント：配達先が n か所のとき、回る順番は (n−1)!/2 通り。20か所で約6×10¹⁶通り、30か所なら宇宙の年齢の間に総当たりしても終わりません。遺伝的アルゴリズムは最良解の保証はないが、実用的に十分良い解を短時間で見つける方法で、実際の配送計画に使われています。
進化の4ステップ
| ステップ | 内容 |
|---|---|
| ① 評価 | 各ルートの総距離を計算（短いほど“適応度”が高い） |
| ② 選択 | トーナメント選択：ランダムに数本選び、いちばん短いものを親にする |
| ③ 交叉 | 順序交叉（OX）：親Aのルートの一部を切り取り、残りを親Bの順で埋める |
| ④ 突然変異 | 一定確率でルートの一部を反転（2-opt）して、新しい形を試す |
さらに「エリート保存」として、各世代の最良ルートはそのまま次世代に残します。これで最良解が悪化することはなく、世代を重ねるほど単調に改善します。
巡回セールスマン問題（TSP）
「すべての都市を1回ずつ訪れて戻る最短経路」を求めるこの問題は、計算量理論でNP困難に分類される代表的な難問です。厳密解を求める最良のアルゴリズムでも都市数が増えると急激に時間がかかるため、実務では遺伝的アルゴリズム・焼きなまし法・アントコロニー最適化などの「近似アルゴリズム」が使われます。宅配便の配送順、基板への部品実装順、望遠鏡の観測順序などが応用例です。
観察のコツ
最初の数世代で急激に短くなり、その後は「あと一歩」がなかなか縮まらない——これは最適化全般に共通する形です。突然変異率を上げると停滞から抜け出しやすい反面、良い解が壊れやすくなります。個体数を増やすと安定しますが、1世代の計算が重くなります。
引用・転載について
本ページのシミュレーション結果・数値は、出典を明記いただければブログ・ニュース記事・SNS・授業や社内資料への引用を歓迎します。事前連絡は不要です。
推奨クレジット表記：
出典：シミュラボ「遺伝的アルゴリズムで最短ルート シミュレーター」 https://shimulabo.com/sims/ga-route/よくある質問
- 最短が保証される？
- いいえ。遺伝的アルゴリズムは近似解法で、「これ以上短いルートがない」ことは証明できません。ただし20か所程度なら、経験的にほぼ最適解に到達します。
- 線が交差しているルートは最適？
- 交差があるルートは、その2本を付け替えれば必ず短くなるため最適ではありません。突然変異（2-opt）はまさにこの交差をほどく操作です。
- 現実の配送はこれで決めている？
- 基本は同じ発想ですが、実務では配達時間帯の指定・車両の積載量・交通状況なども制約に加えた「配送計画問題（VRP）」として解きます。