3D ant colony optimisation

Ants walk between mushrooms at different heights and learn the shortest closed route with pheromone.

Switch to 2D

Presets

Playback

Colony parameters

Run

Camera

Layers

Quality

Model check

The science

What is modelled

The travelling salesman problem in three dimensions: find the shortest closed route that visits every mushroom cap once. Mushroom caps stand at random heights in a terrarium, so the distances are true 3D distances. A colony of artificial ants builds routes using pheromone memory and the length of each link, then reinforces the routes it finds short (Ant System, Dorigo 1992).

Equations

  • An ant at city i chooses the next unvisited city j with probability pij = τijα ηijβ / Σl τilα ηilβ, with visibility ηij = 1/dij.
  • After all ants finish: τij ← (1 - ρ) τij + Σk Δτijk, where an ant with tour length Lk adds Q / Lk to every edge it used. With elitist weight e, the best-so-far tour adds e Q / Lbest more.
  • The start value is τ0 = m / Lnn with Lnn the nearest-neighbour tour length.
  • Reference length: for up to 12 cities the exact optimum from the Held-Karp dynamic programme, f(S, j) = mink in S\{j} [f(S\{j}, k) + dkj], cost O(n2 2n). For more cities the reference is nearest neighbour followed by 2-opt, which is a good but not proven-optimal tour.

Checks run in the page

  • On a fixed 8-city instance the dynamic programme equals a brute-force search over all 5040 tours, and a private ant colony never finds a tour shorter than that optimum.
  • 20,000 sampled choices reproduce the transition probabilities of the formula.
  • One pheromone update changes the total pheromone by exactly -ρ times the old total plus the deposits.
  • Every tour is a Hamiltonian cycle with the stated length.

Honest simplifications

  • Ants move along straight twigs between caps; there is no real 3D obstacle avoidance. The "ants" are a metaphor for a probabilistic search, not a model of real ant behaviour (real colonies use pheromone to find short paths, but they do not solve tours).
  • Ant System has no guarantee of finding the optimum; it is a heuristic. The result depends on the random seed, and the parameters (alpha, beta, rho, Q) are common textbook choices, not tuned values.
  • All ants of an iteration are built from the same pheromone matrix and then walk in parallel; the animation shows one edge per beat.

What to try

  • Set beta to 0: the ants ignore distances and the search is slow. Set alpha to 0: there is no memory and the colony never improves.
  • Try evaporation 0.9 (the colony forgets) and 0.02 (it locks in early).
  • Switch on Turbo and watch the trail thickness collapse onto one tour, then press "New random instance".
Loading model...
Loading Blender model...
Tour length vs iteration
Pheromone vs edge length
Choice probabilities of the lead ant
Made with 🟠 Blender · Three.js