Particle Swarm Optimization: A survey of historical and recent developments with hybridization perspectives

Saptarshi Sengupta; Sanchita Basak; Richard Alan Peters

Source-linked AI summary

Particle Swarm Optimization: A survey of historical and recent developments with hybridization perspectives

Saptarshi Sengupta, Sanchita Basak, Richard Alan Peters

arXiv:1804.05319v2Apr 15, 2018cs.NE

TL;DR

PSO addresses difficult optimization landscapes, including multimodal functions where standard algorithms may settle on one optimum or fail to reach any optimum. This paper surveys PSO’s mechanisms, convergence perspectives, variants, and hybridizations, reporting successes across search-space and objective-function settings while noting unresolved challenges.

Problem
Multimodal and otherwise difficult optimization landscapes can prevent standard algorithms from distinguishing promising regions or reaching optima.
Method
The paper provides a broad survey of PSO mechanisms, parameter choices, convergence, topologies, discrete optimization, niching, and hybridization approaches.
Results
The reviewed PSO developments include successful applications across continuous or discontinuous and tractable or intractable objective functions, with set-based PSO yielding superior results to existing methodologies on Solomon’s VRPTW datasets.
Takeaways & Limitations
PSO has accumulated diverse developments and reported successes for optimization problems with arbitrary search spaces and limited prior guarantees about optima.
Takeaways & Limitations
PSO particles may prematurely converge to a stochastic attractor that is not an optimum.

Abstract

from arXiv · show

Particle Swarm Optimization (PSO) is a metaheuristic global optimization paradigm that has gained prominence in the last two decades due to its ease of application in unsupervised, complex multidimensional problems which cannot be solved using traditional deterministic algorithms. The canonical particle swarm optimizer is based on the flocking behavior and social co-operation of birds and fish schools and draws heavily from the evolutionary behavior of these organisms. This paper serves to provide a thorough survey of the PSO algorithm with special emphasis on the development, deployment and improvements of its most basic as well as some of the state-of-the-art implementations. Concepts and directions on choosing the inertia weight, constriction factor, cognition and social weights and perspectives on convergence, parallelization, elitism, niching and discrete optimization as well as neighborhood topologies are outlined. Hybridization attempts with other evolutionary and swarm paradigms in selected applications are covered and an up-to-date review is put forward for the interested reader.

1. Introduction

PSO emerged within computational intelligence as a broadly applicable optimization technique for ill-structured continuous or discrete, constrained or unconstrained problems. The paper surveys its history, mechanism, advances, and hybridization approaches.

PSO is among optimization techniques that make little or no assumption about problem nature.
PSO has been widely used for continuous and discrete, constrained and unconstrained function optimization.
The survey reviews PSO’s historical development, working mechanism, recent advances, and hybridization with evolutionary algorithms.

2. The Particle Swarm Optimization: Historical Overview

The historical motivation for PSO lies in decentralized agents whose low-level interactions produce meaningful collective behavior without centralized perception of a high-level goal.

Natural computing models decentralized agents that can represent complex real-world systems without perceiving the overall goal.
Meaningful collective behavior arises when agents meet several low-level goals.

3. Working Mechanism of the canonical PSO

Canonical PSO uses particles as candidate solutions moving through a multidimensional search space under the influence of personal and neighboring experience. Its velocity update uses stochastic acceleration toward remembered best positions, and subsequent improvements target convergence, diversity, and shortcomings.

Each particle is a potential solution that traverses a multidimensional search space while being influenced by its own and its neighbors’ experiences.
The initial velocity is adjusted in the positive or negative direction according to the particle’s current and best positions.
The velocity update adds a stochastic cognition component based on the particle’s pBest position.
The original random multiplier of 2 allowed particles to overshoot the target across the search space half of the time.
Since 1995, PSO improvements have addressed convergence guarantees, diversity preservation, and inherent shortcomings through hybridization with parallel evolutionary-computation paradigms.

4. Perspectives on Development

PSO development has focused on balancing exploration, exploitation, convergence, and diversity through adaptive parameters, constriction, velocity control, swarm models, and neighborhood topologies. These advances expose trade-offs between convergence speed and the risk of local or premature convergence.

Parameter control: Particle initialization and maximum velocity jointly shape exploration: large vmax supports global exploration, while small vmax favors local search but may limit new-region discovery.With zero initial velocity, pBest and gBest search around the initial kernel; velocity clamping helps prevent divergence.
Inertia-weight development: Linear time-varying inertia typically decreases ω from 0.9 to 0.4 over the optimization process.The current inertia weight depends on the iteration t relative to the total iteration count tmax.
Inertia-weight development: Nonlinear time-varying inertia preserves higher values longer before decreasing, thereby allocating more time to local search or exploitation.Adaptive alternatives update inertia using swarm improvement, particle distance from the local best, or fuzzy rules based on fitness and current inertia.
Constriction and acceleration: Constriction coefficient χ was introduced from eigenvalue analyses to balance exploration and exploitation, with Ω1 and Ω2 representing cognitive and social acceleration effects.Under Ω ≥ 4 and ν ∈ [0,1], convergence is guaranteed; ν near 1 emphasizes exploration but slows convergence while increasing accuracy.
Constriction and acceleration: Velocity constriction combined with clamping achieves faster convergence rates than unconstrained velocity control in empirical studies.The constriction formulation modifies the velocity update by multiplying the combined prior velocity and attractor terms by χ.
Cognition and social models: The cognition-only model searches locally and can yield suboptimal solutions, whereas the social-only model converges faster with predominantly exploratory behavior.The cognition model is weak in exploration and slow in convergence; the social model attracts particles toward the global best in the feasible neighborhood.
Acceleration and hybridization: Acceleration coefficients C1 and C2 weight attraction toward pBest and gBest, and adaptive or hybrid variants modify these coefficients to improve efficiency, stability, or runtime.An empirically found pair is 2.05 for each coefficient, while time-varying and fuzzy schemes adapt them or inertia over the run.
Topologies: lBest topology uses multiple neighborhood attractors to improve global-optimum discovery, while gBest increases convergence speed but may stagnate at local optima.The lBest trade-off is slower convergence with a significantly increased chance of finding global optima; gBest shares information across all particles.

4.7. Velocity and Position Update Equations of the Standard PSO

Standard PSO updates particle velocities using inertia, personal experience, and global experience, then updates positions. The survey also reviews hybrid PSO designs that combine these mechanisms with other optimization strategies.

Standard PSO updates: Particle positions are updated by adding the new velocity to the current position.This equation advances each coordinate after the velocity calculation.
Standard PSO updates: The standard PSO velocity update combines inertia with cognitive and social attractions toward personal-best and global-best locations.The inertia weight scales prior velocity, while acceleration terms direct particles toward promising regions identified by individual and swarm experience.
Hybridization perspectives: Hybridized PSO combines its social cooperation with other optimization strategies to support exploration-exploitation and offset algorithmic weaknesses.The survey describes hybridization with evolutionary and swarm paradigms, including GA, DE, SA, ACO, CS, ABC, AIS, BA, FA, and GSO.
GA-PSO hybridization: GA-PSO hybrids use sequential or parallel execution, GA operators inside PSO, or phased mechanisms that accelerate search while maintaining diversity.Examples include switching algorithms after stagnation and using PSO for evolution with GA for diversity preservation.
DE-PSO hybridization: DE-PSO hybrids modify particle movement or intermittently apply differential evolution to move particles from poorer regions toward better ones.Reported applications include clustering, dynamic optimization, planning, and benchmark optimization.
Other hybridization approaches: A DE-PSO-ABC design uses self-adjusted weights, with DE reducing premature convergence, PSO accelerating optimization, and ABC exploring new regions when fitness stagnates.The three components are assigned complementary search roles in the hybrid method.

4.9. Parallelized Implementations of PSO

Parallel PSO implementations exploit the algorithm’s inherently parallel structure by distributing particles or sub-swarms across processing units. GPU-based parallelization has produced substantial acceleration in particle-filtering applications.

Parallel architectures: Parallel PSO assigns independent computations to multiple processing units, using sub-swarms or master-slave configurations with information exchange.These structures exploit the separable computational work in PSO while coordinating particle information.
Parallel architectures: Sub-swarm parallelism distributes different particle groups across processors, whereas master-slave designs designate a coordinating master process.The passage contrasts these two broad implementation patterns.
GPU acceleration: 40-fold speedup was achieved using CUDA-capable GPUs over CPUs for parallel PSO-based particle filtering.The application used adaptive appearance models for object tracking.

5. Niche Formation and Multi-Objective Optimization

PSO niching methods address multimodal and dynamic landscapes by maintaining multiple search regions, but their effectiveness and scalability remain problem-dependent. The section surveys stretching, neighborhood, memory-swarm, and subpopulation approaches alongside computational and dimensionality challenges.

5. Niche Formation and Multi-Objective Optimization: Multimodal functions contain multiple optima, requiring algorithms that can distinguish promising regions rather than settling on one optimum.
5.1 Formation of Niches in PSO: Function stretching modifies fitness neighborhoods to remove local optima, but its effectiveness varies across objectives and can introduce false minima.Deflection and Repulsion techniques were introduced to improve stretching-based niching.
5.1 Formation of Niches in PSO: Sequential niching raises solutions below a fitness threshold while removing local optima that violate the constraint.
5.1 Formation of Niches in PSO: Spatially proximate local neighborhoods enable parallel niching effects in nbest PSO, while NichePSO extends this neighborhood-based approach.
5.1 Formation of Niches in PSO: FER-PSO combines a memory swarm of personal bests with an explorer swarm of current positions to guide particles toward promising regions.Particles are attracted to the fittest and closest neighborhood point using a Fitness Euclidean Ratio.
5.2. Niching in Dynamic Environments and Challenges: Subpopulation algorithms search in parallel and can locate multiple optima undergoing changes in shape, height, depth, or spatial position.
5.2. Niching in Dynamic Environments and Challenges: Representative dynamic niching approaches include Multi-Swarm PSO, rPSO, Dynamic SPSO, and lbest PSO with Ring Topology.
5.2. Niching in Dynamic Environments and Challenges: Niching methods can have best-case complexity O(N^2), with performance degradation in high dimensions and sensitivity to parameter settings.

6. Discrete Hyperspace Optimization

Discrete PSO adapts continuous swarm updates through rounding, binarization, set representations, penalties, constraints, and hybrid search. These strategies can improve applicability to discrete and mixed-variable problems, while introducing feasibility or computational trade-offs.

6. Discrete Hyperspace Optimization: Rounding discrete variables can provide significant speedup, but unintelligent round-offs may move particles into infeasible regions and worsen fitness.
6. Discrete Hyperspace Optimization: Binary PSO commonly maps updated velocities into [0,1] with a sigmoid, treating the result as the probability that a position bit equals 1.
6. Discrete Hyperspace Optimization: Set-based PSO replaces conventional position and velocity operators with crisp-set and possibility-set operators for discrete search spaces.
6. Discrete Hyperspace Optimization: SPSO-VRPTW represents vehicle-routing solutions as subsets of graph arcs and achieved superior results against existing state-of-the-art methods on Solomon’s datasets.
6. Discrete Hyperspace Optimization: Penalty approaches increase incentive near discrete values by penalizing points away from them, but impose a heavy computational burden on complex problems.The augmented objective becomes non-convex and continuous, allowing PSO-based optimization.
6. Discrete Hyperspace Optimization: Hybridizing PSO with Branch and Bound combines PSO’s global search with Branch and Bound’s fast convergence to reduce computational effort in nonlinear programming.
6. Discrete Hyperspace Optimization: Across seven integer-programming problems, a constriction-factor and inertia-weight PSO variant was fastest, while other variants offered better global exploration.
6. Discrete Hyperspace Optimization: Discrete PSO variants have also been applied to network benchmarks and real-world networks, including fractional-order IIR filter design.

7. Ensemble Particle Swarm Optimization

Ensemble PSO methods combine multiple search behaviors or parameter schedules to balance convergence and diversity under the No Free Lunch limitation. Reported approaches include local search, differential mutation, heterogeneous strategies, and varied inertia weights.

7. Ensemble Particle Swarm Optimization: The No Free Lunch theorem states that no single optimizer is superior on average across all objective functions.
7. Ensemble Particle Swarm Optimization: MEPSO uses Gaussian local search to improve convergence and differential mutation to increase particle diversity.
7. Ensemble Particle Swarm Optimization: Heterogeneous PSO uses a pool of different search behaviors and empirically outperforms homogeneous PSO.
7. Ensemble Particle Swarm Optimization: Ensemble Particle Swarm Optimizer variants use pools of PSO strategies rather than relying on a single search behavior.
7. Ensemble Particle Swarm Optimization: An inertia-weight ensemble incorporated linear, logarithmic, exponential, Gompertz, chaotic, and oscillating decreasing strategies within heterogeneous comprehensive-learning PSO.

8. Notes on Benchmark Solution Quality and Performance Comparison Practices

The benchmark discussion uses standard unimodal and multimodal functions as an introductory reference for comparing PSO variants. It cautions that reliable accuracy and efficiency inferences require broader benchmark coverage, including rotated, compositional, separable, and non-separable functions.

8. Notes on Benchmark Solution Quality and Performance Comparison Practices: The benchmark section presents commonly used unimodal and multimodal functions to build an intuitive understanding of PSO-based variant performance.
8. Notes on Benchmark Solution Quality and Performance Comparison Practices: Functions F1-F8 include unimodal, simple multimodal, and unrotated multimodal cases.
8. Notes on Benchmark Solution Quality and Performance Comparison Practices: Full-scale performance analysis should include rotated multimodal and compositional functions, with a mix of separable and non-separable benchmarks.
8. Notes on Benchmark Solution Quality and Performance Comparison Practices: Accuracy and efficiency should not be inferred before evaluating a sufficiently broad and varied benchmark suite.
8. Notes on Benchmark Solution Quality and Performance Comparison Practices: Table 8 provides benchmark functions F1-F8 as a first-course reference for introductory purposes.
8. Notes on Benchmark Solution Quality and Performance Comparison Practices: The listed benchmark set includes Rosenbrock, Schwefel’s Problem 2.26, Rastrigin, Griewank, and Schwefel’s Problems 2.22 and 1.2.
8. Notes on Benchmark Solution Quality and Performance Comparison Practices: Table 9 presents 3D plots of the benchmark functions, while Table 10 reports performances of PSO variants on F1-F8.

DEPSO [211]

The section reviews budget-based comparison methods for optimization algorithms and reports that algorithm competitiveness depends on available objective-function evaluations. It also identifies stagnation in local minima before budget exhaustion as a shortcoming.

DEPSO [211]: Benchmarking results provide a high-level view of PSO and variants, while statistical significance tests are commonly used to assess performance differences.The passage cites confidence levels such as alpha=0.01 or 0.05 for significance testing.
DEPSO [211]: The compared algorithms are competitive, with each surpassing the other depending on the available cost-function evaluations.The reported comparison is conditioned on computational cost rather than a uniformly superior algorithm.
DEPSO [211]: A reported shortcoming is under-performance when an algorithm stagnates in a local minimum before the computational budget is exhausted.The authors propose two measures to work around this issue, though the supplied passage does not describe them fully.
DEPSO [211]: Budget-based comparisons use local limits nmax and a global limit Nmax to assess optimization performance across trials.Algorithms operate within nmax, while success is checked against the global budget Nmax; post-optimization data supports aggregate operational zones.
DEPSO [211]: Operational zones support comparisons of deterministic and stochastic algorithms under various computational budgets.The approach uses different reinitializations across local budgets while keeping the global budget constant.

9. Future directions

Future PSO research must address parameter sensitivity, local-optimum convergence, and theoretical shortcomings of basic and ensemble optimizers. The paper points toward more self-adaptive frameworks with fewer user-specified customizations.

9. Future directions: PSO solution quality is sensitive to parameter selection, and one parameter-selection strategy does not work for every problem.The paper identifies parameter sensitivity as a pressing issue for the PSO community.
9. Future directions: Basic PSO can converge to local optima unless it is substantially modified to account for objective-function modalities.This limitation appears among the future-work issues identified by the paper.
9. Future directions: Ensemble optimizers remain promising but do not resolve basic PSO shortcomings such as particle explosion, diversity loss, and local-optimum stagnation.The paper calls for continued attention to these theoretical issues.
9. Future directions: Future work should pursue a unified framework with more intelligent self-adaptation and fewer user-specified customizations.This direction is presented as a response to the unresolved theoretical and practical issues in PSO.