XII. Travelling Salesman Problem


About the Problem

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.



Implementation

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.

Crossover

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.



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 - Terms of use