Ant colony optimization: how a pheromone trail finds a short path

Stigmergy, the double bridge experiment, Dorigo’s Ant System, the role of the parameters α, β and ρ, and improved variants — on a tour through the regional capitals and on 60 cities, compared with simulated annealing.

13 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 29 of 52

1. Map of artificial intelligence: what is what and how it all fits together
2. A brief history of artificial intelligence: from Turing to language models
3. Data, model, training, inference: the basic terms on a single example
4. How to read mathematical notation: symbols, indices, sums and quantifiers
5. Sets and relations: the building blocks of definitions in AI
6. Functions and mappings: why every AI model is a function
7. Logic and proofs: the rules AI reasons by
8. Graphs and trees: the structure that both search and neural networks stand on
9. Linear algebra for machine learning: vectors, matrices and why AI mostly multiplies
10. Derivatives, the gradient and the chain rule: how a model finds out which way to learn
11. Gradient descent: how a model learns
12. What probability is: from rolling dice to the Kolmogorov axioms
13. Conditional probability and Bayes’ theorem: how to update your estimate when you learn something new
14. Random variables and the cumulative distribution function: one function that tells you everything about a distribution
15. Probability density and probability mass functions: why a continuous variable has zero probability at a point
16. Expected value, variance and covariance: where a distribution lies, how wide it is and what goes with what
17. Overview of probability distributions: Bernoulli, binomial, Poisson, uniform, normal and exponential
18. Law of large numbers and central limit theorem: why averages behave so predictably
19. Statistics and parameter estimation: maximum likelihood, MAP and confidence intervals
20. Information theory: entropy, cross-entropy and KL divergence — where loss functions come from
21. State-space search: BFS, DFS, UCS and A* with animations
22. Games and adversaries: minimax, alpha-beta pruning and Monte Carlo tree search
23. Constraint satisfaction: backtracking, constraint propagation and AC-3 on sudoku and a map of Czech regions
24. Logic and knowledge systems: forward and backward chaining, resolution and expert systems
25. Planning: STRIPS, the blocks world, heuristics from relaxation and planning in AI agents
26. Local search and simulated annealing: a travelling salesman through the Czech regional capitals
27. Genetic algorithms: population, crossover, mutation and selection on a backpack for a hike
28. Evolution strategies and genetic programming: from the one-fifth rule to Kepler’s law
29. Ant colony optimization: how a pheromone trail finds a short path
30. Particle swarm optimisation: inertia, personal experience and the swarm’s experience
31. Neuroevolution: evolving the weights and shape of neural networks, and the NEAT algorithm
32. Fuzzy sets and membership functions: how to write down “somewhat warm”
33. Fuzzy logic and probability: why “somewhat warm” does not mean “probably warm”
34. Fuzzy logic: t-norms, implications and IF–THEN rules
35. Fuzzy control: Mamdani and Sugeno from a fan to a pole on a cart
36. Fuzzy clustering: the fuzzy c-means algorithm and points between clusters
37. Neuro-fuzzy systems (ANFIS): fuzzy rules that learn from data
38. Markov chains: the transition matrix, the stationary distribution and PageRank
39. Hidden Markov models: the Viterbi algorithm and the dishonest casino
40. Bayesian networks: why the grass is wet and what it means for the sprinkler
41. The Kalman filter: how to estimate where a car is and how fast it goes from imprecise measurements
42. Types of machine learning: supervised, unsupervised, semi-supervised and more
43. Prompts, context and RAG: how to give a model the right information
44. Variational autoencoders (VAE): new images from a continuous latent space
45. Generative adversarial networks (GAN): the forger versus the detective
46. Diffusion models: how pure noise becomes an image
47. Markov decision processes: states, actions, rewards and the Bellman equations
48. Q-learning and DQN: learning the value of actions, from a table to a neural network
49. Policy gradient and PPO: learning the policy directly
50. How an AI agent works: a language model in a loop with tools
51. Programming with AI agents: the task, tests and review
52. Evaluating and securing AI systems: how to measure and how to keep watch

Full series syllabus 52 of 83 topics published

A single ant has no map, cannot count and sees barely a few centimetres ahead. Yet the colony reliably finds the shortest path from the nest to food. No ant knows it — it emerges from the way they all mark the ground together. In the early nineties Marco Dorigo of the Politecnico di Milano noticed that the same trick can be applied to the travelling salesman problem. That is how ant colony optimization was born, and with it the whole field of swarm intelligence.

It follows on from Local search and simulated annealing. We solve the same task — a tour through the regional capitals with an optimum of 1,060.4 km — so we will see how the ants fare against annealing.

1. Communicating through traces

Definition — stigmergy

Let a group of individuals (e.g. the ants of one colony) share a common environment whose state can change. Stigmergy is a way of coordinating these individuals in which all three conditions hold:

1. an individual changes the state of the environment by its activity — it leaves a trace in it (e.g. pheromone);
2. the changed state of the environment influences what the other individuals, or the individual itself, do later;
3. the individuals do not pass information to each other directly (by a signal from one individual to another), but only through the state of the environment.

Stigmergy is thus indirect communication through the environment. The term was coined by Pierre-Paul Grassé in 1959 while studying how termites build their mounds.

2. The double bridge experiment

In 1989 Goss, Deneubourg and their colleagues built two bridges for Argentine ants between the nest and food — one twice as long as the other. After a while most of the colony was using the shorter one. Why? An ant that picked the short branch reaches the food sooner, and on its way back the short branch is already marked at the food end. The short route gets marked faster and starts to win.

Definition — the branch choice model (Deneubourg et al.)

Let two branches, a short one and a long one, lead between the nest and the food. Let A ≥ 0 and B ≥ 0 be the amounts of pheromone at the start of the short and the long branch at the moment an ant arrives at the fork, and let k > 0 and h > 0 be parameters of the model. The ant chooses the short branch with probability

P(A, B) = (k + A)^h/(k + A)^h + (k + B)^h

and the long branch with probability 1 − P(A, B). The ant lays one unit of pheromone at the start of the chosen branch and another at its end when it gets there.

So the parameter k sets how strongly an ant reacts to a weak trail (the larger k, the less), and h > 1 amplifies differences between the branches; for A = B, P = 1/2.

P = (k + A)^h/(k + A)^h + (k + B)^h

P

the probability that the next ant takes the short branch — the ant does not decide for certain, only with a weight; the long branch gets the remainder 1 − P

A

pheromone on the short branch — the only thing the ant “knows” about the route; the more of it there is, the more the short branch pulls

B

pheromone on the long branch — in the denominator it competes with the short one, so what decides is the ratio of the trails, not their absolute amount

k

an “attention threshold” — added equally to both branches, so the first few molecules of pheromone barely change the ratio; without it the very first ant would decide for the whole colony

h

the amplifier — a power greater than 1 exaggerates the difference; it is what turns a small random advantage into positive feedback

Example — how k = 30 and h = 2 decide

The short branch has A = 20 units of pheromone, the long one B = 10:

P = (30 + 20)²/(30 + 20)² + (30 + 10)² = 2,500/2,500 + 1,600 = 2,500/4,100 ≈ 0.610

(Colours as in the formula above.)

• Equal trails (A = B, say both zero): P = 0.500 — pure chance.
• Five units against zero: P = (30 + 5)²/(30 + 5)² + (30 + 0)² = 35²/35² + 30² ≈ 0.576 — a small trail hardly decides anything; that is the work of k.
• A = 60, B = 10: P = 8,100/8,100 + 1,600 ≈ 0.835 — a clear lead by now.
• Without amplification (h = 1), A = 20, B = 10 would give only 50/90 ≈ 0.556 instead of 0.610.

A simulation of the model (k = 30, h = 2, ten ants per step, short branch 5 steps, long one 10) shows the share of pheromone on the short branch in eight colonies:

Seven colonies settled on the short branch, one on the long one: the first few ants happened to pick the long branch and positive feedback “locked” it in. Out of a hundred colonies, 85 ended on the short branch and 9 on the long one. When both branches are equally long, the colonies split roughly in half (46 and 42) — chance breaks the symmetry. So the length of the route shifts the outcome but does not guarantee it. We will see the same weakness in the algorithm.

3. Ant System

Dorigo’s Ant System (1992) sends virtual ants across a graph of cities. Each one builds a complete tour and, depending on how short it is, lays pheromone on its edges.

Definition — a tour and its length

Let n ∈ ℕ, n ≥ 3, be the number of cities, label the cities 1, …, n, and let for all i, j ∈ {1, …, n}, i ≠ j, a distance d_ij ∈ ℝ be given such that d_ij = d_ji > 0.

1. A tour is an ordered n-tuple π = (π₁, …, π_n) in which every city appears exactly once, i.e. {π₁, …, π_n} = {1, …, n} (π is a permutation of the cities). For brevity we set π_n+1 = π₁.
2. The length of a tour π is the number L(π) = ∑_k=1ⁿ d_πkπk+1 = d_π1π2 + d_π2π3 + … + d_πnπ1; the last term brings the traveller back home.
3. An edge (i, j) belongs to the tour π if and only if there is k ∈ {1, …, n} such that {π_k, π_k+1} = {i, j}.
4. The travelling salesman problem is the task of finding a tour π^* such that L(π^*) ≤ L(π) for every tour π.

So a tour passes through every city exactly once and returns to the starting one; an edge belongs to it if and only if its two cities follow each other directly in it.

Definition — the transition rule

Let cities 1, …, n be given with distances d_ij > 0 (see the definition of a tour above), pheromone τ_ij > 0 on every edge (i, j) and parameters α ≥ 0, β ≥ 0. The visibility of the edge (i, j) is the number

η_ij = 1/d_ij.

Let an ant stand in city i and let N_i ⊆ {1, …, n} be the non-empty set of cities it has not yet visited on its tour. The ant moves to city j with probability

p_ij = τ_ij^α · η_ij^β/∑_{l ∈ Ni} τ_il^α · η_il^β   for j ∈ N_i,   p_ij = 0   for j ∉ N_i.

So the ant chooses only among unvisited cities, with a weight proportional to the product of the trail τ_ij^α and the visibility η_ij^β (nearby cities are more attractive); the parameters α and β weigh the trail against the distance. The probabilities p_ij over j ∈ N_i sum to 1.

p_ij = τ_ij^α · η_ij^β/∑_{l ∈ Ni} τ_il^α · η_il^β

p_ij

the probability of a step from i to j — we draw at random rather than pick the best, so that the colony keeps trying other tours too

τ_ij^α

the colony’s memory — pheromone carries the experience of earlier ants; the exponent α says how much to trust it (α = 0 switches it off completely)

η_ij^β

greed — η = 1/d favours nearby cities; it is advice we get for free right from the first iteration, when the pheromone does not know anything yet

∑ … over N_i

the sum of the weights of all cities not yet visited — dividing by it turns the weights into probabilities that add up to 1; visited cities are not in it, so the ant never returns to them

Example — one decision of an ant

An ant stands in city i and has three cities left: at distances of 50, 100 and 150 km, with pheromone τ = 1, 3 and 2. The constant in the visibility cancels out in the fraction, so let us work with η = 100/d, that is 2, 1 and 2/3. With α = 1 and β = 3 (colours as in the formula above):

• weights τ^α · η^β: 1 · 2³ = 8.000, 3 · 1³ = 3.000, 2 · (2/3)³ ≈ 0.593;
• their sum is 11.593;
• probabilities p = 8.000/11.593 ≈ 0.690, 3.000/11.593 ≈ 0.259 and 0.593/11.593 ≈ 0.051.

The nearest city wins even though it has the least pheromone. With β = 1 we would get 0.316, 0.474 and 0.211 — pheromone leads. And with β = 0 only the trail decides: 0.167, 0.500 and 0.333 (ratio 1 : 3 : 2).

Definition — the pheromone update

Let ρ ∈ (0, 1) be the evaporation rate and Q > 0 a constant. Let M ≥ 1 ants have built the tours π⁽¹⁾, …, π^(M) in one iteration (tour m is π^(m)) with lengths L_m = L(π^(m)), m = 1, …, M. After the iteration the pheromone on every edge (i, j) is replaced by the value

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ tour m} Q/L_m,

where the sum runs over all m ∈ {1, …, M} for which the edge (i, j) belongs to the tour π^(m) (an empty sum is 0). So the pheromone evaporates everywhere by the fraction ρ, and each ant m adds the amount Q/L_m, inversely proportional to the tour length, to the edges of its tour.

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ tour m} Q/L_m

τ_ij on the left

the new pheromone on the edge — what the ants of the next iteration will decide by

(1 − ρ)

evaporation — every iteration takes the same fraction ρ off every trail; old experience thus fades geometrically and the colony can relearn

τ_ij on the right

the pheromone so far — the memory is only corrected, it does not start from zero

∑_m

a sum over the ants that used the edge — each ant adds only to the edges of its own tour; an edge used by more ants gets more — this is where the colony’s “votes” are counted

Q/L_m

a reward inversely proportional to the tour length — shorter tour = stronger trail; the constant Q only sets the scale

Example — one update

An edge has τ = 1, ρ = 0.3, Q = 1,000, and two ants with tours 1,100 and 1,300 km long passed along it (colours as in the formula above):

τ ← 0.7 · 1 + 1,000/1,100 + 1,000/1,300 ≈ 0.700 + 0.909 + 0.769 = 2.378

An edge that nobody used has only 0.7 after the same iteration. The ant with the shorter tour added more (0.909 against 0.769).

import random

def postav_okruh(start, n, tau, d, alfa=1, beta=3):
    okruh, volna = [start], set(range(n)) - {start}
    while volna:
        i = okruh[-1]
        kandidati = list(volna)
        vahy = [tau[i][j] ** alfa * (1 / d[i][j]) ** beta for j in kandidati]
        j = random.choices(kandidati, weights=vahy)[0]
        okruh.append(j)
        volna.remove(j)
    return okruh

def aktualizuj(tau, okruhy, delka, rho=0.3, Q=1.0):
    for radek in tau:
        for j in range(len(radek)):
            radek[j] *= 1 - rho                 # evaporation
    for okruh in okruhy:
        L = delka(okruh)
        for a, b in zip(okruh, okruh[1:] + okruh[:1]):
            tau[a][b] += Q / L                  # shorter tour, stronger trail
            tau[b][a] += Q / L

The whole Ant System then simply alternates building tours and updating, and remembers the best tour anyone has ever built:

def mravenci_system(n, d, mravencu, iteraci, tau0):
    tau = [[tau0] * n for _ in range(n)]      # the same everywhere at the start
    nejlepsi = None
    for it in range(iteraci):
        okruhy = [postav_okruh(m % n, n, tau, d) for m in range(mravencu)]
        aktualizuj(tau, okruhy, delka)        # evaporation + new trail
        kandidat = min(okruhy, key=delka)
        if nejlepsi is None or delka(kandidat) < delka(nejlepsi):
            nejlepsi = kandidat
    return nejlepsi

4. Ants on the regional capitals

Let us release 13 ants (one from each city) for 100 iterations with α = 1, β = 3 and ρ = 0.3. The map shows the pheromone on the edges after the 1st, 5th, 20th and 100th iteration — the thicker the line, the more pheromone:

In the first iteration the trail is spread almost everywhere and the best tour is 1,292.6 km long. Already in the fifth iteration one of the ants finds the optimum of 1,060.4 km. The pheromone then concentrates on the edges of good tours — weak lines vanish, strong ones stay — and the average ant builds a tour of roughly 1,250 km. The colony never converges completely; it keeps trying a little.

A trace of the run by iteration — the best tour found so far and the average tour of the thirteen ants in that iteration:

The best tour improves in jumps (the third iteration brought nothing new, the fourth cut 111 km), while the average falls more slowly and unevenly: the ants draw at random, so even in a good iteration some of them build weak tours. The gap between the average and the best is exactly the exploration that keeps the colony from freezing completely.

It does not always turn out this well. Out of twenty runs with different seeds only 7 found the optimum, the average was 1,073.9 km and the worst result 1,083.0 km. Annealing, with 98 out of 100 on the same task, was more reliable. For comparison: the greedy “nearest neighbour”, which always goes to the nearest unvisited city, gives 1,120 to 1,336 km depending on the start. The ants are markedly better, but the basic Ant System on its own is no champion — that is why its improved variants came about.

5. What α, β and ρ are for

On thirteen cities a lot can be solved even without pheromone. Only a larger task shows the difference — the same 60 random cities as in the article on annealing, 30 ants, 150 iterations, the average of three runs:

• Without pheromone (α = 0) the ants are just random greedy travellers and learn nothing — tours a third longer.
• Without distances (β = 0) the colony has nothing to push off from: the first tours are completely random and the pheromone from them leads to further random ones.
• Slow evaporation keeps the trails of the first, poor tours for too long and the colony learns slowly. Fast evaporation, on the other hand, forgets the good things too.

How long the colony remembers can be calculated exactly. It is enough to follow a single edge.

Theorem — steady-state pheromone and evaporation half-life

Let ρ ∈ (0, 1), Δ ≥ 0 and τ₀ ∈ ℝ. Let the sequence (τ_t)_{t = 0, 1, 2, …} (the pheromone of one edge after t iterations, which receives the same increment Δ in every iteration) satisfy, for every t ≥ 0,

τ_t+1 = (1 − ρ) τ_t + Δ.

Then

1. for every t ≥ 0, τ_t = Δ/ρ + (1 − ρ)^t (τ₀ − Δ/ρ),
2. lim_{t → ∞} τ_t = Δ/ρ,
3. if Δ = 0 and τ₀ > 0, then τ_t = (1 − ρ)^t τ₀, and for real t ≥ 0, (1 − ρ)^t τ₀ = τ₀/2 if and only if t = t_½, where t_½ = ln 2/−ln(1 − ρ) is the evaporation half-life (in general not an integer).

Proof. Denote by e_t = τ_t − Δ/ρ the deviation from Δ/ρ. Since (1 − ρ) · Δ/ρ + Δ = Δ/ρ, subtracting Δ/ρ from both sides of the recurrence gives e_t+1 = (1 − ρ) e_t, and by induction e_t = (1 − ρ)^t e₀; that is point 1. Since 1 − ρ ∈ (0, 1), (1 − ρ)^t → 0, and hence e_t → 0; that is point 2. For Δ = 0, τ_t = (1 − ρ)^t τ₀, so τ_t = τ₀/2 if and only if (1 − ρ)^t = 1/2, i.e. t · ln(1 − ρ) = −ln 2; since ln(1 − ρ) < 0, the only solution is t = ln 2/−ln(1 − ρ). ∎

τ^* = Δ/ρ

τ^*

the level at which the edge’s pheromone settles — adding and evaporation are in balance

Δ

how much the edge receives per iteration — edges from frequent, short tours have a large Δ and therefore a high level too

ρ

in the denominator: slow evaporation lets trails grow high and differences between edges take a long time to even out; fast evaporation keeps them low and dependent only on the last few iterations

Two edges with τ₀ = 1 and ρ = 0.3: one receives Δ = 1 in every iteration, the other is used by nobody.

The used edge approaches τ^* = 1/0.3 ≈ 3.33 (colours as in the formula above); the unused one drops below three hundredths within ten iterations. The evaporation half-life for the rows of the table above: with ρ = 0.3 it is 1.94 iterations, with ρ = 0.02 a full 34.31 iterations — so the trails of the first random tours still rule for dozens of iterations — and with ρ = 0.9 only 0.30 iterations, so the colony remembers practically only the last round.

The best setting gave 2,194 to 2,314 km — comparable to annealing from the previous article, which ended between 2,210 and 2,270 km on the same cities.

6. Better ants

• The elitist strategy adds extra pheromone to the best tour so far so that it is not lost.
• MAX–MIN Ant System (Stützle and Hoos, 2000) lets only the best ant lay pheromone and keeps τ between a lower and an upper bound. The lower bound guarantees that no edge disappears completely, so the colony does not freeze prematurely — like the one that ended on the long branch in the bridge experiment.
• Ant Colony System (Dorigo and Gambardella, 1997) with some probability takes the best edge outright and removes pheromone already while a tour is being built, so that the other ants try elsewhere.
• Local search. In practice every tour built by an ant is further polished with 2-opt moves from the article on annealing. The ants find a good region and hill climbing fine-tunes it — in the nineties this combination was among the best methods for the travelling salesman.

Definition — the elitist strategy and MAX–MIN Ant System

Let ρ ∈ (0, 1) and Q > 0 be as in the pheromone update of Ant System and let π^best be the best tour found since the start of the run, with length L^best = L(π^best).

1. The elitist strategy with parameter e ∈ ℕ (the number of “elitist ants”) performs the usual update of Ant System and then adds to every edge (i, j) that belongs to the tour π^best a further e · Q/L^best; the other edges are not affected by this step.
2. MAX–MIN Ant System with bounds 0 < τ_min < τ_max lays pheromone according to a single best tour π^best only (depending on the variant, the best in the given iteration or the best since the start of the run) and clips the result to the interval [τ_min, τ_max]: for every edge (i, j) τ_ij ← min(τ_max, max(τ_min, (1 − ρ) τ_ij + Δ_ij)), where Δ_ij = 1/L^best if (i, j) belongs to π^best, and Δ_ij = 0 otherwise.

So the elitist strategy gives the best tour so far extra reinforcement, while MAX–MIN Ant System allows only that tour to be reinforced and lets no edge drop below τ_min or climb above τ_max.

Stützle and Hoos choose the upper bound τ_max = 1/ρ L^best — exactly the steady-state value Δ/ρ from the theorem above for an edge that lies in the best tour every time. The lower bound is a small fraction of the upper one; in addition, the pheromone is initialized to τ_max so that the first iterations explore as widely as possible.

Definition — the rules of Ant Colony System

Let cities, distances, pheromone τ_ij > 0 and visibility η_ij = 1/d_ij be given as in the transition rule above, together with parameters q₀ ∈ [0, 1], β ≥ 0, ρ ∈ (0, 1), ξ ∈ (0, 1) and an initial pheromone value τ₀ > 0. Ant Colony System differs from Ant System in three rules:

1. Pseudorandom proportional rule. An ant in city i with a non-empty set of unvisited cities N_i draws q uniformly from [0, 1), independently of earlier draws. If q ≤ q₀, it moves to the city j = arg max_{l ∈ Ni} τ_il · η_il^β; if q > q₀, it chooses j ∈ N_i at random by the transition rule of Ant System with α = 1.
2. Local update. Right after the ant moves along the edge (i, j), τ_ij ← (1 − ξ) τ_ij + ξ τ₀.
3. Global update. Let π^best be the best tour found so far and L^best its length. After every iteration, only for the edges (i, j) belonging to π^best, τ_ij ← (1 − ρ) τ_ij + ρ/L^best; the pheromone of the other edges does not change.

So with probability q₀ the ant takes the best edge outright; by rule 2 a used edge weakens slightly towards the initial value τ₀, so the other ants try elsewhere; and both evaporation and reinforcement concern only the best tour.

Dorigo and Gambardella (1997) use q₀ = 0.9, β = 2 and ρ = ξ = 0.1 in the original paper — so in nine steps out of ten the ant takes the best edge and only in the tenth does it explore.

7. Where ants are at work

• Routing in networks. The AntNet algorithm (Di Caro and Dorigo, 1998) sends small ant packets through the network that measure delays and update the routing tables. The network thus continuously adapts to congestion.
• Vehicle routing and scheduling. Delivering goods, collecting waste or ordering jobs in production — tasks related to the travelling salesman, where ant algorithms are used together with local search.
• Swarm intelligence. An ant colony is one example of how clever behaviour of the whole emerges from simple individuals and local rules. Another, the particle swarm, is the subject of the next article.

8. Summary

• Ants communicate through traces in the environment (stigmergy): a shorter path gets marked faster and positive feedback reinforces it.
• In the double bridge model 85 out of 100 colonies settle on the short branch — but chance can lock in the long one too.
• Ant System chooses the next city by the pheromone τ^α and the distance η^β; pheromone evaporates at the rate ρ and short tours add more of it.
• On the regional capitals it found the optimum, but only in 7 out of 20 runs; on 60 cities it did about as well as annealing. Without pheromone or without distances it does much worse.
• The variants used in practice (MAX–MIN, ACS) prevent premature freezing and combine ants with local search.

Want to get your hands on it? Have an AI agent write a simulation of the double bridge and try what happens when you “close” the short branch halfway through the experiment — can the colony switch back to the long one?

Do you see it differently? Write to support@coden-app.com.