基于混合策略改进的麻雀搜索算法

胡树斌,魏霖静

(1.甘肃农业大学 理学院,甘肃 兰州 730070;2.甘肃农业大学 信息科学技术学院,甘肃 兰州 730070)

0 引 言

群智能优化算法(Intelligence Optimization Algorithm,IOA)灵感来于自然界中物理现象或生物群体行为,可用于求解函数最优化问题,其方便易操作且处理问题高效,为解决某些实际应用问题提供了新的思路。Xue等人[1]受麻雀群体觅食活动启发,于2020年提出麻雀搜索算法(SSA)。试验表明,对比其他传统优化算法,它具有优化能力强、易于实现、调节参数较少的优势。然而SSA算法同样存在不足,如迭代过程中种群丰富性降低、早熟收敛、易陷入局部最优停滞。为进一步提升原算法的性能,吕鑫等人[2]借鉴鸟群算法思想,优化SSA算法的发现者和加入者迭代方式,并将改进算法应用于多阈值图像分割中,在减少分割时间的同时提升了分割精度。魏晓鸽等人[3]采用精英反向学习策略改善初始种群,发现者位置迭代更新引入正余弦算法及动态权重因子,最后将改进算法用于火灾路径规划。付华等人[4]首先通过立方混沌序列初始化麻雀种群,然后引入透镜成像反向策略提升初始解质量,借鉴鸡群算法优化跟随者位置更新方式,最后引入柯西-高斯变异策略对最优个体进行变异帮助算法脱离局部最优停滞状态。Yuan等人[5]使用重心反向学习策略改善初始种群质量,并用学习系数改善发现者位置变换方式提升算法全局寻优能力。Yan等人[6]将加入者追随发现者时进一步划分为全局与局部搜索,并通过观察超出边界个体的数量变化来验证可变螺旋因子与改进迭代搜寻策略的有效性。Jiang等人[7]引入随机游走策略,可有效帮助算法摆脱局部最优状态。Tang等人[8]借鉴遗传算法思想,将交叉和变异思想引入SSA算法中,保障种群多样性的同时可提升个体跳出局部最优的概率。

上述研究中学者们从各个方面对SSA算法的缺陷加以改善,提升算法性能,不过探索更多有效的改进策略提升算法收敛精度、全局寻优性能仍需深入研究。基于此,该文提出了一种基于混合策略改进的麻雀搜索算法。首先,利用精英反向学习机制改善种群迭代后期多样性降低的问题,为算法全局寻优奠定基础;然后,在发现者位置采用黄金正弦策略改进,提升算法开发能力;最后,加入者跟随发现者时融入莱维飞行步长,使搜索方向与范围多样化,避免算法“早熟收敛”。

1 基本麻雀搜索算法

麻雀搜索算法根据个体在觅食活动中的不同分工,将种群成员划分为发现者、加入者、警戒者。发现者与加入者身份可动态转换,但占群体比例不变。规模为N的麻雀种群可用矩阵表示为:

(1)

式中,N为麻雀群体的规模,d为待优化问题的空间维度。每只麻雀表示为xi=[xi,1,xi,2,…,xi,d],适应度值为f(xi),全部麻雀的适应度值矩阵为Fx=[f(x1),f(x2),…,f(xN)]。

发现者为种群中位置较好的个体,占种群比例为10%～20%,负责寻找食物。

其位置更新如下:

(2)

式中,t是当前迭代次数;Max-iter为最大迭代次数;α∈(0,1)为随机数,随机数Q服从正态分布;L是元素取值均为1的1×d矩阵。R2∈[0,1]为预警值;ST∈[0.5,1]是安全阈值。

当R2

加入者通过监视发现者的行为觅食,适应度值较高的在最佳位置的发现者附近搜索食物,适应度较低的则移动到空间其他位置。加入者位置更新如下:

(3)

警戒者数量占种群总数的10%～20%,随机在发现者和加入者中选取,负责侦察警戒,初始位置更新公式为:

(4)

2 改进麻雀搜索算法

该文混合三种有效策略改善SSA算法迭代时种群丰富性降低、早熟收敛、难以脱离局部最优现象,具体策略如下。

2.1 精英反向学习机制

反向学习机制[9]靠近最优解的概率可提升50%,在可行解及其反向解中选择更优的个体作为新种群是其核心思想。精英反向学习(Elite Opposition-Based Learning,EOBL)则是在此基础上只针对种群精英个体构造反向种群。精英个体携带更多有效信息,相比较普通反向学习既提高了种群质量,又提升了搜索效率,有效地使种群避免寻优时掉入局部最优陷阱。

定义1(精英反向解)。

(5)

(6)

该文采用精英反向学习策略对初始种群以及迭代后期种群精英个体计算反向解时,根据式(5)计算种群适应度排名前N/2个体的反向解,将反向种群与原种群依据个体适应度排序,挑选最优的N个精英个体组成下一代寻优种群。该策略可有效避免算法盲目搜索而降低求解效率,为提升求解精度、加快收敛速度奠定基础。

2.2 黄金正弦机制

黄金正弦算法(Golden Sine Algorithm,Golden-SA)是Tanyildizi 等人[10]结合正弦函数原理在2017年提出,其原理简单、易于操作、收敛性能好。最大特点是可遍历单位圆上全部正弦值,其中黄金分割系数可帮助个体在迭代过程中极大程度缩小解空间,并进行充分寻优,提升了算法求解速度,更有效平衡了算法全局“搜索”与“开发”。

Golden-SA的核心是位置迭代方式,数学描述如下:

(7)

观察SSA算法式(2)可知,发现者在迭代初期就快速向全局最优靠近,容易造成早熟收敛现象,且相互之间缺乏足够的交流,难以对优质解空间全面探索。针对此不足,引入黄金正弦机制改善发现者探索方式,改进后更新方式描述如下:

(8)

2.3 莱维飞行机制

莱维飞行[11]是对自然界中昆虫与鸟类觅食路径随机游走过程的模拟,其以大概率短距离搜索与小概率长距离搜索的方式交错移动,产生服从重尾分布的随机步长[12]。莱维飞行步长较大时可适当扩大搜索范围,较小时可提升算法局部寻优能力,其多样变化的特性使个体在空间内搜索更加全面。

观察SSA算法式(3)可知,发现者找到食物时,距离近的加入者会迅速靠近,算法得以快速收敛,但也因此造成短时间内麻雀在局部空间大量聚集,种群多样性降低,增大了算法“早熟收敛”的风险。因此,该文在加入者位置更新中加入莱维飞行随机步长step,可以对与最优位置之间的空间全面搜索,最大限度降低算法陷入局部最优陷阱的风险。莱维飞行产生的随机步长为:

(9)

(10)

式中,Γ为标准伽玛函数;β1为固定步长,一般取值为1.5;συ、σμ为正态分布中的标准差。式(3)引入莱维飞行随机步长step后改进为:

(11)

3 EGSSA算法

3.1 EGSSA算法步骤

(1)参数设置。种群规模N、最大迭代次数Max-iter、发现者比例PD、警戒者比例SD、空间维度d、安全阈值ST;

(2)初始化种群。对麻雀种群随机初始化,根据目标函数计算麻雀个体的适应度值并排序;

(3)计算精英反向解。选取种群排名前N/2的麻雀个体根据式(5)求解反向种群,根据式(6)对超过边界的个体进行重置,计算反向种群适应度值;

(4)从当前种群和反向种群中选取适应度值排名前N的个体组成新一代种群并依据个体适应度排序,找到新一代种群中最差和最优适应度值:fworst、fbest,以及对应的麻雀个体位置Xworst、Xbest;

(5)根据公式(8)更新发现者位置;

(6)根据公式(11)更新加入者位置;

(7)根据公式(4)更新警戒者位置;

(8)判断结束条件,若迭代次数满足t>Max-iter,则终止操作,输出全局最优位置及最优解,否则跳转步骤(3)继续执行。

3.2 EGSSA算法伪代码

设置相关参数:种群规模N、最大迭代次数Max-iter、发现者比例PD、警戒者比例SD、空间维度d、安全阈值ST;

初始化种群,计算个体适应度值并排序

t=1

Whilet

foriin range(0,N/2):

forjin range(0,d):

根据公式(5)计算反向解

计算适应度值

检查是否超过边界,若超过,根据公式(6)重置

从当前种群和反向种群选取适应度值前N的个体组成新一代种群

对新种群按适应度值排序,记录最优、最差个体位置及适应度

随机取值R2并判断与ST关系:

foriin range(0,pNum):

根据公式(8)更新发现者位置

foriin range(pNum+1,N):

根据公式(11)更新加入者位置

foriin range(0,N*SD):

根据公式(4)更新警戒者位置

计算适应度值并更新最优个体适应度值及最优位置

返回最优位置及适应度值

ift% 1 == 0:

print('在第t代,种群最优适应度值为:fbest')

t=t+1

3.3 EGSSA时间复杂度分析

时间复杂度[13]是反映算法性能的一个重要指标。假定麻雀种群规模为N,空间维度为d,求解目标函数所需的时间为f(d)。根据文献[14],SSA算法的时间复杂度为T=O(d+f(d))。在EGSSA算法中,参数初始化的时间为η0,种群初始化的时间为η1,按式(5)生成反向种群所需时间为η2,则麻雀种群初始化阶段的时间复杂度为:

T1=O(η0+N(f(d)+d(η1+η2)))=

O(d+f(d))

(12)

对上一代种群求精英反向解阶段,按式(5)更新麻雀精英个体所需的时间为η3,生成随机变量k∈[0,1]所需的时间为η4,对两个种群排序所需时间为η5,在这一阶段的时间复杂度为:

T2=O(N/2×((η3+η4)d+f(d))+η5)=

O(d+f(d))

(13)

麻雀种群中发现者数量为PD×N,PD为发现者比例,每一维位置按式(8)进行更新的时间为η6,两个随机参数以及两个黄金分割系数生成时间均为η7,则该阶段时间复杂度为:

T3=O(PD×N((η6+4×η7)d+f(d)))=

O(d+f(d))

(14)

麻雀种群中加入者数量为(1-PD)×N,(1-PD)为加入者比例,每一维位置按式(11)进行更新的时间为η8,生成莱维飞行随机步长算子的时间为η9,则该阶段的时间复杂度为:

T4=O((1-PD)×N((η8+η9)d+f(d)))=

O(d+f(d))

(15)

麻雀种群中警戒者数量为SD×N,SD为警戒者比例,每一维位置按式(4)进行更新的时间为η10,两个正态分布随机参数更新的时间为η11,则这一阶段的时间复杂度为:

T5=O(SD×N((η10+2×η11)d+f(d)))=

O(d+f(d))

(16)

最大迭代次数为Max-iter,综上,EGSSA算法的时间复杂度为:

T'=T1+Max-iter(T2+T3+T4+T5)=

O(d+f(d))

(17)

综上可知,EGSSA与标准SSA算法的时间复杂度在数量级上一致,该文针对标准SSA的不足所提出的改进策略没有增加计算负担。

4 仿真实验结果与分析

4.1 仿真实验环境

仿真实验环境为:操作系统Windows10(64 bit),CPU为Intel(R)Core(TM) i5-4200M,内存12 GB,主频2.50 GHz,仿真软件为python3.9。

4.2 比较对象和参数设置

为验证改进EGSSA算法的优越性以及可行性,将提出的EGSSA算法分别与其他经典元启发式算法(鲸鱼优化算法(WOA)[15]、粒子群算法(PSO)[16]、灰狼算法(GWO)[17]、飞蛾扑火算法(MFO)[18])、三种其他文献所提改进算法(自适应变异麻雀算法(AMSSA)[19]、自适应t分布与随机游走麻雀算法(ARSSA)[20]、基于等级制度与布朗运动的混沌麻雀算法(CSSAHB)[21])在基准函数上进行仿真对比,通过最优值、平均数以及标准差三个指标的比较来检验所提改进算法的求解精度与稳定性。所选的基准测试函数中F1-F5、F6-F9、F10-F12依次是单峰、多峰、低维多峰函数,单峰函数用来验证算法的开发能力,多峰函数用来检验算法能否脱离局部最优。

所选基准测试函数见表1。设定种群规模N=50,

表1 基准测试函数

F1-F9维度d=30,Max-iter为500。为保证公平,实验中各算法均独立运行30次。其余各参数设置见表2。

表2 各算法参数设置

4.3 EGSSA与其他元启发式算法对比分析

为验证EGSSA的寻优性能,将提出的EGSSA算法与传统元启发式算法:标准麻雀搜索算法(SSA)、鲸鱼优化算法(WOA)、粒子群算法(PSO)、灰狼算法(GWO)、飞蛾扑火算法(MFO)在12个测试函数上进行仿真实验,实验维度为30,其余参数设置见表2,独立运行30次的实验结果见表3。

由表3的仿真实验结果可见,在所选12个基准测试函数上,EGSSA算法寻优稳定性和求解精度均表现最优,在F4函数上虽未找到最优值,但是平均值以及标准差是所选算法中最优的,算法收敛精度以及稳定性更能得到保证。SSA算法在F1、F3、F4、F7、F8、F10～F12函数上虽能偶尔寻到最优解,但较小的平均值以及较大的标准差表明算法具有强烈的不稳定性,在低维固定维度函数F10～F12上,其他群智能算法存在与标准SSA算法同样的问题,改进的EGSSA算法明显克服了这一不足,提高算法收敛精度的同时保证了算法求解的稳定性。综合对比实验结果的平均值、标准差可得出,EGSSA的收敛精度更高,稳定性更好,明显优于其余5种算法。

表3 与其他群智能算法实验结果对比

为更直观地对比EGSSA与GWO、MFO、PSO、WOA、SSA的寻优速度和性能,图1给出在12个测试函数上独立运行30次的平均收敛曲线。图中横坐标为迭代次数,为便于比较,纵坐标中函数值为正值的图像作以10为底的对数处理。

图1 不同群智能算法收敛曲线

由图1收敛曲线可看出,EGSSA算法的收敛曲线在12个基准测试函数上均表现更平滑,收敛速度更快。在单峰测试函数F1-F4上,EGSSA表现出远超于其他算法的收敛速度和求解精度(见图1(a)-(d));在F5函数上虽未达到理论最有值,但结合收敛曲线图实验结果来看,EGSSA收敛速度在所有算法中最快(见图1(e)),平均值与标准差更小;在F6-F12多峰测试函数上,EGSSA都能在迭代100次以内快速靠近全局最优,并未像其他算法一样陷入局部最优,与其他算法相比表现出明显的优越性(见图1(f)-(l))。

4.4 Wilcoxon秩和检验

仅比较平均值和标准差并不能完全说明算法之间的差异性,为充分证明提出的EGSSA算法相比其他算法的优越性,本节采用统计方法Wilcoxon秩和检验来验证EGSSA算法与其他算法性能是否有显著差异。实验设定显著性水平为5%。当p<0.05时,拒绝原假设,判定EGSSA与其他算法具有显著差异;否则判定EGSSA与其他算法并无显著差异,寻优性能相当。

表4为在显著性水平5%下EGSSA与SSA、GWO、MFO、PSO、WOA之间的Wilcoxon秩和检验结果。

表4 Wilcoxon秩和检验p值

由表4数据可知,大部分p值远小于0.05,表明EGSSA在优化性能上优于所选传统智能优化算法。

4.5 EGSSA与其他改进策略的SSA算法对比分析

为进一步验证所提算法具有优越性能,本节将EGSSA算法与文献[19]提出的自适应变异麻雀算法(AMSSA)、文献[20]提出的自适应t分布与随机游走麻雀算法(ARSSA)、文献[21]提出的基于等级制度与布朗运动的混沌麻雀算法(CSSAHB)进行对比分析。测试函数选取表1中F1-F8,其中F1-F6迭代次数为1 000,F7、F8两个函数迭代次数依旧为500。种群规模N=50,实验维度为30,各算法在测试函数上独立运行30次,其余参数设置见表2。为保证实验对比公平合理性,对比的三种改进算法实验结果与文献[20]数据结果相同,对比结果见表5。

表5 不同改进算法实验结果对比

由表5可知,对于函数F3、F7、F8所有改进算法均寻到理论最优值,且标准差为0;EGSSA算法在函数F5上各项指标略差于其他三种改进算法,在其余函数上,EGSSA算法寻优精度及稳定性均优于AMSSA算法;对于函数F2和F4,EGSSA算法可以稳定收敛到理论最优,而其他算法仅ARSSA算法在F2函数上寻到最优值;四种算法在函数F6上均未稳定收敛到最优值,但是EGSSA算法的平均值和标准差两个指标均优于其他三种算法。综上,融合精英反向学习与黄金正弦的麻雀搜索算法寻优能力更强、稳定性更好,与其他策略改进算法相比同样具有一定的竞争优势。

5 结束语

针对标准SSA算法迭代后期种群多样性减少、早熟收敛等不足,提出一种基于混合策略改进的麻雀搜索算法。在迭代过程中融入精英反向学习机制,丰富种群多样性,提高种群质量,提升算法搜索效率和收敛精度;在发现者搜索时采用黄金正弦策略,有效协调算法搜索能力和开发能力;最后在加入者靠近发现者时引入莱维飞行步长,增加个体位置变化多样性,有助于跳出局部最优,避免算法“早熟收敛”。选择单峰、多峰、固定维度多峰12个基准测试函数进行仿真实验,对比经典元启发式算法、其他改进算法寻优性能。研究结果表明,所提改进算法具有更好的收敛性能、全局寻优性能以及稳定性。