About | Front page | Previous | Next |

An introduction to Ant Colony Algorithms

Ant Colony Algorithms are inspired by the behaviour of natural ant colonies, in the sense that they solve their problems by multi agent cooperation using indirect communication through modifications in the environment. Natural, or real, ants release a certain amount of pheromone while walking, and each ant prefers(probabilistically) to follow a direction which is rich of pheromone. This simple behaviour explains why ants are able to adjust to changes in the environment, such as new obstacles interrupting the currently shortest path. Let me illustrate: What happens when an ant colony following a shortest path between a food source and the nest (see below) gets interrupted

by an obstacle appearing somewhere in the path? When the ants reach the obstacle they will randomly choose some way around it(right, left, over or under). If we assume that the only way around the obstacle is either right or left, we can safely assume that approximately half of the ants will go right and the other half left, as illustrated below.

The ants that happen to pick the shorter path will obviously create a strong trail of pheromone a lot faster than the ones choosing a longer path(see below). This will cause more and more ants to choose the shorter path until eventually all ants have found the shortest path.

Ant Colony Algorithms attempt somehow to apply similar techniques in order to solve real life problems. The main idea is to use repeated and often recurrent simulations of artificial ants (mobile agents inspired by real ant behaviour) to generate new solutions to the problem at hand. The ants use information collected during past simulations to direct their search and this information is available and modified through the environment. Many different artificial ant algorithms have been implemented and no universal definition of an artificial ant fits them all. In the next section we will take a look at an example where an artificial ant colony solves the travelling salesman problem.

About | Front page | Previous | Next |

Comments : Johann Bragi Fjalldal
Last modified: Mon Feb 15 09:43:17 GMT 1999