CI Chapter 7 — Ant Colony Optimization.

ACO is one of those algorithms that looks almost suspiciously poetic the first time you meet it. “Ants walk, ants smell chemicals, therefore solve NP-hard optimisation?” It sounds like a joke right until you work through the mechanism carefully. Then it clicks. The ants are simple. The environment carries memory. Positive feedback amplifies good partial decisions. Evaporation stops the system from worshipping old mistakes forever. Suddenly the metaphor stops being cute and starts being computationally sharp.

01 Why real ants matter to optimisation at all

Real ants are individually limited creatures. No single foraging ant holds a global map of the environment, runs Dijkstra in its head, and broadcasts a path plan to the colony. Yet colonies reliably discover efficient routes from nest to food. That means the intelligence is not sitting inside one genius ant. It is emerging from a distributed process.

That is exactly the kind of pattern computational intelligence loves: simple local rules, indirect communication, adaptation over time, and no central coordinator. Ants are doing path discovery and collective optimisation with ingredients that look algorithmically promising.

This matters for AI because many hard optimisation problems can also be expressed as constructing a path through a graph or state space: visiting cities, assigning jobs, routing packets, sequencing actions, designing circuits. If ants are naturally good at incremental path construction, maybe we can borrow that principle.

02 The double-bridge experiment and the logic of pheromone

The classical biological story behind ACO is the double bridge experiment. Imagine a nest connected to a food source by two bridges, one shorter and one longer. At the start, ants choose more or less randomly. But as they walk, they deposit pheromone. Pheromone is a chemical trail that makes a path more attractive to later ants.

Now notice what happens over time. Ants on the shorter bridge complete the round trip faster. That means, per unit time, the shorter bridge receives more traversals, and therefore more pheromone reinforcement. More pheromone attracts more ants. More ants add more pheromone. This is positive feedback. The colony gradually concentrates on the shorter route even though no individual ant explicitly knows it is shorter in a global geometric sense.

But positive feedback alone would be dangerous. A random early fluctuation could lock the colony into a poor path forever. That is why evaporation matters. Pheromone fades over time. Old trails lose influence unless ants keep reinforcing them. Evaporation gives the colony a forgetting mechanism, which means exploration is never fully dead.

03 Stigmergy: the environment becomes the message board

One of the prettiest ideas in this chapter is stigmergy. It means indirect communication through the environment. An ant does not have to talk directly to another ant. It modifies the environment by leaving pheromone, and future ants read that modification.

Computationally, this is powerful because it gives us a distributed external memory. In ACO, the pheromone matrix plays exactly that role. It is the colony's public notebook. Each ant reads from it while constructing a tour, and then writes back to it after completing the tour.

This is why ACO feels different from a normal single-agent search procedure. The knowledge of good partial decisions is not sitting in one global planning brain. It is emerging in the pheromone structure, edge by edge.

04 The TSP is the perfect stage for ACO

The most famous application of ACO is the Travelling Salesman Problem (TSP): given \(n\) cities, visit each city exactly once, return to the start, and minimise the total tour length. It is a canonical NP-hard combinatorial optimisation problem. For a symmetric TSP, the number of distinct tours is \((n-1)!/2\). That grows explosively.

TSP is ideal for ACO because a solution is naturally constructed one city at a time. At each step, an ant chooses the next city from the set of unvisited cities. Pheromone can live on edges \((i,j)\). Local desirability can be encoded through inverse distance. The path-building metaphor fits perfectly.

Many other problems can be bent into this form too, but TSP is the clean teaching case because every component is visible: path construction, memory on edges, heuristic desirability, and a final tour cost.

05 Ant System: the original ACO algorithm

Marco Dorigo's original algorithm is called Ant System (AS). The outline is simple:

1. Place \(N\) ants on the graph.
2. Each ant constructs a complete tour by probabilistically choosing the next city.
3. Evaluate every tour length \(L_k\).
4. Evaporate pheromone globally.
5. Let ants deposit new pheromone on the edges they used.
6. Repeat until a stopping criterion is met.

The algorithm uses two main ingredients for each edge \((i,j)\):

• Pheromone \(\tau_{ij}\): learned collective desirability from past search.
• Visibility \(\eta_{ij}\): usually a hand-designed local heuristic, most often \(1/d_{ij}\), the inverse of distance.

The transition probability for moving from city \(i\) to an allowed city \(j\) is:

Here \(\alpha\) controls how strongly the ant follows pheromone, and \(\beta\) controls how strongly it follows the visibility heuristic. If \(\alpha=0\), ants ignore pheromone entirely. If \(\beta=0\), ants ignore distance entirely.

After all ants finish their tours, pheromone is updated by:

The term \((1-\rho)\) models evaporation. If \(\rho=0.1\), then 10% evaporates each iteration. The deposit term \(Q/L_k\) means shorter tours leave larger pheromone deposits, which reinforces good tours.

06 Reading the transition formula without panicking

The transition probability formula looks scary until you decode each factor in plain language.

Suppose an ant is at city \(i\). It has a set of candidate next cities it has not visited yet. For each allowed city \(j\), it computes a weight

Then it normalises these weights so they add to 1. That is all the probability formula is doing.

The role of each symbol is worth stating in human terms:

• \(\tau_{ij}\) — “How much has the colony liked this edge before?”
• \(\eta_{ij}=1/d_{ij}\) — “How attractive is this edge locally right now because it is short?”
• \(\alpha\) — “How much do we trust the colony's memory?”
• \(\beta\) — “How much do we trust the local distance heuristic?”

Typical Ant System settings give \(\beta\) a stronger influence than \(\alpha\), often something like \(\alpha=1\), \(\beta=5\). That makes sense: early in the run, pheromone does not know much yet, but edge length is already informative.

07 Worked 5-city TSP example, AIMLCZG557 style

Let us build a complete worked example in the style used in class. We use a symmetric 5-city TSP with start node 4. Parameters:

• \(\alpha = 0.5\)
• \(\beta = 0.75\)
• \(\rho = 0.1\)
• \(Q = 100\)
• initial pheromone \(\tau_0 = 1\) on every edge

We choose the following distance matrix:

	1	2	3	4	5
1	0	8	4	7	3
2	8	0	3	2	6
3	4	3	0	4	2
4	7	2	4	0	5
5	3	6	2	5	0

So the visibility values are \(\eta_{ij}=1/d_{ij}\). For example, \(\eta_{42}=1/2=0.5\), \(\eta_{43}=1/4=0.25\), \(\eta_{45}=1/5=0.2\), and \(\eta_{41}=1/7\approx 0.1429\).

Because all pheromone values start equal at 1, the initial transition weights from city 4 depend only on visibility:

Numerically:

• to city 2: \((0.5)^{0.75} \approx 0.5946\)
• to city 3: \((0.25)^{0.75} \approx 0.3536\)
• to city 5: \((0.2)^{0.75} \approx 0.2991\)
• to city 1: \((0.1429)^{0.75} \approx 0.2324\)

Total weight is about 1.4797, so the normalised transition probabilities are roughly:

• \(P(4\to2)\approx 0.402\)
• \(P(4\to3)\approx 0.239\)
• \(P(4\to5)\approx 0.202\)
• \(P(4\to1)\approx 0.157\)

City 2 has the highest probability, so for this worked example let the ant move 4 \(\to\) 2.

Now the tabu list forbids returning to 4 or revisiting 2. From city 2, allowed cities are 1, 3, and 5.

• \(\eta_{23}=1/3\), weight \((1/3)^{0.75} \approx 0.4387\)
• \(\eta_{25}=1/6\), weight \((1/6)^{0.75} \approx 0.2608\)
• \(\eta_{21}=1/8\), weight \((1/8)^{0.75} \approx 0.2102\)

After normalising, city 3 has the highest probability, so choose 2 \(\to\) 3.

From city 3, allowed cities are 1 and 5:

• \(\eta_{35}=1/2\), weight \(0.5946\)
• \(\eta_{31}=1/4\), weight \(0.3536\)

So choose 3 \(\to\) 5. Then the only unvisited city left is 1, so move 5 \(\to\) 1, and finally return to the start: 1 \(\to\) 4.

The complete tour is therefore:

Its length is:

So the pheromone deposit contributed by this ant is:

08 Pheromone update, second iteration, and how memory starts to form

Before deposition, evaporation reduces every pheromone value by 10% because \(\rho=0.1\). Since every edge started at 1, every edge temporarily drops to:

Now add \(5.882\) to every edge used in the tour \((4,2), (2,3), (3,5), (5,1), (1,4)\). Those used edges become approximately:

Unused edges remain at 0.9. That already creates a clear colony memory: five edges now look much more attractive than the rest.

What does that mean on the next iteration? Consider the choice from city 4 again. The edge \((4,2)\) now has high pheromone 6.782, while edges \((4,3)\) and \((4,5)\) remain near 0.9. Because the transition weight is \(\tau^{\alpha}\eta^{\beta}\), the colony memory starts amplifying the already-strong short edge 4–2.

For instance, using \(\alpha=0.5\), the new factor from pheromone on edge 4–2 becomes \(\sqrt{6.782}\approx 2.604\), whereas unused edges contribute only \(\sqrt{0.9}\approx 0.949\). Multiplying by visibility gives a much stronger weight for 4–2 than before. That is how good tours reinforce themselves.

Notice the positive-feedback logic carefully. A short tour deposits more because \(Q/L\) is larger. That raises pheromone on its edges. Stronger pheromone makes those edges more likely to be selected. More ants use them, so they receive more deposits. This is why ACO can converge quickly on strong structures — and why parameter tuning is crucial to stop it converging too quickly on the wrong ones.

09 Parameter sensitivity: what \(\alpha\), \(\beta\), \(\rho\), and \(N\) really do

ACO is famous for being intuitive and also a little touchy. The main parameters control the exploration–exploitation balance.

High \(\alpha\) means pheromone matters a lot. Ants strongly exploit the colony's learned memory. This can speed convergence, but it increases the risk of getting trapped in local optima because early trails become self-fulfilling.

High \(\beta\) means visibility matters a lot. In TSP that means ants strongly prefer short immediate edges. This can make the algorithm resemble a greedy nearest-neighbour heuristic. Sometimes good, sometimes too myopic.

Low \(\rho\) means slow evaporation. Old information persists, which strengthens exploitation and memory. High \(\rho\) means fast evaporation, which weakens old trails quickly and increases exploration.

More ants \(N\) means better sampling of the search space per iteration, but higher computation. More ants can also smooth out randomness because the pheromone update aggregates more tours.

The key is not tuning parameters in isolation. \(\alpha\), \(\beta\), and \(\rho\) interact. A large \(\alpha\) with a tiny \(\rho\) creates strong trail persistence. A small \(\alpha\) with a large \(\rho\) makes pheromone almost irrelevant. Good ACO behaviour lives in the balance.

10 Improvements over basic Ant System: ACS, MMAS, and elitist ideas

The original Ant System is elegant, but later variants improve convergence behaviour and reduce stagnation.

Ant Colony System (ACS) introduces three famous changes. First, ants perform a local pheromone update while constructing their tours, which discourages too many ants from collapsing onto exactly the same edges inside one iteration. Second, only the best ant performs the main global update instead of every ant depositing equally. Third, ACS uses a pseudo-random proportional rule: with high probability \(q_0\), choose the best-looking next city greedily; otherwise sample probabilistically. This blends exploitation with controlled randomness.

Max-Min Ant System (MMAS) is another influential variant. Usually only the best ant updates pheromone, and pheromone values are clipped to stay within bounds:

These bounds matter because they stop pheromone from exploding on a handful of edges and driving total stagnation. MMAS often starts all edges at \(\tau_{max}\) so the initial search is unbiased.

Elitist Ant System gives extra reinforcement to the best-so-far ant when updating, explicitly increasing the pressure toward globally strong tours.

11 Convergence and the specter of stagnation

In practice, you often stop ACO after a fixed number of iterations, after no improvement for a while, or once the tour length plateaus. Another interesting stopping idea is stagnation: if all ants keep taking the same tour, the colony has effectively converged.

But stagnation is not always success. The colony can converge to a suboptimal tour if exploration died too early. That is why evaporation, bounded pheromone, local updates, and probabilistic choice remain so important. ACO is powerful because it remembers, but memory is dangerous when it becomes dogma.

12 ACO beyond TSP

TSP is the teaching star, but ACO becomes really interesting when you see how many real problems can be encoded as graph-construction tasks.

In vehicle routing, ants construct routes for fleets that must serve customers under capacity constraints. In job-shop scheduling, they construct sequences of operations across machines to minimise makespan. In network routing, ant-inspired protocols such as AntNet adaptively discover good paths through changing traffic conditions. Researchers have also used ACO ideas in telecommunications design, circuit layout, protein folding, and feature selection.

The common requirement is that the problem should be expressible as incremental construction on a graph or component set, where partial decisions can be reinforced and future construction can benefit from learned desirability.

13 ACO versus GA, hill climbing, simulated annealing, and exact methods

Against a GA, ACO usually has an advantage on permutation and path-construction problems like TSP because it works with the structure of the problem directly. A basic GA crossover can be blind or destructive on permutations unless specialised operators are used. ACO, by contrast, builds tours edge by edge and stores experience on those edges.

Against hill climbing, ACO has collective memory and population diversity. Hill climbing is cheap but memoryless and easy to trap locally. ACO uses many ants and a shared pheromone memory, so it can retain and reuse good structure across the colony.

Against simulated annealing, ACO is more population-based and usually more robust because many ants search simultaneously. SA is a single-solution search with a temperature schedule. It can be elegant and effective, but it has no explicit collective memory like pheromone.

Against exact methods such as dynamic programming or branch-and-bound, ACO gives up guarantees in exchange for scalability. For moderate or large instances where exact methods become intractable, ACO can deliver near-optimal tours quickly. That is often exactly what practitioners want.

14 Practical tuning instincts and the mistakes students usually make

The most useful tuning instinct is to ask, “Does my colony feel too forgetful, too greedy, or too stubborn?” Too forgetful means pheromone evaporates or is weighted too weakly. Too greedy means visibility or pheromone is dominating too hard. Too stubborn means early trails are freezing the colony. Those qualitative questions help more than memorising one magical parameter set.

15 What the second iteration looks like numerically

It is worth doing one more small numerical step because this is where many students finally feel ACO rather than just reciting it. After the first iteration in our example, edge \((4,2)\) has pheromone about 6.782, while unused edges like \((4,3)\) and \((4,5)\) sit near 0.9. Since \(\alpha=0.5\), the pheromone term contributes \(\sqrt{6.782}\approx 2.604\) on 4–2 and only \(\sqrt{0.9}\approx 0.949\) on unused edges.

Now multiply by the visibility terms again. From city 4 we get rough second-iteration weights:

• 4 \(\to\) 2: \(2.604 \times (1/2)^{0.75} \approx 2.604 \times 0.5946 \approx 1.548\)
• 4 \(\to\) 3: \(0.949 \times (1/4)^{0.75} \approx 0.949 \times 0.3536 \approx 0.336\)
• 4 \(\to\) 5: \(0.949 \times (1/5)^{0.75} \approx 0.949 \times 0.2991 \approx 0.284\)
• 4 \(\to\) 1: \(2.604 \times (1/7)^{0.75} \approx 2.604 \times 0.2324 \approx 0.605\)

The total is about 2.773, so the new probability of choosing city 2 jumps to about \(1.548/2.773 \approx 0.558\). That is a serious increase from the first iteration's roughly 0.402. In one iteration, the colony has already become much more confident that 4–2 is promising.

Also notice something subtle: edge 4–1 became more attractive too, even though it is long, because it participated in the first successful tour. So ACO is not merely “shortest local edge first.” It is “short local edges plus colony memory of what complete tours have worked.” That mix of local and global information is why the method is richer than a greedy nearest-neighbour heuristic.

16 ACS and MMAS, but this time in operational terms

Textbooks sometimes state ACS and MMAS like they are just variants to memorise, but it helps to understand what pain each one is trying to cure.

ACS is trying to reduce over-concentration inside an iteration. In plain Ant System, if a few edges start looking good, many ants may pile onto them immediately, making the search too herd-like. ACS introduces a local update while ants are still constructing tours. When an ant uses an edge, the pheromone on that edge is slightly reduced toward the baseline. The effect is counterintuitive but useful: it temporarily makes the edge less tempting to the next ant in the same iteration, which spreads the ants out more. Then, after all tours are built, a strong global update from the best ant reinforces the genuinely good tour.

ACS also uses the pseudo-random proportional rule. With probability \(q_0\), the ant picks the argmax edge greedily. Otherwise it samples according to the usual probability rule. This makes the algorithm mostly exploitative with occasional structured exploration. It is like telling the colony, “Usually trust your best guess, but sometimes gamble intelligently.”

MMAS, by contrast, is trying to cure stagnation over the longer horizon. If pheromone values are allowed to explode, one set of edges can become overwhelmingly dominant and exploration collapses. So MMAS imposes explicit bounds: no edge can fall below \(\tau_{min}\), and no edge can rise above \(\tau_{max}\). The lower bound preserves some chance of exploration. The upper bound stops one trail from becoming a dictatorship.

Once you see the variants this way, they become easier to remember. ACS = spread ants within the iteration and let the best tour lead globally. MMAS = bound pheromone to stop freeze-out and keep the colony from becoming fanatically certain too early.

17 How ACO maps onto real scheduling and routing problems

One reason ACO keeps showing up in engineering literature is that “construct a solution step by step on a graph” is a surprisingly flexible template.

In vehicle routing, an ant may build a route customer by customer, but unlike plain TSP it must also respect vehicle capacity and possibly time windows. That means the “allowed” set at each step is not just “unvisited cities,” but “unvisited cities that still satisfy capacity and schedule feasibility.” Pheromone then learns which route fragments tend to be useful under those constraints.

In job-shop scheduling, the nodes may represent operations, and an ant constructs an order in which jobs are assigned to machines. Visibility can encode shorter processing times or urgent deadlines. Pheromone can reinforce operation sequences that tend to reduce the final makespan. Here again, the power of ACO is not in a magical ant metaphor; it is in giving the search a way to accumulate experience over promising partial schedules.

In network routing systems such as AntNet, the ants are really control packets exploring the network. Their travel times reveal congestion. The pheromone-like values then bias data traffic and future control packets toward lower-latency paths. This is a beautiful example of the stigmergic idea escaping the classroom and entering a dynamic distributed system where conditions genuinely keep changing.

That is why ACO extends so naturally beyond TSP. The surface details change, but the construction-memory-feedback loop stays recognisable.

18 Why ACO often beats a naive GA on TSP-style problems

This comparison is worth stating sharply because it often appears in course discussions. A naive GA working on TSP usually has to solve two headaches at once: it must preserve permutation validity and it must somehow ensure crossover respects useful tour fragments. Standard one-point crossover is often disastrous. Even with repair, the algorithm can spend energy undoing invalid or structurally poor offspring.

ACO begins from a stronger fit to the problem. A tour is built city by city, so validity is easy: the tabu list blocks repeats. Experience is stored exactly where it matters, on edges. If edge \((i,j)\) tends to belong to good tours, pheromone on \((i,j)\) rises directly. That is a cleaner match between memory and structure than hoping a general-purpose crossover will preserve the same edge across two parent permutations.

This does not mean ACO always wins. A highly specialised permutation GA can be excellent. But basic GA versus basic ACO on TSP is often not a fair fight, because ACO's representation and feedback mechanisms line up with the problem much more naturally.

19 A practical checklist for solving exam-style ACO numericals

ACO exam questions often look intimidating because they mix symbols, probability, and tables, but the workflow is actually very mechanical once you know the order. If I had to reduce the whole numerical method to a checklist, it would be this.

1. Write down the parameters first — identify \(\alpha\), \(\beta\), \(\rho\), \(Q\), the starting node, and the initial pheromone \(\tau_0\).
2. Build or read the distance matrix carefully. If the TSP is symmetric, remember \(d_{ij}=d_{ji}\).
3. Compute visibility using \(\eta_{ij}=1/d_{ij}\). Many students skip this step mentally and then make arithmetic errors later.
4. At each city, restrict to the allowed set using the tabu list. Never include already visited cities in the denominator of the probability formula.
5. Compute unnormalised weights \((\tau_{ij})^{\alpha}(\eta_{ij})^{\beta}\) for each allowed move.
6. Normalise by dividing each weight by the sum of all allowed weights.
7. Select the next city — in worked solutions this is often the highest probability for illustration, even though the real algorithm is stochastic.
8. Complete the tour and compute its cost \(L_k\).
9. Evaporate old pheromone with \((1-\rho)\tau\).
10. Add deposits \(Q/L_k\) to the edges that were used.

That is really it. The algorithm feels more magical before you compute one example than after. Once you do a full tour by hand, ACO becomes an orderly bookkeeping process with a nice biological story wrapped around it.

There is also a strategic exam tip here. If the question gives equal initial pheromone everywhere, then during the first move the pheromone term contributes equally to all allowed edges. That means the first-step probabilities are determined entirely by visibility. Recognising shortcuts like that saves time.

20 What makes ACO feel “intelligent” instead of just random search

It is worth ending the conceptual arc of the chapter on this question because it ties back to Chapter 1. Why do we call this computational intelligence at all? Why is it more than just sampling random tours and hoping one is short?

First, ACO is adaptive. The search distribution changes over time based on experience. The colony after 50 iterations is not behaving like the colony at iteration 1. That is already one major CI property.

Second, it is robust under uncertainty. No ant needs full global certainty. Decisions are local and probabilistic, yet the colony accumulates meaningful global structure.

Third, it uses distributed parallel search. Many ants explore simultaneously, and the colony does not bet everything on one path too early unless the parameters force it to.

Fourth, it combines heuristic information and learned experience. Visibility is the immediate local clue. Pheromone is the slowly learned collective memory. That hybrid of prior heuristic knowledge plus adaptive reinforcement is exactly the kind of design CI does well.

Finally, ACO embodies the core CI lesson that complex global behaviour can emerge from simple local rules. No ant solves TSP in a symbolic theorem-proving sense. But the colony still becomes better over time at constructing short tours. That is why ACO deserves its place in computational intelligence: it is an adaptive mechanism enabling intelligent behavior in a complex environment — which is almost Chapter 1's definition coming back in algorithmic form.

That is also why ACO remains memorable long after the formulas fade. It is one of the clearest demonstrations that intelligence can arise from feedback, memory, and interaction rather than from a single central reasoner. In other words: Chapter 7 is not just an optimisation chapter. It is a compact case study in the whole CI worldview.

Why does a shorter tour deposit more pheromone?

Because the deposit is often \(Q/L_k\). When the tour length \(L_k\) is smaller, the deposited amount is larger. This creates positive feedback toward shorter tours.

What exactly does the tabu list do?

It records the cities already visited by an ant in the current tour. Without it, the ant could revisit cities before completing a valid TSP permutation.

Why is ACO especially strong for TSP-like problems?

Because the problem is naturally built step by step, edge desirability matters, and good partial decisions can be reinforced on those same edges. The representation and the search dynamic fit each other beautifully.

Is ACO better than GA for every optimisation problem?

No. ACO is especially natural for graph/path construction. For some continuous parameter problems, other methods such as DE, ES, or gradient-based optimisation may be more suitable.

• ACO is inspired by pheromone-based path discovery in ant colonies, especially the double-bridge effect.
• The core mechanism is stigmergy: indirect communication through the environment.
• Ant System uses pheromone \(\tau\), visibility \(\eta\), transition probabilities, evaporation, and pheromone deposition \(Q/L\).
• Parameters \(\alpha\), \(\beta\), \(\rho\), and the number of ants govern the exploration–exploitation balance.
• ACO is strongest when the problem can be expressed as incremental path construction on a weighted graph.