一种人工鱼群蛙跳混合优化算法

姜慧楠， 张向锋

(上海电机学院 电气学院, 上海 201306)

人工鱼群算法(Artificial Fish Swarm Algori-thm, AFSA)，是一种根据鱼群觅食行为的优化算法[1]。算法以模仿自然界的鱼群寻食过程来求得问题的最优解，它最初的收敛速度较快，但是后期收敛速度慢，因此，适用于精度要求不高的寻优问题[2-3]。蛙跳算法(Shuffled Frog Leaping Algori-thm, SFLA)是一种新的结合了全局搜索和局部更新的元启发式协同搜索算法[4]。SFLA求解速度快且全局寻优能力强，但存在前期收敛速度慢的问题。

AFSA因具有收敛速度快、计算原理简单等优势，得到了国内外学者的广泛关注。文献[5]对适应度值最好的人工鱼利用最速下降法进行更新，提高鱼群的整体水平；文献[6]采用引入对称正态随机行为及自适应调整行为参数，使得系统的收敛速度更佳；文献[7]验证了一种基于DNA改进的AFSA；文献[8]将禁忌搜索策略融入到AFSA寻优过程中，并在求解车间调度问题中取得了比较好的结果；文献[9-10]采用对鱼群行为的改变，提高了AFSA的搜索速度。文献[11-12]为克服SFLA存在的问题，对全局及局部做出改进，提出一种改进的SFLA；文献[13-14]通过对步长公式的改变及引入影响因子的方法，提升了SFLA的搜索能力；文献[15-16]通过借鉴优化及搜索策略的思想，使得最差青蛙的位置趋向最佳，提高了SFLA搜索的速度。

针对SFLA在后期收敛速度慢、易陷入局部最优和精度低等问题，本文将结合AFSA前期收敛速度快和SFLA局部搜索能力强的优势，通过将两种仿生算法联合运用，提出一种人工鱼群-蛙跳混合优化算法(Artificial Fish Swarm Algori-thm-Shuffled Frog Leaping Algorithm, AFSA-SFLA)。

1 人工鱼群算法及蛙跳算法

1.1 AFSA基本原理

鱼群的主要行为包括鱼群初始化、觅食行为、聚群行为、追尾行为、随机行为[17]。其主要行为如下：

(1) 鱼群初始化。鱼群中的每一条人工鱼是在给定范围内产生的随机数组。

(2) 觅食行为。假设当前人工鱼的状况为Xi，在其感知的范围内随机选择一个状况Xj，如果求极大值问题，Yi为第i条人工鱼当前所在食物浓度(Yi

(3) 聚群行为。设当前人工鱼的状况为Xi，探究当前领域内(即di，jδYi(δ为拥挤度)，说明同伴中央有较多的食物且不太拥挤，则朝同伴中央的位置行进一步，否则实施觅食行为。

(4) 追尾行为。设当前人工鱼的状况为Xi，试探当前领域内(即di，jδYi，说明同伴Xj的状态有较多的食物且不太拥挤，则朝同伴的Xj的位置行进一步，否则实施觅食行为。

(5) 随机行为。随机行为的实现比较简单，就是在视线中随机抉择一个情况，然后向该方向行进，即Xi的下一个动作为

X′i=Xi+r·V

(1)

式中：r是[-1，1]区间的随机数。

1.2 SFLA基本原理

SFLA是模拟青蛙在寻食的过程当中，青蛙群体通过按子群分类进行信息交换的进展，将全局搜索与子群局部搜索相结合，使算法朝着全局最优解的方向进化[18]。

(1) 全局搜索。全局搜索的布置如下：① 设置SFLA参数种群分组数m，每组青蛙包含的青蛙个数n，组内迭代次数Ne，最大、最小步长分别为swmax、swmin，种群总的进化代数N′max，青蛙位置的最大、最小值分别为Pmax、Pmin；② 随机初始化青蛙的种群，共生成F只青蛙，简记为P={P1，P2，…，PF}，其中Pi代表第i个解(0≤i≤F)，Pi={Pi1，Pi2，…，Pid}，d为解的维数，每一只青蛙代表着一种可行的解；③ 设Ff(Pi)为适应度函数，计算P中的每一只青蛙的适应度值，并将其进行降序处理，同时将第一个适应度值所对应的Pi记录为全局最优青蛙gx，并将排序后的青蛙放置P中；④ 将P中的F只青蛙，分成m组，每一组包含n只青蛙。将P中第1只青蛙放置第一组，依次第m只青蛙放置第m组。第m+1只青蛙放置第1组，依次第m+m只青蛙放置第m组，依次共循环n次，F只青蛙分组完成；⑤ 每个子群执行子群局部搜索，具体步骤见局部搜索；⑥判别是不是达到了最大迭代次数N′max，若达到了则算法结束，反之，重新混合所有的青蛙，执行步骤③。

(2) 局部搜索。局部搜索的布置如下：① 设j=1，用于记录每组内的迭代次数；② 关于每一组青蛙适应度值按降序排序，pb代表着每一组的最优青蛙，pw代表着每一组的最差青蛙；③ 组内更新，利用式(2)计算最差青蛙的移动步长sw1，若Ff(pwnew)>Ff(pwold)，执行步骤⑥，否则执行步骤④；

sw1=r·(pb-pw)swmin≤sw1≤swmax

(2)

pwnew=pwold+sw1

(3)

④ 全局最优更新。利用式(4)计算最差青蛙的移动步长sw2，若Ff(pwnew)>Ff(pwold)，执行步骤⑥，不然执行步骤⑤；

sw2=r·(gx-pw)swmin≤sw2≤swmax

(4)

pwnew=pwold+sw2

(5)

⑤ 随机更新。利用式(6)计算最差青蛙的移动步长sw3；

sw3=Pmax·r(1，d)swmin≤sw3≤swmax

(6)

pwnew=pwold+sw3

(7)

⑥ 将pwnew代替pwold，判别j>Ne是否成立，若成立则一组的局部搜索完成，反之，j=j+1，执行步骤②。

图1 混合算法流程图

2 人工鱼群蛙跳混合优化算法

针对AFSA和SFLA算法优缺点，本文提出一种AFSA-SFLA，该算法首先采用AFSA收敛速度快的优势快速寻找到待求解参数全局最优解所在区域。后期为SFLA利用前期AFSA的迭代结果，进行SFLA的初始化。AFSA-SFLA的具体流程如图1所示。具体步骤如下：① 设定主要初始参数，在给定的规模内初始化鱼群；②i=1作为一个循环变量来循环记录人工鱼的个数，人工鱼的数目为N；③ 鱼群执行聚群行为得到(X1，Y1)，执行追尾行为得到(X2，Y2)；④ 若Y1>Y2则Xi=X1，不然Xi=X2；⑤ 判别i>N是否成立，若成立执行步骤⑥，不然i=i+1，执行步骤③，gen=gen+1；⑥ 判别gen>Nmax是否成立，若成立则执行步骤⑦，反之，执行步骤②；⑦ 切换至SFLA，采用AFSA的最后一次迭代产生的人工鱼群进行SFLA的初始化，设置SFLA参数种群分组数m、每组青蛙包含的青蛙个数n、组内迭代数Ne、最大步长swmax、种群总的进化代数N′max，青蛙位置最大、最小值分别为Pmax、Pmin，循环变量ii=1。其中特意要说明的是初始化青蛙种群时，将AFSA迭代后的结果，取占取青蛙种群个数的L倍赋值给青蛙种群(0N′max是不是成立，若成立则输出参数最优值，不然ii=ii+1执行步骤⑧。

3 仿真实验与分析

本文采取Rastrigin函数、Griewank函数和Rosenbrock函数作为基准函数，这3个函数都具有数个局部最小值点和一个全局最小值点，可以很好地测验算法规避局部极值搜索全局最优的能力，标准测试函数如表1所示。

3.1 参数设置与测试函数

实验中主要参数设置如下：人工鱼的数目fishnum=100，最多试探次数try_number=100，最大步长step=0.1，蛙跳组内迭代次数Ne=25，种群分组数m=10。本实验的仿真软件如下：Intel i3 CPU 2.40 GHz，RAM 4.00 GB，Window 2007操作系统，MatLab2016b。

表1 标准测试函数

3.2 仿真结果分析

3.2.1 固定迭代次数下算法求解精度对比 采用不同的维数d消除算法的随机性干扰，在维数d为10和20时，对每一个测试函数分别用SFLA、AFSA-SFLA各自进行20次实验，仿真结果如表2所示。图2～图7为3个基准测试函数在不同维数下的优化结果图，其中横轴为迭代的次数，纵轴为log化的函数最优解。

表2 3种基准测试函数仿真数据结果

图2 Griewank函数在d=10时的进化曲线

图3 Griewank函数在d=20时的进化曲线

图4 Rosenbrock函数在d=10时的进化曲线

图6 Rastrigin函数在d=10时的进化曲线

图7 Rastrigin函数在d=20时的进化曲线

由表2可以看出，当维数d相同时，AFSA-SFLA的寻优结果优于单独SFLA的寻优结果。当维数d由10增大至20时，对Griewank函数，SFLA平均寻优结果由1.106 29增大至2.256 83，增大了2.04倍，AFSA-SFLA平均寻优结果由0.000 70增大至0.015 42，增大了22倍。当维数d由10增大至20时，对Rosenbrock函数，SFLA平均寻优结果由10.054 70增大至87.308 12，增大了8.6倍，AFSA-SFLA的平均寻优结果由3.574 68增大至7.456 81，增大了2.08倍，说明AFSA-SFLA相对SFLA对该函数的维数适应性更好。当维数d由10增大至20时，对Rastrigin函数，SFLA平均寻优结果由0.167 38增大至4.361 75，增大了26倍，AFSA-SFLA的平均寻优结果由1.03×10-4，增大至0.102 65，增大了996倍，虽然AFSA-SFLA增大的倍数较大，但是AFSA-SFLA的求解精度优于SFLA的求解精度。

由图2可知，对于Griewank函数，SFLA在后期迭代效果比较明显，前期迭代的效果不佳，AFSA-SFLA相对SFLA能快速地在其前期找到可行解，并于迭代70次左右收敛。由图4和图5可知，对于Rosenbrock函数在维数为20时，SFLA的平均寻优曲线接近直线，开始就陷入局部最优，全局寻优能力不强。由图6和7可以看出，对于Rastrigin函数，AFSA-SFLA在前期寻优结果明显，SFLA收敛慢且平均寻优结果远大于AFSA-SFLA的寻优结果。

综合图2～7可知，SFLA的寻优结果要远小于AFSA-SFLA的寻优结果，且在高纬数时更易陷入局部最优解，而AFSA-SFLA能更快地找到全局最优解所在的区域，迭代速度快，寻优结果更佳。需要指出的是AFSA-SFLA前段使用AFSA，并将AFSA最后一次迭代产生的人工鱼群按照适应度值大小降序排列，取前一定比例赋值给青蛙种群，使得青蛙种群更接近最优范围，因而其收敛曲线在前期能快速的找到最优解所在的区域，且迭代较为缓慢。

3.2.2 指定精度下算法迭代次数对比 表3为AFSA-SFLA在指定精度下求解基准函数迭代次数的对比，其中成功率是指算法达到指定求解精度的实验次数除以总实验次数20。Griewank函数、Rosenbrock函数、Rastrigin函数指定精度分别为10-1、10、10-1，最大迭代次数为300次，即算法迭代300次仍未达到指定精度时，表示迭代失败。

表3 指定精度下算法迭代次数对比

从表3中可以看出，在指定收敛精度下，对Griewank函数SFLA算法达到指定精度的成功率只有5%，平均迭代次数为263次，对Rosenbrock函数SFLA算法达到指定精度的成功率只有66.67%，平均迭代次数为156次，对Rastrigin函数SFLA算法未能达到指定精度，平均迭代次数为300次。AFSA-SFLA对3个基准测试函数成功率均为100%，并且迭代次数比SFLA迭代次数少很多。

以上仿真结果分析表明，在指定精度下，AFSA-SFLA的成功率、稳定性和计算效率均比SFLA算法有一定优势。

3.2.3 与他算法寻优结果对比分析 粒子群算法(Particle Swarm Optimization, PSO)的参数设置为速度更新参数C1=1.494 45、C2=1.494 45，种群规模Spop=100，AFSA及AFSA-SFLA的参数设置同3.1小节的参数设置一样。在d维数为10时对于每一个测试函数均采用AFSA、PSO、AFSA-SFLA各自进展20次试验，仿真数据如表4所示。

由表4中的仿真数据能看出，对于Griewank函数，AFSA-SFLA的平均寻优结果为0.000 70，PSO的平均寻优结果为0.004 01，AFSA的平均寻优结果为0.083 99，AFSA-SFLA的平均寻优结果是PSO的平均寻优结果的5.74倍，是AFSA的平均寻优结果的119.48倍；对于Rosenbrock函数，AFSA-SFLA的平均寻优结果为3.574 68，PSO的平均寻优结果为9.659 31，AFSA的平均寻优结果为11.326 70，AFSA-SFLA的平均寻优结果是PSO的平均寻优结果的2.70倍，是AFSA的平均寻优结果的3.17倍；对于Rastrigin函数AFSA-SFLA的平均寻优结果为1.03×104，PSO的平均寻优结果为5.912 86，AFSA的平均寻优结果为49.499 70，AFSA-SFLA的平均寻优结果是PSO的平均寻优结果的5.74×104倍，是AFSA的平均寻优结果的4.806×105倍。由此可以看出在维数相同的情况下AFSA-SFLA的寻优精度是最小的，寻优能力是较强的。

4 参数L值对AFSA-SFLA的影响分析

初始化青蛙种群过程中，将AFSA最后一次产生的人工鱼群依据适应度值大小降序排序，取占青蛙种群个数的L倍赋值给青蛙种群，作为初始化青蛙种群的一部分，剩余青蛙种群则依照常规的方法进行青蛙的初始化，L为采用人工鱼群初始化青蛙的个数占青蛙种群总个数的比例。分析不同比例对AFSA-SFLA所带来的影响，分别取L为0.3、0.5、0.7时对测试函数进行优化实验，函数参数设定同3.1节参数设定一样，其中d为20，每组进行20次实验，图8～图10给出了L值不同的情况下，AFSA-SFLA对测试函数的平均优化结果。

图8 L取值不同时对Griewank函数的影响

图9 L取值不同时对Rosenbrock函数的影响

图10 L取值不同时对Rastrigin函数的影响

由图8可知，对Griewank函数，L为0.5时，平均寻优优化结果最好，且L为0.3时在迭代40次左右收敛，而L为0.5时在迭代90次左右仍有迭代的趋势。由图9可知：对Rosenbrock函数L为0.3时迭代效果最好，且平均寻优结果最好。由图10可知，对Rastrigin函数L为0.7时平均寻优结果最好，但L为0.5时的迭代效果是较好的。由此可见应根据不同的目标函数选取合适的L值。

5 结 论

为改善SFLA前期收敛速度慢及易陷入局部最优的问题，本文提出了一种人工鱼群-蛙跳混合优化算法。算法前期采用ASFA前期搜索速度快的优势，迅速找到可能的最优解，后期切换至SFLA，初始化青蛙种群时，将ASFA迭代后的结果，取一定比例赋值给青蛙种群，提高了青蛙种群的质量。通过与ASFA、SFLA、PSO 3种算法的比较与分析验证了混合算法能有效的避免陷入局部最优，且优化精度高。分析混合算法中初始青蛙种群中前期AFSA迭代结果所占的比例对混合算法的影响，结果表明：不同L值对函数的影响不同，故应根据不同的目标函数选择不同的L值。