×

A review of particle swarm optimization. I: Background and development. (English) Zbl 1125.90065

Summary: Particle Swarm Optimization (PSO), in its present form, has been in existence for roughly a decade, with formative research in related domains (such as social modelling, computer graphics, simulation and animation of natural swarms or flocks) for some years before that; a relatively short time compared with some of the other natural computing paradigms such as artificial neural networks and evolutionary computation. However, in that short period, PSO has gained widespread appeal amongst researchers and has been shown to offer good performance in a variety of application domains, with potential for hybridisation and specialisation, and demonstration of some interesting emergent behaviour. This paper aims to offer a compendious and timely review of the field and the challenges and opportunities offered by this welcome addition to the optimization toolbox. Part I discusses the location of PSO within the broader domain of natural computing, considers the development of the algorithm, and refinements introduced to prevent swarm stagnation and tackle dynamic environments. Part II considers current research in hybridisation, combinatorial problems, multicriteria and constrained optimization, and a range of indicative application areas.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Software:

AntNet; Boids
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Afshinmanesh F, Marandi A, Rahimi-Kian A (2005) A novel binary particle swarm optimization method using artificial immune system. EuroCon 2005 - The international conference on computer as a tool, Serbia & Montenegro, Belgrade
[2] Al-kazemi B, Mohan CK (2002) Multi-phase Discrete Particle Swarm Optimization. Proceedings of fourth international workshop on frontiers in evolutionary algorithms (FEA 2002)
[3] Angeline PJ (1998a) Evolutionary optimization versus particle swarm optimization: philosophy and performance differences. 7th Annual conf evolutionary programming
[4] Angeline PJ (1998b) Using Selection to Improve Particle Swarm Optimization. Proceedings of IEEE congress on evolutionary computation, Anchorage, Alaska
[5] Blackwell TM, Bentley PJ (2002) Dynamic search with charged swarms. Proceedings of the genetic and evolutionary computation conference 2002 (GECCO 2002), New York, NY, USA, pp 19-26
[6] Bremermann HJ (1958) The evolution of intelligence. The Nervous System as a Model of its Environment. Technical report, no 1, contract no 477(17), Dept Mathematics, Univ Washington, Seattle, July, 1958
[7] Calude CS, Paun G, Tataram M (2001) A Glimpse into natural computing. CDMTCS Tech Rep 117, Univ of Auckland, 2000 and J Multi-Valuate Logic 7:1-28
[8] Cantú-Paz E (2000) Efficient and accurate parallel genetic algorithms. Kluwer Academic Publishers · Zbl 0963.68164
[9] Carlisle A, Dozier G (2000) Adapting particle swarm optimization to dynamic environments. Proceedings of international conference on artificial intelligence, vol 1, pp 429-434, Las Vegas, NV
[10] Carlisle A, Dozier G (2001a) Tracking changing extrema with particle swarm optimizer. Auburn University Technical Report CSSE01-08
[11] Carlisle A, Dozier G (2001b) An Off-The-Shelf PSO. Proceedings of workshop on particle swarm optimization. Indianapolis, IN
[12] Carlisle A, Dozier G (2002) Tracking changing extrema with adaptive particle swarm optimizer. Proceeding of WAC 2002, Orlando, Florida
[13] Chang, J-F; Chu, S-C; Roddick, JF; Pan, JS, A parallel particle swarm optimization algorithm with communication strategies, J Information Sci Eng, 21, 809-818 (2005)
[14] Clerc, M.; Kennedy, J., The particle swarm: explosion, stability and convergence in a multi-dimensional complex space, IEEE Trans Evol Comput, 6, 58-73 (2002)
[15] Clerc M (2003) TRIBES - Un Exemple D’Optimisation par Essaim Particulaire Sans Parametres de Contrôle. In: Optimisation par Essaim Particulaire (OEP 2003), Paris, France
[16] Colorni A, Dorigo M, Maniezzo V (1991) Distributed Optimization by Ant Colonies. Proceedings of European conference on artificial life, Paris, France, pp 134-142
[17] Cui X, Hardin CT, Ragade RK, Potok TE, Elmagraghby AS (2005) Tracking non-stationary optimal solution by particle swarm optimizer. Proceedings of the sixth international conference on software engineering, artificial intelligence, networking and parallel/distributed computing and first acis international workshop on self-assembling wireless networks (SNPD/SAWN’05)
[18] Di Caro, G.; Dorigo, M., AntNet: Distributed Stigmergetic Control for Communications Networks, J Artificial Intelligence Res (JAIR), 9, 317-365 (1998) · Zbl 0910.68182
[19] Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press · Zbl 1092.90066
[20] Eberhart, RC; Simpson, P.; Dobbins, R., Computational intelligence PC tools, 212-226 (1996), San Diego: AP Professional, San Diego
[21] Eberhart RC, Shi Y (2000) Comparing Inertia Weights and Constriction Factors in Particle Swarm Optimization. Proceedings of IEEE congress evolutionary computation, San Diego, CA, pp 84-88
[22] Eberhart RC, Shi Y (2001) Tracking and optimizing dynamic systems with particle swarms. Proceedings of the 2001 congress on evolutionary computation, vol 1, pp 94-100
[23] Feigenbaum, EA; Buchanan, BG; Lederberg, J.; Meltzer, B.; Michie, D., On generality and problem solving: a case study using the DENDRAL program, Machine intelligence, 165-190 (1971), New York: American Elsevier, New York
[24] Fogel, LJ; Owens, AJ; Walsh, MJ, Artificial intelligence thorough simulated evolution (1966), Chichester, UK: John Wiley & Sons, Ltd, Chichester, UK · Zbl 0148.40701
[25] Friedberg RM (1958) A learning machine: Part I. IBM J 2-13
[26] Gehlhaar DK, Fogel DB (1996) Tuning evolutionary programming for conformationally flexible molecular docking. In: Evolutionary programming: proceedings of the fifth annual conference on evolutionary programming February 29-March 3, 1996, San Diego, California, pp 419-429
[27] Gies, D.; Rahmat-Samii, Y., Particle Swarm Optimization for Reconfigurable Phase-Differentiated Array Design, Microwave and Optical Technology Letters, 38, 3, 168-175 (2003)
[28] Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison Wesley · Zbl 0721.68056
[29] Haykin, S., Neural networks – a comprehensive foundation (1999), Delhi, India: Pearson, Delhi, India · Zbl 0934.68076
[30] Hebb, DO, The organization of behavior (1949), New York: Wiley, New York
[31] Heppner, F.; Grenander, U.; Krasner, S., A stochastic nonlinear model for coordinated bird flocks, The ubiquity of chaos (1990), Washington, DC: AAAS Publications, Washington, DC
[32] Holland, JH, Outline for a logical theory of adaptive systems, J Assoc Comput Machinery, 3, 297-314 (1962) · Zbl 0225.68044
[33] Holland, JH, Adaptation in natural and artificial systems (1975), Ann Arbour: University of Michigan Press, Ann Arbour · Zbl 0317.68006
[34] Johnson, S., Emergence: the connected lives of ants, brains, cities, and software (2001), New York: Scribner, New York
[35] Kaewkamnerdpong B, Bentley P (2005) Perceptive particle swarm optimization. Proceedings of the seventh international conference on adaptive and natural computing algorithms (ICCANGA 2005)
[36] Kennedy J, Eberhart RC (1995) Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, pp 1942-1948
[37] Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm algorithm. Proceedings of the conference on systems, man and cybernetics, Piscataway, New Jersey, pp 4104-4109
[38] Kennedy J (1997) The particle swarm: social adaptation of knowledge. Proceedings of international conference evolutionary computation, IEEE, pp 303-308, Piscataway, NJ
[39] Kennedy J (1999) Small Worlds and Mega-Minds: Effects of Neighborhood Topology on Particle Swarm Performance. Proceedings of IEEE Congress on Evolutionary Computation, Piscataway, NJ
[40] Kennedy J (2000) Stereotyping: improving particle swarm performance with cluster analysis. Proceedings of IEEE congress on evolutionary computation, pp 1507-1512, San Diego, CA
[41] Kennedy J, Eberhart RC, Shi Y (2001) Swarm intelligence. Morgan Kaufman, San Francisco, USA
[42] Kennedy, J.; Mendes, R., Population structure and particle swarm performance, Proceedings of Congress on Evolutionary Computation, 2, 1671-1676 (2002)
[43] Kennedy J (2003) Bare bones particle swarms. Proceedings of the IEEE swarm intelligence symposium 2003 (SIS 2003), Indianapolis, Indiana, USA, pp 80-87
[44] Koza, J., Genetic programming: on the programming of computers by means of natural selection (1992), Cambridge, MA: MIT Press, Cambridge, MA · Zbl 0850.68161
[45] Krink T, Vestertroem JS, Riget J (2002) Particle swarm optimization with spatial particle extension. Proceedings of the IEEE congress on evolutionary computation (CEC 2002), Honolulu, Hawaii (2002)
[46] Laskari EC, Parsopoulos KE, Vrahatis MN (2002) Particle swarm optimization for integer programming. Proceedings of the IEEE
[47] McCulloch, WS; Pitts, W., A logical calculus of the ideas imminent in nervous activity, Bull Mathematical Biophys, 5, 115-133 (1943) · Zbl 0063.03860
[48] Mendes R, Kennedy J, Neves J (2003) Watch thy neighbor or how the swarm can learn from its environment. Proceedings of IEEE swarm intelligence symposium, Indianapolis, Indiana, pp 88-94
[49] Minsky, M., The society of mind (1986), New York: Simon and Schuster, New York
[50] Monson CK, Seppi KD (2004) The Kalman swarm. Proceedings of the genetic and evolutionary computation conference (GECCO), Seattle, Washington
[51] Monson CK, Seppi KD (2005a) Bayesian optimization models for particle swarm. Proceedings of genetic and evolutionary computation conference (GECCO), ACM, Washington, DC
[52] Monson CK, Seppi KD (2005b) Improving on the Kalman swarm extracting its essential characteristics. Proceedings of genetic and evolutionary computation conference (GECCO), ACM, Washington, DC
[53] Nelder, JA; Mead, R., A simplex method for function minimization, Computer J, 7, 308-313 (1965) · Zbl 0229.65053
[54] Ozcan E, Mohan CK (1998) Analysis of a simple particle swarm optimization system. Intelligent Engineering Systems Through Artificial Neural Networks 253-258
[55] Ozcan E, Mohan CK (1999) Particle swarm optimization: surfing the waves. Proceedings of IEEE congress on evolutionary computation, Washington, DC
[56] Parrott D, Li X (2004) A particle swarm model for tracking multiple peaks in a dynamic environment using speciation. In: Proceeding of the 2004 congress on evolutionary computation (CEC’04), IEEE Service Center, Piscataway, NJ, pp 98-103, 08855-1331
[57] Parsopoulos KE, Vrahatis MN (2002) Initializing the particle swarm optimizer using the nonlinear simplex method. Advances in intelligent systems, fuzzy systems, evolutionary computation, pp 216-221
[58] Parsopoulos KE, Vrahatis MN (2004) UPSO: a unified particle swarm optimization scheme. In: Lecture series on computer and computational sciences, Proceedings of international conference on computational methods in sciences and engineering (ICCMSE 2004), VSP International Science Publishers, Zeist, The Netherlands, pp 868-873
[59] Parsopoulos KE, Vrahatis MN (2005a) Unified Particle Swarm Optimization in Dynamic Environments. In: Rothlauf F et al (eds) EvoWorkshops 2005, LNCS 3449, pp 590-599
[60] Parsopoulos KE, Vrahatis MN (2005b) Unified particle swarm optimization for tackling operations research problems. Proceedings swarm intelligence symposium SIS 2005, pp 53-59
[61] Ratnaweera, A.; Halgamuge, SK; Watson, HC, Self-organising hierarchical particle swarm optimizer with time-varying acceleration coefficients, IEEE Trans Evol Comput, 8, 3, 240-255 (2004)
[62] Rechenberg I (1965) Cybernetic solution path of an experimental problem. Royal Aircraft Establishment, Library Translation No 1122, August
[63] Reeves, WT, Particle systems – a technique for modeling a class of fuzzy objects, ACM Trans Graphics, 2, 2, 91-108 (1983)
[64] Reynolds, CW, Flocks, herds, and schools: a distributed behavioral model, Computer Graphics, 21, 4, 25-34 (1987)
[65] Riget J, Vesterstrøm JS (2002) A diversity-guided particle swarm optimizer – the ARPSO. EVALife Technical Report no 2002-2002
[66] Shi Y, Eberhart RC (1998) A modified particle swarm optimizer. Proceedings of the IEEE international conference on evolutionary computation, pp 69-73. IEEE Press, Piscataway, NJ
[67] Schutte, JF; Reinbolt, JA; Fregly, BJ; Haftka, RT; George, AD, Parallel Global Optimization with the Particle Swarm Algorithm, Int J Numer Meth Eng, 61, 13, 2296-2315 (2004) · Zbl 1073.65539
[68] Silva A, Neves A, Costa E (2002) An empirical comparison of particle swarm and predator prey optimization. In Proceedings of 13th Irish international conference on artificial intelligence and cognitive science 2464:103-110 · Zbl 1018.68812
[69] Sipper, M.; Sanchez, E.; Mange, D.; Tomassini, M.; Pérez-Uribe, A.; Stauffer, A.; Mange, D.; Tomassini, M., An introduction to bio-inspired machines, Bio-inspired computing machines towards novel computational architectures, 1-12 (1998), Luasanne, Switzerland: Presses Polytechniques et Universitaires Romandes, Luasanne, Switzerland · Zbl 0902.68001
[70] Storn R, Price K (1995) Differential Evolution - A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces. Technical Report TR-95-012, ICSI Available from: http://http.icsi.berkeley.edu/∼storn/litera.html · Zbl 0888.90135
[71] Trelea, IC, The particle swarm optimization algorithm: convergence analysis and parameter selection, Information Processing Lett, 85, 317-325 (2003) · Zbl 1156.90463
[72] Turing, AM, The chemical basis of morphogenesis, Philosophical Trans Royal Society of London, series B, 641, 237 (1952) · Zbl 1403.92034
[73] van den Bergh F, Engelbrecht AP (2002) A new locally convergent particle swarm optimizer. Proceedings of IEEE conference on systems, man and cybernetics, Hammamet, Tunisia
[74] Veeramachaneni K, Peram T, Mohan CK, Osadciw LA (2003) Optimization using particle swarms with near neighbor interactions. Proceedings of genetic and evolutionary computation conference (GECCO), LNCS 2723, Chicago, IL, pp 110-121 · Zbl 1028.68918
[75] Venter G, Sobieszczanski-Sobieski J (2005). A parallel particle swarm optimization algorithm accelerated by asynchronous evaluations. 6th world congresses of structural and multidisciplinary optimization. Rio de Janerio, Brazil, 30 May-03 June 2005
[76] Wolpert, DH; Macready, WG, No free lunch theorems for optimization, IEEE Trans Evol Comput, 1, 1, 67-82 (1997)
[77] Xie XF, Zhang WJ, Yang ZL (2002) A dissipative particle swarm optimization. Congress on evolutionary computation, Honolulu, HI, USA, 2002:1456-1461
[78] Zhang L, Yu H, Hu S (2005) Optimal choice of parameters for particle swarm optimization. J Zhejiang Univ Sci 528-534
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.