The idea: many searchers that share what they find

Particle swarm optimization (PSO) looks for the lowest point of a function f(x, y) with a swarm of simple searchers called particles. Each particle has a position x and a velocity v. It remembers the best point it has seen itself, its personal best p. The swarm shares one global best g, the best point any particle has seen. PSO needs only the values of f, no gradient, so it works on bumpy or noisy functions too. It was proposed by Kennedy and Eberhart in 1995, after models of birds flocking.

Vector diagram: from the particle at x, a grey arrow w·v, then a blue arrow c1·r1·(p − x) towards its personal best p, then a green arrow c2·r2·(g − x) towards the global best g. A black arrow from x to the end of the green arrow is the new velocity; the particle moves there next.
The new velocity is the sum of three arrows: keep going, go back towards your own best, go towards the swarm's best.

The canvas has 8 particles on the square 0 … 10 × 0 … 10. The map has three valleys: the global minimum f = 2.24 at (6.97, 3.03), a local minimum f = 3.87 at (2.55, 7.45) and a shallow local minimum f = 6.12 at (7.95, 8.44). Darker cells are higher.

The velocity update

In every iteration each particle updates its velocity, one axis at a time, and then moves:

v ← w·v + c1·r1·(p − x) + c2·r2·(g − x)
x ← x + v
  • w·v is the inertia: the particle keeps part of its old velocity. The inertia weight w is 0.7 by default.
  • c1·r1·(p − x) is the personal (cognitive) pull back towards its own best point.
  • c2·r2·(g − x) is the social pull towards the swarm's best point.
  • r1 and r2 are fresh random numbers in [0, 1) for every particle, axis and iteration. They make each step a little different, so the swarm does not move in lock step.

After all particles have moved, each one compares f at its new place with f(p) and keeps the better one; then g becomes the best of all p. Each velocity component is capped at ±1.5 (a common safety limit called vmax), and a particle that hits the edge stops on that axis. (Demo 1: one iteration up close draws the three arrows for particle 1 in iteration 4: w·v = (0.06, 0.92), personal pull (−0.12, −0.62), social pull (−0.23, −1.11), new v = (−0.29, −0.80), so particle 1 moves from (7.04, 3.89) to (6.75, 3.09). The arrows on the map are drawn 3× longer than the real step.)

The page's settings are the usual textbook ones: w between 0.4 and 0.9, c1 = c2 = 1.5 (values near 1.5–2 are common).

Convergence: the swarm closes in

At first the particles are spread over the map, and g jumps whenever someone finds a lower point. As the social pull draws everyone towards g and the inertia dies down, the particles circle around g in smaller and smaller loops. The spread, the mean distance of the particles to g, is plotted for every iteration. (Demo 2: the swarm converges on the global minimum: seed 148, w = 0.7; after 30 iterations g = (6.97, 3.02), f = 2.236, and the spread has fallen from 3.91 to 0.12.)

The inertia weight w

w decides how long a particle keeps flying before the pulls take over. High w means more exploration (looking at new places); low w means more exploitation (refining the best place known so far).

Spread against iteration for seed 148 with w = 1.0, 0.7 and 0.4. All start at 3.91. With w = 1.0 the spread stays near 1. With w = 0.7 it falls to 0.12 on the global minimum. With w = 0.4 it falls to 0.00 by iteration 21, on the local minimum.
Same start, only w changes: 1.0 never settles, 0.7 settles on the global minimum, 0.4 settles fast on the wrong valley.
w (seed 148)g after 30 iterationsspreadwhat happened
1.0global min, f = 2.2461.06nothing damps v; the particles keep overshooting g (Demo 3)
0.7global min, f = 2.2360.12explores first, then settles (Demo 2)
0.4local min, f = 3.8680.00the swarm collapses before anyone finds the deep valley (Demo 4)

Many programs start with w ≈ 0.9 and lower it to 0.4 during the run: explore early, refine late. Another common choice, the constriction factor of Clerc and Kennedy, is the same as w ≈ 0.73 with c1 = c2 ≈ 1.5.

Getting stuck in a local minimum

PSO gives no guarantee. If the first good point a particle finds lies in a local valley, g sits there, and the social pull drags every particle into the same valley. Once the spread is near 0, nobody looks elsewhere, and the swarm stays there for good. This is called premature convergence. (Demo 5: stuck in a local minimum: seed 4 ends with g = (2.53, 7.45), f = 3.868, spread 0.07.)

A stronger personal pull helps: each particle keeps circling its own best point, so the swarm stays spread out longer. (Demo 6: more personal pull escapes the trap: the same seed 4 with c1 = 2.5, c2 = 0.5 finds the global minimum, f = 2.236, and is still spread out, 3.05.) Over seeds 1–100 on this map (30 iterations, w = 0.7), the swarm ends in the global valley 78 times with c1 = c2 = 1.5, 87 times with c1 = 2.5, c2 = 0.5, and 76 times with c1 = 0.5, c2 = 2.5. The price of a strong personal pull is a swarm that settles slowly.

PSO next to the other search methods

MethodWhat it keepsHow it moves
Gradient descentone pointdownhill along −∇f; needs the gradient
Simulated annealingone pointrandom neighbour, a worse move is sometimes taken
Genetic algorithma populationselection, crossover and mutation make a new generation
Particle swarma population with memory (p and g)each particle flies, pulled by its own best and the swarm's best

Like a genetic algorithm, PSO uses a population, but nobody is replaced: the same particles fly all the time, and the only shared information is g.

See also Ant Colony Optimization, another swarm method, where the shared memory is pheromone on the edges of a graph instead of a global best point.

See also Boids: Steering Behaviours and Flocking, where each bird follows only its neighbours, with no shared best point.

What the page leaves out

Real uses have many dimensions (tens to thousands of weights or design parameters) and larger swarms (20–50 particles). The page shows the global-best ("gbest") version; the local-best version, where each particle only listens to a few neighbours (a ring topology), spreads news more slowly and gets stuck less often. Also left out: inertia that drops during the run, the constriction factor in its exact form, asynchronous updates, restarts when the swarm stalls, binary and discrete PSO, and the theory of when the swarm is stable.

On the mind map

This page on the AI: Search, Games & Reasoning mind map · 23 pages in 7 branches · open it to see the whole map and test yourself in recall mode.