改进麻雀搜索算法及其应用研究

严浩洲 刘旺盛 蔡振亮 敬添俊

(集美大学 现代物流研究中心，福建厦门 361021)

随着人工智能及工业技术的发展，对算法性能的要求越来越严格，传统的优化算法越来越难以满足其发展的需求。同时，群智能优化算法因结构简单、求解效率高等优点，受到了学者的青睐，越来越多的群智能优化算法被提出。群智能算法是通过模拟自然界中的一些事物或生物的生命特征与行为规则，搜索分布在一定范围内解空间的最优解。学者们通过蚂蚁、鲸鱼、狼、飞蛾、麻雀等各种智能生物的群集行为，提出了许多的群智能优化算法，包括蚁群算法(Ant Colony Optimization, ACO)、粒子群算法(Particle Swarm Algorithm, PSO)、灰狼优化算法(Grey Wolf Optimization, GWO)、鲸鱼优化算法(Whale Optimization Algorithm, WOA)、麻雀搜索算法(Sparrow Search Algorithm, SSA)等[1-6]。其中，薛建凯等[7]于2020年提出的麻雀搜索算法是一种新型的群智能优化算法。

SSA相较于其它群智能优化算法具有易操作、鲁棒性强、应用范围广的优点，受到学者们的广泛关注。但SSA同其它群智能优化算法一样，具有收敛过早和迭代后期易陷入局部最优等问题。因此为进一步提高SSA的优化能力，研究者们进行了一系列的研究和改进。大多改进方法集中在利用帐篷映射、混沌映射、反向学习、Levy飞行策略、Tent混沌序列以及柯西变异[8-19 ]等方面。如Ouyang C等利用透镜反向学习策略、随机逆向学习策略、正余弦搜索和可变螺旋搜索策略等方法先后提出了学习型麻雀算法和自适应螺旋麻雀搜索算法[8-9]；Yuan J和Zhao Z等先后将粒子群算法和SSA结合以解决求解精度低的问题，并利用重心反向学习和变异算子提高了跳跃出局部极值的能力[12]；毛清华和张强针对基本麻雀搜索算法在迭代后期种群多样性减小，容易陷入局部极值的问题，提出了一种融合柯西变异和反向学习的改进麻雀算法[16]。

以上改进算法在一定程度上提高了全局搜索能力，避免了过早收敛，但仍存在不足，主要体现两个方面：1)在上述相关改进策略中，缺少对动态参数的调整，容易限制算法的可搜索性；2)目前的各种改进方法主要集中在利用各种改进理论对麻雀位置进行调整，忽略了SSA本身的机理参数设置上的缺陷(麻雀跳跃方式和发现者与跟随者的位置变化)。针对此类问题，本文提出一种改进的麻雀搜索算法(ISSA)：首先针对发现者位置进行调整，改变最优位置的跳跃方式，在跟随者处采用非线性的正余弦搜索进行改进；其次，为解决算法在迭代后期易陷入局部最优的问题，对发现者和跟随者位置进行动态调整，为避免算法易受随机性干扰，利用反向学习对种群进行初始化；最后，为解决算法过早收敛的问题，利用柯西—高斯变异选择适应度最好的个体进行变异。笔者用12个基准函数进行仿真实验，并将其运用到简单的车辆路径问题中，验证了此算法的可行性和有效性。

1 麻雀搜索算法

1.1 基本原理

麻雀搜索算法(Sparrow Search Algorithm，SSA)数学模型中的主要规则如下。

1)发现者负责搜索食物位置，为跟随者的飞行提供方向。模型中发现者通过对某一位置的适应度值进行分析，判断位置的好坏。

2)当群体中的麻雀发现捕食者后，个体发出警告信号，如果警告值大于安全值时，发现者会进行飞行，寻找其他位置进行觅食。

3)发现者和跟随者的身份可以相互转换，每只麻雀都可以成为发现者，但是发现者和跟随者的比例是一定的。

4)跟随者的能量越低，觅食位置越差。此时，食物不充足的跟随者会飞行到其他位置，向食物多的位置移动。

5)跟随者总能寻找到发现者的位置，能够在发现者或者跟随者附近觅食。同时，跟随者为获得更好的觅食位置会不断监控发现者的位置，再跟随发现者移动。

6)当麻雀意识到危险时，位于边缘位置的麻雀会向安全区靠近，位于种群中间的麻雀则会随机向其他麻雀的位置移动。

麻雀算法中，n只麻雀组成的种群可表示为：

(1)

其中，d为待求解问题的维数，n表示麻雀的数量，每只麻雀所在位置的食物量即待求解问题的适应度值，适应度值可用下式表示：

(2)

其中，f表示适应度值。算法中，正在觅食的麻雀能感受到捕食者的临近，它们通过鸣叫信号发出警报。当警报值大于保护阈值时，麻雀将会飞离原位置；当警报值小于保护阈值时，则在原位置附近进行广泛觅食。

由于发现者负责寻找食物，为了扩大食物的搜索范围，其位置经常发生变化，发现者位置变化方式如下：

(3)

跟随者的位置变化方式如下所示：

(4)

种群觅食时，会随机选取部分麻雀负责警戒，当天敌靠近时，无论是发现者还是跟随者，均会放弃当前的食物飞到其他位置。每次从种群中随机选取若干只麻雀进行预警行为(一般取麻雀总数的10% ～ 20%)，位置更新方式为：

(5)

式(5)中，Xbest表示全局最佳位置；β为步长调整系数，是一个均值为 0，方差为 1 的正态分布随机数；K∈[-1,1]范围内的一个均匀随机数。这里，fi是当前麻雀的适应度值；fg和fw分别为目前全局最优和最差适应度值；ε为最小常数，防止出现分母为0的情况。当fi>fg时，表示麻雀处于种群的边缘地带，易被天敌袭击；fi=fg表明在种群中心的麻雀察觉到了被天敌袭击的危险，需要向其它麻雀靠拢。K表示麻雀运动的方向，即步长调整系数。

1.2 算法流程

算法具体流程如下：

步骤1：初始化麻雀种群，定义相关参数，确定最大迭代次数；

步骤2：根据麻雀的适应度将麻雀划分为发现者和跟随者，确定初始适应度值；

步骤3：更新发现者位置；

步骤4：更新跟随者位置；

步骤5：随机选择麻雀进行预警行为；

步骤6：更新适应度值，若当前迭代次数大于最大值，则结束，否则重新执行步骤3。

2 改进麻雀搜索算法

对基本麻雀算法提出如下几点改进，以下称改进的麻雀算法为ISSA(Improved Sparrow Search Algorithm)。

2.1 发现者位置调整

表1 F1测试函数

设置最大迭代次数为100，种群数量为100，发现者数量为20，跟随者数量为80，统计种群适应度值最低的50只麻雀(i>n/2)的坐标值变化与函数图像如图1。

图1显示，从算法迭代开始，发现者麻雀出现在零点附近聚集的现象。该聚集现象，虽然对最优解在零点附近的优化问题可以提高问题的求解速度；但对最优解不在零点附近的优化问题，该现象会降低种群的多样性。因此，去除麻雀向原点附近移动的操作，并将向最优位置的跳跃操作改为向最优位置的移动。公式如下：

(6)

图1 发现者坐标值变化与函数图像

2.2 基于正余弦搜索的跟随者位置调整

在SSA的跟随者位置更新公式中，跟随者的位置会随适应度值的大小而变化，但公式中动态参数较少，易限制麻雀种群的搜索范围，限制算法的可搜索性。为了解决此类问题，在跟随者阶段采用正余弦搜索策略，利用正余弦特性动态更新麻雀个体位置，扩大搜索范围。具体调整公式如下：

(7)

其中，r1是决定个体搜索范围的关键参数，随着迭代次数的增加，r1值逐渐减少，麻雀的搜索范围也相应减小；a为常数；r2是[0,2π]内的随机数，决定了个体的运动距离；r3和r4分别为[0,2]和[0,1]中的随机数。针对r1，常用的方法是采用线性的方式进行搜索[8-9]，但该种方法在面对高纬的复杂函数时容易陷于局部最优。因此本文采用非线性方式来设置r1，如式(8)。

(8)

式(8)中，b为固定值0.1，c为调节因子，通过多次调试发现c为0.9时效果最佳。引入正余弦策略以降低麻雀搜索盲目性，加速种群中处于最佳和最差位置的个体之间的信息交流，使追随者的搜索更具有目的性。

2.3 发现者和跟随者位置进行动态性调整

麻雀算法同其它基于概率的群智能搜索算法类似，在算法迭代后期易陷入局部最优解。针对此问题，对发现者和跟随者位置进行动态性调整，具体策略如下：

(9)

JD是跟随者在麻雀种群中的数量比重；itermax是算法的最大迭代次数；i是当前的迭代次数；Fbest是当前全局最优适应度值；若i>(itermax/2)，算法开始动态调整发现者与跟随者的比例。此时，若第i-1次迭代的最优适应度值f(i-1)与第i-30次迭代的最优适应度值f(i-30)的差的绝对值小于Fbest/10，表示最优值多次未更新，需增加跟随者群体的比重(令JD=0.6)以增加全局搜索概率，否则维持跟随者种群比重(0.4)不变。

2.3 反向学习初始化种群

群智能算法的精度、收敛性和求解出的结果与初始种群的好坏有关。若麻雀种群数量较少，在初始化种群阶段易受随机性的干扰，发生聚集现象，导致后期寻优精度不足且易陷入局部最优。因此，令算法生成初始种群后，再经反向学习产生一个新种群，选取适应度排名前n个的解，随机组成新的麻雀种群。

一维空间的反解可以定义为：

(10)

类似地，D维空间中的反向解定义为

(11)

利用动态边界来代替搜索空间的固定边界，能积累搜索经验，使生成的反向解位于逐步缩小的搜索空间，加速算法收敛。当生成的反向解，位于边界之外时，用随机生成的方法进行重置。

2.4 柯西-高斯变异

SSA迭代后期，麻雀逐渐向最优个体靠近，导致算法缺乏种群多样性，有过早收敛的趋势。为解决该问题，引入了Cauchy-Gaussian变异策略，选择当前适应度最好的个体进行突变，再比较突变前后的位置，选择较优的位置进入下一次迭代。柯西-高斯变异策略的数学定义如下：

(12)

(13)

2.5 算法流程

改进的麻雀算法实现步骤如下：

步骤1：初始化算法参数；

步骤2：利用反向学习初始化麻雀种群(发现者、跟随者)；

步骤3：求每只麻雀的适应度值；

步骤4：根据全局适应度值变化情况，调整发现者与跟随者比例；

步骤5：更新发现者、跟随者以及感知到危险的麻雀的位置；

步骤6：按照适应度值大小调整每只麻雀的顺序；

步骤7：选取适应度值最优的麻雀进行柯西-高斯变异；

步骤8：重复步骤3～4，直到迭代次数大于目标值。

3 仿真实验与结果分析

为测试改进麻雀搜索算法的收敛精度、稳定性和收敛速度，利用12种测试函数，并与鲸鱼优化算法(GWO)、灰狼优化算法(WOA)、遗传算法(GA)、粒子群算法(PSO)、原始麻雀搜索算法(SSA)进行比较。

3.1 测试函数选取

分别采用6种单峰函数和6种多峰函数，对改进麻雀搜索算法的收敛精度、稳定性和收敛速度进行检验。F1～F6的单峰函数搜索范围分别为[-100,100]、[-10,10]、[-100,100]、[-100,100]、[-30,30]和[-100,100]，F7～F12的多峰测试函数中搜索范围分别为[-1.28,1.28]、[-500,500]、[-5.12,5.12]、[-32、32]、[-600,600]和[-50,50]，维度均为30，测试函数如表2。

表2 测试函数

3.2 算法对比分析

上述算法在函数测试时，统一使用相同的参数设置：算法的迭代测试均为1 000次，种群数为100；GWO和WOA中的和都为(0，1)中的随机数，α值由0到2线性下降；GA中交叉概率设为0.8，变异概率0.01；PSO中c1和c2均为1.494 45，w为0.8；麻雀搜索算法(SSA)和改进麻雀搜索算法(ISSA)中发现者数量占总麻雀数量的20%，意识到危险进行预警行为的麻雀数量占总麻雀数量的10%，安全阀值为0.8；各个算法独立运行1 000次，取最优值、平均值、标准差、平均运行时间。实验环境为2.50 GHz的英特尔i5处理器、12 GB内存、Matlab2020a。实验结果如表3～表5。

表3 算法测试对比(SSA、WOA)

表4 算法测试对比(GA、GWO)

表5 算法测试对比(ISSA、PSO)

由表3～表5可知，在收敛精度方面，ISSA在F1、F2、F3、F4、F9以及F11中均能寻到最优值，F5、F6、F7、F8、F10、F12测试函数中虽未寻到最优值，但在精度上均明显优于其它优化算法，如F6函数中最优解的精度相比SSA提高了16个数量级；在稳定性方面，由表3～表5中的标准差数据可以看出，ISSA的稳定性在测试函数中表现最好，其中在F1～F4中标准差为0，如测试函数F5中，稳定性排序为ISSA>SSA>WOA>WGO>GA>PSO。

对算法的收敛速度的分析，例举了F1～F2函数的迭代图像，如图2。从图2中可以看出ISSA相比与其它五种算法其收敛速度更快，如F1函数中，SSA需迭代约100次寻到最优解，而ISSA在50次左右既寻求了到最优解。

图2 F1～F2函数测试结果图

综上，ISSA算法在收敛精度、稳定性以及收敛速度方面相比于其它五种算法更具优势，且有良好的寻优能力。

4 ISSA算法在车辆路径问题的应用

为验证改进麻雀搜索算法在车辆路径问题中的应用与测试函数中的优化是否表现一致，选择Solomon算例对改进算法进行验证。同样地，为保证实验的严谨性，在实验中分别同鲸鱼优化算法(WOA)、灰狼优化算法(GWO)、遗传算法(GA)、粒子群算法(PSO)、原始麻雀搜索算法(SSA)进行比较。此类车辆路径问题为带容量限制和时间窗的车辆路径问题，数据中的节点数为30，车辆容量限制为200，车辆从节点0出发配送完成后返回节点0，目标是为寻找配送距离最小的路径[19]。

为保证实验不失一般性，选择Solomon算例中三种算例进行实验，分别为R、C和RC系列数据。这三种数据集的客户节点的分布方式不一样，R系列数据中客户节点的位置分布较为分散，没有聚集性，而C系列数据中的客户节点有聚集性，RC系列既包括分散的节点又包括一部分聚集的节点。每种类型的数据各选取2组进行对比实验，一共6组数据，每组数据独立运行100次取平均值，分别为R101、R102，C101、C102，RC101、RC102。算法中参数设置与上一节一致。

表6为R101的部分数据，其他数据见附录。

表6 R101数据集

R系列、C系列以及RC系列数据集实验结果如下表7所示。

表7 R系列、C系列、RC系列数据集车辆路径问题实验结果

六种算法在车辆路径问题实验收敛曲线比较(选取了C101、R101、RC101)，如图3。

图3 六种算法在车辆路径问题实验收敛曲线比较

从表7和图3可以看出，ISSA能有效求解车辆路径问题。从收敛精度方面，在三种数据集中，ISSA的收敛精度均为最高，收敛精度比其他五种算法高10%以上，WOA、GWO、SSA算法与ISSA收敛精度较接近，收敛精度最差的是PSO、GA算法。在稳定性方面，ISSA优于SSA、WOA和GWO，略低于PSO。由于GA算法一直未收敛，因此其标准差是六种算法中最小的。在收敛速度方面，R、C、RC三种系列数据集中，ISSA总是能快速收敛寻找到车辆路径问题的最优解，通常迭代300次左右就能寻找到最优解，与其他五种算法相比具有着较大优势。由此验证了ISSA应用到实际工程问题的可行性，为进一步的研究奠定了基础。

5 结论

通过12种基准函数的测试，关于ISSA可以得到以下结论：

1)ISSA寻优性能提升明显，如ISSA在12个基准测试函数的寻优结果均优于其他种算法，且相比对部分函数的最优解的精度提高了16个数量级以上；

2)ISSA的随机性和搜索性较高，具有优良的开拓能力。笔者改变发现者的跳跃方式，引入非线性的正余弦搜索，并动态的调整发现者和跟随者的比例，采用反向学习的种群化初始策略，这样可以丰富种群多样性，避免了ISSA陷入局部最优，增强了算法的全局搜索能力；

3)ISSA具有良好的稳定性。ISSA在12个基准测试函数上多次寻优的标准差普遍低于其他5种算法的标准差，寻优结果较为稳定；

4)ISSA收敛速度快，搜索能力强。从ISSA的收敛曲线可以直观看出其收敛速度明显优于其他5种算法。

从ISSA应用于车辆路径问题的对比实验可知，ISSA总是能快速收敛寻找到车辆路径问题的最优解，在收敛精度和收敛速度方面都明显较优于其它五种算法，在稳定性方面明显略低于PSO。

笔者利用Solomon算例验证了ISSA在车辆路径问题中的有效性和可行性，但关于ISSA的研究尚处于初始阶段，后续考虑将ISSA应用到更复杂的车辆路径规划的实际工程问题中，如多配送中心车辆路径问题、多车型车辆路径问题、随机车辆路径问题、模糊车辆路径问题等，再结合具体问题进一步优化算法性能，以检验ISSA在车辆路径的实际工程问题中的有效性。