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.
|
