Ant Colony Optimization
Virtual ants traverse a graph of cities, depositing pheromone on the edges they walk. Good routes accumulate more pheromone; bad routes evaporate. Over many iterations, the colony converges on short tours — a nature-inspired heuristic for the NP-hard Traveling Salesman Problem, discovered by Marco Dorigo in 1992.
How it works
Each iteration, every ant constructs a complete tour by visiting each city exactly once. The probability of choosing the next city depends on two factors: pheromone intensity on the edge (raised to power α) and inverse distance (raised to power β). After all ants complete their tours, pheromone on every edge evaporates by a factor ρ, and each ant deposits pheromone on the edges it traversed, inversely proportional to its tour length.
The parameters
α (pheromone influence) controls how strongly ants follow existing trails. High α leads to rapid convergence but risks premature stagnation. β (distance influence) biases ants toward nearby cities. ρ (evaporation rate) controls memory decay — high evaporation forgets quickly, allowing exploration; low evaporation reinforces established paths.
Convergence
The algorithm exploits positive feedback: good routes attract more ants, which deposit more pheromone, which attracts still more ants. Evaporation provides the negative feedback needed to prevent total lock-in. The balance between exploitation and exploration is the central tension of all swarm intelligence methods.