动态调整搜索策略的果蝇优化算法

张水平，高 栋

江西理工大学 信息工程学院，江西 赣州 341000

1 引言

2011年，潘文超博士提出了一种新的可用于全局优化的群智能进化算法[1]，即果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）。该算法思想源于对果蝇觅食行为的模拟，相比其他群智能算法，该算法可塑性强，结构简单，易于理解且便于实现，仅有3 个参数需要调整（遗传、粒子群、人工鱼群算法均需调整5 个参数，蚁群算法需调整7 个参数），同时具有较快的搜索速度和较低的算法复杂度，自从提出便受到国内外广大学者的关注，现已成功地应用于科学和工程等诸多领域[2]。

果蝇优化算法作为群体智能算法的一种，其存在共性缺陷的同时，也有特性缺陷，如不能解决最优值为负数的问题等。针对其存在的缺陷，在近几年的研究中，关于果蝇优化算法的改进和应用逐步涌现。马巧梅等[3]对味道浓度进行修正，一定程度上解决了味道浓度判定值不能为负数的问题；信成涛等[4]通过对个体的搜索距离进行自适应调整，使算法的收敛精度得到提升；张前图[5]、刘成忠[6]等对种群进行划分，进行多种群协调搜索以达到平衡全局和局部搜索能力的目的；张彩宏等[7]提出设计混合算法，从而提高了算法的局部寻优能力。上述改进算法都在一定程度上提高了果蝇优化算法的优化性能，但均未对种群的进化方向进行充分的利用；部分改进算法在寻优过程中未对种群的多样性进行动态调整，以降低算法陷入局部最优的概率；当算法陷入局部最优时，其跳出局部最优的能力不强，寻优速度和寻优精度还有待于进一步提高。

本文研究提出了一种动态调整搜索策略的果蝇优化算法（Fruit fly Optimization Algorithm with Dynamic Adjustment of Search Strategy，FOAASS）。该改进算法从种群位置初始化、寻优搜索策略、迭代搜索半径、跳出局部最优四方面进行优化。对6 个经典性能函数进行仿真运算，结果表明，本文提出的改进算法有较好的寻优精度和收敛速度。

2 标准果蝇优化算法

果蝇群体广泛分布在热带和温带地区，相比其他生物，其嗅觉和视觉能力更为发达。在觅食过程中，果蝇先利用自身的嗅觉发现食物气味，并将气味信息发送给周围的果蝇（或接收由周围果蝇发送的气味信息）；之后，通过对比得到当前种群中获取最优气味信息的果蝇个体位置，群体中的其他果蝇均利用其发达的视觉器官向该位置飞去，并继续进行搜索[8]。

根据以上所述果蝇觅食行为的特点，可将标准果蝇优化算法归纳为以下7个必要的寻优步骤[9]：

步骤1 初始化设置算法的相关参数，主要包括算法运行的最大迭代次数(MaxTimes) 、果蝇种群的规模(SizePop) 、果蝇群体的可活动范围(LR) 和搜索半径(SR)，并根据式（1）随机初始化种群中每个果蝇个体的初始位置(X_axis,Y_axis)。

步骤2 赋予每只果蝇随机搜索的距离方向。

步骤3 计算种群中每只果蝇个体的位置坐标与坐标原点的距离Disti和其味道浓度判定值Si，其中Si为Disti的倒数。

步骤4 将味道浓度判定值Si带入适应度函数（或目标函数）中，计算种群中每个果蝇个体的味道浓度值Smelli。

步骤5 找出当前种群中味道浓度值最佳的果蝇个体，记录其位置信息和相应的味道浓度值。

步骤6 保留最优迭代坐标和最佳味道浓度值，群体中的其他果蝇均利用视觉向该位置飞去。

步骤7 开始进行迭代寻优，将步骤2～步骤5重复执行，并同时判断当前的迭代次数是否小于最大迭代次数，当前迭代所求得的味道浓度是否优于历史味道浓度，若均是，则执行步骤6。

3 动态调整搜索策略的FOA

针对标准FOA 存在的缺陷，FOAASS 分别从四方面进行改进：采用“以迭代次数换取初始位置数量”的策略，扩大初始位置数量，并利用混沌映射增强初始位置的均匀性和随机性；改变种群中部分果蝇的寻优策略，使其沿着种群中心点及全局最优解的连线或延长线进行搜索；采用新的搜索半径计算方式，通过种群进化信息动态调整其大小，同时引入转换概率，使果蝇在每次嗅觉搜索时随机选取搜索范围，平衡局部和全局搜索之间的能力；通过种群适应度方差判断算法是否陷入早熟，当陷入早熟时，改变种群中所有果蝇个体下次迭代的搜索策略，不再绕全局最优点飞行，而是随机进行混合变异，此策略在一定程度上提高了种群的多样性，并有较大可能跳出局部最优点。

3.1 利用混沌映射确定种群初始位置

在算法运行的过程中，种群初始位置所产生的解的质量起到了至关重要的作用，好的初始位置，既有利于找到全局最优解，也能加快算法的收敛速度。分析可知，初始解的质量受到种群中初始位置的数量及分布情况两方面的影响。

3.1.1通过等价替换增大初始位置数量

为了在实验初期得到较多的初始位置点，本文提出采用“牺牲迭代次数换取初始位置个数”的策略（在FOA中，迭代N次将遍历N×SizePop个位置矢量），在算法运行时，用N倍的迭代次数换取M个位置点，一定程度上可以提高初始解的质量。

3.1.2通过混沌映射改善初始位置分布

随机产生的初始位置可能导致果蝇群体不能均匀分布，从而导致果蝇群体不能全面地搜索解空间。混沌映射具有随机性、遍历性和规律性等特点，其基本思想是将待优化变量通过混沌映射规则映射到混沌变量空间的取值区间，利用混沌变量的遍历性和规律性进行寻优搜索，之后将获得的优化解线性转化到优化空间中[10]。

本文首先将果蝇种群的位置映射到（0，1）区间，映射公式如下所示。

其中，zmax和zmin为种群中个体位置的最大值和最小值。

然后将得到的数值利用Logistic映射[11]产生混沌值zci+1，并以此更新初始果蝇种群。本文使用的映射迭代如下所示：

其中，μ是控制参数，随着μ值的增大，序列的分布越来越均匀，当μ等于 4 时，Logistic 映射的分布最均匀，本文中μ取值为4。

最后通过式（12）将经过混沌映射后的混沌值转化到种群的变量空间中，从而使果蝇种群的初始位置分布更加均匀。

3.2 调整部分果蝇寻优策略

在标准果蝇优化算法中，群体中的所有果蝇均围绕最优位置进行搜索寻优，未考虑果蝇种群的迭代进化方向信息。通过大量实验研究FOA算法中果蝇的飞行路径，发现果蝇种群的进化方向是有一定规律可循的。图1给出了30次迭代的种群中心点二维坐标和最优个体飞行路径，虽然并不是每次迭代的最优位置和种群中心点连线及延长线上的点均接近下次迭代的最优值，但从总体上看来，沿着该方向更容易找到下次迭代的最优位置。通过以上规律，可以一定程度上预测下次迭代的进化方向，并可以将其推广到高维空间中。

图1 果蝇寻优路径及种群中心点位置

因此，本文动态调整果蝇的寻优策略，使得果蝇群体中1/4 的果蝇沿着预计的进化方向进行直线搜索，如式（13）所示，其他果蝇环绕最优位置进行搜索，此策略一定程度上可以加快寻优速度并提高种群多样性。

其中，avg为种群位置的中心点，λ为[-2,3]之间的随机数，当 0 ≤λ≤1 时，将生成两点连线上的点，当λ>1时，将生成中心点端点外延长线上的点，当λ<0时，将取得最优位置点外延长线上的点。

3.3 随机选取动态搜索半径

果蝇优化算法的重要研究方向之一是对搜索半径进行改进，标准果蝇优化算法中以固定半径进行随机搜索，多数改进的果蝇优化算法均采用搜索半径递减或自适应的策略，使算法在迭代初期有较大的搜索半径，从而加强全局搜索能力，随着迭代次数的增加，算法后期的搜索范围逐渐减少以便进行精细搜索，此改进一定程度上增强了算法的寻优性能。分析发现，无论是标准FOA，还是现有的改进算法，在同一次迭代过程中，种群中每个果蝇的搜索范围都是相同的，并没有具体的分工。因此，本文结合果蝇种群进化信息设计了新的搜索半径计算方式：

其中，SR1、SR2、SR3分别为三种不同的搜索半径计算公式，SRmin为最小搜索半径，SRmax为最大搜索半径，SR0为初始搜索半径，MaxT为最大迭代次数，t为当前迭代次数，avgSmt、bestSmt分别为第t次迭代时，种群中平均味道浓度和最优味道浓度值，旨在引入浓度差值变化率[12]。

为了明确种群中果蝇个体的分工，引入转换概率p(p∈[0,1])，在每次迭代时将果蝇种群随机分为三类：当0 ≤p≤0.25 时，搜索半径通过递增公式SR1生成，有利于部分果蝇进行全局搜索并尽可能跳出局部最优；当0.25

3.4 更改策略以跳出局部最优

以上对种群位置初始化、寻优搜索策略及迭代搜索半径进行优化，提高了算法的搜索速度和寻优精度，也在一定程度上降低了算法发生早熟收敛的可能性，但是群智能算法的特性决定了其仍然无法避免陷入局部最优，一旦受到局部最优值的约束，现有搜索策略很难摆脱束缚。

因此，本文以种群味道浓度方差(α2)判断算法是否陷入局部最优，α2反映了果蝇种群的聚集程度，α2越大，代表种群的聚集程度提高，种群多样性降低，算法的寻优过程逐步陷入停滞状态[13]。种群味道浓度方差α2计算公式如下：

式中，平均味道浓度值avgSmt由式（17）确定。

算法在运行时，当α2≤η（η代表种群的味道浓度方差阈值）时，认定种群陷入局部最优，此时更改下次迭代的搜索策略，果蝇个体均不再围绕最优位置进行随机搜索，而是对所有果蝇位置进行随机的混合变异（群体中的1/2果蝇进行高斯变异，1/2的果蝇进行非均匀变异），增强种群中个体的逃逸能力，从而跳出局部，拓展新的进化方向，在空间中的其他区域继续搜索，直到找到全局最优值。

高斯变异是指将一个服从高斯分布的随机扰动项加在原有个体的状态上，如式（19）所示。

式中，N(0,1)为标准高斯分布。

非均匀变异是对原有的位置做随机扰动，以扰动后的结果作为变异后的新位置[14]，如式（20）所示。

式中，[LB,UB]为果蝇的搜索范围，r为[0，1]区间均匀分布的随机数，Δ(x,y)的值由式（21）确定，t是当前迭代次数，MaxT是最大迭代次数，b是决定变异运算时非均匀度的系统参数。

3.5 FOAASS算法实现步骤

基于标准果蝇优化算法原理及上述改进方法，本文动态调整进化方向的果蝇优化算法具体寻优步骤如下：

步骤1 参数初始化，设置种群规模SizePop、最大迭代次数MaxTimes、味道浓度方差阈值η、等价替换因子N、初始搜索半径SR0等。

步骤2 种群位置初始化。首先利用“等价替换”原则确定初始位置数量；其次通过混沌映射改善种群初始位置(X_axis,Y_axis)的质量。

步骤3 运行标准果蝇优化算法中的步骤2～步骤5一次，从而得到初始解等信息，并由式（18）计算种群初始味道浓度方差α2。

步骤4 进行方差判断，若α2≤η，则认定算法陷入局部最优，转至步骤6调整搜索策略，否则转至步骤5。

步骤5 根据式（13）～（15）计算种群中前1/4 的果蝇位置信息，其余果蝇随机选择搜索半径并通过式（2）更新位置信息，然后转至步骤7。

步骤6 进行变异操作，利用式（19）对群体中部分果蝇位置进行高斯变异，其余果蝇位置利用式（20）进行非均匀变异，完成后转至步骤7。

步骤7 执行标准果蝇优化算法中的步骤3～步骤6。

步骤8 利用式（18）更新种群内的味道浓度方差α2，并利用式（16）计算下次迭代的搜索半径。

步骤9 判断是否满足终止条件，若满足条件，则转至步骤10，否则转至步骤4进行下一次寻优探索。

步骤10 输出全局最优解。

改进算法具有了防止算法早熟收敛及跳出局部最优的能力。FOAASS算法运行的伪代码如下所示。

算法动态调整搜索策略的果蝇优化算法

输入：目标函数f(x)、种群规模SP、味道浓度方差阈值η、最大迭代次数MT、初始搜索半径SR0等。

输出：全局最优解。

1. 利用等价替换及混沌映射初始化种群

2. 在初始种群中找到最优解SmellBest，并利用式（18）计算初始种群味道浓度方差α2

3. fort=1:MT-N

4. fori=1:SP%循环遍历果蝇个体

5. ifα2＜η

6. 随机选取式（19）或式（20）更新位置

7. else

8. ifi

9. 按照式（13）、（14）、（15）更新位置

10. else

11. 按照式（2）更新位置

12. end

13. end

14. 对生成的位置进行边界化处理

15. 将处理后的位置代入式（3）、（4）、（5）得到味道浓度值

16. end %果蝇个体迭代结束

17. 找到种群中最优的解

18. 判断本次循环得到的解是否优于全局最优解，若是，更新全局最优解和最优位置

19. 利用式（18）重新计算种群味道浓度方差α2

20. 利用式（20）计算下次迭代的搜索半径SR

21. end %迭代循环结束

22. 输出找到的最优解

3.6 FOAASS算法时间复杂度分析

时间复杂度是指算法执行所需要的计算工作量，主要取决于问题重复执行的次数。在标准果蝇优化算法中，时间复杂度主要受到种群规模S和迭代次数M的影响，在迭代过程中，每个个体迭代需要的计算量为O(1)，则FOA算法的时间复杂度为O(N×M)。

FOAASS 算法是由FOA 算法改进而来，根据 3.5 节中算法步骤和伪代码可知，FOAASS在FOA算法的基础上增加了计算搜索半径、计算味道浓度方差、判断调整搜索策略等步骤：第20步搜索半径的计算复杂度为O(M)，第19 步种群味道浓度方差计算复杂度为O(M)，第5～13 步循环判断调整搜索策略的计算复杂度为O(N×M),因此本文算法的时间复杂度为O(N×M+N×M)。

由上述分析可知，FOAASS算法的时间复杂度相对较高，这是提高寻优精度和收敛速度所付出的代价，寻求较低的时间复杂度将是日后研究的重点。

4 实验仿真与结果分析

4.1 实验设计

为了检验本文所提出算法的有效性，选取了6个经典性能测试函数对标准果蝇优化算法、本文改进算法和参考文献中的四种改进算法在相同环境下进行Matlab4仿真实验对比（求最小值），一是比较算法的收敛速度和寻优精度（通过固定种群规模和迭代次数），二是比较算法的成功率和平均迭代次数（通过固定收敛精度）[15]。

表1 列出了6 个测试函数的名称、表达式、搜索空间、维度及峰值等信息。当函数的自变量搜索空间越广、维度越大、目标的收敛精度越高时，顺利搜索到最优解的难度也就越大，对所优化的算法的性能要求就越高。

4.2 固定种群规模和迭代次数的性能测试

为了降低算法随机性对实验数据的影响，以20次独立实验的平均值作为评估算法收敛速度和收敛精度的最终结果。具体参数设置如下：种群规模SizePop=30,最大迭代次数MaxTimes=1 000，等价替换因子N=10，6个测试函数的味道浓度方差阈值η均为1×10－6，初始、最大、最小搜索半径分别为1、2、0.5。

表2给出了FOA算法、FOAASS算法和文献[16-19]中的 ASCEFOA 算法[16]、MFOAADS 算法[17]、DCFOA 算法[18]、FOAMR 算法[19]在不同函数上的最优值（best）、平均值（avg）、最差值（worst）和标准差（sd），结果保留4位小数，其中解的质量由最优值和最差值反映，算法所能达到的精度由平均值反映，算法的鲁棒性及稳定性由标准差反映。

表1 测试函数参数设置

表2 6种算法性能比较

从整体上看，无论多峰还是单峰函数，FOAASS算法都比FOA 算法有更好的搜索能力，整体上优于文献[16-19]中的算法，同时具有更快的收敛速度。其中Schaffer 函数、Sphere 函数、Griewank 函数、Rastrigin 函数都可以达到理论最优值，对于Ackley 函数，FOAASS相比FOA 算法在最优解的精度上提高了14 个数量级，但是对于Rosenbrock 函数，其改进效果并不明显，搜索精度提升得有限。

图2给出了以上6种算法在不同测试函数上进行迭代寻优的对比曲线，横坐标为迭代次数。同时为了更好地观察对比两种算法的迭代曲线，将得到的最佳味道浓度值取以10 为底的对数，则纵坐标为收敛精度。结合迭代曲线及实验数据，分析如下：

（1）对比较简单的单峰值Sphere 函数而言，其寻优难度并不是太大，FOAASS算法在迭代初期就沿着正确的方向逼近最优解，并在第500次迭代左右便搜索到理论最优值，标准差为0亦表明了改进算法寻优的稳定性良好，相比另外4种改进算法，可以更迅速地找到最优解。

（2）Griewank函数是一种具有无数局部极小值点的可变维高峰函数，由图2（b）可知，FOA 算法在第100 次迭代左右便陷入了局部极值点且一直无法跳出，但FOAASS、ASCEFOA、MFOAADS算法均可跳出局部极值点并继续在大范围内搜索，直到找到全局最优点，具有更好的稳定性。

（3）由图2可知，在6个性能测试函数中，6种算法对Rosenbrock函数进行求解的性能均较差。虽然FOAASS算法相比其他4 种改进算法，其求解的精度略有提高，但相比其他函数，对本函数的优化效果不明显。从函数本身分析，其全局最优点位于一条平滑而狭长的抛物线形状的山谷底部，为算法提供的信息很少，算法很难辨别搜索方向，因此找到其全局极小值就显得特别困难[20]。为此，接下来的算法改进将考虑引入三角函数因子，利用三角函数具有的周期震荡性使每个个体可获得较强的震荡性，并扩大每个个体的搜索空间，从而可以引导个体逐步向全局最优点靠近，以提高算法对本函数的求解精度或找到全局最优点的概率。

（4）Rastrigin函数的三维空间图形类似于无数起伏不平的山峰，在迭代寻优的过程中，FOA 和FOAMR 算法在第100次左右便陷入局部最优，并一直在局部最优点徘徊，无法跳出；FOAASS 和ASCEFOA 算法在寻优过程中也会陷入局部极值点，但均可多次跳出局部极值点并找到全局最优点。

（5）Ackley 函数是一种具有爬山形态的多峰值函数，全局最优值极难寻找，从图2（e）可以看出，FOA 算法对其求解的精度不高，寻优速度十分缓慢，在迭代初期就陷入了局部最优；MFOAADS和FOAMR算法对其寻优精度略有提升；ASCEFOA 算法虽然在第100 次迭代左右便可迅速找到较高精度的解，但是其最终结果相比FOAASS算法的求解精度略有不足。

（6）由图2（f）可知，FOA 和MFOAADS 算法对具有震荡性、多峰值、多次优点的Schaffer 函数寻优难度较大，容易陷入局部最优且难以逃离；FOAMR、DCFOA和ASCEFOA 算法对函数的求解精度及速度逐步提升，但均无法找到理论最优值；FOAASS算法可迅速跳出并找到理论最优值，其收敛速度和收敛精度均远远好于FOA算法，全局收敛性能相比而言更好。

图2 函数进化曲线

表3 算法成功率和平均迭代次数比较

经上述分析可知，本文提出的FOAASS算法优于标准的FOA 算法，虽然对Rosenbrock 函数的寻优效果不理想，只提升了有限的搜索精度，但对另外5 个函数的寻优效果均比其他4种改进算法要好，充分说明了本文的改进算法具有更高的收敛精度和更好的搜索能力，同时更容易跳出局部最优。

4.3 固定收敛精度下的性能测试

为了更好地验证FOAASS算法的收敛性，通过设置固定的收敛精度，对6 个测试函数进行了性能测试，其20 次独立运行实验的成功率(K)和平均迭代次数(T)如表3 所示。在表3 中，成功率=达到精度的运行次数/总次数，“—”表示该参考文献未给出相关数据，“D”表示该实验所用的目标精度。

分析可知，本文提出的FOAASS算法在6个测试函数上进行了20 次独立运行实验，都很早达到了目标精度，并且成功率均为100%。对于Rastrigin函数和Ackley函数，FOAASS 算法设置了更高的求解精度，但寻优效果依旧不错。从整体上讲，在固定收敛精度的情况下，FOAASS 算法具有更高的寻优效率和更好的寻优可信性，寻优性能相对而言更好。

5 总结

通过对标准果蝇算法进行分析，针对其存在的缺陷并结合现有文献对其做出的改进，本文提出了一种动态调整搜索策略的改进算法。在种群初始化过程中进行等价替换和混沌映射，使果蝇种群初始解的质量更好；调整部分果蝇的搜索策略，以引导种群在进化过程中保持正确的搜索方向；随机选取动态搜索半径，对种群内的果蝇进行分工；采用混合变异策略，方便跳出局部最优。

最后，进行仿真实验，结果表明本文算法相比标准FOA具有更高的求解精度、更快的求解速度和更好的稳定性，比参考文献中的改进算法更易于跳出局部最优并得到全局最优，寻优可信性更强。本文的改进算法也存在时间复杂度较高、对个别函数寻优效果不理想等缺陷，因此，寻求较低的时间复杂度，提高算法在部分函数上的寻优性能，对算法的收敛性进行详细的研究分析以解决生活中的实际问题，将是下一步研究的工作重点。