XII. Travelling Salesman Problem

About the Problem

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.

Implementation

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:

Crossover

One point - part of the first parent (i.e. part of the cities order) is copied and the rest of cities 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 these two parts 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 that the "normal random" mutation is performed
Systematic improving - the same as "systematic, only improving", but before that the "normal random" mutation is performed
None - no mutation

Example

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 graph.
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.

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

(c) Marek Obitko, 1998