一种利用动态搜索策略的混合蛙跳算法

姜建国， 张丽媛， 苏 仟， 邓凌娟， 刘梦楠

(西安电子科技大学 计算机学院，陕西 西安 710071)

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)是一种较新的基于群体智能的元启发式全局优化算法，由Eusuff和Lansey于2003年受青蛙觅食过程的启发而提出[1]．该算法结合了模因算法(Memetic Algorithm，MA)和粒子群算法(Particle Swarm Optimization，PSO)两者的优点，具有结构简单、收敛速度快和全局寻优能力强等特点[2]．但在标准SFLA中，初始种群通过随机方式产生，种群分布不是很均匀;局部更新策略中，子群当前最差值对其进化行为的影响在进化过程中恒定不变，使得种群在迭代后期需要多次迭代才能收敛到全局最优;随着进化代数的增加，算法进化速度会降低甚至停滞，陷入早熟．

文献[3-5]均对算法进行了一些改进．其中，文献[3]用基于对立学习的策略产生初始种群，提高了候选解的质量，但是SFLA与差分进化算法的交替搜索在一定程度上增加了算法的执行时间，降低了算法的执行效率；文献[4]在子群局部搜索中引入搜索加速因子，提高了算法的寻优能力，但改进后的局部搜索算法本质上仍为线性搜索算法，不利于算法快速收敛于最优解；文献[5]在基本蛙跳算法的全局搜索过程中加入自适应混沌变异操作，提高了算法的寻优能力．但是当求解问题的维数增加时，计算量与之成正比，降低了算法的执行效率．

为此，笔者综合考虑初始化、局部搜索和全局搜索，提出了一种利用动态搜索策略的混合蛙跳算法(Shuffled Frog Leaping Algorithm using Dynamic Searching Strategy，DSFLA)，即通过随机化均匀设计方法[6]构造初始种群，使算法的初始种群能更均匀地分布于可行域中；引入影响因子，动态地改变子群当前最差值对其进化行为的影响，使算法快速收敛到全局最优解；根据相邻两次混合迭代后种群的适应度方差差值，判断种群是否陷入早熟，并通过对全局最优值微扰，使算法跳出局部最优．实验结果表明，DSFLA既能提高收敛精度，又能加快收敛速度，对于经典的评价优化算法执行效率的测试函数，均取得了比较好的结果．

1 标准SFLA

1.1 算法描述

混合蛙跳算法是一种受自然生物模仿启示而产生的群体进化算法，它模拟青蛙群体寻找食物时，按子群分类进行信息交换的过程，将全局搜索与子群局部搜索相结合，使算法朝着全局最优解的方向进化[1]．

在SFLA中，种群由虚拟的青蛙组成，每只青蛙代表1个候选解．种群被分成多个子群，每个子群包含一定数量的青蛙，称为1个memeplex．不同的memeplex可以看做是具有不同文化的青蛙子群，其中每只青蛙都有自己的文化，同时其行为又会受到其他青蛙行为的影响．每个memeplex内部执行局部搜索，在已定义的局部搜索次数结束后，所有的memeplex被混合，形成新的种群，使得各个memeplex间的信息得到全局交换．局部搜索和全局信息交换交替进行，直到满足收敛条件(一定的收敛精度或最大迭代次数)为止．

1.2 求解无约束函数优化问题的步骤

(1) 初始化．对于一个D维优化问题，在其可行域Ω⊂RD中随机生成P个候选解，记为初始种群S= (X1，X2， …，XP)，用Xi= (xi1，xi2， …，xiD)表示第i(1≤i≤P)个候选解．

(2) 子群划分．计算每个候选解的适应度值f(Xi)(即目标函数值)，并按降序排序，然后将其分到M个子群中．具体方法为：第1个候选解分到第1个子群中，第2个候选解分到第2个子群中，第M个候选解分到第M个子群中，第M+1 个候选解分到第1个子群中，第M+2 个候选解分到第2个子群中，依此完成P个候选解的分组．

(3) 子群局部搜索．设一个子群中的最好青蛙为Xb，最差青蛙为Xw，整个种群中的最好青蛙为Xg．对每个子群进行局部搜索，即对子群中的Xw进行更新，更新策略如下:

其中，Di是步长更新值，int[x]是对x取整；r为(0， 1)之间的随机数，其有效位依所计算的问题和仿真环境而定；Dmax是允许青蛙移动的最大距离．

(4) 全局信息交换．当各个子群完成局部搜索后，混合所有的子群，重复执行步骤(2)、(3)和(4)，直到满足终止条件为止．

2 改进的SFLA

针对标准SFLA中存在的问题，对初始种群的构造、局部搜索更新策略和早熟收敛均进行了改进，提出了一种改进的混合蛙跳算法．

2.1 基于随机化均匀设计方法的初始种群的构造

SFLA是一种基于种群的元启发式全局优化算法，初始种群的好坏对该算法的搜索性能具有非常重要的影响．当种群中的青蛙在其搜索空间分布不均匀时，会降低SFLA的全局搜索能力．经典SFLA中，初始种群是随机生成的，分布并不均匀．针对此问题，文中使用随机化均匀设计方法[6]构造初始种群．随机化均匀设计(Random Uniform Design，RUD)是用一般生成向量代替均匀设计中的本原根产生随机化均匀设计点集，许多随机化均匀设计点集的偏差明显小于原有均匀设计，因而具有更好的代表性．因此，文中采用随机化均匀设计方法构造更均匀的初始种群．

文献[6]将随机化均匀设计方法应用于改进遗传算法，取得了比较理想的结果．文中引用此方法，并根据混合蛙跳算法的具体情况进行如下调整：将文献[6]3.3节中利用随机化均匀设计所得的元素xij映射到SFLA问题的可行域中，则第i个候选解(记为aij)的第j维的值为

aij=amin+xij(amax-amin) ，i=1，2，…，P，j=1，2，…，D,

其中，amax为可行域的上界，amin为可行域的下界．

图1(a)是在[0，1]2中用随机化均匀设计方法产生的 1 000 个点组成的点集，图1(b)是用随机方法产生的 1 000 个点组成的点集．由图1可以看出，随机化均匀设计方法相比于随机方法产生的点集更能均匀地分布在可行域中，有利于提高算法搜索到最优解的概率，为算法更快、更准确地搜索到全局最优解提供了条件．

图1 随机化均匀设计法与随机法效果对比

2.2 动态影响因子的引入

在标准SFLA的局部搜索策略中，子群当前最差值根据全局最优值或子群当前最优值生成步长更新值，并将此步长更新值与当前最差值进行求和，生成子群中最差值的更新值(见式(1)和式(2))，从而实现对子群中最差值的更新．在算法的整个迭代过程中，子群当前最差值对其更新值的影响恒定不变，即系数恒为1．此系数设置为1对应较大的更新值，能保证算法在迭代初期具有较强的全局搜索能力，进而不断搜索到新区域．但是随着迭代次数的增加，算法需要在最优解周围进行局部搜索，如果此时子群当前最差值对其更新值的影响仍然和算法迭代初期相同，算法可能会因为更新值过大而跳过最优值，因而需要执行很多次才能收敛到全局最优，从而导致算法在后期收敛速度不够理想．因此，可以考虑引入影响因子，动态地减小子群当前最差值对其更新值的影响．

文献[7]给出了一种更新公式，即Xneww=KXw+Di，-Dmax≤Di≤Dmax，并将其中的影响因子K设为从0.9到0.4线性地减小，即K= 0.9- (0.9- 0.4)t/tmax，其中，t是当前迭代次数，tmax是最大混合迭代次数．可以看出，当迭代次数不断增加时，K线性地减少．该方法使得SFLA在搜索初期具有较强的全局搜索能力，在后期具有较强的局部搜索能力．线性递减意味着递减速率在迭代过程中是恒定的，但是考虑到算法的寻优原理，迭代初期需要较慢的迭代速率，以保证算法能展开充分的全局搜索．为此，在综合考虑提高搜索效率并改善早熟收敛的情况下，这里采用余弦函数动态地改变子群当前最差值对其更新值的影响，即

Xneww=c1KXw+c2Xw+Di， -Dmax≤Di≤Dmax,

(3)

其中，影响因子K=cos((t/tmax)(π/2))；c1和c2为调节参数，且有c1+c2=1，当取c1>c2时，动态调节因子K对Xw的影响较大；当取c1

余弦函数在[0，π/2]区间内非线性地单调递减，从而满足更新值在迭代初期较大、而在迭代后期以较小的速率单调递减的要求；而且在此区间内开始时，递减速度较慢，有利于种群在迭代初期充分地展开全局搜索，而不会迅速减小到很小以至于算法快速进入局部搜索而产生早熟收敛现象．因此，采取动态的余弦函数来调整当前子群最差值对更新值的影响，对混合蛙跳算法收敛速度的提高有显著的推进作用．

2.3 基于群体适应度方差的局部最优的判断

文献[8]在粒子群算法中利用群体适应度方差δ2小于某个阈值c来判断粒子群是否发生早熟收敛现象．文中通过进一步实验发现，当混合蛙跳算法陷入局部最优时，群体适应度方差也会在数次迭代过程中保持相对稳定．据此，这里通过计算相邻两次混合迭代后群体适应度方差δ2的差值，来判断种群是否出现早熟收敛现象．

2.4 局部最优的处理

在标准混合蛙跳算法中，局部更新策略根据当前子群最优值或全局最优值来更新子群中的最差值，这使得算法能够朝着最优值进化，因而能在短时间内收敛到全局最优值[9]．但如果当前最优值是局部最优，则算法就会在数次更新后陷入早熟收敛，而很难收敛到全局最优值，特别是对一些具有许多局部最优解的复杂多峰函数，为全局最优解的计算带来了很大的困难．

早熟收敛的处理方法一般分为两种：早熟收敛预防与早熟收敛后的再处理，即重构种群多样性[10]．早熟处理相对于设计方法复杂的早熟收敛预防显得简单．文献[10]将全局最优值的微扰应用于解决粒子群优化算法的早熟收敛，取得了很好的效果．因此，可采用对陷入早熟的青蛙种群的全局最优值微扰，帮其跳出局部最优．其基本思路是：根据2.3节给出的方法判断种群是否出现早熟收敛现象，如果是，则对当前全局最优值进行微扰．这种改进在后面的测试中显示出了良好的性能．

微扰公式为

(4)

3 仿真与结果分析

3.1 仿真设置

为了检验文中算法的性能，将DSFLA与文献[2]的改进算法(Shuffled Frog Leaping Algorithm Using Niche Technology，NSFLA)和经典混合蛙跳算法SFLA进行对比．

实验选取5个典型的函数优化问题：Sphere[11]，Rosenbrock[11]，Rastrigin[11]，Griewank[11]和Schaffer’s f7[5]进行测试．其中，Sphere是简单的单峰函数；Rosenbrock是非凸的病态函数；Rastrigin，Griewank和Schaffer’s f7是复杂的多峰函数．参数设置如表1所示．适应度值即为测试函数的函数值f(x)．对于每个测试函数，算法独立运行20次取平均值，仿真从平均求解精度和求解成功率两方面对3个算法进行对比，涉及的公共参数设置如下:

(1) 青蛙移动的最大步长Dmax: 根据文献[1]将其设置为可行域的界×45%．

(2) 对于式(3)中的c1和c2，实验中取值c1=0.6，c2=0.4．

(3) 通过实验分析，2.4节中的扰动系数q取值为[0.5， 3]时，具有良好的扰动效果，这里取q=1.3．

表1 文献[2]中初始条件的设置

注：种群规模P=20；子群个数M=5；局部搜索次数N=10；混合迭代次数G=100．

3.2 仿真结果与分析

3.2.1 算法求解精度对比

对于每个测试函数，算法独立运行20次，表2是算法求解精度的对比结果．由表2可以看出，对于Sphere函数，DSFLA的平均值在数量级上比SFLA和NSLFA均有较明显的提高;对于非凸的病态函数Rosenbrock，DSFLA得到了更好的结果；对于Rastrigin和Griewank函数，DSFLA收敛到了真正的全局最优解0；对于Schaffer’s f7函数，DSFLA也较另外两种算法有更理想的结果．由此可得，DSFLA具有更高的收敛精度．

表2 算法求解精度对比

3.2.2 算法求解成功率对比

指定各测试函数的收敛精度如表3所示．为了避免算法因局部收敛而使程序无法结束，设最大迭代次数G=200，如果在200次迭代内算法无法结束，则认为算法无法收敛到指定的精度．算法独立运行20次后，结果如表4所示．表4中成功率定义为: 成功率=(达到精度的次数/总次数)×100%．

表3 函数收敛精度设置

由表4可以看出，除了Rosenbrock函数之外，DSFLA全部以100%的成功率收敛到了相应的精度，且平均进化代数较少．虽然DSFLA的平均运行时间大于文献[2]中的NSFLA的平行运行时间，但是较标准的SFLA还是有所改善．

综上分析，文中提出的DSFLA在求解精度和收敛效果两方面均获得了比较满意的结果．尤其对于具有较多局部最优值的问题，更体现出了DSFLA的优越性．

表4 固定目标精度下20次实验结果对比

4 结 束 语

分析了混合蛙跳算法的优化原理，针对原算法中存在的初始种群不均匀、局部更新策略中存在的收敛速度慢以及算法执行后期易陷入局部最优等问题，提出了一种改进的混合蛙跳算法．通过随机化均匀设计方法构造更加均匀的初始种群，提高了算法搜索到全局最优解的概率;在局部更新策略中引入影响因子，动态地改变子群当前最差值对其进化行为的影响，提高了算法的收敛速度;根据群体适应度方差判断种群是否陷入局部最优，并通过对全局最优值微扰，帮其跳出局部最优，处理了早熟收敛，提高了算法的收敛精度．仿真结果表明，DSFLA在求解精度和收敛效果两方面都有所提高，取得了较好的结果．

[1] Eusuff M, Lansey K, Pasha F. Shuffled Ffrog-leaping Algorithm: a Memetic Meta-heuristic for Discrete Optimization[J]. Engineering Optimization, 2006, 38(2): 129-154.

[2] 姜建国, 李锦, 龙秀萍, 等. 采用小生境技术的混合蛙跳算法[J]. 计算力学学报, 2012, 29(6): 960-965.

Jiang Jianguo, Li Jin, Long Xiuping, et al. Shuffled Frog Leaping Algorithm Using Niche Technology [J]. Chinese Journal of Computational Mechanics, 2012, 29(6): 960-965.

[3] 赵鹏军, 邵泽军. 一种新的改进的混合蛙跳算法[J]. 计算机工程与应用, 2012, 48(8): 48-50.

Zhao Pengjun, Shao Zejun. Novel Improved Shuffled Frog Leaping Algorithm [J]. Computer Engineering and Applications, 2012, 48(8): 48-50.

[4] Elbeltagi E, Hegazy T, Grierson D. A Modified Shuffled Frog-leaping Optimization Algorithm: Applications to Project Management[J]. Structure and Infrastructure Engineering, 2007, 3(1): 53-60.

[5] 葛宇, 王学平, 梁静. 自适应混沌变异蛙跳算法[J]. 计算机应用研究, 2011, 28(3): 945-947.

Ge Yu, Wang Xueping, Liang Jing. Adaptive Chaotic Mutation Shuffled Frog Leaping Algorithms[J]. Application Research of Computers, 2011, 28(3): 945-947.

[6] 任哲, 周本达, 陈明华. 一种基于随机化均匀设计点集的遗传算法用于求解 MVCP[J]. 模式识别与人工智能, 2010, 23(2): 284-288.

Ren Zhe, Zhou Benda, Chen Minghua. A Genetic Algorithm Based on Random Uniform Design Point Set for Solving MVCP[J]. Pattern Recognition and Artificial Intelligence, 2010, 23(2): 284-288.

[7] Luo P, Lu Q, Wu C. Modified Shuffled Frog Leaping Algorithm Based on New Searching Strategy[C]//7th International Conference on Natural Computation. Piscataway: IEEE, 2011: 1346-1350.

[8] 吕振肃, 侯志荣. 自适应变异的粒子群优化算法[J]. 电子学报, 2004, 32(3): 416-420.

Lü Zhenxiao, Hou Zhirong. Particle Swarm Optimization with Adaptive Mutation[J]. Acta Electronica Sinica, 2004, 32(3): 416-420.

[9] 巩敦卫, 朱美强, 郭西进, 等. 一种新的基于混沌变异解决早熟收敛的遗传算法[J]. 控制与决策, 2003, 18(6): 686-689.

Gong Dunwei, Zhu Meiqiang, Guo Xijin, et al. Genetic Algorithm Based on Chaotic Mutation to Deal with Premature Convergence[J]. Control and Decision, 2003, 18(6): 686-689.

[10] 金荣洪, 袁智皓, 耿军平, 等. 基于改进粒子群算法的天线方向图综合技术[J]. 电波科学学报, 2006, 21(6): 873-878.

Jin Ronghong, Yuan Zhihao, Geng Junping, et al. The Pattern Synthesis of Antennas Based on a Modified PSO Algorithm[J]. Chinese Journal of Radio Science, 2006, 21(6): 873-878.

[11] 姜建国, 田旻, 王向前, 等. 采用扰动加速因子的自适应粒子群优化算法[J]. 西安电子科技大学学报, 2012, 39(4): 93-101.

Jiang Jianguo, Tian Min, Wang Xiangqian, et al. Adaptive Particle Swarm Optimization via Disturbing Acceleration Coefficents [J]. Journal of Xidian University, 2012, 39(4): 93-101.