基于粒子群搜索策略的混合果蝇优化算法∗

2019-12-27郭德龙周锦程周永权

计算机与数字工程 2019年12期

郭德龙周锦程周永权

（1.黔南民族师范学院数学与统计学院都匀 558000）（2.黔南民族师范学院复杂系统与计算智能重点实验都匀 558000）（3.广西民族大学信息科学与工程学院南宁 530006）

1 引言

群智能优化算法是一种越来越受到从事这个领域研究的学者重视，2011年台湾学者潘文超针对果蝇的觅食行为展开研究和总结，在此基础上提出了果蝇优化算法［1～2］（Fruit Fly Optimization Algo⁃rithm，FOA），这一算法最大特点在于它的群体智能性。因为它是一个比较新的算法。虽然，FOA算法已成为数学函数极值、微调Z-SCORE模型系数等问题的可选方法之一［3］。关于果蝇优化算法的改进与应用发展主要由韩俊英等提出的动态双子群协同进化果蝇优化算法［4］、基于细菌趋化的果蝇优化算法［5］、自适应变异的果蝇优化算法［6］、以历史认知为基础的果蝇优化算法［7］、自动改变参数的果蝇优化算法［8］；王雪刚及其研究小组发明的基于优化算法的支持向量机参数优化在船舶操纵预报中的应用［9］；程慧等提出的基于混沌映射的混合果蝇优化算法［10］；侯越等提出的基于萤火虫优化的BP神经网络算法研究［11］；马超，董玲提出的果蝇优化算法（FOA）步长改进及其多元函数最优化方法［12］仍有缺点特别在求解精度和收敛速度方面的研究，所以对于FOA改进的研究是非常必要的。

FOA与其他的群智能优化算法相比较，算法简单容易理解和操作，参数的调整较少等特点。但是，该算法同样也存在一些不足，如算法容易陷入局部最优解级收敛速度慢等问题。基于以上不足本文给出一种基于混合变异的果蝇优化算法，该改进的果蝇优化算法在果蝇个体利用嗅觉搜索食物之随机方向距离上引入粒子群算法中的变异算子代替了原来的随机方向变异算子，目的在于使果蝇优化算法跳出局部最优和后期收敛速度慢，通过测试函数结果对比在收敛速度和求解精度上都有所提高。

2 标准果蝇优化算法

果蝇优化算法是一种模仿果蝇寻找食物的全局寻优的算法，该算法在实现上不难，需要调整的参数并不多，充分体现果蝇本身在感官知觉上优于其他物种的特点，尤其在嗅觉与视觉上，果蝇的嗅觉器官能很好地搜集漂浮在空气中的各种气味，甚至能嗅到40km以外的食物源，然后飞进食物位置后亦可使用敏锐的视觉发现食物与同伴聚集的位置，并且往该方向飞去。从以上果蝇寻找行为的特性，标准果蝇优化算法实现的步骤如下。

1）首先根据给定初始寻优的范围随机生成初始群体并且位置矢量用X_axis，Y_axis，给出果蝇的初始群体的规模，popsize，最大迭代次数maxgen。

2）采用随机的方法，设定食物位于果蝇的某个方向和某段距离上，RandomValue代表距离。

3）考虑到食物的准确地点是未知的，首先预测它和原点的距离是Dist，然后通过计算得到味道浓度判定值S和距离之间的关系互为倒数。

4）联立上式（3）以及味道浓度判定函数，那么就能够得到果蝇所处地方的味道浓度（Smelli）。

5）计算所有果蝇的味道浓度，进而确定拥有最大值的果蝇（当前最优的个体）。

6）记录并保存最佳味道浓度值bestSmell和位置信息X及Y，在这一时刻，果蝇会依赖视觉器官去接近这一位置。

7）开始迭代计算，反复操作2）～5）步骤，一旦味道浓度超过了前一迭代结果，启动步骤6）程序执行，直到预先设定最大迭代次数maxgen或是已达到目标要求的精度或理论最优值。

3 粒子群搜索策略

粒子群算法［13～14］（Particle Swarm Optimization，PSO）是一种新兴的演化算法。该算法是由Kenne⁃dy和Eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物（如蚂蚁、鸟、鱼等）通过群聚而有效的觅食和逃避追捕，在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。

在PSO算法中，粒子群在一个n维的空间中搜索，每个粒子所处的位置都被看成解空间的一个，粒子通过个体和群体的飞行经历来不断调整自己的位置。第i个粒子所经历过的最好位置被记作个体极值(xpbest)，整个群体所经历过的最好位置被记做全局极值(xgbest)。粒子根据下面的公式来更新自己的速度和位置：

其中w为非负惯性权重，c1，c2为学习因子，为［0，1］之间的随机数。

本文根据果蝇优化算法和粒子群算法的优点，给出了基于粒子群搜索策略的混合果蝇优化算法，FOA优化算法是模拟果蝇觅食行为，但由于FOA是一种提出新的算法，也存在后期收敛速度比较慢的缺点。而PSO中利用了个体极值和全局极值来更新位置收敛的速度快些。因此用PSO中的粒子移动的方式代替果蝇优化算法中的位置更新，即采用上面的式（7）、（8）进行果蝇个体的位置更新。

4 混合算法的设计

1）首先根据给定初始寻优的范围随机生成初始群体并且位置矢量用 X_axis，Y_axis，给出果蝇的初始群体的规模，popsize，最大迭代次数maxgen。

2）执行FOA算法流程2）～5）。

3）记录并保留最佳味道浓度值bestSmell与其位置坐标X，Y，以及此时果蝇群体利用视觉往该位置飞去。

4）在本文定义在n维空间中，第i个果蝇t时刻和t-1时刻位置更新的公式为

这里 X̂_axisi，Ŷ_axisi分别表示历史最佳味道浓度时位置坐标。当前粒子所经历过的最好位置被记作个体极值(xpbest)，整个群体所经历过的最好位置被记作全局极值(xgbest)，其中w为非负惯性权重 w∈[0.9，1.2]，c1，c2为学习因子，通常取c1=c2≈2.05，r1，r2为［0，1］之间的随机数。

5）先按照式（13）估计新位置 Xi(t)，Yi(t)与原点之距离，再按照式（14）计算更新后的位置味道浓度判定值(i=1，2，…，Sizepop)。

6）将味道浓度函数判定值S′i代入味道浓度判定函数，求出新位置的味道浓度Smell′i。

8）开始迭代计算，反复操作2）～7）步骤，程序执行已达到预先设定最大迭代次数maxgen或是已达到目标要求的精度或理论最优值。

5 数值仿真实验结果与分析

5.1 测试函数与初始化参数

表1 选取标准测试函数［15］

改进算法的性能，这里采用的是对于智能算法通用的方法，选用6个标准测试函数中包括了单峰、多峰、线性、非线性、等特征。并且5个标准测试函数的最优值都是0；测试实验平台为Windows7和Matlab2010B，机器主频为2.0GHz，内存为16GB；HFOA和FOA中的参数使用是一样测，试实验中的参数设置如下，果蝇种群的规模为Sizepop=40，最大迭代次数为Maxgen=200。

5.2 实验结果

5.2.1 实验结果的对比

应用本文算法的和标准的FOA算法对8个标准函数（维数均取40）进行30次实验，实验中所得到最好的最优值、最差最优值、平均方差、平均最优值如表2所示。

5.2.2 固定进化迭代次数的收敛和精度

图1～12是表1中的6个标准测试函数分别用标准果蝇优化算法和基于粒子群搜索策略混合果蝇优化算法运行求解的适应度函数变化曲线图。从图中可以看出本文算法的收敛性和收敛速度明显要优于标准果蝇优化算法的，这主要是因为粒子群搜索策略混合算子的作用，使得果蝇种群保持种群的多样性，同时也使得个体具有较好的鲁棒性的特点。