About Ant Colony Optimization

Ant Colony Optimization (ACO) studies artificial systems that take inspiration from the behavior of real ant colonies and which are used to solve discrete optimization problems. In 1999, the Ant Colony Optimization metaheuristic was defined by Dorigo, Di Caro and Gambardella.

The first ACO system was introduced by Marco Dorigo in his Ph.D. thesis (1992), and was called Ant System (AS). AS is the result of a research on computational intelligence approaches to combinatorial optimization that Dorigo conducted at Politecnico di Milano in collaboration with Alberto Colorni and Vittorio Maniezzo. AS was initially applied to the travelling salesman problem, and to the quadratic assignment problem.

Since 1995 Dorigo, Gambardella and Stützle have been working on various extended versions of the AS paradigm. Dorigo and Gambardella have proposed Ant Colony System (ACS), while Stützle and Hoos have proposed MAX-MIN Ant System (MMAS). They both have been applied to the symmetric and asymmetric travelling salesman problem, with excellent results. Dorigo, Gambardella and Stützle have also proposed new hybrid versions of ant colony optimization with local search.

For a nice introduction to the field see the March 2000 issue of Scientific American or the paper titled "Inspiration for Optimization from Social Insect Behavior" appeared on July 6, 2000, in Nature.

The book "Ant Colony Optimization" (Dorigo and Stützle, 2004) gives a full overview of the many successful applications of Ant Colony Optimization.

Last modified: January 14, 2010
Web site responsible: Marco A. Montes de Oca