Particle swarm optimization: Difference between revisions

Revision as of 07:58, 26 October 2023

Revision as of 01:27, 17 January 2024

Line 54:

A commonly used swarm topology is the ring, in which each particle has just two neighbours, but there are many others.<ref name=bratton2007/> The topology is not necessarily static. In fact, since the topology is related to the diversity of communication of the particles,<ref name=oliveira2016communication/> some efforts have been done to create adaptive topologies (SPSO,<ref>SPSO [http://www.particleswarm.info Particle Swarm Central]</ref> APSO,<ref> 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]</ref> stochastic star,<ref>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</ref> TRIBES,<ref>Clerc, M. (2006). Particle Swarm Optimization. ISTE (International Scientific and Technical Encyclopedia), 2006</ref> Cyber Swarm,<ref>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</ref> and C-PSO<ref name=elshamy07sis/>)

By using the ring topology, PSO can attain generation-level parallelism, significantly enhancing the evolutionary speed.<ref>J. -Y. Li, Z. -H. Zhan, R. -D. Liu, C. Wang, S. Kwong, and J. Zhang, "Generation-Level Parallelism for Evolutionary Computation: A Pipeline-Based Parallel Particle Swarm Optimization," in IEEE Transactions on Cybernetics, vol. 51, no. 10, pp. 4848-4859, Oct. 2021, doi: 10.1109/TCYB.2020.3028070.</ref>

== Inner workings ==

Line 68 ⟶ 70:

* 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.<ref name=bergh01thesis/><ref name=clerc02explosion/><ref name=trelea03particle/> These analyses have resulted in guidelines for selecting PSO parameters that are believed to cause convergence to a point and prevent divergence of the swarm's particles (particles do not move unboundedly and will converge to somewhere). However, the analyses were criticized by Pedersen<ref name=pedersen08simplifying/> for being oversimplified as they assume the swarm has only one particle, that it does not use stochastic variables and that the points of attraction, that is, the particle's best known position '''p''' and the swarm's best known position '''g''', remain constant throughout the optimization process. However, it was shown<ref>{{cite book|last1=Cleghorn|first1=Christopher W|title=Swarm Intelligence |chapter=Particle Swarm Convergence: Standardized Analysis and Topological Influence |volume=8667|pages=134–145|date=2014|doi=10.1007/978-3-319-09952-1_12|series=Lecture Notes in Computer Science|isbn=978-3-319-09951-4}}</ref> 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 modellingmodeling assumption utilized during the stability analysis of PSO,<ref name=Liu2015/> with the most recent generalized result applying to numerous PSO variants and utilized what was shown to be the minimal necessary modeling assumptions.<ref name=Cleghorn2018/>

Convergence to a local optimum has been analyzed for PSO in<ref>{{cite journal|last1=Van den Bergh|first1=F|title=A convergence proof for the particle swarm optimiseroptimizer |journal=Fundamenta Informaticae|url=https://repository.up.ac.za/bitstream/handle/2263/17262/VanDenBergh_Convergence(2010).pdf?sequence=1}}</ref> and.<ref name=Bonyadi2014/> 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.<ref name=zhan10OLPSO/> However, such studies do not provide theoretical evidence to actually prove their claims.

=== Adaptive mechanisms ===