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


巡回セールスマン問題(TSP)については前の章ですでに紹介しました。 それを繰り返すと、都市と都市間の距離が与えられます。 巡回セールスマンはすべての都市を回る必要があります。 しかし彼は旅がすきではありません。 仕事は、旅行する距離を最少にする順番を見つけることです。 言い換えると、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.


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

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.






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.

prev             next

(c) Marek Obitko, 1998
Japanese translation (c) Ishii Manabu, 1999
- Terms of use