第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的优点［４］ ，具有概念简单、参数设置少、计算速度 快、全局寻优能力强、易于实现等特点［５］ ，并在无线 传感器网络覆盖优化［６］ 、函数优化［７］ 、经济负荷分 配［８］ 、生产调度组合优化［９］ 等领域取得较好应用， 正成为智能计算领域的研究热点。 与其他群智能算法相似，混合蛙跳算法也存在 易陷入局部极值、进化后期收敛速度慢、计算精度低 等缺点。 为此，研究人员在不断深入研究和分析后， 提出了多种不同思想的改进混合蛙跳算法，比较有 代表性的有罗雪晖等［１０］ 在混合蛙跳算法中加入调 整序思想设计了局部搜索策略，并在全局信息交换 中加入变异算法，提出一种改进的混合蛙跳算法并 应用于求解 ＴＳＰ 问题；Ｔ． Ｎｉｋｎａｍ 等［１１］ 利用混沌局 部搜索策略提出改进的混沌混合蛙跳算法；借鉴分 子动力学模拟的思想，张潇丹［１２］ 提出基于分子动力 学模拟的改进混合蛙跳算法；Ｓｕｎ 等［１３］ 提出一种基 于粒子共享的粒子群蛙跳混合优化算法，算法利用 粒子群具有良好全局搜索性能与混合蛙跳算法具有 较强局部搜索能力的特点，克服了群体智能算法后 期易陷入局部最优及“早熟”收敛的缺点。 这些算 法都在标准 ＳＦＬＡ 基础上进行不同程度的改进，但 其改进也不同程度增加了算法的复杂性。 在 ＳＦＬＡ 中，青蛙的跳跃主要经历局部搜索和 全局信息交换 ２ 个阶段，局部搜索使模因信息在局 部个体间进行传递，全局信息交换使得局部间的模 因信息得到交换，这在很大程度上决定了算法的收 敛速度与解的质量。 但青蛙在进化过程中，族群中 的最差青蛙只向自身蛙群和最优青蛙所在蛙群的最 好青蛙学习，族群之间的相互学习不够、共享能力不 强。 为此，利用各族群最优蛙的优势，构造广义中心 青蛙，并改进蛙群的进化策略，使蛙群在原有学习策 略的基础上，增加向广义中心青蛙学习的能力，提出 广义中心混合蛙跳算法（ ｓｈｕｆｆｌｅｄ ｆｒｏｇ ｌｅａｐｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｇｅｎｅｒｎａｌ ｃｅｎｔｅｒ， ＧＣ⁃ＳＦＬＡ）。 通过对 ８ 个标准测试函数的实验仿真，将提出的广义中心 混合蛙跳算法与标准混合蛙跳算法及新近提出的知 名群智能算法比较算法收敛速度和全局寻优能力。 １ 混合蛙跳算法 混合蛙跳算法是一种基于群体智能的生物进化 算法。 该算法模拟湿地中一群青蛙按族群划分的思 想进行觅食。 在算法执行时，首先产生 Ｆ 只青蛙组 成蛙群，对于 Ｎ 维优化问题，群体中第 ｉ 只青蛙表示 为 Ｘｉ ＝ （ｘ １ ｉ ，ｘ ２ ｉ ，．．．，ｘ Ｎ ｉ ） ，将蛙群内的青蛙个体按照 适应值进行降序排列，找到全局最好青蛙（解） Ｐｇ 。 将蛙群分成 ｍ 个族群，每个族群包含 ｎ 只青蛙，满 足关系 Ｆ ＝ ｍ × ｎ 。 族群的划分规则是：第 １ 只青蛙 进入第 １ 个族群，第 ２ 只青蛙进入第 ２ 个族群，第 ｍ 只青蛙进入第 ｍ 个族群，第 ｍ ＋ １ 只青蛙又进入第 １ 个族群，第 ｍ ＋ ２ 只青蛙进入第 ２ 个族群，以此类 推，直至所有青蛙划分完毕。 第 ｋ 个族群中最好的 一个青蛙，记为 Ｐ ｂ ｋ ，相应地可以得到一个最差的青 蛙，记为 Ｐ ｗ ｋ 。 为了获得更多的食物，较差的蛙受较好蛙的影 响而跳向较好的蛙。 根据上述初始蛙跳规则，第 ｋ 个青蛙族群中最差蛙的更新公式为： Ｄｋ ＝ ｒ × （Ｐ ｂ ｋ － Ｐ ｗ ｋ ） （１） Ｐ ｎｅｗ＿ｗ ｋ ＝ Ｐ ｗ ｋ ＋ Ｄｋ， － Ｄｍａｘ ≤ Ｄｉ ≤ Ｄｍａｘ （２） 式中： ｋ 表示是第几个族群，且 １ ≤ ｋ ≤ ｍ ； ｒ 为［０， １］的随机数； Ｄｋ 为第 ｋ 个族群最差蛙移动的步长； Ｐ ｎｅｗ＿ｗ ｋ 为第 ｋ 个族群最差蛙更新后新位置； Ｄｍａｘ 为蛙 的最大跳动步长。 若执行更新策略（１）和（２）后， Ｐ ｎｅｗ＿ｗ ｋ 对应的适 应值优于 Ｐ ｗ ｋ 对应的适应值，则用 Ｐ ｎｅｗ＿ｗ ｋ 取代 Ｐ ｗ ｋ ；否 则采用 Ｐｇ 代替式（１）中的 Ｐ ｂ ｋ ，重新更新 Ｐ ｎｅｗ＿ｗ ｋ 。 若 重新执行更新后， Ｐ ｎｅｗ＿ｗ ｋ 对应的适应值优于 Ｐ ｗ ｋ 对应 的适应值，则用 Ｐ ｎｅｗ＿ｗ ｋ 取代 Ｐ ｗ ｋ ；否则采用式（３）随机 产生一个新的蛙代替 Ｐ ｗ ｋ 。 Ｐ ｗ ｋ ＝ ｒ × （Ｏｍａｘ － Ｏｍｉｎ ） ＋ Ｏｍｉｎ （３） 式中： Ｏｍａｘ 和 Ｏｍｉｎ 分别表示算法搜索范围的最大值 和最小值。 重复以上的更新操作，直至满足事先设定的族 群内的算法迭代次数。 当所有族群的局部深度搜索 完成以后，进行全局信息交换。 局部深度搜索和全 局信息交换两阶段交替进行，直到满足相应的结束 条件。 ２ 广义中心混合蛙跳算法 ２．１ 广义中心策略 在群智能算法中，随着进化的进行，全局极值将 会越来越接近最优解。 搜索结束后，全局极值将位 于最优解的邻近区域。 与此同时，由于群智能算法 的随机性，每个个体也分布在全局极值的邻近区域。 为了改善全局极值，使其更快向最优解靠近［１４］ ，Ｌｉｕ 等［１５］引入中心粒子。 中心粒子由群体的中心位置 形成，伴随于整个搜索过程，除不具有速度外，该粒 子具有与其他普通粒子相同的所有性质。 其产生的 方式如式（４）所示： ｘ ｓｃ ｄ ＝ ∑ Ｆ ｉ ＝ １ ｘ ｄ ｉ （４） 第 ３ 期 赵嘉，等：广义中心混合蛙跳算法 ·４１５·