引入精英反向学习和柯西变异的混沌蜉蝣算法

张少丰，李书琴

(西北农林科技大学 信息工程学院，陕西 杨凌 712100)

0 引 言

蜉蝣算法(mayfly algorithm，MA)[1]是Zervoudakis等受蜉蝣的飞行和繁衍行为启发提出的一种新型的智能优化算法，通过模拟雌性蜉蝣选择适合的雄性蜉蝣个体进行繁衍，逐步淘汰子代蜉蝣中适应度值较低的个体的过程完成寻优。相比于其它算法，该算法具有结构简单、控制参数少、寻优能力强[2-4]等优点，因此在诸多领域[5，6]有广泛的应用，但在解决高维复杂问题下，由于蜉蝣在移动过程中步长较短，导致其算法存在收敛速度慢、易陷入局部最优等缺陷。

针对蜉蝣算法的不足，Zheng-MingGAO等[7]提出异构蜉蝣算法，通过增加蜉蝣更新的方式，来提高蜉蝣算法寻优能力。李浩等[8]提出多目标离散蜉蝣算法的动态网络社区发现方法，通过标签扩散算法将种群进行离散化，提高了蜉蝣算法求解精度。陈伟超等[9]提出基于倒位变异的蜉蝣算法，利用倒位操作，将随机个体的维度向最优个体靠近，提高了算法收敛性。

上述研究在一定程度上提高了蜉蝣算法的寻优能力，但是仍存在收敛速度慢、稳定性不强等问题。因此本文提出了混沌蜉蝣算法(chaotic mayfly algorithm，CMA)，主要改进策略为：

(1)基于Circle混沌初始化种群，使蜉蝣个体均匀分布在搜索空间，增加初始解的可行性。

(2)引入基于精英个体的反向学习机制，对子代蜉蝣个体中的精英个体生成反向解，并选择其中较优个体作为下一代迭代个体，增加算法寻优能力和收敛速度。

(3)将自适应概率阈值与柯西变异策略相结合，对劣势蜉蝣个体进行变异扰动，保证种群进化方向，提高算法的全局寻优能力，防止算法陷入局部最优。

1 蜉蝣算法(MA)

蜉蝣种群包含雄性蜉蝣和雌性蜉蝣，其数量均为N/2，N为群体总数。在蜉蝣繁衍过程中，雄性蜉蝣通过全局最优和自身历史最优值移动，而雌性则是向优于自己的配偶移动，若配偶弱于自己则自行局部搜索。蜉蝣产生后代，逐渐淘汰适应度较低的个体并保留群体中较优个体，最终完成寻优的过程。

1.1 雄性蜉蝣的移动

雄性蜉蝣的移动会根据自身邻域范围内的局部最优和全局最优进行位置调整，雄性蜉蝣在t时刻的位置更新方式请参见文献[1]，雄性蜉蝣会在水面表演舞蹈吸引雌性蜉蝣，在此阶段中蜉蝣速度更新方式为

(1)

(2)

其中，xij表示蜉蝣i的第j个分量，Xi为蜉蝣对应的pbest和gbest。 为了找到最优位置，蜉蝣需要不断更新速度，其速度的更新方式为

(3)

其中，d表示舞蹈系数，r为[-1，1]之间的随机数。

1.2 雌性蜉蝣的移动

雌性蜉蝣会飞到雄性群体中选择适配度较高的雄性蜉蝣进行交配繁衍。它的位置通过增加速度来更新，雌性蜉蝣位置更新方式请参见文献[1]，雌性蜉蝣的速度计算方法如下

(4)

1.3 蜉蝣交配过程

蜉蝣交配过程中一对雌性和雄性会产生两个后代，交配过程中通过蜉蝣的适应度选择亲本，最优的雄性蜉蝣与最优的雌性蜉蝣进行繁衍交配，次优雄性蜉蝣与次优的雌性蜉蝣进行繁衍交配。交叉算子代表两个蜉蝣交配过程，交叉的结果是两个后代，产生结果如下

offspring1=L·male+(1-L)·female
offspring2=L·female+(1-L)·male

(5)

其中，male表示雄性父代，female表示雌性父代，L是 [-1，1] 之间的随机数。

2 混沌蜉蝣算法

2.1 Circle混沌映射

针对MA进行初始化种群分布是随机生成，导致算法容易陷入局部最优的问题。本文采用混沌映射的方式实现对中群的初始化，结合混沌映射具有不可预测、非线性等特点。通过混沌初始化种群使得蜉蝣种群均匀分布在搜索空间内，从而提高蜉蝣算法的搜索性能。常用来初始化种群的混沌映射有Logistic映射和Tent映射，相关研究结果表明[10，11]Logistic映射呈现切比雪夫分布，随着迭代次数增加在[0，0.1]和[0.9，1]区间内有较高的分布，导致分布不均，搜索盲区较大，从而影响算法的寻优能力。Tent映射分布相对均匀，但是属于映射折叠次数有限的混沌模型，存在周期不稳定容易使得映射陷入不动点的缺陷。而Circle混沌映射不仅能克服Tent和Logistics映射的缺点，而且其产生的混沌序列也更加均匀[13]。因此采用的Circle混沌映射来生成初始群体，Circle映射定义如式(6)所示

(6)

其中，xi+1表示映射之后的位置，xi表示目标原位置，i表示维度。

随机生成的种群分布图和经过Circle映射后的种群分布图如图1和图2所示，通过Circle混沌映射初始化后的蜉蝣种群与随机生成的种群序列相比，蜉蝣个体的位置分布更加均匀，增加群体位置的多样性。提高了初始解的可靠性，一定程度上提高了算法跳出局部最优的能力，从而提高了算法的寻优效率。

图1 随机生成种群分布

图2 Circle映射后的种群分布

2.2 精英反向学习机制

反向学习[14](opposition-based learning，OBL)是通过求解问题可行解的反向解，并对反向解和可行解进行评估，从中选择更优解为下一代个体，提高算法的寻优效率。为了增加MA算法的全局寻优能力，防止算法进入“早熟”阶段，引入精英反向学习机制。在蜉蝣交配繁衍产生子代中，针对精英个体，使用反向学习机制生成对应的反向解，采用双向评估导则，在选取适应度较高的蜉蝣个体作为下一代种群，加快算法的收敛速度。设当前蜉蝣在D维搜索空间的可行解表示为

Xi=(x1，x2，…，xD)

(7)

则当前可行解的反向解则表示为

(8)

(9)

其中，k为[0，1]上均匀分布的随机函数，ai、bi分别为xi的最大值和最小值。

当前种群内所有个体中对应的评价函数的极值为精英个体，如式(10)所示。对精英个体构造反向解可以增加种群的多样性，并从当前候选解和反向解中选择最优值作为子代蜉蝣个体，从而提高算法的收敛能力。精英反向解的计算方法如式(11)、式(12)所示

(10)

(11)

(12)

2.3 基于柯西变异扰动机制

在蜉蝣群体在繁衍过程中，如果蜉蝣个体进化程度多次低于种群平均进化程度，则评定该蜉蝣为劣势蜉蝣。如果劣势蜉蝣个体较多使得种群进化方向偏移，导致算法陷入局部最优。为了减少劣势蜉蝣个体出现，本文引入基于柯西变异的扰动机制策略，每次更新种群时，将劣势蜉蝣个体进行柯西变异，在蜉蝣个体附近生成更大扰动，扩大寻优范围，增加收敛速度，从而提高全局寻优能力。判断是否为劣势蜉蝣标准如式(13)、式(14)所示

(13)

(14)

为了避免陷入局部最优值以及保障整个种群进化方向，对劣势蜉蝣个体通过自适应扰动概率p进行柯西变异。自适应概率p的定义如式(15)所示

(15)

其中，N为种群个数，Iter为迭代次数，ε为调节因子取值为0.05，0.1，0.15，0.2进行调整。

相比正态分布，柯西分布具有相对平缓的概率浮动的特点，在峰值处相比正态分布较低，在两侧趋近于0的速率较慢[15]。因此能够产生更好的扰动效果，利用柯西变异对蜉蝣个体进行扰动，提高CMA跳出局部最优能力，从而提高算法的收敛能力。具体更新方式如式(16)所示，其中cauchy(0，1) 为标准柯西分布函数，标准柯西变异分布函数定义参见文献[16]

(16)

如果当前蜉蝣满足式(13)则可以判断为劣势蜉蝣个体，然后随机生成随机ϖ，ϖ∈[0，1]。 如果ϖ>p， 则进行变异扰动，否则保持不变。因此当前蜉蝣位置更新方式如下

(17)

其中，柯西分布随机变量生成函数为η=tan[(ξ-0，5)π]。

2.4 算法流程

综上所述，基于精英反向学习和柯西变异的混沌蜉蝣算法的伪代码见表1，算法流程如图3所示，CMA算法主要流程为：

表1 混沌蜉蝣算法CMA伪代码

图3 CMA算法流程

步骤1 初始化参数，种群规模N，迭代次数Iterator，舞蹈系数dance， 飞行系数α。

步骤2 根据式(6)进行Circle混沌映射生成初始化种群，并初始化蜉蝣位置和速度。

步骤3 根据式(1)、式(2)更新雄性蜉蝣的速度和位置，并计算适应度值。并对雄性蜉蝣的适应度值进行排序，获取当前雄性蜉蝣的pbest和gbest。

步骤4 根据式(4)更新雌性蜉蝣速度。

步骤5 根据式(5)蜉蝣交叉算子产生子代。

步骤6 结合蜉蝣pbest和gbest， 对适应度进行排序，选择精英个体，根据式(14)生成精英反向解。

步骤7 通过式(13)、式(14)判断劣势蜉蝣个体offspringi， 如果符合则根据式(17)进行柯西变异。第n行对更新后种群进行筛选，淘汰适应度值低的个体。

步骤8 判断是否达到终止条件，是则输出最优解，否则执行步骤3～步骤6。

2.5 算法时间复杂度分析

设搜索空间的维度为D，种群总数为N，雄性蜉蝣的个数为N1，雌性蜉蝣的个数为N2，子代蜉蝣个体为N3，最大迭代次数为T。初始化复杂度为O(1)，则MA的时间复杂度T(n)=O(1+T(N1D+N2D+N3D))=O(TN)。 Circle混沌映射初始化种群分布的时间复杂度为O(N)，由于精英反向学习机制嵌套在种群交配循环内，时间复杂度为O(N1D)， 柯西变异的扰动机制只在子代蜉蝣产生后进行判断，时间复杂度为O(N3D)。 所以改进CMA的时间复杂度为T(n)=Of(n)=O(T(N1(D+2)+N2(D+1)+N3(D+2)))。

3 实验与结果分析

3.1 实验环境

为验证CMA算法的寻优性能，本文选取了粒子群优化算法(PSO)[17]、蜻蜓优化算法(DA)[18]、基于Logistics映射的蜉蝣算法(LMA)[19]以及蜉蝣算法(MA)[3]、进行实验对比。并选择8个标准benchmark测试函数进行实验，其中包括4个单峰测试函数(f1～f4)和4个多峰测试函数(f5～f8)。种群规模设置为N=30， 最大迭代次数为Iterator=500， 维度为30，各类算法独立运行50次，编译工具为Matlab R2021a，算法主要参数见表2，测试函数见表3，本文的实验分为3个部分进行：

表2 算法主要参数

表3 测试函数

(1)将CMA与基本MA算法、PSO算法、DA算法和LMA算法进行比较，分别从算法性能、收敛速度、高维度分析3个角度进行分析，验证算法的有效性。

(2)以MA为基本模型，将CMA与基本MA算法、基于Circle混沌映射的蜉蝣算法CIMA、基于精英反向学习的蜉蝣算法EMA和基于柯西变异的蜉蝣算法CAMA进行对比分析，验证改进策略的有效性。

(3)Wilcoxon秩和检验，验证CMA与其它对比算法之间的显著性差异。

3.2 算法性能分析

通对5种算法在8个测试函数对比分析，并以最优值Best、 平均值Mean、 标准差Std为评价标准，实验结果见表4。在最优值方面，CMA在f1、f2、f3、f5这4个测试函数中已经达到最优值，且其它算法均没到达最优值，说明CMA搜索性能得到了一定的提高。在单峰测试函数f4中尽管没有到达理论最优值，但相比其余4种算法均有较大提升，而且平均值也更接近理论最优值。说明CMA在单峰测试函数中具有较强的搜索能力且有更高的收敛精度。而在多峰测试函数f6、f7、f8中，求解精度有一定的下降，但是仍然比MA、PSO、DA、LMA的求解平均高出其它算法10～15个数量级，说明引入针对精英个体的反向学习策略和柯西变异扰动策略使得CMA的跳出局部最优能力有所提升提高。

表4 测试函数的实验对比结果

在均值和标准差方面，在f1、f2、f3中，CMA的均值都是最优的，而在测试函数f4、f8中DA、PSO、MA在寻优后期陷入了局部最优值，标准差比较小而CMA能够跳出局部最优解，因此CMA标准差大于DA、PSO、MA三者，但是同时也具有更高求解精度。说明CMA算法的稳定性和鲁棒性优于其它4种算法。通过与MA进行对比，在所有测试函数函数中最优值、均值和标准差均比MA具有更好的效果，并且在f1、f2、f3、f5这4个测试函数中已经达到了理论值，说明在MA中加入混沌映射、精英反向学习、基于柯西变异的扰动机制策略，帮助算法提高的收敛能力和寻优能力，验证了改进策略的有效性。

3.3 收敛速度分析

为了验证算法的收敛精度和收敛速度，绘制了测试函数的收敛曲线图，分别如图4～图11所示，由图4～图7单峰收敛曲线可知，在f1、f2、f3、f4单峰测试函数中，PSO、DA的收敛曲线呈现平缓、停滞状态，容易陷入局部最优值，寻优精度较低。LMA和MA收敛曲线相比PSO、DA在收敛速度所有提高，但是仍然存收敛精度较低的问题。而随着迭代次数的增加CMA的收敛曲线一直处于其它曲线的下方，具有更快的收敛速度。在收敛速度和收敛精度方面，CMA都明显优于其它算法，说明在单峰测试函数方面，CMA收敛速度和寻优精度有较大提升。

图4 f1收敛曲线

图5 f2收敛曲线

图6 f3收敛曲线

图7 f4收敛曲线

由于多峰测试函数都存在大量的局部最优值，在测试函数f5、f6、f7、f8中，如图8～图11多峰收敛曲线可知，MA、PSO、DA都容易陷入局部最优值，全局收敛性较差，收敛曲线呈现平缓趋势，出现早熟早收敛的现象。LMA相比MA、DA、PSO具有更好的收敛速度，但仍然存在收敛精度不足的问题。相比CMA法的收敛曲线，随着迭代次数的增加，收敛曲线表现呈现较好的向下寻优过程。说明CMA引入精英反向学习机制扩大寻优范围和柯西变异扰动机制保证整个种群的进化方向，使得CMA算法性能得到显著提高。综上所述，相比于其它算法，CMA算法具有更好的收敛速度和收敛精度，改善了MA的早熟早收敛的问题。

图8 f5收敛曲线

图9 f6收敛曲线

图10 f7收敛曲线

图11 f8收敛曲线

3.4 高纬度分析

为了验证CMA算法求解高维度问题的能力，分别测试CMA在50、100维下实验结果，参数设置均保持不变，分别从平均值Mean和标准差Std两个方面进行评估，实验结果见表5。由表可知，在维度50维、100维的情况下，CMA在测试函数f1、f2、f3、f5仍然可以达到理论最优值。其它算法中表现次好的为LMA，在f1、f2单峰测试函数维度为50情况下，LMA算法均值为1.3257e-15、2.2581e-08，虽然与CMA相比仍然还有所差距，但是仍然比其它算法有更高精度。

表5 CMA算法高纬度对比结果

通过结合表4中上述算法在30维度的实验数据，由表4、表5可知随着维度的增加，使得函数更加复杂，搜索空间增大，寻优难度增加。所以PSO、MA、DA求解精度和鲁棒性整体呈现下降趋势，其中DA是3种算法中较差的，PSO次之。且CMA在求解单峰函数f4和多峰函数f6～f8时，随着维度的增加，收敛精度和鲁棒性整体也呈现下降趋势。但仍比其它算法提高了5～10个的数量级的收敛精度和更好的稳定性。CMA在f4精度存在波动但表现出很强的鲁棒性，在f6、f7、f8中随着维度的增加表现出更好的收敛精度和稳定性，从而验证CMA在低维和高维情况下均有更好的寻优能力。

在标准差方面，CMA的标准差整体都小于其它算法，但在100维多峰测试函数f6、f7、f8中，MA、PSO、DA、LMA其它4种算法随着维度的增加而陷入局部最优值，所以每次寻优结果比较接近，标准差小。CMA标准差虽然大于其它算法，但是跳出局部最优能力较强，具有较高的求解精度。说明引入精英反向学习策略避免陷入局部最优值，在种群更新的过程中引入了柯西变异，保证了种群的多样式，提高算法的寻优能力。

3.5 改进策略分析

为进一步探究改进策略对CMA的有效性，以标准蜉蝣算法(MA)作为基本模型，对基于Circle混沌初始化的蜉蝣法(CIMA)、基于精英反向学习的蜉蝣算法(EMA)、基于柯西变异的蜉蝣算法(CAMA)以及CMA进行对比实验。实验分别从最优值Best、均值Mean以及标准差Std这3个方面分析改进策略的有效性。算法参数设置与3.1节相同，算法独立运行50次，实验结果见表6。

表6 不同改进策略对比结果

由表6可知，CMA在测试函数f1、f2、f3、f5的3个指标均能达到理论值，对于f4、f6、f8虽然没有寻到最优，但是相对于其它改进算法，CMA具有更高的求解精度和稳定性。相比于基础模型MA而言，CIMA的求解精度是3种改进策略算法中最差的，但其收敛精度也得到了一定的提高，其中在f2、f3、f5函数上提升效果最好，说明混沌初始化改进策略提高了算法寻优能力。EMA在最优值Best和均值Mean都有较大提升，在整体测试函数中提升大约5～10个数量级，说明引入精英反向学习对于算法收敛性有较大提升。而CAMA在收敛精度有所提升，但是提升效果低于EMA。在标准差方面，EMA均小于MA，说明引入基于柯西变异的扰动机制增强了MA的稳定行。综合表6的实验结果，在最优值Best、均值Mean以及标准差Std方面相比其它算法，CMA都有更优的性能，同时具有更强的有效性和可行性。综上所述，说明融合3种改进策略的CMA，对于增加种群多样性、增强算法寻优能力是有效的。

3.6 Wilcoxon秩和检验

为了验证CMA算法稳定性和公平性，本文采用Wil-coxon秩和检验[20]对CMA进行显著性分析，对CMA独立运行30次的数据在5%的显著水平下验证与其它算法是否存在显著差异，若计算出p<0.05， 则说明两种算法存在显著性差异。若计算出p>0.05， 则说明两种算法不存在显著性差异。CMA和MA、PSO、DA、LMA在显著水平p=5%， 维度30维下的实验结果见表7，其中N/A表示二者性能相当，无法进行比较。由表7可知大部分的p值均小于0.05，说明CMA的寻优能力与其它算法存在显著性差异。对于f5、f6、f7函数CMA和LMA，f4和f7函数，CMA和MA寻优效果差异不明显，寻优能力相当。结合上述实验，故认为CMA与其它算法存在显著性差异且CMA的性能更加。

表7 Wilcoxon秩和检验结果

4 结束语

针对MA的不足，提出一种引入精英反向学习和柯西变异的混沌蜉蝣算法。首先通过Circle映射初始化种群，使其种群分布均匀，然后对精英个体进行反向学习策略生成精英反向解，提高算法的收敛速度，最后引入基于自适应概率阈值和柯西变异的扰动策略，对劣势蜉蝣进行扰动，扩大寻优范围保证种群寻优方向。实验验证CMA具有更好的寻优能力、收敛速度以及稳定性。同时本文改进策略也为其它启发式算法提供借鉴，在未来的研究中，考虑将改进算法运用于优化移动群智感知的任务分配问题，以进一步验证算法的性能。