一种混合多策略改进的麻雀搜索算法

2024-02-28李江华王鹏晖

计算机工程与科学 2024年2期

李江华,王鹏晖,李伟

(江西理工大学信息工程学院,江西赣州 341000)

1 引言

为在实际问题中解决最优化的问题,高效的优化算法一直是工程领域的主要研究内容之一。面对越来越复杂多样的大型优化问题,传统优化算法虽然简单易行,但适用性也越来越差,无法在短时间内得到可接受的解。因此,许多受自然现象启发的群体智能优化算法陆续被提出,如蚁群优化ACO(Ant Colony Optimization)算法[1]、粒子群优化PSO(Particle Swarm Optimization)算法[2]、萤火虫算法FA(Firefly Algorithm)[3]和鲸鱼优化算法WOA(Whale Optimization Algorithm)[4]等。这些算法相比传统算法结构简单,具有良好的寻优性能,并在可接受的时间内能够提供较好的解决复杂问题的方案,在现实生活中得到了广泛应用。但是,随着实际问题的约束条件越来越复杂,许多算法的适用性已经不足,这就要求更高性能和更高适用性的优化算法来应对这些复杂的应用问题。其中,麻雀搜索算法SSA(Sparrow Search Algorithm)[5]在2020年被Xue等首先提出,通过模拟麻雀觅食和反捕食行为,不断更新个体位置进行寻优,结构简单,控制参数较少,并已成功在随机配置网络[6]、电池堆参数优化识别[7]、无线传感器网络[8]和无人机航迹规划[9]等领域得到了应用。但受麻雀种群自然特征的限制,SSA仍然存在依赖初始种群、全局搜索能力较弱、易向最优解跃进从而陷入局部最优的缺点。

Yang等[10]在种群初始化阶段加入混沌映射方法,对种群多样性进行了增强,利用自适应加权策略平衡全局搜索与局部开发能力,通过一种自适应t分布变异算子提高算法的搜索能力。Song等[11]引入非线性递减权重,促进搜索空间的探索和利用,采用变异策略,将混沌搜索与能量较高的搜寻麻雀的局部搜索相结合,避免陷入局部最优。黄辉先等[12]利用精英个体具有更多的进化信息从而改善算法的全局搜索能力,引入混沌动态权重因子加强算法的局部搜索能力,提高算法的收敛精度。Ouyang等[13]融合透镜原理的对立学习策略与随机逆向学习策略增加种群多样性,采用改进正余弦算法的策略使搜索更加广泛,并利用差异的局部搜索,提高解的质量。段玉先等[14]通过在种群初始化阶段引入Sobel序列,提高麻雀种群的多样性和遍历性,利用非线性惯性权重,加速算法的收敛,应用纵横交叉策略引导算法跳出局部最优。Liang等[15]通过自适应加权的方法加速了算法的收敛,改进的边界处理策略在一定程度上提高了算法的收敛精度。

以上文献提出的改进算法在一定程度上提高了全局搜索能力,改善了过早收敛的情况,但算法寻优精度不足、跳出局部最优能力欠缺、随着搜索空间维度增加精度下降、收敛缓慢等问题依旧存在。针对以上问题,本文提出了一种混合多策略改进的麻雀搜索算法MISSA(Multi-strategy Improved Sparrow Search Algorithm)。首先,对各改进策略进行阐述,在种群初始化阶段加入精英反向学习策略,提高初始解的质量与多样性,扩大搜索范围。对发现者的位置更新进行步长控制,采取分阶段的位置公式,来提高算法的收敛精度与寻优能力。对跟随者的位置更新加入Circle映射参数和余弦因子,进一步提高算法的遍历性与搜索能力。利用自适应选择机制对麻雀个体位置加入Lévy飞行,并进行贪心机制择优更新,增强算法跳出局部最优的能力。基于13个测试函数进行了仿真实验对比,并进行了Friedman检验以验证本文所提算法的优越性。然后,对改进算法进行有效性分析,利用消融实验测试所使用的每个策略是否能够提高原始算法的性能,最后对提出的MISSA进行时间复杂度分析。实验结果表明,MISSA具有更好的寻优能力和收敛精度,能够有效避免陷入局部最优,并具有良好的稳定性。

2 麻雀搜索算法

在麻雀搜索算法中,通过麻雀群体的捕食与反捕食行为,将个体区分为发现者、跟随者和警戒者,每只个体位置对应一个解。发现者为整个种群找寻最佳的觅食区域,跟随者通过跟随发现者获取食物,警戒者负责对觅食区域进行监视。为了获得更好的食物来源,每只麻雀个体都可以成为发现者,但总体比例不变。当警戒值高于安全值时,整个种群面临危险,需要放弃觅食并执行反捕食行为,飞往安全区域。

将以上行为建立成模型。在SSA中,假设搜索空间为J维,存在I只麻雀,式(1)为I只麻雀在J维空间中对应的位置：

(1)

发现者的位置更新方式如式(2)所示：

(2)

跟随者的位置更新公式如式(3)所示：

(3)

警戒者的位置更新公式如式(4)所示：

(4)

3 改进的麻雀搜索算法

3.1 精英反向学习策略

初始种群的质量和多样性很大程度上会影响后续算法的寻优能力与收敛性能[16],因此本文将精英反向学习策略[17]应用到初始化阶段,通过反向解的生成与精英个体的选择,不仅使算法搜索范围得到扩大,提高了全局搜索的能力,也能够提高算法规避局部最优的能力。对于原适应度值较高的个体来说,对其进行反向区域的搜索,没有太大价值。而对于反向解适应度值较高的个体来说,反向区域具有较高的搜索价值。通过选取更优的个体作为初始种群,能更好地提高整个种群的寻优能力与搜索效率,同时具备更快的收敛速度。

(5)

3.2 阶段性控制步长策略

算法的综合性能需要在探索与开发之间平衡。在原始麻雀搜索算法中,缺乏对步长的有效控制,在发现最优解时,其他个体迅速向最优解靠拢,过早的收敛会导致难以平衡全局探索与局部开发。

当警戒值低于阈值时,发现者采用螺旋式搜索策略,在不断靠近最优值的同时,对附近一定范围也进行寻优比较。这种搜索方式虽然搜索范围更广,但相应地也带来了搜索精度不足的问题。因此,引入非线性衰减因子μ,使算法在前期不同区域广泛搜索,在中后期专注于开发已知区域,提高搜索精度和收敛速度。改进后的发现者位置更新公式如式(6)～式(9)所示：

(6)

l=(a-1)×rand+1

(7)

(8)

(9)

其中,ST′∈[0.8,1]表示安全值,rand为[0,1]的随机数,ω为一个常数,经多次实验,取5.5;衰减因子μ与原始算法中发现者位置更新的系数exp(-i/(α×itermax))对比如图1所示。

Figure 1 Comparison of attenuation factors图1 衰减因子对比图

在迭代更新的过程中,与标准SSA的系数相比,本文提出的衰减因子前期权重较大,变化速度较快,发现者不断探索未知区域,避免了前期过早收敛;而在迭代的后期,衰减因子权重较小,变化速度较慢,发现者能够保持较强的局部开发能力,缩小搜索范围,加速算法收敛。

3.3 混沌余弦变化因子

在发现者寻找到最优解并引领种群收敛的情况下,其余跟随者的迅速靠拢是跳跃式的,这会导致算法陷入局部最优,降低了算法的多样性。因此,本文在跟随者的位置更新中引入混沌余弦变化因子,通过在不同阶段调整,加强跟随者对未知区域的广泛探索,降低陷入局部最优的概率。为降低当前最优位置对个体的影响,使跟随者个体也能够进行一定的搜索,引入随迭代次数变化的惯性权重η,如式(10)和式(11)所示：

(10)

(11)

其中,δ为常数,本文经过多次实验,设置为3。

在算法搜索的前期,跟随者在靠近发现者最优位置的过程中,也能够开展搜索,有一定几率成为新的发现者,而不是仅仅跃进到最优位置。在算法的后期,权重较大,变化速度慢,最优个体的影响逐渐变大,提高了算法的收敛能力。为了提高跟随者移动的遍历性与随机性,本文采用Circle混沌映射生成相关参数。

Circle映射如式(12)所示：

(12)

混沌状态下的Circle映射分布与随机分布如图2所示。

Figure 2 Comparison of random distribution and Circle map distribution图2 随机分布与Circle映射分布对比图

从图2可以看到,Circle映射分布的随机数更为均匀,具有更好的随机性与遍历性,能更好地扩大搜索范围到整个区域。

改进后的跟随者位置更新如式(13)所示：

(13)

其中,k为Circle映射生成的0～1之间的随机数。在引入混沌余弦变化因子后,惯性权重η随着迭代次数的增加而增加,不断调整跟随者向最优个体移动的位置,前期以尽可能大的螺旋式范围搜索最优个体周围区域并逐渐靠近最优个体,若有更优值,则跟随者个体成为新发现者,并转换位置更新;后期在小范围内开发,加速向最优个体靠近,提升算法的寻优精度。

3.4 自适应选择机制的Lévy飞行

针对SSA算法在陷入局部最优时,种群搜索陷入停滞的情况,本文设计了一种自适应选择机制的Lévy飞行策略,通过随迭代次数不断减小的自适应因子p,随机选择麻雀个体进行Lévy飞行扰动,增强麻雀位置的多样性,改善算法容易陷入局部最优的缺陷。自适应选择因子公式如式(14)所示：

(14)

该因子在前期较大,以较高的概率对麻雀个体进行扰动,增强前期种群的广泛搜索能力;在后期较小,有利于算法的收敛能力。

Lévy飞行在随机行走的过程中会以较大的概率出现大范围的移动,具有较为平稳、独立的增量。

Lévy飞行的位置更新公式如式(15)所示：

(15)

由于Lévy分布十分复杂,在Mantegna等[18]提出的算法中将Lévy飞行路径定义为式(16)：

(16)

(17)

其中,参数β取值范围为(0,2),一般β=1.5,Γ(x)=(x-1)!。

Lévy飞行示意图如图3所示。

Figure 3 Schematic diagram of Lévy flight图3 Lévy飞行示意图

很多研究工作都基于Lévy飞行策略改进并取得了较好的效果[19-22]。尽管Lévy飞行可以对个体的位置进行更新,但无法保证更新后位置的新适应度值优于原位置的适应度值。因此,本文利用贪心机制的特性,通过更新前后位置的适应度值比较,保留更优的解,贪心机制如式(18)所示：

(18)

通过执行策略前后的适应度值大小对比,选取更优的位置进行更新,以提高全局寻优的能力,最大程度地避免陷入局部最优。

4 MISSA算法步骤

步骤1初始化参数：种群规模为n,最大迭代次数为itermax,空间维度为J,发现者数量为PD,警戒者数量为SD,报警阈值为ST,初始上下界为lb和ub,适应度函数为F(·);

步骤2种群初始化：根据式(5)生成随机性、遍历性强的初始精英种群;

步骤3对每只麻雀个体的适应度值进行计算并排序,记录最优适应度值pfit、最优个体位置xbest;

步骤4通过式(12)生成随机参数R2,根据式(7)～式(9)更新相应的参数l、a、μ;

步骤5根据式(6)更新发现者位置;

步骤6通过式(12)生成随机参数,根据式(9)和式(10)更新相应的参数μ、η;

步骤7根据式(13)更新跟随者位置;

步骤8通过式(12)生成随机参数K,根据式(4)更新警戒者位置;

步骤9根据式(14)更新自适应选择概率p,通过式(16)和式(17)对麻雀个体位置加入Lévy飞行扰动,依据式(18)进行适应度值的比较,择优更新位置;

步骤10输出最优个体适应度值及其位置。

5 实验与结果分析

5.1 实验设计与测试函数

为了充分测试本文改进算法MISSA的寻优能力,本节在13个测试函数上(如表1和表2所示)进行仿真实验,分别将其与PSO[2]、GWO[23]、WOA[4]、SSA[5]和CLSSA[24]进行对比实验。并在实验对比后加入Friedman检验,对所有算法进行综合比较。上述实验均在AMD RyzenTM5 3400GE,3.30 GHz,16 GB内存,Windows 11(64位)的测试环境下进行,使用MATLAB R2019a软件编写所有程序。

Table 1 Unimodal test functions

Table 2 Multimodal test functions

在这13个测试函数中,F1(x)～F6(x)为单峰函数,用于重点检测算法的求解精度;F7(x)～F10(x)为复杂多峰函数,含有较多的局部极小值,用于检测算法跳出局部极小值的能力,表中最优值的J表示维度;F11(x)～F13(x)为固定低维多峰测试函数,且最优值不同,用于检测算法的综合寻优能力。

为使各算法在公平条件下进行对比,实验参数设置如表3,各算法的种群规模设置为50,最大迭代次数设置为500,均分别独立运行30次,统计各算法求解各测试函数的最优值、平均值和标准差,用以检验算法的寻优能力、寻优精度以及稳定性。

Table 3 Algorithm parameters setting

5.2 算法对比分析

为检验算法MISSA在不同维度下的性能,除了固定维度的测试函数,对其余测试函数分别设置维度为30,50和100,以进行更加全面的对比。实验结果见表4～表6,表中的最优值均已加粗显示。

Table 4 Experimental results of MISSA and contrastive algorithms on test functions with dimension 30

从表4可以发现,MISSA在单峰函数上能获得更高的求解精度,寻优能力明显强于WOA、GWO、PSO、SSA和CLSSA的,且标准差也均为最小,说明算法的稳定性强于其他算法的。在复杂多峰函数上,对于函数F8和F9,SSA、CLSSA与MISSA均找到了最优值,且精度都达到了最高;对于函数F10,MISSA的收敛精度明显高于其他算法的,且稳定性也最好。在固定低维多峰函数上,虽然各算法都有不错的性能,但SSA在函数F11上表现不够优秀,MISSA很好地改善了这一点;在函数F12和F13上,MISSA都达到了更高的寻优精度与稳定性。上述结果说明在同等30维的情况下,MISSA具有更强的搜索能力、更优的搜索精度与稳定性。

表5展示了当维度为50时,除去固定低维函数后各算法的实验结果。可以看到,MISSA在单峰函数F1～F6上各方面性能依然明显高于其他算法的,而PSO、WOA和GWO随着维度增加,算法的精度明显下降。而在更高维度的多峰函数上,MISSA依旧稳定,CLSSA次之。总体来说,MISSA具备更强的解决高维问题的能力,并具有较强的稳定性。

Table 5 Experimental results of MISSA and contrastive algorithms on test functions with dimension 50

在100维的情况下,实验情况与50维的基本类似,如表6所示,进一步验证了MISSA相比于其他算法在高维情况下的优势。

Table 6 Experimental results of MISSA and contrastive algorithms on test functions with dimension 100

为使实验结果更具有说服力,本文对以上算法的平均值与标准差进行了Friedman检验,检验结果如表7所示。从表7可以看出,不同维度和不同函数下,算法性能具有差异,但排名均为：MISSA>CLSSA>SSA>WOA>GWO>PSO,这表明MISSA相比其他算法具有很强的竞争力。

Table 7 Friedman test on test functions with different dimensions

为了反映MISSA的动态收敛特征,图4给出了各算法在30维情况下13个测试函数的平均收敛曲线图。测试函数迭代收敛曲线可以较为直观地对比出各个算法的收敛性和寻优能力。通过图4a～图4f可以看出,MISSA比其他算法能够更快地收敛到最优值;在图4f和图4g中,多峰函数存在多个局部最优值,为函数寻优增加了难度,各算法都一定程度地陷入停滞,但MISSA能够及时跳出局部最优,扩大搜索,向更优值收敛;在图4i和图4j中,MISSA达到了更快的收敛速度和更高的收敛精度;在固定低维函数上,图4k和图4l中CLSSA与MISSA的收敛曲线相近,都达到了较好的收敛效果。

Figure 4 Convergence curves of MISSA and contrastive algorithms图4 MISSA和比较算法收敛曲线图

针对引言提出的随着搜索空间维度增加寻优精度下降、收敛缓慢等问题,除去固定维函数,图5给出了50维情况下算法的收敛情况：在50维情况下,MISSA同样很好地解决了算法在高维单峰条件下寻优精度不足的问题,在函数F1～F4上大幅度加速了算法整体的收敛;在函数F5与F6上及时地跳出局部最优,提高了搜索能力;在函数F10上,不仅达到了更高的精度,也具备更快的收敛速度。可见,MISSA很好地解决了SSA随着搜索空间维度增加寻优精度下降、收敛缓慢的问题。

Figure 5 Convergence curves of high-dimensional algorithms图5 高维算法收敛曲线图

5.3 改进算法有效性分析

为了验证改进策略的有效性,使实验更具说服力,本节对算法进行消融实验,使用表1和表2中的测试函数对标准SSA、仅使用精英反向学习策略的SSA(ESSA)、仅使用阶段性控制步长策略的SSA(SSSA)、仅使用混沌余弦变化因子的SSA(CSSA)、仅使用自适应选择机制的Lévy飞行(LSSA)和MISSA进行实验,各算法参数设置与标准SSA的保持一致,种群数量为50,迭代次数为500,结果如表8所示。从表8可以看出,在单峰函数F1～F6上,与标准SSA相比,所使用策略皆对算法的寻优能力有较大提升;在高维多峰函数上,虽然在F7上的寻优能力类似,但各改进算法稳定性都有所提高,在F10上各算法的性能提升明显,至少提升2个量级,而MISSA效果最好;在固定低维多峰函数上,在函数F11上,除ESSA效果一般,其余算法均有效提高了SSA的寻优能力,同时提高了算法的稳定性;在函数F12上,MISSA和ESSA收敛于最优值附近,表现稳定;在函数F13上,各算法性能相近。综上所述,消融实验验证了所使用策略都对标准SSA的寻优性能有所提高,验证了策略的可行性,结合改进策略后的MISSA具有更高的优越性。

5.4 MISSA时间复杂度分析

假设SSA算法中种群规模为n,维度为J,初始化种群参数时间为α1,求个体适应度值的时间为F(J),发现者数量为pNum,每一维更新时间为α2,跟随者数量sNum,每一维更新时间为α3,警戒者每一维更新时间为α4。因此初始阶段时间复杂度T1=O(α1+n(F(J)+J×α1));发现者更新时间复杂度T2=O(pNum×J×α2);跟随者更新复杂度T3=O(sNum×J×α3);警戒者位置更新复杂度T4=O((n-pNum-sNum)×J×α4)。综上,SSA时间复杂度T=T1+(T2+T3+T4)。

在MISSA中,假设求取反向种群时间为β1,因此初始阶段MISSA的时间复杂度T′1=O(α1+n(β1+F(J)+J×β1));发现者更新公式产生参数时间为β2,发现者更新时间复杂度T′2=O(pNum×J×β2);跟随者改进公式产生混沌因子时间为β3,产生余弦变化因子时间为β4,跟随者更新时间复杂度T′3=O(sNum×J×(β3+β4));警戒者的时间复杂度不变,依旧为T′4=T4;自适应选择机制的Lévy飞行产生自适应因子时间为β5,位置更新比较时间为β6,其时间复杂度T′5=O(β5+β6)。

综上MISSA时间复杂度T′=T′1+(T′2+T′3+T′4+T′5)=T。以上分析表明,相对于标准SSA,MISSA的优越性没有以时间复杂度的增加为代价。