Abstract:The particle swarm optimization (PSO) algorithm is an evolutionary algorithm that simulates the mechanism of biological swarm social behavior. The models of bird flocking and swarm actions are firstly introduced, and the fundamental characteristics and the working mechanisms of PSO algorithm are also analyzed. Then the recent progress in theory of PSO algorithm is reviewed, which are related to the improvement of PSO algorithm, the parameter selection in PSO algorithm, the convergence features of PSO algorithm, and the merging mechanism to other metaheuristic optimization algorithms. In addition, several typical application areas of PSO algorithm are surveyed respectively, which include continuous function optimization, neural network training, optimization of power system and optimization in electromagnetics. Finally, some suggestions on future trends and existing problems related to PSO algorithm are discussed and concluded.
[1] Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies // Proc of the 1st European Conference on Artificial Life. Paris, France, 1991: 134142 [2] Kennedy J, Eberhart R C. Particle Swarm Optimization // Proc of the IEEE International Conference on Neural Networks. Perth, Australia, 1995: 19421948 [3] Heppner F, Grenander U. A Stochastic Nonlinear Model for Coordinated Bird Flocks // Krasner S, ed. The Ubiquity of Chaos. Washington, USA: American Association for the Advancement of Science, 1990: 233238 [4] Kennedy J, Eberhart R C, Shi Yuhui. Swarm Intelligence. San Francisco, USA: Morgan Kaufmann Publishers, 2001 [5] Reynolds C W. Flocks, Herds and Schools: A Distributed Behavioral Model. Computer Graphics, 1987, 21(4): 2534 [6] Kennedy J. The Particle Swarm: Social Adaptation of Knowledge // Proc of the IEEE International Conference on Evolutionary Computation. Indianapolis, USA, 1997: 303308 [7] Shi Yuhui, Eberhart R C. A Modified Particle Swarm Optimizer // Proc of the IEEE International Conference on Evolutionary Computation. Anchorage, USA, 1998: 6973 [8] Shi Yuhui, Eberhart R C. Parameter Selection in Particle Swarm Optimization // Porto V W, Saravanan N, Waagen D E, et al, eds. Lecture Notes in Computer Science, 1998, 1447: 591600 [9] Chatterjee A, Siarry P. Nonlinear Inertia Weight Variation for Dynamic Adaptation in Particle Swarm Optimization. Computers and Operations Research, 2006, 33(3): 859871 [10] Clerc M. The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization // Proc of the Congress on Evolutionary Computation. Washington, USA, 1999: 19511957 [11] Angeline P J. Using Selection to Improve Particle Swarm Optimization // Proc of the IEEE International Conference on Evolutionary Computation. Anchorage, USA, 1998: 8489 [12] Senthil A M, Chandramohan A, Rao M V C. Competitive Approaches to PSO Algorithms via New Acceleration CoEfficient Variant with Mutation Operators // Proc of the 6th International Conference on Computational Intelligence and Multimedia Applications. Las Vegas, USA, 2005: 225230 [13] Kennedy J. Small Worlds and MegaMinds: Effects of Neighborhood Topology on Particle Swarm Performance // Proc of the Congress on Evolutionary Computation. Washington, USA, 1999: 19311938 [14] Kaewkamnerdpong B, Bentley P J. Perceptive Particle Swarm Optimisation: An Investigation // Proc of the IEEE Swarm Intelligence Symposium. Pasadena, USA, 2005: 169176 [15] Janson S, Middendorf M. A Hierarchical Particle Swarm Optimizer and Its Adaptive Variant. IEEE Trans on Systems, Man and Cybernetics, 2005, 35(6): 12721282 [16] Kennedy J. Why Does it Need Velocity? // Proc of the IEEE Swarm Intelligence Symposium. Pasadena, USA, 2005: 3844 [17] Kennedy J. DynamicProbabilistic Particle Swarms // Proc of the Genetic and Evolutionary Computation Conference. Washington, USA, 2005: 201207 [18] He S, Wu Q H, Wen J Y, et al. A Particle Swarm Optimizer with Passive Congregation. Biosystems, 2004, 78(1/2/3): 135147 [19] He Ran, Wang Yongji, Wang Qing, et al. An Improved Particle Swarm Optimization Based on SelfAdaptive Escape Velocity. Journal of Software, 2005, 16(12): 20362044 (in Chinese) (赫 然,王永吉,王 青,等.一种改进的自适应逃逸微粒群算法及实验分析.软件学报, 2005, 16(12): 20362044) [20] van den Bergh F, Engelbrecht A P. A Cooperative Approach to Particle Swarm Optimization. IEEE Trans on Evolutionary Computation, 2004, 8(3): 225239 [21] Dou Quansheng, Zhou Chunguang, Xu Zhongyu, et al. SwarmCore Evolutionary Particle Swarm Optimization in Dynamic Optimization Environments. Journal of Computer Research and Development, 2006, 43(1): 8995 (in Chinese) (窦全胜,周春光,徐中宇,等.动态优化环境下的群核进化粒子群优化方法.计算机研究与发展, 2006, 43(1): 8995) [22] Kennedy J, Eberhart R C. Discrete Binary Version of the Particle Swarm Algorithm // Proc of the IEEE International Conference on Systems, Man and Cybernetics. Orlando, USA, 1997: 41044108 [23] Pang Wei, Wang Kangping, Zhou Chunguang, et al. Fuzzy Discrete Particle Swarm Optimization for Solving Traveling Salesman Problem // Proc of the 4th International Conference on Computer and Information Technology. Wuhan, China, 2004: 796800 [24] Gao Haibing, Zhou Chi, Gao Liang. General Particle Swarm Optimization Model. Chinese Journal of Computers, 2005, 28(12): 19801987 (in Chinese) (高海兵,周 驰,高 亮.广义粒子群优化模型.计算机学报, 2005, 28(12): 19801987) [25] Zeng Jianchao, Wang Lifang. A Generalized Model of Particle Swarm Optimization. Pattern Recognition and Artificial Intelligence, 2005, 18(6): 685688 (in Chinese) (曾建潮,王丽芳.一种广义微粒群算法模型.模式识别与人工智能, 2005, 18(6): 685688) [26] Eberhart R C, Shi Yuhui. Particle Swarm Optimization: Developments, Applications and Resources // Proc of the IEEE Congress on Evolutionary Computation. Soul, Korea, 2001: 8186 [27] Peng Yu, Peng Xiyuan, Liu Zhaoqing. Statistic Analysis on Parameter Efficiency of Particle Swarm Optimization. Acta Electronica Sinica, 2004, 32(2): 209213 (in Chinese) (彭 宇,彭喜元,刘兆庆.微粒群算法参数效能的统计分析.电子学报, 2004, 32(2): 209213) [28] Wang Junwei, Wang Dingwei. Experiments and Analysis on Inertia Weight in Particle Swarm Optimization. Journal of Systems Engineering, 2005, 20(2): 194198(in Chinese) (王俊伟,汪定伟.粒子群算法中惯性权重的实验与分析.系统工程学报, 2005, 20(2): 194198) [29] Ratnaweera A, Halgamuge S K, Watson H C. SelfOrganizing Hierarchical Particle Swarm Optimizer with TimeVarying Acceleration Coefficients. IEEE Trans on Evolutionary Computation, 2004, 8(3): 240255 [30] Zeng Jianchao, Cui Zhihua. A New Unified Model of Particle Swarm Optimization and Its Theoretical Analysis. Journal of Computer Research and Development, 2006, 43(1): 96100 (in Chinese) (曾建潮,崔志华.微粒群算法的统一模型及分析.计算机研究与发展, 2006, 43(1): 96100) [31] Shi Yuhui, Eberhart R C. Empirical Study of Particle Swarm Optimization // Proc of the Congress on Evolutionary Computation. Washington, USA, 1999: 19451950 [32] Clerc M, Kennedy J. The Particle Swarm Explosion, Stability, and Convergence in a Multidimensional Complex Space. IEEE Trans on Evolutionary Computation, 2002, 6(1): 5873 [33] van den Bergh F. An Analysis of Particle Swarm Optimizers. Ph.D Dissertation. Pretoria, South Africa: University of Pretoria. Department of Computer Science, 2002 [34] van den Bergh F, Engelbrecht A P. A New Locally Convergent Particle Swarm Optimizer // Proc of the IEEE International Conference on Systems, Man and Cybernetics. Yasmine Hammamet, Tunisia, 2002: 96101 [35] Zeng Jianchao, Cui Zhihua. A Guaranteed Global Convergence Particle Swarm Optimizer. Journal of Computer Research and Development, 2004, 41(8): 13331338 (in Chinese) (曾建潮,崔志华.一种保证全局收敛的PSO算法.计算机研究与发展, 2004, 41(8): 13331338) [36] Eberhart R C, Shi Yuhui. Comparison between Genetic Algorithms and Particle Swarm Optimization // Proc of the 7th International Conference on Evolutionary Programming. San Diego, USA, 1998: 611616 [37] Krink T, Lovbjerg M. The LifeCycle Model: Combining Particle Swarm Optimisation, Genetic Algorithms and HillClimbers // Proc of the 7th International Conference on Parallel Problem Solving from Nature. Granada, Spain, 2002: 621630 [38] Lü Zhensu, Hou Zhirong. Particle Swarm Optimization with Adaptive Mutation. Acta Electronica Sinica, 2004, 32(3): 416420 (in Chinese) (吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报, 2004, 32(3): 416420) [39] Shi X H, Liang Y C, Lee H P, et al. An Improved GA and a Novel PSOGABased Hybrid Algorithm. Information Processing Letters, 2005, 93(5): 255261 [40] Settles M, Soule T. Breeding Swarms: a GA/PSO hybrid // Proc of the Genetic and Evolutionary Computation Conference. Washington, USA, 2005: 161168 [41] Liu Bo, Wang Ling, Jin Yihui, et al. Improved Particle Swarm Optimization Combined with Chaos. Chaos, Solitons and Fractals, 2005, 25(5): 12611271 [42] Das S, Konar A, Chakraborty U K. Improving Particle Swarm Optimization with Differentially Perturbed Velocity // Proc of the Genetic and Evolutionary Computation Conference. Washington, USA, 2005: 177184 [43] Holden N, Freitas A A. A Hybrid Particle Swarm/Ant Colony Algorithm for the Classification of Hierarchical Biological Data // Proc of the IEEE Swarm Intelligence Symposium. New Delhi, India, 2005: 100107 [44] Parsopoulos K E, Vrahatis M N. On the Computation of All Global Minimizers through Particle Swarm Optimization. IEEE Trans on Evolutionary Computation, 2004, 8(3): 211224 [45] Parsopoulos K E, Plagianakos V P, Magoulas G D, et al. Improving the Particle Swarm Optimizer by Function “Stretching” // Hadjisavvas N, Pardalos P M, eds. Advances in Convex Analysis and Global Optimization. Dordrecht, the Netherlands: Kluwer Academic Publishers, 2001: 445457 [46] Parsopoulos K E, Vrahatis M N. Particle Swarm Optimization Method for Constrained Optimization Problems // Sincak P, Vascak J, Kvasnicka V, et al, eds. Intelligent Technologies-Theory and Application: New Trends in Intelligent Technologies. Amsterdam, the Netherlands: IOS Press, 2002: 214220 [47] Parsopoulos K E, Vrahatis M N. Particle Swarm Optimization Method in Multiobjective Problems // Proc of the ACM Symposium on Applied Computing. Madrid, Spain, 2002: 603607 [48] Coello C A C, Pulido G T, Lechuga M S. Handling Multiple Objectives with Particle Swarm Optimization. IEEE Trans on Evolutionary Computation, 2004, 8(3): 256279 [49] Zhang Libiao, Zhou Chunguang, Ma Ming, et al. Solutions of MultiObjective Optimization Problems Based on Particle Swarm Optimization. Journal of Computer Research and Development, 2004, 41(7): 12861291 (in Chinese) (张利彪,周春光,马 铭,等.基于粒子群算法求解多目标优化问题. 计算机研究与发展, 2004, 41(7): 12861291) [50] Ho S L, Yang Shiyou, Ni Guangzheng, et al. A Particle Swarm OptimizationBased Method for Multiobjective Design Optimizations. IEEE Trans on Magnetics, 2005, 41(5): 17561759 [51] Eberhart R C, Hu Xiaohui. Human Tremor Analysis Using Particle Swarm Optimization // Proc of the IEEE Congress on Evolutionary Computation. Washington, USA, 1999: 19271930 [52] Mendes R, Cortez P, Rocha M , et al. Particle Swarms for Feedforward Neural Network Training // Proc of the International Joint Conference on Neural Networks. Honolulu, USA, 2002: 18951899 [53] Lu W Z, Fan H Y, Lo S M. Application of Evolutionary Neural Network Method in Predicting Pollutant Levels in Downtown Area of Hong Kong. Neurocomputing, 2003, 51(4): 387400 [54] Gao Haibing, Gao Liang, Zhou Chi, et al. Particle Swarm Optimization Based Algorithm for Neural Network Learning. Acta Electronica Sinica, 2004, 32(9): 15721574(in Chinese) (高海兵,高 亮,周 驰,等.基于粒子群优化的神经网络训练算法研究.电子学报, 2004, 32(9): 15721574) [55] Chen Yuehui, Yang Bo, Dong Jiwen. TimeSeries Prediction Using a Local Linear Wavelet Neural Network. Neurocomputing, 2006, 69(4/5/6): 449465 [56] Yoshida H, Kawata K, Fukuyama Y, et al. A Particle Swarm Optimization for Reactive Power and Voltage Control Considering Voltage Security Assessment. IEEE Trans on Power Systems, 2000, 15(4): 12321239 [57] Abido M A. Optimal Design of PowerSystem Stabilizers Using Particle Swarm Optimization. IEEE Trans on Energy Conversion, 2002, 17(3): 406413 [58] Esmin A A A, LambertTorres G, Zambroni de Souza A C. A Hybrid Particle Swarm Optimization Applied to Loss Power Minimization. IEEE Trans on Power Systems, 2005, 20(2): 859866 [59] Huang Chaoming, Huang Chijen, Wang Mingli. A Particle Swarm Optimization to Identifying the ARMAX Model for ShortTerm Load Forecasting. IEEE Trans on Power Systems, 2005, 20(2): 11261133 [60] Jeyakumar D N, Jayabarathi T, Raghunathan T. Particle Swarm Optimization for Various Types of Economic Dispatch Problems. International Journal of Electrical Power and Energy Systems, 2006, 28(1): 3642 [61] Robinson J, RahmatSamii Y. Particle Swarm Optimization in Electromagnetics. IEEE Trans on Antennas and Propagation, 2004, 52(2): 397407 [62] Li Hui, Zhang An, Zhao Min, et al. Particle Swarm Optimization Algorithm for FIR Digital Filters Design. Acta Electronica Sinica, 2005, 33(7): 13381341 (in Chinese) (李 辉,张 安,赵 敏,等.粒子群优化算法在FIR数字滤波器设计中的应用. 电子学报, 2005, 33(7): 13381341) [63] Liu W C. Design of a Multiband CPWFed Monopole Antenna Using a Particle Swarm Optimization Approach. IEEE Trans on Antennas and Propagation, 2005, 53(10): 32733279 [64] Wang Wen, Lü Yilong, Fu J S, et al. Particle Swarm Optimization and FiniteElement Based Approach for Microwave Filter Design. IEEE Trans on Magnetics, 2005, 41(5): 18001803 [65] Jin N, RahmatSamii Y. Parallel Particle Swarm Optimization and FiniteDifference TimeDomain (PSO/FDTD) Algorithm for Multiband and WideBand Patch Antenna Designs. IEEE Trans on Antennas and Propagation, 2005, 53(11): 34593468 [66] Rasmussen T K, Krink T. Improved Hidden Markov Model Training for Multiple Sequence Alignment by a Particle Swarm OptimizationEvolutionary Algorithm Hybrid. Biosystems, 2003, 72(1/2): 517 [67] Sousa T, Silva A, Neves A. Particle Swarm Based Data Mining Algorithms for Classification Tasks. Parallel Computing, 2004, 30(5/6): 767783 [68] Franken N, Engelbrecht A P. Particle Swarm Optimization Approaches to Coevolve Strategies for the Iterated Prisoner’s Dilemma. IEEE Trans on Evolutionary Computation, 2005, 9(6): 562579