多方向螺旋搜索的混沌海鸥优化算法

张冰洁,何 庆,戴松利,杜逆索

1(贵州大学 大数据与信息工程学院,贵阳 550025) 2(贵州大学 贵州省公共大数据重点实验室,贵阳 550025)

1 引 言

近些年来,越来越多的学者受到自然界动植物的启发,模拟动植物的行为提出优化算法[1],例如群智能算法中蝴蝶优化算法(Butterfly Optimization Algorithm,BOA)[2],樽海鞘算法(Slap Swarm Algorithm,SSA)[3],萤火虫算法(Fire-fly Algorithm,FA)[4],秃鹰搜索算法(Bald Eagle Search,BES)[5]等,以及后来提出的人工蜂群算法(Artificial Bee Colony,ABC)[6]、黏菌优化算法(Slime Mould Algorithm,SMA)[7]、蝠鲼觅食优化(Manta Ray Foraging Optimization,MRFO)[8].随着算法的性能不断地改进,这些算法已经成功被应用到各种复杂问题的优化解决.

海鸥优化算法(Seagull Optimization Algorithm,SOA)[9]是Dhiman 和 Kumar 在 2019 年提出一种新的基于生物行为启发的元启发式算法.SOA算法模拟了现实生活中海鸥的生活方式,通过模拟海鸥寻找迁移位置和攻击候鸟的两种行为,实现了算法全局搜索以及局部搜索的功能.SOA算法的原理较为简单,也容易实现,目前已经用于解决一些工业问题以及分类问题[10].虽然SOA算法在一定方面上具有较大的优势,但由于算法搜索能力不足、海鸥行动路线较为单一,导致海鸥算法容易陷入局部最优解,收敛精度较差.针对上述问题,目前提出的解决方法有对算法加入莱维飞行[11]的机制,通过增加海鸥飞行过程中的随机性来提升算法全局搜索的能力.文献[11]中还提出了一种添加非线性递减的惯性权重来调整海鸥的飞行位置,使得算法能够能快地找到解.

上述改进方法对于SOA算法的收敛速度和精度都有一定程度上的改善,为了进一步提高SOA算法的寻优性能和收敛速度,本文提出了多方向螺旋搜索的混沌海鸥优化算法(MESOA).首先,算法加入了二维的kent映射混沌初始化,使得初始海鸥个体位置分布更加均匀,使海鸥能够更快、更加准确的接近目标食物源;其次,提出多方向螺旋飞行路径,让海鸥接近目标食物源时不再是以前的单一轨迹,用不同的飞行路径交换进行,使海鸥能够探索更多的区域,增加算法的多样性;最后,根据算法收敛情况控制海鸥个体围绕目标小范围搜索,当算法适应度方差小于一定数值之后对目标进行小范围搜索,减慢算法收敛速度,提高算法跳出局部最优的能力.本文选取了8个基准测试函数对算法进行了实验,以不同角度对于算法的性能进行测试,并使用Wilcoxon秩和检验来证明算法的性能,结果表明了MESOA算法改进在寻优能力、稳定性、鲁棒性等方面均有提升.

2 海鸥优化算法

海鸥优化算法[9],是通过模拟海鸥最重要的迁徙和攻击两种行为模式提出的算法.海鸥是群居动物,根据季节的更替会大规模地从一个地方迁徙到另外一个地方,目的是为了寻找最丰富的食物.在迁徙的过程中海鸥个体之间为了不发生碰撞会飞行在不同的位置,在一个群体中,每一个海鸥个体都会朝着最丰富食物的位置移动,来改变自身的位置.为了取得更多的食物,海鸥常常会攻击其他的候鸟,海鸥迁移和攻击的行为可以用如下数学模型来描述.

2.1 迁移

在这个过程中,算法模拟了海鸥种群从原来位置移动到一个新的位置.这个阶段里,海鸥个体要满足以下的3个条件:

1)避免碰撞:

Cs(t)=A×Ps(t)

(1)

(2)

其中Cs(t)表示不会和其他海鸥碰撞的新位置,Ps(t)表示海鸥攻击的位置,t表示迭代的次数,Maxieration表示最大迭代次数,fc用于控制A的频率,这里fc取值为2,控制A从2下降到0.

2)最佳位置方向:

Ms(t)=B×(Pbs(t)-Ps(t))

(3)

B=2×A2×rd

(4)

其中Ms(t)是当前海鸥的移动方向,Pbs(t)是指当前海鸥个体找到的最优位置,rd是一个取值为(0,1)的随机数.

3)靠近最佳位置：

Ds(t)=|Cs(t)+Ms(t)|

(5)

Ds(t)是海鸥移动到的新位置,|·|是绝对值.

2.2 攻击

在这个过程中,算法模拟了海鸥攻击候鸟的行为.当海鸥进行攻击时,它们利用翅膀在空中以螺旋形状进行运动,模拟三维坐标x,y,z来对它进行描述,海鸥的攻击位置可以用以下公式表示:

Ps(t)=Ds(t-1)×x×y×z+Pbs(t-1)

(6)

Ps(t)是指这一时刻海鸥攻击的位置.Ds(t-1)是上一时刻海鸥的位置,Pbs(t-1)是上一时刻海鸥个体找到的最优位置.

x=r×cos(θ)

(7)

y=r×sin(θ)

(8)

z=r×θ

(9)

r=u×eθv

(10)

其中r表示移动时的螺旋半径,θ是在(0,2π)中随机取值的角度.而u和v是定义e的常数.

3 多方向螺旋搜索的混沌海鸥优化算法

3.1 Kent映射初始化

原本的海鸥优化算法初始化是在上下界内随机生成海鸥个体的位置,这样的初始化可能会使海鸥在空间中位置分布得不均匀,导致算法早熟,陷入局部最优解.为了解决这一问题,本文提出基于Kent混沌序列的初始化形式.

由于混沌映射的随机性、遍历性等性质,可将其用于群智能算法种群的初始化中.其原理是利用混沌映射产生的在[0,1]之间的序列,再根据混沌因子对海鸥种群进行初始化.这样可以控制海鸥在最初的分布更加合理,避免早熟.Kent映射的数学模型由式(11)给出:

(11)

当a=0.5时,系统会呈现短周期状态,故本文中a的取值范围是(0.01,0.5).利用混沌映射初始化的模型由式(12)给出:

x=xmin+Chaos×(xmax-xmin)

(12)

其中,xmin与xmax分别代表自变量取值的下限和上限.chaos为Kent映射函数产生的混沌因子.

图1(a)和图1(b)分别给出了在(0,10)范围内,随机初始化和利用Kent序列初始化的分布图,可以看出图1(a)中种群在取值的边界处分布较为密集,而在中间地带则较为稀疏,图1(b)中种群分布则较为均匀.

图1 初始化分布图Fig.1 Initialize distribution map

利用混沌序列优化算法时,最初考虑Logistic映射,但Logistic映射并不是最好的.利用Logistic映射初始化的序列在[0,1]范围内呈切比雪夫分布,从整体上来看,搜索盲区较大.本文采取Kent映射进行初始化.Kent映射具有更好的遍历性,可以克服Logistic映射的缺点,使初始化更加均匀.

图2为在Schwefel′s Problem 1.2函数的测试下,海鸥算法利用随机初始化、Kent初始化以及Logistic初始化之后的收敛曲线.Sphere函数的最优值为0,实验迭代次数为500.可以看出,利用混沌序列初始化之后的算法收敛性均强于随机初始化,而利用Kent初始化在迭代100次以后的精度就明显强于利用Logistic初始化.利用Kent序列进行初始化之后,海鸥个体的分布更加均匀,能够更加准确地接近目标,增加了算法的多样性.

图2 初始化收敛曲线Fig.2 Initialized convergence curve

3.2 多方向螺旋飞行路径

在初始的海鸥算法中,攻击阶段的位置更新方式如按照公式(6)所示.从式中可以看出,海鸥在经过迁移过后,基于迁移过后的位置依照给定的行动模型寻找攻击位置.由于行动模型单一化,海鸥移动时存在飞行死角,导致有可能错过最优位置.即搜索过程中找不到最优值,只能找到局部最优值的情况.为解决这一问题,本文提出以下这种新的海鸥攻击位置更新方式.

(13)

其中r1是在(0,1)之间的随机数,a为海鸥选择更新方式的阈值,在多次实验之后得出取值为0.8最为合适,此时Ts(t)为适应多方向螺旋的海鸥迁移位置,如式(14)所示：

Ts(t)=Cs(t)+Ms(t)

(14)

Pbs(t)、Cs(t)、Ms(t)含义已在海鸥优化算法中介绍过.经过改进的位置更新方式让海鸥根据阈值选择攻击方式,两种不同的攻击方式使海鸥的飞行轨迹不再单一,能够搜索更多的区域.两种不同攻击方式交替进行,缩小了海鸥飞行死角,减少了飞行盲区.以不同的方式,可以得到不一样的结果,即以不同的角度更新最优值,增加了算法的多样性.

3.3 根据收敛情况进行小范围搜索

基于原始的海鸥算法存在易陷入局部最优值这一问题,本文提出一种新的位置更新机制.在每次迭代时计算种群中海鸥适应度的方差,根据方差的大小来判断是否围绕目标位置进行小范围的搜索.具体数学表达如式(15)和式(16)所示：

(15)

其中δ表示方差,n为海鸥的种群数量,Ps(i)为第i个海鸥种群的适应度,Pavg为海鸥种群的平均适应度,Pbs为种群中的最优适应度,Pls为种群的最差适应度.

当δ

Ps(t)=Ps(t-1)×(1+sin(R))

(16)

其中Ps(t-1)表示上一次迭代时的位置,R为在(-2,2)区间内服从正态分布的随机数.

图3为在Sphere函数的测试下,海鸥算法根据不同阈值b进行小范围搜索的收敛曲线,Sphere函数的最优值为0,实验迭代次数为500.由图3可以看出,加入小范围搜索后,算法精度明显高于加入之前,而当阈值b取0.8时,有最好的搜索效果.故当迭代过程中海鸥适应度方差小于0.8时,海鸥进行围绕目标的小范围搜索.每个海鸥个体利用正态分布模型,围绕前一刻的位置进行小范围搜索.在搜索的过程中,若发现比之前寻找的最优解更好的解,即重新更新最优解的值,再根据新的适应度值方差判断是否再次进行小范围搜索.这样的位置更新机制增加了算法的多样性,减慢算法收敛过程,避免算法陷入局部最优值,增强了算法跳出局部最优解的能力.

图3 阈值b收敛曲线Fig.3 Convergence curve of threshold b

3.4 MESOA算法

本文提出的MESOA算法将海鸥种群进行Kent初始化,对初始化后的海鸥种群进行迁移与多方向地攻击,更新海鸥位置,再根据方差判断是否进行小范围搜索.MESOA算法在增加了上述改进后,增加了算法多样性,提高了算法跳出局部最优的能力.多方向螺旋搜索的混沌海鸥优化算法的流程图可见图4,算法的伪代码如下:

图4 多方向螺旋搜索的混沌海鸥优化算法流程图Fig.4 Schematic diagram of MESOA

MESOA算法

begin

设置初始参数:种群规模N,最大迭代次数Maxieration,需要测试的函数F.

Kent初始化种群,计算个体适应度

设置初始参数:种群规模N,

while t

for i=1 to N do

根据式(14)更新海鸥迁移位置

根据式(15)计算方差δ

ifδ<0.8:

根据式(16)更新海鸥攻击位置

else:

根据式(13)更新海鸥攻击位置

end

根据式(14)更新海鸥迁移位置

end for

end while

end

3.5 时间复杂度计算

算法的时间复杂度可以表示算法运算的速度,从而反应算法的效率.若改进算法的过程中增加了时间复杂度,会让算法效率变低,这是不利于计算的,故本文在此计算算法改进前后的时间复杂度.

标准SOA算法需要计算:随机初始化参数O(1),计算算法初始适应度O(N),迭代计算函数最优值O(NT),则整个算法所需的时间复杂度为:

O(1)+O(N)+O(NT)=O(NT)

(17)

这里的N为种群大小,T为迭代次数.

经过改进之后的MESOA算法需要计算:Kent混沌初始化参数O(NT),计算算法初始适应度O(N),迭代计算最优值O(NT),混合策略更新位置O(NT),方差判断小范围搜索O(N),则整个算法所需的时间复杂度为:

O(NT)+O(N)+O(NT)+O(NT)+O(N)=O(NT)

(18)

文献[11]中的I-SOA算法对于SOA算法的优化改变了惯性权重O(NT),增加了莱维飞行机制O(NT),故I-SOA算法所需的时间复杂度为:

O(1)+O(N)+O(NT)+O(NT)+O(NT)=O(NT)

(19)

由此可得,本文改进后的算法MESOA时间复杂度O(NT)与改进之前的SOA算法时间复杂度O(NT)以及文献[11]改进的I-SOA算法时间复杂度O(NT)相同,没有增加,故MESOA算法的改进对算法计算的效率并未产生负面影响.

4 实验仿真与分析

4.1 实验环境和参数设置

本文实验的运行环境为64位Windows 10操作系统,处理器是Intel Corei7-10750H,使用的软件是MATLAB R2018b.

本文的实验引入了8个经典测试函数,如表1所示.其中F1-F4为单峰函数,函数的局部最优值就是函数的全局最优值,通常用于检测算法的收敛速度和寻优精度;F5-F8为多峰函数,这些函数存在多个局部最优值,通常用于测试算法跳出局部最优值和对全局进行探索的能力.

表1 测试函数Table 1 Test function

4.2 验证本文算法有效性

为了验证本文算法的有效性,本文选择了3种不同的优化算法:贝叶斯优化算法(BOA)[12]、灰狼优化算法(GWO)[13]、鲸鱼优化算法(WOA)[14]来与未经改进的海鸥优化算法(SOA)[9]以及本文提出的改进算法MESOA进行试验.为了降低实验偶然性,对每个测试函数均进行30次独立实验后,取实验结果的最优值、平均值和标准差进行对比.本次实验时所设置的参数有:种群规模N=50,最大迭代次数T=500,空间维度dim=30.列出实验后的数据见表2.

从表2可以看到,就单峰函数F1-F4而言,SOA算法的寻优能力比BOA,GWO以及WOA算法要强,且MESAO算法的寻优能力最强,能够在最快时间内找到最好的解.例如函数F1,函数SOA找到的最优值是3.57E-127、函数BOA找到的最优值是9.42E-12、函数GWO找到的最优值是6.91E-36、函数WOA找到的最优值是4.36E-94、而函数MESOA找到的最优值是0,寻优能力明显强于其他4个函数.对于前4个测试函数,算法MESOA都能找到它的理论最优值,实验说明了本文算法具有较好的寻优能力和收敛精度.

表2 不同算法寻优结果对比Table 2 Comparison of the results of different algorithms

对于F5-F8,5种算法均未找到最优值,但MESOA算法找到的解在5个不同的解中属于最优解,且明显优于改进之前的SOA函数所找到的解.如F6函数,改进前算法解的平均值为1.87E+01,而改进后的MESOA算法解的平均值可以达到8.88E-16,与改进之前相差17个数量级,说明本次改进确实提高了了算法的全局搜索能力以及给予了算法跳出局部最优解的能力.在F5、F7、F8中,MESOA的标准差没有达到最小,如在F7中WOA算法的标准差为2.20E-01,是几个算法中最小,而MESOA算法的标准差为2.58E-01,较WOA算法略微大些.结合改进前的SOA算法标准差为4.62E-01,可知改进后算法的标准差有所下降,出现这种结果的原因是SOA算法的寻优模式主要依靠攻击时的旋转寻优,搜索路径较为单一,故而导致算法在某些函数中稳定性稍低.本文针对海鸥搜索方向做出改进,对于标准差的降低有所影响,但还是在某些函数中不如另一些算法,这也是对海鸥优化算法以后改进的空间.

图5(a)-图5(f)是5种优化算法在求解8个函数最优值时,随迭代次数增加,其适应值的变化.从图中可以看出,MESOA在绝大部分测试函数中具有更强的寻优能力,收敛速度快,解的精度高.例如F1函数,由于本次改进为了避免算法陷入局部最优而减慢了算法的收敛速度,可以看出在最初算法收敛得并不是很快,可以搜索更大的范围.当算法迭代到第207代时,MESOA算法所寻得的最优值是1.31E-08,在5种算法中排名第4,并且各个算法寻到的最优值也拉不开差距.当算法迭代进行到384代时,MESOA算法已能寻到最优值1.59E-127,这个数值放到第500次迭代中也已是最优,可以看出各个算法寻找到的最优值已经初步拉开距离.而在之后的迭代中,MESOA算法迅速寻优且在迭代结束之前达到近理论最优值0,是5种算法中最好的.且MESOA算法仅仅在F6函数中与算法WOA寻找到解的精度相同,寻找到的解的平均值是8.88E-16,与SOA算法相差15个精度,在其余的函数测试中均能在最少的迭代次数下取得最好的寻优结果.

图5 测试函数平均收敛曲线Fig.5 Average convergence curve of test function

4.3 与其他最新改进算法性能对比

为了能够更好地研究MESOA算法的优化性能,本文将提出的MESOA算法与一种基于非线性惯性权重的海鸥优化算法I-SOA、以及另两种优化算法法CPWOA[15]、LWOA[16]进行对比.MESOA算法的数据在30维进行计算,经过50次独立实验,取实验过后的平均值和标准差进行比较,其他算法的测试数据从相应参考文献中找到这些算法的实验数据,在30维对他们的寻优性能进行比较,其他参数在原参考文献中给出,相应数据在表3中可以看到(相关文献中没有给出的数据在表格里用…表示).

从表3中可以看出,MESOA的寻优性能在4个函数中明显偏好,在F1、F2、F3、F4中,MESOA算法都能找到理论最优值,在F5-F8中,MESOA的寻优结果相对也较好.另外的3种算法中,较差的是CPWOA算法,无论是哪一个函数找到的最优值都不算太好,较好的是LWOA算法,在单峰测试函数中有两个能找到理论最优值,在MESOA算法与LWOA算法找到理论最优值0的F1函数中,最差的CPWOA算法仅能找到2.82E-02,解的精度相当低.而同样是海鸥算法的改进算法I-SOA与MESOA相比较,MESOA的寻优性能明显要优于I-SOA.在单峰测试函数F1-F3中,MESOA能找到理论最优值的,而I-SOA算法仅能寻找到低精度的解,在F1函数中I-SOA算法找到解2.59E-03,仅仅比最差的CPWOA算法提升一个精度.在F2与F3函数中,I-SOA算法的表现也远远不如MESOA算法,甚至不是其他3个算法中表现得最好的.仅仅在F7函数中,I-SOA算法的寻优能力要略强于MESOA算法.I-SOA算法对于SOA算法加入莱维飞行机制,增加了算法种群位置的多样性,种群位置多样性的增加对于某些函数的寻优任务起着重要的作用.这也变相地反映出SOA算法对于种群位置多样性上存在不足,有着较大改进的空间.

从整体看来,MESOA算法对于SOA算法的改进整体要优于I-SOA算法,且在近些年新兴的改进算法中也有一定的竞争力.实验结果说明了本文对于海鸥算法的改进具有较好的寻优能力和收敛精度,本次改进确实提高了了算法的全局搜索能力以及给予了算法跳出局部最优解的能力.

4.4 不同维度下测试算法

为了测试不同维度下算法的能力,这里选择了5个算法分别为SOA、BOA、GWO、WOA和MESOA,分别在50维、200维和500维进行了实验,实验中所选择的参数有:迭代次数T为500,种群数量均为30,50次独立试验后取了每个算法对于函数的最优值、平均值和标准差进行对比,实验结果如表4所示.

从表4中可以看出,在单峰函数中F1-F4中,另外的4种算法在各个函数的寻优表现各不相同,但都不如MESOA表现的好.例如函数F1在低维阶段,SOA算法表现得较好,50维时可以找到的最优值能达到8.61E-132,与BOA算法找到的最优值相差了121个数量级;而在高维阶段,算法WOA所寻得的平均值又比SOA要好,在500维时,算法WOA所寻得的平均值为1.37E-79,这与GWO算法所寻得的平均值相差了75个维度.随着维度的增加,算法寻优的难度增大,而MESOA算法可以在50、200、500维度都寻得函数的理论最优值0.再看函数F3,从低维来看,算法BOA表现得较好,50维时BOA寻得的最优值为9.32E-12,最差的WOA算法寻得的最优值为9.92E+04,相差了16个数量级.在500维时,BOA算法寻得的最优值9.71E-05反不如SOA算法寻得的最优值3.97E-07,几个算法在低维和高维都没能找到精度太高的解,说明F3这个函数的寻优难度较大,而MESOA算法的表现却一直很稳定,在实验所选择的3个维度都能能都寻找到理论最优值0.在F1-F4这4个单峰函数中,MESOA算法仅在F2函数的500维寻优时没有找到理论最优值0,在其余算法的不同维度都比其他算法能更快、更精准地找到最优值.这说明MESOA算法在单峰函数寻优时具有较强的寻优精度、稳定性以及鲁棒性.

表4 不同维度下的算法测试Table 4 Algorithm testing in different dimensions

在F5-F8这4个多峰函数寻优过程中,5个函数都没有找到理论最优值,但无论是哪一个算法哪一个维度,MESOA算法都能找到最佳的最优值以及平均值,且对比改进之前的SOA算法寻优能力明显有所增长.例如函数F6中,虽然在50维时,SOA算法与MESOA算法寻找到的最优值相同,都是8.88E-16.但维度增加到500维时,MESOA算法找到的最优值依然是8.88E-16,并没有受到维度的影响,但SOA算法找到的最优值却改变为2.04E+01,算法性能受维度改变影响较大,500维时MESOA算法与SOA算法相差了17个维度.再看F7函数,在30维时MESOA算法找到的最优值为4.82E-06,经过将维度增加到500维后,MESOA算法找到的最优值没有变差反而变好,最优解为1.85E-08.这说明经过改进后的算法稳定程度有所保证,并没有因为维度增加算法性能有很大的折扣,改进后的算法收敛精度也有所提升.

在8个基准函数之中,MESOA算法寻得的解在绝大多数情况下都是最好的,这说明MESOA的寻优能力较好,且稳定性也有所保证,随着实验过程中维度的增加,其他算法的寻优精度或多或少有所影响时,MESOA的寻优性能却基本没有改变,这说明MESOA算法有着较强的鲁棒性.

4.5 Wilcoxon秩和检验

在之前做的几个实验中,仅仅是最优值、平均值和标准差的对比还不够完整,Derrac提出采用Wilcoxon秩和检验进行统计分析[17]可以对于不同次数地实验结果独立地进行对比,能够避免算法偶然性的优势[18].文献[17]中表示,Wilcoxon秩和检验的p值可以对于不同算法的差异性进行比较.当p的值小于5%时,表示两种算法的差异性显著,否则说明两种算法在整体来说差异不大.

本次实验利用之前介绍的4个单峰基准函数和4个多峰基准函数,将SOA、BOA、GWO、WOA、I-SOA与本文的多方向螺旋搜索的混沌海鸥优化算法MESOA进行对比.所选参数为迭代次数T=500,种群大小n=30,维度dim=30,进行50次独立的实验,分别计算每个算法与MESOA算法的p值,其中I-SOA算法的数据为参考文献中给出的数据.表5中最后一行的符号“+”、“-”和“=”表示:表格中另外几个算法与MESOA算法相比较,MESOA算法的性能优于、劣于和等于表格中另几种算法.根据表5中的结果,与其他几种算法比较,MESOA算法的p值均低于5%,基本都处于10的-10次方以上,这说明MESOA算法的性能对比其余几种算法有着显著的提升,即MESOA算法相比于SOA、BOA、GWO、WOA和I-SOA算法具有更好的寻优能力.

表5 测试函数Wilcoxon秩和检验的p值Table 5 p values of Wilcoxon rank sum test of test function

5 结束语

为了改善海鸥优化算法(SOA)的各项不足,本文提出了多方向螺旋搜索的混沌海鸥优化算法(MESOA),首先,在初始化时利用Kent混沌序列让海鸥个体分布得更加均匀,使海鸥更准确地找到目标;其次,令海鸥选择不同得飞行方向,增加了新的飞行方向,使其行动轨迹不再单一,增大海鸥寻优范围;最后,在迭代中通过海鸥适应值的方差控制海鸥判断是否进行小范围搜索,增加了算法多样性,增强算法跳出局部最优解的能力,提高算法的寻优精度.为了验证本文算法改进的可行性,通过8个基准测试函数对于算法进行了3组实验,并使用Wilcoxon秩和检验来证明了算法的有效性.实验不仅证明了MESOA算法与不同的改进算法具有可比性,还体现出改进之后的算法在寻优能力、稳定性、鲁棒性等方面都有明显的提升.