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

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.

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