Ant colony optimization
From DDL Wiki
Ant colony optimization (ACO) is a probabalistic (stochastic), heuristic optimization technique inspired by the way ants make and find paths from the colony to food. The technique is used to solve discrete optimization problems that can be reduced to finding good paths through graphs.
Contents |
History
The first appearance of an ACO system was in a Ph.D. thesis in 1992 by Marco Dorigo at Politecnico di Milano. It was called Ant System (AS). Since 1995 various other extended versions of AS have been developed, including Ant Colony System (ACS) and MAX-MIN Ant System (MMAS). In 1999 Dorigo proposed the Ant Colony Optimization (ACO) metaheuristic that became the most successful and recognized algorithm based on ant behavior.
Real World Ant Behavior
When searching for food, ants will wander around randomly until they find a food source, and then return to the colony while laying down a pheromone path that can be retraced by other ants. The ants at the colony that are wandering around will pick up this trail and follow it to the food and on the return to the colony they will also reinforce the trail by laying down a pheromone path.
The pheromone path is not permanent and evaporates over time. This means that the paths that are longer will be weaker since there is more time between pheromone dropping. However, a short path will have a much stronger pheromone path since it is closer and will be replenished with pheromones continuously. Thus the shorter paths will be preferred and the ants will tend to travel to the optimum (closest) food source.
Application
When one ant finds an optimal path from the colony to a food source, other ants are more likely to follow that path and positive feedback eventually causes all the ants to follow the same path. The ACO algorithm mimics this by walking around the graph representing the problem to solve.
These algorithms have been applied to the symmetric and asymmetric traveling salesman problem with near-optimal results.
There has been an interest in using ACO for network routing and urban transportation systems since the algorithm can be run continuously giving it the ability to adapt to changes in real time. This is an advantage over the simulated annealing and genetic algorithm approaches since they do not change dynamically.
In machine learning and data mining problems, ACO variations have been used to create a model of the way worker ants "cluster" ant corpses in ant cemetary maintenance. This has been applied to a task called clustering in machine learning which involves finding groups of objects that are similar. This method has proven to have higher performance and accuracy than previous classical methods.
External Links
- Ant Colony Optimization Home Page
- ANSI C implementation of ACO, by Thomas Stützle
- Java implementation of ACO, by Andrew Carson
- A list of dissertations relevant to the ACO field
- Combinatorial Optimisation - JAVA Applet demonstrating ACO variants including Ant Systems, Rank Based Ant Systems, Max-Min Ant Systems, Ant Colony Systems
- Java Applet Showing Traveling Salesman Application of ACO, by Mark Sinclair
References
- Éric Bonabeau, Marco Dorigo et Guy Theraulaz, Inspiration for optimization from social insect behaviour, Nature, 406 39-42, July 2000.
- F. Moyson, B. Manderick, The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Proceedings of AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, California, 1988.
- A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, Proceedings of the first european conference on artificial life, Paris, France, Elsevier Publishing, 134-142, 1991.
- M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy, 1992.
- Éric Bonabeau, Marco Dorigo et Guy Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, 1999. ISBN 0-19-513159-2
- M. Dorigo, T. Stützle, Ant Colony Optimization, MIT Press, 2004. (ISBN 0-262-04219-3)
