粒子群算法的交互性与随机性分析

刘建华; 刘国买; 杨荣华; 胡文瑜

doi:10.3724/SP.J.1004.2012.01471

粒子群算法的交互性与随机性分析

doi: 10.3724/SP.J.1004.2012.01471

1.
福建工程学院计算机与信息科学系福州 350108;
2.
福建工程学院管理学院福州 350108

详细信息

通讯作者:
刘建华

计量
- 文章访问数: 2191
- HTML全文浏览量: 39
- PDF下载量: 1021
- 被引次数: 0
出版历程
- 收稿日期: 2011-07-25
- 修回日期: 2012-01-10
- 刊出日期: 2012-09-20

Analysis of Interactivity and Randomness in Particle Swarm Optimization

1.
Department of Computer and Information, Fujian University of Technology, Fuzhou 350108;
2.
School of Management, Fujian University of Technology, Fuzhou 350108

摘要

摘要: 在现有分析结论的基础上, 分别采用优化的凸性理论和概率收敛理论, 分析了粒子群 (Particle swarm optimization, PSO) 算法的交互性和随机性对算法的影响. 分析得出, 在不考虑随机性的条件下, 当 PSO 算法优化单峰函数时, 交互性使粒子最终收敛于全局最优粒子位置; 当 PSO 算法优化多峰函数时, 交互性未必使粒子最终收敛于全局最优位置. 但如果考虑随机性, 算法优化的目标函数无论是单峰函数还是多峰函数, 粒子都会依概率收敛于最优位置. 通过基准函数的实验验证了分析的结论.
- 粒子群算法 /
- 收敛性 /
- 交互性 /
- 随机性
Abstract: Based on the existing theoretical results, this paper analyzes the influence on convergence of particle swarm optimization (PSO) exerted by interactivity of PSO using the conver optimization theory, then analyzes the randomness of PSO using the probability convergence theory. It is concluded that when PSO is used to optimize the unimodal function without consideration of randomness of particle movement, the trajectory of particle will eventually converge to the global optimal location; when PSO is used to optimize the multimodal function particles, the trajectory of particle may not necessarily converge to the global optimal location. However, if the randomness of particle movement is considered for analysis of PSO, particles will all converge to the optimal location in probabilities no matter the objectives function is unimodal or multimodal. Experiments are conducted on beckmark function to test these conclusions.
- Particle swarm optimization (PSO) /
- convergence /
- interactivity /
- randomness

HTML全文

参考文献(1)

[1]

Eberhart R C, Kennedy J. A new optimizer using particle swarm theory. In: Proceedings of the 6th International Symposium on Micro Machine and Human Science. Nagoya, Japan: IEEE, 1995. 39-43[2] Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of the 1995 IEEE Internationa1 Conference on Neural Networks. Perth, WA, Australia: IEEE, 1995. 1942- 1948[3] Shi Y H, Eberhart R C. A modified particle swarm optimizer. In: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation. Anchorage, AK, USA: IEEE, 1998. 69-73[4] Poli R, Kennedy J, Blackwell T. Particle swarm optimization: an overview. Swarm Intelligence, 2007, 1(1): 33-57[5] Kang Qi, Wang Lei, An Jing, Wu Qi-Di. Approximate dynamic programming based parameter optimization of particle swarm systems. Acta Automatica Sinica, 2010, 36(8): 1171 -1181 (康琦, 汪镭, 安静, 吴启迪. 基于近似动态规划的微粒群系统参数优化研究. 自动化学报, 2010, 36(8): 1171-1181)[6] Alfi A. PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems. Acta Automatica Sinica, 2011, 37(5): 541-549[7] Huang Fa-Liang, Xiao Nan-Feng. Discovering overlapping communities based on line graph and PSO. Acta Automatica Sinica, 2011, 37(9): 1140-1144 (黄发良, 肖南峰. 基于线图与 PSO 的网络重叠社区发现. 自动化学报, 2011, 37(9): 1140-1144)[8] Banks A, Vincent J, Anyakoha C. A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications. Natural Computing, 2008, 7(1): 109-124[9] Ozcan E, Mhoan C K. Analysis of a simple particle swarm optimization system. Intelligent Engineering Systems Through Artificial Neural Networks, 1998, 8: 253-258[10] Ozcan E, Mohan C K. Particle swarm optimization: surfing the waves. In: Proceedings of the 1999 Congress on Evolutionary Computation. Washington, DC, USA: IEEE, 1999. 1939-1944[11] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58-73[12] Solis F J, Wets R J B. Minimization by random search techniques. Mathematics of Operations Research, 1981, 6(1): 19 -30[13] Van de Bergh F. An Analysis of Particle Swarm Optimizer [Ph.D. dissertation], University of Pretoria, South Africa, 2002[14] Van de Bergh F, Engelbrecht A P. A convergence proof for the particle swarm optimiser. Fundamenta Informaticae, 2010, 105(4): 341-374[15] Blackwell T M. Particle swarms and population diversity. Soft Computing —— A Fusion of Foundations, Methodologies and Applications, 2005, 9(11): 793-802[16] Trelea I C. The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters, 2003, 85(6): 317-325[17] Ghosh S, Das S, Kundu D, Suresh K, Abraham A. Inter-particle communication and search-dynamics of lbest particle swarm optimizers: an analysis. Information Sciences, 2012, 182(1): 156-168[18] Fernandez-Martinez J L, Garcia-Gonzalo E. Stochastic stability analysis of the linear continuous and discrete PSO models. IEEE Transactions on Evolutionary Computation, 2011, 15(3): 405-423[19] Zheng Y L, Ma L H, Zhang L Y, Qian J X. On the convergence analysis and parameter selection in particle swarm optimization. In: Proceedings of the 2nd International Conference on Machine Learning and Cybernetics. Xi'an, China: IEEE, 2003. 1802-1807[20] Zhang L P, Yu H J, Hu S X. Optimal choice of parameters for particle swarm optimization. Journal of Zhenjian University (Science), 2005, 6A(6): 528-534[21] Pan Feng, Chen Jie, Gan Ming-Gang, Cai Tao, Tu Xu Yan. Model analysis of particle swarm optimizer. Acta Automatica Sinica, 2006, 32(3): 368-375(潘峰, 陈杰, 甘明刚, 蔡涛, 涂序彦. 粒子群优化算法模型分析. 自动化学报, 2006, 32(3): 368-375)[22] Li Ning. Theory Analysis of Particle Swarm Optimization and Its Application Research [Ph.D. dissertation], Huazhong University of Science and Technology, China, 2007 (李宁. 粒子群优化算法的理论分析与应用研究 [博士学位论文], 华中科技大学, 中国, 2007)[23] Li Ning, Sun De-Bao, Zou Tong, Qin Yuan-Qing, Wei Yu. An analysis for a particle's trajectory of PSO based on difference equation. Chinese Journal of Computers, 2006, 29(11): 2052 -2061 (李宁, 孙德宝, 邹彤, 秦元庆, 尉宇. 基于差分方程的 PSO 算法粒子运动轨迹分析. 计算机学报, 2006, 29(11): 2052-2061)[24] Jin Xin-Lei, Ma Long-Hua, Wu Tie-Jun, Qian Ji-Xin. Convergence analysis of the particle swarm optimization based on stochastic processes. Acta Automatica Sinica, 2007, 33(12): 1263-1268 (金欣磊, 马龙华, 吴铁军, 钱积新. 基于随机过程的 PSO 收敛性分析. 自动化学报, 2007, 33(12): 1263-1268)[25] Ren Zi-Hui, Wang Jian, Gao Yue-Lin. The global convergence analysis of particle swarm optimization algorithm based on Markov chain. Control Theory and Applications, 2011, 28(4): 463-467 (任子晖, 王坚, 高岳林. 马尔科夫链的粒子群优化算法全局收敛性分析. 控制理论与应用, 2011, 28(4): 463-467)[26] Shen Yuan-Xia, Wang Guo-Yin. Probabilistic characteristics analysis of particle swarm optimization and its improved algorithm. Control and Decision, 2011, 21(6): 816-820 (申元霞, 王国胤. 粒子群优化算法的概率特性分析及算法改进. 控制与决策, 2011, 21(6): 816-820)[27] Liu Jian-Hua, Yang Rong-Hua, Sun Shui-Hua. The analysis of binary particle swarm optimization. Journal of Nanjing University (Natural Sciences), 2011, 47(5): 504-514 (刘建华, 杨荣华, 孙水华. 离散二进制粒子群算法分析. 南京大学学报 (自然科学版), 2011, 47(5): 504-514)[28] Horst R, Pardalos P M, Thoai N V [Author], Hao Si-Te [Translator]. Introduction to Global Optimization. Beijing: Tsinghua University Press, 2003. 120-207 (Horst R, Pardalos P M, Thoai N V [著], 郝斯特 [译]. 全局优化引论. 北京: 清华大学出版社, 2003. 120-207)

施引文献

资源附件(0)

访问统计