Main Page | See live article | Alphabetical index

Ant colony algorithm

The ant colony algorithm is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphss. 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