How ant colonies solve hard problems

A guide to Ant Colony Optimization for people who have never met it — built entirely around a system we actually ran, and the things that surprised us.

Reza Tabibazar, Avriz Engineering. Implementation and analysis with Claude (Anthropic). Every number below came off a real run on BareMetal Cloud. Where something is counterintuitive we say so and show the measurement that changed our minds — including the one where our clever idea made things worse.

The problem: a salesman and 52 cities

You have 52 cities and need the shortest route visiting each exactly once, returning home. It sounds like the kind of thing a computer should just solve.

It is not. With 52 cities there are 51!/2 possible tours — a number with 66 digits. If every atom in the observable Earth were a computer checking a billion tours a second, since the Big Bang, you would not be close. This is the travelling salesman problem, and it is the canonical example of combinatorial explosion.

Here is what a 52-city problem actually looks like, and why the naive approach disappoints. The obvious algorithm — “always drive to the nearest city you have not visited yet” — is called nearest-neighbour, and it is what most people invent in the first thirty seconds.

The idea: borrow it from actual ants

Real ants find short paths to food without any ant knowing the route, seeing the map, or being told what to do. The mechanism was pinned down in a famous 1989 experiment where a nest was connected to food by two bridges of different lengths.

Turning that into an algorithm

Marco Dorigo made this into an optimisation method in 1992. Replace the map with a graph, the ants with simulated ants, and the scent with a number on every edge. Then run four steps, over and over.

1. Each ant builds a complete tour. Starting from a random city, it repeatedly picks the next one — not greedily, but at random, weighted so that attractive edges are more likely. Twenty-five ants build twenty-five different tours.
2. Score them. Measure each tour. Keep the shortest.
3. Evaporate. Every edge loses a fixed percentage of its pheromone. Ours loses 2% per round. This is not housekeeping — it is the most important step.
4. Deposit. Add pheromone to the edges of the best tour, so the next round’s ants are more likely to reuse them.

That is the entire algorithm. The probability an ant moves from city i to city j is proportional to:

τ_ij × (1 / d_ij)^β

τ — pheromone: what the colony has learned. 1/d — nearness: what is obvious right now. β — how much to trust the obvious.

Those two terms balance experience against instinct, and the balance is the whole design. With pheromone only, the colony has no sense of distance and locks onto whatever it stumbled into first. With nearness only, every ant is a nearest-neighbour tour with dice and nothing is ever learned. Used together, the colony starts out guided by distance and gradually becomes guided by what has actually worked.

Why evaporation is the clever part

Depositing pheromone is the obvious half. Forgetting it is the half that makes the method work, for two separate reasons.

Five things that surprised us

1. Rewarding the all-time best is a trap

The natural instinct is to reinforce the best tour you have ever seen. We did exactly that. It failed, and it failed in a way that looked like success.

On a 52-city map our colony reached the known optimum on 3 runs out of 10, and the other seven froze — no improvement after 18,000 rounds. The colony had convinced itself. Every ant was walking the same route, reinforcing it, and no alternative could ever accumulate enough pheromone to compete.

The fix is one line: reward the best tour of this round, not the best tour ever. The all-time best is still tracked and still reported — it just stops being the thing that gets fed.

Measured, same code, one line changed. Reinforcing the all-time best: 3 of 10 runs reached the optimum. Reinforcing the round’s best: 10 of 10.

The lesson generalises well beyond ants: a system that only ever reinforces its current champion stops being able to discover that the champion is mediocre.

2. The ants are not enough on their own

Any self-crossing route can be shortened by uncrossing it. There is a classical method that does nothing but this, called 2-opt: look for two edges that could be swapped for two shorter ones, swap them, repeat until no such pair exists.

On the smallest problem the omission was invisible. That is the uncomfortable part: our test suite passed, every tour was valid, and the algorithm was “working” — it was simply much worse than it should have been, in a way only a bigger problem could reveal.

The discipline that made this legible. We wrote down the quality we would accept before running anything, and when the 442-city result came in at 14% we reported it as a failure rather than adjusting the target. Adding 2-opt afterwards is defensible because it is a missing standard component. Quietly loosening the threshold would not have been — and from the inside, the two feel almost identical.

3. Sharing results made the swarm worse

With the algorithm working, we ran it on three separate machines. Two ways to use three machines: three colonies with no communication at all, taking the best answer at the end; or the same three, each publishing its best tour every 500 rounds and adopting any better one it finds.

Sharing is obviously better. Three heads, pooled discoveries, no wasted effort. We expected a clear win.

Three machines exploring different ideas are worth more than three machines agreeing quickly. Sharing information is not free — it is paid for in diversity, and diversity is the only reason to have run three of them.

Note how total the collapse was: all three sharing colonies returned the identical route, so their average and their best are the same number. There was no “best of three” left to take.

This is a real trade-off with a real knob. We shared every 500 rounds, which is aggressive; every 5,000 would likely keep most of the benefit and much of the diversity. The point is not that sharing is bad — it is that “obviously we should pool results” was a hypothesis, and it lost.

4. We moved the cities underneath it, and the stale trails did no harm

Everything above about forgetting-as-error-correction was an argument. We later turned it into a measurement: solve a map, then pick up a fifth of the cities and drop them somewhere else, mid-run, leaving their pheromone exactly where it was. Those trails now point at where the cities used to be. They are lies, and nothing deletes them.

Keeping the pheromone beat starting over — and here is the odd part: deliberately scrubbing the false trails made things worse. Leaving the lies in place was better than cleaning them up.

The row that stopped us publishing this. We swept the change from 5% of the cities up to 100%. Keeping the pheromone won at every single setting — including when every city had moved and there was no old map left to remember anything about. Whatever was producing that number, it could not be memory.

A pheromone matrix that has been running for a while differs from a fresh one in two ways at once. It remembers which edges were good — and it is concentrated, nearly all its weight on a few edges, where a restart spreads everything flat. “Keep versus restart” confounds the two. So we added a fourth arm that keeps one and destroys the other: shuffle the matrix through a random relabelling of the cities. Every value survives, so the concentration is untouched. Which edge holds which value is scrambled, so the memory is gone.

Survived: keeping the lies is never worse than scrubbing them, at any amount of change. Wrong pheromone genuinely does not hurt — evaporation absorbs it, and paying to clean it up is a net loss.

Did not survive: the vaguer version, that this algorithm’s edge on changing problems is mostly about remembering the old map. Mostly it is about not throwing away a set of preferences that took a while to sharpen.

5. A search splits two hundred ways for free, then falls off a cliff

If a colony can be run on three machines, why not three hundred? We fixed a compute budget and spent it every way we could: one long run, then ten shorter, then a hundred, up to ten thousand runs of twenty rounds each. Same total work every time, combined by taking the best tour anyone found — which needs no communication at all.

The collapse is not caused by having too many workers. It is caused by each one becoming too short. A colony spends its first rounds building pheromone up from a crude starting route; a worker that dies before that happens hands back something barely better than where it began. Ten thousand of those are worth less than one run that got somewhere.

Give every worker at least a couple of seconds of real work. Then have as many workers as you like.

That is a floor on task size, not a ceiling on parallelism — and it is the number that decides what kind of machine makes sense. Against a two-second task, a unikernel that boots in 31 ms costs 1.7% overhead; a serverless function at 45 ms costs 2.5%; booting a whole Linux guest at 950 ms costs 53%.

One caution we want on the record. The best split beat one long run by a whisker on both maps, but the margin is inside the noise. The claim we will defend is “splitting the work costs nothing”, not “splitting the work helps”. That is still the claim that matters, because the payoff was never better answers — it was the same answers on hardware that costs a twentieth as much.

When should you reach for this?

Good fit: routing and scheduling with awkward real-world constraints; problems that change while you are solving them; anywhere you need a good answer continuously rather than a perfect one once.

Poor fit: static, pure TSP — specialised solvers like Lin–Kernighan will beat this comfortably and it is not close. Anything with a known exact algorithm. Problems where a solution cannot be built one piece at a time.

The honest summary: ACO is rarely the best tool for a textbook problem, and often a very good tool for a messy one that changes underneath you. Its real advantage is that it never stops adapting, because it never stops forgetting.

What we built

Three colonies on three machines with 16 MB of memory each and no operating system — the program runs directly on the hardware. They coordinate through a single shared file in cloud storage: each writes its own best tour, and reads the others. No coordinator, no locks, nothing to fail centrally. The same stigmergy the ants use, one level up.

The source, the raw logs and every number above are public: github.com/tabibazar/unikernel-c, branch aco-swarm.

If you remember five things

1. Simple local rules produce global intelligence. No ant knows the route. The colony still finds it.
2. Forgetting is a feature. It prevents lock-in, and it happens to make the system shrug off hardware faults.
3. Reinforcing only your current champion stops you discovering it was mediocre. 3 out of 10 became 10 out of 10 on that one insight.
4. Consensus has a cost. Our sharing swarm agreed faster and finished worse.
5. Check what your good result is actually made of. Keeping the pheromone through a change beat restarting every time — and a control arm showed three quarters of that was concentration, not memory.

Avriz Engineering, 2 September 2026. Every figure is from a measured run; the code and logs are linked above. Updated 4 September 2026 with the last two findings — moving the cities mid-run, and how far a search can be split before it stops working.