Swarm Intelligence & PSO

Source: Unit 5 §9

What a swarm is

A swarm is a loosely structured collection of interacting agents that exhibits collective behaviour. Agents belong to a group, contribute to it and benefit from it, and can recognise, communicate with and interact with one another.

Swarm intelligence is an AI technique based on decentralised, self-organised systems: robust, reliable, simple, with no central control, and copied from nature. The standard examples are a bee swarm, an ant colony, a bird flock, road traffic, human crowds and the immune system.

≡FactsWhy insects are the stock example

A single ant acts almost randomly, often to its own destruction, yet the colony feeds and protects the whole population (E. O. Wilson, 1950s). That gap between agent and group is emergent intelligence, and it is the entire premise of swarm methods.

Particle swarm optimisation

PSO (Kennedy and Eberhart, 1995) is a population-based stochastic optimisation technique. Individuals, called particles, fly through the problem space, learning from their own experience and from their neighbours, and gradually move into better regions. It is inspired by flocks of birds, schools of fish and bee swarms.

≡FactsThe basic idea

• Each particle is searching for the optimum, and it moves, so it has a velocity.
• Each particle remembers its own best position so far, its pbest. That memory is the thing a GA chromosome does not have.
• Particles cooperate: a particle knows the fitness of its neighbourhood and uses the position of the best neighbour to adjust its velocity.

⇄ComparePSO against GA

PSOPopulation of random solutions updated over generations. No crossover, no mutation. Particles fly toward current optima and each carries a memory. One operation - the velocity update - so overhead is low.

GAPopulation of random solutions updated over generations. Crossover and mutation recombine chromosomes, which carry no memory of where they have been. More operators to tune.

The equations

For particle $i$, dimension $d$, iteration $t$:

$$v_{i,d}^{\,t+1} = v_{i,d}^{\,t} + c_1 \cdot rand_1 \cdot (p_{i,d}^{\,t} - x_{i,d}^{\,t}) + c_2 \cdot rand_2 \cdot (p_{g,d}^{\,t} - x_{i,d}^{\,t})$$ $$x_{i,d}^{\,t+1} = x_{i,d}^{\,t} + v_{i,d}^{\,t+1}$$

The velocity update is three pulls added together: keep going, go back to your own best, follow the swarm.

Symbol	Meaning
xᵢ	particle position, a D-dimensional vector
vᵢ	particle velocity
pᵢ (pbest)	the particle's best previous position, i.e. its memory
p_g (gbest)	the best position found anywhere in the swarm
c₁, c₂	cognitive and social parameters, positive constants
rand₁, rand₂	random numbers drawn uniformly from [0, 1]

≡FactsThree controls on the velocity

• Velocity clamping - if $v_i > V_{max}$ set $v_i = V_{max}$, and if $v_i < -V_{max}$ set $v_i = -V_{max}$. Without it a particle can leave the search space in one step.
• Inertia weight $w$ multiplies the previous velocity. Start it large for global exploration and decrease it over time for refinement.
• Constriction factor $\varphi$ guarantees convergence.

$$v_{i,d}^{\,t+1} = \varphi\left(w \cdot v_{i,d}^{\,t} + c_1 rand_1 (p_{i,d} - x_{i,d}) + c_2 rand_2 (p_{g,d} - x_{i,d})\right)$$ $$\varphi = \frac{2}{\left|2 - \psi - \sqrt{\psi^2 - 4\psi}\right|}, \qquad \psi = c_1 + c_2 > 4$$

⚠GotchaThe constriction factor needs ψ > 4

$\psi = c_1 + c_2$ must exceed 4 or the square root goes imaginary and the formula is meaningless. This is a constraint on your choice of $c_1$ and $c_2$, not a suggestion.

The algorithm, global version

→StepsOne PSO run

1. Initialise the particles with random positions and velocities in D dimensions.
2. Evaluate the fitness of each particle.
3. Update pbest: if the current fitness beats the particle's own best, replace it.
4. Update gbest: if the current fitness beats the swarm's best, replace it.
5. Update velocity and position with the two equations, applying inertia.
6. If the stopping criterion is not met, good enough fitness or maximum iterations, go back to step 2. Otherwise stop.

A worked example

Minimise $f(x) = x^2$ with a swarm of 3 particles, $w = 0.7$, $c_1 = c_2 = 1.4$, and take $rand = 1$ to keep the arithmetic clean.

Init: x₁ = −2 (f = 4), x₂ = 0.5 (f = 0.25), x₃ = 3 (f = 9); all v = 0

pbestᵢ = xᵢ; gbest = x₂ = 0.5 (lowest f)

 

Particle 1: v = 0.7·0 + 1.4·(pbest₁ − x₁) + 1.4·(gbest − x₁)

= 1.4·(−2 − (−2)) + 1.4·(0.5 − (−2)) = 0 + 3.5 = 3.5

x_new = −2 + 3.5 = 1.5 → f = 2.25 (improved from 4)

 

Particle 3: v = 1.4·(3 − 3) + 1.4·(0.5 − 3) = −3.5

x_new = 3 − 3.5 = −0.5 → f = 0.25 (improved from 9)

Minimising f(x) = x². Both outer particles are dragged toward gbest at 0.5, and both land closer to the true optimum at 0.

Both particles moved towards $x = 0$, the true optimum, pulled there by gbest. Repeat until convergence.

⚠GotchaThis example is illustrative, not from the slides

The slide deck's PSO example was image-only, so the 1-D walkthrough above was reconstructed to show the same mechanics. The equations and the parameter meanings are the examinable part.