许健　许峰

摘要：针对蛙跳算法进化后期种群多样性下降、易陷于局部最优解的缺陷，提出一种自适应变异蛙跳算法。其基本思想是：根据函数变化率建立一种自适应变异选择机制，当函数变化率较大时，采用高斯变异提高算法的局部收敛能力；当函数变化率较小，即算法可能陷入局部收敛时，采用柯西变异促使算法跳出局部最优。数值实验结果表明，该自适应变异选择机制不仅提高了蛙跳算法的局部收敛性，而且能在很大程度上避免早熟现象。

关键词：蛙跳算法；变异；自适应；函数变化度；局部收敛性

DOIDOI：10.11907/rjdk.181434

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）009007704

英文标题Adaptive Mutation SFLA Based on the Function Change Rate

--副标题

英文作者XU Jian， XU Feng

英文作者单位（College of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001，China）

英文摘要Abstract：In light of population diversity decline in the late evolution of shuffled frog leaping algorithm，an adaptive mutation shuffled frog leaping algorithm is put forward.The basic idea is to establish an adaptive selection mechanism according to the function change rate；when the function change rate is large，the Gauss mutation is used to improve the local convergence of the algorithm；when the function change rate is less likely to fall into local convergence，Cauchy mutation is used to urge algorithm jump out local optimum.Numerical experiments show that this adaptive mutation selection mechanism not only improves the local convergence of shuffled frog leaping algorithm，but can also avoid the premature phenomenon to a great extent.

英文关键词Key Words：SFLA；mutation；adaptive；function change rate；local convergence

0引言

蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）[1]是一种新型群智能优化算法。与其它群智能优化算法类似，蛙跳算法不可避免地存在一些缺陷，如局部搜索能力欠佳、搜索效率不高等。因此，学者们进行了大量研究工作。崔玉娟等[2]将混沌映射引入蛙跳算法，改善了蛙跳算法的局部收敛性；吴国伟[3]、银莉等[4]将蛙跳算法与粒子群算法相结合，在一定程度上避免了蛙跳算法過早收敛的现象；李盼池等[5]根据平均目标函数值进行自适应分组，提高了蛙跳算法的优化能力；叶晶晶[6]在蛙跳算法中引入模拟退火思想，有效避免了算法陷入局部最优；许波等[7]将蛙跳算法引入遗传算法，以改善遗传算法性能；任聪等[8]将混合蛙跳搜索策略引入人工蜂群粒子群算法，改善了粒子群算法性能。蛙跳算法的应用研究也取得了丰硕成果，已被应用于流水线调度、车辆路径问题、神经网络优化、支持向量机预测等多个领域[9-14]。

变异操作作为提高群智能优化算法寻优能力的一种有效手段，已被成功用于遗传算法、粒子群算法和蚁群算法等经典算法中。在蛙跳算法中，如何利用、改进变异操作以提高算法寻优性能已被越来越多学者所重视，特别是对自适应变异机制的研究已成为蛙跳算法的一个研究热点。葛宇等[15]应用混沌序列构造一种自适应变异算子；李晶晶[16]根据种群中最优个体是否相同给出一种高斯变异与柯西变异的自适应选择方法；刘珂等[17]在蛙跳算法中根据种群交换次数设计一种高斯变异与柯西变异的自适应选择方法；彭平等[18]利用层次分析法自适应调整各影响参数权重。

本文在传统研究工作的基础上，提出一种基于目标函数变化率的自适应变异蛙跳算法，并根据数值实验对该算法进行了性能测试。

1蛙跳算法

1.1蛙跳算法数学模型

蛙跳算法可以用数学语言描述如下：设有N只青蛙，构成一个种群X=（X1，X2，…，Xn），其中每个个体在空间中的坐标为Xi=（xi1，xi2， …，xid），坐标值可以理解为该个体信息。计算每个个体的适应度f（xi1，xi2，…，xid），根据适应度大小按逆序排列，存储于集合F={（Xi，f（xi1，xi2，…，xid）），i=1，2，…，n}。将种群分割为S个子种群（S1，S2，…， Ss），每个子种群含有P个个体，即N=S*P。在进化时，将集合F={（Xi，f（xi1，xi2，…，xid）），i=1，2，…，n}中的所有个体依次放入子种群（S1，S2，…，Ss）中。重复上述过程，直到将所有个体放入集合S。

将每个子种群中适应度最大和最小的个体分别记为Pb和Pw，种群中适应度最大的个体记为Xb。每次更新时，仅对Pw进行操作以提高其适应度。更新方法是：

Ds=r（Pb-Pw）（1）

Pn=Pw+Ds （-Dmax≤Ds≤Dmax）（2）

其中，Dmax是最大步长，Ds是调整向量，r是（0，1）内的随机数。

若新个体Pn的适应度大于Pw的适应度，则以Pn替代Pw；否则，以Xb替代Pb，重复以上更新方法。若适应度有所改进，则替代Pw；否则，随机生成新个体替代Pw。重复上述步骤，直至达到设定的最大迭代次数Ne。

对所有子种群进行局部搜索，混合这些子种群后组成一个新种群，并对新种群按适应度排序，再将其分割成子种群，然后进行更新和局部搜索，直至达到设定的最大进化代数Nmax。

1.2蛙跳算法流程

蛙跳算法流程如图1所示。

2基于函数变化率的自适应变异蛙跳算法

2.1变异算子

“变异”的概念来源于生物学，指父代与子代间的遗传学差异。1975年，美国Michigan大学的Holland教授提出遗传算法时，首次将变异操作引入进化算法。在进化算法中，变异算子主要有以下两个作用：①当进化计算进行局部搜索时，变异算子可加速算法向最优解收敛，提高算法局部搜索能力和收敛速度；②当种群的多样性下降，有陷于局部收敛的趋势时，变异算子可以提高种群多样性，引导个体跳出局部最优区域。

蛙跳算法主要采用下列两种变异算子：

（1）高斯变异算子。在概率统计中，正态分布也称为高斯分布，标准正态分布的概率密度函数φ（x）及图形如下：

φ（x）=12πe-x22，-

高斯变异是将一个服从高斯分布的随机扰动项加到每个个体上。若用Ni（ni1，ni2，…，nid）表示第i个个体服从高斯分布的随机扰动项，则第i个个体的高斯变异可描述为：

Xi=Xi+XiNi，（4）

其中nij是服从标准正态分布的随机数。

（2）柯西变异算子。柯西分布是数学期望不存在最著名的例子，在概率统计中占有重要地位，其概率密度函数f（x）如下：

将一个服从柯西分布的随机扰动项加到个体上的操作称为柯西变异。

从图3中可以清楚看出，柯西分布在中间区域部分小于高斯分布，而在两侧区域部分大于高斯分布，且两翼较窄，具有典型的两翼概率特征，说明柯西分布能以很大概率产生一个较大的随机数，也即是说，柯西分布能以很大概率产生较大的变异步长。

图3柯西分布密度函数

根据上述分析可知，高斯变异具有较强的局部搜索能力，可提高算法收敛速度；柯西变异则具有较强的全局搜索能力，当算法可能陷于局部最优时，能以很大概率引导个体跳出局部最优区域。

2.2自适应变异选择机制

如何适当地选择高斯变异和柯西变异是蛙跳算法中极具实用价值的问题。传统自适应方法基本上是针对具体问题设计的，在特定问题中效果较好，但缺乏普适性。因此，本文根据目标函数变化率，提出下列变异机制的自适应选择方法[19]：

当γij的模小于设定阈值ε（通常取10-2），即目标函数变化率很小时，表明算法可能陷入局部收敛，此时选用柯西变异引导个体跳出局部收敛，否则选择高斯变异进行局部搜索，以提高算法收敛速度。

2.3基于函数变化率的自适应变异蛙跳算法流程

本文提出一种基于函数变化率的自适应变异蛙跳算法 （Adaptive Mutation SFLA Based on the Function Change Rate，AMSFLA），其流程如下：①给定蛙跳算法参数，包括：种群规模N、子种群数S、子种群内部更新次数Ne、进化次数Nmax，并生成初始种群；②计算每个个体的适应度，并根据适应度将这些个体按降序排列，确定Xb；③若满足停止条件，则输出结果，否则进行下一步；④计算目标函数的相对变化率，并据此选择高斯变异或柯西变异；⑤将种群分成S个子种群；⑥对子种群进行局部搜索；⑦将各子种群重新混合组成新种群，转到②。

3数值实验与算法性能测试

为了检测AMSFLA的性能，下面选取4个标准测试函数，分别用基本蛙跳算法（SFLA）、一种改进蛙跳算法（ISFLA）[20]和AMSFLA 3种算法进行对比实验。

（1）De Jong F1。

f1（x1，x2，x3）=∑3i=1x2i-5.12≤xi≤5.12 （i=1，2，3）

（2） De Jong F2。

f2（x1，x2）=100（x21-x2）2+（1-x1）2-2.048≤xi≤2.048 （i=1，2）

（3）Schaffer F6。

f3（x1，x2）=0.5+sin2x21+x22-0.51.0+0.001（x21+x22）2-100≤xi≤100 （i=1，2）

（4） Schaffer F7。

f4（x1，x2）=（x12+x22）0.25[sin2（50（x21+x22）0.1）+1.0]-100≤xi≤100 （i=1，2）

这4个函数理论上的最优值均为0。第1个为简单函数，常用于测试算法效率。其余3个均为复杂多峰函数，常导致算法陷入局部最优，所以可用来测试算法是否发生早熟。

验证方法为：首先给出3种算法对4个测试函数某次运算得到的典型进化曲线，以直观比较3种算法的性能，然后进一步从收敛速度、优化精度、优化结果穩定性及100次优化成功率4个方面进行定量比较。

图4显示，对于f1这种简单函数，ISFLA与AMSFLA的优化效果几乎没有区别，SFLA的优化效果稍差；图5-图7则显示，虽然ISFLA的优化效果明显优于SFLA，但在进化过程中，还是与SFLA一样出现了早熟现象，而AMSFLA的优化效果不仅远优于SFLA，而且也明显优于ISFLA，几乎未出现早熟现象，只是对于f4的优化效果与理论值相比略差。

为更进一步定量比较SFLA、ISFLA和AMSFLA的性能，表1给出了3种算法优化指标。其采用相同参数运行100次，若最优值与理论值的误差在允许误差内，则视为成功。

表1中的各项指标显示，AMSFLA在最優解质量、算法稳定性与收敛速度方面均远优于SFLA，对于复杂问题的优化能力也明显优于ISFLA。需要特别指出的是，AMSFLA的抗早熟能力得到了很大提高。

4结语

通过对高斯变异和柯西变异不同特点的分析，本文设计了一种根据函数变化率自适应选择高斯变异和柯西变异的方法，具有较强的普适性，并将其引入蛙跳算法。新算法可实现高斯变异局部搜索能力强和柯西变异可避免早熟两个优势的互补。数值实验结果显示，该算法不仅局部搜索能力强、解的精度高，而且可在很大程度上克服蛙跳算法易陷于局部收敛的缺陷。

虽然基本蛙跳算法已被证明是全局收敛[16]，但本文在基本蛙跳算法中引入了高斯变异和柯西变异，因此其理论上的收敛性尚有待研究。另外，由于本文算法中添加了目标函数变化率过程，所以运行效率有所下降。然而，这恰好符合优化中“没有免费午餐”的原理。

参考文献参考文献：

[1]EUSUFF M M，LANSEYLE K F.Optimization of water distribution network design using shuffled frog leaping algorithm [J].Journal of Water Resource Planning and Management，2003，129（3）：210225.

[2]崔玉娟，察豪，田斌.改进的混合蛙跳算法在雷达网部署中的应用[J].海军工程大学学报，2015，27（1）：108112.

[3]吴国伟，赵艳玲，王龙.基于蛙跳算法的离散粒子群算法端元提取[J].中国图像图形学报，2015，20（5）：724732.

[4]银莉，靳雁霞，张晓闻.粒子群蛙跳算法在图像相关反馈中的研究[J].微电子学与计算机，2017，34（2）：97101.

[5]李盼池，卢爱平.自适应分组量子衍生蛙跳算法[J].系统工程理论与实践，2016，36（5）：13061317.

[6]叶晶晶.蛙跳算法的改进及在车辆路径问题中的研究[D].广州：广东工业大学，2016.

[7]许波，彭志平，余建平.基于蛙跳思想的量子编码遗传算法[J].中国工程科学，2014，16（3）：108112.

[8]任聪，葛洪伟，杨金龙.引入混合蛙跳搜索策略的人工蜂群粒子群算法[J].计算机工程与应用，2015，51（22）：3841.

[9]潘玉霞，潘全科，李俊青.蛙跳优化算法求解多目标无等待流水线调度[J].控制理论与应用，2011，28（10）：13631370.

[10]张思亮，葛洪伟.粒子群和蛙跳的混合算法求解车辆路径问题[J].计算机工程与应用，2011，47（21）：246248.