改进混合蛙跳算法的研究

高建瓴 潘成成 吴建华 陈娅先 王许

摘要：针对传统混合蛙跳算法（SFLA）在优化过程中出现的求解精度不高、收敛速度慢、算法易陷入局部最优的问题，本文经过改变种群个体的位置更新公式，提出一种改进混合蛙跳算法（IS，FLA）。在种群个体位置更新公式中，引入自适应同步因子和惯性权重系数。通过引入自适应同步因子，控制青蛙寻优过程中的移动步长，改进算法的局部搜索范围，保持种群的多样性。通过引入惯性权重系数，加入上一次的移动距离，表示对过去的经验记忆，加快搜索速度。通过对6个测试函数的实验结果表明，改进后的混合蛙跳算法相较于传统混合蛙跳算法具有较好的寻优性能。

关键词：混合蛙跳算法：自适应同步因子：惯性权重系数：局部搜索

中图分类号：TP391文献标识码：A

蛙跳算法（Shumed Fmg Leading Algorithm）是一种启发式算法，通过启发式函数进行启发式搜索，从而找到组合最优问题的解。混合蛙跳算法的运行原理从仿生上来说可以这么认为：在一个池塘，有若干块石头，青蛙可以落在石头上，每块石头上可以获取到的食物数量是不同的，在池塘中有很多只青蛙，也有很多块石头，青蛙间可以交流，这样所有青蛙就都会往自己所在蛙群中所知道的最多食物的方向跳，或往全部青蛙中食物最多的方向跳，最终在池塘中找到最多食物的石头。他结合了以遗传为基础的memetic算法和以社会行为为基础的粒子群优化算法的优点，其显著特点是具有局部搜索与全局信息混合的协同搜索策略，寻优能力强，易于编程实现。

虽然混合蛙跳算法具有概念简单，调整的参数少，全局搜索寻优能力强，易于实现的特点。但是该算法与其他群智能优化算法类似也存在着一些缺点，求解精度不高、收敛速度慢、算法易陷入局部最优的问题。针对这些问题，近年来也有不少的国内外学者对其进行研究改进，张新明等提出了将每次只更新组内最差青蛙的方式改为更新组内所有青蛙的方式，增大了获得优质解的概率，提高可操作性和优化效率。赵红星等提出了对青蛙的觅食机制和更新迭代公式重新定义，青蛙的第一步向组内其它蛙搜索，第二步向组内最优蛙搜索，第三步向全局最优蛙搜索，提高混合蛙跳算法的全局和局部搜索能力。戴月明等提出一种新的协同进化混合蛙跳算法，在局部搜索中对最差蛙的更新引人平均值，扩大青蛙搜索空间;在全局搜索中采取精英群自学进化机制，对精英空间进行精细搜索，提升全局搜索能力。李敏楠等提出通过引人自适应同步因子，改变局部搜索蛙跳规则，从而增加种群的多样性。周林锦提出对初始种群引人Tent混沌来改进，在最差个体更新中引人扰动的柯西因子，提高算法的寻有能力。虽然以上文献在一定程度上提升了算法的优化能力，但随着更多复杂优化问题和严格实时性要求的提出，需要求解精度更高、优化性能更好的混合蛙跳算法，因此，对于混合蛙跳算法的改进仍然有较大空间。本文在传统算法的基础上，通过引人自适应同步算子和惯性权重系数，提出一种新的混合蛙跳算法，改变个体青蛙更新公式，提高算法的求解精度、收敛速度、避免陷人局部最优。

1标准混合蛙跳算法

在混合蛙跳算法中，种群被分为若干个子群（memeplex），每一个子群包括一定数量的青蛙。不同的子群具有不同的文化，分别进行局部搜索。在每个子群中，每只青蛙都有自己的想法，并且受到其他青蛙想法的影响，通过文化进化来发展。这样经过一定的文化进化以及跳跃过程，这些想法思路就在各个子群中传播开来，然后局部搜索和跳跃，直到收敛或满足标准为止。

2改进的混合蛙跳算法

2.1自适应同步因子

在混合蛙跳算法中种群进行局部搜索是算法寻优的核心步骤，在局部搜索过程中，青蛙移动距离的大小对于算法的运算速度和搜索精度十分重要。步长较小有利于精细搜索，但寻优速度比较慢且容易陷人局部最优值：步长较大可使青蛙容易在全局范圍内展开搜索，提高搜索速度，但同时容易在搜索过程中跳过全局最优解所在位置。在标准混合蛙跳算法中，最差解的移动步长是随机更新的，这种随机的跳跃距离使最优解的引导作用无法充分发挥，容易使算法陷入局部极值或跳过全局极值。因此，本文在算法局部搜索时，引人了动态自适应同步因子：当自适应移动因子为增函数时，在更新初始阶段移动距离比较小，对周围进行精细搜索，保持种群的多样性，在更新迭代中后期，移动步长增大，保持算法的全局搜索能力，避免算法陷入局部极值。

3.2结果分析

为了使实验结果更加客观准确，使算法单独运行30次，取30次实验结果的最好值、最差值、平均值作为参照指标进行对比分析，如表2所示。同时为了可以直观的看出两种算法的寻优能力，给出如图2所示各测试函数的进化曲线图。

通过表2可以看出在相同的设置参数下，本文算法在最差值、最好值、平均值都优于标准混合蛙跳算法;在表2中，最好值是运行算法30次结果中最优的一次，最差值为运行算法30次中结果最差的一次，平均值则是对30次结果求平均，表1中的6个测试函数的最优值为0.ISFLA在六个测试函数中无论是最好值、最差值还是平均值都比SF-LA更接近理想值0;且在f（x）函数运行的30次结果中最好值达到了函数的最优值，在f（x）函数的运行结果中每次均能收敛到最优解，而SFLA在各个测试函数中都出现了早熟收敛，在6个测试函数中30次运行结果没有一次是收敛到最优值0.通过表2的对比，可以明显看出ISFLA比SFLA的收敛精度高，寻优效果好。图2是SFLA和ISFLA在6个测试函数中的进化曲线图，纵坐标表示函数最优解，横坐标表示种群的总进化代数，从图2中可以很直观的发现，ISFLA在f（x）到f（x）五个测试函数中进化曲线一开始就体现出比SFLA跟优秀的寻优能力，寻优值都几乎接近函数最优值0.并且收敛速度快，在f（x）函数中虽然ISFLA刚开始的寻优精度没有SFLA好，但是当进化到50代左右时，ISFLA的寻优精度变得比SFLA好并且迅速找到最优解，SFLA则在各个测试函数中都出现了不同程度的早熟收敛，因此本文改进的混合蛙跳算法在求解精度、收敛速度上比标准混合蛙跳算法有了大幅度的提高。这是因为在传统蛙跳算法中加入白适应移动因子和惯性权重系数之后，保持了种群的多样性，扩大搜索范围，提升算法搜索效率以及搜索能力，说明本文对传统混合蛙跳算法的改进是有效的。

4 结论

本文提出的一种基于自适应移动因子、惯性权重系数的混合蛙跳算法，有效地改善算法在优化过程中出现的求解精度不高、收敛速度慢、易陷人局部最优等缺陷。在局部搜索过程中改变蛙跳策略，扩大算法的局部搜索范围，保持种群多样性，通过6个15维测试函数的实验对比分析，表明本文改进的算法较传统混合蛙跳算法寻优精度更高，算法寻优性能更好。