Particle Swarm Optimization

"I found a good spot. The swarm found a better one. So I pointed myself somewhere between the two and trusted the crowd to be only half wrong."

A Particle Splitting the Difference

The previous section put ants on a graph and let pheromone trails solve discrete routing problems. Continuous optimization asks a different question: given a real-valued objective $f(\mathbf{x})$ over a vector $\mathbf{x} \in \mathbb{R}^d$, find the input that minimizes it. When $f$ is smooth and you can differentiate it, gradient descent is the right tool and most of Part IV is about scaling it across machines. But many objectives are black boxes: a physics simulation, a wind-tunnel surrogate, the validation accuracy of a trained model as a function of its hyperparameters. You can evaluate them, sometimes at considerable cost, but you cannot differentiate them, and they may be riddled with local minima. Particle swarm optimization (PSO), introduced by Kennedy and Eberhart in 1995, attacks exactly this regime with a swarm of candidate solutions that explore the space together.

1. The Swarm as a Search Population Beginner

A particle swarm is a fixed population of $n$ candidate solutions, each a point $\mathbf{x}_i \in \mathbb{R}^d$ in the search space together with a velocity $\mathbf{v}_i \in \mathbb{R}^d$. You can picture each particle as a tiny agent flying over the landscape of the objective function, its height at any moment given by $f(\mathbf{x}_i)$. The swarm's job is to drive as many particles as possible down to the lowest valley. Two pieces of memory make this work. Each particle remembers $\mathbf{p}_i$, the best position it personally has visited (the one with the smallest objective value it has ever recorded). The swarm as a whole tracks $\mathbf{g}$, the best position any particle has visited. These are the only states a particle needs beyond its current position and velocity.

What makes PSO a member of the swarm-intelligence family, alongside the ant colonies of the previous section and the flocks of the next, is that the global behavior is not programmed anywhere. Each particle follows a fixed, local rule, and the convergence of the population onto good optima is emergent. There is no master that decides where the swarm should look next; there is only a shared scalar-and-vector summary, $\mathbf{g}$, that every particle reads and that any particle can improve. The contrast with a centralized optimizer is the same contrast this part of the book keeps returning to, and it is exactly what lets the method scale.

2. The Velocity and Position Update Intermediate

At each iteration, every particle updates its velocity and then its position. The velocity update is the heart of the method, and it is a weighted sum of the three pulls drawn in Figure 31.4.1. For particle $i$ at iteration $t$,

followed by the position update

Here $\mathbf{r}_1$ and $\mathbf{r}_2$ are vectors of independent uniform random numbers in $[0,1]$, drawn fresh each step, and $\odot$ is the elementwise product. The randomness is essential: it keeps the swarm from collapsing into a single deterministic trajectory and lets particles overshoot, undershoot, and probe around the two attractors rather than marching straight at them. Each of the three terms has a clear job. The inertia term $w\,\mathbf{v}_i^{\,t}$ carries the particle's momentum forward, so it keeps exploring in its current direction rather than snapping instantly to an attractor. The cognitive term pulls the particle back toward its own best discovery $\mathbf{p}_i$, the "nostalgia" that keeps it loyal to good places it has personally seen. The social term pulls it toward the swarm's best $\mathbf{g}$, the conformity that lets one particle's lucky find recruit the whole population.

3. Global Best Versus Local Best Intermediate

The social term hides a design decision: what does "the swarm's best" mean to a given particle? In the global-best (gbest) variant, every particle is connected to every other, so $\mathbf{g}$ is the single best position in the entire swarm and all particles feel the same social pull. This is fast: one good discovery propagates to the whole population in a single iteration. It is also the variant most prone to premature convergence, because if that one best position sits in a deep but suboptimal local minimum, the entire swarm dives in after it and may never escape.

The local-best (lbest) variant gives each particle a neighborhood instead of the whole swarm. A particle's social attractor is the best position among only its neighbors on some fixed communication graph, the classic choice being a ring in which each particle talks to two others. Now a good discovery spreads slowly, hopping neighbor to neighbor around the ring rather than broadcasting instantly. The swarm explores more independent regions in parallel, which makes it slower to converge but markedly more robust against being trapped: a subgroup stuck in a bad basin does not immediately drag the rest in with it. This is the same idea, expressed on a population of optimizers, that Section 29.9 develops as the communication-graph topology of a multi-agent system, where the connectivity of the agent graph trades speed of consensus against resistance to a bad signal propagating too quickly. The neighborhood graph is the swarm's communication topology, and choosing it is choosing how fast information, good or bad, travels.

4. Why PSO Is Embarrassingly Parallel Intermediate

Here is where PSO earns its place in a book about scaling out. Within one iteration, the expensive operation is evaluating the objective $f(\mathbf{x}_i)$ at each of the $n$ particles, and those evaluations are completely independent: particle $i$'s objective value does not depend on particle $j$'s. If $f$ is a black box that takes seconds or minutes to evaluate, a wind-tunnel surrogate or a full model-training run, you can scatter the $n$ particles across $n$ workers, evaluate them all at once, and the per-iteration wall-clock collapses from $n$ sequential evaluations to one. This is the textbook definition of an embarrassingly parallel workload, and it is the dominant cost whenever the objective is expensive.

The only information that must cross the network is the best position. After the workers report their objective values, the swarm needs to know the single best (gbest) or each neighborhood's best (lbest) so that every particle can apply its social pull next iteration. Finding the global minimum over $n$ scalar values and broadcasting the winning position is a reduction followed by a broadcast: precisely the all-reduce primitive built from scratch in Section 4.3, except that the reduced payload is a single $d$-dimensional vector and one scalar, kilobytes rather than the gigabyte gradient buffers of distributed training. The communication-to-computation ratio is therefore tiny: heavy independent compute, a featherweight collective. That is the ideal shape for scale-out, and it is why PSO parallelizes so naturally for exactly the expensive black-box objectives where you most need the speed.

5. A Swarm That Converges, From Scratch Intermediate

The code below implements both variants on the Rastrigin function, a standard optimization torture test whose surface is a smooth bowl studded with a regular grid of local minima, with the global minimum of $0$ at the origin. A method that only does local descent gets stuck in the nearest ripple; a working swarm has to use its exploration to hop across the ripples toward the center. The implementation is plain NumPy: positions, velocities, the three-term velocity update, and the two topologies (a single shared best for gbest, a three-particle ring neighborhood for lbest).

import numpy as np

def rastrigin(P):
    # P: (n_particles, d). Global minimum 0 at the origin.
    A = 10.0
    return A * P.shape[1] + np.sum(P**2 - A * np.cos(2 * np.pi * P), axis=1)

def run_pso(topology, n=40, d=2, iters=60, seed=0):
    rng = np.random.default_rng(seed)
    w, c1, c2 = 0.72, 1.49, 1.49          # inertia, cognitive, social coefficients
    lo, hi = -5.12, 5.12                   # Rastrigin search box per dimension
    X = rng.uniform(lo, hi, (n, d))        # particle positions
    V = rng.uniform(-1, 1, (n, d))         # particle velocities
    Pbest = X.copy()                       # each particle's own best position
    Pbest_val = rastrigin(X)
    history = []
    for _ in range(iters):
        if topology == "gbest":            # fully connected: one shared best
            g = Pbest[np.argmin(Pbest_val)]
            G = np.broadcast_to(g, X.shape)
        else:                              # lbest ring: best among the 2 ring neighbours
            order = np.argsort(Pbest_val)
            G = np.empty_like(X)
            for i in range(n):
                nb = [(i - 1) % n, i, (i + 1) % n]
                G[i] = Pbest[nb[int(np.argmin(Pbest_val[nb]))]]
        r1, r2 = rng.random((n, d)), rng.random((n, d))
        V = w * V + c1 * r1 * (Pbest - X) + c2 * r2 * (G - X)   # velocity update
        X = np.clip(X + V, lo, hi)                              # position update
        val = rastrigin(X)
        improved = val < Pbest_val
        Pbest[improved], Pbest_val[improved] = X[improved], val[improved]
        history.append(Pbest_val.min())
    return Pbest[np.argmin(Pbest_val)], Pbest_val.min(), history

for topo in ("gbest", "lbest"):
    best_x, best_f, hist = run_pso(topo)
    print(f"{topo:6s}  best f = {best_f:.6e}   at ({best_x[0]:+.4f}, {best_x[1]:+.4f})")
    print(f"        best-so-far at iter 0 / 10 / 30 / 59 : "
          f"{hist[0]:7.3f} {hist[10]:7.3f} {hist[30]:7.4f} {hist[59]:.2e}")

gbest   best f = 5.907045e-05   at (+0.0005, -0.0002)
        best-so-far at iter 0 / 10 / 30 / 59 :   6.363   1.052  0.0181 5.91e-05
lbest   best f = 3.079467e-03   at (+0.0013, +0.0037)
        best-so-far at iter 0 / 10 / 30 / 59 :   9.480   1.470  0.0682 3.08e-03

The numbers tell the gbest-versus-lbest story cleanly. Both topologies escape the Rastrigin ripples and home in on the origin, the global optimum, so both work. But gbest reaches a far smaller objective at iteration 59 because its instant broadcast of the best position lets the whole swarm pile onto the most promising spot early. The lbest swarm is one to two orders of magnitude behind at the same iteration count, the visible price of letting good news travel only neighbor to neighbor; the compensating benefit, harder to see on a single friendly seed but real across many runs and harder problems, is that the slower spread makes lbest much less likely to commit the whole swarm to a wrong basin. On a problem with one dominant deceptive minimum, the rankings can reverse, which is exactly why the topology is a knob and not a default.

6. PSO Against Gradients, and Where It Is Used Advanced

It is worth being precise about when to reach for a swarm and when not to. PSO is derivative-free: it never needs $\nabla f$, only the ability to evaluate $f$. That is its whole reason for existing and its main weakness inverted. When you do have a cheap, reliable gradient, gradient-based optimization is dramatically more sample-efficient, converges with provable rates, and should be your default; throwing a swarm at a smooth convex problem is wasteful. PSO earns its keep precisely where gradients are unavailable or unhelpful: black-box objectives you can only query, non-differentiable or discontinuous objectives, noisy simulations, and rugged multi-modal landscapes where a gradient would just slide you into the nearest local pit. In those regimes its population-based exploration is a genuine advantage rather than a crutch.

The most common place a reader of this book will meet PSO is hyperparameter optimization. Validation performance as a function of learning rate, weight decay, and architecture choices is a black box with no gradient and many local optima, and each evaluation is a full training run, expensive and independent. That is the PSO sweet spot, and population-based search sits alongside random search, Bayesian optimization, and evolutionary methods in the distributed HPO toolkit that Chapter 21 builds out, where the parallel evaluation of a population across a cluster is the central engineering concern. Beyond HPO, PSO and its relatives are workhorses of engineering design optimization: antenna and circuit layout, structural and aerodynamic shape design, controller tuning, and power-system scheduling, wherever a simulator scores a continuous design vector and no gradient is on offer.

# pip install pyswarms
import numpy as np
import pyswarms as ps

def rastrigin(P):                                  # P: (n_particles, d), vectorized
    return 10*P.shape[1] + np.sum(P**2 - 10*np.cos(2*np.pi*P), axis=1)

opts = {"w": 0.72, "c1": 1.49, "c2": 1.49}
opt = ps.single.GlobalBestPSO(n_particles=40, dimensions=2, options=opts)
best_cost, best_pos = opt.optimize(rastrigin, iters=60)   # swap for LocalBestPSO for lbest

7. Strengths, Weaknesses, and Honest Limits Intermediate

PSO's strengths are real and explain its popularity. It is simple to implement and to explain, it has very few parameters to set, it makes no assumptions about the objective beyond being able to evaluate it, and its parallel structure matches expensive black-box problems beautifully. Those four properties, simplicity, few knobs, generality, and parallelism, are why it shows up across engineering disciplines that have no interest in optimization theory for its own sake.

The weaknesses are equally real and must be stated plainly. PSO is a heuristic: it offers no guarantee of finding the global optimum and no convergence-rate bound of the kind gradient methods enjoy on well-behaved problems. It can stagnate, the swarm collapsing onto a suboptimal point with all velocities near zero and no mechanism to reignite exploration, which is the failure mode of overly social settings. Its performance is sensitive to the coefficients and the population size, so the method that has "few parameters" still requires some tuning to work well on a hard problem. And on high-dimensional problems the population needed to cover the space grows uncomfortably, so PSO is most at home in low to moderate dimensions. None of this disqualifies it; it means you use a swarm where its assumptions fit (expensive, non-differentiable, low-to-moderate-dimensional black boxes) and reach for gradients or Bayesian optimization where theirs fit better. The collective failure modes of swarms in general, stagnation among them, get their own dedicated treatment later in this chapter.

You now have the continuous-optimization member of the swarm-intelligence family: a population of particles, a three-term velocity rule, two coefficients that trade exploration against exploitation plus an inertia that paces the search, a topology choice that trades convergence speed against robustness, and a parallel structure that reduces communication to a single best-position vector. The next section keeps the swarm but drops the objective function entirely: in flocking and distributed consensus, the agents have no global goal to optimize, only local rules of attraction, alignment, and separation, and we ask what coherent collective motion emerges and when the flock can be said to agree. That story begins in Section 31.5.