The Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is a popular ‘toy problem’ in the AI community since it is at once simple to understand and very difficult (NP-hard) to solve. A salesman needs to complete a tour of a certain number of cities using the most efficient path possible. The salesman can travel from any city to any other city, but must visit each city once and only once. It doesn’t sound like a difficult problem until you consider the sheer number of possible solutions, even for a small fifteen city problem. Marco Dorigo and his associates Gianni Di Caro and Luca Gambardella[6] realised that ants’ inherent ability to discover shortest paths could be put to use on the TSP and, it turned out, with some success.

The first TSP solution they developed was called Ant System and works like this: ants first make a number of random tours starting from a random city, depositing pheromone as they go. At each city an ant picks its next destination using a combination of probability and the amount of pheromone present on that route to inform its decision. Every ant must visit every city once, as per the criteria of the TSP. After a tour is completed, an ant deposits a certain amount of pheromone on each edge of the graph, depending on how far the ant travelled during its tour – shorter tours lead to more pheromone being deposited. A certain amount of pheromone will also decay, causing older solutions to fade away and be replaced by new ones.

After this process has run for some time, the pheromone present on the edges of the graph will tend to influence any ant traversing the graph towards an optimal solution. Ant System and subsequent versions of the algorithm such as Ant Colony Optimisation do not always find optimal solutions, but are effective in finding good solutions in a reasonable number of iterations.

An interesting thing to note about the design of these algorithms is that although they are inspired by the behaviour of ants, they implement features unused by mother nature. For example, while pheromone decay is present in natural ant pheromones, it is generally much faster in ant algorithms since it aids the dynamic nature of the algorithms in finding new solutions. Real ants however would not benefit if all their trails disappeared overnight! But some aspects of the algorithms are very rigorously reproduced from nature. The variables controlling trail-laying in some algorithms have derived from studies, such as Deneubourg’s Argentine ant research which yielded very precise probabilities controlling the ants’ chances of choosing trails based on pheromone strength.