ACO: How Ants Solve Hard Problems

Stigmergy: coordination without a commander

In 1959 entomologist Pierre-Paul Grassé coined the term stigmergy — coordination that happens entirely through the shared environment rather than direct signalling. Real ants never issue instructions to one another. Each ant deposits a pheromone trail as it walks, and every ant that follows reacts only to the accumulated trail left by the whole colony. Put an obstacle between the nest and a food source with a short detour and a long one, and ants initially spread evenly across both. The ants that took the short path return sooner and lay pheromone sooner, so the short path accumulates scent faster — a positive feedback loop that, within minutes, funnels nearly all traffic onto the optimal route with no ant ever seeing the whole picture.

From stigmergy to an algorithm

Ant Colony Optimisation (ACO), introduced by Marco Dorigo in 1992, turns this behaviour into a general solver for combinatorial problems, most classically the Travelling Salesman Problem: find the shortest Hamiltonian cycle through n cities. The number of possible tours is (n−1)!/2 — for just 20 cities that is already ~6×10¹⁶, so brute force is out of the question. Every edge (i, j) between two cities carries two numbers: a fixed distance d[i][j] and a mutable pheromone level τ[i][j], plus a derived visibility η[i][j] = 1/d[i][j] that favours short edges.

One iteration has three phases: every ant independently constructs a full tour, each tour's length is scored, and the pheromone map is updated from those scores. Repeat for a few hundred iterations and the pheromone map converges onto the shortest tours found.

Probabilistic edge selection and pheromone update

Standing at city i, an ant chooses its next unvisited city j with probability proportional to a mix of pheromone and visibility, weighted by exponents α and β:

p[i][j] = ( τ[i][j]^α · η[i][j]^β ) / Σ_l∈allowed ( τ[i][l]^α · η[i][l]^β )
  α — weight given to accumulated pheromone (typical: 1)
  β — weight given to raw distance (typical: 2–5)
  allowed — the set of cities not yet visited by this ant

After all ants finish, pheromone is updated in two steps — evaporation, then deposition:

τ[i][j] ← (1 − ρ) · τ[i][j]                    // evaporation, ρ ≈ 0.1
τ[i][j] ← τ[i][j] + Σ_k Δτ_k[i][j]              // deposition
  Δτ_k[i][j] = Q / L_k   if ant k used edge (i,j), else 0
  Q — constant, L_k — length of ant k's tour

Evaporation is not a minor detail — without it the first mediocre route ever found would only accumulate more pheromone forever, and the colony would never reconsider it. Ants that found shorter tours deposit proportionally more (Q/L is larger when L is smaller), so good edges get reinforced fastest.

Min-Max ACO: fixing premature convergence

Plain Ant System has a known weakness called stagnation: after a few hundred iterations essentially every ant follows the same route and exploration stops entirely. MAX-MIN Ant System (Stützle & Hoos, 2000) clamps every pheromone value inside explicit bounds τ_min ≤ τ[i][j] ≤ τ_max, and lets only the single best ant of the round deposit. This keeps every edge just plausible enough to be revisited later, delivering results 15–35% better than classic Ant System on large instances.

Where ACO is actually used

Beyond TSP demonstrations, ACO variants solve vehicle routing for freight delivery, job-shop scheduling on processor clusters, and adaptive network packet routing (the AntNet protocol). Its real edge shows up in dynamic environments — when a graph's edges appear or disappear over time, an ant colony can keep adapting in real time because the pheromone map is, in effect, a live, decaying memory of what has worked recently, rather than a one-shot answer computed for a graph that no longer exists.

Frequently asked questions

Try it live

Watch a colony lay, follow and evaporate pheromone trails in real time in Ant Colony — nothing is installed, the whole simulation runs in one browser tab.