基于自适应t分布与随机游走的麻雀搜索算法_聂方鑫.pdf

2023 年第 36 卷第 7 期Electronic Sci.Tech./Jul.15，2023https:/收稿日期:2022-03-17基金项目:国家自然科学基金(61703270)National Natural Science Foundation of China(61703270)作者简介:聂方鑫(1996 )，男，硕士研究生。研究方向:进化计算。王宇嘉(1979 )，女，博士，副教授。研究方向:群智能算法、进化计算。基于自适应t分布与随机游走的麻雀搜索算法聂方鑫，王宇嘉(上海工程技术大学 电子电气工程学院，上海 201620)摘要针对麻雀搜索算法在解决复杂问题时存在的收敛精度降低以及陷入局部最优等问题，文中提出了一种基于自适应 t 分布与随机游走的麻雀搜索算法。该算法在初始化过程中使用反向学习来生成反向解，从中选择优秀的个体组成初始化种群。在原始麻雀搜索算法上采用自适应 t 分布策略和高斯随机游走策略可以提高麻雀个体的寻优能力，同时防止算法早熟。仿真结果表明，相较于对比算法，文中所提算法的收敛精度和收敛速度都有所提升。关键词麻雀搜索算法;自适应 t 分布;反向学习策略;随机游走策略;函数优化;局部最优;全局最优;优化算法中图分类号TP301 6文献标识码A文章编号1007 7820(2023)07 075 06doi:10.16180/ki.issn1007 7820.2023.07.011Sparrow Search Algorithm Based on Adaptive t Distribution andandom WalkNIE Fangxin，WANG Yujia(School of Electronic and Electrical Engineering，Shanghai University of Engineering Science，Shanghai 201620，China)AbstractIn view of the problems of low convergence accuracy and falling into local optimum when solvingcomplex problems，a sparrow search algorithm based on adaptive t distribution and random walk is proposed in thisstudy In the initialization process，the algorithm uses reverse learning to generate reverse solutions from which excel-lent individuals are selected to form the initial population In the original sparrow search algorithm，the adaptive t distribution strategy and Gaussian random walk strategy are used to improve the optimization ability of the sparrow in-dividuals，and can prevent the algorithm from premature The simulation results show that the proposed algorithm im-proves the convergence accuracy and convergence speed when compared with the comparison algorithmKeywordssparrow search algorithm;adaptive t distribution;opposition based learning strategy;randomwalk strategy;function optimization;local optimum;global optimum;optimistic algorithm麻雀搜索算法(Sparrow Search Algorithm，SSA)1 属于群智能优化算法。SSA 因具有寻优能力强、收敛速度快等优点，被广泛应用于各个领域2 4。但 SSA与粒子群优化算法5 和萤火虫算法6 存在相同的问题，其在勘探能力上存在不足，并且有陷入局部最优的趋势。为了解决上述的 SSA 问题，文献 7提出了一种多策略 SSA。该算法采用均匀 多样化定向策略帮助初始种群提高多样性和随机性，然后在危险感知转移策略中避免算法进入停滞状态，并在动态演化策略中引入三角形相似理论来提高算法的搜索能力。文献 8 提出一种混沌 SSA，该算法利用混沌映射初始化过程中个体的位置，使个体更接近最优点。此外，该算法使用两个自适应超参数来更新发现者的位置和警戒者的数量，并采用变异算子提高种群的多样性，有效提高了 SSA 的寻优能力。文献 9提出了一种自适应SSA，该算法分别在发现者、加入者和警戒者位置更新时引入一个自适应学习因子，从而提高麻雀个体的开采能力。文献 10 提出了一种改进的 SSA，该算法中的个体根据自身位置采用不同的更新策略来加快算法收敛速度。为了防止陷入停滞，该算法还引入了聚集度来提高种群的多样性。文献 11提出了一种基于逐维高斯变异的混沌 SSA，该算法为了解决初始化过程中个体随机分布的问题，采用 Singer 混沌映射使种群均匀分布，并采用一种新颖的翻筋斗觅食策略12 来帮助麻雀个体跳出局部最优，最后采用高斯变异来提高算法的勘探能力。虽然现有的改进 SSA 提高了优化性能，但这些算57Electronic Science and Technology聂方鑫，等:基于自适应 t 分布与随机游走的麻雀搜索算法https:/法仍然存在局限性和不确定性，容易陷入局部最优，无法获得更好的收敛精度，影响了原 SSA 的优化性能。因此，为了提高 SSA 的综合优化性能并解决 SSA 的这些缺点，本文提出了一种基于自适应 t 分布与随机游走的麻雀搜索算法(Sparrow Search Algorithm Based onAdaptive t Distribution and andom Walk，ASSA)，采用 3 种策略改进并提高了原 SSA 的性能。1麻雀搜索算法在 SSA 中有 3 种不同类型的麻雀，每个麻雀都对应于所求解问题的一个解13。第 1 种麻雀被称为发现者，它在种群中处于领导地位，负责为整个种群中的其它个体提供搜索方向，从而获得食物，其适应度值在种群中处于领先位置。第 2 种麻雀被称为加入者，它会通过跟随发现者来获得食物，以提高自身适应度值。第 3 种麻雀被称为警戒者，负责观察周围的同伴和危险的捕食者，从而提高捕食成功的概率和风险防范能力。发现者和警戒者之间可以转换，但是在种群中的比例不变。由 n 只麻雀所构成的种群及其空间位置由式(1)所示X=x1，1x1，2x1，dx2，1x2，2x2，dxn，1xn，2xn，d(1)式中，d 是决策变量的维数;n 是麻雀个体的数量。在模型中，发现者的位置更新如式(2)所示XT+1i，j=XTi，j exp i iter()max，2 STXTi，j+Q L，2ST(2)式中，XTi，j表示在第 T 次迭代中，第 i 个麻雀在第 j 维的位置;rand(0，1;itermax是最大迭代次数;2rand 0，1表示预警值;ST rand 0 5，1表示安全值;2 ST 表示周围没有发现危险，发现者可以在搜索空间中寻找食物;2 ST 表示有麻雀意识到了危险，需要所有麻雀立即飞往其它安全位置捕食;Q 是服从标准正态分布的随机数;L是1 d的矩阵，每个元素都为 1。加入者的位置更新如式(3)所示XT+1i，j=Q expXworst XTi，ji()2，i n/2XT+1p+XTi，j XT+1p A+L，otherwise(3)式中，Xp是发现者历史最优位置;Xworst是当前种群最差位置;A 是 1 d 的矩阵，每个元素随机赋值为 1 或 1，其中A+=AT(AAT)1。当i n/2 时，此时加入者的适应度值排名靠后，表明该麻雀获取的食物不够，需要到其它地方获得食物来补充能量;否则就在发现者所处位置的附近获取食物。在觅食活动中，假设意识到危险的这些麻雀，即警戒者，占整个种群的 10%20%。当它们意识到任何不确定的危险时，会为了安全立即靠近其他麻雀或进行其他反捕食行为。其位置更新如式(4)所示XT+1i，j=XTbest+XTi，j XTbest，fi fgXTi，j+K XTi，j XTworstfi f()w+()，fi=fg(4)式中，Xbest表示全局最优位置;是服从标准正态分布的随机数，表示步长控制参数;K rand 1，1;fi是麻雀的适应度值;fg是全局最优适应度值;fw是全局最劣适应度值;K 是当前麻雀移动方向的参数;是起调节的参数，可以避免分母为0。当fi fg时，表示警戒者处于种群的边缘，此时易被天敌捕食;当 fi=fg时，表示警戒者处于种群中心，必须接近其它麻雀来降低被捕获的危险。2自适应t分布与随机游走的麻雀搜索算法2 1精英初始化策略反向学习策略14 可以有效增加种群的多样性，并证明反向解有 50%的可能性比当前解更接近于全局最优点。假设在 d 维搜索空间中，个体是 Xi=(x1，x2，x3，xd)，其反向解为 X*i=(x*1，x*2，x*3，x*d)，数学表征如式(5)所示x*i=r(a+b)xi(5)式中，r 是0 1 之间的随机数;a 和 b 是 xi的上界和下界。在初始化种群的过程中，当前种群中的所有个体可以通过反向学习先得到一个反向种群，然后再在当前种群和反向种群中选取适应度值排名靠前的个体构建初始化种群。此时不但可以提高解的质量，还增加了种群中个体的探索性，同时也能够有效地防止算法早熟。2 2自适应t分布策略高斯分布(Gaussian Distribution，GD)和柯西分布(Cauchy Distribution，CD)都已经被证明可以有效地提升算法的优化能力，其中 GD 可以增强个体在最优点附近的搜索能力，加快算法的收敛速度，CD 可以增强个体在解空间中的搜索能力，增加种群的多样性。t 分布同时具有 GD 和 CD 这两者的优点15。自由度参数67聂方鑫，等:基于自适应 t 分布与随机游走的麻雀搜索算法Electronic Science and Technologyhttps:/为 m 的 t 分布概率密度函数如式(6)所示。pt(x)=m+1()2mm()21+x2()mm+12，x +(6)本文把 t 分布的自由度参数设置为 T。在算法迭代开始时，t 分布和 GD 比较相似，随着 T 增加，t 也会增加，t分布逐渐由CD慢慢转变为GD。基于上述分析，由于发现者在种群中处于领导位置，因此采用自适应t分布改进发现者的位置更新计算式，可以帮助发现者更快地搜索到最优点，如式(7)所示。Xt+1i，j=Xti，j(1+t(T)，2 STXti，j+t(T)L，2ST(7)式中，=1 i/itermax。在迭代初期，t分布与CD相似，发现者在搜索空间中具有较强的勘探能力。在迭代中期，t 分布在 CD 和GD 之间，可以使算法的收敛性和种群多样性在迭代过程中保持平衡。在迭代后期，t 分布和 GD 类似，此时发现者可以在最优点附近进行搜索，具有良好的局部开采能力，可以使算法快速收敛到最优点。2 3高斯随机游走策略当种群中最优的个体在迭代过程中不能搜索到更好的适应度值时，此时算法迭代进入停滞状态。随机游走模型中的高斯随机游走策略(Gaussian andomWalk Strategy，GWS)可以利用种群中适应度值最好的个体对所有个体的位置进行调整，从而对整个种群中的所有个体进行扰动，帮助个体跳出局部最优点。基于最优个体的 GWS 如式(8)和式(9)所示。XTi，G=Gaussian(XTbest，)+(r1 XTbest r2 XTi)(8)=log(T)T(XTi XTbest)(9)式中，XTi，G表示的是在第 T 次迭代中，个体 i 经过扰动后所生成的新个体;r1和r2是0 1 之间的均匀分布的随机数;r1 XTbest r2 XTi表示的是个体 i 的搜索方向;的值跟 T 是负相关关系。从式(8)和式(9)中可以得出，GWS 利用种群中适应度值最好的个体对其它个体进行扰动后产生了新的随机种群。扰动后的个体分布在适应度值最好的个体附近，帮助适应度值最好的个体寻找到最优点，不仅增强了算法的开采能力，还帮助最优个体跳出局部最优点。2 4ASSA 算法步骤ASSA 算法流程如图 1 所示。图 1 ASSA 流程Figure 1 Flow chart of the ASSA3仿真实验3 1测试函数为了检验 ASSA 的优化效果，选取 10 个测试函数进行仿真对比，下面给出了这 10 个测试函数的数学描述，维数 d 分别取 30 和 100。F1函数di=1x2i(10)式中，xi 100，100，最优值为 0。F2函数di=1xi+di=1xi(11)式中，xi 10，10，最优值为 0。F3函数di=1ij=1x()j2(12)式中，xi 100，100，最优值为 0。F4函数max1idxi(13)式中，xi 100，100，最优值为 0。F5函数di=1100(xi+1 x2i)2+(1 x2i)2(14)式中，xi 30，30，最优值为 0。F6函数di=1xi+52(15)77Electronic Science and Technology聂方鑫，等:基于自适应 t 分布与随机游走的麻雀搜索算法https:/式中，xi 100，100，最优值为 0。F7函数di=1i x4i+rand 0，1(16)式中，xi 128，128，最优值为 0。F8函数di=1 xisinxi(17)式中，xi 500，500，最优值为 418 982 9 d。F9函数di=1x2i 10cos(2xi)+10(18)式中，xi 5 12，5 12，最优值为 0。F10函数14 000di=1x2idi=1cos(xii)+1(19)式中，xi 600，600，最优值为 0。3 2算法设置本文 将 提 出 的 ASSA 算 法 与 EGWO16、TL-BO17、SSA1、自适应变异 SSA(AMSSA)18、基于等级制度与布朗运动的混沌 SSA(CSSAHB)19 进行仿真对比。在实验中，所有算法的参数设置如表 1 所示，其中 PD 为发现者的数量，SD 为警戒者的数量。对于所有的算法，n=50，对 F1 F10的实验重复 30 次。在F1 F8中 itermax=1 000，在 F9和 F10中 itermax=500，计算 30 次寻优结果的平均值和标准差。表 1 不同算法参数设置Table 1 Parameter settings of different algorithms算法参数设置EGWOa=2 (1 t/max_iter)1/3)，A=2ar2 a，C=2r1TLBOSSAPD=20%，SD=10%，ST=0 8AMSSAPD=20%，SD=10%，ST=08，m=2CSSAHBPD=20%，SD=10%，ST=08，P=0 5ASSAPD=20%，SD=10%，ST=08，=1 i/itermax3 3结果分析表2、表 3 和图 2 分别是 ASSA 和 EGWO、TLBO、SSA、AMSSA 和 CSSAHB 的实验数据结果(在图 2 中，收敛曲线的纵轴采用对数处理)，加粗的值为最优。从总体上分析，相较于对比算法，本文所提 ASSA 的寻优能力和稳定性基本上都取得了领先，获得了较好的适应度值。相较于 EGWO 和 TLBO 这些不同类型的算法，本文所提的ASSA 可以较大幅度提高测试函数的优化性能。相较于同类型的对比算法，ASSA 也可以在绝大部分的测试函数上取得更好的值和更稳定的解。当维数从30 提高到100 时，ASSA 的寻优性能也没有明显下降，仍然能够在大部分测试函数上处于领先地位，说明 ASSA 受维度变化的影响比较小，具有较好的鲁棒性。在测试函数 F9和F10上，所有算法都取得了最优值，但是在图2 中可以明显看出，基于 SSA 的算法可以在较短的迭代次数中取得最优值，说明 SSA 算法在求解问题时比其它类型的群智能算法具有一定的优越性。同时本文提出的ASSA 能够在最少的迭代次数中获得最优值，说明 ASSA 在这几个算法中的收敛速度是最快的。表 2 30 维实验数据Table 2 30 dimensional experimental data函数性能指标EGWOTLBOSSAAMSSACSSAHBASSAF1平均值8 62 10144162 10167221 10177201 1031700标准差2 66 1014300000F2平均值7 80 10833 96 1083367 1080753 10150760 101733 94 10208标准差8 23 10832 48 1083201 1079412 1014900F3平均值7 85 10453 23 1034251 10119000标准差1 72 10447 80 1034127 10118000F4平均值3 71 10393 96 1067253 1087194 10147102 101421 44 10173标准差5 32 10392 20 1067136 1086107 10146556 101420F5平均值2 66 1018 32 100339 106279 108243 1081 69 109标准差397 1011 58 100634 106728 108415 1083 00 109F6平均值137 1014 98 1031169 1017445 1019889 10202 54 1020标准差142 1013 08 1031575 1017724 1019373 10201 31 1020F7平均值169 1053 99 104310 104430 105333 1055 80 105标准差196 1051 25 104298 104764 105426 1054 25 106F8平均值336 1038 48 103847 103101 104108 1041 11 104标准差2 80 1028 02 102690 102260 103190 1031 71 103F9平均值000000标准差000000F10平均值000000标准差00000087聂方鑫，等:基于自适应 t 分布与随机游走的麻雀搜索算法Electronic Science and Technologyhttps:/表 3 100 维实验数据Table 3 100 dimensional experimental data函数性能指标EGWOTLBOSSAAMSSACSSAHBASSAF1平均值4 59 1068282 10151818 10172498 10270609 102860标准差1 08 1067202 101510000F2平均值4 36 10411 09 1075340 1077811 10126572 101176 20 10168标准差2 45 10415 46 1076186 1076444 10125313 101160F3平均值1 01 10151 20 1013161 1099318 10202944 102340标准差3 65 10154 19 1013880 1099000F4平均值2 12 10161 93 1059336 1084175 10133895 101279 00 10139标准差1 69 10166 94 1060184 1083956 10133490 101264 93 10138F5平均值9 69 1018 85 101113 104220 106628 1061 40 107标准差567 1011 83 100324 104858 106898 1067 01 107F6平均值1 07 1012 17 104162 107869 109671 10104 97 1010标准差617 1011 00 103840 107711 109879 1097 90 1010F7平均值222 1055 75 104378 104442 105161 1053 21 105标准差220 1051 86 104348 104756 105197 1053 42 105F8平均值577 1032 16 104257 104391 104395 1044 05 104标准差4 85 1024 88 103123 103305 103586 1032 82 103F9平均值000000标准差000000F10平均值000000标准差000000(a)(b)图 2 收敛曲线(a)测试函数 F9(b)测试函数 F10Figure 2 Convergence curve(a)Test function F9(b)Test function F104结束语基于 SSA 在解决复杂问题时，容易出现寻优能力差、种群多样性缺失等问题，本文在初始化过程中使用反向学习策略使个体更接近最优点，从而增强个体寻优能力。通过对发现者的位置更新式进行改进，帮助发现者更快地搜索到最优点。最后，本文利用适应度值最好的个体帮助其它个体跳出局部最优点。实验结果表明，ASSA 的优化性能较其它算法具有较大改善。然而本文所提算法还没有在实际工程问题上得到验证，下一步研究将对此问题进行实验讨论。参考文献 1 Xue J K，Shen B A novel swarm intelligence optimization ap-proach:sparrow search algorithmJ Systems Science Control Engineering，2020，8(1):22 34 2Wang Y，Ding S F，Wang L J，et al A manifold p spec-tral clustering with sparrow search algorithm J Soft Compu-ting，2022，26(4):1765 1777 3Zhang Z，He，Yang K A bioinspired path planning approachfor mobile robots based on improved sparrow search algorithm J Advances in Manufacturing，2022(10):1 17 4Abdulhammed O Y Load balancing of IoT tasks in the cloudcomputing by using sparrow search algorithmJ The Jour-nal of Supercomputing，2021(2):1 27 5杨巍，毛剑琳，熊晔 一种动态权值自适应粒子群优化典型函数问题 J 电子科技，2018，31(9):9 1297Electronic Science and Technology聂方鑫，等:基于自适应 t 分布与随机游走的麻雀搜索算法https:/Yang Wei，Mao Jianlin，Xiong Ye A dynamic weighted adaptiveparticle swarm optimization for typical functional problems J Electronic Science and Technology，2018，31(9):9 12 6刘晨旻，王亚刚 基于连续空间的萤火虫算法改进 J 电子科技，2022，35(2):40 45Liu Chenmin，Wang Yagang Optimization of firefly algorithmbased on continuous space J Electronic Science and Tech-nology，2022，35(2):40 45 7Ma J，Hao Z Y，Sun W J Enhancing sparrow search algorithmvia multi strategies for continuous optimization problems J Information Processing Management，2022，59(2):1 12 8Zhang C L，Ding S F A stochastic configuration networkbased on chaotic sparrow search algorithm J Knowledge Based Systems，2021，22(10):1 20 9Zhu Y L，Yousefi N Optimal parameter identification ofPEMFC stacks using adaptive sparrow search algorithm J International Journal of Hydrogen Energy，2021，46(14):9541 9552 10 张晓萌，张艳珠，刘禄，等 融合多策略的改进麻雀搜索算法 J 计算机应用研究，2022，39(4):1086 1091Zhang Xiaomeng，Zhang Yanzhu，Liu Lu，et al Improved sparrowsearch algorithm fused with multiple strategies J Applicationesearch of Computers，2022，39(4):1086 1091 11 楚哲宇，唐秀英，谭庆，等 基于逐维高斯变异的混沌麻雀优化算法 J 自动化应用，2021(8):60 63Chu Zheyu，Tang Xiuying，Tan Qing，et al Chaos sparrow op-timization algorithm based on dimensional gaussian mutation J Automation Application，2021(8):60 63 12 王正通，程凤芹，尤文，等 基于翻筋斗觅食策略的灰狼优化算法 J 计算机应用研究，2021，38(5):1434 1437Wang Zhengtong，Cheng Fengqin，You Wen，et al Grey wolf op-timization algorithm based on somersault foraging strategy J Application esearch of Computers，2021，38(5):1434 1437 13 薛建凯 一种新型的群智能优化技术的研究与应用:麻雀搜索法 D 上海:东华大学，2020:1 50Xue Jiankai esearch and application of a novel swarm intel-ligence optimization technique:sparrow search algorithm D Shanghai:Donghua University，2020:1 50 14 Li M D，Xu G H，Lai Q，et al A chaotic strategy basedquadratic opposition based learning adaptive variable speed whale optimization algorithmJ Mathematics andComputers in Simulation，2022，19(3):71 99 15 韩斐斐，刘升 基于自适应 t 分布变异的缎蓝园丁鸟优化算法 J 微电子学与计算机，2018，35(8):117 121Han Feifei，Liu Sheng Adaptive satin bower bird optimizationalgorithm based on t distribution mutation J Microelectron-ics Computer，2018，35(8):117 121 16 黎素涵，叶春明 重选精英个体的非线性收敛灰狼优化算法 J 计算机工程与应用，2021，57(1):62 68Li Suhan，Ye Chunming Improved grey wolf optimizer algo-rithm using nonlinear convergence factor and elite re elec-tion strategyJ Computer Engineering and Applications，2021，57(1):62 68 17 ao V，Savsani V J，Vakharia D P Teaching learning based optimization:A novel method for constrained mechani-cal design optimization problems J Computer Aided De-sign，2011，43(3):303 315 18 唐延强，李成海，宋亚飞，等 自适应变异麻雀搜索优化算法 J 北京航空航天大学学报，2022，48(6):1 6Tang Yanqiang，Li Chenghai，Song Yafei，et al Adaptive mu-tation sparrow search optimization algorithmJ Journal ofBeijing University of Aeronautics and Astronautics，2022，48(6):1 6 19 汤安迪，韩统，徐登武，等 基于等级制度和布朗运动的混沌麻雀搜索算法 J 空军工程大学学报(自然科学版)，2021，22(3):96 103Tang Andi，Han Tong，Xu Dengwu，et al A chaos sparrowsearch algorithm based on hierarchy and brownian motion J Journal of Air Force Engineering University(NaturalScience Edition)，2021，22(3):96 10308