The idea: ants that leave trails
Real ants find short paths to food without a map. Each ant leaves a chemical, pheromone, on the ground, and ants prefer paths that smell stronger. Ants on a short path come back sooner and lay pheromone more often, so the short path gets stronger, which draws even more ants to it. Ant colony optimization (ACO), proposed by Marco Dorigo in 1992, copies this for problems on graphs. The page uses the first version, the Ant System, on the Travelling Salesman Problem: find the shortest closed tour through all cities.
The map has 8 cities A–H on a 100 × 100 grid. The shortest tour, found by trying all 2520 tours, is 251.2 long. 4 ants start on A, C, E and G. Every one of the 28 edges starts with τ = 1. The line width and darkness of an edge on the map show its pheromone.
How an ant chooses the next city
An ant at city i looks at every city j it has not visited yet. It gives each one a weight from two things: the pheromone τ(i, j) on the edge, which is what earlier ants learned, and the visibility η(i, j) = 1/d(i, j), which says that near cities look attractive. The chance of going to j is
p(j) = τ(i,j)^α · η(i,j)^β / Σ over unvisited k of τ(i,k)^α · η(i,k)^β
α and β set how much each part counts; the page uses the usual α = 1, β = 2. The ant then spins a roulette wheel: the slices p(j) are laid end to end from 0 to 1, a random number r is drawn, and the slice that r falls in wins. A likely city usually wins, but not always: that is how ants try new tours.
(Demo 1: ant 1 builds a tour, choice by choice) At the start every τ is 1, so only distance counts. From A, H is nearest (19.1), and with β = 2 it gets the largest share, p = 0.380; B (24.6) gets 0.229. But the first random number is r = 0.012, which falls in B's slice 0 … 0.229, so ant 1 goes to B. From B, D is the favourite (p = 0.410), and r = 0.062 picks C (p = 0.063). Ant 1 is unlucky: its tour A B C H F E G D A is 346.1 long. It draws 6 random numbers for 7 choices: the last city is a forced move.
Evaporation and deposit
When all 4 ants are home, the pheromone is updated in two parts. First every trail evaporates:
τ(i,j) ← (1 − ρ) · τ(i,j) on all 28 edges, used or not
Then every ant k deposits Q / Lk on each edge of its tour, where Lk is its tour length and Q = 100:
τ(i,j) ← τ(i,j) + Σ over ants k whose tour uses i–j of Q / L_k
A short tour adds more per edge, and an edge on several tours gets several deposits. (Demo 2: one round: 4 tours, evaporate, deposit: the tours are 346.1, 393.2, 298.7 and 358.9 long, so the ants deposit 0.289, 0.254, 0.335 and 0.279 per edge. With ρ = 0.5 every τ drops from 1 to 0.5. Edge E–G is on the tours of ants 1, 3 and 4 and ends at 0.5 + 0.902 = 1.402. Edges no ant used stay at 0.5.)
The short tour emerges
Next round, the ants see more pheromone on the edges of the good tours, so they pick those edges more often, and deposit on them again. This positive feedback is the whole method. Evaporation is the brake: edges that stop being used fade, so the colony can forget early mistakes. (Demo 3: 20 rounds, ρ = 0.5: the short tour emerges: an ant finds the optimal tour, 251.2, in round 4. After round 20, 84% of all pheromone lies on its 8 edges, and the map shows one thick loop. The ants still walk 3 different tours: some still explore.)
The evaporation rate ρ
ρ decides how long the colony remembers. The same 20 rounds, the same random numbers, three values of ρ:
| ρ | best after 20 rounds | pheromone on the best tour | different tours in round 20 | what happens |
|---|---|---|---|---|
| 0.9 | 261.9 | 100% | 1 | trails of the last round dominate; all ants walk the same longer tour (Demo 4) |
| 0.5 | 251.2, the optimum | 84% | 3 | explores, then concentrates (Demo 3) |
| 0.1 | 251.2, the optimum | 71% | 4 | old tours still count; the ants keep exploring (Demo 5) |
With ρ = 0.9 an edge keeps only 10% of its pheromone each round, so the newest deposits are almost all there is. Whatever the ants walked last round becomes much more likely next round. Soon all 4 ants walk the same tour, deposit on the same 8 edges, and nothing else has any pheromone left. This is called stagnation: the search has stopped, on a tour 4.3% above the optimum. With ρ = 0.1 the trails change slowly; the ants still find the optimum by chance, but the colony has not yet settled on it.
Pheromone and distance both matter
Set α = 0 and τ^0 = 1: the ants ignore the pheromone and choose by distance alone, a random nearest-neighbour rule. Rounds do not help each other. (Demo 6: α = 0: distance only, nothing learned: one ant stumbles on 251.2 in round 15, but round 20's best tour is 288.9 again, and the pheromone is spread out.) Set β = 0 and the ants ignore distance: at first every edge is equally likely, so the tours are random and long, and the pheromone only reinforces those. (Demo 7: β = 0: pheromone only: the best tour after 20 rounds is 296.5, 18% above the optimum.)
ACO next to the other search methods
| Method | What it keeps between steps | How a new solution is made |
|---|---|---|
| Nearest neighbour + 2-opt | one tour | swap two edges while the tour gets shorter |
| Simulated annealing | one solution | random neighbour; a worse one is sometimes accepted |
| Genetic algorithm | a population of solutions | selection, crossover and mutation |
| Particle swarm | positions, velocities, best points | each particle flies towards its best and the swarm's best |
| Ant colony | pheromone on every edge | each ant builds a tour from scratch, guided by τ and η |
ACO is a constructive method: no ant changes an old tour; the memory lives in the pheromone on the graph, not in the solutions. That makes it natural for problems built step by step on a graph: routing, scheduling, vehicle routes. The exact optimum on this small map can also be found with Held–Karp dynamic programming.
What the page leaves out
The better ACO variants: the elitist Ant System (the best tour gets extra pheromone), Max–Min Ant System (τ kept between τmin and τmax against stagnation, only the best ant deposits) and Ant Colony System (local pheromone update and a greedy choice with probability q0). Real solvers also add a local search such as 2-opt to every ant's tour, use candidate lists of the nearest cities, and run one ant per city (m = n) for hundreds of rounds. ACO is also used for vehicle routing, scheduling and network routing (AntNet), which the page does not show.