## Ant Colony Optimizationedited by Christian Blum, IRIDIA ## Contents## About Ant Colony OptimizationAnt Colony Optimization (ACO) is a metaheuristic approach proposed by Dorigo et al. in [Dorigo 1992], [Dorigo et al. 1996], and [Dorigo et al. 1999]. The inspiring source of ACO is the foraging behavior of real ants. This behavior enables ants to find shortest paths between food sources and their nest. While walking from food sources to the nest and vice versa, ants deposit a substance calledpheromone on
the ground. When they decide about a direction to go, they choose with higher
probability paths that are marked by stronger pheromone concentrations. This
basic behavior is the basis for a cooperative interaction which leads to the
emergence of shortest paths.
ACO algorithms are based on a parametrized probabilistic model -- the The framework of the ACO metaheuristic is shown below. It consists of three parts gathered in the
online step-by-step pheromone update. Once an ant has built a solution, it can (by using its memory) retrace the same path backward and update the pheromone trails of the used components and/or connections according to the quality of the solution it has built. This is called online delayed pheromone update. Another important concept in Ant Colony Optimization is pheromone evaporation. Pheromone evaporation is the process by means of which the pheromone trail intensity on the components decreases over time. From a practical point of view, pheromone evaporation is needed to avoid a too rapid convergence of the algorithm toward a sub-optimal region. It implements a useful form of forgetting, favoring the exploration of new areas in the search space.
## Readings-
M. Dorigo, 1992. Optimization, Learning and Natural Algorithms *(in Italian)*, Ph.D. thesis, DEI, Politecnico di Milano, Italy. pp. 140. -
M. Dorigo and G. Di Caro, 1999. The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo, and F. Glover editors, New Ideas in Optimization}, pages 11-32. McGraw-Hill. -
M. Dorigo, G. Di Caro and L. M. Gambardella, 1999. Ant algorithms for discrete optimization. Artificial Life, 5, 2, pages 137-172. -
M. Dorigo and L. M. Gambardella, 1997. Ant colony system: A cooperative learning approach to the travelling salesman problem. IEEE Transactions on Evolutionary Computation, 1, 1, pages 53-66. -
M. Dorigo, V. Maniezzo and A. Colorni, 1996. Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics - Part B, 26, 1, pages 29-41. -
M. Dorigo and T. Stützle, 2002. The ant colony optimization metaheuristic: Algorithms, applications and advances. In F. Glover and G. Kochenberger editors, Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science, pages 251-285. Kluwer Academic Publishers, Norwell, MA. -
M. Dorigo and T. Stützle, 2004. Ant Colony Optimization. MIT Press, Boston, MA. -
T. Stützle and H. H. Hoos, 2000. MAX-MIN Ant System. Future Generation Computer Systems, 16, 8, pages 889-914.
## Links- The Ant Colony Optimization website
| ||

Network Coordinator: Marco Dorigo e-mail: mdorigo@ulb.ac.be Web site responsibles: Christian Blum and Max Manfrin |