The genetic algorithms of the previous lesson searched through inheritance: good individuals reproduce and their traits propagate. Ant colony optimization (ACO) searches through something stranger and more elegant: indirect cooperation. No agent inherits anything from another; each one simply leaves marks in the environment that bias the decisions of those that follow. It is an idea copied literally from real ants, and it turns out to be especially natural for the routing problems that obsess Rutalia: the marks live exactly where the problem lives, on the legs between stops. In this lesson we will formalize the mechanism (pheromones, transition probabilities, evaporation), implement it in full in Python on the same 10-point instance from the three previous lessons, and close the module with what was promised: the experimental comparison of the three approaches to the TSP — branch and bound, genetic, and ant colony — and a guide to when to choose each one.

1. The inspiration: ants, pheromones, and stigmergy
2. Anatomy of ACO: what it maintains and how it decides
3. The transition probability: α and β
4. Pheromone evaporation and deposit
5. Complete implementation: ACO for Rutalia's TSP
6. Parameter tuning
7. Experimental comparison: B&B vs genetic vs ACO
8. When to choose each approach

The classic experiment (Deneubourg, 1980s, with real Argentine ants): an ant nest is connected to a food source by two bridges, one short and one long. At first the ants choose at random, half and half. After a while, almost all of them use the short bridge. No ant has compared the bridges; no ant even knows there are two. The mechanism:

1. Each ant deposits pheromone (a chemical signal) as it walks.
2. Ants probabilistically prefer paths with more pheromone.
3. Those taking the short bridge make the round trip sooner, so the short bridge accumulates pheromone faster.
4. More pheromone attracts more ants, which deposit more pheromone: positive feedback.
5. Pheromone evaporates, gradually erasing trails that aren't reinforced.

This coordination through modifications of the environment — no direct communication, no boss, no map — is called stigmergy. What turns it into an algorithm is one observation: pheromone works as a collective memory of quality distributed over the problem's edges, and evaporation as a controlled forgetting that prevents locking onto the first mediocre solution. Marco Dorigo formalized this in 1992 as an optimization method, with the TSP as its first proving ground — the same problem, at almost the same scale, as our Rutalia route.

Translation into computational ingredients, side by side with the GA to anchor the ideas:

The philosophical difference: the GA recombines whole solutions; ACO learns, edge by edge, which local decisions tend to appear in good solutions. That's why ACO shines on problems where the solution is a sequence of decisions over a map of options — routes, scheduling, chained assignments.

An ant sitting at point i chooses its next stop j among the unvisited ones, at random but with bias. The probability of choosing j is proportional to:

where:

• τ(i,j) is the edge's pheromone — the collective memory: "good routes passed through here".
• η(i,j) is the local heuristic information, for the TSP η = 1 / distance(i,j) — the useful myopia: "this stop is nearby".
• α and β are exponents that weigh how much each source counts.

The two extremes clarify each exponent's role:

• With α = 0, pheromone is ignored: each ant is a probabilistic nearest neighbor, with no collective learning. Recall from 02-02 that pure nearest neighbor gave 43.1 km (+22%): that's roughly the quality of ACO's first iteration, before any trail exists.
• With β = 0, distance is ignored: the first (random) routes lay pheromone, the following ones imitate them, and the colony self-confirms onto bad routes — textbook premature convergence.

The art lives in the middle: typically α = 1 and β between 2 and 5 (the heuristic leads at the start, when the pheromone is uniform; the trail takes control as it accumulates evidence).

After all the ants have built their routes, the matrix τ is updated in two steps:

1. Evaporation — every edge loses a fraction ρ of its pheromone:

   τ(i,j) ← (1 − ρ) · τ(i,j)

   Without evaporation, past mistakes are never erased and the first reasonable route fossilizes. With a typical ρ of 0.3–0.5, an unreinforced trail dies out within a few iterations.

2. Deposit — each ant adds pheromone to the edges of its route, in an amount inversely proportional to its length:

   τ(i,j) ← τ(i,j) + Q / L for every edge (i,j) of a route of length L

   Short routes deposit more per edge: Deneubourg's bridge feedback loop, in one line of code. Q is just a scaling constant.

This is the original scheme (Ant System). The variants that dominate the literature fine-tune exactly here: elitist (the best-ever route deposits extra), MAX-MIN (τ clamped between a minimum and a maximum to force exploration), ACS (local evaporation during construction). We'll stick with the classic scheme, which already exhibits all the interesting behavior.

On the module's canonical instance (requires NAMES, D, and route_length from 02-02; known optimum: 35.22 km):

Guided reading:

• random.choices(..., weights=weights) implements the transition roulette: we don't pick the best candidate (that would be a greedy) but one at random with biased probabilities. That residue of randomness is what keeps exploration alive.
• The cost per iteration is n_ants × N decisions, each over O(N) candidates: Θ(ants · N²). With 20 ants and 100 iterations that's 20 × 100 = 2,000 routes constructed — a budget similar to the GA's (20,000 evaluations, but those were cheaper: just measuring, not constructing).
• We keep the global best (best_km) separate from the matrix τ: the colony may temporarily drift away from the best route found (and it's fine that it explores), but the result we deliver never gets worse.
• In our run, ACO reaches the optimal 35.22 km, typically within the first few dozen iterations: the history shows the expected mechanics — early iterations around 40-44 km (near-greedy ants over uniform pheromone) and a rapid drop as the trail accumulates evidence.

Diagnosis works just as with the GA: with the history and with several seeds. If all the ants build nearly identical routes by iteration 15, there's premature convergence (raise ρ or lower α); if the global best is still dropping at the last iteration, you need more iterations.

Time to close what we opened in 02-02. Same instance (10 points, depot included), same hardware, runs with each lesson's configuration:

Honest readings of this table:

• On this instance everyone ties at 35.22 km. That is neither a coincidence nor a merit of the metaheuristics: 10 nodes is comfortable territory for anyone. We chose it precisely so we would have the correct answer and could verify that each method reaches it. The interesting row is "with 100 stops": there the exact methods vanish and all that's left is comparing metaheuristics against each other — against lower bounds, since the optimum is unknowable.
• The difference between GA and ACO here is not quality but character. The GA is agnostic: it only needs to evaluate solutions, so it serves equally for knapsacks, routes, or schedules. ACO builds in problem structure (the local heuristic η, trails over edges): it usually converges faster on routing problems, and does worse — or requires a redesign — outside them.
• B&B is unbeatable as long as it gets there. Certificate, no seeds, no hyperparameters to calibrate. The practical frontier of exact TSP with serious techniques sits at hundreds to thousands of nodes; our homemade bound reaches far less, but the principle is the same.

Decision rules that summarize the entire module, in "Monday morning at Rutalia" form:

• Is the instance small, or does the problem have exploitable exact structure (pseudo-polynomial DP like the knapsack, strong relaxations as in ILP)? → Exact method (DP, B&B, ILP solver). It's the only option with a certificate, and the certificate has business value: nobody renegotiates a route that was proven optimal.
• Large instance, "messy" objective function (odd penalties, business rules, time windows), or a model that changes every week? → Metaheuristic. The GA if the problem is heterogeneous or has no route structure; ACO if it's a sequential construction of paths over a map of options. In both cases: several seeds, a history, and a lower bound — however crude — so you know how much you're leaving on the table.
• Need the best of both? Hybrids: a metaheuristic for a B&B's initial incumbent (we saw it in 02-03), or local search refining the best individual/ant. In industrial practice almost nothing beats a good hybrid.
• And always: a greedy first. It costs minutes, gives you the baseline, and sometimes (fractional knapsack, canonical coin systems) it turns out to be optimal. The sophisticated tools justify themselves against that baseline, not against a vacuum.

• Forgetting evaporation (or setting it near zero). Pheromone only grows, the first decent route fossilizes, and the whole colony repeats it. It's the most common failure in homemade implementations: the algorithm "converges" suspiciously fast and always to the same thing.
• η upside down. The heuristic must reward short edges: η = 1/distance. If you use the distance directly, the ants prefer long legs and the algorithm actively malfunctions. If there are zero distances (two stops in the same doorway), add an epsilon.
• Picking the maximum instead of sampling. Replacing the roulette with max(candidates) turns the colony into N copies of the same deterministic greedy: without variety there's no trail to learn from. (Serious variants like ACS blend both, but with an explicit probability.)
• Updating pheromone mid-construction when the scheme uses global updates: it mixes the phases and makes the behavior irreproducible. All ants construct, then evaporate, then deposit.
• Comparing metaheuristics with a single seed. With two stochastic methods, one run of each is ranking coin flips. Distributions over 10-30 seeds, same instances, same evaluation budget.
• Tip: print the matrix τ (or a heatmap) every 20 iterations. Watching the trail concentrate on the optimal route's edges — and spotting when it concentrates on the wrong ones — teaches more than any description.

1. The transition rule by hand. An ant is at the depot; three stops remain: P (distance 2, τ = 4), Q (distance 4, τ = 1), and R (distance 1, τ = 1). With α = 1 and β = 1, compute the probability of choosing each stop. Repeat with α = 0 and with β = 0. Comment on the "personality" the ant shows in each case.

2. The role of evaporation. Run ant_colony with ρ ∈ {0.0, 0.1, 0.5, 0.9} (10 seeds each). Record how many seeds reach 35.22 km and the mean iteration at which the best result is reached. Explain the two extremes using the lesson's vocabulary.

3. Three-way tournament. Build a test bench that runs, on the Rutalia instance, the GA from 02-04 and this lesson's ACO with an equalized budget (e.g. 20,000 route evaluations each) and 20 seeds, and compares: best result, mean, and standard deviation. Add the B&B row (deterministic, from 02-03). Does your experiment reproduce the conclusions of the lesson's table?

Exercise 1. With α = β = 1, each candidate's weight is τ · (1/d): P → 4 · (1/2) = 2; Q → 1 · (1/4) = 0.25; R → 1 · (1/1) = 1. Sum 3.25 → p(P) ≈ 0.615, p(Q) ≈ 0.077, p(R) ≈ 0.308. With α = 0 (heuristic only): weights 0.5 / 0.25 / 1 → p ≈ 0.286 / 0.143 / 0.571 — the ant is a probabilistic nearest-neighbor and prefers R, the closest one. With β = 0 (pheromone only): weights 4 / 1 / 1 → p ≈ 0.667 / 0.167 / 0.167 — the ant is pure herd and follows the trail toward P even though closer options exist. The full rule negotiates between the two personalities.

Exercise 2. Expected pattern: with ρ = 0.0 the pheromone is never erased; the reinforcements from the first iterations (built almost at random) dominate forever and several seeds stall above the optimum — fossilization. With ρ = 0.1 it improves but changes of opinion still consolidate slowly. With ρ = 0.5 (our default), balance: almost every seed reaches 35.22 km within a few dozen iterations. With ρ = 0.9 the colony is amnesiac: each iteration nearly wipes out what was learned, the trail never accumulates evidence, and the behavior stays close to the random nearest-neighbor of the first iteration; reaching the optimum becomes a matter of luck. Evaporation is ACO's exploration/exploitation dial, just as mutation was in the GA.

Exercise 3. Skeleton: fix evaluations = 20_000; for the GA that is pop_size × generations = 100 × 200; for ACO, n_ants × iterations × 1 construction per ant → e.g. 20 ants × 100 iterations = 2,000 constructions (if you want a finer match, count each construction as N choices and adjust). Run each method with seed = 0..19, record the best km of each run, and compute the minimum, mean, and standard deviation with statistics. Expected result on this instance: both methods reach 35.22 km on most seeds (ACO's mean is usually equal or slightly better thanks to its local heuristic; the GA shows somewhat more variance), and B&B contributes the only row containing the word "certificate". If your numbers differ, it's not an error: it's the stochastic nature this lesson has taught you to measure rather than ignore.

We close the optimization module with the three families face to face on the same problem. The ant colony supplied the last piece: search through stigmergic cooperation, where the collective memory lives on the edges (pheromone τ), the useful myopia is contributed by the local heuristic (η), the transition rule with α and β negotiates between them, and evaporation keeps the learning revisable. On Rutalia's TSP, B&B certified 35.22 km, and both the genetic algorithm and the ants reached it without a certificate — a tie on the small instance we chose precisely so we could grade the exam, with the real divergence reserved for the large instances where only the metaheuristics remain standing. The whole module fits in one sentence: formulate precisely (02-01), respect the combinatorial explosion (02-02), demand the optimum while you can afford it (02-03), and negotiate intelligently when you can't (02-04, 02-05). One debt remains, deliberately unpaid: we have spent five lessons talking about routes, legs, connected points, and "edges" — even the pheromone lived on them — without formally defining what that structure is. That structure is the graph, and it stars in module 3: we will learn to represent graphs rigorously (03-01), to traverse them (03-02), and to exploit their classic algorithms — there the seeds we planted in 01-04 await us: the heap that will power Dijkstra in shortest paths (03-03) and the union-find that will support Kruskal in spanning trees (03-04). Rutalia's routes are about to become first-class mathematics.