第10卷第3期 智能系统学报 Vol.10 No.3 2015年6月 CAAI Transactions on Intelligent Systems Jun.2015 D0:10.3969/j.issn.1673-4785.201405070 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150611.0902.001.html 广义中心混合蛙跳算法 赵嘉，吕莉，樊棠怀 (南昌工程学院信息工程学院，江西南昌330099) 摘要：为解决标准混合蛙跳算法族群之间信息共享能力差的问题，加强族群内蛙的学习能力，利用各族群最优蛙 位置的平均中心，构造一个与各族群最优蛙都有关联的虚拟广义中心蛙，提出广义中心混合蛙跳算法。该算法在进 化过程中，首先蛙群最优蛙在原有位置及广义中心蛙的位置上进行“贪梦”选择，选择最好位置作为新的族群最优蛙 位置：其次将广义中心蛙的优势运用于蛙跳规则中，在标准混合蛙跳算法的蛙跳规则中加入族群最差蛙向广义中心 蛙学习的能力。将本文算法与不同维度下的标准混合蛙跳算法及新近提出的知名群智能算法进行比较，实验结果 表明，本文算法在解的精度、收敛速度及解的稳定性等方面具有更优的性能。 关键词：蛙跳算法；混合蛙跳算法；广义中心：蛙跳规则：群智能算法 中图分类号：TP301文献标志码：A文章编号：1673-4785(2015)03-0414-08 中文引用格式：赵嘉，吕莉，樊棠怀.广义中心混合蛙跳算法[J].智能系统学报，2015,10(3)：414-421. 英文引用格式：ZHAO Jia,LYU Li,FAN Tanghuai..Shuffled frog-leaping algorithm based on the general center[J].CAAI Trans- actions on Intelligent Systems,2015,10(3):414-421. Shuffled frog-leaping algorithm based on the general center ZHAO Jia,LYU Li,FAN Tanghuai (School of Information Engineering,Nanchang Institute of Technology,Nanchang 330099,China) Abstract:In this paper,a shuffled frog-leaping algorithm based on general center (GC-SFLA)is proposed to solve the problem of weak information sharing between memeplexes in the shuffled frog leaping algorithm(SFLA)to en- hance the learning ability and use the average center of optimal frog.The proposed GC-SFLA generates a virtual general center frog from the optimal frog of each memeplex.Firstly,the optimal frog selects the best location among the original location and general center greedily as new location of new memeplex.After that,the advantage of gen- eral center frog is applied to the frog-leaping rule,which enable the worst frog to learn from the general center frog. Experiments are conducted on a set of swarm intelligence algorithms to verify that the new approach outperforms SF- LA in different dimensions.The experiment results present promising performance of the GC-SFLA on convergence velocity,precision and stability of solution. Keywords:frog-leaping algorithm;shuffled frog leaping algorithm (SFLA);general center;frog leaping rule; swarm intelligence algorithms 混合蛙跳算法(shuffled frog leaping algorithm, SLA))是一种基于群体智能的亚启发式协同搜索 计算技术，最早由M.M.Eusuff和K.E.Lansey于 收稿日期：2014-06-03.网络出版日期：2015-06-11. 基金项目：国家自然科学基金资助项目(61261039,61263029)：江西 2000年提出。它结合了基于基因进化的模因演算 省自然科学基金资助项目(20132BAB211031):江西省科 法(memetic algorithm,MA)[2)和基于群体行为的粒 技厅科技支撑项目(20142BBC70034):南昌市科技计划项 目(2013HZCG006,2013HZCG011,2014HZZC008). 子群优化算法(particle swarm optimization,PSO)[) 通信作者：赵嘉.E-mail:zhaojia925@163.com
第 １０ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．３ ２０１５ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０５０７０ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０６１１．０９０２．００１．ｈｔｍｌ 广义中心混合蛙跳算法 赵嘉，吕莉，樊棠怀 （南昌工程学院 信息工程学院，江西 南昌 ３３００９９） 摘 要：为解决标准混合蛙跳算法族群之间信息共享能力差的问题，加强族群内蛙的学习能力，利用各族群最优蛙 位置的平均中心，构造一个与各族群最优蛙都有关联的虚拟广义中心蛙，提出广义中心混合蛙跳算法。 该算法在进 化过程中，首先蛙群最优蛙在原有位置及广义中心蛙的位置上进行“贪婪”选择，选择最好位置作为新的族群最优蛙 位置；其次将广义中心蛙的优势运用于蛙跳规则中，在标准混合蛙跳算法的蛙跳规则中加入族群最差蛙向广义中心 蛙学习的能力。 将本文算法与不同维度下的标准混合蛙跳算法及新近提出的知名群智能算法进行比较，实验结果 表明，本文算法在解的精度、收敛速度及解的稳定性等方面具有更优的性能。 关键词：蛙跳算法；混合蛙跳算法；广义中心；蛙跳规则；群智能算法 中图分类号：ＴＰ３０１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０３⁃０４１４⁃０８ 中文引用格式：赵嘉，吕莉，樊棠怀． 广义中心混合蛙跳算法［Ｊ］． 智能系统学报， ２０１５， １０（３）： ４１４⁃４２１． 英文引用格式：ＺＨＡＯ Ｊｉａ， ＬＹＵ Ｌｉ， ＦＡＮ Ｔａｎｇｈｕａｉ． Ｓｈｕｆｆｌｅｄ ｆｒｏｇ⁃ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｇｅｎｅｒａｌ ｃｅｎｔｅｒ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓ⁃ ａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（３）： ４１４⁃４２１． Ｓｈｕｆｆｌｅｄ ｆｒｏｇ⁃ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｇｅｎｅｒａｌ ｃｅｎｔｅｒ ＺＨＡＯ Ｊｉａ， ＬＹＵ Ｌｉ， ＦＡＮ Ｔａｎｇｈｕａｉ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｎａｎｃｈａｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｃｈａｎｇ ３３００９９， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ａ ｓｈｕｆｆｌｅｄ ｆｒｏｇ⁃ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｇｅｎｅｒａｌ ｃｅｎｔｅｒ （ＧＣ⁃ＳＦＬＡ） ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｗｅａｋ ｉｎｆｏｒｍａｔｉｏｎ ｓｈａｒｉｎｇ ｂｅｔｗｅｅｎ ｍｅｍｅｐｌｅｘｅｓ ｉｎ ｔｈｅ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ （ＳＦＬＡ） ｔｏ ｅｎ⁃ ｈａｎｃｅ ｔｈｅ ｌｅａｒｎｉｎｇ ａｂｉｌｉｔｙ ａｎｄ ｕｓｅ ｔｈｅ ａｖｅｒａｇｅ ｃｅｎｔｅｒ ｏｆ ｏｐｔｉｍａｌ ｆｒｏｇ． Ｔｈｅ ｐｒｏｐｏｓｅｄ ＧＣ⁃ＳＦＬＡ ｇｅｎｅｒａｔｅｓ ａ ｖｉｒｔｕａｌ ｇｅｎｅｒａｌ ｃｅｎｔｅｒ ｆｒｏｇ ｆｒｏｍ ｔｈｅ ｏｐｔｉｍａｌ ｆｒｏｇ ｏｆ ｅａｃｈ ｍｅｍｅｐｌｅｘ． Ｆｉｒｓｔｌｙ， ｔｈｅ ｏｐｔｉｍａｌ ｆｒｏｇ ｓｅｌｅｃｔｓ ｔｈｅ ｂｅｓｔ ｌｏｃａｔｉｏｎ ａｍｏｎｇ ｔｈｅ ｏｒｉｇｉｎａｌ ｌｏｃａｔｉｏｎ ａｎｄ ｇｅｎｅｒａｌ ｃｅｎｔｅｒ ｇｒｅｅｄｉｌｙ ａｓ ｎｅｗ ｌｏｃａｔｉｏｎ ｏｆ ｎｅｗ ｍｅｍｅｐｌｅｘ． Ａｆｔｅｒ ｔｈａｔ， ｔｈｅ ａｄｖａｎｔａｇｅ ｏｆ ｇｅｎ⁃ ｅｒａｌ ｃｅｎｔｅｒ ｆｒｏｇ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｆｒｏｇ⁃ｌｅａｐｉｎｇ ｒｕｌｅ， ｗｈｉｃｈ ｅｎａｂｌｅ ｔｈｅ ｗｏｒｓｔ ｆｒｏｇ ｔｏ ｌｅａｒｎ ｆｒｏｍ ｔｈｅ ｇｅｎｅｒａｌ ｃｅｎｔｅｒ ｆｒｏｇ． Ｅｘｐｅｒｉｍｅｎｔｓ ａｒｅ ｃｏｎｄｕｃｔｅｄ ｏｎ ａ ｓｅｔ ｏｆ ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ ａｌｇｏｒｉｔｈｍｓ ｔｏ ｖｅｒｉｆｙ ｔｈａｔ ｔｈｅ ｎｅｗ ａｐｐｒｏａｃｈ ｏｕｔｐｅｒｆｏｒｍｓ ＳＦ⁃ ＬＡ ｉｎ ｄｉｆｆｅｒｅｎｔ ｄｉｍｅｎｓｉｏｎｓ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ｐｒｅｓｅｎｔ ｐｒｏｍｉｓｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ＧＣ⁃ＳＦＬＡ ｏｎ ｃｏｎｖｅｒｇｅｎｃｅ ｖｅｌｏｃｉｔｙ， ｐｒｅｃｉｓｉｏｎ ａｎｄ ｓｔａｂｉｌｉｔｙ ｏｆ ｓｏｌｕｔｉｏｎ． Ｋｅｙｗｏｒｄｓ： ｆｒｏｇ⁃ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ； ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ （ ＳＦＬＡ）； ｇｅｎｅｒａｌ ｃｅｎｔｅｒ； ｆｒｏｇ ｌｅａｐｉｎｇ ｒｕｌｅ； ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ ａｌｇｏｒｉｔｈｍｓ 收稿日期：２０１４⁃０６⁃０３． 网络出版日期：２０１５⁃０６⁃１１． 基金项目：国家自然科学基金资助项目（ ６１２６１０３９，６１２６３０２９）；江西 省自然科学基金资助项目（ ２０１３２ＢＡＢ２１１０３１）；江西省科 技厅科技支撑项目（２０１４２ＢＢＧ７００３４）；南昌市科技计划项 目（２０１３ＨＺＣＧ００６，２０１３ＨＺＣＧ０１１，２０１４ＨＺＺＣ００８）． 通信作者：赵嘉． Ｅ⁃ｍａｉｌ： ｚｈａｏｊｉａ９２５＠ １６３．ｃｏｍ． 混合蛙跳算法（ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ， ＳＦＬＡ） ［１］是一种基于群体智能的亚启发式协同搜索 计算技术，最早由 Ｍ． Ｍ． Ｅｕｓｕｆｆ 和 Ｋ． Ｅ． Ｌａｎｓｅｙ 于 ２０００ 年提出。 它结合了基于基因进化的模因演算 法（ｍｅｍｅｔｉｃ ａｌｇｏｒｉｔｈｍ， ＭＡ） ［２］和基于群体行为的粒 子群优化算法（ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＳＯ） ［３］
第3期 赵嘉，等：广义中心混合蛙跳算法 415· 的优点[)，具有概念简单、参数设置少、计算速度 将蛙群分成m个族群，每个族群包含n只青蛙，满 快、全局寻优能力强、易于实现等特点[)，并在无线 足关系F=m×n。族群的划分规则是：第1只青蛙 传感器网络覆盖优化、函数优化)、经济负荷分 进入第1个族群，第2只青蛙进入第2个族群，第m 配)]、生产调度组合优化]等领域取得较好应用， 只青蛙进入第m个族群，第m+1只青蛙又进入第1 正成为智能计算领域的研究热点。 个族群，第m+2只青蛙进人第2个族群，以此类 与其他群智能算法相似，混合蛙跳算法也存在 推，直至所有青蛙划分完毕。第k个族群中最好的 易陷入局部极值、进化后期收敛速度慢、计算精度低 一个青蛙，记为，相应地可以得到一个最差的青 等缺点。为此，研究人员在不断深入研究和分析后， 蛙，记为P。 提出了多种不同思想的改进混合蛙跳算法，比较有 为了获得更多的食物，较差的蛙受较好蛙的影 代表性的有罗雪晖等[o]在混合蛙跳算法中加入调 响而跳向较好的蛙。根据上述初始蛙跳规则，第 整序思想设计了局部搜索策略，并在全局信息交换 个青蛙族群中最差蛙的更新公式为： 中加入变异算法，提出一种改进的混合蛙跳算法并 D=r×(Ph-P) (1)》 应用于求解TSP问题：T.Niknam等[]利用混沌局 Pr.=P+Dk,-Das≤D:≤Dx(2) 部搜索策略提出改进的混沌混合蛙跳算法；借鉴分 式中：k表示是第几个族群，且1≤k≤m;r为[0， 子动力学模拟的思想，张潇丹[]提出基于分子动力 1]的随机数：D,为第k个族群最差蛙移动的步长： 学模拟的改进混合蛙跳算法：Sun等[)提出一种基 P"-"为第k个族群最差蛙更新后新位置；D为蛙 于粒子共享的粒子群蛙跳混合优化算法，算法利用 的最大跳动步长。 粒子群具有良好全局搜索性能与混合蛙跳算法具有 若执行更新策略(1)和(2)后，P"对应的适 较强局部搜索能力的特点，克服了群体智能算法后 应值优于P对应的适应值，则用P"取代P;否 期易陷入局部最优及“早熟”收敛的缺点。这些算 则采用P。代替式(1)中的P,重新更新P。若 法都在标准SLA基础上进行不同程度的改进，但 重新执行更新后，P"对应的适应值优于P对应 其改进也不同程度增加了算法的复杂性。 的适应值，则用P"取代P;否则采用式(3)随机 在SFLA中，青蛙的跳跃主要经历局部搜索和 产生一个新的蛙代替P。 全局信息交换2个阶段，局部搜索使模因信息在局 Pg=r×(0ns-0in）+0nma (3) 部个体间进行传递，全局信息交换使得局部间的模 式中：O和0m分别表示算法搜索范围的最大值 因信息得到交换，这在很大程度上决定了算法的收 和最小值。 敛速度与解的质量。但青蛙在进化过程中，族群中 重复以上的更新操作，直至满足事先设定的族 的最差青蛙只向自身蛙群和最优青蛙所在蛙群的最 群内的算法迭代次数。当所有族群的局部深度搜索 好青蛙学习，族群之间的相互学习不够、共享能力不 完成以后，进行全局信息交换。局部深度搜索和全 强。为此，利用各族群最优蛙的优势，构造广义中心 局信息交换两阶段交替进行，直到满足相应的结束 青蛙，并改进蛙群的进化策略，使蛙群在原有学习策 条件。 略的基础上，增加向广义中心青蛙学习的能力，提出 广义中心混合蛙跳算法(shuffled frog leaping algo- 2广义中心混合蛙跳算法 rithm based on genernal center,GC-SFLA)。通过对 2.1广义中心策略 8个标准测试函数的实验仿真，将提出的广义中心 在群智能算法中，随着进化的进行，全局极值将 混合蛙跳算法与标准混合蛙跳算法及新近提出的知 会越来越接近最优解。搜索结束后，全局极值将位 名群智能算法比较算法收敛速度和全局寻优能力。 于最优解的邻近区域。与此同时，由于群智能算法 1 混合蛙跳算法 的随机性，每个个体也分布在全局极值的邻近区域。 为了改善全局极值，使其更快向最优解靠近[，iu 混合蛙跳算法是一种基于群体智能的生物进化 等]引入中心粒子。中心粒子由群体的中心位置 算法。该算法模拟湿地中一群青蛙按族群划分的思 形成，伴随于整个搜索过程，除不具有速度外，该粒 想进行觅食。在算法执行时，首先产生F只青蛙组 子具有与其他普通粒子相同的所有性质。其产生的 成蛙群，对于N维优化问题，群体中第i只青蛙表示 方式如式(4)所示： 为X,=(x,x,,x),将蛙群内的青蛙个体按照 适应值进行降序排列，找到全局最好青蛙（解）P。。 x (4) i=1
的优点［４］ ，具有概念简单、参数设置少、计算速度 快、全局寻优能力强、易于实现等特点［５］ ，并在无线 传感器网络覆盖优化［６］ 、函数优化［７］ 、经济负荷分 配［８］ 、生产调度组合优化［９］ 等领域取得较好应用， 正成为智能计算领域的研究热点。 与其他群智能算法相似，混合蛙跳算法也存在 易陷入局部极值、进化后期收敛速度慢、计算精度低 等缺点。 为此，研究人员在不断深入研究和分析后， 提出了多种不同思想的改进混合蛙跳算法，比较有 代表性的有罗雪晖等［１０］ 在混合蛙跳算法中加入调 整序思想设计了局部搜索策略，并在全局信息交换 中加入变异算法，提出一种改进的混合蛙跳算法并 应用于求解 ＴＳＰ 问题；Ｔ． Ｎｉｋｎａｍ 等［１１］ 利用混沌局 部搜索策略提出改进的混沌混合蛙跳算法；借鉴分 子动力学模拟的思想，张潇丹［１２］ 提出基于分子动力 学模拟的改进混合蛙跳算法；Ｓｕｎ 等［１３］ 提出一种基 于粒子共享的粒子群蛙跳混合优化算法，算法利用 粒子群具有良好全局搜索性能与混合蛙跳算法具有 较强局部搜索能力的特点，克服了群体智能算法后 期易陷入局部最优及“早熟”收敛的缺点。 这些算 法都在标准 ＳＦＬＡ 基础上进行不同程度的改进，但 其改进也不同程度增加了算法的复杂性。 在 ＳＦＬＡ 中，青蛙的跳跃主要经历局部搜索和 全局信息交换 ２ 个阶段，局部搜索使模因信息在局 部个体间进行传递，全局信息交换使得局部间的模 因信息得到交换，这在很大程度上决定了算法的收 敛速度与解的质量。 但青蛙在进化过程中，族群中 的最差青蛙只向自身蛙群和最优青蛙所在蛙群的最 好青蛙学习，族群之间的相互学习不够、共享能力不 强。 为此，利用各族群最优蛙的优势，构造广义中心 青蛙，并改进蛙群的进化策略，使蛙群在原有学习策 略的基础上，增加向广义中心青蛙学习的能力，提出 广义中心混合蛙跳算法（ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｇｅｎｅｒｎａｌ ｃｅｎｔｅｒ， ＧＣ⁃ＳＦＬＡ）。 通过对 ８ 个标准测试函数的实验仿真，将提出的广义中心 混合蛙跳算法与标准混合蛙跳算法及新近提出的知 名群智能算法比较算法收敛速度和全局寻优能力。 １ 混合蛙跳算法 混合蛙跳算法是一种基于群体智能的生物进化 算法。 该算法模拟湿地中一群青蛙按族群划分的思 想进行觅食。 在算法执行时，首先产生 Ｆ 只青蛙组 成蛙群，对于 Ｎ 维优化问题，群体中第 ｉ 只青蛙表示 为 Ｘｉ ＝ （ｘ １ ｉ ，ｘ ２ ｉ ，．．．，ｘ Ｎ ｉ ） ，将蛙群内的青蛙个体按照 适应值进行降序排列，找到全局最好青蛙（解） Ｐｇ 。 将蛙群分成 ｍ 个族群，每个族群包含 ｎ 只青蛙，满 足关系 Ｆ ＝ ｍ × ｎ 。 族群的划分规则是：第 １ 只青蛙 进入第 １ 个族群，第 ２ 只青蛙进入第 ２ 个族群，第 ｍ 只青蛙进入第 ｍ 个族群，第 ｍ ＋ １ 只青蛙又进入第 １ 个族群，第 ｍ ＋ ２ 只青蛙进入第 ２ 个族群，以此类 推，直至所有青蛙划分完毕。 第 ｋ 个族群中最好的 一个青蛙，记为 Ｐ ｂ ｋ ，相应地可以得到一个最差的青 蛙，记为 Ｐ ｗ ｋ 。 为了获得更多的食物，较差的蛙受较好蛙的影 响而跳向较好的蛙。 根据上述初始蛙跳规则，第 ｋ 个青蛙族群中最差蛙的更新公式为： Ｄｋ ＝ ｒ × （Ｐ ｂ ｋ － Ｐ ｗ ｋ ） （１） Ｐ ｎｅｗ＿ｗ ｋ ＝ Ｐ ｗ ｋ ＋ Ｄｋ， － Ｄｍａｘ ≤ Ｄｉ ≤ Ｄｍａｘ （２） 式中： ｋ 表示是第几个族群，且 １ ≤ ｋ ≤ ｍ ； ｒ 为［０， １］的随机数； Ｄｋ 为第 ｋ 个族群最差蛙移动的步长； Ｐ ｎｅｗ＿ｗ ｋ 为第 ｋ 个族群最差蛙更新后新位置； Ｄｍａｘ 为蛙 的最大跳动步长。 若执行更新策略（１）和（２）后， Ｐ ｎｅｗ＿ｗ ｋ 对应的适 应值优于 Ｐ ｗ ｋ 对应的适应值，则用 Ｐ ｎｅｗ＿ｗ ｋ 取代 Ｐ ｗ ｋ ；否 则采用 Ｐｇ 代替式（１）中的 Ｐ ｂ ｋ ，重新更新 Ｐ ｎｅｗ＿ｗ ｋ 。 若 重新执行更新后， Ｐ ｎｅｗ＿ｗ ｋ 对应的适应值优于 Ｐ ｗ ｋ 对应 的适应值，则用 Ｐ ｎｅｗ＿ｗ ｋ 取代 Ｐ ｗ ｋ ；否则采用式（３）随机 产生一个新的蛙代替 Ｐ ｗ ｋ 。 Ｐ ｗ ｋ ＝ ｒ × （Ｏｍａｘ － Ｏｍｉｎ ） ＋ Ｏｍｉｎ （３） 式中： Ｏｍａｘ 和 Ｏｍｉｎ 分别表示算法搜索范围的最大值 和最小值。 重复以上的更新操作，直至满足事先设定的族 群内的算法迭代次数。 当所有族群的局部深度搜索 完成以后，进行全局信息交换。 局部深度搜索和全 局信息交换两阶段交替进行，直到满足相应的结束 条件。 ２ 广义中心混合蛙跳算法 ２．１ 广义中心策略 在群智能算法中，随着进化的进行，全局极值将 会越来越接近最优解。 搜索结束后，全局极值将位 于最优解的邻近区域。 与此同时，由于群智能算法 的随机性，每个个体也分布在全局极值的邻近区域。 为了改善全局极值，使其更快向最优解靠近［１４］ ，Ｌｉｕ 等［１５］引入中心粒子。 中心粒子由群体的中心位置 形成，伴随于整个搜索过程，除不具有速度外，该粒 子具有与其他普通粒子相同的所有性质。 其产生的 方式如式（４）所示： ｘ ｓｃ ｄ ＝ ∑ Ｆ ｉ ＝ １ ｘ ｄ ｉ （４） 第 ３ 期 赵嘉，等：广义中心混合蛙跳算法 ·４１５·
·416: 智能系统学报 第10卷 式中，F为个体总数，d(1≤d≤N)为个体维数，N 次数的增加，各族群的性能将趋同，多样性降低。 为个体总维数，x为第i个体第d维位置。 本文提出一种新的蛙跳规则，该策略借助广义 汤可宗等6通过实验进一步发现，在粒子群优 中心青蛙的特性，使族群内最差粒子在进化过程中， 化算法中，所有个体极值形成的中心相比群体的中 能够学习其他族群内最优粒子。首先，此蛙跳规则 心更能趋近于最优解。为此，将Liu等s提出的中 会增加最差粒子向全局最优点运动的可能：其次，根 心定义为狭义中心(special center,SC),见式(4)； 据蛙跳规则的数学表述可知，该操作扩大了最差粒 将个体极值形成的中心定义为广义中心(general 子的搜索范围：再次，各族群在进化过程中形成了自 center,GC),并提出双中心粒子群优化算法。广义 己族群特色，也保证各族群的多样性。其位置更新 中心粒子产生的方式如式(5)： 公式与式(2)一致，最差蛙的移动步长更新公式为 =∑pi D4=T1×(Ph-P)+T2×(P则-P)(9) (5) i=1 式中：j∈1,2，…，m,r1、r2为[0,1]的随机数。 式中：p为第i个体第d维极值位置。 若执行更新策略(9)和(2)后，P"对应的适 混合蛙跳算法的基本原理是每只青蛙在族群内 应值优于P,则用P"取代P,否则，最差蛙的 最优青蛙和全群最优青蛙的引导下，“积极”向着最 移动步长更新公式为 优解靠近，青蛙会被吸引到全群最优蛙和族群最优 D=11×(P.-P)+r2×(P-P)(10) 蛙的邻域。混合蛙跳算法的核心思想是族群划分， 若执行更新策略(10)和(2)后，P"对应的适 每个族群均有族群内最优粒子。搜索结束后，每个 应值优于P,则用P"取代P,否则采用式(3) 族群的最优蛙位置位于最优解或其邻近区域，相比 随机生成1个新的个体位置代替原来的P:。 全群最优蛙，族群最优蛙的中心或许会更接近最优 2.3算法流程 解，这一启示给改善混合蛙跳算法提供了思路，为加 GC-SFLA算法的流程如图1所示。 速算法的收敛速度提供了非常有用的信息。借鉴文 献[16]广义中心思想，但混合蛙跳算法中无个体极 开始 值概念。为此，混合蛙跳算法中的广义中心青蛙定 种群初始化 义如下。 定义1广义中心青蛙(general center frog, 种群分割 GCF)在混合蛙跳算法的进化过程中，各族群的 广义中心蛙产生 最优蛙位置表示为P,其中k表示是第几个族群。 并依式(8)更新P。 则广义中心青蛙P则定义为 p=(p) (6) 族群1 族群2 族群 m k= 进化 进化 化 p时可能会跳出边界[Om,Om]成为非可行解，此 时，按照式(7)进行重置。 种群混合 (pee =O, P对>Om pof =0 pre <O (7) 是否游足 N 终止茶 对形成的广义中心青蛙，评估其适应值，从P Y 和P选择较优的解作为新的P。,其公式描述为 结束 (pr,f(P)<f(P) P= (8) 图1GC-SFLA算法流程 (P.,fPa)≤fP) Fig.1 Flowchart of GC-SFLA 式中：f(·)为适应值函数。 2.2蛙跳规则的改进 1)GC-SFLA算法参数设置，包括族群数、族群 标准SFLA算法蛙跳规则过于简单，族群最差 内更新次数L、族群内青蛙数、，混合迭代次数G 蛙向本族群最优蛙学习，最差蛙的可能新位置被限 等的设置。 定在当前蛙与最好蛙位置的线段上6，限制了模因 2)蛙群初始化。初始化蛙群中青蛙位置并评 进化的搜索区域，且青蛙的学习能力不强，随着迭代 估其适应值，记录蛙群最优蛙为P
式中， Ｆ 为个体总数， ｄ（１ ≤ ｄ ≤ Ｎ） 为个体维数， Ｎ 为个体总维数， ｘ ｄ ｉ 为第 ｉ 个体第 ｄ 维位置。 汤可宗等［１６］通过实验进一步发现，在粒子群优 化算法中，所有个体极值形成的中心相比群体的中 心更能趋近于最优解。 为此，将 Ｌｉｕ 等［１５］ 提出的中 心定义为狭义中心（ ｓｐｅｃｉａｌ ｃｅｎｔｅｒ， ＳＣ），见式（４）； 将个体极值形成的中心定义为广义中心（ ｇｅｎｅｒａｌ ｃｅｎｔｅｒ， ＧＣ），并提出双中心粒子群优化算法。 广义 中心粒子产生的方式如式（５）： ｘ ｇｃ ｄ ＝ ∑ Ｆ ｉ ＝ １ ｐ ｄ ｉ，ｂｅｓｔ （５） 式中： ｐ ｄ ｉ，ｂｅｓｔ 为第 ｉ 个体第 ｄ 维极值位置。 混合蛙跳算法的基本原理是每只青蛙在族群内 最优青蛙和全群最优青蛙的引导下，“积极”向着最 优解靠近，青蛙会被吸引到全群最优蛙和族群最优 蛙的邻域。 混合蛙跳算法的核心思想是族群划分， 每个族群均有族群内最优粒子。 搜索结束后，每个 族群的最优蛙位置位于最优解或其邻近区域，相比 全群最优蛙，族群最优蛙的中心或许会更接近最优 解，这一启示给改善混合蛙跳算法提供了思路，为加 速算法的收敛速度提供了非常有用的信息。 借鉴文 献［１６］广义中心思想，但混合蛙跳算法中无个体极 值概念。 为此，混合蛙跳算法中的广义中心青蛙定 义如下。 定义 １ 广义中心青蛙 （ ｇｅｎｅｒａｌ ｃｅｎｔｅｒ ｆｒｏｇ， ＧＣＦ） 在混合蛙跳算法的进化过程中，各族群的 最优蛙位置表示为 Ｐ ｂ ｋ ，其中 ｋ 表示是第几个族群。 则广义中心青蛙 Ｐ ｇｃｆ 定义为 Ｐ ｇｃｆ ＝ １ ｍ （∑ ｍ ｋ ＝ １ Ｐ ｂ ｋ） （６） Ｐ ｇｃｆ 可能会跳出边界 ［Ｏｍｉｎ ，Ｏｍａｘ］ 成为非可行解，此 时，按照式（７）进行重置。 Ｐ ｇｃｆ ＝ Ｏｍａｘ， Ｐ ｇｃｆ ＞ Ｏｍａｘ Ｐ ｇｃｆ ＝ Ｏｍｉｎ ， Ｐ ｇｃｆ ＜ Ｏｍｉｎ { （７） 对形成的广义中心青蛙，评估其适应值，从 Ｐｇ 和 Ｐ ｇｃｆ 选择较优的解作为新的 Ｐｇ ，其公式描述为 Ｐｇ ＝ Ｐ ｇｃｆ ， ｆ（Ｐ ｇｃｆ ） ＜ ｆ（Ｐｇ ） Ｐｇ ， ｆ（Ｐｇ ） ≤ ｆ（Ｐ ｇｃｆ { ） （８） 式中： ｆ（·） 为适应值函数。 ２．２ 蛙跳规则的改进 标准 ＳＦＬＡ 算法蛙跳规则过于简单，族群最差 蛙向本族群最优蛙学习，最差蛙的可能新位置被限 定在当前蛙与最好蛙位置的线段上［６］ ，限制了模因 进化的搜索区域，且青蛙的学习能力不强，随着迭代 次数的增加，各族群的性能将趋同，多样性降低。 本文提出一种新的蛙跳规则，该策略借助广义 中心青蛙的特性，使族群内最差粒子在进化过程中， 能够学习其他族群内最优粒子。 首先，此蛙跳规则 会增加最差粒子向全局最优点运动的可能；其次，根 据蛙跳规则的数学表述可知，该操作扩大了最差粒 子的搜索范围；再次，各族群在进化过程中形成了自 己族群特色，也保证各族群的多样性。 其位置更新 公式与式（２）一致，最差蛙的移动步长更新公式为 Ｄｋ ＝ ｒ１ × （Ｐ ｂ ｋ － Ｐ ｗ ｋ ） ＋ ｒ２ × （Ｐ ｇｃｆ － Ｐ ｗ ｋ ） （９） 式中： ｊ ∈ １，２，．．．，ｍ ， ｒ１ 、 ｒ２ 为［０，１］的随机数。 若执行更新策略（９）和（２）后， Ｐ ｎｅｗ＿ｗ ｋ 对应的适 应值优于 Ｐ ｗ ｋ ，则用 Ｐ ｎｅｗ＿ｗ ｋ 取代 Ｐ ｗ ｋ ，否则，最差蛙的 移动步长更新公式为 Ｄｋ ＝ ｒ１ × （Ｐｇ － Ｐ ｗ ｋ ） ＋ ｒ２ × （Ｐ ｇｃｆ － Ｐ ｗ ｋ ） （１０） 若执行更新策略（１０）和（２）后， Ｐ ｎｅｗ＿ｗ ｋ 对应的适 应值优于 Ｐ ｗ ｋ ，则用 Ｐ ｎｅｗ＿ｗ ｋ 取代 Ｐ ｗ ｋ ， 否则采用式（３） 随机生成 １ 个新的个体位置代替原来的 Ｐ ｗ ｋ 。 ２．３ 算法流程 ＧＣ⁃ＳＦＬＡ 算法的流程如图 １ 所示。 图 １ ＧＣ⁃ＳＦＬＡ 算法流程 Ｆｉｇ． １ Ｆｌｏｗｃｈａｒｔ ｏｆ ＧＣ⁃ＳＦＬＡ １）ＧＣ⁃ＳＦＬＡ 算法参数设置，包括族群数、族群 内更新次数 Ｌｍａｘ 、族群内青蛙数、混合迭代次数 Ｇｍａｘ 等的设置。 ２）蛙群初始化。 初始化蛙群中青蛙位置并评 估其适应值，记录蛙群最优蛙为 Ｐｇ 。 ·４１６· 智 能 系 统 学 报 第 １０ 卷
第3期 赵嘉，等：广义中心混合蛙跳算法 ·417- 3)族群初始化。将蛙群分成族群，每个族群包 表18个基准测试函数 含相同数量的蛙，第k个族群内的最优蛙和最差蛙 Table 1 Eight benchmark functions used in this paper 分别记为P与Pg。 函数序号 函数名 范围 最优值坐标最优值 4)广义中心蛙的生成。利用式(6)计算P时并 Sphere [-100.100](0.0.…,0) 0 评估其适应值，并根据式(8)更新P。。 1 Schwefel.2.22 [-10,10] (0,0,…,0) 0 5)族群进化。对第k个族群中的P:根据式 f Schwefel.1.2[-100,100](0,0,…,0) 0 (9)和(2)进行更新并计算其适应度值，若更新后的 Quadric Noise[-1.28,1.28](0,0,…,0) 0 5 Rastrigin [-5.12,5.12](0,0,…,0) 蛙优于原来的蛙，则取代原来族群中的蛙：如果没有 0 Ackley [-32,32](0,0,…,0) 0 改进，则根据式(10)和(2)进行更新并评估其适应 Griewank [-600,600](0,0,…,0) 0 度值，若更新后的蛙优于原来的蛙，则取代原来族群 Penalized..1[-50,50](1,l,…,1)0 中的蛙：否则根据式(3)随机产生1个新蛙直接取 代原来的P:重复上述局部搜索L次。 3.2与标准混合蛙跳算法在不同维度下的比较 6)族群混合。将更新后的各族群内蛙重新混 维度差异对算法性能有显著性影响。为验证改 合，对更新后的蛙群中的蛙排序，记录更新后的蛙群 进算法的寻优效果和稳定性，将GC-SFLA算法与标 最优蛙为P。。 准SFLA算法在不同维度下进行实验。实验参数设 7)检验是否满足终止条件，若满足，则停止迭 置为：最大函数评估次数5.0×10，青蛙个体总数 代，输出全局最优粒子位置P。及其对应的适应值， 200,族群数为20，每个族群的青蛙个体数10，族群 否则转到步骤2)。 内的迭代次数10，最大蛙跳步长为最大搜索范围的 3 仿真实验 0.4倍。 考虑篇幅限制，选取1个单峰函数∫和3个多 3.1测试函数 峰函数∫~，进行不同维度下的实验，为消除算法 本文选用8个基准测试函数[)来测试算法的 的随机性影响，算法独立运行50次，以最终的平均 性能，见表1，其中f~f是单模态函数，在给定搜 值作为算法的最后寻优结果，实验结果见表2。表 索范围内只有1个极值点，主要检验算法的收敛速 中Mean、Std.Dev表示在限定的评估次数下算法的 度和寻优精度，了~∫是多模态函数，在给定搜索范 平均最优适应值及标准差，平均最优适应值反映了 围内有多个局部极值点，主要考察算法的全局搜索 限定的评估次数下算法的寻优精度，标准差反映了 能力和逃离局部最优能力。 算法的稳定性和鲁棒性。 表22种混合蛙跳算法在不同维度下的寻优结果 Table 2 The optimization results of two shuffled frog-leaping algorithms under different dimensions Mean±Std.Dev 函数 D=10 D=30 D=50 序号 SFLA GC-SFLA SFLA GC-SFLA SFLA GC-SFLA 6.6550e-007± 0.0000e+000± 6.1305e+000± 0.0000e+000± 9.6093e+001±0.0000e+000± f月 8.7744e-006 0.0000e+000 7.9651e+001 0.0000e+000 5.3049e+001 0.0000e+000 5.12e+000± 0.0000e+000± 5.12e+000± 0.0000e+000± 5.12e+000± 0.0000e+000± 1.2561e-014 0.0000e+000 1.2561e-014 0.0000e+000 1.2561e-014 0.0000e+000 6.1549e-005± 5.8872e-016± 7.7590e-001± 5.8872e-016± 2.0828e+000± 9.4281e-002± 5.7195e-004 0.0000e+000 3.9127e+000 0.0000e+000 2.6408e+000 1.2781e-001 5.4809e-002± 0.0000e+000± 1.6115e-001± 0.0000e+000± 9.1673e-001± 6.5056e-012± f 1.7120e-001 0.0000e+000 5.9205e-001 0.0000e+000 9.6645e-001 2.2778e-011 由表2可以看出，在不同的实验维度下，无论是SLA算法均能寻找到最优解，但SLA算法在不同 解的质量还是算法的稳定性，GC-SLA算法较标准维度下的测试结果差异大。针对多峰函数，标准SF SFLA算法均有较大提高。f1函数为单峰函数，在搜索LA算法的寻优结果均不理想，对f5函数，不论在何测 区域内只有1个极值点，无论在何测试维度下，GC-试维度下，算法的均值和方差都一样，且效果非常不
３）族群初始化。 将蛙群分成族群，每个族群包 含相同数量的蛙，第 ｋ 个族群内的最优蛙和最差蛙 分别记为 Ｐ ｂ ｋ 与 Ｐ ｗ ｋ 。 ４）广义中心蛙的生成。 利用式（６）计算 Ｐ ｇｃｆ 并 评估其适应值，并根据式（８）更新 Ｐｇ 。 ５）族群进化。 对第 ｋ 个族群中的 Ｐ ｗ ｋ 根据式 （９）和（２）进行更新并计算其适应度值，若更新后的 蛙优于原来的蛙，则取代原来族群中的蛙；如果没有 改进，则根据式（１０）和（２）进行更新并评估其适应 度值，若更新后的蛙优于原来的蛙，则取代原来族群 中的蛙；否则根据式（３）随机产生 １ 个新蛙直接取 代原来的 Ｐ ｗ ｋ ；重复上述局部搜索 Ｌｍａｘ 次。 ６）族群混合。 将更新后的各族群内蛙重新混 合，对更新后的蛙群中的蛙排序，记录更新后的蛙群 最优蛙为 Ｐｇ 。 ７）检验是否满足终止条件，若满足，则停止迭 代，输出全局最优粒子位置 Ｐｇ 及其对应的适应值， 否则转到步骤 ２）。 ３ 仿真实验 ３．１ 测试函数 本文选用 ８ 个基准测试函数［１７］ 来测试算法的 性能，见表 １，其中 ｆ １ ～ ｆ ４ 是单模态函数，在给定搜 索范围内只有 １ 个极值点，主要检验算法的收敛速 度和寻优精度， ｆ ５ ～ ｆ ８ 是多模态函数，在给定搜索范 围内有多个局部极值点，主要考察算法的全局搜索 能力和逃离局部最优能力。 表 １ ８ 个基准测试函数 Ｔａｂｌｅ １ Ｅｉｇｈｔ ｂｅｎｃｈｍａｒｋ ｆｕｎｃｔｉｏｎｓ ｕｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ 函数序号 函数名 范围 最优值坐标 最优值 ｆ １ Ｓｐｈｅｒｅ ［－１００，１００］ （０，０，…，０） ０ ｆ ２ Ｓｃｈｗｅｆｅｌ．２．２２ ［－１０，１０］ （０，０，…，０） ０ ｆ ３ Ｓｃｈｗｅｆｅｌ．１．２ ［－１００，１００］ （０，０，…，０） ０ ｆ ４ Ｑｕａｄｒｉｃ Ｎｏｉｓｅ ［－１．２８，１．２８］ （０，０，…，０） ０ ｆ ５ Ｒａｓｔｒｉｇｉｎ ［－５．１２，５．１２］ （０，０，…，０） ０ ｆ ６ Ａｃｋｌｅｙ ［－３２，３２］ （０，０，…，０） ０ ｆ ７ Ｇｒｉｅｗａｎｋ ［－６００，６００］ （０，０，…，０） ０ ｆ ８ Ｐｅｎａｌｉｚｅｄ．１ ［－５０，５０］ （１，１，…，１） ０ ３．２ 与标准混合蛙跳算法在不同维度下的比较 维度差异对算法性能有显著性影响。 为验证改 进算法的寻优效果和稳定性，将 ＧＣ⁃ＳＦＬＡ 算法与标 准 ＳＦＬＡ 算法在不同维度下进行实验。 实验参数设 置为：最大函数评估次数 ５．０ × １０ ５ ，青蛙个体总数 ２００，族群数为 ２０，每个族群的青蛙个体数 １０，族群 内的迭代次数 １０，最大蛙跳步长为最大搜索范围的 ０．４ 倍。 考虑篇幅限制，选取 １ 个单峰函数 ｆ １ 和 ３ 个多 峰函数 ｆ ５ ～ ｆ ７ 进行不同维度下的实验，为消除算法 的随机性影响，算法独立运行 ５０ 次，以最终的平均 值作为算法的最后寻优结果，实验结果见表 ２。 表 中 Ｍｅａｎ、Ｓｔｄ．Ｄｅｖ 表示在限定的评估次数下算法的 平均最优适应值及标准差，平均最优适应值反映了 限定的评估次数下算法的寻优精度，标准差反映了 算法的稳定性和鲁棒性。 表 ２ ２ 种混合蛙跳算法在不同维度下的寻优结果 Ｔａｂｌｅ ２ Ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｆ ｔｗｏ ｓｈｕｆｆｌｅｄ ｆｒｏｇ⁃ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｄｉｍｅｎｓｉｏｎｓ 函数 序号 Ｍｅａｎ±Ｓｔｄ．Ｄｅｖ Ｄ＝ １０ ＳＦＬＡ ＧＣ－ＳＦＬＡ Ｄ＝ ３０ ＳＦＬＡ ＧＣ－ＳＦＬＡ Ｄ＝ ５０ ＳＦＬＡ ＧＣ－ＳＦＬＡ ｆ １ ６．６５５ ０ｅ－００７± ８．７７４ ４ｅ－００６ ０．０００ ０ｅ＋０００± ０．０００ ０ｅ＋０００ ６．１３０ ５ｅ＋０００± ７．９６５ １ｅ＋００１ ０．０００ ０ｅ＋０００± ０．０００ ０ｅ＋０００ ９．６０９ ３ｅ＋００１± ５．３０４ ９ｅ＋００１ ０．０００ ０ｅ＋０００± ０．０００ ０ｅ＋０００ ｆ ５ ５．１２ｅ＋０００± １．２５６ １ｅ－０１４ ０．０００ ０ｅ＋０００± ０．０００ ０ｅ＋０００ ５．１２ｅ＋０００± １．２５６ １ｅ－０１４ ０．０００ ０ｅ＋０００± ０．０００ ０ｅ＋０００ ５．１２ｅ＋０００± １．２５６ １ｅ－０１４ ０．０００ ０ｅ＋０００± ０．０００ ０ｅ＋０００ ｆ ６ ６．１５４ ９ｅ－００５± ５．７１９ ５ｅ－００４ ５．８８７ ２ｅ－０１６± ０．０００ ０ｅ＋０００ ７．７５９ ０ｅ－００１± ３．９１２ ７ｅ＋０００ ５．８８７ ２ｅ－０１６± ０．０００ ０ｅ＋０００ ２．０８２ ８ｅ＋０００± ２．６４０ ８ｅ＋０００ ９．４２８ １ｅ－００２± １．２７８ １ｅ－００１ ｆ ７ ５．４８０ ９ｅ－００２± １．７１２ ０ｅ－００１ ０．０００ ０ｅ＋０００± ０．０００ ０ｅ＋０００ １．６１１ ５ｅ－００１± ５．９２０ ５ｅ－００１ ０．０００ ０ｅ＋０００± ０．０００ ０ｅ＋０００ ９．１６７ ３ｅ－００１± ９．６６４ ５ｅ－００１ ６．５０５ ６ｅ－０１２± ２．２７７ ８ｅ－０１１ 由表 ２ 可以看出，在不同的实验维度下，无论是 解的质量还是算法的稳定性，ＧＣ⁃ＳＦＬＡ 算法较标准 ＳＦＬＡ 算法均有较大提高。 ｆ １ 函数为单峰函数，在搜索 区域内只有 １ 个极值点，无论在何测试维度下，ＧＣ⁃ ＳＦＬＡ 算法均能寻找到最优解，但 ＳＦＬＡ 算法在不同 维度下的测试结果差异大。 针对多峰函数，标准 ＳＦ⁃ ＬＡ 算法的寻优结果均不理想，对 ｆ ５ 函数，不论在何测 试维度下，算法的均值和方差都一样，且效果非常不 第 ３ 期 赵嘉，等：广义中心混合蛙跳算法 ·４１７·
.418 智能系统学报 第10卷 理想，但GC-SFLA算法不仅算法稳定性好，且都能寻 0 ★★★★★ 找到最优解：对函数，在不同测试维度下，标准SF LA算法寻优结果与最优结果差距大，但GC-SFLA算 5 法均能在误差允许的范围内（如设置允许的误差范 -GC.SFLA10维 围为10-0)达到最优：f。函数是一个带有指数项的 0维 连续、多峰值函数，对f6函数，虽然GC-SFLA算法的 SFLA.30维 020 寻优结果与最优解之间有差距，但较标准SFLA算 法，寻优能力确有明显提高。 -25 图2给出了GC-SFLA算法与SFLA算法在不同 -30 05101520253035404550 维度下对上述4个基准测试的进化过程曲线，图中横 计算次数 坐标计算次数的范围为0~5×10，从图2可以看出， (d)f6,函数 GC-SFLA算法不仅寻优能力强，且收敛速度快，每种 图24种测试函数的进化曲线 算法在较少次迭代后均达到较理想的寻优结果，而 Fig.2 The evolution curves of four benchmark functions SFLA算法在较少的迭代后陷入局部极值。 3.3 与新近提出的知名群智能算法进行比较 为进一步验证广义中心混合蛙跳算法的进化效 50 果，将广义中心混合蛙跳算法和新近提出的知名群智 0 中牛中中中牛料 能算法，如M.M.Eusuff等提出的标准混合蛙跳算 菊 -50 法(shuffled frog leaping algorithm,SFLA)、Zhan等18] -100 提出的自适应粒子群优化算法(adaptive particle swarm -150 +-GC-SFLA,10维 optimization,APs0)、Zhu等o提出的全局最优引导 -200 -SFLA.10维 +=GC-SFLA.30维 的人工蜂群算法(Gbest-guided artificial bee colony al- +-SFLA.30维 -250 gorithm,GABC)、汤可宗等16提出的双中心粒子群优 -30065 101520253035404550 化算法(double center particle swarm optimization,DCP- 计算次数 SO)和Wang等[0提出的多策略集成的人工蜂群算法 (a)f函数 (multi-strategy ensemble artificial bee colony algorithm, MEABC)等进行比较。GC-SFLA与SFLA算法参数设 置参见3.2节，其他群智能算法的参数设置参见对应 -10t 文献，最大函数评估次数2.0×10。表3给出了GC- -15 SLA与其他群智能算法在30维时的寻优结果对比。 GC-SFLA.10维 表3的数据显示出，在8个测试函数中，GC-SFLA算法 -25 -SFLA,10维 -GC-SLA.30维 SFLA30 相比于SFLA、DCPSO、GABC、MEABC等4种算法得到 车60唯 的种群均值和方差均有明显的优势：与APSO算法相 5 101520253035404550 比仅在f函数上表现较APS0差，在另外7个测试函 计算次数 数中，均有较好的表现。 (b)5函数 为了进一步比较这6种算法的测试结果，对6 中★◆味来本本支 种算法进行t检验，表4是GC-SFLA算法和其他5 种算法在8个函数的t验结果。t检验的分位数为 -10 单侧0.05，自由度为30，查表得到t检验的临界值 -15 公米 -GC-SFLA.10维 为1.697，即当1值大于这个值时，2种算法存在显 -20 把1难0维 著性差异。用“w/L/I"”表示GC-SFLA算法与所选 一SFLA,30 蛔 车6M0唯 算法相比在w个函数上优于该算法，t个函数上无 -30 明显差异，1个函数上差于该算法。 ★★★★★★★★★★★★ 40 从表4中数据可知，GC-SFLA算法与标准SFLA 5 101520253035404550 计算次数 算法、DCPSO算法相比，在5个测试函数上表现出较 (c)f。函数 明显的优势，在3个测试函数上无显著差异：与AP
理想，但 ＧＣ⁃ＳＦＬＡ 算法不仅算法稳定性好，且都能寻 找到最优解；对 ｆ ７ 函数，在不同测试维度下，标准 ＳＦ⁃ ＬＡ 算法寻优结果与最优结果差距大，但 ＧＣ⁃ＳＦＬＡ 算 法均能在误差允许的范围内（如设置允许的误差范 围为 １０ －１０ ）达到最优； ｆ ６ 函数是一个带有指数项的 连续、多峰值函数，对 ｆ ６ 函数，虽然 ＧＣ⁃ＳＦＬＡ 算法的 寻优结果与最优解之间有差距，但较标准 ＳＦＬＡ 算 法，寻优能力确有明显提高。 图 ２ 给出了 ＧＣ⁃ＳＦＬＡ 算法与 ＳＦＬＡ 算法在不同 维度下对上述 ４ 个基准测试的进化过程曲线，图中横 坐标计算次数的范围为 ０ ～ ５×１０ ５ ，从图 ２ 可以看出， ＧＣ⁃ＳＦＬＡ 算法不仅寻优能力强，且收敛速度快，每种 算法在较少次迭代后均达到较理想的寻优结果，而 ＳＦＬＡ 算法在较少的迭代后陷入局部极值。 （ａ） ｆ １ 函数 （ｂ） ｆ ５ 函数 （ｃ） ｆ ６ 函数 （ｄ） ｆ ７ 函数 图 ２ ４ 种测试函数的进化曲线 Ｆｉｇ． ２ Ｔｈｅ ｅｖｏｌｕｔｉｏｎ ｃｕｒｖｅｓ ｏｆ ｆｏｕｒ ｂｅｎｃｈｍａｒｋ ｆｕｎｃｔｉｏｎｓ ３．３ 与新近提出的知名群智能算法进行比较 为进一步验证广义中心混合蛙跳算法的进化效 果，将广义中心混合蛙跳算法和新近提出的知名群智 能算法，如 Ｍ． Ｍ． Ｅｕｓｕｆｆ 等［１］ 提出的标准混合蛙跳算 法（ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ， ＳＦＬＡ）、Ｚｈａｎ 等［１８］ 提出的自适应粒子群优化算法（ａｄａｐｔｉｖｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ＡＰＳＯ）、Ｚｈｕ 等［１９］ 提出的全局最优引导 的人工蜂群算法（Ｇｂｅｓｔ⁃ｇｕｉｄｅｄ ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ ａｌ⁃ ｇｏｒｉｔｈｍ， ＧＡＢＣ）、汤可宗等［１６］提出的双中心粒子群优 化算法（ｄｏｕｂｌｅ ｃｅｎｔｅｒ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ＤＣＰ⁃ ＳＯ）和 Ｗａｎｇ 等［２０］提出的多策略集成的人工蜂群算法 （ｍｕｌｔｉ⁃ｓｔｒａｔｅｇｙ ｅｎｓｅｍｂｌｅ ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ， ＭＥＡＢＣ）等进行比较。 ＧＣ⁃ＳＦＬＡ 与 ＳＦＬＡ 算法参数设 置参见 ３．２ 节，其他群智能算法的参数设置参见对应 文献，最大函数评估次数 ２．０ × １０ ５ 。 表 ３ 给出了 ＧＣ⁃ ＳＦＬＡ 与其他群智能算法在 ３０ 维时的寻优结果对比。 表 ３ 的数据显示出，在 ８ 个测试函数中，ＧＣ⁃ＳＦＬＡ 算法 相比于 ＳＦＬＡ、ＤＣＰＳＯ、ＧＡＢＣ、ＭＥＡＢＣ 等 ４ 种算法得到 的种群均值和方差均有明显的优势；与 ＡＰＳＯ 算法相 比仅在 ｆ ８ 函数上表现较 ＡＰＳＯ 差，在另外 ７ 个测试函 数中，均有较好的表现。 为了进一步比较这 ６ 种算法的测试结果，对 ６ 种算法进行 ｔ 检验，表 ４ 是 ＧＣ⁃ＳＦＬＡ 算法和其他 ５ 种算法在 ８ 个函数的 ｔ 验结果。 ｔ 检验的分位数为 单侧 ０．０５，自由度为 ３０，查表得到 ｔ 检验的临界值 为 １．６９７，即当 ｔ 值大于这个值时，２ 种算法存在显 著性差异。 用“ ｗ ／ ｔ ／ ｌ” 表示 ＧＣ⁃ＳＦＬＡ 算法与所选 算法相比在 ｗ 个函数上优于该算法，ｔ 个函数上无 明显差异，ｌ 个函数上差于该算法。 从表 ４ 中数据可知，ＧＣ⁃ＳＦＬＡ 算法与标准 ＳＦＬＡ 算法、ＤＣＰＳＯ 算法相比，在 ５ 个测试函数上表现出较 明显的优势，在 ３ 个测试函数上无显著差异；与 ＡＰ⁃ ·４１８· 智 能 系 统 学 报 第 １０ 卷
第3期 赵嘉，等：广义中心混合蛙跳算法 419. SO和GABC算法在8个函数的仿真实验相比，除了外GC-SFLA算法与MEABC相比，除在f上有明显劣 在f函数上无显著差异，在f上有明显劣势外，在其势，在f和f上无显著差异外，在其他5个函数上均 他6个函数上，GC-SFLA算法有着很大的优势。另有明显的优势。 表3GC-LSFLA与新近的知名群智能算法寻优结果对比 Table 3 Comparison between the GC-LSFLA and the recently proposed swarm intelligence algorithms 测试函数 指标 SFLA APSO DCPSO GABC MEABC GC-SFLA Mean 5.41e-1 1.45e-150 7.31e-2304.70e-16 1.55e-56 1.99e-277 Std.Dev 6.40e-1 5.73e-150 0 2.57e-15 3.67e-55 0 Mean 7.84e0 5.15e-84 1.94e-85 1.26e-15 1.08e-29 1.21e-111 Std.Dev 2.37el 1.44e-83 3.07e-84 6.90e-15 2.21e-28 1.24e-110 Mean 1.00e2 1.0e-10 2.22e-22 5.49e3 8.31e3 5.81e-86 Std.Dev 1.03e2 2.13e-10 6.50e-21 3.00e4 7.54e3 7.62e-85 Mean 2.17e3 4.66e-3 3.34e-4 5.00e-2 2.18e-2 2.20e-4 f. Std.Dev 4.19e-3 1.7e-3 1.01e-3 2.74e-1 3.77e-3 2.15e-4 Mean 5.12e0 5.8e-15 0 0 0 0 Std.Dev 1.25e-14 1.01e-14 0 0 S Mean 7.80e-3 1.11e-14 2.96e-15 2.91e-14 4.13e-14 5.88e-16 Std.Dev 3.81e-2 3.55e-15 0 1.59e-13 2.17e-15 0 Mean 1.45e-1 1.67e-2 3.70e-17 0 0 f Std.Dev 5.67e-1 2.41e-2 0 2.08e-16 0 0 Mean 3.03e-2 3.76e-31 1.42e-1 4.75e-16 3.02e-17 1.31e-2 Std.Dev 2.77e-1 1.2e-30 1.88e-1 2.60e-15 0 2.15e-2 表4 GC-SFLA算法与其他5种算法的1检验结果 表56种优化算法的Friendman检验结果 Table 1 The results of t test of GC-SFLA algorithm and Table 5 The results of Friendman test of 6 algorithms the other 5 algorithms 算法 秩均值 测试函数SFLA APsO DCPSO GABC MEABC GC-SFLA 2.44 DCPSO 2.81 APSO 3.13 GABC 3.44 MEABC 3.56 X SFLA 5.63 为清晰地描述6种优化算法在进化过程中的收 敛速率。本文给出了SFLA、APSO、DCPSO、GABC、 w/t/l 5/3/0 6/1/1 5/3/0 6/1/1 5/2/1 MEABC和GC-SFLA在8个测试函数30维上的收 敛性能曲线图，如图3所示。由图3可知，GC-SFLA 为进一步在统计意义上比较6种算法的性能。 算法能很好地增强算法逃离局部最优的能力，以及 采用Friendman检验对结果进行分析。表5给出 加速算法后期的收敛速度。GC-SFLA算法在处理单 SFLA、APSO、DCPSO、GABC、MEABC和GC-SFLA6 种算法在8个测试函数上总体性能的平均排名。算 模态函数时，优势相当明显，其中、方、3个函数 法秩均值越小，性能越好，排名越高（排名最高的算 的进化曲线几乎呈直线下降。GC-SFLA算法在处理 法秩均值用粗体显示)。从表5中数据可知，GC-SF 复杂的多模态函数时，收敛速度也具有非常大的优 LA明显高于其他5种算法。 势，特别是f5和f方2个函数，在评估次数在2万次左
ＳＯ 和 ＧＡＢＣ 算法在 ８ 个函数的仿真实验相比，除了 在 ｆ １ 函数上无显著差异，在 ｆ ８ 上有明显劣势外，在其 他 ６ 个函数上，ＧＣ⁃ＳＦＬＡ 算法有着很大的优势。 另 外 ＧＣ⁃ＳＦＬＡ 算法与 ＭＥＡＢＣ 相比，除在 ｆ ８ 上有明显劣 势，在 ｆ ５ 和 ｆ ７ 上无显著差异外，在其他 ５ 个函数上均 有明显的优势。 表 ３ ＧＣ⁃ＬＳＦＬＡ 与新近的知名群智能算法寻优结果对比 Ｔａｂｌｅ ３ Ｃｏｍｐａｒｉｓｏｎ ｂｅｔｗｅｅｎ ｔｈｅ ＧＣ⁃ＬＳＦＬＡ ａｎｄ ｔｈｅ ｒｅｃｅｎｔｌｙ ｐｒｏｐｏｓｅｄ ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ ａｌｇｏｒｉｔｈｍｓ 测试函数 指标 ＳＦＬＡ ＡＰＳＯ ＤＣＰＳＯ ＧＡＢＣ ＭＥＡＢＣ ＧＣ⁃ＳＦＬＡ ｆ １ Ｍｅａｎ ５．４１ｅ－１ １．４５ｅ－１５０ ７．３１ｅ－２３０ ４．７０ｅ－１６ １．５５ｅ－５６ １．９９ｅ－２７７ Ｓｔｄ．Ｄｅｖ ６．４０ｅ－１ ５．７３ｅ－１５０ ０ ２．５７ｅ－１５ ３．６７ｅ－５５ ０ ｆ ２ Ｍｅａｎ ７．８４ｅ０ ５．１５ｅ－８４ １．９４ｅ－８５ １．２６ｅ－１５ １．０８ｅ－２９ １．２１ｅ－１１１ Ｓｔｄ．Ｄｅｖ ２．３７ｅ１ １．４４ｅ－８３ ３．０７ｅ－８４ ６．９０ｅ－１５ ２．２１ｅ－２８ １．２４ｅ－１１０ ｆ ３ Ｍｅａｎ １．００ｅ２ １．０ｅ－１０ ２．２２ｅ－２２ ５．４９ｅ３ ８．３１ｅ３ ５．８１ｅ－８６ Ｓｔｄ．Ｄｅｖ １．０３ｅ２ ２．１３ｅ－１０ ６．５０ｅ－２１ ３．００ｅ４ ７．５４ｅ３ ７．６２ｅ－８５ ｆ ４ Ｍｅａｎ ２．１７ｅ３ ４．６６ｅ－３ ３．３４ｅ－４ ５．００ｅ－２ ２．１８ｅ－２ ２．２０ｅ－４ Ｓｔｄ．Ｄｅｖ ４．１９ｅ－３ １．７ｅ－３ １．０１ｅ－３ ２．７４ｅ－１ ３．７７ｅ－３ ２．１５ｅ－４ ｆ ５ Ｍｅａｎ ５．１２ｅ０ ５．８ｅ－１５ ０ ０ ０ ０ Ｓｔｄ．Ｄｅｖ １．２５ｅ－１４ １．０１ｅ－１４ ０ ０ ０ ０ ｆ ６ Ｍｅａｎ ７．８０ｅ－３ １．１１ｅ－１４ ２．９６ｅ－１５ ２．９１ｅ－１４ ４．１３ｅ－１４ ５．８８ｅ－１６ Ｓｔｄ．Ｄｅｖ ３．８１ｅ－２ ３．５５ｅ－１５ ０ １．５９ｅ－１３ ２．１７ｅ－１５ ０ ｆ ７ Ｍｅａｎ １．４５ｅ－１ １．６７ｅ－２ ０ ３．７０ｅ－１７ ０ ０ Ｓｔｄ．Ｄｅｖ ５．６７ｅ－１ ２．４１ｅ－２ ０ ２．０８ｅ－１６ ０ ０ ｆ ８ Ｍｅａｎ ３．０３ｅ－２ ３．７６ｅ－３１ １．４２ｅ－１ ４．７５ｅ－１６ ３．０２ｅ－１７ １．３１ｅ－２ Ｓｔｄ．Ｄｅｖ ２．７７ｅ－１ １．２ｅ－３０ １．８８ｅ－１ ２．６０ｅ－１５ ０ ２．１５ｅ－２ 表 ４ ＧＣ⁃ＳＦＬＡ 算法与其他 ５ 种算法的 ｔ 检验结果 Ｔａｂｌｅ １ Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｔ ｔｅｓｔ ｏｆ ＧＣ⁃ＳＦＬＡ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｏｔｈｅｒ ５ ａｌｇｏｒｉｔｈｍｓ 测试函数 ＳＦＬＡ ＡＰＳＯ ＤＣＰＳＯ ＧＡＢＣ ＭＥＡＢＣ ｆ １ ＋ ＝ ＋ ＝ ＝ ｆ ２ ＋ ＋ ＝ ＝ ＝ ｆ ３ ＋ ＋ ＝ ＝ ＋ ｆ ４ ＋ ＋ ＝ ＝ ＋ ｆ ５ ＋ ＋ ＋ ＋ ＋ ｆ ６ ＝ ＋ ＋ ＝ ＋ ｆ ７ ＝ ＋ ＋ ＝ ＋ ｆ ８ ＝ － ＋ － － ｗ／ ｔ ／ ｌ ５ ／ ３ ／ ０ ６ ／ １ ／ １ ５ ／ ３ ／ ０ ６ ／ １ ／ １ ５ ／ ２ ／ １ 为进一步在统计意义上比较 ６ 种算法的性能， 采用 Ｆｒｉｅｎｄｍａｎ 检验对结果进行分析。 表 ５ 给出 ＳＦＬＡ、ＡＰＳＯ、ＤＣＰＳＯ、ＧＡＢＣ、ＭＥＡＢＣ 和 ＧＣ⁃ＳＦＬＡ ６ 种算法在 ８ 个测试函数上总体性能的平均排名。 算 法秩均值越小，性能越好，排名越高（排名最高的算 法秩均值用粗体显示）。 从表 ５ 中数据可知，ＧＣ⁃ＳＦ⁃ ＬＡ 明显高于其他 ５ 种算法。 表 ５ ６ 种优化算法的 Ｆｒｉｅｎｄｍａｎ 检验结果 Ｔａｂｌｅ ５ Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ Ｆｒｉｅｎｄｍａｎ ｔｅｓｔ ｏｆ ６ ａｌｇｏｒｉｔｈｍｓ 算法 秩均值 ＧＣ⁃ＳＦＬＡ ２．４４ ＤＣＰＳＯ ２．８１ ＡＰＳＯ ３．１３ ＧＡＢＣ ３．４４ ＭＥＡＢＣ ３．５６ ＳＦＬＡ ５．６３ 为清晰地描述 ６ 种优化算法在进化过程中的收 敛速率。 本文给出了 ＳＦＬＡ、ＡＰＳＯ、ＤＣＰＳＯ、ＧＡＢＣ、 ＭＥＡＢＣ 和 ＧＣ⁃ＳＦＬＡ 在 ８ 个测试函数 ３０ 维上的收 敛性能曲线图，如图 ３ 所示。 由图 ３ 可知，ＧＣ⁃ＳＦＬＡ 算法能很好地增强算法逃离局部最优的能力，以及 加速算法后期的收敛速度。 ＧＣ⁃ＳＦＬＡ 算法在处理单 模态函数时，优势相当明显，其中 ｆ １ 、 ｆ ２ 、 ｆ ３ ３ 个函数 的进化曲线几乎呈直线下降。 ＧＣ⁃ＳＦＬＡ 算法在处理 复杂的多模态函数时，收敛速度也具有非常大的优 势，特别是 ｆ ５ 和 ｆ ７ ２ 个函数，在评估次数在 ２ 万次左 第 ３ 期 赵嘉，等：广义中心混合蛙跳算法 ·４１９·
420 智能 系统学报 第10卷 右就可以寻找到最优位置，其他5种算法却很容易 A 陷入局部最优，造成收敛速度变慢，甚至停滞不前。 0 50 14←9合g48合8合至 0 -10 100 -12 150 ×10 200 6 8101214161820 评估次数 -250 GC-SFLA (e)5函数 300 4 6 80立4682ǒ10 评估次数 (a)f函数 国4国4 20 -5 4444日-4小日444小可 A -20 10 40 细 15 60 -20 -80 10 0 2 4 6 8101214161820 评估次数 100 GC-SFLA 120 ×101 6 810.1214161820 ()f6函数 评估次数 (b)f5函数 10 10 GC-SFLA -15 00 -20 10 4 6 8101214161820 GC-SFLA 评估次数 4×101 0 8101214161820 (g)f方函数 评估次数 (c)f方函数 0 餐午可华斗年华车华车年十年身日 -5 APSO -10 -15 -20 2 +GC-SFLA -25 0 -30 GC-SFLA 35 -2 8成图 24 6 8101214161820 10 评估次数 人4在业4坐4x10 246 8101214161820 (h)f函数 评估次数 图38种测试函数的进化曲线 (d)f函数 Fig.3 The evolutionary curve of eight benchmark functions
右就可以寻找到最优位置，其他 ５ 种算法却很容易 陷入局部最优，造成收敛速度变慢，甚至停滞不前。 （ａ） ｆ １ 函数 （ｂ） ｆ ２ 函数 （ｃ） ｆ ３ 函数 （ｄ） ｆ ４ 函数 （ｅ） ｆ ５ 函数 （ｆ） ｆ ６ 函数 （ｇ） ｆ ７ 函数 （ｈ） ｆ ８ 函数 图 ３ ８ 种测试函数的进化曲线 Ｆｉｇ． ３ Ｔｈｅ ｅｖｏｌｕｔｉｏｎａｒｙ ｃｕｒｖｅ ｏｆ ｅｉｇｈｔ ｂｅｎｃｈｍａｒｋ ｆｕｎｃｔｉｏｎｓ ·４２０· 智 能 系 统 学 报 第 １０ 卷
第3期 赵嘉，等：广义中心混合蛙跳算法 ·421. 4结束语 shuffled frog leaping algorithm based on molecular dynamics simulations[J].Journal of Data Acquisition Processing, 本文在传统混合蛙跳算法的基础上，提出广义 2012,27(3):327-332. 中心混合蛙跳算法。该算法分析传统混合蛙跳算法 [13]SUN Hui,ZHAO Jia.Application of particle sharing based 存在的族群之间学习能力不强的问题，引入广义中 particle swarm frog leaping hybrid optimization algorithm in wireless sensor network coverage optimization[J].Journal 心青蛙的概念，设计广义中心策略以改进族群进化 of Information and Computational Science,2011,8(14): 规则，该方法极大改善了族群之间的信息共享能力， 3181-3188. 增强了族群的多样性以及加快了算法的收敛速度。 [14]汤可宗.遗传算法与粒子群优化算法的改进及应用研 后续将加强算法在各类实际问题中的应用研究。 究[D].南京：南京理工大学，2011：1-100. TANG Kezong.Modifications and application research on 参考文献： genetic algorithm and particle swarm optimization algorithm [1]EUSUFF MM,LANSEY K E.Optimization of water distri- [D].Nanjing,China:Nanjing University of Science bution network design using the shuffled frog leaping algo- Technolo,2011:1-100. rithm[J].Joumal of Water Resources Planning and Manage- [15]LIU Yu,QIN Zheng,SHI Zhewen,et al.Center particle memt,2003,129(3):210-225. swarm optimization[J].Neurocomputing,2007,70(4/5/ [2]MOSCATO P.On evolution,search,optimization,genetic 6):672-679. algorithms and martial arts:towards memetic algorithms, [16]汤可宗，柳炳祥，杨静宇，等.双中心粒子群优化算法 Technical report C3P 826[R].Pasadena,USA:California [J].计算机研究与发展，2012,49(5)：1086-1094. Institute of Technology,1989. TANG Kezong,LIU Bingxiang,YANG Jingyu,et al. [3]KENNEDY J,EBERHART R.Particle swarm optimization Double center particle swarm optimization algorithm[J]. [C]//Proceedings of the IEEE International Conference on Journal of Computer Research and Development,2012,49 Neural Networks.Perth,Australia,1995:1942-1948. (5):1086-1094. 4]RAHIMI-VAHED A,MIRZAEI A H.A hybrid multi-objec- [17]YAO Xin,LIU Yong,LIN Guangming.Evolutionary pro- tive shuffled frog-leaping algorithm for a mixed-model assem- gramming made faster[J].IEEE Transactions on Evolution- bly line sequencing problem[J].Computers Industrial En- ary Computation,1999,3(2):82-102. gineering,2007,53(4):642-666. [18]ZHAN Zhihui,ZHANG Jun,LI Yun,et al.Adaptive parti- [5]崔文华，刘晓冰，王伟，等.混合蛙跳算法研究综述[] cle swarm optimization[J].IEEE Transactions on Systems 控制与决策，2012,27(4)：481-486,493. Man,and Cybernetics-Part B:Cybernetics,2009,39 CUI Wenhua,LIU Xiaobing,WANG Wei,et al.Survey on (6):1362-1381. shuffled frog leaping algorithm[].Control and Decision, [19]ZHU Guopu,KWONG S.Gbest-guided artificial bee colony 2012,27(4):481-486,193. algorithm for numerical function optimization[J].Applied [6]FAN Tanghuai,LU Li,ZHAO Jia.Improved shuffled frog Mathematics and Computation,2010,217 (7):3166- leaping algorithm and its application in node localization of 3173. wireless sensor networksJ.Intelligent Automation Soft [20]WANG Hui,WU Zhijian,RAHNAMAYAN S,et al. Computing,.2012,18(7):807-818. Multi-strategy ensemble artificial bee colony algorithm[J]. [7]XIA Li,LUO Jianping,CHEN Minrong,et al.An improved Information Sciences,2014,279:587-603. shuffled frog-leaping algorithm with extremal optimisation for 作者简介： continuous optimisation J.Information Sciences,2012, 赵嘉，男，1981年生，副教授，主要 192:143-151. 研究方向为计算智能、群体智能、智能 [8]ROY P,ROY P,CHAKRABARTI A.Modified shuffled frog 信息处理。 leaping algorithm with genetic algorithm crossover for solving economic load dispatch problem with valve-point effect[]]. Applied Soft Computing,2013,13(11):4244-4252. 9]VAISAKH K,REDDY A S.MSFLA/GHS/SFLA-GHS/SDE algorithms for economic dispatch problem considering multi- ple fuels and valve point loadings[J].Applied Soft Compu- 吕莉，女，1982年生，副教授，主要 tig,2013,13(11):4281-4291. 研究方向计算智能、目标跟踪。 [10]罗雪晖，杨烨，李霞.改进混合蛙跳算法求解旅行商问 题[J].通信学报，2009,30(7)：130-135. LUO Xuehui,YANG Ye,LI Xia.Modified shuffled frog- leaping algorithm to solve traveling salesman problem[J]. Journal on Communications,2009,30(7):130-135. [11]NIKNAM T,FIROUZI BB,MOJARRAD H D.A new evo- lutionary algorithm for non-linear economic dispatch[J]. 樊棠怀，男，1962年生，教授，博士， Expert Systems with Applications,2011,38(10):13301- 主要研究方向为无线传感器网络、数据 13309. 采集与处理、信息融合。 [12]张潇丹，胡峰，赵力，等.基于分子动力学模拟的改进 混合蛙跳算法[J].数据采集与处理，2012,27(3)： 327-332. ZHANG Xiaodan,HU Feng,ZHAO Li,et al.Improved
４ 结束语 本文在传统混合蛙跳算法的基础上，提出广义 中心混合蛙跳算法。 该算法分析传统混合蛙跳算法 存在的族群之间学习能力不强的问题，引入广义中 心青蛙的概念，设计广义中心策略以改进族群进化 规则，该方法极大改善了族群之间的信息共享能力， 增强了族群的多样性以及加快了算法的收敛速度。 后续将加强算法在各类实际问题中的应用研究。 参考文献： ［１］ＥＵＳＵＦＦ Ｍ Ｍ， ＬＡＮＳＥＹ Ｋ Ｅ． Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｗａｔｅｒ ｄｉｓｔｒｉ⁃ ｂｕｔｉｏｎ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ ｕｓｉｎｇ ｔｈｅ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｗａｔｅｒ Ｒｅｓｏｕｒｃｅｓ Ｐｌａｎｎｉｎｇ ａｎｄ Ｍａｎａｇｅ⁃ ｍｅｎｔ， ２００３， １２９（３）： ２１０⁃２２５． ［２］ ＭＯＳＣＡＴＯ Ｐ． Ｏｎ ｅｖｏｌｕｔｉｏｎ， ｓｅａｒｃｈ， ｏｐｔｉｍｉｚａｔｉｏｎ， ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｍａｒｔｉａｌ ａｒｔｓ： ｔｏｗａｒｄｓ ｍｅｍｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ， Ｔｅｃｈｎｉｃａｌ ｒｅｐｏｒｔ Ｃ３Ｐ ８２６［Ｒ］． Ｐａｓａｄｅｎａ， ＵＳＡ： Ｃａｌｉｆｏｒｎｉａ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， １９８９． ［３］ ＫＥＮＮＥＤＹ Ｊ， ＥＢＥＲＨＡＲＴ Ｒ． Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ． Ｐｅｒｔｈ， Ａｕｓｔｒａｌｉａ， １９９５： １９４２⁃１９４８． ［４］ＲＡＨＩＭＩ⁃ＶＡＨＥＤ Ａ， ＭＩＲＺＡＥＩ Ａ Ｈ． Ａ ｈｙｂｒｉｄ ｍｕｌｔｉ⁃ｏｂｊｅｃ⁃ ｔｉｖｅ ｓｈｕｆｆｌｅｄ ｆｒｏｇ⁃ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａ ｍｉｘｅｄ⁃ｍｏｄｅｌ ａｓｓｅｍ⁃ ｂｌｙ ｌｉｎｅ ｓｅｑｕｅｎｃｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］． Ｃｏｍｐｕｔｅｒｓ ＆ Ｉｎｄｕｓｔｒｉａｌ Ｅｎ⁃ ｇｉｎｅｅｒｉｎｇ， ２００７， ５３（４）： ６４２⁃６６６． ［５］崔文华， 刘晓冰， 王伟， 等． 混合蛙跳算法研究综述［ Ｊ］． 控制与决策， ２０１２， ２７（４）： ４８１⁃４８６， ４９３． ＣＵＩ Ｗｅｎｈｕａ， ＬＩＵ Ｘｉａｏｂｉｎｇ， ＷＡＮＧ Ｗｅｉ， ｅｔ ａｌ． Ｓｕｒｖｅｙ ｏｎ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ Ｄｅｃｉｓｉｏｎ， ２０１２， ２７（４）： ４８１⁃４８６， １９３． ［６］ＦＡＮ Ｔａｎｇｈｕａｉ， ＬＵ Ｌｉ， ＺＨＡＯ Ｊｉａ． Ｉｍｐｒｏｖｅｄ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｎｏｄｅ ｌｏｃａｌｉｚａｔｉｏｎ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｉｎｔｅｌｌｉｇｅｎｔ Ａｕｔｏｍａｔｉｏｎ ＆ Ｓｏｆｔ Ｃｏｍｐｕｔｉｎｇ， ２０１２， １８（７）： ８０７⁃８１８． ［７］ＸＩＡ Ｌｉ， ＬＵＯ Ｊｉａｎｐｉｎｇ， ＣＨＥＮ Ｍｉｎｒｏｎｇ， ｅｔ ａｌ． Ａｎ ｉｍｐｒｏｖｅｄ ｓｈｕｆｆｌｅｄ ｆｒｏｇ⁃ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｅｘｔｒｅｍａｌ ｏｐｔｉｍｉｓａｔｉｏｎ ｆｏｒ ｃｏｎｔｉｎｕｏｕｓ ｏｐｔｉｍｉｓａｔｉｏｎ ［ Ｊ ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ， ２０１２， １９２： １４３⁃１５１． ［８］ＲＯＹ Ｐ， ＲＯＹ Ｐ， ＣＨＡＫＲＡＢＡＲＴＩ Ａ． Ｍｏｄｉｆｉｅｄ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｃｒｏｓｓｏｖｅｒ ｆｏｒ ｓｏｌｖｉｎｇ ｅｃｏｎｏｍｉｃ ｌｏａｄ ｄｉｓｐａｔｃｈ ｐｒｏｂｌｅｍ ｗｉｔｈ ｖａｌｖｅ⁃ｐｏｉｎｔ ｅｆｆｅｃｔ［ Ｊ］． Ａｐｐｌｉｅｄ Ｓｏｆｔ Ｃｏｍｐｕｔｉｎｇ， ２０１３， １３（１１）： ４２４４⁃４２５２． ［９］ＶＡＩＳＡＫＨ Ｋ， ＲＥＤＤＹ Ａ Ｓ． ＭＳＦＬＡ／ ＧＨＳ ／ ＳＦＬＡ⁃ＧＨＳ ／ ＳＤＥ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｅｃｏｎｏｍｉｃ ｄｉｓｐａｔｃｈ ｐｒｏｂｌｅｍ ｃｏｎｓｉｄｅｒｉｎｇ ｍｕｌｔｉ⁃ ｐｌｅ ｆｕｅｌｓ ａｎｄ ｖａｌｖｅ ｐｏｉｎｔ ｌｏａｄｉｎｇｓ［ Ｊ］． Ａｐｐｌｉｅｄ Ｓｏｆｔ Ｃｏｍｐｕ⁃ ｔｉｎｇ， ２０１３， １３（１１）： ４２８１⁃４２９１． ［１０］罗雪晖， 杨烨， 李霞． 改进混合蛙跳算法求解旅行商问 题［Ｊ］． 通信学报， ２００９， ３０（７）： １３０⁃１３５． ＬＵＯ Ｘｕｅｈｕｉ， ＹＡＮＧ Ｙｅ， ＬＩ Ｘｉａ． Ｍｏｄｉｆｉｅｄ ｓｈｕｆｆｌｅｄ ｆｒｏｇ⁃ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ｓｏｌｖｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ２００９， ３０（７）： １３０⁃１３５． ［１１］ＮＩＫＮＡＭ Ｔ， ＦＩＲＯＵＺＩ Ｂ Ｂ， ＭＯＪＡＲＲＡＤ Ｈ Ｄ． Ａ ｎｅｗ ｅｖｏ⁃ ｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｎｏｎ⁃ｌｉｎｅａｒ ｅｃｏｎｏｍｉｃ ｄｉｓｐａｔｃｈ ［ Ｊ］． Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１１， ３８（１０）： １３３０１⁃ １３３０９． ［１２］张潇丹， 胡峰， 赵力， 等． 基于分子动力学模拟的改进 混合蛙跳算法［ Ｊ］． 数据采集与处理， ２０１２， ２７ （ ３）： ３２７⁃３３２． ＺＨＡＮＧ Ｘｉａｏｄａｎ， ＨＵ Ｆｅｎｇ， ＺＨＡＯ Ｌｉ， ｅｔ ａｌ． Ｉｍｐｒｏｖｅｄ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｍｏｌｅｃｕｌａｒ ｄｙｎａｍｉｃｓ ｓｉｍｕｌａｔｉｏｎｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｄａｔａ Ａｃｑｕｉｓｉｔｉｏｎ ＆ Ｐｒｏｃｅｓｓｉｎｇ， ２０１２， ２７（３）： ３２７⁃３３２． ［１３］ＳＵＮ Ｈｕｉ， ＺＨＡＯ Ｊｉａ． Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｐａｒｔｉｃｌｅ ｓｈａｒｉｎｇ ｂａｓｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｆｒｏｇ ｌｅａｐｉｎｇ ｈｙｂｒｉｄ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｃｏｖｅｒａｇｅ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｓｃｉｅｎｃｅ， ２０１１， ８（１４）： ３１８１⁃３１８８． ［１４］汤可宗． 遗传算法与粒子群优化算法的改进及应用研 究［Ｄ］． 南京： 南京理工大学， ２０１１： １⁃１００． ＴＡＮＧ Ｋｅｚｏｎｇ． Ｍｏｄｉｆｉｃａｔｉｏｎｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｒｅｓｅａｒｃｈ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ［Ｄ］． Ｎａｎｊｉｎｇ， Ｃｈｉｎａ： Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ， ２０１１： １⁃１００． ［１５］ ＬＩＵ Ｙｕ， ＱＩＮ Ｚｈｅｎｇ， ＳＨＩ Ｚｈｅｗｅｎ， ｅｔ ａｌ． Ｃｅｎｔｅｒ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２００７， ７０（ ４ ／ ５ ／ ６）： ６７２⁃６７９． ［１６］汤可宗， 柳炳祥， 杨静宇， 等． 双中心粒子群优化算法 ［Ｊ］． 计算机研究与发展， ２０１２， ４９（５）： １０８６⁃１０９４． ＴＡＮＧ Ｋｅｚｏｎｇ， ＬＩＵ Ｂｉｎｇｘｉａｎｇ， ＹＡＮＧ Ｊｉｎｇｙｕ， ｅｔ ａｌ． Ｄｏｕｂｌｅ ｃｅｎｔｅｒ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２０１２， ４９ （５）： １０８６⁃１０９４． ［１７］ＹＡＯ Ｘｉｎ， ＬＩＵ Ｙｏｎｇ， ＬＩＮ Ｇｕａｎｇｍｉｎｇ． Ｅｖｏｌｕｔｉｏｎａｒｙ ｐｒｏ⁃ ｇｒａｍｍｉｎｇ ｍａｄｅ ｆａｓｔｅｒ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎ⁃ ａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ， １９９９， ３（２）： ８２⁃１０２． ［１８］ＺＨＡＮ Ｚｈｉｈｕｉ， ＺＨＡＮＧ Ｊｕｎ， ＬＩ Ｙｕｎ， ｅｔ ａｌ． Ａｄａｐｔｉｖｅ ｐａｒｔｉ⁃ ｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ Ｍａｎ， ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ—Ｐａｒｔ Ｂ： Ｃｙｂｅｒｎｅｔｉｃｓ， ２００９， ３９ （６）： １３６２⁃１３８１． ［１９］ＺＨＵ Ｇｕｏｐｕ， ＫＷＯＮＧ Ｓ． Ｇｂｅｓｔ⁃ｇｕｉｄｅｄ ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｎｕｍｅｒｉｃａｌ ｆｕｎｃｔｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｊ］． Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎ， ２０１０， ２１７ （ ７ ）： ３１６６⁃ ３１７３． ［ ２０ ］ ＷＡＮＧ Ｈｕｉ， ＷＵ Ｚｈｉｊｉａｎ， ＲＡＨＮＡＭＡＹＡＮ Ｓ， ｅｔ ａｌ． Ｍｕｌｔｉ⁃ｓｔｒａｔｅｇｙ ｅｎｓｅｍｂｌｅ ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ， ２０１４， ２７９： ５８７⁃６０３． 作者简介： 赵嘉，男，１９８１ 年生，副教授，主要 研究方向为计算智能、群体智能、智能 信息处理。 吕莉，女，１９８２ 年生，副教授，主要 研究方向计算智能、目标跟踪。 樊棠怀，男，１９６２ 年生，教授，博士， 主要研究方向为无线传感器网络、数据 采集与处理、信息融合。 第 ３ 期 赵嘉，等：广义中心混合蛙跳算法 ·４２１·