How Particle Swarm Optimization Finds Global Optima: Theory and Practice

Particle Swarm Optimization

Particle Swarm Optimization (PSO) was first proposed by Dr. Kennedy and Dr. Eberhart in 1995, inspired by artificial life research and the foraging behavior of bird flocks. It is a population‑based evolutionary computation technique with parallel processing, good robustness, high probability of finding global optima, and higher computational efficiency than traditional random methods. Its main advantages are simple programming, fast convergence, and a solid intelligent background, making it suitable for both scientific research and engineering applications. Since its introduction, PSO has attracted extensive attention in the evolutionary computation community and has become a regular topic at the International Conference on Evolutionary Computation.

Background

Imagine a scenario where a group of birds is randomly distributed in an area that contains a single food source. The birds do not know the location of the food, but they can measure their distance to it. The optimal strategy is to follow the bird that is currently closest to the food. Treating the food as the optimal point and the distance as a fitness value, the birds’ foraging process becomes a function optimization process, which inspired the simplified formulation of PSO.

Basic Idea of PSO

Each potential solution of an optimization problem is represented as a “particle” in the search space, possessing a fitness value determined by the objective function and a velocity that dictates its direction and step size. Particles track two extrema: the best position found by the particle itself (personal best) and the best position found by the entire swarm (global best). Optionally, a particle may consider only a subset of the swarm as its neighbors, using the best among them as a local best.

Basic Model

Assume a swarm size of N in a D‑dimensional search space. The position of particle i is a D‑dimensional vector x_i, and its velocity is v_i. The personal best position of particle i is p_i, and the global best position found by the swarm is g. The velocity and position are updated by the following equations:

v_i^{t+1} = w·v_i^{t} + c_1·r_1·(p_i - x_i^{t}) + c_2·r_2·(g - x_i^{t})

x_i^{t+1} = x_i^{t} + v_i^{t+1}

where w is the inertia weight (typically between 0.4 and 0.9), c_1 and c_2 are acceleration coefficients, and r_1, r_2 are random numbers in [0,1]. The inertia weight balances exploration and exploitation, while the acceleration coefficients control the influence of personal and social components.

Basic Procedure

The basic PSO algorithm proceeds as follows:

(1) Initialize particles with random positions and velocities.

(2) Evaluate the fitness of each particle.

(3) Compare each particle’s fitness with its personal best; if better, update the personal best.

(4) Compare each particle’s fitness with the global best; if better, update the global best.

(5) Update particle velocities and positions using the two update equations.

(6) If a termination condition is met (sufficient fitness or maximum iterations G_max), stop; otherwise, return to step (2).

(7) Output the global best position (gbest).

PSO with Inertia Weight

To improve convergence, Y. Shi and R. C. Eberhart introduced an inertia weight in 1998. The inertia weight w moderates the particle’s step size, enabling a balance between global exploration (large w) and local exploitation (small w). A common strategy is to decrease w linearly during evolution, e.g., from 0.9 to 0.4. Research suggests optimal w values around 0.6–0.7. Larger w enhances global search ability, while smaller w accelerates convergence by allowing finer local search.