Travelling Salesman Problem
The Travelling Salesman Problem is a problem that seeks to find the shortest way of getting through a network, starting from any point, visiting every other point, in the shortest time. It is commonly modelled as a network of arcs and nodes.
It is a common example of an algorithm that has to be solved heuristically; while it is possible to solve it with brute force, by trying every single route and finding the shortest, this is impractical, since the number of routes increases factorially; while a 3-node network has only 6 routes, a 10-node one has 3,628,800.
Example letting simulated evolution find a good solution
The salesman should visit a number of towns, one at a time, and wants to know in what order they should be visited in order to make the tour as short as possible.
Suppose that the number of towns is = 60. For a random search process, this is like having a deck of cards numbered 1, 2, 3, ... 59, 60 where the number of permutations is of the same order of magnitude as the total number of atoms in the universe. If the hometown is not counted the number of possible tours becomes 60*59*58*...*4*3 (about 10 raised to 80, 10^80, 1. e. a 1 followed by 80 zeros).
Suppose that the salesman does not have a map showing the location of the towns, but only a deck of numbered cards, which he may permute, put in a card reader - like in the childhood of computers - and let the computer calculate the length of the tour. The probability to find the shortest tour by random permutation is about one in 10^80 so, it will never happen. So, should he give up?
No, by no means, evolution may be of great help to him; at least if it could be simulated on his computer. The natural evolution uses an inversion operator, which - in principle - is tailored for finding good solutions to the problem. A part of the card deck - chosen at random - is taken out, turned in opposite direction and put back in the deck again like in the figure below with 6 towns. The hometown (nr 1) is not counted.
If this inversion takes place where the tour happens to have a loop, then the loop is opened and the salesman is guaranteed a shorter tour. The probability that this will happen is greater than 1/(60*60) for any loop if we have 60 towns, so, in a population with one million card decks it might happen 1000000/3600 = 277 times that a loop will disappear.
This has been simulated with a population of 180 card decks, from which 60 decks are selected in every generation (using MATLAB, the language of technical computing). The figure below shows a random tour at start
After about 1500 generations a tour with no loops has been found and the length of the random tour at start has been reduced to 1/5 of the original tour. The human eye can see that some improvements can be made, but probably the random search has found a tour, which is not much longer than the shortest possible. See figure below.
In a special case when all towns are equidistantly placed along a circle, the optimal solution is found when all loops have been removed. This means that this simple random search is able to find one optimal tour out of as many as 10^80. This random process is also similar to evolution in the sense that it uses random variation and selection in cyclic repetition. This also means that the cyclic repetition of random variation and selection of individuals is a very important principle for creating a huge amount of information. See Goldberg, 1989.
- Goldberg, D. E. Genetic Algorithms in Search Optimization & Machine Learning. Addison-Wesley, New York, 1989.