遺伝的アルゴリズム

巡回セールスマン問題の経路を、選択・交叉・突然変異で世代ごとに改良していく様子を見せます。交叉や選択の方法、突然変異の確率を変えて、結果の違いを比べられます。

太い線が最良の経路、薄い線は同じ世代のほかの個体（上位 12 個）です。図をクリックすると都市を足せます（60 個まで。始め直しになります）。

都市

正方形の中にばらまいた 30 都市。

設定

変えると第 0 世代から始め直します。

個体の数

選択

ランダムに 3 個体を選び、いちばん短いものを親にする。強さを数で調整しやすい。

交叉

親 A の区間をそのまま写し、残りを親 B に出てくる順に埋める。都市の並び順を受け継ぐ。

突然変異

区間を逆順にする。変わる辺は 2 本だけ（2-opt と同じ動き）。

突然変異の確率（1 個体あたり）

エリート（上位をそのまま残す数）

交叉の例（順序交叉（OX））

1 世代進めると、その世代で行った交叉の例（親どうしの違いが最も大きい組）をここに表示します。

第 1000 世代まで進むと自動で記録します。設定を変えて、同じ都市での結果を比べてみてください。

都市の配置を選んで「再生」を押すと、世代が進むたびに最良の経路が描き直されます。第 1000 世代で止まり、結果を「試行の記録」に残します。
「1 世代」で 1 世代ずつ進められます。キーボードでは Space で再生 / 一時停止、→ で 1 世代進みます。
図をクリックすると都市を足せます。「都市を消して手で置く」で空にしてから、好きな配置を作れます（4〜60 都市）。
個体の数・選択・交叉・突然変異・エリートを変えて、同じ都市での結果を記録の表で比べられます。点線の「最近傍法 + 2-opt」は、遺伝的アルゴリズムを使わない手軽な解き方の長さです。

すべての都市を 1 回ずつ訪れて出発点に戻る、いちばん短い経路を探す問題です。都市が n 個なら経路は (n − 1)! / 2 通りあり、30 都市でも約 4 × 10³⁰ 通りになるので、すべてを調べることはできません。

生物の進化をまねて、たくさんの候補（個体）を少しずつ良くしていく方法です。このアプリでは、個体は都市を訪れる順番（順列）で、経路が短いほど良い個体です。

第 0 世代: ランダムな順番の個体を集めます。
選択: 短い個体ほど選ばれやすいように、親を 2 つ選びます。
交叉: 2 つの親の順番を組み合わせて子を作ります（確率 90%。しないときは親をそのまま写す）。順列のどこかを切って入れ替えるだけでは同じ都市が 2 回出てくるので、順序交叉・部分写像交叉・循環交叉のような、順列のまま組み合わせる方法を使います。
突然変異: 決めた確率で子の順番を少し変えます。新しい並びを生み、集団が同じ経路ばかりになるのを防ぎます。
エリート: 世代の上位の個体を、そのまま次の世代に残します。最良の経路が悪くならなくなります。

選ぶ力が強すぎたり突然変異が少なすぎたりすると、早いうちに集団が同じ経路ばかりになり（早期収束）、それ以上良くならなくなります。逆に突然変異が多すぎると、良い並びが壊れやすくなります。「異なる経路の数」を見ながら、つり合いを探してみてください。