基于倒位变异的蜉蝣优化算法①

陈伟超,符 强

(宁波大学科学技术学院,宁波 315300)

随着社会的发展,出现了许多复杂的优化问题亟待解决,传统的数学工具已经不在适用于求解这些问题.随着计算智能的发展,出现了群智能算法[1].群智能算法是一种新兴的演化计算技术,相比于其它传统优化算法能更快的发现复杂优化问题的最优解,已成为越来越多研究者的关注焦点.群智能算法原理简单,寻优能力良好.通过对群智能算法的不断改进和优化,使得群智能算法应用面越来越广,粒子群算法[2]等已经广泛应用于非线性复杂约束规划、作业调度优化等实际工程中.

蜉蝣算法(Mayfly Algorithm,MA)[3]是2020年新提出的群智能优化算法.MA 算法根据蜉蝣的活动方式和习性而编写.其中雄蜉蝣成群的聚集,每只雄蜉蝣的位置都是根据自己和邻居的经验来调整,雄蜉蝣通过婚礼舞蹈吸引雌蜉蝣进行交配.

MA 算法把雄蜉蝣的位置移动看作算法的寻优过程,同时引入了婚礼舞蹈系数和随机飞行系数,有助于算法跳出局部最优.但在高维非线性复杂问题中,MA算法的全局收敛性能较差.本文将倒位变异和突变结合,提出了一种基于倒位变异的蜉蝣算法(Inversion Variation Mayfly Algorithm,IVMA),以提高算法在高维非线性复杂问题的收敛精度.并通过随机抽取的10个50 维度benchmark 标准测试函数对算法性能进行验证.

1 标准蜉蝣优化算法简介

MA[3]算法是一种求解优化问题的群智能优化算法,该算法受蜉蝣飞行行为和交配过程的启发.其中MA 算法结合了粒子群算法(PSO)[4,5]、遗传算法(GA)[6]和萤火虫算法(FA)[7]的主要优点,提高了算法寻优能力,使得MA 算法具有较好的寻优能力,但在高维非线性复杂问题上,MA 算法跳出局部最优的能力较差,容易出现早熟收敛的现象.使得算法在多峰函数中表现较差.具体的计算方法如下:

设有一个D维问题,MA 算法根据蜉蝣的位置来求出最优解,第i个蜉蝣的位置xi={x1,x2,x3,…,xD}对应速度为Vi={V1,V2,V3,…,VD}.

1.1 雌蜉蝣更新

雌蜉蝣的速度更新:雌蜉蝣不会像雄蜉蝣一样成群结队,当雌蜉蝣被雄蜉蝣吸引时,会向雄蜉蝣靠近,否则雌蜉蝣会随机飞行.它们的速度计算如下:

其中,Vijt+1是雌蜉蝣i在维度j中的位置,a2是固定的可见性系数,rmf是雄蜉蝣和雌蜉蝣之间的笛卡尔距离为笛卡尔距离计算公式),fl是随机飞行系数,r是[-1,1]区间内的一个随机数,iter是当前迭代次数,itermax为最大迭代次数.g是动态惯性系数,更新公式如下:

雌蜉蝣的位置移动通过蜉蝣所在位置加上蜉蝣获得的速度Vit+1来改变.

其中,yit为雌性蜉蝣i在时间步长t时在搜索空间上的位置,蜉蝣在搜索空间中飞行,因此位置具有限制yij∈(ymin,ymax).

1.2 雄蜉蝣更新

雄蜉蝣的速度更新:在表演婚礼舞蹈时,雄蜉蝣不能产生出很快的速度,但它们会不断地移动.因此,雄性蜉蝣i的速度计算如下:

其中,Vijt+1是雄蜉蝣i在维度j上的速度,a1,a2分别是正吸引系数,用于衡量认知和社会贡献.d是舞蹈系数,r是[-1,1]区间内的一个随机数,g是动态惯性系数,GlobalBest是全局最优个体.

此外pbest是蜉蝣i去过最好的位置,在下一个时间步长中,个体最优位置为:

其中,全局最优位置gbest的定义如下

雄蜉蝣的位置的移动通过在蜉蝣所在位置加上蜉蝣获得的速度来改变.

其中,xit+1为雄蜉蝣i在时间步长t时在搜索空间上的位置,雄蜉蝣在搜索空间中飞行,因此位置具有限制xij∈(xmin,xmax).

当更新一个远离全局最佳位置或个人最佳位置的蜉蝣的速度时可能会出现蜉蝣飞出问题空间的情况.根据蜉蝣的生活习性,蜉蝣不会一直增加速度.假设每个蜉蝣能够产生一个指定的最大速度Vmax.因此,速度调整为:

其中,Vmax=rand*(xmax-xmin),其中rand∈(0,1].

1.3 蜉蝣交配

在一个种群中,雄雌蜉蝣按照适应值选择配对个体进行交配,适应值最优的雄蜉蝣和适应值最优的雌蜉蝣进行交配,依此类推.交配结果是产生两个子代,其产生公式如下:

其中,L是[-1,1]之间的一个随机数,子代的初始速度设定为0.

1.4 蜉蝣变异

为了处理可能导致出现的最优值是局部最优而不是全局最优的早熟收敛情况,在,将正态分布的随机数加到所选子代蜉蝣中进行突变,子代蜉蝣突变公式如下:

其中,σ是正态分布的标准偏差.N(0,1)是平均值为0,方差为1的标准正态分布.变异个体的数量为round(0.05*雄蜉蝣数量).

婚礼舞蹈系数与随机飞行系数也会随迭代次数减少,公式如下:

其中,dt与flt为t时刻的婚礼舞蹈系数和随机飞行系数,ddamp与fldamp是婚礼舞蹈系数和随机飞行的衰减参数.

2 基于倒位变异的蜉蝣算法(Inversion Variation Mayfly Algorithm,IVMA)

面对高维非线性复杂问题时,MA 算法容易陷入局部最优区域,发生进化停滞的情况.如图1所示在函数Griewank中MA 算法较早的出现了陷入局部最优的现象,使得种群进化停滞.

图1 Griewank 函数

对于MA 算法存在的缺陷,本文提出的IVMA 算法通过对最优个体进行倒位变异操作,使得IVMA 算法具有较好全局搜索能力.对倒位变异策略产生的新个体使用精英策略保留进化成果.改变原算法在变异上的操作,提高IVMA 算法在高维复杂问题中的收敛精度.

2.1 倒位变异机制

由于MA 算法在算法收敛过程中容易出现早熟收敛的问题,IVMA 算法在为了避免在算法后期陷入局部最优,提高算法摆脱局部极值点的能力,引用了倒位变异机制[8].在进行一轮种群进化之后,当种群的适应值连续两代的差值小于某个阈值时(阈值设于10-3),对蜉蝣的最优个体进行倒位变异,以增强种群的多样性,提高算法的全局收敛性能.

倒位变异的具体操作如下,对最优个体GlobalBest进行倒位操作.首先在[1,D]之间随机选取两个整数p和q,设p＜q,p,q为最优个体的不同维度,将p,q两个维度之间的GlobalBest位置进行倒序,如当p为10,q为20 时,GlobalBest的10 维的位置和20 维的位置进行交换,GlobalBest的11 维的位置和19 维的位置进行交换.以此进行类推,则执行倒序操作后得到了新个体,带入目标函数,如果产生的新个体比当前全局最优个体更好,则进行更新,以此保留种群进化的成果.

利用倒位变异改变GlobalBest在随机维度段p至q之间的位置,即对选定的维度段内GlobalBest的位置进行倒序操作,得到的新个体和GlobalBest比较,使用较优个体对种群进化进行引导.因为雄蜉蝣的位置是通过自身到过的最好位置和当前全局最优个体GlobalBest的位置进行移动的,利用经过倒位变异操作的GlobalBest的引导,使得雄蜉蝣在靠近自身到过的最优位置和当前全局最优位置的过程中具备了找到优于当前全局最优个体的位置的能力.

通过倒位变异机制,使得IVMA 算法具备了良好的找到全局最优的能力,提高算法了在高维非线性复杂问题中的全局收敛性能.

2.2 突变操作

改变原算法的变异操作,在进行交配操作后从子代中随机选择一个个体xi,产生新个体xi.具体操作为,从子代蜉蝣种群中随机选择一个个体,通过改变它的单个随机维度的蜉蝣位置来优化算法.xi中随机的维度d向蜉蝣全局最优个体的随机维度b靠近,公式如下:

其中,b,d∈{1,2,3,…,D}分别是随机选取的一个值,λ∈[-1,1].

通过改变所选子代蜉蝣的随机维度的位置,提高了种群多样性.改善了MA 算法摆脱局部极值点的能力.

2.3 IVMA 算法流程

Step 1.基本参数设置,包括种群规模,最大迭代次数等.

Step 2.随机产生初始种群,随机蜉蝣的位置并且设置初始速度为零.

Step 3.根据式(1),式(3)分别更新雌蜉蝣的速度和位置,雌蜉蝣的位置带入目标函数比较适应值,如果优于个体最优则根据式(5)更新个体最优数据.

Step 4.根据式(4),式(7)分别更新雄蜉蝣的速度和位置.

Step 5.雄蜉蝣的位置带入目标函数比较适应值,如果优于个体最优则根据(5)更新个体最优数据,在此基础上,如果优于全局最优则根据式(6)更新全局最优数据.

Step 6.对雄雌蜉蝣的适应值根据优劣性进行排序.

Step 7.根据式(9),式(10)对蜉蝣进行交配操作产生子代蜉蝣.

Step 8.根据式(14)对子代蜉蝣进行突变操作.

Step 9.在进行一次种群进化后,如果符合阈值条件,则进行倒位变异操作,通过比较适应值决定是否更新.

Step 10.对于蜉蝣适应值进行排序,取较优解,保持总群数量不变.更新舞蹈系数(式(12)),飞行系数(式(13)),动态惯性系数(式(2)).

Step 11.判断是否达到终止条件,若是则输出最优解:若否,则执行Step 3.

3 仿真实验及分析

为了测试IVMA 算法的优化性能,从文献[3]中随机选取了10 个标准benchmark 函数进行验证.各函数的参数说明及特征如表1所示.

表1 测试函数的维度,搜索空间,最优值

将IVMA 算法和MA 算法,PSO 算法[9]、优化的蜂群算法(CABC)[10]进行对比仿真实验.MA 算法,PSO 算法,CABC 算法,IVMA的种群数量均设定为40 个,其中MA 算法,PSO 算法,CABA 算法其他参数设置参考所引文献.IVMA 算法具体的参数设置为:雄雌蜉蝣的数量各为20,迭代次数2000 次,蜉蝣的舞蹈系数为1,随机飞行系数为1,ddamp为0.8,fldamp为0.99,gmax为1.5,gmin为0.4,a1=1,a2=1.5.为了测试算法在高维非线性复杂问题中的表现,函数测试维度均为50 维,每个测试函数做100 次重复实验进行对比分析,得出4 种算法的最优值,最差值,平均值和标准差,结果如表2所示.

表2 4 种算法对10 个函数的计算结果比较

表2显示,在50 维度的10 个函数优化测试中,MA 算法,PSO 算法和ABC 算法的搜索能力较差.MA 算法,PSO 算法和CABC 没有一个函数获得理论最优值,而IVMA 算法在f7,f9 两个测试函数中获取了理论最优值.从整体函数测试结果来看,IVMA 算法具有更好的收敛精度,搜索能力优于其他对比算法.

为了更直观地反应IVMA 算法的搜索性能.本文进一步绘制了IVMA 算法,MA 算法,CABC 算法以及PSO 算法的适应度收敛曲线图,如图2～图11所示(其中横坐标为迭代次数,纵坐标为收敛精度)

图2 f1 函数收敛性能比较

图3 f2 函数收敛性能比较

图4 f3 函数收敛性能比较

图5 f4 函数收敛性能比较

图6 f5 函数收敛性能比较

图7 f6 函数收敛性能比较

图8 f7 函数收敛性能比较

图9 f8 函数收敛性能比较

图10 f9 函数收敛性能比较

图11 f10 函数收敛性能比较

由函数图观察发现在f1,f2,f4 函数中,MA 算法相较于PSO 算法和CABA 算法具有一定优越性,IVMA提高了收敛精度.函数f5中其他3 种算法在迭代200次时都陷入了局部最优区域收敛趋于平缓,但IVMA还是具有较好寻优能力.函数f6中,MA 算法,PSO 算法,CABC 算法的全局收敛性能并不好,但IVMA 经过倒位变异后,改善了早熟收敛的问题,提高了全局搜索的能力.函数f7 存在大量局部优值,MA 算法在迭代至400 次时,陷入了局部最优,但IVMA 算法利用倒位变异保持了正确的搜索方向,持续地寻找全局最优解.函数f8中其他3 种算法的收敛性能较差,但IVMA 算法从迭代开始至结束都具有良好的寻优能力,在较少的迭代次数下获取了较好的优化结果.在函数f7,f9中,IVMA 算法较快的找到了全局最优,算法性能得到极大提高.

4 结论

为了改善MA 算法在高维复杂问题中全局收敛性能较差,容易出现早熟收敛的问题.本文提出了一种基于倒位变异的IVMA 算法,IVMA 算法引入倒位变异操作和改变MA 算法在变异上的操作,提高了跳出局部最优的能力.对10 个标准测试函数寻优的实验结果表明,MA 算法相对于MA 算,PSO 算法和CABC 算法,在高维非线性复杂问题中具有更好的收敛精度,优化了算法的寻优能力.