融合哈密顿图的麻雀与算术混合优化算法

doi:10.3778/j.issn.1673-9418.2110060

摘要/Abstract

摘要： 针对麻雀搜索算法（SSA）迭代后期种群多样性减少、易陷入局部最优等问题，提出一种基于哈密顿图的麻雀算术混合优化算法（HSSAAOAH）。首先，在SSA发现者-跟随者模型和侦察机制的基础上，引入算术优化算法（AOA）的乘除算子。利用乘除算子的高分布性，提高算法在迭代后期解的多样性；其次，将种群中所有个体转化成一个无向加权图，在每一轮迭代后，使用改良圈算法计算个体构成的哈密顿环长度，根据相邻两代长度的比值衡量种群收敛趋势；然后，对于没能有效收敛的子代，随机生成一定数量的个体并使用贪婪策略进行选择，替代表现较差的个体，提高解的质量，增强跳出局部极值的能力；最后，将HSSAAOAH与不同优化算法在基准函数和两个工程设计问题上进行仿真实验，结果表明HSSAAOAH算法收敛速度更快，寻优精度更高，具有良好的鲁棒性和寻优性能。

关键词: 麻雀搜索算法（SSA）, 算术优化算法（AOA）, 哈密顿图, 改良圈算法

Abstract: Aiming at the shortcomings of sparrow search algorithm (SSA), such as decreased population diversity in the late iteration and easily falling into local optimal solution, a hybrid algorithm of sparrow search algorithm and arithmetic optimization algorithm based on Hamiltonian graph (HSSAAOAH) is proposed. Firstly, the multiplica-tion and division operator of arithmetic optimization algorithm (AOA) is introduced into the discoverer-follower model and reconnaissance mechanism of SSA. The high distribution of multiplication and division operator is used to improve the randomness of later optimization. Secondly, the population composed by all the individuals is transferred into an undirected weight graph. After each iteration, a Hamiltonian cycle and its length composed of individuals will be computed according to a modified cycle algorithm, and the population optimization trend is measured by the ratio of the Hamiltonian cycle length. Then, for the progeny that fails to perform effective convergence, a certain number of individuals are randomly generated to replace the last ones according to the greedy algorithm, which improves the quality of solution and enhances the ability to jump out of local extrema. Finally, HSSAAOAH and different optimization algorithms are simulated on the benchmark function and two engineering design problems. The results show that HSSAAOAH algorithm has faster convergence speed, higher optimization accuracy, and good robustness and optimization performance.

Key words: sparrow search algorithm (SSA), arithmetic optimization algorithm (AOA), Hamiltonian graph, modified cycle algorithm

田露, 刘升. 融合哈密顿图的麻雀与算术混合优化算法[J]. 计算机科学与探索, 2023, 17(7): 1586-1598.

TIAN Lu, LIU Sheng. Hybrid Algorithm of Sparrow Algorithm and Arithmetic Optimization Algorithm Based on Hamiltonian Graph[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(7): 1586-1598.

参考文献

[1] 王凌. 智能优化算法及其应用[M]. 北京：清华大学出版社, 2001．
WANG L. Intelligent optimization algorithm and its appli-cation[M]. Beijing: Tsinghua University Press, 2001.
[2] 张松灿, 普杰信, 司彦娜, 等. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
ZHANG S C, PU J X, SI Y N, et al. Adaptive improved ant colony algorithm based on population similarity and its app-lication[J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[3] 卜冠南, 刘建华, 姜磊, 等. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
BU G N, LIU J H, JIANG L, et al. Ant colony algorithm with adaptive grouping[J]. Computer Engineering and App-lications, 2021, 57(6): 67-73.
[4] 王贵程, 吴国新, 左云波, 等. 基于改进蚁群算法包装机器人轨迹规划研究[J]. 电子测量与仪器学报, 2019, 33(8):100-106.
WANG G C, WU G X, ZUO Y B, et al. Research on trajec-tory planning of packaging robot based on improved ant colony algorithm[J]. Journal of Electronic Measurement and Instrumentation, 2019, 33(8): 100-106.
[5] MAHESHWARI P, AJAY K S, VERMA K. Energy efficient cluster based routing protocol for WSN using butterfly opti-mization algorithm and ant colony optimization[J]. Ad Hoc Networks, 2020, 110: 102317.
[6] 薛建凯, 沈波. 一种新型群智能优化算法：麻雀搜索算法[J]. 系统科学与控制工程, 2020, 8(1): 22-34.
XUE J K, SHEN B. A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34.
[7] 何国松, 董泽, 孙明. 基于混合量子麻雀算法的过热汽温模型参数辨识[J]. 华北电力大学学报(自然科学版), 2023(1): 92-100.
HE G S, DONG Z, SUN M. Parameter identification of superheated steam temperature model based on hybrid quantum sparrow algorithm[J]. Journal of North China Electric Power University (Natural Science Edition), 2023(1): 92-100.
[8] 高兵, 郑雅, 秦静, 等. 基于麻雀搜索算法和改进粒子群优化算法的网络入侵检测算法[J]. 计算机应用, 2022, 42(4): 1201-1206.
GAO B, ZHENG Y, QIN J, et al. Network intrusion detection algorithm based on sparrow search algorithm and improved particle swarm optimization algorithm[J]. Journal of Computer Applications, 2022, 42(4): 1201-1206.
[9] 付华, 刘昊. 多策略融合的改进麻雀搜索算法及其应用[J]. 控制与决策, 2022, 37(1): 87-96.
FU H, LIU H. Improved sparrow search algorithm with multi-strategy integration and its application[J]. Control and Deci-sion, 2022, 37(1): 87-96.
[10] ABUALIGAH L, DIANAT A, MIRJALILI S, et al. The arithmetic optimization algorithm[J]. Computer Methods in Applied Mechanics and Engineering, 2021, 376: 113609.
[11] 王海英, 黄强, 李传涛, 等. 图论算法及其MATLAB实现[M]. 北京: 北京航空航天大学出版社, 2010.
WANG H Y, HUANG Q, LI C T, et al. Graph theory algorithm and its MATLAB implementation[M]. Beijing: Beihang University Press, 2010.
[12] SOLIS F J, WETS J B. Minimization by random search techniques[J]. Mathematics of Operations Research, 1981, 6(1): 19-30.
[13] 毛清华, 张强. 融合柯西变异和反向学习的改进麻雀算法[J]. 计算机科学与探索, 2021, 15(6): 1155-1164.
MAO Q H, ZHANG Q. Improved sparrow algorithm com-bining Cauchy mutation and opposition-based learning[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(6): 1155-1164.
[14] 唐延强, 李成海, 宋亚飞, 等. 自适应变异麻雀搜索优化算法[J]. 北京航空航天大学学报, 2023, 49(3): 681-692.
TANG Y Q, LI C H, SONG Y F, et al. Adaptive mutation sparrow search optimization algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2023, 49(3): 681-692.
[15] MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
[16] 严逍亚, 王振雷, 王昕. 动态调整成长方式的郊狼优化算法及其应用[J]. 计算机工程, 2022, 48(7): 73-81.
YAN X Y, WANG Z L, WANG X. Coyote optimization algorithm with dynamically adjusting growth mode and its application[J]. Computer Engineering, 2022, 48(7): 73-81.
[17] HE Q, WANG L. An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J]. Engineering Applications of Artificial Intelligence, 2007, 20(1): 89-99.