戴月明，张明明，王 艳

(江南大学物联网工程学院，江苏 无锡 214122)

1 引言

混合蛙跳算法SFLA(Shuffled Frog Leaping Algorithm)于2003年由Eusuff等[1,2]提出。该算法结合了模因算法MA(Memetic Algorithm)和粒子群优化PSO(Particle Swarm Optimization)算法两者的优点，具有结构简单、参数设置少、运算速度快、全局寻优能力强、易于实现等特点，正成为智能计算领域的研究热点。

但是，相关研究表明，混合蛙跳算法在进化后期收敛速度慢，易陷入局部极值，求解精度低。为此，众多学者对其进行了大量的研究与改进。文献[3]通过反向学习策略生成初始种群以及对局部搜索策略引入比例因子两个阶段来进行改进，有效地提高了蛙跳算法的性能；文献[4]改进了蛙跳算法的局部搜索跳跃规则，同时引入协作与柯西变异策略代替随机更新，一定程度上提高了算法的收敛速度与精度；文献[5]提出一种新的更新策略，对子群内每一个青蛙都进行更新，并固定全局混合迭代时间间隔，实验结果表明改进的算法寻优精度高、收敛速度快；文献[6]通过结合量子进化算法的理论，提出量子二进制混合蛙跳算法，具有收敛速度快、全局搜索能力强、稳定性好等优点；文献[7]提出了双加速因子的搜索策略，同时对子群最差蛙以及子群最优蛙进行更新，进一步提高了算法的收敛速度。

以上文献对混合蛙跳算法的不同改进方法虽在一定程度上提高了算法的收敛速度和精度，但效果并不是很理想，这些改进并没有充分考虑到更优青蛙更可能存在于最优青蛙附近空间以及子群之间的交互学习和精英群体的自主学习进化能力。因此，本文提出了一种协同进化混合蛙跳算法CSFLA(Coevolutionary Shuffled Frog Leaping Algorithm)。该算法在子群内最差个体更新策略中引入子群青蛙平均值，并充分利用最优个体的优秀基因对最优个体附近空间进行有效探索。同时，结合交互学习策略，每个子群内少量较差的个体向邻近子群的最优个体进行交互学习，利于信息共享，增加种群的多样性，提高算法解的质量，加快寻优速度。为避免陷入局部极值，在全局迭代过程中采取精英群自学习进化机制，以进一步精细搜索精英个体空间获得更优解，引领种群逃出局部最优，提高算法性能。最后，通过仿真实验验证了新算法的有效性。

2 混合蛙跳算法

由文献[8]可知，基本混合蛙跳算法SFLA(Shuffled Frog Leaping Algorithm)是一种基于群体智能的生物进化算法，模拟青蛙按族群划分进行觅食的过程，是一种结合了确定性方法和随机性方法的进化计算方法。SFLA的基本思想是[1]：随机生成F只青蛙组成初始种群体P=(P1,P2,…,PF)，D维解空间中的第i只青蛙表示为Pi=(Pi1,Pi2,…,PiD)。生成初始群体之后，首先将种群内的青蛙个体按适应值f(Pi)进行降序排列，并记录蛙群中具有最优适应值的全局最优青蛙为Pg。然后将蛙群分成m个子群，每个子群包含n只青蛙，满足关系F=m*n。第1只青蛙进入第1个子群，第2只青蛙进入第2个子群，…，第m只青蛙进入第m个子群，第m+1个青蛙又进入第1个子群，第m+2只青蛙进入第2个子群，以此类推，直到F只青蛙划分完毕。

局部搜索：每个子群中具有最好适应值的最优青蛙个体和最差适应值的最差青蛙个体分别记为Pb和Pw。然后对每个子群进行局部搜索,即对子群中的Pw循环进行局部搜索操作。其更新策略为：

ds=rand(0,1)*(Pb-Pw)

(1)

(2)

其中：ds代表移动步长，rand(0,1)为[0,1]内的随机数；dmax为其移动的最大步长。

如果新个体Pn优于原个体Pw，则取代Pw；如果没有得到改进，则用全局最优个体Pg代替Pb，代入式(1)～式(2)重新生成新个体，若优于Pw则取代Pw，否则随机生成一个新个体取代Pw。重复以上更新操作直到子群最大迭代数。

全局信息交换：当所有子群的局部搜索完成后，进行全局信息交换，将所有子群中的青蛙重新混合成一个新的蛙群，并再次排序和划分子群，然后每个子群再进行局部搜索。如此反复，直到满足相应的结束条件(收敛到指定精度或达到全局最大进化代数)。

3 协同进化混合蛙跳算法

协同进化混合蛙跳算法(CSFLA)针对基本SFLA存在收敛速度缓慢、收敛精度低、青蛙子群局部信息和青蛙种群全局信息交流不全面等缺点进行了优化。本文通过引入子群青蛙平均值，并充分利用最优个体的优秀基因对子群内最差青蛙个体更新方式进行改进；同时考虑到子群之间的交互学习有利于信息共享，对子群内较差的青蛙个体采取交互学习策略，以提高解的质量，加快算法寻优速度；最后，在全局迭代过程中采取精英群自学习进化机制，以获得更优解，避免陷入局部最优，提升算法的全局寻优能力。

3.1 局部位置更新算子

传统混合蛙跳算法只对子群内最差青蛙个体Pw进行更新，局部搜索为一个线性搜索，使得生成的新个体Pn总是沿直线方向向Pb或Pg靠近[9]，限制了搜索区域，进化后期种群多样性明显下降，易陷入局部最优，从而影响算法的求解精度和收敛速度。

本文充分利用子群最优个体和全局最优个体的优秀基因，深入搜索最优青蛙附近空间以获得更优青蛙。同时考虑到全组青蛙的更新现状对下一步进化具有重要的影响，组内最优个体代表了组内青蛙所处的最好位置，对整个子群起到重要的引领作用；组内所有青蛙的平均值在一定程度上反映了子群的整体水平。因此，对传统混合蛙跳算法的组内更新策略进行了重新设计，本文从最优青蛙位置出发，利用最优青蛙与最差青蛙以及组内所有青蛙的平均值与最差青蛙的随机差值为步长基数，调整更新步长，最后采用随机双向的更新方式。双向随机查找更优青蛙，以此扩大解空间的搜索范围，从而提高了局部搜索的效率。

在进行组内搜索时，首先计算组内青蛙的平均值Pa。对子群内最差青蛙的更新策略进行改进，定义如下：

ds=r*(r*(Pb-Pw)+(1-r)*(Pa-Pw))

(3)

Pn=Pb±ds

(4)

其中r代表[0,1]内的随机数。

根据子群最优个体Pb对Pw进行更新操作，若所得出的新个体Pn优于子群内最差青蛙个体Pw，则对其进行取代；若得出的结果没有改进，那么用种群的最优个体Pg代替Pb，代入式(3)～式(4)重新进行更新操作，若优于Pw则用新个体取代Pw；否则双向随机生成一个新个体取代Pw。

3.2 交互学习策略

启发于人类社会不同群体间可以交互学习的特点[10]，依据生物学上同物种间信息的交互共享有利于物种生存的原理，个体与其近邻同伴之间进行频繁的信息交互，可以扩大个体的感知范围，提高个体感知信息的速度和准确率，成员间的信息交互有利于个体进化[11]。

因此，在算法进行局部搜索时，对子群内较差的青蛙个体采取交互学习策略进行更新，对子群内部少量(例如3个)适应值较差的青蛙个体，利用全局最优个体Pg与所在子群的最优个体Pb之间的随机点为起点，以保持当前迭代全局最优个体以及所在子群的优秀基因。每一只较差青蛙个体向邻近子群的最优个体进行交互学习，获取其他子群的优质元素，整体提升整个种群的质量。通过此交互学习策略产生的新个体，若优于原个体则对其进行取代，否则保持不变，定义式如下：

Po=r*Pg+(1-r)*Pb

(5)

(6)

Pn=Po+△Pmi

(7)

交互学习策略使得青蛙个体学习的方向具有了多样性，为算法摆脱局部最优提供了新的额外动力。同时，可以减少算法寻优过程的盲目性，加快算法的寻优速度。

3.3 精英群自学习进化机制

自然界的生物不断调整自身状态来适应环境[12]。针对目前蛙跳算法研究中忽视个体能动性，尤其是种群中精英群体的自主学习进化能力，提出了精英群自学习进化机制。在全局迭代中种群的多个精英个体组成单独的精英群进行主动的自我学习和调整，在精英个体空间进行小邻域精细搜索，将搜索到的更优解返回当前迭代种群，每一代个体都能比上一代个体更好地适应环境，从而最终必然更加逼近最优个体，进而指导算法改善下一步的进化方向，进一步提高算法的全局寻优能力，减少陷入局部最优的危险。

精英群自学习进化机制的第1 步是精英个体的选择。根据多精英比单精英更能够引导群体学习的社会现象，在蛙跳算法的全局信息交换阶段，将个体按适应值进行排序，选取当前种群最好的m个精英个体组成一个精英群，引入双向随机变异算子，通过对“精英”个体携带的信息进行多次多角度的随机扰动变异操作进行自学习进化，既保留了精英个体的优秀基因，又在其周围邻域空间进行更深入的精细探索以产生更优秀的新个体，通过在精英群空间多角度双向随机探索，使算法具备了一定的自主学习能力，有利于算法跳出局部最优解的束缚进行全局搜索。精英自学习方程为：

△Pij=ξrands()ij*Pij

(8)

(9)

其中,Pij是个体Pi第j维数；rands()ij为对应Pij的-1到1的随机数，使得对种群的精英个体Pi的每一维度进行双向随机变异扰动；ξ为变异参数。

如果式(8)和式(9)产生一个更优解则取代原精英个体，否则对式(8)精英个体的随机扰动进行反序双向探索，再利用公式(9)获得更优解，如果还是不能找到更优解，则保持原精英个体不变，以避免产生的种群个体劣化。式(8)和式(9)是在精英个体Pi的基础上增加了双向随机变异因子，增加了新个体的随机性，既具有随机搜索的作用，又优于随机搜索，因为它利用了胜者的信息。精英群自学习进化机制增强了算法逃离局部最优的能力，能够正确导向算法的进化，指引种群有效搜索，加速收敛。

3.4 协同进化混合蛙跳算法的算法流程

综上所述，本文提出的协同进化混合蛙跳算法CSFLA的基本流程如下：

步骤1初始化种群及相关参数，选取合适的青蛙总数F，每个青蛙个体的维度为D，子群数m，子群内个体数n，子群内迭代数Ne，种群总进化代数MAXGEN，精英变异参数ξ。

步骤2计算每个个体的适应度，根据适应度将F个个体降序排列，选取适应度值最好的m个精英个体组成精英群，在全局迭代中对精英群根据式(8)和式(9)采取精英群进化机制进行多次多角度的迭代进化，以产生更优个体取代原个体，指导整个种群向更好的方向进化。

步骤3重新计算每个个体的适应度，根据适应度将F个个体降序排列，记录整个种群的最优候选解为Pg并划分成m个子群。

步骤4对每个子群依次进行局部搜索，局部深度搜索策略如下：

(1)确定子群内最优青蛙个体Pb，最差的青蛙个体Pw，整个种群的最优青蛙个体Pg，根据式(3)和式(4)生成新个体Pn对子群内最差的青蛙个体Pw进行更新，并且若新个体位置优于Pb，则更新子群内最优青蛙个体Pb的位置；若新个体位置同时又优于Pg，则更新全局最优个体Pg的位置。

(2)交互学习策略，对子群内部少量较差的青蛙个体根据式(5)～式(7)向邻近子群的最优个体进行交互学习，产生1个新个体，若优于原个体，则对其进行取代，否则保持不变，并且若变异生成的新个体位置优于Pb，则更新子群内最优青蛙个体Pb的位置；若变异生成的新个体位置又优于Pg，则同时更新全局最优个体Pg的位置。

步骤5对每个子群不断迭代直到达到子群最大迭代数Ne从而跳出步骤4，结束局部搜索。

步骤6将各个子群重新混合构成一个新的种群，重复步骤2到步骤5,直到达到种群总进化代数MAXGEN。

CSFLA算法的伪代码描述如下所示：

Begin

/*全局迭代中精英群自学习进化机制*/

Calculate the fitness of each individual；

select the bestmelite individuals to form the elite group；

forgg= 1 tom

forgi= 1 to 5

Updateelitesby formula (8) and formula (9)；

break；/*一旦精英进化生成更优秀的青蛙个体,则立即取代原个体,否则保持不变*/

end if

end for

end for

/*局部搜索中*/

fori= 1 tom

forj= 1 toNe

/*子群最差青蛙个体更新策略*/

UpdatePwby formula (3) and formula (4)；

iff(Pn)

Pw=Pn;/*找出更好的新个体取代Pw*/

end if

iff(Pn)

Pb=Pn； /*更新子群最优位置*/

iff(Pn)

Pg=Pn；/*更新全局最优位置*/

end if

end if

/*子群内较差青蛙个体交互学习策略*/

formi=floor(9/10*n) ton-1

Update a small number of worse frogs individual by formula (5)～formula (7)；

iff(Pnew)

Pmi=Pnew；/*取代较差个体*/

iff(Pnew)

Pb=Pnew；/*更新子群最优位置*/

iff(Pnew)

Pg=Pnew；/*更新全局最优位置*/

end if

end if

end if

end for

nextj

nexti

End for

4 仿真实验结果及分析

4.1 实验设置

为了验证本文改进算法CSFLA的有效性，选取了如表1中的七个测试函数，并与混合蛙跳算法(SFLA)、文献[13]的GSFLA(A New Updated Strategy Shuffled Frog Leaping Algorithm based on Gravitation Search Algorithm)和文献[14]的改进混合蛙跳算法ISFLA(Improvement and Simulation for Shuffled Frog Leaping Algorithm)进行对比实验。

以上这七个测试函数的理论最优值都是0，其中Sphere(f1)函数是简单的单模态函数，通常被用来测试算法的进化效率。f2和f3是单峰函数，其余是复杂的多峰函数，通常有许多局部极小值点，在算法搜索过程中极易陷入局部极值而无法收敛到全局最优点。以上所选测试函数形态各异，具有很好的测试性能，可有效检验算法的收敛速度、全局寻优精度以及多峰寻优能力等优化性能。

性能评估采用如下方法：(1)固定全局迭代次数，评估算法的收敛速度、精度和稳定性；(2)固定收敛精度，评估算法的全局迭代次数；(3)CSFLA收敛到最优解0时全局迭代次数分析。

4.2 固定全局迭代次数的实验结果分析

实验参数设置如下：所有算法的青蛙种群规模F= 500，子群数m= 20，子群个体数n= 25，子群内个体迭代数Ne= 30。种群总进化代数MAXGEN= 250，青蛙个体解的维度D= 30，为了确保测试的准确性减小偶然性，本文采用多次测试取平均值的方法，设置重复运行次数t= 30并统计相关结果，取30 次的最优适应度值、平均适应度值和标准差作为参照指标进行对比。实验结果如表2所示。为了更直观地比较各种算法的寻优性能，图1中给出了每种算法所对应的测试函数适应度的进化曲线。

Table 1 Definition of the test functions

Table 2 Experimental results of the test functions

从表2中可以看出，无论是对于简单单峰函数还是复杂多峰函数，CSFLA在寻优精度及算法的稳定性上都取得了极大的提高，在表1中的七个测试函数Sphere(f1)、Quadric(f2)、Hyperellipsoide(f3)、Ackley(f4)、Griewank(f5)、Rastrigrin(f6)和Schaffer(f7)中均能收敛到最优解。表2中，最优值为30次运行结果中最好的一次，平均值则是30次运行结果的平均值，CSFLA算法在七个测试函数中均能收敛到最优解0，而其他三种算法都不同程度地陷入了早熟收敛。从这两项对比可以表明，在相同的进化迭代次数下，CSFLA相比ISFLA、GSFLA和SFLA具有更快的寻优速度、更高的收敛精度。标准差为30次独立运行结果的标准差，CSFLA算法在七个测试函数中的标准差均是0，通过对比，也可以明显看到，改进的CSFLA算法体现了更好的稳定性。这说明CSFLA具有较强的全局搜索能力，能够有效摆脱局部最优，具有比其他三种算法更好的收敛速度和寻优精度，极大地提高了算法性能，具有一定的鲁棒性。

Figure 1 Optimization results of the seven test functions图1 七个测试函数的优化对比结果图

图1是CSFLA、ISFLA、GSFLA和SFLA在七个测试函数中的进化曲线图，横坐标表示种群的进化代数，纵坐标表示平均适应度值的lg对数。从图1中也可以直观地看出，一开始进化，CSFLA就比ISFLA、GSFLA和SFLA体现出更优秀的寻优能力。相比其他三种算法，其收敛速度更快。在进化中后期，SFLA和GSFLA均不可避免地出现早熟收敛现象，ISFLA也不可避免地在函数f1～f3中出现早熟收敛现象，而CSFLA则有效避免了这种现象，成功寻找到全局最优解，大大提高了算法的收敛精度和寻优能力。以上实验结果表明，CSFLA在测试函数中具有更快的收敛速度和更精确的搜索精度，在函数f1、f2、f3、f4、f5、f6和f7的实验结果中，均收敛到最优值0。因此，本文改进后的算法CSFLA无论是在收敛速度、寻优精度还是稳定性方面都得到了极大的提高，有效改善了算法的性能。

4.3 固定收敛精度的实验结果分析

本实验指定各测试函数收敛精度如表3所示。所有算法的青蛙种群规模F= 500，子群数m= 20，子群个体数n= 25，子群内个体迭代数Ne= 30，青蛙个体解的维度D= 30。

为了避免算法因收敛到局部最优解而无法达到指定的精度，导致程序无法结束，本实验设置最大有效迭代次数MAXGEN= 250，如果在250次全局迭代后仍然没有达到指定的收敛精度，就认为算法该次没有收敛。独立运行30次，实验结果如表4所示。其中成功率=达到精度的实验次数/总的实验次数。

Table 3 Convergence accuracy of each test function

从表4可以看出，GSFLA和SFLA几乎对所有的测试函数都很难达到指定精度，ISFLA对f1～f6函数虽然可以达到指定精度，但收敛代数上明显高于CSFLA。本文提出的算法CSFLA对该七个函数的求解，收敛代数上明显低于ISFLA、GSFLA和SFLA，同时成功率均达到了100%。这说明CSFLA不仅收敛速度比其他算法要快，而且具有良好的可靠性和有效性。

4.4 CSFLA收敛到最优解0时全局迭代次数实验结果分析

从4.2节可以看出，本文所提算法CSFLA在七个测试函数中均能收敛到最优解0。所以，设计本实验得出CSFLA收敛到最优解0时所需的最小迭代次数、最大迭代次数、平均代数以及成功率，以进一步验证本文所提算法CSFLA收敛到全局最优解0的可靠性与有效性。参数设置均同4.2节，独立运行30次，实验结果如表5所示。

从表5可以看出，本文提出的算法CSFLA在250次全局迭代中均能100%收敛到七个测试函数全局最优解0，尤其对f4～f7的复杂多峰函数，寻优代数较小，寻优性能更好。本实验再次验证了CSFLA收敛到全局最优解0的可靠性与有效性。

Table 4 Comparison of experimental resultswith fixed convergence precision

Table 5 Experimental results of the time of global iterationwhen the CSFLA converges to the optimal solution of 0

5 结束语

本文提出的CSFLA针对混合蛙跳算法易早熟收敛、求解精度不高的缺陷，对子群最差青蛙个体更新策略进行改进使其能够有效避免算法陷入局部最优，交互学习策略的应用可增加子群间相互交流学习的机会，不仅有效提高了种群质量，而且加快了寻优速度。最后，在全局迭代过程中选取种群的部分精英个体组成精英群引入自学习进化机制，在精英群周围空间进行进一步深入搜索以获得更优的青蛙个体，引领整个种群的进化，有效地避免了算法陷入早熟收敛，大幅度提高了算法的性能。实验仿真结果也验证了所提算法的有效性。将改进的算法应用于实际工程中，进一步检验算法性能，将是下一步工作的重点。

[1] Eusuff M M,Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of Water Resources Planning and Management,2003,129(3):210-225.

[2] Eusuff M M,Lansey K E.Shuffled frog-leaping algorithm:A memetic meta-heuristic for discrete optimization[J].Engineering Optimization,2006,38(2):129-154.

[3] Naruka B, Sharma T K,Pant M,et al.Two-phase shuffled frog-leaping algorithm[C]∥Proc of the 3rd International Conference on Reliability,Infocom Technologies and Optimization (ICRITO)(Trends and Future Directions),2014:1-5.

[4] Wang H,Zhang K,Tu X,et al.A mnemonic shuffled frog leaping algorithm with cooperation and mutation[J].Applied Intelligence,2015,43(1):32-48.

[5] Wang L,Gong Y.A fast shuffled frog leaping algorithm[C]∥Proc of the 2013 9th International Conference on Natural Computation (ICNC),2013:369-373.

[6] Wang L,Gong Y.Quantum binary shuffled frog leaping algorithm[C]∥Proc of the 2013 3rd International Conference on Instrumentation,Measurement,Computer,Communication and Control,2013:1655-1659.

[7] Jaballah S,Rouis K,Ben Abdallah F,et al.An improved shuffled frog leaping algorithm with a fast search strategy for optimization problems[C]∥Proc of the 2014 IEEE International Conference on Intelligent Computer Communication and Processing (ICCP),2014:23-27.

[8] Cui Wen-hua, Liu Xiao-bing, Wang Wei,et al.Survey on shuffled frog leaping algorithm[J].Control and Decision,2012,27(4):481-486.(in Chinese)

[9] Li Jing-jing,Dai Yue-ming.Adaptive shuffled frog leaping algorithm adopting mixed mutation[J].Computer Engineering and Applications,2013,49(10):58-61.(in Chinese)

[10] Qin Quan-de, Li Li,Cheng Shi,et al.Interactive learning particle swarm optimization algorithm[J].CAAI Transactions on Intelligent Systems,2012,7(6):547-553.(in Chinese)

[11] Zhu Yong-fang.Information interaction and processing particle swarm optimization algorithm[D].Taiyuan:Taiyuan University of Science & Technology,2009.(in Chinese)

[12] Nie Chong, Wang Wei-ping,Zhao Wen,et al.An active learning genetic algorithm with learning operator[J].Computer Simulation,2006,23(9):168-171.(in Chinese)

[13] Sun Y H,Liu W,Xie Y S,et al.A new updated strategy shuffled frog leaping algorithm based on gravitation search algorithm[C]∥Proc of the 3rd International Conference on Material,Mechanical and Manufacturing Engineering (IC3ME 2015),2015:1432-1437.

[14] Li Jian-jun,Yu Bin,Chen Wu-ping.Improvement and simulation for shuffled frog leaping algorithm[J].Journal of System Simulation,2014,26(4):755-760.(in Chinese)

附中文参考文献：

[8] 崔文华,刘晓冰,王伟,等.混合蛙跳算法研究综述[J].控制与决策,2012,27(4):481-486.

[9] 李晶晶,戴月明.自适应混合变异的蛙跳算法[J].计算机工程与应用,2013,49(10):58-61.

[10] 秦全德,李丽,程适,等.交互学习的粒子群优化算法[J].智能系统学报,2012,7(6):547-553.

[11] 褚永芳.信息交互与处理微粒群算法[D].太原：太原科技大学,2009.

[12] 聂冲,王维平,赵雯,等.基于学习算子的自学习遗传算法设计[J].计算机仿真,2006,23(9):168-171.

[14] 李建军,郁滨,陈武平.混合蛙跳算法的改进与仿真[J].系统仿真学报,2014,26(4):755-760.