Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 36 ยท Swarm and Other Metaheuristics

Particle Swarm Optimization

Learn how particle swarm optimization works: velocity, inertia, personal and global best. Build PSO in NumPy, tune its parameters and compare it with a genetic algorithm.

A genetic algorithm borrows from evolution: selection, crossover and mutation. Particle swarm optimization (PSO) borrows from flocking birds and schools of fish. There is no crossover and no selection. Instead, a swarm of particles flies through the search space, and each particle is pulled toward two places: the best spot it has ever seen, and the best spot anyone in the swarm has seen.

PSO was proposed in 1995. It is short to implement, has few parameters, and is a very good first choice for continuous problems such as tuning numeric parameters.

The idea

Every particle has a position x (a candidate solution) and a velocity v (how it moves). In each iteration, three forces shape the new velocity:

  1. Inertia: keep going the way you were going.
  2. Cognitive pull: go back toward your own best position pbest.
  3. Social pull: go toward the best position found by the swarm, gbest.
TEXT
v = w * v + c1 * r1 * (pbest - x) + c2 * r2 * (gbest - x)
x = x + v
  • w is the inertia weight (typically 0.4 to 0.9).
  • c1 and c2 are the acceleration coefficients (often both about 1.5 to 2).
  • r1, r2 are fresh random numbers in [0, 1) for each dimension.

After moving, evaluate the particle. If it beat its own best, update pbest. If it beat the swarm's best, update gbest.

flowchart LR
    X["Current position x"] --> N["New velocity"]
    I["Inertia w*v"] --> N
    C["Cognitive c1*r1*(pbest - x)"] --> N
    S["Social c2*r2*(gbest - x)"] --> N
    N --> M["x = x + v"]
    M --> E["Evaluate, update pbest / gbest"]

Three influences are mixed into the new velocity every iteration.

A test function: Rastrigin

We need a problem with many local minima. Rastrigin is the classic: a bowl covered with regular bumps. Its global minimum is 0 at the origin.

TEXT
f(x) = 10 * n + sum(x_i ** 2 - 10 * cos(2 * pi * x_i))
Python PSO from scratch on the Rastrigin function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tuning the three coefficients

The coefficients control the balance between exploring and exploiting.

Setting Effect
Large w (0.9) Particles overshoot, wide exploration
Small w (0.4) Quick settling, risk of premature convergence
Large c1 Particles trust their own memory: diverse swarm
Large c2 Particles rush to the leader: fast but can trap the swarm

A popular trick is to decrease w linearly from 0.9 to 0.4 over the run: explore first, refine later. Another is the constriction factor version of Clerc and Kennedy, which uses c1 = c2 = 2.05 and multiplies the whole velocity by chi = 0.7298, a setting that is mathematically stable.

Python Effect of inertia weight, averaged over 10 seeds

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Averaging over several seeds is important. A single run of any stochastic optimizer proves nothing.

Topologies: who is in your neighbourhood?

So far every particle follows the single global best (the gbest topology). It is fast, but the whole swarm can be fooled by one lucky early point. The alternative is the lbest topology: each particle only sees a small neighbourhood (for example the ring of 2 neighbours on each side) and follows the best of those. Information then spreads slowly through the swarm, which keeps diversity high and helps on multimodal problems.

PSO versus a genetic algorithm

PSO GA
Natural encoding Real vectors Bits, reals, permutations, trees
Operators Velocity update Selection, crossover, mutation
Memory Each particle remembers its best None (the population is the memory)
Parameters w, c1, c2, swarm size Rates, selection, population size
Discrete problems Needs special variants Natural

PSO is typically the quicker route for smooth continuous functions, while GAs shine for combinatorial structure.

Common mistakes

  • No velocity clamp or bounds handling. Particles can fly out of the valid range and explode.
  • Reusing one random number for all dimensions. Draw r1, r2 per dimension, as in the code above.
  • Too small a swarm. Ten particles on a 30-dimension problem rarely work: start with 30 to 50.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which three terms make up a particle's new velocity in basic PSO?

    v = wv + c1r1*(pbest - x) + c2r2(gbest - x).
  2. 2. What is the main effect of a large inertia weight w?

    A large w keeps old velocity, so particles overshoot and explore.
  3. 3. Why use an lbest (ring) topology instead of gbest?

    Local neighbourhoods slow down premature convergence.
  4. 4. Why average results over several random seeds?

    Reliable comparisons need many runs.

Summary

  • PSO moves particles using inertia plus pulls toward their own best and the swarm's best.
  • It is simple, has few parameters and excels at continuous optimization.
  • A decreasing inertia weight (0.9 to 0.4) balances exploration and exploitation.
  • The topology (gbest or lbest) controls how fast information spreads.
  • Clamp velocities, respect bounds and compare over many seeds.

Next: Differential Evolution