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
ichooses the next unvisited cityjwith probabilitypij = τijα ηijβ / Σl τilα ηilβ, with visibilityηij = 1/dij. - After all ants finish:
τij ← (1 - ρ) τij + Σk Δτijk, where an ant with tour lengthLkaddsQ / Lkto every edge it used. With elitist weighte, the best-so-far tour addse Q / Lbestmore. - The start value is
τ0 = m / LnnwithLnnthe 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], costO(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...