改进交叉算子的自适应人工蜂群黏菌算法

刘成汉，何 庆

(贵州大学 大数据与工程学院，贵阳 550025)(贵州省公共大数据重点实验室，贵阳 550025)

1 引 言

近年来，群智能优化算法在许多应用学科中非常流行，因为群智能优化算法在各种优化问题中比确定性算法性能好、速度快.随着研究的深入，各学者研究出了各种智能优化算法，例如：粒子群优化(Particle Swarm Optimization，PSO)算法[1]、灰狼优化(Grey Wolf Optimization，GWO)算法[2]、正余弦优化算法(Sine Cosine Algorithm，SCA)[3]、蜉蝣算法(Mayfly Algorithm，MA)[4]、海鸥优化算法(Seagull Optimization Algorithm，SOA)[5]等.

黏菌算法(Slime Mould Algorithm，SMA)是由Li等人[6]于2020年提出的一种新型群智能优化算法，其灵感来源于黏菌的分散觅食行为，SMA与其他群智能优化算法相比具有参数少，寻优能力强等优点.然而，SMA同样存在着收敛速度慢，易陷入局部极小值的问题，针对这些问题，众多学者对SMA做出了改进，例如：Houssein等人[7]将SMA与自适应差分进化算法(AGDE)结合使用，提出了一种求解组合优化和全局优化问题的混合黏菌算法，采用AGDE的交叉策略加快算法收敛，突变策略来增加种群的多样性并避免算法过早收敛；Chen等人[8]在SMA中加入了混沌映射，提出了一种混沌黏菌优化算法，从而提高算法的搜索效率并更好地利用算法的局部搜索能力；Ewees等人[9]将萤火虫算法的位置更新思想结合到SMA中，提出了一种基于萤火虫算法的改进黏菌算法，为SMA寻优提供更多灵活性，从而加快了算法搜索速度；Abdel-Basset等人[10]提出了一种高效的二进制黏菌算法，该算法将标准SMA转换为二进制版本(BSMA)，然后引入两相突变(TM)与BSMA集成，最后结合一种新的攻击策略(AF)，从而提高了SMA算法的收敛速度并改善了算法易陷入局部最优值的问题；Rizk-Allah等人[11]提出了一种混沌对立增强的黏菌算法，通过引入交叉策略增强算法的多样性，采用混沌搜索策略，提高算法的开发能力，从而避免了算法过早收敛的问题；Naik等人[12]针对基本黏菌算法开发效率底下，收敛速度慢的问题，提出了一种基于精英领导的黏菌算法，采用全局最优解领导其他个体更新位置的方式，解决了上述问题.

综上所述，虽然上述改进方案在一定程度上改善了SMA搜索开发能力弱，收敛速度慢等问题，但是SMA仍然存在收敛精度不高，易早熟收敛的问题.因此，本文提出一种改进交叉算子的自适应人工蜂群黏菌算法(ISMA)，采用自适应可调节的反馈因子和交叉算子提高算法的收敛速度和精度；引入改进的人工蜂群搜索策略防止算法早熟收敛，最后采用8个基准测试函数以及部分CEC2014测试函数对改进算法进行寻优测试，并结合Wilcoxon值和统计检测验证了改进算法的有效性.

2 黏菌优化算法

SMA是根据黏菌个体的振荡捕食行为提出的一种智能优化算法，自然界中的黏菌可以根据空气中食物气味的浓度来接近食物，当黏菌静脉接触的食物浓度越高，生物振荡越强，黏菌静脉宽度增大，该区域聚集更多黏菌；当该区域食物浓度低时，黏菌转向探索其他区域.黏菌接近食物的数学模型描述如公式(1)所示：

(1)

式中，t为当前迭代次数，Xb(t)为当前最优个体位置，XA(t)和XB(t)为随机选择两个个体的位置，W为黏菌质量，代表适应度权重，vb和vc为控制参数，其中vb∈[-a，a]，vc从1线性下降到0，r是[0，1]之间的随机数，控制变量p和参数a的数学模型描述如公式(2)和公式(3)所示：

p=tanh|S(i)-DF|

(2)

(3)

式中，i∈1，2，3，…，n，S(i)是当前个体适应度值，DF为当前最佳适应度值，tmax为最大迭代次数.权重参数W的数学模型描述如公式(4)所示：

(4)

SI(i)=sort(S)

(5)

式中，r表示取值[0，1]的随机数，bF表示当前迭代最佳适应度，S(i)表示当前个体适应度值，wf表示当前迭代最差适应度值，i=C表示种群中适应度排在前一半个体，i=O表示剩下的个体，SI(i)是适应度排序，表示气味指数.

即使黏菌找到了更好的食物来源，它们仍然会分离一些个体探索其他领域试图寻找更高质量的食物来源.因此，黏菌种群更新位置的数学模型描述如公式(6)所示：

(6)

式中，UB和LB分别表示搜索区域的上下界，rand表示取值[0，1]之间的随机数，z为自定义参数.

3 多策略改进黏菌优化算法

3.1 自适应可调节反馈因子

在SMA中，反馈因子vc用来描述食物浓度与黏菌质量之间的反馈关系，其值从1线性下降到0，这种线性下降的反馈因子并不能准确地描述实际情况下质量和浓度之间的反馈关系，可能会导致算法收敛速度慢等问题.因此，本文引入一种自适应可调节的反馈因子：在算法迭代前期，黏菌个体大范围感受食物浓度，此时食物浓度低，应该加快反馈因子的下降速度，减弱反馈关系，有利于提高算法全局搜索能力；在算法迭代后期，食物浓度高，此时应该保持较为平稳的反馈系数，有利于个体局部探索最高的食物浓度(最优解).此外，加入下降速率调节因子k，可以自动调节反馈因子下降速度，自适应可调节的反馈因子数学模型描述如公式(7)所示：

(7)

式中，t为当前迭代次数，tmax为最大迭代次数，k是调节因子，线性反馈因子和调节参数k分别取1、4和7时的自适应可调节反馈因子比较如图1所示.

图1 反馈因子曲线图Fig.1 Feedback factor curve

由图1可知，改进的反馈因子曲线的下降速度随着调节因子k的增大而增大.在具体算法调试中，k值的选取不宜过大也不能太小，k值太大可能会导致算法前期收敛过快，算法开发能力减弱从而陷入局部极小值点；而k值太小则不能体现反馈因子在平衡算法搜索能力上的优势，算法收敛速度变慢.为了平衡算法的搜索能力，本文经过大量实验分析，最后选取k=4最为合适.

3.2 算数交叉算子

交叉算子是遗传算法中3个关键算子之一，通过交换两个父代的位置信息产生新的个体，新的个体继承了父代的有效信息.本文为了加快SMA的收敛速度，引入改进的算数交叉算子更新个体位置，即以一定的概率Pt让当前个体与种群最优个体进行交叉操作.交叉算子数学模型如公式(8)所示：

(8)

式中，t为当前迭代次数，XA1和XA2分别为交叉产生的两个子代个体位置，XA为当前个体位置，Xbest为当前种群最优个体位置，L为取值(0，1)的随机参数.

由公式(8)可知，子代主要由父代和参数L确定，其中参数L控制子代从两个父代获取信息的比例，为了使子代获取更多优秀父代的基因，并保持种群多样性，本文改进了原始的随机参数，引入用拉普拉斯系数[13]控制的参数L.改进后的控制参数L数学模型描述如公式(9)所示：

(9)

式中，μ和λ为拉普拉斯系数，其中μ取自然数，控制位置，λ>0控制尺度，r为取值[0，1]的随机数.由公式(9)可知，改进后的参数L通过引入系数λ调节父代与子代的距离，λ越小子代越靠近父代，种群多样性越高，同时，在拉普拉斯系数μ和λ的共同调节下，子代能选择性获得更多优秀父代的位置信息.

3.3 改进的人工蜂群搜索策略

人工蜂群算法(Artificial Bee Colony Algorithm，ABC)[14]是由Karaboga等人于2006年提出的一种智能优化算法，该算法通过模拟自然界蜂群的采蜜行为实现对复杂优化问题的处理，在复杂多峰函数寻优上具有良好的性能，拥有强大的探索能力.针对SMA易早熟收敛的问题，本文引入人工蜂群搜索策略并做出改进，基本人工蜂群搜索策略数学模型描述如公式(10)所示：

Zi，j=xi，j+φi，j(xi，j-xk，j)

(10)

式中，Zi，j为产生的候选解，xi，j为当前个体，xk，j为随机个体，k和j为随机参数，k∈{0，1，…，M}，j∈{1，2，…，d}，M为固定值，d表示维度，且k不等于i，φi，j为取值[-1，1]的随机数.由公式(10)可知，候选解由随机选取两个个体进行差分操作产生.

虽然人工蜂群搜索策略在搜索能力上有着很大的优势，但是其开发能力不强，因此本文引入一种新的搜索策略，在人工蜂群强大搜索能力的基础上加入全局最优位置引导，从而提高其开发能力，改进策略数学模型描述如公式(11)所示：

Zi，j=xi，j+φi，j(xi，j-xk，j)+Ωi，j(pg，j-xi，j)

(11)

式中，Ω为取值[0，1.5]的随机数，pg为全局最优位置.

综上所述，本文在SMA迭代过程中引入改进的人工蜂群搜索策略，在每一次迭代结束时，对于原始算法更新产生的个体和引入人工蜂群策略生成的个体，采用贪婪策略保留其中较优的个体，加快算法收敛，同时，人工蜂群搜索策略强大的搜索能力可以减少局部极值点对SMA的影响，从而提高算法跳出局部最优解的能力.

3.4 ISMA实现步骤

综上改进策略，ISMA实现步骤如下所示：

步骤1.参数初始化：设置搜索上界UB、下界LB，种群规模N，最大迭代次数tmax，维度D.

步骤2.初始化种群：在搜索空间随机产生初始种群.

步骤3.计算种群每个个体的适应度并排序，记录最好适应度wF和最差适应度bF.

步骤4.根据公式(6)更新候选解位置.

步骤5.根据公式(8)以一定的概率Pt让当前个体与种群最优个体进行交叉操作.

步骤6.引入人工蜂群搜索策略，根据贪婪策略保留较优个体.

步骤7.判断结束条件，若满足迭代条件则算法终止，否则重复步骤3-步骤6.

步骤8.输出最优值，算法结束.

ISMA实现流程图如图2所示.

图2 ISMA实现流程图Fig.2 ISMA implementation flowchart

4 仿真实验与结果分析

4.1 参数设置说明

仿真实验采用的计算机配置为，Intel Core i5-7500U，32GB内存，64bit操作系统，计算环境为Matlab2016(a).本文选取粒子群优化(PSO)算法，灰狼优化(GWO)算法，鲸鱼优化算法(WOA)和SMA与ISMA进行实验对比，基本参数统一设置为：最大迭代次数tmax=500，低维维度d=30，高维维度d=200，种群规模N=30.各算法内部参数设置如表1所示.

表1 算法参数设置Table 1 Algorithm parameter setting

4.2 测试函数介绍

为了测试ISMA在实际算法上的寻优效果，选取8个基准测试函数进行仿真实验，其中f1-f5为单峰测试函数，f6-f8为复杂多峰测试函数.测试函数基本信息如表2所示.

4.3 各改进SMA寻优性能对比

为了验证ISMA改进策略的效果，将ISMA与基本SMA、文献[15]提出的LF-SMA和文献[16]提出的BTβSMA进行基准测试函数寻优性能对比实验，其中LF-SMA是引入莱维飞行的黏菌算法，BTβSMA是引入自适应β爬山策略的黏菌算法.相比于基本的SMA，LF-SMA和BTβSMA在对于基准测试函数的寻优性能上相比于SMA有很大提升，为了体现实验的公平性，实验参数统一设置为：最大迭代次数tmax=500，维度d=30，种群规模N=30，算法寻优执行30次，取平均值和标准差，测试函数相关信息由表2给出，寻优性能对比结果如表3所示.

表2 基准测试函数介绍Table 2 Introduction to benchmark functions

由表3可知，ISMA对于基础测试函数的寻优性能整体优于其他改进SMA，对于单峰测试函数f1-f4和多峰测试函数f6、f7，ISMA能够收敛到理论最小值0；对于单峰测试函数f5和f8，虽然ISMA不能收敛到理论值，但其收敛精度优于LF-SMA和BTβSMA，并且相对于SMA有一定提升，说明本文提出的ISMA在基准测试函数上具有一定的优势.

表3 各改进算法性能对比Table 3 Performance comparison of the improved algorithms

4.4 ISMA高维寻优性能测试

为了进一步测试ISMA处理高维问题的能力，将其与基本PSO算法，GWO算法，WOA以及SMA进行高维测试函数寻优对比，统一采取维度d=200，最大迭代次数tmax=500，种群规模N=30，各算法其他内部参数由表1给出，测试函数相关信息由表2给出，为了更直观地分析ISMA处理高维问题的性能，图3给出了在200维时各算法独立运行30次后的适应度平均值收敛曲线.

图3 基准测试函数平均收敛曲线(200维)Fig.3 Function average convergence curve(200d)

由图3结果可知，相比与基本PSO算法、GWO算法、WOA以及SMA，ISMA在高维优化问题的处理上仍然具有很大的优势.对于高维基准测试函数f1、f2、f3、f4、f6和f7，ISMA能够收敛到全局最小值0，且收敛速度也是最快的，例如：对于单峰函数f1，SMA和ISMA都能找到0，但是ISMA在迭代142次时算法收敛，而SMA则需要迭代439次；对于单峰测试函数f5和复杂多峰测试函数f8，ISMA虽然没有收敛到全局最优值，但能快速跳出局部最优值，并收敛到更加接近全局最小值.由此可知，ISMA在高维函数处理时同样具有优越的性能.

4.5 Wilcoxon秩和检测

Wilcoxon秩和检测是一种比较两组数据的非参数统计检验，测试本质上是计算对比数据之间的差异，并分析这些差异，以确定它们是否在统计上存在显著不同.为了全面体现ISMA的优势，本文引入Wilcoxon秩和统计检验验证ISMA对于基准测试函数仿真结果的有效性，选取基本PSO算法、GWO算法、WOA、SMA以及本文引入改进人工蜂群算法策略的SMA变体(ASMA)与ISMA对表2所示8个基本测试函数仿真结果进行秩和统计分析并计算p值，当p<5%时，可以被认为是拒绝零假设的有力验证[17].结果+、-和=分别表示ISMA秩和统计结果优于、差于和等于对比算法，NaN表示没有数据进行对比，Wilcoxon秩和检验结果如表4所示.

由表4结果可知，ISMA算法与PSO算法、GWO算法、WOA、SMA以及ASMA的Wilcoxon秩和检验对比结果p值基本上都小于5%，说明从统计学上来说，ISMA算法对于基本函数的寻优结果优势是明显的，从而进一步体现了ISMA的鲁棒性.

表4 Wilcoxon秩和检验结果Table 4 Wilcoxon rank sum test results

4.6 CEC2014测试函数寻优对比

为了验证ISMA求解复杂优化问题的性能，本文采用部分CEC2014函数进行仿真实验，CEC2014测试函数具有复杂的特征，常用于验证算法有效性，其中包括单峰(UN)、多峰(MF)、混合(HF)和复合(CF)类型函数，部分CEC2014测试函数相关信息如表5所示.实验参数统一为：种群规模N=50，维度d=30，最大迭代次数tmax=2000，每个函数独立运行30次取平均值和标准差.本文选取PSO算法、SCA、L-SHADE算法以及LFSMA与ISMA进行寻优结果对比，其中，PSO算法和SCA算法实验数据分别来源于文献[18]和文献[19]；LFSMA[20]是引入量子旋转门策略的SMA；L-SHADE算法[21]由于其在CEC2014中的优秀表现，常用来进行对比实验.各算法对于CEC2014测试函数寻优结果对比分析如表6所示.

表5 部分CEC2014函数介绍Table 5 Part of the CEC2014 function

表6 CEC2014函数优化对比Table 6 CEC2014 function optimization comparison

由表6结果可知，在求解单峰CEC03函数时，L-SHADE算法表现优秀，但是对于多峰、混合和复合类型的函数优化上ISMA表现出了绝对的优势；对于CEC07、CEC12、CEC14和CEC19函数，ISMA能够找到最优值，对于其他混合和复合类型的CEC2014函数，ISMA也能收敛到最优值附近；虽然SMA变体LFSMA对于CEC2014函数的寻优效果也具有一定优势，但是整体性能略差于ISMA.说明ISMA在对于复杂问题的处理上同样具有很好的鲁棒性.

5 结束语

为了解决黏菌算法存在的收敛速度慢，易早熟收敛的问题，本文提出了一种改进交叉算子的自适应人工蜂群黏菌算法.引入自适应可调节反馈因子和改进的交叉算子加快算法收敛；考虑到人工蜂群算法强大的搜索能力，引入一种全局最优解引导的人工蜂群搜索策略，从而提高了算法跳出局部最小值的能力.通过8个基准函数和部分具有复杂特征的CEC2014测试函数，以及Wilcoxon秩和统计检测进行实验仿真，结果表明，本文提出的ISMA具有很好的寻优性能.下一步研究内容考虑将ISMA应用到实际工程问题中，进一步验证ISMA在处理实际问题的优越性.