Travelling salesman problem (TSP) has been already mentioned in one of the previous chapters. Just to remind, there are cities and given distances between them. Travelling salesman has to visit all of them, but he does not want to travel very much. The 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 chromosomes permutation encoding is used - you can find in the chapter about encoding, 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. The description of their meaning follows:
The following applet shows GA optimizing the TSP. Button
"Change View" changes view from whole population to the best solution and vice
versa. You can add and remove cities by clicking on the graph. After adding
or deleting cities a random tour will appear between them as new population with
new random chromosomes is created. Also note that we are solving TSP on complete
Try to run GA with different types of crossover and mutation and note how the performance (and speed - add more cities to see it) of GA changes.
Known bug: If you are using older versions of Java in Netscape, please press button "Change View" before doing anything else otherwise some graphs will not respond.