Ant Colony Pheromone Trails

Stigmergy

Ants do not talk to each other or hold a map. They change the environment (a chemical trail) and the changed environment steers the next ant. This indirect coordination is called stigmergy. Here the nest (gold label) and the food stations must be visited in one round trip: the travelling-salesman problem on a graph, where every pair of stations is an edge.

Ant System (Dorigo, 1991)

An ant standing at station i picks the next unvisited station j with probability

After every ant has finished, the pheromone is updated: evaporation, then deposits proportional to tour quality.

The elitist variant adds e·Q / L_best on the best tour found so far. Short tours deposit more per edge, so good edges are reinforced; evaporation erases poor early choices.

What the numbers mean

• alpha weighs the trail, beta weighs closeness. alpha = 0 is a pure greedy walker; large alpha with small beta locks onto early luck.
• rho is memory loss per iteration. rho = 0 never forgets; rho near 1 forgets everything.
• Choice entropy is the average normalised Shannon entropy of the move probabilities: 1 means every move equally likely, 0 means every ant walks the same way (convergence or stagnation).
• Exact optimum comes from the Held-Karp dynamic programme, O(n² 2ⁿ), exact for up to 16 nodes.

Honest simplifications

Real foraging ants deposit pheromone while walking, on both legs of the trip, and the trail evaporates continuously; classic Ant System deposits once per finished tour. Real ants are about 5 mm; here they are drawn at a stylised size so you can see them. The terrain is decoration only; distances are straight-line in the plane.

• Run the Balanced preset and watch the gold best tour appear on the thickest trails while the "choice entropy" graph falls.
• Switch to Never forget (rho = 0) and compare: trails never fade, and the gap to the optimum often stays larger.
• Set alpha high and beta low: the colony freezes onto an early tour, and the entropy drops to zero with a poor best length.
• Press +300 to jump ahead, then tick Exact optimal tour to compare the colony's route with the true optimum.
• Try New random layout, Clusters or Ring: ring instances are easy, clustered ones need more iterations.