-
摘要:
为改善麻雀搜索算法(SSA)在单种群搜索中收敛速度过快导致其收敛速度出现冗余,易忽略优质解而陷入局部最优的缺陷,提出一种基于K-means聚类的多种群麻雀搜索算法(KSSA)。将多种群机制引入SSA,减弱单种群的收敛能力,并减小陷入局部最优的概率;采用K-means聚类划分子种群,增加子种群间的差异性,同时使子种群内个体在小范围内专注搜索,提升前期搜索效率;借助加权重心交流策略改善种群间交流的质量,减少自身种群的干扰,同时消减因某一子种群陷入局部最优而导致所有子种群陷入局部最优的风险;引入动态反向学习到警戒者中,增强其反捕食行为,改善因子种群数量增加而带来的收敛速度变慢和收敛精度不足的缺陷。经测试函数仿真实验表明:较SSA等算法,KSSA具有更优的寻优性能。
Abstract:A K-means multi-group sparrow search algorithm (KSSA) based on K-means clustering is proposed in order to improve the convergence speed of the sparrow search algorithm (SSA) in single population search, which causes redundancy in its convergence speed and makes it simple to ignore the flaw that the high-quality solution falls into local optimization. Firstly, the multi-population mechanism is introduced into SSA to weaken the convergence ability of a single population and reduce the probability of falling into local optimization. Secondly, in order to boost the effectiveness of early search, the sub-population is divided, the differences between the sub-populations are increased, and the members of the sub-population are forced to concentrate on searching within a certain area Then, the weighted center of gravity communication strategy is used to improve the quality of population communication, reduce the interference of its own population, and reduce the risk of all sub populations falling into local optimization due to a sub population falling into local optimization. Finally, dynamic reverse learning is introduced into vigilant to enhance their back feeding behavior and improve the defects of slow convergence speed and insufficient convergence accuracy caused by the increase of factor population. Through the test function simulation experiment, it is proved that KSSA has better optimization performance than SSA and other algorithms.
-
表 1 算法参数
Table 1. Algorithm parameter
表 2 测试函数
Table 2. Test function
类型 函数 维度 搜索区域 理论最优值 单峰 ${F_1}\left( x \right) = \mathop \sum \limits_{i = 1}^n x_i^2$ 30 [−100,100] 0 $ {F_2}\left( x \right) = \mathop \sum \limits_{i = 1}^n \left( {\sum\limits_{j = 1}^i {x_j^2} } \right) $ 30 [−100,100] 0 ${F_3}\left( x \right) = \mathop \sum \limits_{i = 1}^{n - 1} \left[ {100{{({x_{i + 1}} - x_i^2)}^2} + {{({x_i} - 1)}^2}} \right]$ 30 [−100,100] 0 ${F_4}\left( x \right) =\mathop \sum \limits_{i = 1}^n {\left( {\left[ {{x_i} + 0.5} \right]} \right)^2}$ 30 [−100,100] 0 多峰 ${F_5}\left( x \right) = \mathop \sum \limits_{i = 1}^n - {x_i}\sin \left( {\sqrt {\left| {{x_i}} \right|} } \right)$ 30 [−500,500] −418.98 n $ {F_6}(x) = \sum\limits_{i = 1}^n {\left[ {x_i^2 - 10\cos \left( {2{\text{π}} {x_i}} \right) + 10} \right]} $ 30 [−5.12,5.12] 0 $ \begin{gathered} {F_7}\left( x \right) = \dfrac{{\text{π}} }{n}\Bigg\{ {10{\mathrm{sin}}\left( {{\text{π}} {y_1}} \right) + \textstyle\sum\limits_{i = 1}^{n - 1} {{\left( {{y_i} - 1} \right)}^2}\left[ {1 + 10{{\mathrm{sin}}^2}\left( {{\text{π}} {y_{i + 1}}} \right)} \right] + } \\\quad\quad{{{\left( {{y_n} - 1} \right)}^2}} \Bigg\} + \textstyle\sum \limits_{i = 1}^n u\left( {{x_i},10,100,4} \right)\quad\quad{y_i} = 1 + \dfrac{{{x_i} + 1}}{4} \end{gathered} $ 30 [−50,50] 0 $ \begin{gathered} {F_8}\left( x \right) = 0.1\left\{ {{{\mathrm{sin}}^2}\left( {3{\text{π}} {x_1}} \right) + \textstyle\sum \limits_{i = 1}^n {{\left( {{x_i} - 1} \right)}^2}\left[ {1 + {{\mathrm{sin}}^2}\left( {3{\text{π}} {x_i} + 1} \right)} \right] + } \right. \\ \quad\quad\left. {{{\left( {{x_n} - 1} \right)}^2}\left[ {1 + {{\mathrm{sin}}^2}\left( {2{\text{π}} {x_n}} \right)} \right]} \right\} + \textstyle\sum \limits_{i = 1}^n u\left( {{x_i},5,100,4} \right) \\ \end{gathered} $ 30 [−50,50] 0 表 3 测试函数结果对比
Table 3. Comparison of test function results
算法 最优值 F1 F2 F3 F4 F5 F6 F7 F8 PSO 7.37×10−6 4.50×101 1.76×101 1.10×10−5 −7.99×103 3.23×101 4.47×10−8 5.51×10−6 WOA 3.80×10−84 1.11×104 2.69×101 9.79×10−2 −1.26×104 0 8.75×10−3 6.90×10−2 GWO 7.48×10−28 5.52×10−8 2.59×101 2.46×10−1 −7.45×103 0 8.04×10−3 1.97×10−1 SSA 0 0 0 0 −1.26×104 0 1.57×10−32 1.35×10−32 GSSA 0 0 6.05×10−10 1.36×10−12 −1.26×104 0 2.24×10−13 7.06×10−13 CSSA 0 0 6.05×10−10 1.36×10−12 −1.26×104 0 2.24×10−13 7.06×10−13 KSSA 0 0 0 0 −1.26×104 0 1.57×10−32 1.35×10−32 算法 平均值 F1 F2 F3 F4 F5 F6 F7 F8 PSO 2.35×10−4 9.21×101 8.62×101 2.62×10−4 −5.13×103 5.69×101 6.91×10−3 7.01×10−3 WOA 9.85×10−75 4.22×104 2.80×101 4.04×10−1 −1.06×104 3.79×10−15 2.50×10−2 5.92×10−1 GWO 3.17×10−26 4.52×10−5 2.69×101 5.90×10−1 −5.45×103 8.49×10−1 3.92×10−2 5.58×10−1 SSA 1.55×10−73 3.28×10−61 1.36×10−5 1.10×10−8 −9.06×103 0 1.30×10−9 2.71×10−8 GSSA 0 0 1.09×10−4 3.51×10−9 −1.11×104 0 7.55×10−10 3.92×10−9 CSSA 0 0 1.09×10−4 3.51×10−9 −1.11×104 0 7.55×10−10 3.92×10−9 KSSA 0 0 4.05×10−7 4.45×10−8 −1.20×104 0 3.79×10−27 1.35×10−32 算法 标准差 F1 F2 F3 F4 F5 F6 F7 F8 PSO 4.11×10−4 4.13×101 5.72×101 6.59×10−4 1.41×103 1.50×101 3.79×10−2 9.64×10−3 WOA 2.78×10−74 1.64×104 5.38×10−1 1.98×10−1 1.85×103 2.08×10−14 1.60×10−2 3.52×10−1 GWO 5.04×10−26 9.41×10−5 7.74×10−1 3.16×10−1 1.02×103 2.80×100 1.90×10−2 2.09×10−1 SSA 8.48×10−73 1.49×10−60 5.86×10−5 2.34×10−8 1.66×103 0 3.85×10−9 1.14×10−7 GSSA 0 0 2.58×10−4 9.68×10−9 1.02×103 0 1.56×10−9 6.94×10−9 CSSA 0 0 2.58×10−4 9.68×10−9 1.02×103 0 1.56×10−9 6.94×10−9 KSSA 0 0 1.20×10−6 2.29×10−7 7.17×102 0 2.08×10−26 5.57×10−48 算法 P F1 F2 F3 F4 F5 F6 F7 F8 PSO 1.21×10−12 1.21×10−12 2.63×10−11 1.79×10−11 2.92×10−11 1.21×10−12 1.72×10−12 1.21×10−12 WOA 1.21×10−12 1.21×10−12 2.63×10−11 1.79×10−11 1.12×10−2 3.34×10−1 1.72×10−12 1.21×10−12 GWO 1.21×10−12 1.21×10−12 2.63×10−11 1.79×10−11 2.92×10−11 4.39×10−12 1.72×10−12 1.21×10−12 SSA 6.25×10−10 1.66×10−11 7.53×10−4 3.47×10−3 5.87×10−8 Na 6.93×10−12 4.57×10−12 GSSA Na Na 1.31×10−1 6.27×10−4 2.30×10−10 Na 2.67×10−11 4.57×10−12 CSSA Na Na 2.86×10−9 4.28×10−4 1.75×10−3 Na 1.72×10−12 1.21×10−12 KSSA 注:Na表示本文算法与其他算法相比几乎相同。 -
[1] XUE J K, SHEN B. A novel swarm intelligence optimization approach: Sparrow search algorithm[J]. Systems Science & Control Engineering an Open Access Journal, 2020, 8(1): 22-34. [2] KENNEDY J, EBERHART J. Particle swarm optimization[C]//Proceedings of ICNN’95-International Conference on Neural Networks. Piscataway: IEEE Press, 2022: 1942-1948. [3] WHITLEY D. A genetic algorithm tutorial[J]. Statistics and Computing, 1994, 4(2): 65-85. [4] 闫少强, 杨萍, 朱东林, 等. 基于佳点集的改进麻雀搜索算法[J]. 北京航空航天大学学报, 2023, 49(10): 2790-2798. doi: 10.13700/j.bh.1001-5965.2021.0730YAN S Q, YANG P, ZHU D L, et al. Improved sparrow search algorithm based on good point set[J]. Journal of Beijing University of Aeronautics and Astronautics, 2023, 49(10): 2790-2798 (in Chinese). doi: 10.13700/j.bh.1001-5965.2021.0730 [5] 吕鑫, 慕晓冬, 张钧, 等. 混沌麻雀搜索优化算法[J]. 北京航空航天大学学报, 2021, 47(8): 1712-1720. doi: 10.13700/j.bh.1001-5965.2020.0298LYU X, MU X D, ZHANG J, et al. Chaos sparrow search optimization algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(8): 1712-1720 (in Chinese). doi: 10.13700/j.bh.1001-5965.2020.0298 [6] NASIRI J, KHIYABANI F M. A whale optimization algorithm (WOA) approach for clustering[J]. Cogent Mathematics & Statistics, 2018, 5(1): 1483565. [7] MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61. doi: 10.1016/j.advengsoft.2013.12.007 [8] ZHANG X X, CHEN W R, DAI C H, et al. Dynamic multi-group self-adaptive differential evolution algorithm for reactive power optimization[J]. International Journal of Electrical Power & Energy Systems, 2010, 32(5): 351-357. [9] OUYANG J, YAN G R. A multi-group ant colony system algorithm for TSP[C]//Proceedings of 2004 International Conference on Machine Learning and Cybernetics. Piscataway: IEEE Press, 2005: 117-121. [10] ZANDIEH M, KARIMI N. An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times[J]. Journal of Intelligent Manufacturing, 2011, 22(6): 979-989. doi: 10.1007/s10845-009-0374-7 [11] MARINAKIS Y, MARINAKI M. A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem[J]. Computers & Operations Research, 2010, 37(3): 432-442. [12] WANG Y, CAI Z X. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems[J]. Frontiers of Computer Science in China, 2009, 3(1): 38-52. doi: 10.1007/s11704-009-0010-x [13] LIANG J J, SUGANTHAN P N. Dynamic multi-swarm particle swarm optimizer[C]//Proceedings 2005 IEEE Swarm Intelligence Symposium. Piscataway: IEEE Press, 2005: 124-129. [14] XIA X W, LIU J N, LI Y X. Particle swarm optimization algorithm with reverse-learning and local-learning behavior[J]. Journal of Software, 2014, 9(2): 350-357. [15] HE J, PENG Z, CUI D, et al. A teaching and learning optimization algorithm based on multi-inverse learning[J]. Engineering Science and Technology, 2019, 51(6): 159-167.