Particle swarm optimization

Algorithm

A basic variant of the PSO algorithm is initialized with a connected population (called a swarm) of candidate solutions (called particles). A candidate solution is a vector of numeric values which can be considered as coordinates of a point in a search space; as an iteratively moving point it can be conceptualized as a particle. The particles move around in the search-space according to a few simple formulae. Each particle has some neighbors it is connected to, where the neighborhood may be a few or all other population members. The next position of a particle is stochastically determined by its own best-so-far position in the search space as well as the particle's best neighbor's best-so-far position. When an improved position is discovered - one that produces a better result in the objective function - the best-so-far position of the particle is updated. The process is repeated and by doing so it is expected, but not guaranteed, that a satisfactory solution will eventually be discovered.

Formally, let f: ℝn → ℝ be the cost function which must be minimized. The function takes a candidate solution as an argument in the form of a vector of real numbers and produces a real number as output which indicates the objective function value of the given candidate solution. The gradient of f is not known. The goal is to find a solution a for which f(a) ≤ f(b) for all b in the search-space, which would mean a is the global minimum.

Let S be the number of particles in the swarm, each having a position xi ∈ ℝn in the search-space and a velocity vi ∈ ℝn. Let pi be the best known position of particle i and let g be the best known position of the particle's neighborhood. A basic PSO algorithm to minimize the cost function is then:

for each particle i = 1, ..., S do Initialize the particle's position with a uniformly distributed random vector: xi ~ U(blo, bup) Initialize the particle's best known position to its initial position: pi ← xi if f(pi) update the swarm's best known position: g ← pi Initialize the particle's velocity: vi ~ U(-|bup-blo|, |bup-blo|) while a termination criterion is not met do: for each particle i = 1, ..., S do for each dimension d = 1, ..., n do Pick random numbers: rp, rg ~ U(0,1) Update the particle's velocity: vi,d ← w vi,d + φp rp (pi,d-xi,d) + φg rg (gd-xi,d) Update the particle's position: xi ← xi + vi if f(xi) i) then Update the particle's best known position: pi ← xi if f(pi) Update the swarm's best known position: g ← pi

The values blo and bup represent the lower and upper boundaries of the search-space respectively. The w parameter is the inertia weight. The parameters φp and φg are often called cognitive coefficient and social coefficient.

The termination criterion can be the number of iterations performed, or a solution where the adequate objective function value is found. The parameters w, φp, and φg are selected by the practitioner and control the behaviour and efficacy of the PSO method (below).

Parameter selection

The choice of PSO parameters can have a large impact on optimization performance. Selecting PSO parameters that yield good performance has therefore been the subject of much research.

To prevent divergence ("explosion") the inertia weight must be smaller than 1. The two other parameters can be then derived thanks to the constriction approach, or freely selected, but the analyses suggest convergence domains to constrain them. Typical values are in [ 1,3].

The PSO parameters can also be tuned by using another overlaying optimizer, a concept known as meta-optimization, or even fine-tuned during the optimization, e.g., by means of fuzzy logic.

Parameters have also been tuned for various optimization scenarios.

Neighbourhoods and topologies

The topology of the swarm defines the subset of particles with which each particle can exchange information. thus different topologies have been used to control the flow of information among particles. For instance, in local topologies, particles only share information with a subset of particles. – for example "the m nearest particles" – or, more often, a social one, i.e. a set of particles that is not depending on any distance. In such cases, the PSO variant is said to be local best (vs global best for the basic PSO).

A commonly used swarm topology is the ring, in which each particle has just two neighbours, but there are many others. APSO, stochastic star, TRIBES, Cyber Swarm, and C-PSO)

By using the ring topology, PSO can attain generation-level parallelism, significantly enhancing the evolutionary speed.

Inner workings

There are several schools of thought as to why and how the PSO algorithm can perform optimization.

A common belief amongst researchers is that the swarm behaviour varies between exploratory behaviour, that is, searching a broader region of the search-space, and exploitative behaviour, that is, a locally oriented search so as to get closer to a (possibly local) optimum. This school of thought has been prevalent since the inception of PSO. This school of thought contends that the PSO algorithm and its parameters must be chosen so as to properly balance between exploration and exploitation to avoid premature convergence to a local optimum yet still ensure a good rate of convergence to the optimum. This belief is the precursor of many PSO variants, see below.

Another school of thought is that the behaviour of a PSO swarm is not well understood in terms of how it affects actual optimization performance, especially for higher-dimensional search-spaces and optimization problems that may be discontinuous, noisy, and time-varying. This school of thought merely tries to find PSO algorithms and parameters that cause good performance regardless of how the swarm behaviour can be interpreted in relation to e.g. exploration and exploitation. Such studies have led to the simplification of the PSO algorithm, see below.

Convergence

In relation to PSO the word convergence typically refers to two different definitions:

• Convergence of the sequence of solutions (aka, stability analysis, converging) in which all particles have converged to a point in the search-space, which may or may not be the optimum,
• Convergence to a local optimum where all personal bests p or, alternatively, the swarm's best known position g, approaches a local optimum of the problem, regardless of how the swarm behaves.

Convergence of the sequence of solutions has been investigated for PSO. that these simplifications do not affect the boundaries found by these studies for parameter where the swarm is convergent. Considerable effort has been made in recent years to weaken the modeling assumption utilized during the stability analysis of PSO, with the most recent generalized result applying to numerous PSO variants and utilized what was shown to be the minimal necessary modeling assumptions.

Convergence to a local optimum has been analyzed for PSO in and. It has been proven that PSO needs some modification to guarantee finding a local optimum.

This means that determining the convergence capabilities of different PSO algorithms and parameters still depends on empirical results. One attempt at addressing this issue is the development of an "orthogonal learning" strategy for an improved use of the information already existing in the relationship between p and g, so as to form a leading converging exemplar and to be effective with any PSO topology. The aims are to improve the performance of PSO overall, including faster global convergence, higher solution quality, and stronger robustness. However, such studies do not provide theoretical evidence to actually prove their claims.

Adaptive mechanisms

Without the need for a trade-off between convergence ('exploitation') and divergence ('exploration'), an adaptive mechanism can be introduced. Adaptive particle swarm optimization (APSO) features better search efficiency than standard PSO. APSO can perform global search over the entire search space with a higher convergence speed. It enables automatic control of the inertia weight, acceleration coefficients, and other algorithmic parameters at the run time, thereby improving the search effectiveness and efficiency at the same time. Also, APSO can act on the globally best particle to jump out of the likely local optima. However, APSO will introduce new algorithm parameters, it does not introduce additional design or implementation complexity nonetheless.

Besides, through the utilization of a scale-adaptive fitness evaluation mechanism, PSO can efficiently address computationally expensive optimization problems.

Variants

Numerous variants of even a basic PSO algorithm are possible. For example, there are different ways to initialize the particles and velocities (e.g. start with zero velocities instead), how to dampen the velocity, only update pi and g after the entire swarm has been updated, etc. Some of these choices and their possible performance impact have been discussed in the literature.

A series of standard implementations have been created by leading researchers, "intended for use both as a baseline for performance testing of improvements to the technique, as well as to represent PSO to the wider optimization community. Having a well-known, strictly-defined standard algorithm provides a valuable point of comparison which can be used throughout the field of research to better test new advances." The latest is Standard PSO 2011 (SPSO-2011).

In addition, some PSO variants have been developed to solve large-scale global optimization (LSGO) problems with more than 1000 dimensions. Representative variants include competitive swarm optimizer (CSO) and level-based learning swarm optimizer (LLSO). Recently, PSO has also been extended to solve multi-agent consensus-based distributed optimization problems, e.g., multi-agent consensus-based PSO with adaptive internal and external learning (MASOIE), etc.

Hybridization

New and more sophisticated PSO variants are also continually being introduced in an attempt to improve optimization performance. There are certain trends in that research; one is to make a hybrid optimization method using PSO combined with other optimizers, and the incorporation of an effective learning method.

Alleviate premature convergence

Another research trend is to try to alleviate premature convergence (that is, optimization stagnation), e.g. by reversing or perturbing the movement of the PSO particles, (multi-swarm optimization). The multi-swarm approach can also be used to implement multi-objective optimization. Finally, there are developments in adapting the behavioural parameters of PSO during optimization.

Simplifications

Another school of thought is that PSO should be simplified as much as possible without impairing its performance; a general concept often referred to as Occam's razor. Simplifying PSO was originally suggested by Kennedy and has been studied more extensively, where it appeared that optimization performance was improved, and the parameters were easier to tune and they performed more consistently across different optimization problems.

Another argument in favour of simplifying PSO is that metaheuristics can only have their efficacy demonstrated empirically by doing computational experiments on a finite number of optimization problems. This means a metaheuristic such as PSO cannot be proven correct and this increases the risk of making errors in its description and implementation. A good example of this presented a promising variant of a genetic algorithm (another popular metaheuristic) but it was later found to be defective as it was strongly biased in its optimization search towards similar values for different dimensions in the search space, which happened to be the optimum of the benchmark problems considered. This bias was because of a programming error, and has now been fixed.

Bare Bones PSO

Initialization of velocities may require extra inputs. The Bare Bones PSO variant has been proposed in 2003 by James Kennedy, and does not need to use velocity at all.

In this variant of PSO one dispenses with the velocity of the particles and instead updates the positions of the particles using the following simple rule, : \vec x_i = G\left(\frac{\vec p_i+\vec g}{2},||\vec p_i-\vec g||\right) ,, where \vec x_i, \vec p_i are the position and the best position of the particle i; \vec g is the global best position; G(\vec x,\sigma) is the normal distribution with the mean \vec x and standard deviation \sigma; and where ||\dots|| signifies the norm of a vector.

Accelerated Particle Swarm Optimization

Another simpler variant is the accelerated particle swarm optimization (APSO), which also does not need to use velocity and can speed up the convergence in many applications. A simple demo code of APSO is available.

In this variant of PSO one dispenses with both the particle's velocity and the particle's best position. The particle position is updated according to the following rule, : \vec x_i \leftarrow (1-\beta)\vec x_i + \beta \vec g + \alpha L \vec u ,, where \vec u is a random uniformly distributed vector, L is the typical length of the problem at hand, and \beta\sim 0.1-0.7 and \alpha\sim 0.1-0.5 are the parameters of the method. As a refinement of the method one can decrease \alpha with each iteration, \alpha_n=\alpha_0\gamma^n, where n is the number of the iteration and 0 is the decrease control parameter.

Multi-objective optimization

PSO has also been applied to multi-objective problems, in which the objective function comparison takes Pareto dominance into account when moving the PSO particles and non-dominated solutions are stored so as to approximate the pareto front.

Binary, discrete, and combinatorial

As the PSO equations given above work on real numbers, a commonly used method to solve discrete problems is to map the discrete search space to a continuous domain, to apply a classical PSO, and then to demap the result. Such a mapping can be very simple (for example by just using rounded values) or more sophisticated.

However, it can be noted that the equations of movement make use of operators that perform four actions:

• computing the difference of two positions. The result is a velocity (more precisely a displacement)
• multiplying a velocity by a numerical coefficient
• adding two velocities
• applying a velocity to a position

Usually a position and a velocity are represented by n real numbers, and these operators are simply -, *, +, and again +. But all these mathematical objects can be defined in a completely different way, in order to cope with binary problems (or more generally discrete ones), or even combinatorial ones. One approach is to redefine the operators based on sets.

References

References

1. (2015). "A Comprehensive Survey on Particle Swarm Optimization Algorithm and Its Applications". Mathematical Problems in Engineering.
2. (August 2025)
3. This subset can be a geometrical oneSuganthan, Ponnuthurai N. "[https://ieeexplore.ieee.org/abstract/document/785514/ Particle swarm optimiser with neighbourhood operator]." Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on. Vol. 3. IEEE, 1999.
4. Almasi, O. N. and Khooban, M. H. (2017). A parsimonious SVM model selection criterion for classification of real-world data sets via an adaptive population-based algorithm. Neural Computing and Applications, 1-9. [https://link.springer.com/article/10.1007/s00521-017-2930-y https://doi.org/10.1007/s00521-017-2930-y]
5. Miranda, V., Keko, H. and Duque, Á. J. (2008). [https://repositorio.inesctec.pt/bitstream/123456789/1561/1/PS-05818.pdf Stochastic Star Communication Topology in Evolutionary Particle Swarms (EPSO)]. International Journal of Computational Intelligence Research (IJCIR), Volume 4, Number 2, pp. 105-116
6. Clerc, M. (2006). Particle Swarm Optimization. ISTE (International Scientific and Technical Encyclopedia), 2006
7. Yin, P., Glover, F., Laguna, M., & Zhu, J. (2011). [http://leeds-faculty.colorado.edu/glover/fred%20pubs/428%20-%20A_complementary_cyber_swarm_algorithm_pub%20version%20w%20pen%20et%20al.pdf A Complementary Cyber Swarm Algorithm]. International Journal of Swarm Intelligence Research (IJSIR), 2(2), 22-41
8. (2021). "Generation-Level Parallelism for Evolutionary Computation: A Pipeline-Based Parallel Particle Swarm Optimization". IEEE Transactions on Cybernetics.
9. (2014). "Swarm Intelligence".
10. "A convergence proof for the particle swarm optimizer". Fundamenta Informaticae.
11. (September 2023). "Scale adaptive fitness evaluation-based particle swarm optimisation for hyperparameter and architecture optimisation in neural networks and deep learning". CAAI Transactions on Intelligence Technology.
12. (2015). "Pathological Brain Detection in Magnetic Resonance Imaging Scanning by Wavelet Entropy and Hybridization of Biogeography-based Optimization and Particle Swarm Optimization". Progress in Electromagnetics Research.
13. (2013). "OptiFel: A Convergent Heterogeneous Particle Sarm Optimization Algorithm for Takagi-Sugeno Fuzzy Modeling". IEEE Transactions on Fuzzy Systems.
14. Kennedy, James. (2003). "Proceedings of the 2003 IEEE Swarm Intelligence Symposium. SIS'03 (Cat. No.03EX706)".
15. X. S. Yang, S. Deb and S. Fong, [https://arxiv.org/abs/1203.6577 Accelerated particle swarm optimization and support vector machine for business optimization and applications], NDT 2011, Springer CCIS 136, pp. 53-66 (2011).
16. "Search Results: APSO - File Exchange - MATLAB Central".
17. Roy, R., Dehuri, S., & Cho, S. B. (2012). [http://sclab.yonsei.ac.kr/publications/Papers/IJ/A%20Novel%20Particle%20Swarm%20Optimization%20Algorithm%20for%20Multi-Objective%20Combinatorial%20Optimization%20Problem.pdf A Novel Particle Swarm Optimization Algorithm for Multi-Objective Combinatorial Optimization Problem] {{Webarchive. link. (2022-01-20 . 'International Journal of Applied Metaheuristic Computing (IJAMC)', 2(4), 41-57)
18. Kennedy, J. & Eberhart, R. C. (1997). [http://ahmetcevahircinar.com.tr/wp-content/uploads/2017/02/A_discrete_binary_version_of_the_particle_swarm_algorithm.pdf A discrete binary version of the particle swarm algorithm], Conference on Systems, Man, and Cybernetics, Piscataway, NJ: IEEE Service Center, pp. 4104-4109
19. Clerc, M. (2004). [https://link.springer.com/chapter/10.1007/978-3-540-39930-8_8 Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem], New Optimization Techniques in Engineering, Springer, pp. 219-239
20. Clerc, M. (2005). Binary Particle Swarm Optimisers: toolbox, derivations, and mathematical insights, [http://hal.archives-ouvertes.fr/hal-00122809/en/ Open Archive HAL]
21. (2008). "A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems". Applied Mathematics and Computation.
22. (2002). "The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers".
23. (2017). "Particle swarm optimization for single objective continuous space problems: a review". Evolutionary Computation.
24. (2010). "An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis". Applied Soft Computing.
25. (2002). "Extending Particle Swarm Optimisers with Self-Organized Criticality".
26. Xinchao, Z.. (2010). "A perturbed particle swarm algorithm for numerical optimization". Applied Soft Computing.
27. (2009). "Adaptive Particle Swarm Optimization". IEEE Transactions on Systems, Man, and Cybernetics.
28. (2011). "Orthogonal Learning Particle Swarm Optimization". IEEE Transactions on Evolutionary Computation.
29. (2014). "A locally convergent rotationally invariant particle swarm optimization algorithm". Swarm Intelligence.
30. (2014). "An analysis of the velocity updating rule of the particle swarm optimization algorithm". Journal of Heuristics.
31. (2018). "Particle Swarm Stability: A Theoretical Extension using the Non-Stagnate Distribution Assumption". Swarm Intelligence.
32. (2015). "Order-2 stability analysis of particle swarm optimization". Evolutionary Computation.
33. (1995). "Particle Swarm Optimization".
34. (1997). "The particle swarm: social adaptation of knowledge".
35. (1998). "A modified particle swarm optimizer".
36. (1998). "Parameter selection in particle swarm optimization".
37. (2000). "Comparing inertia weights and constriction factors in particle swarm optimization".
38. (2001). "An Off-The-Shelf PSO".
39. Zhang, Wen-Jun; Xie, Xiao-Feng (2003). [http://www.wiomax.com/team/xie/paper/SMCC03.pdf DEPSO: hybrid particle swarm with differential evolution operator]. ''IEEE International Conference on Systems, Man, and Cybernetics'' (SMCC), Washington, DC, USA: 3816-3821.
40. van den Bergh, F.. (2001). "An Analysis of Particle Swarm Optimizers". University of Pretoria, Faculty of Natural and Agricultural Science.
41. Trelea, I.C.. (2003). "The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection". Information Processing Letters.
42. (2002). "The particle swarm - explosion, stability, and convergence in a multidimensional complex space". IEEE Transactions on Evolutionary Computation.
43. Xie, Xiao-Feng; Zhang, Wen-Jun; Yang, Zhi-Lian (2002). [http://www.wiomax.com/team/xie/paper/CEC02.pdf A dissipative particle swarm optimization]. ''Congress on Evolutionary Computation'' (CEC), Honolulu, HI, USA: 1456-1461.
44. (2008). "A Simplified Recombinant PSO". Journal of Artificial Evolution and Applications.
45. (2001). "Swarm Intelligence". Morgan Kaufmann.
46. Pedersen, M.E.H.. (2010). "Tuning & Simplifying Heuristical Optimization". University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group.
47. Pedersen, M.E.H.. (2010). "Simplifying particle swarm optimization". Applied Soft Computing.
48. Mason, Karl. (2018). "A Meta Optimisation Analysis of Particle Swarm Optimisation Velocity Update Equations for Watershed Management Learning". Applied Soft Computing.
49. Pedersen, M.E.H.. (2010). "Good parameters for particle swarm optimization". Technical Report HL1001.
50. Poli, R.. (2007). "An analysis of publications on particle swarm optimisation applications". Technical Report CSM-469.
51. Poli, R.. (2008). "Analysis of the publications on the applications of particle swarm optimisation". Journal of Artificial Evolution and Applications.
52. Evers, G.. (2009). "An Automatic Regrouping Mechanism to Deal with Stagnation in Particle Swarm Optimization". The University of Texas - Pan American, Department of Electrical Engineering.
53. (2004). "A robust stochastic genetic algorithm (StGA) for global numerical optimization". IEEE Transactions on Evolutionary Computation.
54. (2008). "Corrections to "A Robust Stochastic Genetic Algorithm (StGA) for Global Numerical Optimization"". IEEE Transactions on Evolutionary Computation.
55. (2006). "Optimized Particle Swarm Optimization (OPSO) and its application to artificial neural network training". BMC Bioinformatics.
56. (2008). "Nature-Inspired Metaheuristic Algorithms". Luniver Press.
57. (2002). "Particle swarm optimization method in multiobjective problems".
58. Mason, Karl. (2017). "Multi-objective dynamic economic emission dispatch using particle swarm optimisation variants". Neurocomputing.
59. (2014). "SPSO 2011 analysis of stability; local convergence; and rotation sensitivity.". GECCO2014 (the best paper award in the track ACSI).
60. (2002). "MOPSO: A Proposal for Multiple Objective Particle Swarm Optimization".
61. (2010). "A novel set-based particle swarm optimization method for discrete optimization problem". IEEE Transactions on Evolutionary Computation.
62. (2007). "Clubs-based Particle Swarm Optimization".
63. (2012). "A GPU-Based Multi-Swarm PSO Method for Parameter Estimation in Stochastic Biological Systems Exploiting Discrete-Time Target Series".
64. Clerc, M.. (2012). "Standard Particle Swarm Optimisation". HAL Open Access Archive.
65. (2016). "A novel stability-based adaptive inertia weight for particle swarm optimization". Applied Soft Computing.
66. (2007). "2007 IEEE Swarm Intelligence Symposium".
67. (2013). "2013 IEEE Congress on Evolutionary Computation". Evolutionary Computation (CEC), 2013 IEEE Congress on.
68. (2002). "Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No.02TH8600)".
69. (2016). "Swarm Intelligence".
70. (2015). "The impact of particles initialization in PSO: parameter estimation as a case in point, (Canada)".
71. (2018). "Fuzzy Self-Tuning PSO: a settings-free algorithm for global optimization". Swarm and Evolutionary Computation.
72. (2015). "Proactive particles in swarm optimization: a self-tuning algorithm based on fuzzy logic".