No single ant knows the shortest route to food, yet the colony finds it. No single starling directs the flock, yet it moves as one. Swarm intelligence studies how collective intelligence emerges from many simple agents following local rules. From this, AI researchers derived powerful optimisation algorithms that are simple to implement and embarrassingly parallel.
Principles of swarm systems#
Swarm systems share a few properties:
- Decentralisation — no central controller.
- Local interaction — agents sense only neighbours or their immediate environment.
- Stigmergy — indirect communication by modifying the environment (e.g. ants leaving pheromone).
- Positive and negative feedback — good solutions are reinforced; evaporation or inertia prevents lock-in.
- Emergence — global patterns arise that no individual intends.
Craig Reynolds' Boids (1987) showed that three rules — separation, alignment and cohesion — produce realistic flocking animation. It has been used in films and games ever since.
Particle Swarm Optimisation (PSO)#
Kennedy and Eberhart (1995) introduced PSO to optimise continuous functions. Each particle $i$ has a position $\mathbf{x}_i$ (a candidate solution) and velocity $\mathbf{v}_i$. It remembers its personal best $\mathbf{p}_i$, and the swarm knows the global best $\mathbf{g}$. At each step:
where $r_1, r_2 \sim U(0,1)$ are random, $w$ is the inertia weight, $c_1$ the cognitive coefficient (trust in self) and $c_2$ the social coefficient (trust in the swarm). Typical values: $w \approx 0.7$, $c_1 = c_2 \approx 1.5$.
import numpy as np
def rastrigin(x): # many local minima; global min 0 at the origin
return 10 * x.shape[-1] + (x**2 - 10 * np.cos(2 * np.pi * x)).sum(axis=-1)
def pso(f, dim=5, n=40, iters=300, w=0.72, c1=1.49, c2=1.49, bound=5.12, seed=0):
rng = np.random.default_rng(seed)
x = rng.uniform(-bound, bound, (n, dim))
v = rng.uniform(-1, 1, (n, dim))
pbest, pval = x.copy(), f(x)
g = pbest[pval.argmin()].copy()
for _ in range(iters):
r1, r2 = rng.random((n, dim)), rng.random((n, dim))
v = w * v + c1 * r1 * (pbest - x) + c2 * r2 * (g - x)
x = np.clip(x + v, -bound, bound)
val = f(x)
better = val < pval
pbest[better], pval[better] = x[better], val[better]
g = pbest[pval.argmin()].copy()
return g, pval.min()
best, value = pso(rastrigin)
print(best.round(3), round(value, 4))Ant Colony Optimisation (ACO)#
Marco Dorigo's ACO (1992) mimics how ants find short paths. Ants deposit pheromone as they walk; shorter paths are completed faster and more often, so they accumulate more pheromone, attracting more ants — positive feedback. Pheromone evaporates, preventing the colony from locking into early choices.
For the travelling salesperson problem, ant $k$ at city $i$ chooses the next city $j$ with probability
where $\tau_{ij}$ is the pheromone on edge $(i,j)$, $\eta_{ij} = 1/d_{ij}$ is the heuristic desirability, and $\alpha, \beta$ weight the two. After all ants finish their tours, pheromone updates as
with evaporation rate $\rho$ and tour length $L_k$.
ACO works especially well on dynamic graph problems — for example routing in communication networks where link costs change, because the pheromone trail continuously adapts.
Other swarm algorithms#
- Artificial Bee Colony — employed, onlooker and scout bees balance exploitation and exploration.
- Firefly algorithm — attractiveness decays with distance.
- Swarm robotics — many simple robots cooperate for search-and-rescue, mapping or agriculture, relying on local communication for robustness.