陈嘉豪 童楠 符强

摘要： 在高维复杂问题上，蜉蝣优化算法存在易陷入局部最优区域且求解精度较差等问题，因而提出基于Logistic映射的蜉蝣优化算法。引入依据Logistic映射的混沌机制，当种群进化停滞时，当前最优蜉蝣通过混沌机制寻找适应度更好的蜉蝣，以激发种群进化能力;建立较劣蜉蝣加速进化机制，激励蜉蝣个体以达到种群寻优要求;采用动态惯性权重均衡算法全局和局部的搜索性能。抽取5个benchmark函数测试算法性能，实验结果验证了所提算法在寻优性能上的有效性。

关键词： 群智能算法; 蜉蝣优化算法; Logistic映射; 扰动; 动态惯性权重

中图分类号：TP301.6          文献标识码：A     文章编号：1006-8228（2021）10-06-05

Mayfly optimization algorithm based on Logistic mapping

Chen Jiahao， Tong Nan， Fu Qiang

（College of Science and Technology， Ningbo University， Ningbo， Zhejiang 315300， China）

Abstract： For high-dimensional complex problems， mayfly optimization algorithm has problems such as easy to fall into local optimal area and poor solution accuracy. Therefore， a mayfly optimization algorithm based on Logistic mapping is proposed. Introducing the Logistic mapping based chaotic mechanism， when the evolution of the population stagnates， the current optimal mayfly uses the chaotic mechanism to find a mayfly with better adaptability to stimulate the evolutionary ability of the population; Establishing a accelerated evolution mechanism for inferior mayfly， the mayfly individual is motivated to meet the requirements of the population optimization; Using the dynamic inertial weight balance algorithm， the global and local search capabilities are balanced. Five benchmark functions are selected to test the performance of the algorithm， and the experimental results verify the effectiveness of the proposed algorithm in optimizing performance.

Key words： swarm intelligence algorithm; mayfly optimization algorithm; Logistic mapping; disturbance; dynamic inertia weight

0 引言

群智能優化算法[1-2]易于编程，寻优能力强，现已广泛应用于实际工程领域中，例如解决旅行商问题和0-1背包问题等[3-4]。

蜉蝣优化算法[5]（A mayfly optimization algorithmMA）是一种2020年7月由Konstantinos Zervoudakis和 Stelios Tsafarakis 提出的新型群智能算法，此算法受蜉蝣飞行行为和交配过程的启发，联结粒子群算法[6]和遗传算法[7]的优点，在低维问题上，相比较其余群智能算法具备更好的收敛速度和收敛精度，且算法中的随机飞行和婚礼舞蹈行为能有效平衡种群的全局探索及局部搜索要求。但当遇到高维复杂问题时，蜉蝣算法单纯依靠自身机制仍然较难跳出局部最优区域，且由于蜉蝣在移动时步长太短，导致算法收敛精度不高。

针对上述问题，本文提出基于Logistic映射的蜉蝣优化算法（mayfly optimization algorithm based on Logistic mapping LMA），采用动态惯性权重提高种群的搜索能力，增加算法收敛效率;引入基于Logistic映射的混沌机制，防止种群出现早熟收敛现象;建立较劣蜉蝣加速进化机制，减少较劣蜉蝣在外徘徊的次数，提升种群整体进化速度。通过对标准测试函数的仿真实验，并与其他几种算法进行比较，验证LMA算法对问题求解的有效性。

1 蜉蝣优化算法简介

蜉蝣优化算法抽象出蜉蝣的生命过程，将蜉蝣的位置映射为问题的潜在解决方案。算法最初随机生成蜉蝣种群，将种群分为雄性蜉蝣群和雌性蜉蝣群。设一个[D]维问题，第[i]个蜉蝣的位置为[xi={x1，x2，x3，…，xD}][xi={x1，x2，x3，…，xD}][xi={x1，x2，x3，…，xD}]，对应速度为[Vi={V1，V2，V3，…，VD}]。

1.1 雄雌蜉蝣的移动

MA算法中雄蜉蝣会朝更优方向进化，因此雄蜉蝣的速度将根据自身曾到过的最好位置与种群当前最优位置来调整，且当蜉蝣适应度优于种群当前最优适应度时，蜉蝣将根据婚礼舞蹈系数和惯性权重对速度进行调整，速度更新公式为：

[vt+1ij=g*vtij+a1e-βr2ppbij-xtij+a2e-βr2ggbj-xtij，iffxi>fgbg*vtij+d*r1 ，iffgb≤fxi] ⑴

其中[vtij]为第[t]次迭代第[i]个蜉蝣在[j]维度上的速度，[xtij]为第[t]次迭代时第[i]个雄蜉蝣在[j]维度上的位置，[a1]为蜉蝣个体的认知参数，[a2]为种群社会贡献参数，[g]为惯性权重，[β]是一个固定的能见度因子，[d]为舞蹈因子，[r1]是[[-1，1]]内的随机因子，[pbij]為第[i]个蜉蝣在第[j]维曾经到达过的最好的位置，[gbj]为第[j]维全局最好的位置，[rp]与[rg]分别为第[i]个蜉蝣与[pb]的笛卡尔距离和第[i]个蜉蝣与[gb]的笛卡尔距离。

个体适应度排序等级相同的雄雌蜉蝣将会相互吸引，雌蜉蝣的移动依据为排序等级相同的雄蜉蝣位置。若雄蜉蝣优于雌蜉蝣，则雌蜉蝣向雄蜉蝣靠近，否则受随机飞行因子的影响随机向周围飞行。雌性蜉蝣的速度更新公式为：

[vt+1ij=g*vtij+a2e-βr2mfxtij-ytij ，iffyi>fxig*vtij+fl*r1   ，iffyi≤fxi] ⑵

其中[ytij]为第[t]次迭代时第[i]个雌蜉蝣在[j]维度上的位置，[rmf]为雄雌蜉蝣之间的笛卡尔距离，[fl]是一个随机飞行因子。

MA算法通过在当前位置上添加速度[vt+1i]作为雄雌蜉蝣位置的移动。

[xt+1i=xti+vt+1i] ⑶

同时为防止蜉蝣速度无限增大导致蜉蝣飞出解空间范围，MA算法对蜉蝣的速度进行限定。在迭代的过程中，为满足算法后期局部探索要求，蜉蝣的惯性权重、婚礼舞蹈因子与随机飞行因子将逐渐减少。

1.2 雄雌蜉蝣的交配与变异

MA算法中个体适应度排序等级相同的雄雌蜉蝣将会相互交配生成子代蜉蝣。交配的公式如下：

[offspring1=L*male+1-L*female]

[offspring2=L*female+1-L*male]  ⑷

其中[offspring]为子代蜉蝣，[male]为雄蜉蝣，[female]为雌蜉蝣，[L]为[[-1，1]]中的随机因子。

MA算法引入高斯变异[8]，对子代蜉蝣的单个维度进行基因变异。子代蜉蝣的变异个数以种群数量[Pop]为基数，定义变异几率为[mu]，[Pop*mu]为种群中子代的变异个数。变异公式如下：

[offspringn=offspringn+σ*Nn（0，1）]  ⑸

其中[Nn0，1]为平均值为0，方差为1的标准正态分布随机数，[σ]为正态分布的标准差，[offspringn]为变异蜉蝣的第[n]个维度。

2 改进的蜉蝣优化算法

2.1 根据Logistic映射的混沌机制

基于Logistic映射的混沌机制[9]中存在控制参数[μ∈[0，4]]，当[μ]等于4时，混沌变量的取值将呈现混沌特征，因此本文取[μ]为4。该混沌机制将生成随机分布在解空间中的混沌蜉蝣。LMA算法由当前最优蜉蝣随机产生[10]个混沌蜉蝣，若最优的混沌蜉蝣优于当前最优蜉蝣，则替换之，否则随机替换蜉蝣种群中除了最优蜉蝣外的任一蜉蝣，增加种群多样性，增大算法求得全局最优解的可能性。

Logistic映射的混沌机制进行扰动的公式如下：

[zt+1i=μzti（1-zti）] ⑹

其中[zti∈[0，1]]为第[i]个混沌蜉蝣的混沌位置。

将[xi∈[xmin，xmax]]映射到[zi∈[0，1]]的公式如下：

[zi=（xi-xmin）/（xmax-xmin）] ⑺

将[zi]映射回[xi]公式为：

[xi=xmin+zi（xmax-xmin）] ⑻

当连续两次迭代的种群蜉蝣的平均适应度之差小于[10-3]，判定算法陷入局部最优，将执行混沌机制。

方差[10]计算公式如下：

[σ2=i=1N（（fi-favg）/f）2] ⑼

其中N为种群中蜉蝣的总数，[favg]为种群适应度的平均值，[fi]为蜉蝣个体[i]的适应度。[f]为用来限制[σ2]大小的因子，计算公式为：

[f=maxfi-favg，maxfi-favg>11                             ，max {|fi-favg|}≤1] ⑽

2.2 较劣蜉蝣加速进化机制

种群中存在部分个体的进化程度始终无法达到种群平均进化程度，算法将判定这类个体为失效个体。对多次无法跟随种群进化脚步的蜉蝣进行加速进化操作，激发失效蜉蝣的潜能以增加算法收敛速度。当蜉蝣无法跟随种群进化脚步的次数超过3次时，实施加速操作[11]，蜉蝣与当前最优解的适应度差值与拉伸因子成正比，从而影响蜉蝣的速度。加入拉伸因子[SO]后的蜉蝣速度公式为：

[vtij=g*vtij+a1e-βr2ppbij-xtij][+a2e-βr2ggbj-xtij+SO] ⑾

其中[SO]为拉伸因子，其计算公式为：

[SO=c3*r2*（gbest-pbest）] ⑿

其中[c3]的计算公式为：

[c3=（xcost-gcost）/（avecost-gcost）] ⒀

其中[xcost]为蜉蝣的适应度，[gcost]为全局最优解的适应度，[avecost]为种群平均适应度。

2.3 动态惯性权重

为平衡算法全局搜索能力与局部探索性能，算法前期以较小的惯性权重减小蜉蝣步长，保持种群多样性，中期增大惯性权重，加强全局搜索能力，后期减小惯性权重，增强局部探索性能，增加算法收敛精度，所以本文采用二次函数改变惯性权重，公式如下：

[g=-4gmax-gminMaxIt2*it2+][4gmax-gminMaxIt*it+gmin] ⒁

其中[gmax]为最大惯性因子;[gmin]为最小惯性因子，[MaxIt]为最大迭代次数，[it]为当前迭代次数。

2.4 LMA算法流程

Step1 初始化参数，初始化雄雌蜉蝣位置与速度，并计算适应度，寻找当前最佳适应度。

Step2 更新蜉蝣速度与位置，判断蜉蝣无法跟随进化的次数，若超过3次，则按式⑿更新速度，否则按式⑴和式⑵更新速度，并计算适应度。

Step3 根据式⑷生成后代数量为nm，根据变异可能性mu和式⑸产生变异后代，并将各个后代随机插入雄蜉蝣或雌蜉蝣队列。

Step4 根据种群的适应度实行精英保留策略。

Step5 按式⑼计算本次种群解的方差值，并与上一代种群的方差作比较，若差值小于[10-3]，则按式⑹～式⑻执行混沌机制。

Step6 更新舞蹈因子，隨机飞行因子，更新惯性因子。

Step7 迭代次数加一，判断是否到达迭代上限，若是则转Step8，若否则转Step2。

Step8 输出种群历史最优解。

3 实验及结果分析

3.1 测试函数

为验证LMA的算法性能，随机抽取5个benchmark标准测试函数。其中F1、F2为单峰函数，用来测试算法的全局寻优能力，F3、F4为高维多峰函数，用来检测算法对复杂问题的处理能力。F5函数在最优点附近较为狭窄，用于测试算法的局部搜索能力。测试函数相关参数设置见表1。

3.2 算法参数设置

在解决高维问题时，群智能算法常常较难获得很好的结果，为验证LMA算法在处理高维问题上的寻优能力，设计在50维问题上的对比实验。设置迭代次数为2000次，种群数量为40。实验对比蜉蝣算法（MA），本文所提算法（LMA），经典蜂群算法（ABC）[12]和基于混沌序列的蜂群优化算法（CABC）[13]四种算法，LMA算法的参数设置可参照表2，其他算法参数设置参考文献。

3.3 实验数据及分析

实验将每个算法对每个问题独立测试100次记录算法结果的平均值，最优解，最劣解和方差。

表3中记录四种算法对每个测试函数进行测试后的数据。在F1、F2测试函数上，LMA算法对比其他算法的平均值、最优值、最劣值和方差都有较为明显的优势，说明LMA算法的寻优能力更强、鲁棒性更好。对比MA算法与ABC算法，LMA算法与CABC算法都采用混沌机制，在处理F3、F4函数时，最优值上有较大的优势，说明采用该机制使算法处理多峰复杂问题的能力有所提升。综上所述，LMA算法的改进策略有效地提升算法对处理高维问题的能力，提高了算法寻优性能。

为更加直观地体现LMA算法的优越性能，绘制出图1～图5仿真四种算法的收敛曲线。

在局部搜索能力方面，参照F5函数，观察函数收敛曲线，ABC算法较难向下收敛，CABC算法依靠混沌策略可以向下寻优，但寻优过程不稳定，鲁棒性较差。MA算法较为有效地向下寻优，但对比LMA算法的收敛曲线，LMA算法的求解精度更为准确，收敛效率更高。因此相比较其他算法，LMA算法在局部搜索能力上更强;在算法全局搜索能力方面，对比F2函数曲线可以看到LMA算法在算法中后期的收敛效率明显优于其他三种算法;在改进策略的有效性方面，全面对比函数曲线，LMA算法在迭代前期收敛效率高于MA算法，在迭代后期，LMA算法对于部分容易陷入局部最优的函数仍然可以向下寻优，这说明改进策略有效地提升算法的寻优能力，增强算法对求解陷入困境的处理能力。

4 结束语

MA算法本身在收敛效率、全局搜索能力和局部搜索能力上，比一般群智能算法更好，本文针对MA算法在高维度复杂问题上易陷入局部最优区域和求解精度较低等问题，提出改进算法，实验证明在种群进化停止时，LMA算法的处理能力比MA算法更好，在寻优能力方面，LMA算法也展现出更好的性能，下一步研究方向为加快算法的收敛速度。

参考文献（References）：

[1] Guo X D， Zhang X L， Wang L F， et al. Fruit Fly

Optimization Algorithm Based on Single-Gene Mutation for High-Dimensional Unconstrained Optimization Problems[J].Mathematical Problems in Engineering，2020.

[2] 王习涛.一种优化局部搜索能力的灰狼算法[J].计算机时代，2020.342（12）：57-59

[3] 何锦福，符强，王豪东.求解TSP问题的改进模拟退火算法[J].计算机时代，2019.7：47-50

[4] 刘生建，杨艳，周永权.求解0-1背包问题的二进制狮群算法[J].计算机工程与科学，2019.41（11）：179-187

[5] Zervoudakis K， Tsafarakis S. A mayfly optimizationalgorithm[J].Computers & Industrial Engineering，2020.145：106559

[6] Liu Z， Qin Z， Zhu P， et al. An adaptive switchover hybrid particle swarm optimization algorithm with local search strategy for constrained optimization problems[J].Engineering Applications of Artificial Intelligence，2020.95：103771

[7] Hou L， Zou J， Du C， et al. A fault diagnosis model of  marine diesel engine cylinder based on modified genetic algorithm and multilayer perceptron[J]. Soft Computing，2020.24（2）.

[8] 李永恒，趙志刚.基于越界重置和高斯变异的蝙蝠优化算法[J].计算机工程与科学，2019.41（1）：144-152

[9] 韩雪娟，李国东，王思秀 基于Logistic和超混沌结合的加密算法[J].计算机科学，2019.46（0z2）：477-482

[10] 王亚，熊焰，龚旭东，陆琦玮.基于混沌PSO算法优化RBF网络入侵检测模型[J].计算机工程与应用，2013.49（10）：84-87

[11] 李荣龙，罗杰.一种改进的粒子群优化算法[J].计算机技术与发展，2015.25（7）：67-71

[12] 何尧，刘建华，杨荣华.人工蜂群算法研究综述[J]. 计算机应用研究，2018.319（5）：7-12

[13] 罗钧，李研.具有混沌搜索策略的蜂群优化算法[J].控制与决策，2010.25（12）：1913-1916