具有动态子空间的随机单维变异粒子群算法

doi:10.3778/j.issn.1673-9418.1908037

摘要/Abstract

摘要：

传统粒子群算法采用整体维度更新策略，常因某一维或某几维未达到最优解，导致粒子适应值变差。针对此问题，提出具有动态子空间的随机单维变异粒子群优化算法，从优质粒子全维空间中，构造动态子空间，并随机选择异于子空间的一维进行变异。子空间大小动态变化：前期选取多数维度组成子空间，增大变异维度的多样性；后期选取少数维度组成子空间，增强粒子精细搜索的能力。同时，根据Pareto定律，使种群在前期20%迭代次数内，探索新解空间区域，后期80%迭代次数内，进行有效的平衡搜索，加快种群收敛速度。使用多类型基准测试函数，在30、50和100维下进行仿真实验，结果表明，该算法在收敛速度和精度上，不仅优于新改进的粒子群算法，而且优于新改进的人工蜂群算法和萤火虫算法。

关键词: 粒子群优化算法（PSO）, 单维变异, 动态子空间, Pareto定律

Abstract:

The traditional particle swarm optimization algorithm adopts the overall dimension updating strategy, and the particle??s fitness value deteriorates frequently because the optimal solution is not reached in a certain dimension or a few dimensions. Aiming at this problem, a stochastic single-dimensional mutated particle swarm optimization algorithm with dynamic subspace is proposed. The dynamic subspace is constructed from the high-quality particle's dimension, and one-dimension different from the subspace is randomly selected to mutate. The subspace size changes dynamically. In the early stage, most of the dimensions are used to form the subspace, which increases the diversity of the mutated dimension. Later, a few dimensions are selected to form the subspace, which enhances the ability of the particle to search fine. At the same time, according to Pareto's law, the population explores the new solution space region within the first 20% iterations, and performs an effective balanced search within 80% of the iterations in the later period to accelerate the population convergence speed. Simulation experiments are carried out in 30, 50 and 100 dimensions using multi-type benchmark functions. The results show that the proposed algorithm is not only superior to state of the art particle swarm optimization algorithms, but also the artificial bee colony and firefly algorithm in convergence speed and precision.

Key words: particle swarm optimization (PSO), single-dimensional mutation, dynamic subspace, Pareto's law

邓志诚，孙辉，赵嘉，王晖. 具有动态子空间的随机单维变异粒子群算法[J]. 计算机科学与探索, 2020, 14(8): 1409-1426.

DENG Zhicheng, SUN Hui, ZHAO Jia, WANG Hui. Stochastic Single-Dimensional Mutated Particle Swarm Optimization with Dynamic Subspace[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(8): 1409-1426.

参考文献

[1] Kennedy J, Eberhart R. Particle swarm optimization[C]//Pro-ceedings of the 1995 International Conference on Neural Networks, Perth, Nov 27-Dec 1, 1995. Piscataway: IEEE, 1995: 1942-1948.
[2] Eberhart R, Kennedy J. A new optimizer using particle swarm theory[C]//Proceedings of the 1995 International Symposium on Micro Machine and Human Science, Nagoya, Oct 4-6, 1995. Piscataway: IEEE, 1995: 39-43.
[3] Zhao J, Sun H, Deng C Z, et al. Particle swarm optimization based adaptive image denoising in Shearlet domain[J]. Journal of Chinese Computer Systems, 2011, 32(6): 1147-1150.赵嘉, 孙辉, 邓承志, 等. 基于粒子群优化的Shearlet自适应图像去噪[J]. 小型微型计算机系统, 2011, 32(6): 1147-1150.
[4] Xu M, Zhang L, Du B, et al. A mutation operator accelerated quantum-behaved particle swarm optimization algorithm for hyperspectral endmember extraction[J]. Remote Sensing, 2017, 9(3): 197-184.
[5] Chou J S, Pham A D. Nature-inspired metaheuristic optim-ization in least squares support vector regression for obtaining bridge scour information[J]. Information Sciences, 2017, 399: 64-80.
[6] Sun H, Shi X L, Zhao J, et al. Hybrid algorithm of particle swarm optimization and artificial bee colony with its application in wireless sensor networks[J]. Sensor Letters, 2014, 12(2): 392-397.
[7] Sun H, Li J, Li W L, et al. A hybrid particle swarm optim-ization for wireless sensor network coverage problem[J]. Sensor Letters, 2012, 10(8): 1744-1750.
[8] Delice Y, Aydo?an E K, ?zcan U, et al. A modified particle swarm optimization algorithm to mixed-model two-sided assembly line balancing[J]. Journal of Intelligent Manuf-acturing, 2017, 28(1): 23-36.
[9] Yuan L, Ge H W, Jiang D Y. Partical swarm optimization algorithm with adaptive filter based on health degree[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(2): 332-340.袁罗, 葛洪伟, 姜道银. 基于健康度的自适应过滤粒子群算法[J]. 计算机科学与探索, 2018, 12(2): 332-340.
[10] Jiang L, Ye R Z, Liang C Y, et al. Improved second-order oscillatory particle swarm optimization[J]. Computer Engin-eering and Applications, 2019, 55(9): 130-138.蒋丽, 叶润舟, 梁昌勇, 等. 改进的二阶振荡粒子群算法[J]. 计算机工程与应用, 2019, 55(9): 130-138.
[11] Zhang X, Zou D X, Xiao P, et al. Self-adjusted simplified particle swarm optimization algorithm and its application[J]. Computer Engineering and Applications, 2019, 55(8): 250-263.张鑫, 邹德旋, 肖鹏, 等. 自适应简化粒子群优化算法及其应用[J]. 计算机工程与应用, 2019, 55(8): 250-263.
[12] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58-73.
[13] Zhao J, Lv L, Wang H, et al. Particle swarm optimization based on vector Gaussian learning[J]. KSII Transactions on Internet and Information Systems, 2017, 11(4): 2038-2057.
[14] Hakli H, U?uz H. A novel particle swarm optimization algorithm with Levy flight[J].Applied Soft Computing, 2014, 23: 333-345.
[15] Li S F, Cheng C Y. Particle swarm optimization with fitness adjustment parameters[J]. Computers & Industrial Engineering, 2017, 113: 831-841.
[16] Lin Z, Zhang Q. An effective hybrid particle swarm opt-imization with Gaussian mutation[J]. Journal of Algorithms & Computational Technology, 2017, 11(3): 271-280.
[17] Yan B L, Zhao Z, Zhou Y C, et al. A particle swarm optimization algorithm with random learning mechanism and Levy flight for optimization of atomic clusters[J]. Computer Physics Communications, 2017, 219: 79-86.
[18] Chen K, Zhou F Y, Yin L, et al. A hybrid particle swarm optimizer with sine cosine acceleration coefficients[J]. Infor-mation Sciences, 2018, 422: 218-241.
[19] Anderson C. The long tail[M]. Beijing: CITIC Press, 2006: 10-12.安德森. 长尾理论[M]. 乔江涛, 译. 北京: 中信出版社, 2006: 10-12.
[20] Trelea I C. The particle swarm optimization algorithm: convergence analysis and parameter selection[J]. Information Processing Letters, 2003, 85(6): 317-325.
[21] Ratnaweera A, Halgamuge S K, Watson H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 240-255.
[22] Liang J J, Qin A K, Suganthan P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolu-tionary Computation, 2006, 10(3): 281-295.
[23] Liang J J, Suganthan P N. Dynamic multi-swarm particle swarm optimizer[C]//Proceedings of the 2005 IEEE Swarm Intelligence Symposium, Pasadena, Jun 8-10, 2005. Pisca-taway: IEEE, 2005: 124-129.
[24] Jensi R, Jiji G W. An enhanced particle swarm optimization with Levy flight for global optimization[J]. Applied Soft Computing, 2016, 43: 248-261.
[25] Ouyang H, Gao L, Li S, et al. Improved global-best-guided particle swarm optimization with learning operation for global optimization problems[J]. Applied Soft Computing, 2017, 52: 987-1008.
[26] Liu Z G, Ji X H, Liu Y X. Hybrid non-parametric particle swarm optimization and its stability analysis[J]. Expert Systems with Applications, 2018, 92: 256-275.
[27] Sun H, Xie H H, Zhao J. Global optical guided artificial bee colony algorithm based on sinusoidal selection probability model[J]. Journal of Nanchang Institute of Technology, 2018, 37(6): 84-90.孙辉, 谢海华, 赵嘉. 正弦选择概率模型的全局最优引导人工蜂群算法[J]. 南昌工程学院学报, 2018, 37(6):84-90.
[28] Karaboga D, Akay B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation, 2009, 214(1): 108-132.
[29] Karaboga D, Basturk B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2008, 8(1): 687-697.
[30] Zhu G P, Kwong S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173.
[31] Karaboga D, Gorkemli B. A quick artificial bee colony (qABC) algorithm and its performance on optimization problems[J]. Applied Soft Computing, 2014, 23: 227-238.
[32] Banharnsakun A, Achalakul T, Sirinaovakul B. The best-so-far selection in artificial bee colony algorithm[J]. Applied Soft Computing, 2011, 11(2): 2888-2901.
[33] Kiran M S, Findik O. A directed artificial bee colony alg-orithm[J]. Applied Soft Computing, 2015, 26: 454-462.
[34] Gao W, Liu S. A modified artificial bee colony algorithm[J]. Computers & Operations Research, 2012, 39(3): 687-697.
[35] Cui L Z, Zhang K, Li G H, et al. Modified Gbest-guided artificial bee colony algorithm with new probability model [J]. Soft Computing, 2018, 22(7): 2217-2243.
[36] Chen Q, Liu B, Zhang Q, et al. Problem definition and evaluation criteria for CEC 2015 special session on bound constrained single-objective computationally expensive num-erical optimization[R]. Zhengzhou: Zhengzhou University, 2014.
[37] Yu S H, Zhu S L, Ma Y, et al. A variable step size firefly algorithm for numerical optimization[J]. Applied Mathematics and Computation, 2015, 263: 214-220.
[38] Yu S H, Su S B, Lu Q P, et al. A novel wise step strategy for firefly algorithm[J]. International Journal of Computer Math-ematics, 2014, 91(12): 2507-2513.
[39] Kora P, Krishna K S R. Hybrid firefly and particle swarm optimization algorithm for the detection of bundle branch block[J]. International Journal of the Cardiovascular Academy, 2016, 2(1): 44-48.