混合正弦余弦算法和Lévy飞行的麻雀算法

毛清华 ，张强 *，毛承成 ，柏嘉旋

（1.燕山大学 经济管理学院，河北 秦皇岛 066004；2.莫纳什大学 商学院，澳大利亚 墨尔本 VIC 3145）

0 引言

近几年新的群智能优化算法如雨后春笋一般不断浮现，学者们通过模拟自然界众多生物的行为，提出了一系列的群智能优化算法，如：灰狼优化算法（GWO），飞蛾火焰优化算法（MFO），鲸鱼优化算法（WOA），麻雀搜索算法（SSA）等等。由于群智能优化算法操作简单，求解问题能力强，被众多学者所青睐。其中麻雀搜索算法是2020年由薛建凯［1］首次提出，是一种新型群智能优化算法。麻雀搜索算法与其他算法相比，具有求解速率高、精确度高等特点，然而，在算法搜索后期仍然和其余智能算法一样，面临无法跃出局部极值的问题。

为加强算法抗局部最优的能力，众多学者都提出了各自的改进方法：Hegazy等［2］通过引入惯性权重，提高算法的求解速率，并成功优化特征选择问题。Wang等［3］提出自适应惯性权重，动态调整速度变化，使蝙蝠在靠近最优解过程中能够自适应改变速度。崔志华等［4］引入了平均聚类的多样性度量指标，保持了种群的多样性。Wang等［5］加入柯西扰动操作，避免萤火虫算法困于局部极值。Li等［6］通过引入非线性控制参数和柯西变异，提高了粒子群算法收敛速度和精度。Cui等［7］结合质心策略及改变蝙蝠速度更新方程，以提高算法全局开拓能力。Cui等［8］在布谷鸟算法中引入Lévy分布和指数分布，提高了后期算法扰动变异能力，进而摆脱局部区域。Elaziz等［9］引进差分算法，在局部搜索区域内，以差分变异算子作为住操作符，提升了樽海鞘群算法的特征开掘能力。Xu等［10］在飞蛾算法中，利用高斯变异增强局部挖掘能力，借助柯西变异提升全局探索能力。Mafarja等［11］将模拟退火思想融合到鲸鱼优化算法中，提升算法逃离局部空间的能力。Li等［12］将Lévy飞行分布应用到飞蛾算法中，以此提高算子变异能力。

以上文献对群智能算法的改进，对算法抗局部最优能力均有一定的提高，但是，仍存在精确度差，开掘能力不足的弱点。考虑到自适应权重能够有效平衡局部和全局的挖掘能力，以及Lévy飞行策略具备较强的局部扰动能力，提出一种混合正弦余弦算法和Lévy飞行的麻雀算法（ISSA）。首先，融入正弦余弦思想并添加非线性学习因子，动态调整发现者位置更新机制，并加快求解速率；然后，在跟随者位置更新方式中引进Lévy飞行策略，对当前最优解进行扰动变异，加强局部逃逸能力；最后对8个基准测试函数进行仿真实验，验证了ISSA改进策略的有效性与可行性。

1 基本麻雀搜索算法

麻雀搜索算法是受到生物界麻雀捕食和反捕食行为的启发而提出的。麻雀集合矩阵如下：

式（1）中：n是麻雀的数量，i＝（1，2，…，n），d是变量的维数。

麻雀的适应度值矩阵表示如下：

其中：n表示麻雀的数量，而Fx中的每个值表示个体的适应性值。适应度值更好的麻雀优先获得食物，并作为发现者带领整个种群向食物源靠近。发现者的位置更新方式如下：

其中：t表示当前迭代次数，j＝（1，2，…，d），表示第i个麻雀在第j维的位置，itermax表示最大迭代次数，α∈(0，1)范围的一个随机数，R2（R2∈［0，1］）、ST（ST∈［0.5，1］）分别代表预警值和安全值，Q代表服从［0，1］正态分布的随机数，L表示1×d的矩阵，且矩阵内每个元素为1。当R2＜ST，这表明周围没有天敌，发现者能够进行大范围搜索食物。如果R2≥ST，则意味着一些麻雀已经发现了天敌，整个种群需要快速飞到其他安全区域。

除发现者外，剩余都是跟随者，跟随者的位置更新公式如下：

其中，Xworst表示全局最差的位置，A表示1×d的矩阵，矩阵中每个元素随机赋值1或—1，且A+＝AT(AAT)—1。当i＞n/2时，表示适应度值较差的第i个跟随者没有获得食物，能量值极低，此时需要飞往其他地方觅食，以获得更多的能量。

侦查预警行为：

种群觅食时，会选取少量麻雀负责警戒，当天敌出现时，不论是发现者还是跟随者，都将会放弃当前的食物而飞到一个新的位置。每代从种群中随机选取SD（一般取10%～20%）只麻雀进行预警行为。其位置更新公式为：

其中：Xbest表示全局最佳的位置，β为步长控制参数，是一个均值为0、方差为1的正态分布随机数，k∈［—1，1］范围内的一个均匀随机数。这里，fi是当前麻雀的适应度值。fg和fw分别为当前的全局最佳和最差适应度值，ε为最小常数，以避免分母出现0。当fi＞fg时，表示麻雀在种群的边缘，极容易受到天敌的攻击；fi＝fg表明，处于种群中间的麻雀意识到了被天敌攻击的危险，需要靠近其他麻雀。k表示麻雀移动的方向，即步长控制参数。

2 混合正弦余弦算法和Lévy飞行的麻雀算法（ISSA）

2.1 融合正弦余弦算法（SCA）思想

基本SSA算法中，在R2＜ST时，发现者随着迭代次数的进行，麻雀个体每一维都在变小，搜索空间逐渐减小，增大了坠入局部空间的概率。为改善此问题，在发现者位置更新方式中融合正弦余弦（SCA）算法思想［13］，并引入非线性正弦学习因子，在搜索前期具有较大的值，有助于全局探索，在搜索后期，具有较小的值，有助于提升局部开拓能力、提高精确度。学习因子公式和改进后的发现者位置公式如下：

式（8）中，r1为［0，2π］内的随机数，r2是［0，2］内的随机数。

2.2 Lévy飞行策略

当发现者迭代一定次数且适应度值不变时，此时跟随者成了发现者，为避免算法陷入局部最优，在跟随者更新公式中引入Lévy飞行策略，提高全局搜索能力。改进后的公式如下：

式（10）中r3、r4均为［0，1］范围内的随机数，ξ的值可取1.5，σ计算方式如下：

其中 Γ(x)＝(x—1)！。

混合正弦余弦算法和Lévy飞行的麻雀算法步骤流程图见图1。

图1 ISSA算法流程图Fig.1 Flow of ISSA algorithm

3 算法性能测试

3.1 算法参数设置

为验证ISSA算法的有效性，以及发现者比例对算法性能的影响，选取粒子群算法（PSO）［15］、灰狼算法（GWO）［16］、飞蛾火焰算法（MFO）［17］、基本麻雀算法（SSA）［1］以及改变发现者比例的两种麻雀算法SSA1、SSA2进行对比。算法参数设置如表1所示。

表1 参数设置表Table1 Parameters settings

3.2 算法性能结果对比分析

本文在表2所示的基准测试函数上进行算法性能的测试，使用Matlab2019a编写算法和仿真实现。为增强实验结果说服力，降低偶然误差的可能性，各个算法在每一个基准测试函数上独立运行30次。求解结果如表3所示。

表2 基准测试函数Table 2 Benchmarking functions

表3 基准测试函数优化结果比较Table 3 Comparison among optimal results of benchmarking functions

由表3可以发现，ISSA求解各个基准测试函数的平均值比其余6种算法更接近理论全局最优值，标准差的数值更小，标准差低表明求解数据波动较小，寻优过程鲁棒性更强。因此ISSA算法在寻优性能上相较于 SSA、SSA1、SSA2、GWO、PSO 和MFO等算法精确度更高，更容易寻到最优解。

3.3 算法收敛曲线对比分析

为直观体现ISSA算法的收敛性能，图2展示了7种算法的迭代收敛曲线。横坐标代表迭代次数，纵坐标代表适应度的对数值。

图2 8个基准测试函数收敛曲线Fig.2 Convergence curves of 8 benchmark functions

从以上收敛曲线图可知，不论是在高维或是低维条件下，ISSA都具备更佳的收敛性能，其收敛曲线更加平滑，较大的拐点很少。与其他四种算法相比，ISSA曲线一直处于最下方，表示收敛速度更快，对数值越小，表明求解精度更高。此外，改变发现者的比例，由10%增加到30%的过程中，10%的发现者比例效果最差，20%与30%的发现者比例效果性能差异较小，优化能力相当，但均不及ISSA。

3.4 与混沌麻雀算法（CSSA）比较

为进一步体现改进之后麻雀搜索算法的优越性，选取几个具有代表性的测试函数与吕鑫［18］中所提出的混沌麻雀搜索算法（CSSA），SSA进行算法性能比较，通用条件以文献［18］为准，比较结果如表4所示。

表4 ISSA与CSSA算法性能比较Table 4 Comparison of algorithm performance between CSSA and ISSA

从表4可知，对于优化单峰函数，ISSA在平均值和标准差两个指标上，比CSSA寻优性能至少提升了49个数量级，效果提升较大，对于优化多峰函数f6至f8，ISSA与CSSA优化效果不分上下。总而言之，ISSA的平均值和标准差更小，说明ISSA在求解过程中，精确度更高、稳定性更强，是一种效率更高的算法。

4 结论

本文提出一种改进的麻雀搜索算法（ISSA），并基于基准测试函数进行仿真实验，比较算法性能，得出以下结论：

（1）融合正弦余弦算法思想和引入非线性学习因子改变发现者的位置更新机制，可进一步协调局部挖掘和全局开拓的能力；引进Lévy飞行策略，改进跟随者位置更新方式，可提升抗局部极值的能力。

（2）在基准函数上的测试比较发现，ISSA比GWO、PSO、MFO、SSA、SSA1、SSA2、CSSA具备更强的优化性能，在求解速率、精确度、稳定性等方面展现出了显著的优越性。

（3）后续研究可将ISSA算法应用于一些实际的工程优化问题，如数据预测、路径规划、选址研究等，以验证ISSA在实际问题中的有效性。