巡回セールスマン問題

すべての都市を1回ずつ訪れて出発点に戻る道のうち、いちばん短いものを探す問題を巡回セールスマン問題と呼びます。 都市が増えると道の候補は爆発的に増え（80都市なら 10 の 116 乗を超えます）、全部を調べることはできません。 ここでは遺伝的アルゴリズムで、短い道を少しずつ育てます。「▶ 開始」を押してみてください。

しくみ

1つの道（都市を回る順番）を1匹の生き物に見立て、たくさんの道（個体）を同時に育てます。1世代ごとに次のことを繰り返します。

1. 選ぶ（トーナメント選択）: 何匹かをくじで選び、その中でいちばん短い道を親にする。トーナメントを大きくすると、短い道ばかりが親になる
2. 混ぜる（順序交叉）: 片方の親の道の一部をそのまま受け継ぎ、残りの都市を、もう片方の親が回る順番で埋める
3. ゆらす（2-opt の突然変異）: 決まった確率で、道の一部分を逆向きにする。交差している2本の道をほどく働きがある
4. 残す（エリート保存）: その世代でいちばん短い道を、そのまま次の世代に残す。外すと、最短の記録が一時的に悪くなることがある

「円」の配置では、最短の道（円周に沿って回る道）の長さが計算で分かるので、どこまで近づけるかを確かめられます。 同じシードなら、同じ都市の配置・同じ進化をたどります。