Presets
Playback
Camera
Layers
Quality
Model check
The science
Ants as a search algorithm
Real ants find short routes because each ant lays pheromone while it walks and later ants prefer stronger trails; shorter routes are completed more often per unit time, so they gain more pheromone, while unused trails evaporate. Ant colony optimisation (Dorigo, 1992) turns this into an algorithm for the travelling-salesman problem: visit N cities once each and return, with the shortest total length L. The number of different tours is (N − 1)! / 2 (about 1.8×1015 for 18 cities), so exhaustive search is hopeless and a heuristic is needed.
The rules (Ant System)
An ant standing in city i chooses the next unvisited city j with probability pij = τijα ηijβ / Σk τikα ηikβ, where τ is the pheromone, η = 1/dij the visibility and α, β their weights. After all m ants have built a tour, the trails are updated: τij ← (1 − ρ) τij + Σk Δτijk with Δτkij = Q / Lk (here Q = 1) on every edge of ant k's tour. The evaporation rate ρ keeps the colony from freezing on early, poor tours: without deposits a trail decays exactly as τ0(1 − ρ)t.
Variants
Elitist adds e Q / Lbest on the best-so-far tour every iteration. Max-Min Ant System lets only one ant deposit (the iteration best, every fifth iteration the best so far) and clamps all trails to [τmin, τmax with τmax = 1/(ρ Lbest), which prevents stagnation.
What the graphs show
The branching factor counts, for each city, the edges whose trail exceeds τmin + 0.05(τmax − τmin); it falls towards 2 (one tour: each city keeps its two neighbours) as the colony converges. The reference length is the exact optimum from the Held-Karp dynamic programme for 13 cities or fewer (2N N2 operations), otherwise the best of the 2-opt-polished nearest-neighbour tours, which is a good but not proven bound. For random uniform tours the expected length is exactly N times the mean pairwise distance, a baseline the ants must beat.
Honest simplifications
The ants of one iteration walk simultaneously and the trails are updated when they return (the animation shows the tours that update was computed from). Real ants do not know the whole map, deposit continuously and cannot compute a tour length; the model keeps only the part that explains the optimisation: positive feedback, evaporation and a greedy bias. For 40 cities the result is a heuristic, not a proof of optimality.