9 Particle Swarm Optimization
This chapter introduces particle swarm optimization (PSO) within the broader context of swarm intelligence, emphasizing cooperative, decentralized search in contrast to competitive replacement strategies typical of genetic algorithms. Particles—candidate solutions—move through the search space by combining their own experience (personal best) with neighborhood or global knowledge, yielding emergent problem-solving behavior. The chapter surveys core PSO variants and uses: continuous PSO for real-valued optimization, Binary PSO (BPSO) for bitstring decisions, permutation-based PSO for ordering problems, and adaptive PSO for managing the exploration–exploitation balance. Applications span continuous function optimization, routing and scheduling (e.g., Traveling Salesman Problem), neural network training, and planning problems such as trilateration, coffee shop placement, and doctor rostering.
The mechanics of PSO are developed from the velocity–position update with three forces: inertia (momentum), cognitive (attraction to personal best), and social (attraction to neighborhood or global best). Practical considerations cover initialization of positions/velocities/pbests, synchronous versus asynchronous updates, swarm and neighborhood sizing, and the impact of topologies (star/global-best for fast convergence, ring and von Neumann for stronger diversity, wheel for hub-centric flow). Discrete variants adapt PSO to non-continuous spaces: BPSO interprets velocity as a bit-flip probability via a sigmoid transform, while permutation-based PSO redefines subtraction, addition, and scalar multiplication as swap-sequence operations to navigate permutations. Adaptive strategies tune inertia (random, linear, or nonlinear schedules), optionally clamp velocities, and linearly shift c1 down and c2 up over time to move from exploration to exploitation while maintaining stability.
Implementation guidance includes a from-scratch solver and the use of established libraries to speed experimentation. In continuous settings, PSO is shown solving the multimodal Michalewicz function with stable results across both custom code and ready-made solvers (e.g., PySwarms, pymoo). For discrete optimization, a PSO formulation addresses the TSP by encoding tours and evaluating route lengths, while in learning tasks PSO serves as a gradient-free optimizer to train a small neural network, where the global-best variant achieved the strongest accuracy in the example. Throughout, the chapter stresses parameter tuning and sensitivity analysis, the choice of topology and update mode to avoid premature convergence, and practical tradeoffs between convergence speed, solution quality, and computational cost across continuous and discrete problem classes.
Swarm intelligence algorithm derivation process
Particle Swarm Optimization (PSO) algorithm
Equation 9.1
Equation 9.2
Visualizing motion equation of a particle in the swarm
Equation 9.3
Equation 9.4
Left: Synchronous PSO and Right: Asynchronous PSO
PSO Neighborhood Topologies. a) star social structure, b) ring topology, c) Von Neumann model and d) the wheel topology
Equation 9.5
3D and 2D plots of Michalewicz function. Cross is the optimal solution obtained by the implemented PSO and Circle represents the solution obtained by PySwarms PSO and Pymoo PSO. The three solution are all very close to the optimal solution.
Equation 9.6
Equation 9.7
Position and velocity notations in Binary PSO (BPSO). Each particle represents a position in the binary space. Velocity is defined in terms of the probability of the bit changing.
Equation 9.8
Equation 9.9
Equation 9.10
Re-defined multiplication for permutation-based PSO
Re-defined subtraction operation for permutation-based PSO
Re-defined addition operation for permutation-based PSO
Impact of PSO parameters on the search behavior. Large inertia promotes exploration and small values promote exploitation. c1>c2 results in excessive wandering of individuals through the search space. In contrast, c2>c1 may lead particles to rush prematurely toward a local optimum.
Equation 9.11
Equation 9.12
Equation 9.13
Different inertia weight update methods
Equation 9.14
Equation 9.15
Cognitive and social acceleration coefficient updates. c1>c2 results in more exploration while c2>c1 may lead to more exploitation.
PSO solution of the 20-city TSP
Equation 9.16
Equation 9.17
Neural network’s node demonstration
Penguins dataset
Bill length vs. body mass by species in Penguins dataset
NN layers
Summary
- PSO employs a stochastic approach that utilizes the collective intelligence and movement of a swarm of particles. It is based on the idea of social interaction, which allows for efficient problem-solving.
- The fundamental principle of PSO is to guide the swarm towards the best position in the search space while also remembering each particle's own best-known position as well as the global best known position of the swarm.
- PSO is guided by a straightforward principle: emulate the success of neighboring individuals.
- Although PSO was initially designed for solving problems with continuous variables, many real-world problems involve discrete or combinatorial variables. In these problems, the search space is finite, and the algorithm needs to search through a set of discrete solutions. To address these types of problems, different variants of PSO have been developed, such as Binary PSO (BPSO) and Permutation PSO.
- By carefully tuning inertia weight, cognitive and social acceleration coefficients, PSO can effectively balance exploration and exploitation.
FAQ
What is swarm intelligence and how does it relate to optimization?
Swarm intelligence is a subfield of AI that studies how many simple, decentralized agents interact with each other and their environment to achieve complex goals through self-organization. In optimization, this idea is mimicked by population-based metaheuristics (like Particle Swarm Optimization and Ant Colony Optimization), where multiple candidate solutions cooperate, share information locally, and improve collectively without a central controller.How does Particle Swarm Optimization (PSO) work at a high level?
PSO maintains a swarm of particles (candidate solutions). Each particle has a position and a velocity. At each iteration: (1) evaluate fitness, (2) update each particle’s personal best (pbest) and its neighborhood/global best (nbest/gbest), (3) update velocity using inertia, cognitive (toward pbest), and social (toward nbest/gbest) components, then (4) move the particle by updating its position. The swarm converges by emulating the success of better neighbors.What do the inertia, cognitive, and social terms in PSO mean, and how should I set them?
- Inertia (ω): keeps motion consistent; larger ω encourages exploration, smaller ω promotes exploitation. Typical choices: fixed around ~0.79, or scheduled (e.g., from 0.9 down to 0.4).- Cognitive (c1): pull toward a particle’s own best; larger c1 increases individual exploration.
- Social (c2): pull toward neighborhood/global best; larger c2 increases exploitation.
Common practice: c1 and c2 often around 1.49 each, with c1 + c2 ≤ 4 to avoid divergence. Setting c1=0 yields a social-only model; c2=0 yields a cognition-only (independent hill-climbers) model.
What’s the difference between synchronous and asynchronous PSO?
- Synchronous PSO (S-PSO): all particles update positions/velocities using the same gbest/nbest from the previous iteration, then fitness and bests are updated together. This promotes global, coordinated exploration.- Asynchronous PSO (A-PSO): particles update sequentially and can use the most recent neighbor/best information during the same iteration. This often accelerates information propagation and is generally more effective in practice.
How should I initialize PSO (positions, velocities, swarm size, bounds)?
- Positions: sample uniformly (or with other sampling methods) within the feasible bounds for each dimension.- Velocities: set to zero or small random values to avoid large initial jumps and instability.
- pbest: initialize to the starting positions (and evaluate fitness).
- Swarm size: typically 20–100; larger swarms explore better but cost more computation. Tune empirically for your problem.
- Bounds handling: clamp positions to feasible ranges; optionally clamp velocities to avoid divergence.
What neighborhood topologies can I use and when?
- Star (gbest): everyone connected; fast convergence, good for unimodal problems, higher risk of premature convergence.- Ring (lbest): local neighborhoods; slower but better exploration, recommended for multimodal problems.
- Von Neumann: grid-based neighborhoods; a balance between ring and star.
- Wheel: one hub disseminates information; isolates particles except via the hub. Choose based on the exploration–exploitation tradeoff of your problem.
How does Binary PSO (BPSO) handle discrete (0/1) variables?
In BPSO, positions are bit strings and velocities represent the probability that a bit flips to 1. A sigmoid maps real-valued velocity to [0,1]. For each bit, draw r∈[0,1]; set bit=1 if sigmoid(v) > r, else 0. Velocity updates still use inertia, “cognitive” and “social” pulls, but act on probabilities rather than real positions. This fits binary decision problems like feature selection or assignment.How is PSO adapted for permutations (e.g., TSP)?
Permutation-based PSO redefines arithmetic: (1) Subtraction of positions yields a “velocity” as a sequence of swaps to transform one permutation into another; (2) Multiplication by a scalar truncates/augments the swap sequence; (3) Addition applies a swap sequence (velocity) to a permutation (position) to produce a new tour. These redefinitions let PSO explore permutation spaces coherently.What is Adaptive PSO and how do I schedule parameters?
Adaptive PSO adjusts parameters over time to balance exploration and exploitation:- Inertia ω: Random Selection (mean ~0.75), Linear Time Varying (decrease from ~0.9 to ~0.4), or Nonlinear Time Varying (slower late decay for stronger local search).
- c1 and c2: decrease c1 and increase c2 over iterations (e.g., linear schedules) so the search starts exploratory (c1>c2) and shifts to exploitative (c2>c1). Keep c1 + c2 ≤ 4 for stability.
Where is PSO useful in practice, and what libraries can I use?
- Applications in the chapter: continuous function optimization (e.g., Michalewicz), discrete routing (TSP), neural network training (as an alternative to gradient-based methods), and real tasks like trilateration, planning, and scheduling.- Libraries: PySwarms (broad PSO variants, continuous and discrete, multiple topologies, velocity clamping) and pymoo (continuous PSO among many algorithms). Both produced near-optimal solutions on benchmark examples in the chapter.
Optimization Algorithms ebook for free
