黄世贤 何晓曦 刘一明

（成都信息工程大学软件工程学院 四川省成都市 610225）

基于对自然界一系列独特规律的发现，尤其是对自然界各种动物群体的行为进行研究，人们发现了各种仿生算法。这些仿生算法通用性强，原理简单，实现方便，最重要的是能有效解决各种传统方法不易解决的复杂的组合优化问题，它能通过多次迭代自我适应，学习和发展，最后得到一个复杂问题的最优解或非常靠近最优解。

群智能算法作为一种近些年开始兴起的演化计算机技术，备受许多研究者的关注，它通过个体与个体，个体与环境交互，遵从简单的规则，最终表征出全局上的智能性[1]。通过对自然界中鱼群，鸟群，细菌群，蚁群等的研究，蚁群算法，鱼群算法，粒子群算法等应运而生[2]。而基于对蛙群的研究，混合蛙跳算法SFLA (Shuラed Frog Leaping Algorithm) 于2003年由Eusuあ等[3,4]提出。该算法结合了模因算法MA (Memetic Algorithm)和粒子群优化PSO (Particle Swarm Optimization) 算法两者的优点，混合蛙跳算法是一种求解离散优化问题的元启发式算法。SFLA 是一个基于群体的合作搜索算法，该算法在局部搜索中是通过从一个个体感染另一个的形式，在概念上与粒子群算法相似。全局搜索中运用洗牌策略允许在局部搜索之间交换信息，以向全局最优移动。

1 混合蛙跳算法

1.1 基本原理

举一个例子：给定一片湿地，湿地中生活着一群青蛙，湿地里离散的分布着许多石头，湿地里每只青蛙都通过跳跃不同的石头去到食物较多的地方，每只青蛙个体直接进行信息交换，以最优秀的青蛙为基准，每只青蛙的位置都作为一个解。

湿地的青蛙群体被分为不同的子群体，每个子群体有着自己的文化，执行局部搜索策略。在子群体中的每个个体有着自己的文化，并且影响着其他个体，也受其他个体的影响，并随着子群体的进化而进化。当子群体进化到一定阶段以后，各个子群体之间再进行思想的交流（全局信息交换）实现子群体间的混合运算，一直到所设置的条件满足为止。

1.2 算法模型

混合蛙跳算法SFLA (Shuラed Frog Leaping Algorithm)是模拟青蛙在寻食的过程当中,青蛙群体通过按子群分类进行信息交换的进展,将全局搜索与子群局部搜索相结合,使算法朝着全局最优解的方向进化。

1.2.1 全局搜索

Step1：设置SFLA 参数，青蛙群体总数F，族群数量m，每个族群的青蛙数n，最大迭代次数N，最大、最小步长Smax、Smin。

Step2：随机生成F 只青蛙并计算各个蛙的适应值。

Step3：按适应值大小进行降序排序并记录最好解Px，并且将蛙群分成多个族群。把F 个蛙分配到m 个族群中去，每个族群包含n 个蛙。

Step4：每个族群执行族群局部搜索。

Step5：将各个族群进行混合，然后将各个族群中的蛙重新进行排序和族群划分并记录全局最好解Px。

Step6：检查收敛。如果收敛条件满足，停止。否则，返回到步骤3。

1.2.2 局部搜索

Step4-1：设im=0，im 是当前族群编号；设iN=0，iN 是当前进化次数。

Step4-2：从当前族群青蛙数n 个中选取q 个可能成为最佳的青蛙构成子群，将子群中青蛙按适应度进行降序排列，记录最佳位置和最差位置Pb，Pw，然后im=im+1。

Step4-3：改善子群中最差青蛙的位置，然后iN=iN+1。

其中下标j 表示第j 次更新，Dj表示最差解的更新步长，Pj'表示最差解更新后的解。

Step4-4：如果最差青蛙的新位置比原来的好，则使用新位置替换原来的，如果比原来的差，则用全局最优Px 替换局部最优Pb 并计算新的适应值，计算后如果新的位置更优，则使用新位置，如果新位置没有旧位置好，在可行域中随机生成一只新的青蛙取代最差的青蛙并计算适应值。

Step4-5：重新计算本子群的最优个体Pb 和最差个体Pw。如果iN＜LS(最大进化数)，则转到步骤4-3。如果im＜m，则转到步骤4-2，否则转到全局搜索过程的步骤5。

2 混合蛙跳算法的研究与改进

虽然混合蛙跳算法在很多优化问题上表现出较好的性能，但是它仍然存在一些不足，它的算法后期收敛速度慢，优化精度不够高，容易陷入局部最优，不同参数的选择对它的表现有很大影响。针对这些问题，许多研究人员从不同的方向对SFLA 算法进行了改进，我将其分为参数优化类改进和混合优化类改进。

2.1 参数优化

为提高算法的寻优收敛性能，文献[5]对算法迭代寻优过程中子种群最差解得更新公式进行改进，提出自适应动态局部搜索机制，如下：

随着全局迭代次数由大变小，算法迭代初始，较大的权重系数有利于算法的全局搜索，随着算法接近尾声，变小的权重系数加快了个体的局部搜索力度，能够发现更多的精英个体。该更新机制有利于引导个体向着全局最优解方向探索，加快全局收敛。

文献[6]提出了正态变异优胜劣汰的混合蛙跳算法，首先在对子群内最差的青蛙个体Pw 执行更新策略时，引入一个服从正态分布的随机扰动项，使新个体产生扰动变异，就可以使青蛙个体进入解空间的其他区域进行搜索，扩大搜索范围，从而有可能发现新的个体最优位置和种群最优位置，提高种群多样性。其次对子群内部少量适应值较差的青蛙个体，在原有的青蛙个体基础上每一维度引入一个服从正态分布的随机变异扰动，各自产生1 个新个体,若优于原个体则对其进行取代否则保持不变。最后对子群内部少量(例如3 个)适应值较差的青蛙个体，让它们进行正态变异,即在原有的青蛙个体基础上每一维度引入一个服从正态分布的随机变异扰动，各自产生1 个新个体，若优于原个体则对其进行取代否则保持不变。

为提高SFLA 的收敛性加快其收敛速度，国内外学者先后做出一些改进，文献[7]将SFLA 与遗传算法结合并使用KNN 和留一法(leave-one-out)交叉验证，文中对11 种分类问题进行了比较，有效地提高了分类问题的精度。文献[8]提出一种新的认知组件，使每个青蛙可以根据个体的思维来调整自身位置，并采用六个基准问题验证了对算法有效性的提升。文献[9]基于离散SFLA 算法，提出了一种新的连续空间优化SFLA 算法，该算法根据模因一致性原则对种群进行划分，通过对多个多峰值连续函数进行寻优的仿真结果表明，改进的SFLA 算法能有效地克服早熟收敛和收敛速度慢的问题，获得较高的优化精度。文献[10]提出了一种新的蛙跳规则，主要是通过模拟蛙跳的感知和动作的不确定性来扩展蛙跳的方向和长度，这种改进拓宽了局部搜索空间，有助于防止早熟收敛，提高了SFLA的性能。文献[11]利用系统稳定性分析方法,提出在SFLA 更新公式中基于比例系数和适应度标准差来自适应调整更新的方法，基于8个标准测试函数验证了该方法对高维问题求解的有效性。文献[12]通过引用精英策略保留最适应的个体，并且引用柯西分布变异算子使算法在后期跳出局部最优，并利用Minkowsk 距离提升了全局最优青蛙优化的机会，使改进的SFLA 具有较快的收敛速度，更高的收敛精度。

2.2 混合优化

为了改进SFLA 易陷入局部最优和早熟收敛的状况，近几年有许多结合其他方法的SFLA 改进算法。文献[13]提出基于GPU 的并行SFLA，结合CUDA 线程，有效降低算法运行时间并提高收敛性。文献[14]将粒子群算法与SFLA 融合，引进一个全局反馈分量有效改进蛙群更新速度和更新位置，获得了很好的优化性能。文献[15]根据粒子群优化和差分进化思想，在青蛙个体进化时，引入上一次移动距离的权重惯性系数，有效改善子群位置更新操作，并结合KMC(传统K 均值聚类)算法，获得更强的寻优能力。

在09年，骆剑平等[16]率先证明青蛙族群状态序列是齐次Markov 链，同时指出SFLA 满足随机搜索算法全局收敛的两个条件，保证全局收敛。之后文献[17]通过增加子群次优解和次劣解的信息交互，结合2-opt 方法增加子群多样性，有效防止算法早熟收敛。文献[18]对混合蛙跳算法权重因子进行了改进,设计了基于Pareto支配能力的SFLA 子族群划分策略，并结合自适应网格密度机制和自适应混沌优化技术，实现了多目标优化问题求解。文献[19]引入了全局共享因子和局部共享因子，并实验给出了算法效率分析，固定全局进化次数和收敛精度后，该算法在单峰值和多峰值函数寻优问题上均具有较高的收敛速度和精度。

3 混合蛙跳算法的应用

近年来，混合蛙跳算法被广泛地应用解决不同领域的实际优化问题，本部分对近几年混合蛙跳算法的一些典型应用进行综述。

SFLA 在文本领域有所建树，许方[20]改进了传统的SFLA,并将其分别与K-means（K 均值）和FCM（模糊C 均值）结合,应用到文本聚类领域中，并且提高了Web 文本聚类的精度。同样在文本聚类方面，尉建兴[21]等将SFLA 与K-means 算法结合，提高了聚类的性能。路永和等[22]在文本特征选择优化中应用SFLA，降低了噪声特征项对文本分类的影响程度，取得更高的分类准确率。

SFLA 在水文方面也有所应用，火久元等[23]提出一种基于SFLA 的水文模型参数估计方法,将该方法应用到新安江模型的参数估计中，与基于遗传算法的水文模型参数估计方法定量对比优势明显。司存友等[24]采用SFLA 对API 模型进行参数优化和智能定线，有效的提高了API 模型预报精度。李恩宽等[25]运用基于SFLA 的投影寻踪模型对黄河流域用水效率进行评价，为黄河流域用水效率管理与节水型社会建设提供参考资料。

针对城市电网问题，储琳琳等[26]提出了无功补偿双层优化模型，通过SFLA 对该模型进行求解，并应用IEEE-33 节点测试有效降低网损，提升电压等。仙锋等[27]将SFLA 结合阈值选择策略，应用在现代电网规划中，但没有实验验证，只有理论。张萍等[28]通过一种结合人工鱼群和SFLA 的矢量匹配法，实现了电压传输函数的有理拟合，以实际大型电力变压器模型开展仿真实验，获得了较好的效果，有一定的工程价值。朱芳[29]基于KPCA 与SFLA 提出一种光伏发电功率预测方法，经算例结果表明，相比传统预测模型新方法预测精度更高。

在其他应用方面，李波[30]在可分裂的TCRO(时间、成本，资源优化)问题上应用SFLA，经过她的案例比较，相比其他群智能算法获得了更好的解决方案。李荣波等[31]在梯度水库优化调度中，应用SFLA 结合混沌技术和全局激励调节策略，在李仙江流域优化调度测试中取得优良结果。陈春朝等[32]运用SFLA 结合人工势场法，在机器人路径规划中有效提升规划效率。张新明等[33]提出一种优化的SFLA，在多阈值图像分割中，经过灰度和彩色图像测试实验，具有良好的优化效率。

4 总结与展望

混合蛙跳算法是一种有效的优化算法，众多研究者不断推成出新，提出了大量的改进方法和实际应用案例。但在不断的深入研究中，该算法依旧有许多不足和值得继续研究的地方。

（1）混合蛙跳算法的基础理论仍需要进一步研究。可以通过借鉴部分其他群智能算法的研究，进一步挖掘算法收敛性，收敛速度方面的研究，以及如何进一步避免早熟，进一步优化参数设置取得更好的结果，在局部和全局信息交换层面也可以深入研究。

（2）混合蛙跳算法本身是基于模因算法与粒子群优化结合而来，可以考虑继续结合其他有效的优化技术进行融合创新，比如结合模拟退火算法跳出局部最优，可以结合蜂群和鸟群算法有效提高优化精度，以及结合混度优化策略加快算法搜索速度[34]，还有其他许多算法可以进一步弥补SFLA 在不同方面的不足。

（3）虽然混合蛙跳算法近几年在文本领域，水文领域，电网领域，图像领域及车间调度等领域已经有了一些应用，但还可以继续探索，我相信在更多的领域比如神经网络，语音情感识别，路径规划，信号重构，三维定位等领域还可以有新的探索，在探索研究应用的同时也会加快SFLA 的研究与发展。

本文系统地展示了SFLA 的基本原理和算法流程，主要介绍了近几年SFLA 的研究进展和应用现状，主要资料均来自与谷歌学术与知网，最后简单说明了一下接下来SFLA 的研究方向和应用领域，希望能为众多接触SFLA 的研究人员给出一点参考。