一种改进的麻雀搜索算法

2022-04-02莫愿斌

计算机技术与发展 2022年3期

关键词：发现者测试函数搜索算法

刘睿，莫愿斌

(1.广西民族大学电子信息学院，广西南宁 530006；

2.广西民族大学混杂计算与集成电路设计分析重点实验室，广西南宁 530006；

3.广西民族大学人工智能学院，广西南宁 530006)

0 引言

麻雀搜索算法(sparrow search algorithm，SSA)[1]是2020年由薛建凯和沈波提出的一种群体智能优化算法，该算法模拟了麻雀的觅食行为和反捕食行为，具有实现简单、调节参数少的优点，并且在文献[2-3]中与其他群体智能优化算法进行了对比，在收敛速度、搜索精度、稳定性方面有一定的优势，是一种很有潜力的群智能优化算法。如今，SSA在支持向量机故障诊断[4]、动态路径规划[5]、工控入侵检测[6]等众多领域得到了广泛的应用。然而，SSA与其他群体智能算法类似，在优化过程中也存在着易陷入局部最优、收敛精度不足等缺陷，需要进一步的研究和探索。众多学者针对SSA存在的不足进行改进，其中李敦桥[7]首先采用反向对立学习策略将麻雀种群进行初始化，再结合模拟退火算法产生的Metropolis准则对当前解与新解比较替换，提高了算法的寻优能力；吕鑫等人[8]受BSA算法的启发，对发现者和加入者位置更新公式做出了改进，保障了全局收敛，同时具有一定的种群多样性。上述改进策略均在一定程度上避免了SSA陷入局部最优，提升了算法的性能，但SSA在寻优精度、收敛速度以及稳定性等方面仍有待进一步改善。

在麻雀搜索算法的基础上，该文提出一种加入萤火虫扰动策略的改进算法。该改进策略主要是在麻雀搜索后，利用萤火虫搜索扰动对麻雀位置进行进一步的优化更新，以提高算法搜索性，增强解的多样性，从而避免算法陷入局部最优。该改进策略简洁有效，通过对6个基准测试函数进行仿真实验，对比其他算法，表明该算法较SSA寻优性能提升明显，同时将FSSA应用于常见TSP问题求解，获得了较好的结果，进一步验证了所提算法的寻优性能。

1 麻雀搜索算法

SSA算法的设计灵感来源于鸟类的生物特性，依据麻雀的觅食行为建立的数学模型可归类为发现者-加入者模型，并加入了预警的机制，随机选取种群中的部分麻雀作为意识到危险的麻雀建立反捕食机制。每只麻雀是搜索空间中的一个粒子，可以代表问题的一个解。设定在种群中有发现者(Producer)和加入者(Scrounger)两种角色，发现者具备较高的适应度值，为加入者提供觅食即粒子搜索的方向和区域，引导种群进行搜索。麻雀个体在两种身份之中的变化处于动态平衡，且适应度值的变化决定了加入者是否跟随发现者。种群遭遇危险时，将触发反捕食行为，当预警值大于安全值时，加入者会追随发现者进行位置更新前往更安全区域觅食，在边缘的麻雀会向着群体中心更新自己的位置以规避危险，而位于种群中心的麻雀则会进行随机游走。

麻雀集合如下所示：

其中，n表示麻雀的规模，d表示变量的维数。

麻雀的适应度值如下所示：

其中，f([xi,d])表示个体适应度值。

发现者的位置更新公式为：

(1)

其中，t为当前的迭代数，itermax为最大迭代数，α为(0,1]之间均匀分布的随机数，R2∈[0,1]，ST∈[0.5,1]分别表示预警值与安全值。Q为服从正态分布的随机数，L为1×d的矩阵，其中每个内部元素均为1。当R2

加入者的位置更新公式为：

(2)

麻雀种群中意识到危险的麻雀位置更新公式如下：

(3)

2 加入萤火虫搜索扰动的麻雀搜索算法

2.1 萤火虫扰动策略

萤火虫算法(firefly algorithm，FA)[9]，是由剑桥学者Yang提出，通过模拟萤火虫的发光行为实现位置优化。基本的麻雀搜索算法存在的缺陷如下：算法在解空间搜寻目标时存在过早收敛，即容易“早熟”致使最优解精度不足，发现者在位置更新迭代后期容易直接跳跃至当前极值附近，导致搜索范围不够从而困于局部最优，同时寻优精度也会受到影响。为了改良以上所提到的不足之处，主要在麻雀搜索后，引入萤火虫算法的迭代策略，将萤火虫扰动策略应用于算法之中，借助萤火虫发光吸引的特性，寻找邻域结构内位置较优的个体，增强解的多样性，通过增加随机扰动项，扩展搜索区域，提升算法的全局探索能力，有利于引导算法跳出局部最优，同时进一步更新麻雀位置，使得种群整体搜索更加充分，有利于提升收敛精度。萤火虫算法涉及到的数学建模如下所示。

萤火虫的相对荧光亮度I为：

I=I0·exp(-γrij)

(4)

其中，I0为最大荧光亮度，是距离为零处自身的荧光亮度，且适应度值越优的个体具备的I0值越大；γ为光强吸收系数，体现萤火虫个体随着距离的增加、传播媒介的吸收影响下荧光的减弱效果；rij为各萤火虫之间的空间距离。

萤火虫的吸引度β为：

(5)

其中，β0为最大吸引度，即个体光源处的吸引度。

萤火虫扰动位置更新公式如下：

xi=xi+β·(xj-xi)+α·[rand(*)-1/2] (6)

其中，xi和xj为麻雀i和j的空间位置，α为步长控制参数，rand(*)∈[0,1]为服从均匀分布的随机因子。

2.2 FSSA算法步骤

FSSA算法流程如下：

Step1：初始化种群，设置种群大小N，最大迭代次数Iteration，发现者比例，意识到危险的麻雀比例、安全阈值等参数。

Step2：计算当前麻雀种群个体的适应度值并进行排序，找出当前最优值以及最差值。

Step3：按比例选取适应度值较优的麻雀作为发现者，根据公式(1)更新发现者位置。

Step4：种群中剩下的作为加入者，根据公式(2)更新加入者位置。

Step5：按比例在种群中随机选取部分个体作为意识到危险的麻雀，根据公式(3)更新意识到危险的麻雀位置，并计算新的适应度值，如果比当前最优值好就进行更新操作。

Step6：引入萤火虫算法，此时种群中搜索粒子等价于萤火虫个体；依据上一步迭代后的位置，计算适应度函数值作为各萤火虫最大荧光亮度I0，并根据公式(4)、(5)计算萤火虫的荧光亮度I与吸引度β，决定种群的搜索方向。

Step7：利用萤火虫扰动公式(6)对种群进行位置更新，并对处于最优位置的萤火虫进行随机扰动。

Step8：计算适应度值，保留最优个体位置。

Step9：检验是否满足停止条件，若满足则算法结束输出最优结果，否则转向Step2。

3 基准函数测试

为了验证FSSA的寻优性能，通过选取文献[10-12]中6个不同类型的基准测试函数，将FSSA与粒子群优化算法(particle swarm optimization，PSO)[13]、鲸鱼优化算法(whale optimization algorithm，WOA)[14]、SSA算法进行仿真对比实验。

所有计算过程重复进行30次，结果取最好值、最差值、平均值以及标准差作为算法性能的评判标准，实验的集成开发环境为Matlab(R2018b)，操作系统为win10，64位。设置四种算法迭代次数为1 000，种群数量为100，表1为基准测试函数相关信息，表2记录了四种算法的实验结果。为了直观地体现算法的寻优效果，图1给出了基准函数的搜索空间以及对应四种算法的收敛曲线。

由表2对单峰测试函数、多峰测试函数以及低维多峰测试函数的实验结果可反映出四种算法关于局部开发能力、全局探索能力以及跳出局部最优的能力的强弱；从单峰测试函数f1～f3的测试结果来看，FSSA表现出了良好的收敛速度以及寻优精度，可以准确寻优到理想值，优于其他算法，相比之下改进算法有明显提升。对于多峰测试函数f4和f5，FSSA能够有效地逃脱局部最优并找到全局最优解，对比其他算法，寻优结果数量级有较大提升，在取得较好的平均值同时标准差值较小，说明FSSA具有良好的鲁棒性，进一步说明了改进算法的有效性。对于低维多峰测试函数f6，虽然FSSA较其他算法寻优效果仅有小幅提升，但是FSSA具备的寻优精度最高，通过对平均值与标准差的对比，FSSA的寻优稳定性明显优于其余算法。

表1 基准测试函数

表2 仿真实验结果

图1 搜索空间及优化曲线

4 FSSA在TSP问题中的应用

4.1 TSP问题描述

旅行商问题(traveling salesman problem，TSP)，又译为旅行推销员问题等，最早由Dantzig等人于1959年提出[15]，是组合优化中一道著名的NP难问题，对其的求解也一直是学术界关注的热点。

TSP问题可描述为：假设一位旅行商需要途经若干城市以推销其货物，从其中一座城市出发，遍历每座城市一次最后回到出发点，且各城市之间位置已知，则如何选取、规划路线才能使得旅行商总行程最短。

设各座城市为V=(v1,v2,…,vn)，对城市的访问顺序为T=(t1,t2,…,tn)，每座城市之间的距离为d(vi,vj)，则TSP问题的目标函数为：

(7)

4.2 仿真实验

该文采用具有14座城市的TSP问题进行测试，各城市的初始坐标见表3，设置种群数量为100，最大迭代次数为1 000，分别对SSA与FSSA进行20次独立测试，表4记录了两种算法求解TSP问题的最好值、最差值和平均值。图2为各城市初始位置分布情况与FSSA求解TSP的最优解，图3为FSSA、SSA收敛曲线对比。

表3 14座城市的坐标

表4 两种算法的测试结果

图2 TSP问题仿真实验

图3 两种算法求解TSP的收敛曲线

从表4的实验结果可以看出，FSSA算法在求解TSP问题时可以在最大迭代次数内寻找到最优解，且随着实验次数的增多平均值仍近似等于最优值，体现了FSSA良好的鲁棒性；通过图3可看出，SSA的迭代收敛次数近似于400次，而FSSA在迭代少于50次时即完成收敛产生最优路径长度30.98，说明该文所提算法具有较快的收敛速度与较高的收敛精度；对比最终求解结果，FSSA较SSA在获得的最优解上提升了3.34%，最差解上提升了16.60%，平均值上提升了10.51%，进一步说明了该算法的有效性。