混合蛙跳算法(shuffled frog leaping algorithm,SFLA)^[1]是一种基于群体智能的亚启发式协同搜索计算技术，最早由M. M. Eusuff和K. E. Lansey于2000年提出。它结合了基于基因进化的模因演算法(memetic algorithm,MA)^[2]和基于群体行为的粒子群优化算法(particle swarm optimization,PSO)^[3]的优点^[4]，具有概念简单、参数设置少、计算速度快、全局寻优能力强、易于实现等特点^[5]，并在无线传感器网络覆盖优化^[6]、函数优化^[7]、经济负荷分配^[8]、生产调度组合优化^[9]等领域取得较好应用，正成为智能计算领域的研究热点。

与其他群智能算法相似，混合蛙跳算法也存在易陷入局部极值、进化后期收敛速度慢、计算精度低等缺点。为此，研究人员在不断深入研究和分析后，提出了多种不同思想的改进混合蛙跳算法，比较有代表性的有罗雪晖等^[10]在混合蛙跳算法中加入调整序思想设计了局部搜索策略，并在全局信息交换中加入变异算法，提出一种改进的混合蛙跳算法并应用于求解TSP问题；T. Niknam等^[11]利用混沌局部搜索策略提出改进的混沌混合蛙跳算法；借鉴分子动力学模拟的思想，张潇丹^[12]提出基于分子动力学模拟的改进混合蛙跳算法；Sun等^[13]提出一种基于粒子共享的粒子群蛙跳混合优化算法，算法利用粒子群具有良好全局搜索性能与混合蛙跳算法具有较强局部搜索能力的特点，克服了群体智能算法后期易陷入局部最优及“早熟”收敛的缺点。这些算法都在标准SFLA基础上进行不同程度的改进，但其改进也不同程度增加了算法的复杂性。

在SFLA中，青蛙的跳跃主要经历局部搜索和全局信息交换2个阶段，局部搜索使模因信息在局部个体间进行传递，全局信息交换使得局部间的模因信息得到交换，这在很大程度上决定了算法的收敛速度与解的质量。但青蛙在进化过程中，族群中的最差青蛙只向自身蛙群和最优青蛙所在蛙群的最好青蛙学习，族群之间的相互学习不够、共享能力不强。为此，利用各族群最优蛙的优势，构造广义中心青蛙，并改进蛙群的进化策略，使蛙群在原有学习策略的基础上，增加向广义中心青蛙学习的能力，提出广义中心混合蛙跳算法(shuffled frog leaping algorithm based on genernal center,GC-SFLA)。通过对8个标准测试函数的实验仿真，将提出的广义中心混合蛙跳算法与标准混合蛙跳算法及新近提出的知名群智能算法比较算法收敛速度和全局寻优能力。

混合蛙跳算法是一种基于群体智能的生物进化算法。该算法模拟湿地中一群青蛙按族群划分的思想进行觅食。在算法执行时，首先产生F只青蛙组成蛙群，对于N维优化问题，群体中第i只青蛙表示为X_i=(x_i¹,x_i²,...,x_i^N)，将蛙群内的青蛙个体按照适应值进行降序排列，找到全局最好青蛙(解)P_g。将蛙群分成m个族群，每个族群包含n只青蛙，满足关系F=m×n。族群的划分规则是：第1只青蛙进入第1个族群，第2只青蛙进入第2个族群，第m只青蛙进入第m个族群，第m+1只青蛙又进入第1个族群，第m+2只青蛙进入第2个族群，以此类推，直至所有青蛙划分完毕。第k个族群中最好的一个青蛙，记为P_k^b，相应地可以得到一个最差的青蛙，记为P_k^w。

为了获得更多的食物，较差的蛙受较好蛙的影响而跳向较好的蛙。根据上述初始蛙跳规则，第k个青蛙族群中最差蛙的更新公式为：

若执行更新策略(1)和(2)后，P_k^new_w对应的适应值优于P^{w_k对应的适应值，则用P_knew_w取代P_kw；否则采用P_g代替式(1)中的P_kb,重新更新P_knew_w。若重新执行更新后，P_knew_w对应的适应值优于P_kw对应的适应值，则用P_knew_w取代P_kw；否则采用式(3)随机产生一个新的蛙代替P_kw。}

重复以上的更新操作，直至满足事先设定的族群内的算法迭代次数。当所有族群的局部深度搜索完成以后，进行全局信息交换。局部深度搜索和全局信息交换两阶段交替进行，直到满足相应的结束条件。

在群智能算法中，随着进化的进行，全局极值将会越来越接近最优解。搜索结束后，全局极值将位于最优解的邻近区域。与此同时，由于群智能算法的随机性，每个个体也分布在全局极值的邻近区域。为了改善全局极值，使其更快向最优解靠近^[14]，Liu等^[15]引入中心粒子。中心粒子由群体的中心位置形成，伴随于整个搜索过程，除不具有速度外，该粒子具有与其他普通粒子相同的所有性质。其产生的方式如式(4)所示

汤可宗等^[16]通过实验进一步发现，在粒子群优化算法中，所有个体极值形成的中心相比群体的中心更能趋近于最优解。为此，将Liu等^[15]提出的中心定义为狭义中心(special center,SC)，见式(4)；将个体极值形成的中心定义为广义中心(general center,GC)，并提出双中心粒子群优化算法。广义中心粒子产生的方式如式(5)：

混合蛙跳算法的基本原理是每只青蛙在族群内最优青蛙和全群最优青蛙的引导下，“积极”向着最优解靠近，青蛙会被吸引到全群最优蛙和族群最优蛙的邻域。混合蛙跳算法的核心思想是族群划分，每个族群均有族群内最优粒子。搜索结束后，每个族群的最优蛙位置位于最优解或其邻近区域，相比全群最优蛙，族群最优蛙的中心或许会更接近最优解，这一启示给改善混合蛙跳算法提供了思路，为加速算法的收敛速度提供了非常有用的信息。借鉴文献^[16]广义中心思想，但混合蛙跳算法中无个体极值概念。为此，混合蛙跳算法中的广义中心青蛙定义如下。

定义 1 广义中心青蛙(general center frog,GCF) 在混合蛙跳算法的进化过程中，各族群的最优蛙位置表示为P_k^b，其中k表示是第几个族群。则广义中心青蛙P^gcf定义为

对形成的广义中心青蛙，评估其适应值，从P_g和P^gcf选择较优的解作为新的P_g，其公式描述为

标准SFLA算法蛙跳规则过于简单，族群最差蛙向本族群最优蛙学习，最差蛙的可能新位置被限定在当前蛙与最好蛙位置的线段上^[6]，限制了模因进化的搜索区域，且青蛙的学习能力不强，随着迭代次数的增加，各族群的性能将趋同，多样性降低。

本文提出一种新的蛙跳规则，该策略借助广义中心青蛙的特性，使族群内最差粒子在进化过程中，能够学习其他族群内最优粒子。首先，此蛙跳规则会增加最差粒子向全局最优点运动的可能；其次，根据蛙跳规则的数学表述可知，该操作扩大了最差粒子的搜索范围；再次，各族群在进化过程中形成了自己族群特色，也保证各族群的多样性。其位置更新公式与式(2)一致，最差蛙的移动步长更新公式为

若执行更新策略(9)和(2)后,P_k^new_w对应的适应值优于P_k^w，则用P_k^new_w取代P_k^w，否则，最差蛙的移动步长更新公式为

若执行更新策略(10)和(2)后，P_k^new_w对应的适应值优于P_k^w，则用P_k^new_w取代P_k^w，否则采用式(3)随机生成1个新的个体位置代替原来的P_k^w。

GC-SFLA算法的流程如图 1所示。

图 1 GC-SFLA算法流程 Fig. 1 Flowchart of GC-SFLA

图选项

1)GC-SFLA算法参数设置，包括族群数、族群内更新次数L_max、族群内青蛙数、混合迭代次数G_max等的设置。

2)蛙群初始化。初始化蛙群中青蛙位置并评估其适应值，记录蛙群最优蛙为P_g。

3)族群初始化。将蛙群分成族群，每个族群包含相同数量的蛙，第k个族群内的最优蛙和最差蛙分别记为P_k^b与P_k^w。

4)广义中心蛙的生成。利用式(6)计算P^gcf并评估其适应值，并根据式(8)更新P_g。

5)族群进化。对第k个族群中的P_k^w根据式(9)和(2)进行更新并计算其适应度值，若更新后的蛙优于原来的蛙，则取代原来族群中的蛙；如果没有改进，则根据式(10)和(2)进行更新并评估其适应度值，若更新后的蛙优于原来的蛙，则取代原来族群中的蛙；否则根据式(3)随机产生1个新蛙直接取代原来的P_k^w；重复上述局部搜索L_max次。

6)族群混合。将更新后的各族群内蛙重新混合，对更新后的蛙群中的蛙排序，记录更新后的蛙群最优蛙为P_g。

7)检验是否满足终止条件，若满足，则停止迭代，输出全局最优粒子位置P_g及其对应的适应值，否则转到步骤2)。

本文选用8个基准测试函数^[17]来测试算法的性能，见表 1，其中f₁~f₄是单模态函数，在给定搜索范围内只有1个极值点，主要检验算法的收敛速度和寻优精度，f₅~f₈是多模态函数，在给定搜索范围内有多个局部极值点，主要考察算法的全局搜索能力和逃离局部最优能力。

维度差异对算法性能有显著性影响。为验证改进算法的寻优效果和稳定性，将GC-SFLA算法与标准SFLA算法在不同维度下进行实验。实验参数设置为：最大函数评估次数5.0×10⁵，青蛙个体总数200，族群数为20，每个族群的青蛙个体数10，族群内的迭代次数10，最大蛙跳步长为最大搜索范围的0.4倍。

考虑篇幅限制，选取1个单峰函数f₁和3个多峰函数f₅~f₇进行不同维度下的实验，为消除算法的随机性影响，算法独立运行50次，以最终的平均值作为算法的最后寻优结果，实验结果见表 2。表中Mean、Std.Dev表示在限定的评估次数下算法的平均最优适应值及标准差，平均最优适应值反映了限定的评估次数下算法的寻优精度，标准差反映了算法的稳定性和鲁棒性。

由表 2可以看出，在不同的实验维度下，无论是解的质量还是算法的稳定性，GC-SFLA算法较标准SFLA算法均有较大提高。f₁函数为单峰函数，在搜索区域内只有1个极值点，无论在何测试维度下，GC-SFLA算法均能寻找到最优解，但SFLA算法在不同维度下的测试结果差异大。针对多峰函数，标准SFLA算法的寻优结果均不理想，对f₅函数，不论在何测试维度下，算法的均值和方差都一样，且效果非常不理想，但GC-SFLA算法不仅算法稳定性好，且都能寻找到最优解；对f₇函数，在不同测试维度下，标准SFLA算法寻优结果与最优结果差距大，但GC-SFLA算法均能在误差允许的范围内(如设置允许的误差范围为10^－10)达到最优；f₆函数是一个带有指数项的连续、多峰值函数，对f₆函数，虽然GC-SFLA算法的寻优结果与最优解之间有差距，但较标准SFLA算法，寻优能力确有明显提高。

图 2给出了GC-SFLA算法与SFLA算法在不同维度下对上述4个基准测试的进化过程曲线，图中横坐标计算次数的范围为0~5×10⁵，从图 2可以看出，GC-SFLA算法不仅寻优能力强，且收敛速度快，每种算法在较少次迭代后均达到较理想的寻优结果，而SFLA算法在较少的迭代后陷入局部极值。

图 2 4种测试函数的进化曲线 Fig. 2 The evolution curves of four benchmark functions

图选项

为进一步验证广义中心混合蛙跳算法的进化效果，将广义中心混合蛙跳算法和新近提出的知名群智能算法，如M. M. Eusuff等^[1]提出的标准混合蛙跳算法(shuffled frog leaping algorithm,SFLA)、Zhan等^[18]提出的自适应粒子群优化算法(adaptive particle swarm optimization,APSO)、Zhu等^[19]提出的全局最优引导的人工蜂群算法(Gbest-guided artificial bee colony algorithm,GABC)、汤可宗等^[16]提出的双中心粒子群优化算法(double center particle swarm optimization,DCPSO)和Wang等^[20]提出的多策略集成的人工蜂群算法(multi-strategy ensemble artificial bee colony algorithm,MEABC)等进行比较。GC-SFLA与SFLA算法参数设置参见3.2节，其他群智能算法的参数设置参见对应文献，最大函数评估次数2.0×10⁵。表 3给出了GC-SFLA与其他群智能算法在30维时的寻优结果对比。表 3的数据显示出，在8个测试函数中，GC-SFLA算法相比于SFLA、DCPSO、GABC、MEABC等4种算法得到的种群均值和方差均有明显的优势；与APSO算法相比仅在f₈函数上表现较APSO差，在另外7个测试函数中，均有较好的表现。

为了进一步比较这6种算法的测试结果，对6种算法进行t检验，表 4是GC-SFLA算法和其他5种算法在8个函数的t验结果。t检验的分位数为单侧0.05，自由度为30，查表得到t检验的临界值为1.697，即当t值大于这个值时，2种算法存在显著性差异。用“w/t/l”表示GC-SFLA算法与所选算法相比在w个函数上优于该算法，t个函数上无明显差异，l个函数上差于该算法。

从表 4中数据可知，GC-SFLA算法与标准SFLA算法、DCPSO算法相比，在5个测试函数上表现出较明显的优势，在3个测试函数上无显著差异；与APSO和GABC算法在8个函数的仿真实验相比，除了在f₁函数上无显著差异，在f₈上有明显劣势外，在其他6个函数上，GC-SFLA算法有着很大的优势。另外GC-SFLA算法与MEABC相比，除在f₈上有明显劣势，在f₅和f₇上无显著差异外，在其他5个函数上均有明显的优势。

为进一步在统计意义上比较6种算法的性能，采用Friendman检验对结果进行分析。表 5给出SFLA、APSO、DCPSO、GABC、MEABC和GC-SFLA 6种算法在8个测试函数上总体性能的平均排名。算法秩均值越小，性能越好，排名越高(排名最高的算法秩均值用粗体显示)。从表 5中数据可知，GC-SFLA明显高于其他5种算法。

为清晰地描述6种优化算法在进化过程中的收敛速率。本文给出了SFLA、APSO、DCPSO、GABC、MEABC和GC-SFLA在8个测试函数30维上的收敛性能曲线图，如图 3所示。由图 3可知，GC-SFLA算法能很好地增强算法逃离局部最优的能力，以及加速算法后期的收敛速度。GC-SFLA算法在处理单模态函数时，优势相当明显，其中f₁、f₂、f₃ 3个函数的进化曲线几乎呈直线下降。GC-SFLA算法在处理复杂的多模态函数时，收敛速度也具有非常大的优势，特别是f₅和f₇ 2个函数，在评估次数在2万次左右就可以寻找到最优位置，其他5种算法却很容易陷入局部最优，造成收敛速度变慢，甚至停滞不前。

图 3 8种测试函数的进化曲线 Fig. 3 The evolutionary curve of eight benchmark functions

图选项

本文在传统混合蛙跳算法的基础上，提出广义中心混合蛙跳算法。该算法分析传统混合蛙跳算法存在的族群之间学习能力不强的问题，引入广义中心青蛙的概念，设计广义中心策略以改进族群进化规则，该方法极大改善了族群之间的信息共享能力，增强了族群的多样性以及加快了算法的收敛速度。后续将加强算法在各类实际问题中的应用研究。