Ant colony algorithm
The ant colony algorithm 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 lay down pheromone trails as they search for food. Each ant wanders randomly, but is more likely to travel a path that has pheromone on it. Thus, when one ant finds a good (short) path from the colony to a food source, other ants are more likely to follow that path; 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 algorithms have been used to produce good near-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
Referenced By
List of computability and complexity topics | List of graph theory topics | List of mathematical topics | List of mathematical topics (A-C) | List of mathematics topics
|
