XII. 巡回セールスマン問題

問題について

巡回セールスマン問題（ＴＳＰ）については前の章ですでに紹介しました。それを繰り返すと、都市と都市間の距離が与えられます。巡回セールスマンはすべての都市を回る必要があります。しかし彼は旅がすきではありません。仕事は、旅行する距離を最少にする順番を見つけることです。言い換えると、Nノードを持つ勧善グラフノ最少ハミルトニアンを見つけることです。

Travelling salesman problem (TSP) has been already mentioned in one of the previous chapters. To repeat it, there are cities and given distances between them.Travelling salesman has to visit all of them, but he does not to travel very much. Task is to find a sequence of cities to minimize travelled distance. In other words, find a minimal Hamiltonian tour in a complete graph of N nodes.

実行

１６の染色体で構成される個体群を使います。これらの染色体のコード化には順列コーディングが使われています。この方法はこの章で見ることができます。またどのようにＴＳＰに対して都市が順番にコード化したのかもわかります。ＴＳＰは完全グラフ（つまりどのノードもお互いに繋がっている）のユーグリッド距離で解くことができます。都市を加えたり、削ったりした後で、新しい染色体を作り、もう１度遺伝的アルゴリズム全体をやりなおす必要があります。

Population of 16 chromosomes is used. For encoding these chromosome permutation encoding is used - in chapter about encoding you can find, how to encode permutation of cities for TSP. TSP is solved on complete graph (i.e. each node is connected to each other) with euclidian distances. Note that after adding and deleting city it is necessary to create new chromosomes and restart whole genetic algorithm.

交叉と突然変異のタイプを選ぶ必要があります。それが何を意味してるのかを説明します。

You can select crossover and mutation type. I will describe what they mean.

交叉

One point - １つめの親から部分がコピーされ、２番目の親から順番通りに残りがコピーされます。
Two point - ２つの部分が１つめの親からコピーされ、残り間の部分が２つめの親から同じ順番でコピーされます。
None - 交叉がありません、子孫は両親の完全なコピーです

突然変異

Normal random - 少数の都市が選ばれて交換されます。
Random, only improving - 少数の都市が選ばれて、もしそれらを交換することで問題が改善する場合（適合度が増加したら）のみ都市を交換します。
Systematic, only improving - システマチックにとしが選ばれて、もしそれらを交換することで問題が改善する場合（適合度が増加したら）のみ都市を交換します。
Random improving - "random, only improving"と同じですが,これの前に "normal random" 突然変異が行われます。
Systematic improving - "systematic, only improving"と同じですが,これの前に "normal random" 突然変異が行われます。
None - 突然変異は行われません。

Crossover

One point - part of the first parent is copied and the rest is taken in the same order as in the second parent
Two point - two parts of the first parent are copied and the rest between is taken in the same order as in the second parent
None - no crossover, offspring is exact copy of parents

Mutation

Normal random - a few cities are chosen and exchanged
Random, only improving - a few cities are randomly chosen and exchanged only if they improve solution (increase fitness)
Systematic, only improving - cities are systematically chosen and exchanged only if they improve solution (increase fitness)
Random improving - the same as "random, only improving", but before this is "normal random" mutation performed
Systematic improving - the same as "systematic, only improving", but before this is "normal random" mutation performed
None - no mutation

Example

Following applet shows GA on TSP. Button "Change View" changes view from whole population to best solution and vice versa. You can add and remove cities by clicking on the graph. After adding or deleting random tour will appear because of creating new population with new chromosomes. Also note that we are solving TSP on complete graph.
Try to run GA with different crossover and mutation and note how the performance (and speed - add more cities to see it) of GA changes.

Known bug: Please press button "Change View" before doing anything else otherwise some graphs will not respond in some browsers. I am using CardLayout and I don't know how to make it work right. If you think you know, please mail me.

Here is applet, but your browser does not support Java. If you want to see applets, please check browser requirements.