Ant colony optimization
The ant colony optimization algorithm (ACO), developed by Marco Dorigo [CMD91,Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. They are inspired by the behaviour of ants in finding paths from the colony to food.
|
|
|
In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep travelling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food (see Ant communication and behavior).
Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate. Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.
Thus, when one ant finds a good (short, in other words) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leaves all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with "simulated ants" walking around the graph representing the problem to solve.
Ant colony optimization algorithms have been used to produce near-optimal solutions to the travelling salesman problem. They have an advantage over simulated annealing and genetic algorithm approaches when the graph may change dynamically; the ant colony algorithm can be run continuously and adapt to changes in real time. This is of interest in network routing and urban transportation systems.
Publications (selected)
[CDM91] Distributed Optimization by Ant Colonies A. Colorni, M. Dorigo et V. Maniezzo, In Proceedings of the first european conference on artificial life, Paris, France, Elsevier Publishing, 134-142, 1991.
(it) [Dor92] Optimization, Learning and Natural Algorithms M. Dorigo, In !PhD thesis, Politecnico di Milano, Italy, 1992.
[BDT99] Swarm Intelligence: From Natural to Artificial Systems Éric Bonabeau, Marco Dorigo et Guy Theraulaz, In Oxford University Press, 1999, ISBN 0195131592.
(fr) [DPT+03] Métaheuristiques pour l'optimisation difficile Johann Dréo, Alain Petrowski, Éric Taillard, Patrick Siarry, In Éd. Eyrolles, Paris, septembre 2003, Broché, 356 pages, ISBN 2-212-11368-4 extrait concernant les algorithmes de colonies de fourmis.
[DoSt04] Ant Colony Optimization M. Dorigo, T. Stützle, In MIT Press, 2004, ISBN 0262042193.