About | Front page | Previous | Next |

An introduction to Ant Colony Algorithms

A travelling salesperson has the task of visiting clients living in a number of different cities. The travelling salesman problem is : In what order should the cities be visited so that the total distance travelled is minimized? In order to understand and fully appreciate the potential complexity of the problem you are advised to try to solve the problem yourself. Here is a travelling salesman applet where you can try to beat a simulated annealing algorithm in a TSP competition.

This section describes how an Ant Colony Algorithm was used to solve the travelling salesman problem. The solution is based on the work of Marco Dorigo and Luca Maria Gambardella, Ant colonies for travelling salesman problem, published in BioSystems 1997.

The algorithm

The artificial ant is in this case an agent which moves from city to city on a TSP graph. The agents travelling strategy is based on a probabilistic function that takes two things into account. Firstly it counts the edges it has travelled accumulating their length and secondly it senses the trail(pheromone) left behind by other ant agents. Each agent modifies the environment in two different ways :

The purpose of the local updating is mainly to avoid very strong pheromone edges to be chosen by every ant and hence to increase exploration and hopefully avoid locally optimal solutions. The global updating function gives the shortest path higher reinforcement, that is the amount of pheromone on the edges of the path is increased. There are three main ideas that this ant colony algorithm has adopted from real ant colonies:
  1. The ants have a probabilistic preference for paths with high pheromone value
  2. Shorter paths tend to have a higher rate of growth in pheromone value
  3. It uses an indirect communication system through pheromone in edges
In addition the agents were provided with a few capabilities not present in real ants, but likely to help solving the problem at hand. For example each ant is able to determine how far away cities are, and they all have a memory of which cities they have already visited.

For further details and exact definitions of probability functions see the online report (in postscript)*

Results

The algorithm was applied to both symmetric and asymmetric versions of the TSP problem and its performance was tested against several other naturally inspired global optimization methods, such as neural nets, genetic algorithms and simulated annealing. The performance was quite impressive. The ant algorithm usually found equally good or better solutions than the other methods, and in the remaining cases it was outperformed by a very narrow margin. For very large city numbers the algorithm was modified slightly. For details and further result reports I refer to the online report *.

This type of application does not make use of the adaptive properties of the Ant Colony methology. More advanced applications, such as in telecommunication network routing (see next section), depend on this behaviour.

*These direct postscript links tend to be a bit unstable. If they take too long you might want to try downloading the online report from the provider site or make an enquiry to the the person maintaining the page.

About | Front page | Previous | Next |

Comments : Johann Bragi Fjalldal
Last modified: Mon Feb 15 09:36:26 GMT 1999