融合改进Logistics混沌和正弦余弦算子的自适应t分布海鸥算法

毛清华,王迎港

(燕山大学 经济管理学院,河北 秦皇岛 066004)

1 引 言

通过模拟自然界中某些生物的运动或者行为规律,众多新型群智能优化算法被提出,用以搜索复杂优化问题分布在一定的解空间范围内的最优解.如樽海鞘群算法(Salp Swarm Algorithm,SSA)[1]、鲸鱼优化算法(Whale Optimization Algorithm,WOA)[2]、蝴蝶优化算法(Butterfly Optimization Algorithm,BOA)[3]、粒子群算法(Particle Swarm Optimization,PSO)[4]、花粉算法(Flower Pollination algorithm,FPA)[5]、灰狼优化算法(Grey Wolf Optimization,GWO)[6],海鸥优化算法(Seagull Optimization Algorithm,SOA)[7]等.其中SOA是Dhiman等于2019年提出的一种新型群智能优化算法,其结构简单并且具有相对较好的全局搜索和局部搜索能力,但是也存在诸如多样性不足、后期收敛速度慢等缺陷.

针对基本海鸥算法存在的缺陷,国内外学者提出了一些改进方案:如Cao,Y等[8]使用莱维飞行机制提高了海鸥算法的收敛速度.Jia,HM等[9]将TEO算法中的热交换思想融入海鸥算法,通过优化位置更新公式增强了算法的局部搜索能力.Jiang,H等[10]基于对立学习策略提出了OSOA算法,通过应用OBL增强了海鸥种群的多样性.Dhiman,G等[11]提出了进化多目标海鸥优化算法(EMoSOA),并引入交叉和变异遗传算子增强算法的收敛性和多样性.尽管实验数值表明以上改进海鸥算法具有不错的性能,但都是对算法单一角度的优化,缺少对海鸥算法较为全面的改进.

随着对群智能优化算法研究的深入,学者们引入了不同的改进策略对算法进行优化,如陈忠云等[12]应用Logistics混沌映射进行樽海鞘算法的种群初始化,丰富了种群的多样性.郝晓弘等[13]引入非线性策略改进的收敛因子和惯性权重,在平衡鲸鱼优化算法的全局探索与局部开发能力的同时加快了算法的收敛速度.王依柔等[14]为平衡蝴蝶算法的局部搜索与全局搜索能力,在自身认知飞行部分引入正弦余弦算子.宁杰琼等[15]在花粉算法全局授粉过程中,利用t分布扰动的随机个体和莱维飞行共同实现个体位置更新,加快收敛速度同时提高搜索空间的多样性.王岳等[16]将自适应惯性权重引入粒子群优化算法,非线性递增策略的采用平衡了算法的全局搜索与局部开发能力.

受上述研究的启发,本文提出了一种融合改进Logistics混沌和正弦余弦算子的自适应t分布海鸥算法(ISOA).采用改进Logistics混沌映射初始化海鸥种群,使海鸥更加均匀地分布于初始解空间.对参数A进行改进,用以加快算法的收敛速度.在海鸥迭代过程中引入正弦余弦算子,平衡算法全局搜索和局部开发能力.在最优解附近生成符合自适应t分布的新解并以一定的概率接受这个新解,在保留精英个体信息的同时提高算法跳出局部最优的能力.

2 标准海鸥优化算法

海鸥是地球上具有高等智慧的群居类动物,在全球各地均有分布,其种类较多且体态不一.海鸥是季节性迁徙鸟类,会根据季节变化为获取食物进行迁徙.海鸥算法的基本思想就是模拟海鸥的迁徙和攻击行为,通过不断更新海鸥位置迭代寻求最优解.

2.1 迁徙

在进行全局搜索时,海鸥算法模拟海鸥群在迁徙途中的位置移动进行搜索.海鸥位置移动应满足3个前提条件:

1)避免碰撞:通过海鸥当前位置与附加变量A来确定海鸥的新位置,变量A控制避免相邻海鸥间发生碰撞.

(1)

A=fc-[t×(fc/Tmax)]

(2)

变量A的取值范围取决于fc的大小,本文fc的值设置为2.A的值随迭代次数的增加从2线性降低至0,Tmax为最大迭代次数.

2)最佳位置方向:为了避免与相邻海鸥发生碰撞,海鸥会向最佳海鸥位置所在的方向移动.

(3)

B=2×A2×rd

(4)

rd在[0,1]区间内随机取值.

3)接近最佳海鸥位置:在海鸥个体到达不与其他海鸥存在冲突的位置后,海鸥会更新位置,从而更接近最佳海鸥位置.

(5)

2.2 攻击

海鸥攻击猎物时,通过翅膀和重量保持高度,在空中进行螺旋飞行运动,不断改变攻击角度和速度.X、Y和Z平面的运动行为描述如下:

(6)

其中r是海鸥进行攻击行为时螺旋飞行的半径,θ为[0,2π]区间内的随机角度值,u和v是常数,e是自然对数的底数.

(7)

综上可以得到海鸥算法的迭代公式:

(8)

3 改进海鸥算法(ISOA)

3.1 改进型Logistics混沌映射的种群初始化

在海鸥算法中,海鸥初始种群由随机生成.由于混沌具有遍历性和随机性的特点,可以使用混沌映射进行种群初始化.与随机生成的种群相比较,混沌映射生成的初始种群具有更好的多样性,初始解更均匀地分布在搜索空间,可以有效避免算法早熟和陷入局部最值,从而提高算法的收敛速度与精度.

Logistics混沌映射作为最经典的混沌映射方式之一,具有随机性、遍历性、强发散性等特点而被广泛应用于群智能算法的种群初始化.Logistics混沌映射函数如公式(9)所示:

xn+1=4xn(1-xn)xn∈(0,1),n=1,2,…

(9)

Logistics混沌映射被广泛应用于改进群智能优化算法,但是其仍存有分布不够均匀等缺陷.因此本文拟采用一种改进型Logistics映射(ILM)来初始化海鸥种群.设定目标优化函数为:

minf(x1,x2,x3,…,xn),ai

(10)

通过公式(11)得到均匀化级联混沌序列[yn]:

(11)

海鸥的初始位置由[yn]经过式(12)进行线性变换得到.

Zi=ai+(bi-ai)xn

(12)

其中,ai和bi表示优化变量区间的最小值和最大值.

设置迭代次数t=500,改进前后的Logistics混沌映射曲线如图1(a)和图1(b)所示.

对比图1(a)和图1(b),可以发现改进后的Logistics混沌映射曲线在[0,1]之间有更好的遍历性,分布更加均匀.改进型Logistics混沌相对于经典Logistics混沌性能更加卓越,用于初始化海鸥算法种群可以使海鸥更加均匀地分布于初始解空间,因此本文采用改进后的Logistics混沌映射进行海鸥种群初始化.

图1 改进前后Logistics混沌映射曲线对比图

3.2 参数A改进

海鸥算法通过引入fc控制变量A的频率,使变量A的值随迭代从2线性降低至0,fc通常设置为2.但是算法收敛过程是非线性的,因此线性收敛的参数A并不能完全适用于SOA的搜索过程.因此本文引入一种新型非线性递减的改进参数A,为提高算法的全局搜索能力引入符合beta分布的随机调整数对A进行局部扰动,避免算法陷入局部最优[17].新型非线性递减的参数A如公式(13)所示:

A=(Ainitial-Afinal)÷(1+e(20t/Tmax)-10)+

σ*betarnd(p,q)

(13)

其中Ainitial表示A的初始值,Afinal表示终止值,t为当前迭代次数,Tmax为最大迭代次数.σ为收敛调整因子,经多次实验发现σ=0.1时效果最好,betarnd为MATLAB中的随机数生成器,可以生成符合beta分布的随机数.

本文的改进参数A呈非线性递减,迭代前期参数A在较长时间内保持较大值且变化幅度、速度较小,即海鸥长时间以较大的步伐进行搜索,可以扩大海鸥的搜索范围;迭代中期改进的参数A下降速度明显,对于算法收敛速度的提高有重要作用;迭代后期,改进的参数A在较长时间内保持较小值且变化幅度和速度也较小,加强了算法的局部搜索能力.同时引入beta随机调整数对A的取值进行了局部扰动,意味着扰动海鸥的搜索步伐大小,增加了解的多样性.改进前后的参数A对比如图2所示.

图2 改进前后参数A对比图

3.3 正弦余弦算子

为了促进最优海鸥个体信息在种群中的传递,提高海鸥算法的性能,本文引入正弦余弦算子用以改变海鸥算法的迭代方式,即在迭代过程中改变原有迭代方式,按照相同的概率对海鸥个体进行正弦或者余弦操作,改进迭代方式如公式(14)所示:

(14)

其中r1=a-t×(a/Tmax),r1的值取决于常数a,本文a的取值为2.较大的r1值可以提高算法的全局搜索能力,而较小的r1值则有利于算法的局部开发,同时随着迭代次数的增加r1的取值逐渐变小,对算法的搜索和开发能力进行了平衡.r2在区间[0,2π]之间随机取值,定义了当前解接近或者远离最优解的距离;r3是[0,1]内的随机数,并以相同的概率切换正弦和余弦算子.

引入正弦余弦算子完美契合了海鸥算法的寻优机制,进一步平衡算法的全局搜索和局部开发能力.一部分海鸥遵循新的迭代方式远离最优解,扩大了搜索空间,增加了海鸥种群的多样性,避免原有寻优机制存在的盲点.而另一部分海鸥以更快的速度接近最优解,以较少的迭代达到更佳的寻优效果,提高了算法的收敛速度.正弦余弦算子的融入,丰富了海鸥种群的多样性,提高了算法的收敛速度和精度,极大提升了算法的性能.

3.4 自适应t分布变异策略

在智能优化算法中引入柯西变异和高斯变异已被证实可以有效提升算法性能.其中柯西变异可以丰富种群多样性,而高斯变异可以使算法获得良好的局部搜索能力.柯西分布和高斯分布都是t分布的两种特殊形式,随着迭代次数的增加,自由度参数t的增长,t分布曲线由开始的符合柯西分布逐渐接近高斯分布.

在最优解位置附近生成符合t分布变异的新解,可以同时结合高斯分布和柯西分布的优点.算法迭代初期,自由度参数t取值较小,这时候t分布主要呈现出柯西分布的特点,丰富了种群的多样性,有效提升算法的全局搜索能力;在迭代进行到中后期时,自由度参数t取值较大,t分布无限接近高斯分布,增强的是算法局部开发能力,提高其收敛精度.为了在前期丰富种群多样性的同时,在后期保留海鸥种群的精英解,这里同时引入自适应参数ω.在迭代前期ω可以取较大的值,利用t分布变异产生的新解增加种群多样性.随着迭代次数的增加算法逐渐接近最优解,自适应参数ω控制t分布对新解的影响逐步降低,充分保留了海鸥种群的精英解.符合t分布变异的新解和ω的表达式如公式(15)和公式(16)所示:

(15)

(16)

式中TD(t)表示自由度参数为t的t分布,a=0.1,b=1,T为最大迭代次数.

按照一定的概率接受自适应t分布变异的新解,随机生成一个参数pe∈[0,1],新的最优海鸥位置确定如公式(17)所示:

(17)

这样算法进行迭代寻优时,通过概率pe确定最优解时会有两种选择:一是继续按照原算法进行选择的最优解,维持种群多样性的同时保留了精英解;二是选择了自适应t分布变异扰动后产生的新解,其结合了高斯分布和柯西分布的优点.

3.5 改进海鸥算法的执行步骤

改进海鸥算法(ISOA)的具体执行步骤如下:

步骤1.海鸥种群根据公式(11)、公式(12)进行初始化;

步骤2.设置算法中的参数A,B,Tmax,A的初始值Ainitial和终止值Afinal.设置u=1,v=1,rd在[0,1]内随机取值,θ在[0,2π]内随机取值.其中A的表达式如公式(13);

步骤6.更新最佳海鸥位置和适应值;

步骤7.根据公式(15)对最优位置进行扰动;

步骤8.根据公式(17)确定最优位置;

步骤9.判断是否达到结束条件,若是则进行下一步,否则跳转步骤(2);

步骤10.程序结束,输出最优结果.

4 模拟仿真

4.1 算法参数设置

为验证ISOA算法的有效性,选取遗传算法(GA)、粒子群算法(PSO)和标准海鸥算法(SOA)进行对比.各个算法的种群规模设置均为30,最大迭代次数为100次,算法参数设置如表1所示.

表1 4种算法实验参数设置

4.2 标准测试函数选择

选择8个不同的标准测试函数,其中包括4个单峰函数,4个多峰函数,标准测试函数的具体信息如表2所示.

表2 8个标准测试函数

4.3 仿真结果分析

本文采用的实验环境为:Microsoft Windows 10系统,处理器为Inter(R)Core(TM)i5-7200U CPU@2.50GHz 2.70GHz,内存为8GB,采用 Matlab2014b进行算法的编辑和运行仿真.为减少实验的偶然误差,每个算法在每一个标准测试函数上独立运行100次.运行结果如表3所示.

表3中最优值和平均值可以反映算法的收敛和寻优精度.在4个单峰函数F1-F4上,ISOA求解函数F2时获得了理论最优值0,在其余3个单峰函数上相对于3个对比算法至少提升了10个数量级,求解函数F1时更是比标准SOA提升了31个数量级.对于4个多峰函数F5-F8,ISOA在函数F5、F7、F8上均能求得理论最优值,同时具有更好的收敛精度,例如求解函数F7时虽然标准SOA也获得了理论最优值,但其平均值与理论最优值有所偏差,而ISOA平均值等于理论最优值,说明其寻优能力更佳.因此,ISOA在求解单峰、多峰函数时相对3种对比算法都具有更好的寻优效果.

表3 基准测试函数优化结果

比较8个标准测试函数上4种算法的标准差,ISOA始终比其余3种算法小,而标准差可以反映算法的稳定性和跳出局部最优的能力,这说明ISOA具有较强的稳定性.因为多峰函数具有多个局部最值,一些经典算法很容易出现被局部极值吸引出现早熟的现象,从而无法求得全局最优解.ISOA在多峰函数上具有良好的表现,证明其具有很强的跳出局部最优的能力.

综上所述,ISOA在各方面都优于其余3种算法.为了更加直观地观察ISOA算法的收敛性和跳出局部最优的能力,图3-图11分别展示了4种算法在8个标准测试函数上的迭代收敛曲线.其中横坐标代表迭代次数,纵坐标代表适应度的Log值.

图3 函数F1迭代收敛曲线

图4 函数F2迭代收敛曲线

图5 函数F3迭代收敛曲线

图6 函数F4迭代收敛曲线

图7 函数F5迭代收敛曲线

图8 函数F6迭代收敛曲线

图9 函数7迭代收敛曲线

图10 函数F8迭代收敛曲线

图3-图6给出了4种优化算法在单峰函数上的运行结果.从图中可以看出,大部分情况下相对于其他3种算法ISOA算法的收敛曲线下降速度更快,距离x轴更近.而其余3种算法都出现了不同程度的停滞,寻优精度较低.收敛曲线下降速度快代表其具有更快的收敛速度,距离x轴越近代表其收敛精度越高.这说明应用改进型Logistics映射初始化种群增加了海鸥种群多样性,使得初始解分布更加均匀,算法收敛速度加快.而正弦余弦算子的引入,一方面进一步加快了算法的收敛速度,另一方面扩大了海鸥的搜索空间,避免了海鸥算法搜索机制存在的盲点,提高了算法的收敛精度.

图7-图10是4种优化算法在多峰函数上的收敛曲线.4幅图中ISOA前期收敛速度明显更快,进一步说明改进型Logistics映射的有效性.图9和图10中,ISOA可以在很少的迭代中达到很高的寻优精度,说明算法有很好的寻优性能.这是因为改进参数A改变了海鸥的搜索步长,大大提高了算法的寻优精度和速度.在图7和图8中,尽管ISOA存在一定时期的停滞,但很快可以继续寻优,最终可以达到很高的寻优精度,有力证明了算法具有很强的跳出局部最优的能力,说明自适应t分布变异策略的引入,使ISOA跳出局部最优的能力得到极大提升.

综合以上图形纵向观察,在相同的迭代次数下,ISOA具有更高的收敛速度;横向观察,在相同的收敛精度时,ISOA具有更快的收敛速度.因此,本文提出的海鸥算法改进策略先进有效,ISOA算法在寻优精度、收敛速度和跳出局部最优解3个方面较SOA等3种算法有明显的优势.

5 结束语

针对基本海鸥算法存在的缺陷,提出一种融合改进Logistics混沌和正弦余弦算子的自适应t分布海鸥算法(ISOA),并在8个标准测试函数上进行仿真实验,比较算法性能,得出以下结论:

1)ISOA寻优性能相对基本海鸥算法明显提升,证明了改进策略的有效性.海鸥位置初始化对全局搜索非常重要,通过改进Logistics混沌映射初始化海鸥种群,丰富了解的多样性;改进参数A和正弦余弦算子的引入,有效平衡了算法全局和局部的搜索能力并加快了收敛速度;算法融合了自适应t分布变异策略,在保留精英个体信息的同时,使算法易于跳出局部最优.

2)8个标准测试函数表明:ISOA在收敛精度、求解速度、跳出局部最优能力相较于GA、PSO和SOA表现出了更为出色的寻优性能,证实了算法改进的有效性和鲁棒性.

下一步可以考虑继续改进海鸥算法寻优机理和算法结构,或者融合其它智能算法的优点提出性能更佳的智能算法,以及将ISOA应用到复杂的工程问题中,扩展本算法的应用领域.