基于层级交流机制的混合蛙跳算法
2019-12-20张文康李佳玲
张文康，李佳玲
(1.江苏大学附属医院 信息科，江苏 镇江 212001；2.江苏大学 计算机科学与通信工程学院，江苏 镇江 212013)
0 引 言
混合蛙跳算法(SFLA)[1-2]是一种新型的群智能优化算法，它具有结构简单、易于实现、全局搜索能力强的特点，因此被广泛应用。但是，SFLA算法[3-11]和其他的群智能优化算法一样，在进化后期多样性降低，收敛速度慢，易于陷入局部最优。因此，国内外众多学者对其进行了大量的研究与改进。吕立霞等[12-13]将混沌优化策略加到SFLA中，提高了算法的收敛速度和精度。王俊等[14]在SFLA的基础上加入了讨论机制，并且根据迭代次数动态改变，增强了后期的种群多样性，减少了其陷入局部最优的概率。王娜等[15]前期根据差分进化的思想利用种群中的其他个体有用信息来更新最差个体；后期则利用最好个体来进行交叉变异，同时通过外部归档集来保留种群的多样性，这在一定程度上提高了算法的寻优能力。李俊等[16]则是将SFLA和多种群粒子群算法的优势互补，在多种群粒子群寻优的基础上，将各个子群中的最优粒子组合后运用蛙跳思想进行更新，这在一定程度上改善了算法的整体寻优性能。戴月明等[17]将子群中的平均个体引入到最差个体的更新中，另外让子群中的较差个体向邻近子群中的最优个体学习，再在全局迭代过程中采取精英群自学习机制。
以上算法虽然对SFLA有一定的改进，但并没有考虑到SFLA子群中的那些非最差个体和非最优个体的寻优能力。本文提出了一种基于层级交流机制的SFLA。对子群中非最差个体和非最优个体进行层级交流学习，使得各个子群在局部搜索时也能进行全局的信息交流，提高了解的精度。为保障算法后期的搜索能力，用子群中最差个体的自旋来代替原本的第3次随机跳跃。最后，通过仿真测试表明了新算法的有效性。
1 混合蛙跳算法
SFLA模拟的是青蛙按族群划分所进行的觅食行为，主要基于组内最差青蛙的三级跳跃的局部搜索能力以及全局混合重排的全局搜索能力。其基本思想是：在搜索空间内随机初始化F个点(青蛙)作为初始时候的种群。根据目标函数计算每个青蛙所对应的目标函数值后，按照目标函数值将青蛙从优到劣降序排列；然后将青蛙分配到m个子群，其分配规则是这样的，排在第1个的青蛙进入第1个子群，排在第2个的青蛙进入第2个子群，排在第3个的青蛙进入第3个子群，以此类推，第m个青蛙进入第m个子群，第m+1个青蛙进入第1个子群，第m+2个青蛙进入第2个子群，直到所有的青蛙分配完毕。
初始化及分配完毕之后进入局部搜索状态，混合蛙跳算法的局部搜索发生在每个子群之中。首先找到子群内的最优位置Pb以及最差位置Pw。对Pw进行第1次跳跃是根据下式而来的：
式中:i表示第i个子群;Di是移动步长，rand()表示[0,1]之间的随机数;Dmax表示最大的移动步长。如果得到的新的Pwnew个体优于原来的Pw，则用Pwnew来替换Pw，否则进行第2次跳跃，第2次跳跃是用全局最优个体Pg来代替公式中的Pb，再代入式(1)、(2)重新产生新的个体，如果这次产生的新个体优于Pw，则替换Pw；否则进行第3次跳跃，随机生成1个新个体来替换Pw。重复以上的操作直到所有子群均完成更新。
当所有子群完成其局部搜索后，将所有的青蛙重新混合后，再次按照目标函数值从优到劣进行排序，然后划分子群，对每个子群再进行局部搜索，直到满足相应的结束条件(达到相应的迭代次数或者相应的精度)。
2 改进的混合蛙跳算法
2.1 层级交流机制
SFLA主要是依据对子群中最差的个体进行3次跳跃来进行局部搜索。每次迭代对子群内其他个体没有任何操作，这会明显降低算法整体的收敛速度。对此，受差分进化思想以及多维学习思想启发而来，本文提出一种层级交流机制，对组内的非最优个体和非最差个体进行更新操作。具体为：在每组的迭代时，排在第2至倒数第2的个体的每一维度都有机会(以概率的形式)向排在其他子群的同一位置的个体学习。更新的概率如下：
p=0.8(k/subnum)
(3)
式中：k为该个体所在的列；subnum为每组的总数。对于每个个体而言，如果产生的随机数小于概率p，则用下式来更新；否则，不更新。
Xnew,h=Xnew,h+rand()·(frog1,h-frog2,h)
(4)
式中：frog1和frog2是从对应的列随机选出的2个个体；h代表个体的维度。
对于更新概率而言，如果要被更新的个体排在子群的前排，那么它本身的值就越接近最优值，那它被更新的概率就越小。然后计算选出的新个体的Xnew的目标函数值，若优于原来的，则替换。其伪代码如下所示：
在子群中：
Forn=2:subnum-1
Forh=1∶1∶D
If rand() Xnew=Xn+rand()*(frog1-frog2); Xnew1(1,h)=Xnew(1,h); else Xnew1(1,h)=Xn(1,h); End End If func(Xnew1) Xn=Xnew1; End End 在SFLA的局部搜索中，若更新最差个体第2次跳跃不成功，就会进入第3次跳跃模式，即随机初始化一个新的个体来替换最差个体。然而，这种操作并没有让最差个体的原有信息保留到下一次迭代，这会造成算法后期寻优速度变慢，多样性降低。因此，为了充分利用最差个体的原有信息，提出用下式来替换SFLA中的第3次跳跃，让最差个体进行自旋操作。 Pwnew,h=ch*Pwnew,h+Pwnew,h (5) 式中：Ch为自旋参数。 综上所述，基于层级交流机制的SFLA(IICSFLA)的流程图如图1所示，具体算法步骤如下。 图1 IICSFLA流程图 步骤1初始化F个青蛙，每个青蛙的维度是D，子群个数为m，子群内的个体总数为subnum，因此F=m·subnum，子群内的迭代次数为sub_iter_max,整体迭代次数为iter_max。 步骤2根据目标函数计算每个青蛙的目标函数值，并依据目标函数值从优到劣排序，根据之前提到的分配规则，将F个青蛙分配到m个子群中。 步骤3进行局部搜索，局部搜索分为两部分同时进行： (1)对每个子群中最差个体进行更新，首先使用式(1)、(2)进行第1次跳跃，若得出的新个体优于最差个体，则替换；否则，用全局最优位置去替换式(1)中的子群中的全局最优位置，代入式(1)中得出新的个体，若新个体优于最差个体，则替换；否则，根据式(5)产生1个新个体去替换最差个体。 (2)对于每个子群中的排在第2至倒数第2的个体而言，对于这种个体的每1维随机产生1个数，若小于式(3),则选取该列的其他子群中的两个对应的个体，利用式(4)产生该维度上的新值；若产生的随机数大于式(3)，则该维度上的值不发生改变。最后，根据自然界中优胜劣汰的规则，若产生的新个体优于原有个体，则替换；否则，不做替换。 步骤4若当前子群迭代次数小于子群最大迭代次数，则返回步骤3；否则，继续执行。 步骤5将所有子群中的青蛙重新混合，重复步骤2～4直至达到终止条件。 为验证所提出算法的性能，将本文算法IICSFLA与SFLA，Dmsfla[5]等改进算法进行对比。本文以6个常用的benchmark函数作为测试基准函数，这几个测试函数的全局最优解都是0，具体情况如表1所示。实验过程采用的是Matlab 2017b编程，在Intel(R)Core(TM)i7-5500U 中，Win10操作系统下进行大量实验仿真对比。其参数设置如下：整体迭代次数为400，组内迭代次数为10，总共有100个青蛙，分为10组进行实验。 表1 Benchmark 函数 表2为3种算法在10维情况下，独立运行100次的结果比较，表3为3种算法在30维的情况下，独立运行100次的结果比较。由表2、3可得，IICSFLA的寻优能力比SFLA以及DMSFLA要强。前3个测试函数是单峰测试函数，在相同的迭代次数下，IICSFLA最优，其次是DMSFLA，最后才是SFLA。后面3个是多峰测试函数，IICSFLA也能在取得较优的结果，尤其在f4测试函数上能够取得全局最优值。 图3，图4分别为IICSFLA、SFLA和DMSFLA在10维和30维下的收敛曲线图。从图中可以看出，对于大多数测试函数，IICSFLA的收敛速度都要比其他两个快，在测试函数f4中，IICSFLA能够快速地收敛到全局最优位置。 表2 3种算法在10维下的性能比较 表3 3种算法在30维下的性能比较 (a)f1 (b)f2 (c)f3 (d)f4 (e)f5 (f)f6 本文针对SFLA求解精度不高，易于陷入局部最优的缺点，提出了一种基于层级交流的混合蛙跳算法。该算法让子群内不参与迭代更新的个体进行纵向学习，增强了各个子群中的个体的信息共享，有利于寻找更优解。同时，用最差个体自旋机制来替换原本的第3次随机跳跃，保障了算法后期的搜索能力以及寻优速度，减少了其陷入局部最优的概率。实验结果也表明了所提出的算法的有效性。之后的研究想把改进的算法运用到实际的工程中，如对NP问题的求解，优化分类器等等。 (a)f1 (b)f2 (c)f3 (d)f4 (e)f5 (f)f62.2 最差个体自旋机制
2.3 改进后的算法流程
3 仿真实验及其分析
4 结 语
