XII. Travelling Salesman Problem

About the Problem

The travelling salesman problem (TSP) has already been mentioned in one of the previous chapters. To repeat: there are cities and given distances between them. The travelling salesman has to visit all of them, while traveling as little as possible. The task is to find a sequence of cities that minimizes the total distance traveled. In other words, we want to find a minimal Hamiltonian tour in a complete graph of N nodes.

Implementation

A population of 16 chromosomes is used. These chromosomes use permutation encoding - in the chapter about encoding you can find how to encode a permutation of cities for TSP. The TSP is solved on a complete graph (that is, each node is connected to every other node) with Euclidean distances. Note that after adding or deleting a city, it is necessary to create new chromosomes and restart the whole genetic algorithm.

You can select the crossover and mutation types. Their meanings are described below.

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 section between them is taken in the same order as in the second parent
  • None - no crossover; the offspring is an exact copy of the 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 the solution (increase fitness)
  • Systematic, only improving - cities are systematically chosen and exchanged only if they improve the solution (increase fitness)
  • Random improving - the same as "random, only improving", but a "normal random" mutation is performed first
  • Systematic improving - the same as "systematic, only improving", but a "normal random" mutation is performed first
  • None - no mutation

Example

The following demonstration shows a GA solving the TSP. The "Change View" button switches between the whole population and the best solution. You can add and remove cities by clicking on the graph. After adding or deleting a city, a random tour will appear because a new population with new chromosomes must be created. Also note that we are solving the TSP on a complete graph.
Try running the GA with different crossover and mutation settings, and observe how its performance (and speed - add more cities to see the difference) changes.