The Ant Colony Optimization (ACO) meta-heuristic is a class of model-based search algorithms inspired by the behaviour of real ant colonies, in particular their food foraging behaviour. In real life ants deposit pheromone on the path they have taken, for example to a food source. This can lead other ants to this food source as ants have a higher probability of choosing paths which have stronger pheromone concentrations. ACO algorithms model this biological property of real ants. A number of agents, or ants, are allowed to incrementally construct solutions, depositing different amounts of pheromone based on the quality of the solution constructed. This models the behaviour of real ant colonies, where the behaviour of ants is directed to the survival of the colony rather than to the benefit of an individual ant. The colony is able to exploit the pheromone trails created by individual ants in order to get to a food source. Analogously, ant agents in ACO algorithms use pheromone trails created by other ants in order to get to, or construct, a solution. Similar behaviour can be seen in other social insects, for example wasps, and this area of Artificial Intelligence is known as Swarm Intelligence.
However, it is important to note that although ACO was inspired by the behaviour of real ants, there are a number of important differences between the two. There are some important differences between real and artificial ants. For example, real ants live in a continuous world, while the artificial ants can only move from one discrete state to another. Similarly, artificial ant agents have an internal state for remembering their past actions, a facility not present with real ants. More importantly, there are differences in how pheromone is deposited and how it evaporated. The amount of pheromone deposited by artificial ants is determined by a function of the quality of the solution that is found. This is obviously different from the behaviour of real ants. Differences are more noticeable in how pheromone is deposited and evaporated. Artificial ants often update levels of pheromone only when a solution is constructed, while this is not the case with real ants. On the other hand, the rate at which pheromone evaporates is increased beyond what is biologically possible to allow the ants to move away from local minima. Finally, ACO algorithms can be further improved by additional techniques such as local search, lookahead techniques and backtracking, which of course cannot be done by real ants.
One problem with real life ant colonies is that the ants might get stuck on a longer path to a food source if that path is discovered earlier, and therefore contains a heavier pheromone trail. In some sense this is equivalent to getting stuck in local minima. To combat this, the convergence properties of ACO algorithms have been improved by artificially increasing the rate at which the pheromone deposited evaporates, allowing ants to discover new, better solutions.
A number of different ACO algorithms have been proposed, and a particular algorithm known as Ant Colony System (ACS) has been used for experiments performed in this project.