Travelling Salesman Problem I - Encoding and Operators

The next topic we will discuss in the lesson is the well-known traveling salesman problem. Given a set of cities and distances between them, the goal is to find a path that begins and ends in the same city, visiting each city exactly once and is as short as possible. In other words, we are looking for the shortest Hamiltonian cycle in a complete graph. Of course, we will once again focus on how to solve such a problem with evolutionary algorithms.

Coding the individuals

The solution of the traveling salesman problem is actually a permutation of cities (which indicates the order in which we visit them). So we have to figure out how to encode individuals that express permutations.

One option is to use the real coding. Individuals therefore contain real numbers. These numbers are sorted and the permutation is determined by their positions prior to sorting. For example, if we have the individual [5.4, 1.2, 2.3, 1.7] the resulting permutation is [1, 3, 2, 0], because the smallest number is at position 1, the second smallest in position 3 etc. (indexing from 0). The advantage of this coding is that we can use simple operators and every individual that we create is valid (i.e. it can be decoded to a permutation). The downside, however, is that some useful operations are complex (e.g. moving a city right after another city in the path).

Traditional evolutionary algorithms encode individuals directly as permutations. Thus, the individual is a vector of natural numbers and operators must ensure that each number appears exactly once.

Operators for permutation encoding

Creating a mutation that preserves the permutation is simple. For example, we can swap numbers between positions, or take part of the individual and move it elsewhere. Another option is to take a part of an individual and reverse the order of values in that part.

The crossover is a little more complicated. As an example, we show the Order Crossover (OX). It works similarly to the 2-point crossover, but then the child must be repaired. First, a part of one parent is selected and moved into the child. The values from this part are removed from the other parent. The remaining values are inserted into the child in the order in which they appear in the second parent, starting at the right end of the part selected in the first step. If we want a second child, we swap both parents and repeat the procedure.

There are more ways to perform crossover, some examples can be found here.

Source codes for this lesson

In the source code for this lesson (file tsp.py), we have a simple evolutionary algorithm for the traveling salesman problem. It uses only mutation. Fitness is calculated as 1/path length. Cities are entered as their geographic coordinates, and the distance is calculated as the crow flies (the distance function in tsp.py computes it). We have several inputs: tsp_evropa.in contains the coordinates of the capitals of European countries (including Russia and Iceland). Other inputs are randomly generated all around the Earth, tsp_std.in contains 100 “cities”, tsp_test.in has only 10 of them (useful for testing) and tsp_large.in, on the other hand, contains 1000 “cities”. Today .best files have the .kml extension and can be opened in Google Earth so that you can see the path the algorithm found.