一种改进的粒子群人工鱼群算法

陆俊明， 张向锋

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

群体智能行为是当今科学研究的一个热点。人工鱼群算法[1-4](Artificial Fish Swarm Algorithm, AFSA)和粒子群优化算法[5-7](Particle Swarm Optimization, PSO)都是群体智能算法[8]。AFSA跳出局部极值的寻优能力强，但迭代速度慢。PSO是模拟鸟类的觅食行为的仿生算法，具有快速收敛能力和简单可行等优点，但是在算法的寻优后期很难跳出局部最优值。文献[9-10]综合利用PSO可移植性强和AFSA全局寻优能力强的特点得到一种改进的算法；文献[11]利用最速下降法具有简单、运算速度较快的优势，提出了对精英加速的改进粒子群人工鱼群算法(Particle Swarm Optimization-Artificial Fish Swarm Algorithm, PSO-AFSA)；文献[12]在理论上证明PSO-AFSA的收敛性；文献[13]将PSO-AFSA应用于采煤机的破碎率优化。PSO-AFSA可以用于解决列车运行调度问题[14]以及机器人路径规划问题[15]等。该改进的PSO-AFSA具有更加稳定快速的寻优能力，克服了AFSA后期收敛速度慢，高维度求解精度不高等问题。

1 PSO原理

PSO模仿鸟群的行为来寻最优解[5]。适应度函数值代表粒子在求解过程中的状态结果。假设在D维的寻优空间存在由n个寻优粒子组成的种群，在第k次迭代后，其中：

第i个粒子位置状态为

第i个粒子速度为

第i个粒子历史最好点

第k+1次迭代的粒子的数学描述为

(1)

式中：k为迭代次数；c1和c2为惯性权重；ξ和η为在0到1之间内均匀分布的随机数；设置粒子的飞行速度的下界、上界的值为-Vmax和Vmax。

2 AFSA原理

在AFSA中，人工鱼有3种基本行为：觅食、聚群、追尾[1]。

2.1 觅食行为

(2)

2.2 聚群行为

(3)

式中，δ是拥挤因子。

2.3 追尾行为

(4)

3 PSO-AFSA原理

提出的PSO-AFSA综合利用PSO和AFSA的特性，根据粒子的适应度值大小筛选出精英鱼群与普通鱼群，若求解最大值，则利用PSO对适应度值较大的精英人工鱼群进行更新，在其内部进行nmax次循环，其余普通鱼群利用AFSA更新，每轮更新之后利用排序选出新的精英鱼群，直到满足规定的迭代次数。PSO粒子具有飞行速度和惯性权重两大属性，速度使人工鱼具备像粒子样的飞行功能，可以加快算法的收敛；惯性权重使人工鱼具备了承接先前速度的能力。设立精英鱼群可以结合两个算法的优点从而加快算法的收敛。PSO-AFSA计算流程如下：

(1) 随机初始化N条人工鱼，给定视野V，步长s，拥挤度因子δ，最大尝试次数Nt，外部最大迭代次数Nmax等参数；

(2) 计算每条人工鱼的适应度值Y，选出数量为Ne的精英鱼群Xe，其他人工鱼群为普通鱼群Xn，并寻找适应度值Y最大的人工鱼，记录在公告板Yb；

(3) 利用PSO更新Xe，在PSO内部进行nmax次寻优；

(4) 对普通鱼群进行聚群行为Fs和追尾行为Ff更新，选择适应度值Y较大的作为更新结果；

(5) 比较Y和Yb，判断适应度值Y有没有变大，如果变大则更新Yb，否则利用觅食算子Fp对Xn进行更新；

(6) 将更新后的Xe与Xn的适应度值与公告板Yb进行比较，若更大，则将其赋予公告板Yb；

(7) 当所有人工鱼进行更新完成之后，判断是否达到终止条件(终止条件为达到最大迭代次数)，达到终止条件后输出最优适应度函数值Yb，算法结束，否则转步骤(3)。

算法流程如图1所示。

图1 PSO-AFSA流程图

4 仿真结果与分析

本文用3个典型的多维度函数测试算法性能，这3个函数f(x)具有大量局部最小值，以及为0的全局最小值，利用算法寻找最小值，结果越接近0，说明算法的寻优能力越强。参数设置见表1，本文使用Matlab R2016a仿真，N为100，Nmax为1 000，当迭代达到Nmax时，算法输出最优解。

4.1 基准测试函数及参数设置

(1) Sphere函数

(5)

式中，x⊂[-10,10]。

表1 参数的设置

(2) Ackley函数

(6)

式中：x⊂[-32.768,32.768]；a=b=c=d=1。

(3) Griewank函数

(7)

式中，x⊂[-5,5]。

4.2 结果与分析

为了消除算法的随机性干扰，在维数D为10和20维时，对每个函数分别用AFSA、PSO-AFSA各自独立进行20次实验(见表2)。

由表2可知随着维数增大，AFSA与PSO-AFSA的寻优精度都大幅下降，但是PSO-AFSA的寻优精度始终远远优于AFSA。对函数Ackley，随着维数由10增大至20，AFSA的平均寻优结果由10.021 81增大至20.032 77，PSO-AFSA的平均寻优结果由0.152 39增大至0.305 02，均增大至2倍。对函数Sphere，随着维数由10增大至20，AFSA的平均寻优结果由2.258 39增大至6.082 99，PSO-AFSA的平均寻优结果由0.010 07增大至 0.036 33，均增大至3倍。综合Ackley和Sphere可知，随着维数增大，AFSA和PSO-AFSA的表现一致。但是对于函数Griewank，随着维数由10增大至20，AFSA的平均寻优结果由0.083 99增大至0.255 04，PSO-AFSA的平均寻优结果由0.004 29增大至0.008 65，AFSA的平均寻优结果增大至3倍，而PSO-AFSA的平均寻优结果增大至2倍，说明PSO-AFSA相对于AFSA在该函数下对维度变化适应性更好。图2～图7为3个目标函数在不同维数时的优化结果图，其中横轴为迭代次数，纵轴为log化的函数最优解。

根据图2和图5可以看出，对目标函数Sphere，PSO-AFSA较早地找到了最优值，AFSA在700次以后才收敛，收敛速度太慢。由图3和图6可看出，对目标函数Ackley，AFSA的效果不理想，一开始就陷入局部最优；由图4和图7可以看出，对目标函数Griewank，PSO-AFSA迭代100次前效果明显，AFSA的最终结果远大于PSO-AFSA；结合图2～图7可以看出在1 000次迭代情况下，AFSA寻优效果远小于PSO-AFSA，且AFSA更容易陷入局部最优解，AFSA在高维度的表现不佳，而PSO-AFSA在高维度寻优上迭代速度快，寻优结果更准确，有较大优势。

表2 3种算法仿真数据结果

图2D为10时Sphere函数进化曲线

图3D为10时Ackley函数进化曲线

图4D为10时Griewank函数进化曲线

图5D=20时Sphere函数进化曲线

图6D=20时Ackley函数进化曲线

图7D=20时Griewank函数进化曲线

为了深入研究人工鱼群的搜索过程，分析精英鱼群数对PSO-AFSA所起到的作用，在其他参数不变的情况下，分别采用精英鱼群数Ne为30、50和70 3种模式，利用PSO-AFSA进行20维寻优。由图8和图9可知，精英鱼群数为50时算法迭代效果较好；由图10可知，精英鱼群数为70时算法迭代效果较好。综合分析可知，为了平衡算法迭代效果，精英鱼群数不应过大也不应过小。随着算法继续迭代，不同比例的精英鱼群对算法结果的影响区别不大。

图8 精英鱼群数对Sphere函数的影响

图9 精英鱼群数对Ackley函数的影响

图10 精英鱼群数对Griewank函数的影响

5 结 语

针对AFSA在高维度寻优上表现不佳，提出了PSO-AFSA，并利用AFSA和PSO-AFSA两种算法对3个基准测试函数寻优。对比迭代图形和寻优结果，仿真结果表明：随着维度上升，PSO-AFSA和AFSA寻优精度都会下降，但PSO-AFSA相对于AFSA表现更稳定，且不同精英鱼群数对PSO-AFSA的影响较小，PSO-AFSA在收敛速度和结果都明显优于AFSA。