Ant colony optimization
|
|
The ant colony optimization algorithm (ACO), introduced by Marco Dorigo in his doctoral thesis, is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. They are inspired by the behavior of ants in finding paths from the colony to food.
Overview
In the real world, ants (initially) wander randomly, and when having found food, returning to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to travel on at random but to follow the trail, and return and reinforce it if they eventually find food. (Details on this behaviour.) 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 traveling 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.
External links
- Ant Colony Optimization Home Page (http://www.aco-metaheuristic.org/)
- An Introduction to Ant Colony Algorithms (http://www.cogs.susx.ac.uk/lab/nlp/gazdar/teach/atc/1999/web/johannf/index.html)fr:Algorithme de colonies de fourmis