Teaching objectives
There are problems we cannot solve, and the vans go out every morning all the same. This laboratory starts with the travelling salesman problem — how many routes there are, why we cannot even check that one is the best, and how the error can be bounded — and then looks at five creatures that solve versions of it without any individual knowing the problem: ants, termites, a slime mould, bees and the workers of an ant nest sharing out their work. Everything is measured with a fixed budget, against a bound and against classical methods, and the result is reported even when it does not flatter the creatures. Third in the Optimization trilogy, after Linear optimization and Heuristic optimization. Designed for University; blocks A and B work at upper secondary level.
What is learned
- The combinatorial explosion of the travelling salesman problem: (n − 1)!/2 routes, where each factor comes from, and why a computer a thousand times faster buys only two more stops (rooms 1-2).
- The difference between checking a route and certifying it is optimal, P versus NP, and the deal the whole lab makes: giving up the optimum in exchange for an answer with a bounded error (rooms 3-5).
- The double-bridge experiment with real ants, the choice rule with its parameter α, evaporation ρ and Grassé's stigmergy: communicating through the environment (rooms 6-9).
- From the bridge to the map: drawing routes by hand, greedy and its last leg, the 2-opt swap and Dorigo's ant colony with trail and sight (rooms 10-14).
- Tuning a colony with a fixed budget: how many ants, how much to forget, how much trail and sight weigh, how long to wander at first and who deposits. For every knob, more is not better, and the student measures it (rooms 15-19).
- Measuring and mixing: the minimum spanning tree bound, the colony that polishes with 2-opt and an honest tournament in which the colony alone loses (rooms 20-23).
- Three more mechanisms with the same recipe: the mould that designs cheap and robust networks, bees that share attempts among options of unknown quality and decide by quorum, and Pheidole ants, which share out work with no boss using response thresholds (rooms 24-33).
- What decentralization really offers: not quality, but adaptation when the problem changes, and fault tolerance (rooms 8, 22, 23, 32, 33 and 34).
Key mathematical ideas
- With the depot fixed and the reversed route having the same length, n points give (n − 1)!/2 routes. The factorial grows so fast that 29!/2 ≈ 4.42·10³⁰: at a thousand routes per second, ten billion times the age of the universe.
- The decision version of the travelling salesman is NP-complete, but certifying optimality is harder still. What can be done is bounding: MST ≤ optimum ≤ my route, because removing one leg from the best route leaves a path connecting every point. The gap against the bound is a pessimistic guarantee.
- The choice rule P = (c + τ)^α / Σ turns small advantages into large ones when α > 1 (nonlinear reinforcement). On the map, P ∝ τ^α · η^β combines memory (trail) and sight (1/distance).
- Evaporation τ ← (1 − ρ)τ makes the trail fade geometrically (0.9¹⁰ ≈ 0.35). Without decay what was learned fossilizes; with too much nothing is learned.
- All comparisons use a fixed budget, counted in distance computations. Without that currency, more ants or more rounds always win and there is no trade-off to discover.
- The entropy of the pheromone matrix measures how much doubt the colony has left: the results curve cannot tell "slow" from "dead"; entropy can.
- The mould follows dD/dt = |Q|^μ − D with the flow shared by Kirchhoff's laws: small μ keeps loops (expensive, robust network), large μ approaches the tree (cheap and fragile).
- The explore/exploit dilemma (the multi-armed bandit) always has two ways to fail: deciding on too little information, or spending the budget looking.
- Response thresholds P = s^n / (s^n + θ^n) share out work with no boss; their spread has a trade-off (all at once, or many never working), and if thresholds learn, specialists emerge from identical generalists.
- The lab's only proven guarantees come from classical methods: Christofides (never more than 1.5 times the optimum in the metric case) and Graham (the greedy scheduling rule never more than 4/3 − 1/(3m)). No creature gives guarantees; they give adaptation.
Room-by-room contents
Room 1 · A problem from 1832
A van drives over a city map through the 30 delivery points in the order the orders came in (111 km). The student rates the problem's importance blind, then reads the modern and historical context (the 1832 German handbook; Dantzig, Fulkerson and Johnson in 1954). At the end the same van drives the best known route: 43 km.
Student tasks
- Rate the importance of the problem before reading anything.
- Recognize among four new situations which are the same problem in disguise.
Room 2 · Thirty points
A blind estimate of how long it takes to try every route through 30 points, then the student's own count: the 24 orderings of 4 stops, why each route appears twice (found by pairing kilometres across 24 miniatures with arrows), and 29!/2 typed in (the lab understands factorials). It ends with the time ladder and the key sentence: a computer a thousand times faster buys only two more stops.
Student tasks
- Count the orderings of 4 stops.
- Explain why each route appears twice.
- Write the number of routes with 30 points.
Room 3 · We cannot even check it
Checking a route (cheap) is separated from certifying it is the best (nobody knows how to do it quickly), and P versus NP is introduced. A challenge with a route of 460 and a bound of 430 introduces the idea that saves the problem in practice: bounding the error without knowing the solution.
Student tasks
- Tell "no fast algorithm is known" from "none exists".
- Decide what can be claimed from a route and a bound.
Room 4 · Giving up the optimum
The exact record (85,900 cities in 2006) against the van leaving at seven. The lab's vocabulary is set: bound, gap and anytime method, with a bar drawn on the real instance.
Student tasks
- Choose when paying for the exact optimum is worth it.
- Compute what a 4% excess costs a fleet.
Room 5 · Why look at a creature
A showcase of four animated scenes (ants and their trail, a mould weaving its network, bees and their dance, termites raising an arch). What a colony offers that a human-written algorithm does not, and the honest counterpoint: nature does not optimize, it settles. The final question is repeated in room 33.
Student tasks
- Spot the false claim about nature-inspired methods.
- Choose which creature to copy to design a tram network.
Room 6 · The double bridge
Goss and Deneubourg's experiment (1989) with Argentine ants: the student predicts the traffic split, releases 200 ants and watches the trail thicken on the short branch over an earthy ground, with a live chart. A numeric challenge on round trips uncovers the mechanism: whoever takes the short branch gets back sooner to deposit.
Student tasks
- Predict the split before releasing the ants.
- Answer which ant decided to use the short branch.
- Compute how many drops the short branch gets per drop on the long one.
Room 7 · The only rule
The choice rule P = (c+τ)^α / Σ, with two sums by hand and an interactive fork. Then the second half of Goss's experiment (the short branch opens late) and the α trade-off curve the student measures: with small α the colony never commits; with large α it locks onto the long branch and never corrects.
Student tasks
- Compute the probability of a branch with α = 1 and α = 4.
- Measure the final traffic for several α and explain both extremes.
Room 8 · Forgetting in time
Evaporation τ ← (1 − ρ)τ and a challenge with 0.9¹⁰. Halfway through, the good branch is cut and the student measures how many ants get lost for each ρ: with no evaporation the colony fossilizes; with too much, it has amnesia. This is the room that justifies the lab: the colony wins by adapting, not by speed.
Student tasks
- Compute how much trail is left after 10 steps.
- Measure the ρ curve and diagnose both failures.
Room 9 · Writing on the ground
Grassé's termites (1959) raise pillars without a blueprint: each drops its mud where fresh mud smells strongest. With scent, pillars appear; without it, a flat layer. Stigmergy is defined and the whole lab's recipe is distilled: reinforcement, decay and noise.
Student tasks
- Answer who decides where each pillar goes.
- Spot a system that is not stigmergy.
- Predict what happens to a colony with no noise.
Room 10 · Do it yourself
The student draws a route through 12 points (19,958,400 possible routes) by clicking the stops. It must be under 30 km: neither the list order nor greedy manages it. The van drives the student's route and then the best one, and the student computes their own gap. Hint after two attempts, open exit after four.
Student tasks
- Draw a route under 30 km.
- Compute the gap of their route against the optimum.
Room 11 · Always go to the nearest
Nearest neighbour step by step, with the candidates drawn at each stop. At the end the trip home is almost 10 km when the average leg is 2: greedy leaves itself the leftovers and ends 49% above the best route.
Student tasks
- Predict blind how far over greedy will be.
- Compute its excess as a percentage.
- Explain why it cannot fix the last leg.
Room 12 · Undoing crossings
Croes's 2-opt (1958) by hand: the student clicks two crossing legs and they swap; if the change would lengthen the route, it is rejected. From greedy's 50 km down below 36. It shows why a swap looks at only 4 distances and why 2-opt stops at a local optimum.
Student tasks
- Undo crossings until below 36 km.
- Say how many distances a swap must look at.
Room 13 · One ant on the map
Dorigo's rule (1992): P ∝ τ^α · η^β, trail and sight. After a numeric challenge, one ant chooses stop by stop with its fan of probabilities visible, and the student moves α and β to see what each does.
Student tasks
- Compute the probability of one candidate.
- Explain what an ant does with β = 0 and with α = 0.
Room 14 · The full cycle
Build, deposit, evaporate: ten ants on 30 points for 41 rounds. The first three are shown ant by ant; the trail goes from tangle to skeleton, with the gap and entropy curves below. At the end, three snapshots of the trail to put in time order.
Student tasks
- Compute the deposit of three ants on one edge.
- Put three trail snapshots in order.
Room 15 · A million ants?
The first room of the tuning block, with a fixed budget. The student predicts, computes how many rounds fit and measures the curve for the number of ants: a single ant reinforces noisily, 160 have no time to learn, and the good zone is around a dozen.
Student tasks
- Compute how many rounds fit in the budget.
- Measure the curve and explain both extremes.
Room 16 · How long memory lasts
Evaporation on the map with two curves at once: gap and trail entropy. Three shuffled colonies (very low, healthy and very high ρ) to identify from their charts.
Student tasks
- Measure the ρ curve.
- Recognize the stagnant and the undecided colony by their entropy.
Room 17 · Memory against sight
A grid of 30 colonies (α × β) measured by clicking them, coloured by gap. The β = 0 column is a wall and the α = 4 row does worse than the α = 2 row.
Student tasks
- Find a cell below 6%.
- Explain the failure of β = 0 and of high α.
Room 18 · The early wander
The initial pheromone τ₀ in a colony that trusts the trail (α = 3, β = 1). Each measurement says how many rounds were nearly random: with a tiny τ₀ none, with a huge τ₀ all of them.
Student tasks
- Measure the τ₀ curve.
- Explain why both extremes fail.
Room 19 · Do they all paint?
AS, elitist and MAX-MIN measured with three budgets in a table. The surprise: MMAS is the worst with a small budget and the best with a large one, because its trail floor keeps it exploring.
Student tasks
- Fill in the 4,000 and 40,000 columns.
- Explain why the winner changes with the budget.
Room 20 · A floor for the optimum
The minimum spanning tree grows leg by leg under the greedy route and gives a bound: without knowing the best route, greedy is guaranteed to be at most 45% over. Held-Karp and Christofides in the fold-out.
Student tasks
- Compute the guaranteed gap against the bound.
- Decide what can be claimed with 3% against the bound.
Room 21 · Ants with a penknife
The colony polishes each route with 2-opt on 60 points, with a fixed budget. The student measures how many passes pay off: polishing rescues almost everything, and past a point it eats the colony rounds.
Student tasks
- Measure the 2-opt passes curve.
- Explain what polishing adds and why over-polishing does not pay.
Room 22 · The tournament
Six methods on four maps with the same budget. The colony alone loses to 2-opt with restarts on every map; the polishing colony wins, and only on the large map. It is said plainly, and room 8 is recalled to explain the colony's real value.
Student tasks
- Read the tournament map by map.
- Explain what the colony is for if it does not win on raw power.
Room 23 · The fight
Five methods race live on 60 points: at first there are only 48 stops and halfway through the budget 12 new orders arrive. Before the change the polishing colony leads (0.65%); right after, the 2-opt that repairs its route wins (1.72%) and the colony alone sinks (45%) because its old trail points to routes without the new stops. Memory helps or hinders depending on whether the change is gradual or abrupt, announced or not.
Student tasks
- Predict who will recover first.
- Explain why the colony's memory hinders after an abrupt change.
- Say when the colony pays off.
Room 24 · A mould in the maze
Opens the Physarum block: cheap network against network with loops, Nakagaki (Nature, 2000) and tree counts (35 connections) against 630 possible. Then the mould fills a maze and keeps only the 23 segments of the shortest path; without atrophy it prunes nothing.
Student tasks
- Count the connections of a tree and the possible ones.
- Explain what happens without atrophy.
Room 25 · The Tokyo network
Oat flakes on 36 cities around Tokyo and a mould that weaves the network (Tero et al., Science 2010). With a single parameter μ, the student looks for a network costing at most twice the minimum tree that almost no cut can split.
Student tasks
- Find a μ with acceptable cost and fragility.
- Explain why the minimum tree is not enough.
Room 26 · The same recipe, another kitchen
The double bridge made of mould tubes (the short branch survives), a table of ants versus mould by ingredient, and which creature to copy for each problem.
Student tasks
- Identify the mould's decay.
- Choose a mechanism for a fibre network and for a collection route.
Room 27 · Explore or exploit
The bandit dilemma (Robbins, 1952; Charnov, 1976) in A/B tests, clinical trials and social media. A bee with 300 visits and five flowers: the student measures how many tries per flower pay off before committing.
Student tasks
- Compute how many visits are left after exploring.
- Measure the curve and explain both extremes.
Room 28 · The dance
Von Frisch and the waggle dance; recruits per dance circuit. Seeley's experiment (1991): two feeders that swap halfway. With too much recruitment gain the hive stays at the feeder that is no longer good.
Student tasks
- Compute a dance's followers.
- Measure the gain curve and explain the lock-in.
Room 29 · Choosing a home
A swarm chooses a hollow by quorum (Seeley, Honeybee Democracy). A low quorum decides fast and gets it wrong; a high one gets it right and arrives late. The student measures the value of the decision for several quorums.
Student tasks
- Measure the quorum curve.
- Explain both failures.
Room 30 · Sharing out the work
The makespan with 7 operations and 3 theatres: the student assigns them on a Gantt chart until everything ends at 9 hours. Graham's greedy rule (1969) gives 11: exactly the worst case of his 4/3 − 1/(3m) guarantee.
Student tasks
- Find an assignment that ends at 9 hours.
- Compute how far over the greedy rule is.
Room 31 · Each with its threshold
Response thresholds P = s^n/(s^n+θ^n) with a colony of 100 workers. With equal thresholds the colony works in bursts; with a large spread, part of it never works. The student looks for the middle ground.
Student tasks
- Compute how many workers start for a given stimulus.
- Find a spread meeting both conditions.
Room 32 · Learning by doing
Thresholds that drop with practice: specialists emerge from 100 identical generalists (a two-humped histogram). If the specialists are removed, the rest take their place without anyone reassigning them.
Student tasks
- Compute a threshold after 10 steps of practice.
- Explain who decides the specialization.
Room 33 · When the problem changes
An exact plan, a plan recomputed every 100 steps and a threshold colony facing a demand that flips without warning. Before the change the plan wins; with the change, the colony.
Student tasks
- Say who wins before and after the change.
- Choose when each policy fits.
Room 34 · The test bench
A challenge-free playground: generate a map of 6 to 40 points (with the exact optimum up to 13) and release ants, slime mould or bees with their parameters in plain view. Each release is animated smoothly and saved in a trail chart on the same map, with a button to run 100 more and see the median. Thresholds are absent on purpose: they share out work, they do not build routes or networks.
Student tasks
- Try the three methods on one map and compare their results.
- Move the parameters and check in the trail chart whether the median changes.
Room 35 · None wins everywhere
The recipe table for the five mechanisms with one cell to fill in, which problem each solves, room 5's question again (recalling what the student chose) and the honest close of the trilogy.
Student tasks
- Complete the bees' recipe.
- Answer room 5's question again.
Rooms to project
The most striking ones to show and discuss in class.