Particle Swarm and Ant Colony Optimization

A single ant is nearly mindless. It has poor eyesight, no map, no plan, and no conception of the colony's goal. Yet a colony reliably discovers the shortest route to a food source, and does so without any ant ever comparing two routes. A flock of starlings turns as one without a leader. This is swarm intelligence: complex, apparently purposeful global behaviour emerging from simple local rules, applied by many individuals, with no central control.

For an optimizer the appeal is obvious. If a colony can solve a shortest-path problem it cannot even perceive, using rules simple enough to write in three lines, then those rules are worth stealing. Two mechanisms do the work, and the distinction between them is exactly the distinction between the two algorithms in this chapter.

Stigmergy — coined by Grassé in 1959 for termite mound-building — deserves the emphasis, because it is the more radical idea. The ants never communicate with one another at all. They communicate with the ground, and the ground remembers. Information persists after its author has gone, accumulates when many agree, and fades when unreinforced. That is a shared memory external to every individual, and it is a genuinely different way to build an algorithm.

Both methods are population-based, so both inherit the strengths Chapter 23 attributed to that class: many regions sampled at once, trivial parallelism, robustness to ruggedness. But note what they do not inherit from Chapter 24. Neither method has crossover; neither kills anyone. A GA's population is a gene pool that turns over every generation. A swarm's population is a fixed cast of individuals that persist for the whole run and merely change what they know.

Kennedy and Eberhart introduced PSO in 1995 after trying to simulate a flock of birds and noticing that the simulation, pointed at an objective function, optimised it. A swarm of \(N\) particles flies through \(\mathbb{R}^n\). Particle \(i\) carries three things: where it is, how fast it is going, and the best place it has personally ever been.

Each iteration, every particle updates its velocity from three influences and then moves. These two lines are the entire algorithm:

The full procedure is then short enough to state completely:

Compare this to a genetic algorithm and the economy is striking. There is no encoding — a particle is the design vector, in the units the engineer already uses. There is no selection, no crossover, no mutation, and nothing dies. The whole method is a difference equation, which is also why PSO has been analysed far more successfully than most metaheuristics: it is a linear dynamical system with stochastic coefficients, and its stability can be studied directly.

The velocity update earns its behaviour from the tension between its three terms. Read each as a separate opinion about where the particle should go, with the sum a compromise.

The cognitive and social terms are literally spring forces: each pulls the particle toward an attractor with a strength proportional to the distance, so a particle far from \(\mathbf{g}\) is yanked hard while one already there feels nothing. Without inertia the particle would be over-damped and simply slide to a point between \(\mathbf{p}_i\) and \(\mathbf{g}\). Inertia makes it overshoot — and overshoot is what lets the swarm explore past its own best guesses instead of collapsing onto them. A particle that always stopped exactly where the springs balanced would learn nothing new.

PSO has few parameters, and each is a direct handle on the exploration–exploitation dial of Section 23-4.

The inertia schedule is the workhorse. Shi and Eberhart's linear rule, \(w_k = w_{\max} - (w_{\max}-w_{\min})\,k/K\), starts the swarm loose and wide and finishes it tight and local — the exploration-to-exploitation slide made into arithmetic, exactly as the cooling schedule does for simulated annealing in Chapter 26.

The alternative is Clerc and Kennedy's constriction factor, which arrives at damping by analysis rather than by schedule. Treat the particle as a linear system and ask what keeps it stable; the answer is to multiply the whole velocity by a factor \(\chi\):

The canonical choice \(\varphi = 4.1\) gives \(\chi = 0.7298\), and the method then needs no velocity clamp at all — convergence is guaranteed by the algebra rather than enforced by a cap. It is also, as Example 2 shows, algebraically identical to the inertia form with \(w = 0.7298\) and \(c_1 = c_2 = 1.4962\). The two "competing" formulations are the same equation.

The other design choice is topology: who counts as "the swarm" in the social term. Using the true global best (\(gbest\)) makes every particle a neighbour of every other; using a ring in which each particle sees only two neighbours (\(lbest\)) lets good news travel slowly, so different parts of the swarm can explore different basins for a while.

That framing explains PSO's characteristic failure. Suppose the swarm converges: every particle sits on \(\mathbf{g}\), so \(\mathbf{p}_i = \mathbf{g} = \mathbf{x}_i\) and both spring terms vanish identically. The update degenerates to \(\mathbf{v}_i^{k+1} = w\mathbf{v}_i^{k}\) — a geometric decay to zero for any \(w < 1\). The swarm freezes, permanently, wherever it happens to be, whether or not that place is any good.

The experiment that founded ACO is worth describing exactly, because the algorithm is a direct transcription of it. Goss and colleagues connected an Argentine ant nest to a food source by two bridges, one twice as long as the other, and watched. Ants leaving the nest initially chose at random — they cannot see the food and have no way to measure a bridge. Within minutes, almost the entire colony was using the short bridge.

No ant compared the two. The mechanism is entirely mechanical: ants lay pheromone as they walk, and ants prefer paths with more pheromone. An ant taking the short bridge reaches the food and returns sooner, so its trail is laid down twice while a long-bridge ant is still travelling. The short bridge therefore accumulates pheromone faster; the higher concentration attracts more ants; more ants lay more pheromone. It is autocatalysis — a positive feedback loop in which the difference in trip time is amplified into a difference in choice.

Both halves of that last sentence matter. Feedback without forgetting locks in whatever the first few ants did — and in the real experiment, if the short bridge is added only after the colony has committed to the long one, the ants never switch, because their pheromone does not evaporate fast enough. Artificial ants, unbound by chemistry, are given an evaporation rate we control. Evaporation is not a modelling detail; it is the exploration mechanism, and Example 6 measures exactly how long the colony's memory lasts.

Dorigo's Ant System (1992) turns the bridge into an algorithm. Take the TSP as the standard vehicle. Each edge \((i,j)\) of the city graph carries a pheromone level \(\tau_{ij}\), which the colony writes, and a visibility \(\eta_{ij} = 1/d_{ij}\), which the problem provides and never changes. Each ant builds a complete tour by walking the graph, choosing its next city probabilistically from those it has not yet visited.

The two exponents deserve to be read as a dial of their own. Set \(\alpha = 0\) and pheromone is ignored — the ants become a randomised nearest-neighbour heuristic that learns nothing. Set \(\beta = 0\) and distance is ignored — the colony learns from experience alone, converging slowly and often badly. Typical settings \(\alpha = 1\), \(\beta \in [2,5]\) say something quietly important: trust the problem's own structure more than your accumulated opinion, at least at first.

Once every ant has completed a tour, the colony writes to the environment. This happens in two steps, and their order matters: everything evaporates, then the ants deposit in proportion to how good their tours were.

Here \(L_k\) is the length of ant \(k\)'s tour, \(Q\) a constant, and \(\rho \in (0,1]\) the evaporation rate. The deposit \(Q/L_k\) is the mechanism that replaces the real ants' round-trip timing: a shorter tour is a larger deposit, so good solutions shout louder — and an edge on many good tours gets reinforced many times over. Meanwhile \((1-\rho)\) applies to every edge, including those no ant chose, so unused edges fade geometrically toward irrelevance and old mistakes are forgotten.

The full loop is therefore: initialise all \(\tau_{ij}\) to a small constant \(\tau_0\); let \(m\) ants each construct a tour by the transition rule; evaporate; deposit; record the best tour seen; repeat. Note that ACO fills the generic framework of Section 23-7 in an unusual way — its "generate" step constructs solutions from nothing each iteration rather than perturbing existing ones, and its memory lives entirely in \(\boldsymbol{\tau}\).

Plain Ant System is rarely competitive today; it is the ancestor everything else refines. Each descendant attacks the same weakness — too little intensification, or too much.

MMAS is the most instructive. Its bounds are a direct admission of ACO's characteristic failure mode, the exact mirror of PSO's: runaway positive feedback drives \(\tau\) on one tour's edges so high that every other edge's transition probability rounds to zero, and the colony can never construct anything different again. Clamping \(\tau\) below by \(\tau_{\min}\) guarantees a floor on the probability of every edge forever — exploration by fiat.

With three population methods now on the table, the comparison that matters is which to reach for.

Notice how the last two rows rhyme. All three methods die of the same disease — the population agrees with itself and stops generating anything new — and all three treatments (mutation, inertia, evaporation) are devices for manufacturing disagreement. That is the through-line of Part 6: a population method's real parameter is how vigorously it resists its own consensus.

For the PSO problems, always build the three terms separately before summing. For the ACO problems, compute \(\tau^{\alpha}\eta^{\beta}\) for every candidate before normalising. Difficulty rises down the list.