XII. 巡回セールスマン問題
問題について
巡回セールスマン問題（ＴＳＰ）については前の章ですでに紹介しました。 それを繰り返すと、都市と都市間の距離が与えられます。 巡回セールスマンはすべての都市を回る必要があります。 しかし彼は旅がすきではありません。 仕事は、旅行する距離を最少にする順番を見つけることです。 言い換えると、N ノードを持つ完全グラフ上の最小ハミルトン巡回路を見つけることです。
実行
１６の染色体で構成される個体群を使います。 これらの染色体のコード化には順列コーディング が使われています。この方法はこの章で見ることができます。 またどのようにＴＳＰに対して都市が順番にコード化したのかもわかります。 ＴＳＰは完全グラフ（つまりどのノードもお互いに繋がっている）のユーグリッド距離で解くことができます。都市を加えたり、削ったりした後で、新しい染色体を作り、もう１度遺伝的アルゴリズム全体をやりなおす必要があります。
交叉と突然変異のタイプを選ぶ必要があります。 それが何を意味してるのかを説明します。
交叉
- 1点交叉 - １つめの親から部分がコピーされ、２番目の親から順番通りに残りがコピーされます。
- 2点交叉 - ２つの部分が１つめの親からコピーされ、残りの間の部分が２つめの親から同じ順番でコピーされます。
- なし - 交叉は行われず、子孫は両親の完全なコピーです
突然変異
- 通常ランダム - 少数の都市が選ばれて交換されます。
- ランダム改善のみ - 少数の都市が選ばれ、それらを交換することで解が改善する場合（適合度が増加する場合）のみ都市を交換します。
- 系統的改善のみ - 系統的に都市が選ばれ、それらを交換することで解が改善する場合（適合度が増加する場合）のみ都市を交換します。
- ランダム改善 - 「ランダム改善のみ」と同じですが、その前に「通常ランダム」の突然変異が行われます。
- 系統的改善 - 「系統的改善のみ」と同じですが、その前に「通常ランダム」の突然変異が行われます。
- なし - 突然変異は行われません。
例
以下のデモンストレーションは TSP に対する GA を示します。「Change View」ボタンで個体群全体の表示と最良解の表示を切り替えられます。グラフ上をクリックして都市を追加・削除できます。都市を追加または削除すると、新しい染色体を持つ新しい個体群が作られるため、ランダムな巡回路が表示されます。ここでは完全グラフ上の TSP を解いています。交叉や突然変異の設定を変えて、GA の性能や速度がどう変わるか観察してみてください。