Ant colony optimisation

Ants find the best path

No ant knows the way. Each one just follows its nose. Press Play and watch the whole colony find the shortest path together!

How long is the colony's favourite path?
Favourite path Average ant trip Best possible

Checkpoints — the smell map saved along the way. Tap one to look back.

Smell maps get saved here as the colony learns.

How it works

Wander

Ants leave the nest and pick a path at every crossing, a bit at random. They like short paths and smelly paths.

Find food

An ant that finds food remembers the way it came, and forgets any loops it walked.

Leave a smell

On the way home it drops smell on every path. A short trip means more smell.

Follow and fade

Other ants follow strong smells. Old smells fade, so the colony keeps only the paths that are still good.

What just happened?

For grown-ups: what's really going on

This is Ant Colony Optimisation (Dorigo, 1992), a swarm-intelligence method for shortest-path problems.

  • Choice rule: at a node an ant picks edge e with probability ∝ τ(e)^α · (1/len(e))^β, with α = β = 1.5. Pheromone τ is the shared memory; 1/len is a local "visibility" heuristic. With probability ε (Curiosity) it picks uniformly.
  • Memory: each ant keeps its route as a node list and cuts out loops when it revisits a node.
  • Deposit: on the way back, each edge gets Δτ ∝ (L*/L)², where L is the trip length and L* the current optimum, so shorter trips leave much more smell.
  • Evaporation: every tick τ ← (1−ρ)·τ, the "how fast smells fade" slider.
  • Max–Min Ant System: τ is clamped to [0.3, 8]. Without the cap, an old trail gets so strong that a newly opened shortcut can never compete (premature convergence). The cap keeps the colony adaptable.
  • Elitism: the shortest recent trip gets a small extra deposit, forgotten if the world changes.
  • The green "best possible" line is computed with Dijkstra's algorithm for comparison; the ants never see it. In Node tests the favourite path reached exactly the optimum within about 1,000–1,500 ticks, and re-found it after every challenge.