Catalogue of Artificial Intelligence Techniques
Ant Colony Optimisation
Keywords: computational intelligence, feedback, metaheuristic, pheromone, swarm, trail
Author(s): Grigoris Sotiropoulos
A class of metaheuristic algorithms used in solving combinatorial optimisation problems. Ant Colony Optimisation (ACO) algorithms are part of the research field of Swarm Intelligence and are inspired by the behaviour of real ants, which are capable of finding shortest paths from a food source to the ant colony. The first ants initially choose a path at random. All ants, however, also leave a trail of chemicals, called pheromones, along the path they take, and subsequent ants tend to follow the path with the highest pheromone concentration. Pheromones evaporate over time, so the shorter the path, the higher the pheromones concentration along it; a short path is travelled faster, so there is less time for an older pheromone trail to evaporate before the new one is laid. Since more ants will follow a higher-concentration path, this creates a positive feedback loop, eventually making the ants move along a single path.
ACO algorithms simulate this kind of behaviour and have been used successfully to obtain solutions to hard problems, including Travelling Salesman, Vehicle Routing and Quadratic Assignment problems, which reduce to path-finding problems in a graph. Their advantage over other Computational Intelligence approaches, like genetic algorithms, is that they can adapt to any changes in the graph in real time.
- Marco Dorigo and Krzysztof Soch, An Introduction to Ant Colony Optimization, IRIDIA, Av F. D. Roosevelt 50, CP 194/6, 1050 Bruxelles, Belgium, 2005, pp.27 (ISSN 1781-3794).
- Vittorio Maniezzo, Luca Maria Gambardella, Fabio de Luigi, Ant Colony Optimization, Springer-Verlag, Berlin Heidelberg, 2004, pp.21.