加速收敛的混合蛙跳算法.doc

《加速收敛的混合蛙跳算法.doc》由会员分享，可在线阅读，更多相关《加速收敛的混合蛙跳算法.doc（9页珍藏版）》请在三一办公上搜索。

1、精品论文加速收敛的混合蛙跳算法袁亚杰，马英红，郑自然（ 山东师范大学管理科学与工程学院，济南 250014；）5摘要：混合蛙跳算法在求解函数优化问题时效果较差，搜索速度和收敛精度差强人意，为了 提高混合蛙跳算法的搜索能力，在尊重算法框架的基础上，从全局探索性、局部开发性、降低群体规模等方面提出了改进方案，验证了改进策略的有效性，并结合以上改进提出了一种 性能优秀的混合蛙跳算法 F_SFLA，对典型的 10 个基准函数进行仿真实验，F_SFLA 都可以很快收敛到全局最优解，并能够获得较好的开发精度，表现出高效的收敛能力和广泛的适用性。10关键词：混合蛙跳算法；加速收敛；函数优化；中图分类号：TP

2、301.6Shuffled frog-leaping algorithm with fast convergenceYUAN Yajie, Ma Yinghong, Zheng Ziran15( School of Management Science and Engineering, Shandong Normal University, Jinan 250014;) Abstract: Shuffled frog-leaping algorithm (SFLA) and its passing modified versions are not good at solving functi

3、on optimization problems. In order to improve the convergency of SFLA , some ideas, which make SFLA a more global exploration, a deeper exploitation, or a smaller population size, are proposed on the basis of its framework and principle. An outstanding version named20F_SFLA, combining these new idea

4、s which prove to be effective, gets exciting solutions for ten typical benchmark functions. The born boy surprises us, because we can find global minima rather than local ones and then work out satisfactory and accurate values relying on it. Compared with old versions, F_SFLA has faster convergence

5、and better robustness.Key words: Shuffled Frog-Leaping Algorithm (SFLA);global convergence;function optimization;250引言混合蛙跳算法（Shuffled Frog-Leaping Algorithm，SFLA），又称混洗蛙跳算法，从框架 上看是一种 Memetic 算法，是 Eusuff 等人1于 2003 年提出的一种模拟青蛙觅食的群体智能 算法，首先应用于水资源分配，目前已在组合优化、函数优化等多领域成功应用。基本的蛙30跳算法求解高维函数优化问题的效果较差，在群体规模、运行时

6、间和收敛精度上难与微粒群 算法等其他成熟的智能算法相比。目前国内外学者虽然已经提出了多种改进方法，但是性能提升有限。Elbeltagi 等人2对 GA/Memetic/PSO/ACO/ SFLA 五种算法进行对比，用 Griewank 和 Schaffers F7 两个函数的 实验证明了蛙跳算法具有一定的优势，但是终止条件的设置和测试函数的广泛性都不够。贺35毅朝等3借鉴微粒群算法的速度更新公式和差分演化的变异操作 DE/best/1/bin 模式，取消了 重新排序分组的步骤，是目前效果较好的一种改进，但是较大改变了算法框架和本质。文献 4借鉴微粒群算法中的速度更新模式，引入惯性权重。赵鹏军等

7、人5将生物学中的吸引排斥 思想引入，维持了子群的多样性。骆剑平等6将极值动力学优化 EO 算法引入，提升了局部 搜索能力。其他改进大部分是把蛙跳步长的更新与差分进化 DE 结合进行的，在函数优化领40域没有很大进步。作者简介：袁亚杰(1986-)，男，硕士研究生，主要研究方向：群体智能通信联系人：马英红(1971-)，女，教授，博士生导师，主要研究方向：管理决策、组合最优化、复杂网络 等. E-mail: yinghongma71- 9 -本文经过大量实验研究，提出了几种改进策略，在高维函数优化和低维函数优化中都获得更好的结果，极大得降低了群体规模，提高了收敛速度，增加了算法运行的稳定性。广泛

8、 的函数测试也验证了几种新算法的适用性和鲁棒性。1混合蛙跳算法的理论分析45青蛙种群由 m 个规模为 n 的子群组成，个体总数 N=m*n，种群进化代数 MaxGen，子 群进化代数 Ne，一般令 Ne=n。搜索区域的上界 UB 和下界 LB，个体变量的维度 Dim，单 维度允许的最大步长 Dmax，在求解搜索区域对称的函数时 Dmax=c*UB，参数 c 称为最大步长 系数，用来防止搜索出现振荡。1.1 排序分组的思想50每一代进化完成之后，所有青蛙按适应度从高到底排序，然后重新分组，分组策略为： 适应度排序号为 i 的青蛙进入子群 k=mod(i,m)，前 m 只青蛙依次是 m 个子群的最

9、优个体 pB， 后 m 只青蛙依次是 m 个子群的最差个体 pW，第一只青蛙是全局最优个体 pG。这就是混合 蛙跳算法中的混洗。1.2 蛙跳的策略55小组内只让最差个体 pW 进行更新，每个小组允许更新的次数为 Ne，青蛙个体采取贪 婪选择策略，用的是位置与步长的概念，如公式(1)(2)所示。每只青蛙最多可以有 3 跳：第1 跳向小组最优 pB 学习，如果没取得进步，第 2 跳向全局最优 pG 学习，如果仍然没进步， 第 3 跳随机初始化产生新解，见式(3)。前 2 跳是为了收敛，第 3 跳是为了保持种群多样性 跳出局部搜索停滞。小组内每次更新之后需要重新计算 pB 和 pW，这样保证了小组内

10、并不60是只有一个个体能更新，也不会让小组内大部分个体因随机初始化导致进化退步。D = rand (1, Dim) * (p B- p W)(1)newpW = old pW + D j (D max D j -Dmax )(2)new_pW = LB + rand (1, Dim) * (UB - LB)(3)1.3 进化流程65与其他的智能优化算法一样，混合蛙跳算法从框架上也是基于迭代进化的，也具有交叉 学习、变异、选择的思想。其本质上属于 Memetic 算法，下面图 1 是算法流程图。图 1 混合蛙跳算法的流程2改进策略702.1 全局探索版的蛙跳算法 GE_SFLA将青蛙的第 2 跳

11、向全局最优 pG 学习改为随机选择 m 个组中的任意一个小组最优 pB 进 行学习，这样各小组的经验能够能更加均匀更加广泛地得到交流。每代进化后重新排序分组 虽然也能起到交流作用，但是算法整体上偏重于星式搜索，改进之后则更像网式搜索，更不 易陷入局部停滞及更好地保持群体多样性。第 3.2 节的实验结果也说明了这一点。表明改进75算法具有更好的全局探索(global exploring)能力。2.2 局部开发版的蛙跳算法 LE_SFLAElbeltagi 等人7在蛙跳的前 2 跳的步长更新公式中加了一个参数 C，称为步长加速系数, 见式(4)，并以 Griewank 和 Schaffers F7

12、 两个函数的实验为例，研究了系数 C 的建议取值范 围 1.3C10*2020*1040*5。由于实验中 混合蛙跳算法用到的种群一般较大，以上设置可以兼顾求解多种函数的稳定性进行有弹性的 选取。130图 2 算法 LE_SFLA 的局部开发能力图 3 群体分组对算法 LE_SFLA 开发能力的影响1351403.4 验证 F_SFLA 的有效性及低维函数测试本文算法 F_SFLA 指的是前 100 代不进行混洗操作，前两跳的加速系数C=1.6+2*rand-1，第 3 跳采用差分变异 DE/rand/1/bin，采用了前期多种群局部开发后期混洗 学习策略的一种改进算法。从文献35的实验结果可以

13、明显看出，单纯依靠蛙跳算法及其 改进，在求解高维多模态函数时很容易陷入局部最优，下面研究改进算法在处理低维度函数 时的效果。新算法 F_SFLA 与 LE_SFLA 的主要参数设置同 3.2 节，对本文的 10 个基准函数 进行测试，维度为 2，运行 10 次取最优值、平均值、标准差、时间见表 3 所示，取 10 次进 化曲线的平均值见图 4 和图 5 所示。表 3 中的 3 种算法都用了 200 只青蛙。表 3 本文算法 F_SFLA/LE_SFLA 与基本蛙跳算法 SFLA 对 10 个函数的测试结果对比函数算法最优值平均值标准差F1SFLALE_SFLA3.44243e-31001.46

14、581E-7604.63529E-760F_SFLA000SFLA0(2 次)9.18738E-152.9E-14F2LE_SFLA0(9 次)6.16298E-331.56453E-32F_SFLA000SFLA000F3LE_SFLA000F_SFLA000F4F5F6F7F8F9F10SFLA000LE_SFLA0(8 次)0.001479210.00311844F_SFLA000SFLA-8.88178E-16-8.88178E-160LE_SFLA-8.88178E-16-8.88178E-160F_SFLA-8.88178E-16-8.88178E-160SFLA0(9 次)1.9

15、8E-076.27E-07LE_SFLA0(9 次)4.98E-061.58E-05F_SFLA000SFLA1.20996E-671.88411E-305.95806E-30LE_SFLA000F_SFLA03.00699E-814.4271E-81SFLA1.37584E-1531.19904E-373.79169E-37LE_SFLA2.68869E-1941.36223E-1920F_SFLA2.07694E-1621.10323E-1601.93992E-160SFLA1.79767E-1679.54756E-183.0192E-17LE_SFLA3.55348E-2083.5786

16、6E-1920F_SFLA1.48467E-3208.15378E-3180SFLA2.74341E-1431.13425E-163.58681E-16LE_SFLA9.85835E-1988.70848E-1940F_SFLA2.42909E-1661.73212E-1640145150从表 3 和图 4 图 5 可以看出，基本的蛙跳算法 SFLA 虽然求解 2 维函数也可以获得较好的求解精度，但是很不稳定，即使是对单模态函数 F1 在精度开发上也可能停滞，最优解与 平均解的差别较大；令 C=1.6 的 LE_SFLA 算法具有最强的开发速度，但是在求解多模态函 数时容易陷入局部最优；综合所

17、有函数的实验来看，算法 F_SFLA 最为稳定，不仅对收敛精 度的开发可以一直不停直至计算机承受的最多位数，而且不易陷入局部最优，尤其在 F2/F4/F6/F9 上表现优秀。图 4 3 种算法求解 2 维函数 F1-F6 的进化曲线图 5 3 种算法求解 2 维函数 F7-F10 的进化曲线1551603.5 验证 F_SFLA 和 LE_SFLA 的小群体性一直以来，大量文献在研究混合蛙跳算法时一般用 200 只青蛙分 20 组，需要较大的群 体规模并造成较大的计算量是其劣势之一，但是实验中发现，本文的改进算法求解一般的 2 维函数来讲用 20 只青蛙分 5 组的群体规模就可以满足要求。对函

18、数 F4 和 F6 之外的其他 8 个函数做实验，运行 10 次得表 4，其中对 F3 我们用 LE_SFLA 与 SFLA 对比，对其他的 7 个函数用 F_SFLA 与 SFLA 对比。表 4 小群体的本文算法与基本蛙跳算法 SFLA 对比算法群体设置最优值平均值标准差SFLAF_SFLA SFLA F_SFLA10*105*410*105*53.69769E-1763.93954E-2738.54981E-2407.43777E-325.09429E-2591.15E-0702.35203E-3102.53E-070SFLA5*40(1 次)0.03211370.0848571LE_SF

19、LASFLA5*410*100-8.88178E-16(6 次)02.91E-0709.21E-07F_SFLASFLA F_SFLASFLA F_SFLA SFLAF_SFLA SFLA F_SFLA5*410*105*410*105*410*105*410*105*4-8.88178E-163.80433E-253.4481E-671.72319E-1041.93269E-1317.76651E-763.39894E-2502.0164E-544.51247E-137-8.88178E-162.67E-092.62729E-642.06E-093.94066E-1245.49749E-17

20、3.78446E-2133.43E-134.86734E-13305.78E-096.56024E-646.5E-091.10934E-1231.59319E-1609.71E-131.22021E-132函数F1F2F3F5F7F8F9F10从表 4 可以看出，本文算法 F_SFLA 在群体规模极小的情况下，仍然有很好的收敛精度， 而且稳定性远胜过群体规模为 100 的基本蛙跳算法 SFLA，对比表 3 和表 4 可以看出群体规 模的大小对本文算法 F_SFLA 开发精度的能力影响不大，增大群体规模主要是为了在求解函165170175180185数 F4/F6 这样搜索区域较大的多模态函数时

21、避免陷入局部最优。而基本的蛙跳算法 SFLA 对群体规模比较敏感，在求解 2 维函数时一般需要 100 只青蛙以上。3.6 参数设置和鲁棒性对本文算法 F_SFLA 而言，青蛙群体的分组不一定是 20*10，青蛙总数不变的前提下可 以减小分组数直至 5*40；组内迭代次数 Ne 一般等于每组的青蛙数 n，多几次或少几次基本 没影响；最大步长系数 c 默认设为 0.2-0.5 之间，限制步长不会偶尔过大即可；步长加速系 数 C 一般来讲在 1.55-1.65 之间均可，和群体分组、问题复杂度都有关系，默认为 1.6；进化代数 MaxGen 在一般设为 500 代已经能满足要求，解更复杂的问题可适

22、当增加；群体规模 N， 大部分文献都是以 200 只青蛙来讨论问题的，在求解 2 维函数时，本文算法用 20 只青蛙已 能满足要求。由此可以看出，本文算法 F_SFLA 具有良好的鲁棒性。4结束语混合蛙跳算法具有较好的全局性，但是需要较大的种群规模来保证其稳定性，导致求解 函数优化问题时效果较差，花费时间较多，收敛性不够，尤其在优化高维函数时很难搜索到 质量高的解。本文分析了算法的理论，在不改变算法框架和原理的前提下，提出了几点有建 设性的改进策略，进一步提高了 SFLA 的全局探索性，极大地改善了 SFLA 的局部开发能力 并降低了群体规模。提出的新算法 F_SFLA 在对 10 个经典测试

23、函数多次寻优时均收敛到全 局最优解，而且收敛速度快、精度高、鲁棒性强，是一种优秀的算法。从精度开发能力和种 群规模这两个方面表现出 SFLA 在函数优化领域不弱于其他成熟的智能算法的能力和潜力。 接下来应继续研究在处理高维度函数多模态等更复杂问题时本文算法的调整策略。参考文献 (References)1901952001 Eusuff, M.M. and Lansey, K.E. Optimization of Water Distribution Network Design Using the Shuffled FrogLeaping AlgorithmJ. Water Resources

24、 Planning and Management, 2003,129(3): 210-225.2 Emad Elbeltagi, Tarek Hegazy, Donald Grierson. Comparison among five evolutionary-based optimization algorithmsJ. Advanced Engineering Informatics, 2005, 19(1): 43-53.3 贺毅 朝 , 曲文龙 , 许冀 伟 . 一种改 进的混 合蛙 跳算法 及其 收敛性 分析 J. 计算机 工 程与应 用,2011,47(22):37-40.4 Zh

25、en Ziyang,Wang Daobo,Liu Yuanyuan. Improved shuffled frog leaping algorithm for continuous optimization problemC. Trondheim, Norway: IEEE Congress Evolutionary Computation, 2009.5 赵鹏军,刘三阳. 求解复杂函数优化问题的混合蛙跳算法J. 计算机应用研究, 2009, 26(7):2435-2437.6 骆剑平 , 陈泯 融 . 混 合蛙 跳算法 及其 改进算 法的 运动轨 迹及 收敛性 分析 J. 信号 处理 , 2

26、010,26(9):1428-1433.7 Emad Elbeltagi, Tarek Hegazy, Donald Grierson. A modified shuffled frog-leaping optimization algorithm:applications to project managementJ. Structure and Infrastructure Engineering, 2007, 3(1):53-60.8 Riccardo Poli, James Kennedy, Tim Blackwell. Particle swarm optimization:An overviewJ. SwarmIntelligence, 2007,1(1):33-57.