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.

One round in three boxes in a loop: 1, every ant builds a tour with p proportional to tau to the alpha times eta to the beta; 2, evaporation, tau becomes (1 minus rho) times tau on every edge; 3, deposit, every ant adds Q over L to the edges of its tour. An arrow goes from box 3 back to box 1: the next round uses the new tau.
One round: all ants build tours with the current pheromone, then the trails evaporate and the ants deposit Q/L.

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 tour length so far against round 1 to 20 for rho 0.1, 0.5 and 0.9. All start at 298.7. rho 0.5 reaches the optimum 251.2 in round 4 and rho 0.1 in round 5. rho 0.9 stays on 272.9, then 261.9 from round 6, and never reaches the optimum.
Fast evaporation (ρ = 0.9) locks onto a 261.9 tour; ρ = 0.1 and 0.5 find the 251.2 optimum.
ρbest after 20 roundspheromone on the best tourdifferent tours in round 20what happens
0.9261.9100%1trails of the last round dominate; all ants walk the same longer tour (Demo 4)
0.5251.2, the optimum84%3explores, then concentrates (Demo 3)
0.1251.2, the optimum71%4old 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

MethodWhat it keeps between stepsHow a new solution is made
Nearest neighbour + 2-optone tourswap two edges while the tour gets shorter
Simulated annealingone solutionrandom neighbour; a worse one is sometimes accepted
Genetic algorithma population of solutionsselection, crossover and mutation
Particle swarmpositions, velocities, best pointseach particle flies towards its best and the swarm's best
Ant colonypheromone on every edgeeach 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.

On the mind map

This page on the AI: Search, Games & Reasoning mind map · 23 pages in 7 branches · open it to see the whole map and test yourself in recall mode.