一种新型的改进果蝇优化算法

戈涛，张馨

（1.合肥市现代职业教育公共实训中心，合肥230012；2.安徽大学计算机科学与技术学院，合肥230601）

0 引言

果蝇优化算法是台湾学者潘文超在2011 年提出的新型群体智能优化算法[1-2]，主要是模拟果蝇搜寻食物的过程，果蝇有着优于其他物种的敏感嗅觉器官，能够嗅到漂浮在几十公里外空气中的各种食物味道，当靠近食物位置时又能通过其敏锐的视觉找到食物和同伴，并向味道浓度最大的方向飞去。果蝇算法就是通过模拟此过程并不断迭代寻优以求得问题的最优解。果蝇优化算法自诞生之日起就以其算法简单、调整参数少、易实现等优点而受到广大学者的青睐，现已被广泛应用与求解函数优化[3]、PID 控制参数优化[4]、最小二乘支持向量机参数优化[5]、置换流水线调度[6]、LSSVR 干燥速率建模[7]、多维背包问题[8]等。随着对果蝇优化算法的不断深入研究，算法本身也暴露出了不可忽视的缺点。果蝇优化算法在求解单峰值函数时尚能表现出良好的寻优效果，但是在求解多峰值或者高维度的复杂优化问题时很难达到理想的效果。

为了解决原始果蝇优化算法自身存在的收敛速度慢、寻优精度低、易陷入局部最优等问题，本文提出了一种新型的果蝇优化算法，将本文方法与原始果蝇优化算法及改进的果蝇算法DS-FOA 和LGMS-FOA 进行仿真对比，实验结果表明，本文所提出的算法在收敛效果和寻优速度上有了明显提高且具有更高的稳定性。

1 基本果蝇优化算法介绍

1.1 FOA算法描述

在基本果蝇优化算法中，每只果蝇个体会被随机的分布在一个N 维的特定搜索空间，其搜索步长固定不变，搜寻食物的方向具有随机性，每个果蝇个体都携带有味道浓度，该值与味道浓度判定值有关，由于在初始阶段不知道食物的具体位置，因此把每个果蝇个体与原点距离的倒数作为判断味道浓度判定值的依据，将该值代入目标函数以求得果蝇个体的味道浓度值，味道浓度值越小的果蝇距离食物源的位置越近（适用于最小优化问题），记录下果蝇群体中味道浓度值最小的果蝇位置，其他果蝇凭借敏锐的嗅觉飞往该位置，最后通过迭代不断更新果蝇群体中的最佳位置，直到迭代结束找到问题的最优解。

1.2 FOA具体步骤

FOA 算法主要分为7 个步骤：果蝇群体位置初始化，果蝇飞行方向和距离，味道浓度判定值计算，味道浓度值计算，计算最佳味道浓度，保留最佳味道浓度值及其位置，迭代寻优。

（1）果蝇群体位置初始化

设定果蝇群体规模和最大迭代次数分别为Sizepop、Maxgen,果蝇群体位置为X_axis,Y_axis。

（2）果蝇飞行方向和距离

其中，RValue 为果蝇的随机搜索距离。（3）味道浓度判定值计算

计算果蝇个体与原点的距离（Di）和果蝇个体的味道浓度判定值（Si）：

（4）味道浓度值计算

将味道浓度判定值Si代入适应度函数Function中，求出该果蝇个体位置的味道浓度smell(i)：

smell(i)=Function(Si)

（5）计算最佳味道浓度

找出此果蝇群体中的最优个体（即味道浓度最小值）以及其位置：

[bestsmellbestindex] =min(smell)

（6）保留最佳味道浓度值及其位置

保留最优味道浓度值bestsmell 与其对应的X、Y 坐标，此时果蝇群体往该位置飞去：

（7）迭代寻优

重复执行步骤（2）-（5），并判断味道浓度是否优于前一迭代味道浓度，若成立则执行步骤（6）。

1.3 基本FOA的缺陷

缺陷一：基本FOA 算法中，果蝇个体在搜索空间内移动步长是固定不变的，选择一个固定的移动步长值求解优化问题是不恰当的，尤其是对于多峰值函数，若搜索步长值取得较大，在算法前期尚可获得较快的寻优速度，进行全局搜索，但是到了算法寻优后期较大的移动步长极有可能跳过函数最优解，寻优精度降低，陷入局部最优；若搜索步长值取得较小值，虽然寻优精度提高了，但是步长值较小会降低了寻优速度，需要不断重复的迭代，降低了寻优效率，不利于进行全局寻优。

缺陷二：基本FOA 算法中，在果蝇视觉搜索过程中，果蝇群体一旦发现具有最优味道浓度的果蝇，所有果蝇个体都会飞往该果蝇的位置，可是该果蝇极有可能并不是整个搜索空间中的最优果蝇个体，而是局部最优果蝇个体，若此局部最优果蝇个体周围没有比其味道浓度更优的果蝇，它就会保持不动，其他果蝇则源源不断地飞往此果蝇的位置，不但降低了寻优效率，也容易使算法陷入局部最优。

2 改进的FOA算法（CSFOA）

2.1 非线性递减步长

针对基本FOA 算法中的缺陷一，CSFOA 算法中变固定步长值为非线性递减步长，移动步长变化率如图1所示，在果蝇算法迭代寻优初始阶段，果蝇个体保持一个较大的移动步长，使算法的搜索能力能够渗透到整个搜索空间，从而提高算法全局寻优的能力，避免算法陷入某个局部最优值；在果蝇算法迭代寻优后期，果蝇个体的移动步长非线性的动态逐渐减小，使其能在当前局部最优解附近进行精细搜索，不仅避免了因为移动步长值过大而跳过最优解可能，而且也提高了算法后期的收敛精度。

图1 移动步长变化率

具体公式如下：

其中Lmax，Lmin分别为最大和最小移动步长，Rate为步长的变化率，t 为当前迭代次数，tmax为最大迭代次数，p 为步长调节因子，c 为指数调节因子。

2.2 随机策略

针对基本FOA 算法中的缺陷二，本文引入了随机机制，增加算法探索解空间的能力，若某个最优解经过多次迭代始终不变，则此时极有可能陷入局部最优解，如图2 所示，因此引入随机策略进行扰动，使算法逃离局部最优，增加解得多样性，从而进行全局搜索。具体策略如下：

其中（1-e-λx）满足指数分布，besti-1为上一代最优味道浓度值。

图2 局部最优实例

3 仿真实验及结果分析

3.1 实验平台

本文的实验平台是MATLAB R2014a,在操作系统为Windows 7，内存为4GB，CPU 频率为3.20GHz 的PC上运行。

3.2 参数设置

具体参数设置如下：果蝇群体大小Sizepop=20，迭代次数tmax=100，步长调节因子p=1，指数调节因子c=1.5，最大移动步长Lmax=5，最小移动步长Lmin=0.01，随机策略中的λ=0.5。

3.3 测试函数

为了验证算法的可行性，本文选取8 个基准测试函数对FOA、DS-FOA、LGMS-FOA 以及本文算法进行测试，求出在指定搜索区间内的函数最优值，测试函数如表1 所示。

表1 测试函数

3.4 仿真实验

使用基本FOA、DS-FOA、LGMS-FOA 以及本文算法CSFOA 对8 个基准函数独立运行实验20 次，分别求出8 个基准测试函数的平均值以及标准偏差，函数的平均值反映了算法的寻优能力，标准偏差则能够反映出算法的稳定性。在MATLAB 上经过20 次独立运行的实验结果如表2 所示，其中Mean、Std 分别代指函数的平均值和标准偏差。

表2 四种算法优化性能对比

图3 f1(x)函数优化对比

图4 f2(x)函数优化对比

图5 f3(x)函数优化对比

图6 f4(x)函数优化对比

图7 f5(x)函数优化对比

图8 f6(x)函数优化对比

图9 f7(x)函数优化对比

图10 f8(x)函数优化对比

从表2 中可以看出，在求解高维函数的最优值时，原始FOA 算法的弊端尤其明显，由于原始FOA 采用固定的步长值，限制了算法的寻优性能，导致算法容易陷入局部最优；相较于原始FOA，DS-FOA 引入了初始步长L0，使算法能够随着迭代的进行移动步长逐渐减小，提高了算法在迭代后期的收敛精度；LGMS-FOA 则是引入了权重系数w，并且随着不断迭代权重系数w 按指数形式下降，相较于原始FOA 同样提高了算法的收敛精度，但是在对函数f2(x)、f3(x)、f4(x)求解中其收敛精度却低于原始FOA 的收敛精度，原因在于LGMSFOA 算法并没有解决算法陷入局部极值的问题。与其他三种算法相比，CSFOA 算法不管是在收敛精度还是算法稳定性方面都有着明显的优势。

表3 目标精度下平均迭代次数与成功率对比

图3～图6 为四种算法的迭代寻优过程，从中可以看出，原始FOA 算法收敛速度较慢，DS-FOA 和LGMS-FOA 算法收敛速度虽有提高，但是容易陷入局部最优，而CSFOA 算法由于采用了随机策略，即使遇到局部最优解也能及时跳出局部极值，寻找到函数最优解，提高了算法的寻优性能。

表3 为8 个基准测试函数在目标精度下所需要的迭代次数和成功率的结果对比，从中可以看出，在低维情况下，三种改进的FOA 算法有着更强的寻有能力，迭次数更少，且成功率高；在高维情况下，原始FOA 算法、DS-FOA 算法和LGMS-FOA 算法的寻优能力下降，易陷入局部最优，且在完成目标精度情况下需要经过多次迭代，影响了算法的寻优效率，而CSFOA 算法在低维和高维情况下都表现出了良好的寻优能力，且具有更高的效率和稳定性。

4 结语

本文针对基本果蝇算法的缺陷，提出了非线性动态机制，将基本果蝇算法中的固定步长变为非线性递减步长，既保持了算法在迭代初期全局寻优的能力，又维持了算法在迭代后期进行精细搜索的能力；为了增加算法在整个寻优空间中探索解空间的能力，引入了随机策略，对空间解进行扰动，避免算法陷入局部最优。仿真实验结果表明，改进后的算法具有更好的探索解空间的能力，有效避免了算法陷入局部极值，增加了算法的稳定性，提高了运行效率。接下来的研究任务是将新改进的算法用于解决实际问题，验证其解决问题的能力和效率。