0 引言

果蝇优化算法(Fruit fly Optimization Algorithm，FOA)^[1]是台湾学者潘文超模拟自然界中果蝇的觅食行为提出的一种群体搜索随机优化算法.目前已应用到智能优化、神经网络参数优化、支持向量机优化和工业设计等领域^[2-6].与其它的群智能优化算法相比较，FOA具有简单容易理解和操作，调整参数较少等特点^[7]，但也存在易陷于局部最优和不能处理最优位置在负区间优化等问题.究其原因是由于每个果蝇在其搜索范围内不断向种群中最优的果蝇个体飞行，通过位置的迭代找寻到全局或局部最优解，若搜索范围内没有更优个体，果蝇则做随机运动，这样就降低了发现率和收敛速度.已有学者在个体进化方式改进、种群多样性、启发式算法融合和混沌变异等方面提出一些改进方法.文[8-9]通过双子群寻优，并引入混沌映射和Lévy飞行改进个体进化策略，验证了种群分组寻优的有效性；文[10-13]利用控制个体搜寻范围、混沌变异帮助种群跳出局部最优；文[14]将FOA与元胞自动机理论相结合，利用元胞自动机构造最优个体的领域，借助邻域个体更新进化个体.可见，FOA作为新兴的一种进化算法，其算法的优缺点、适应性及收敛速度和理论分析都需学者做积极的探索研究.本文提出一种动态分组多策略果蝇优化算法(dynamic grouping and multi-strategy fruit fly optimization algorithm，DGM-FOA).首先采用佳点集理论对果蝇种群的位置进行初始化，利用自适应分组策略对种群进行分子群寻优，在迭代过程中建立指定个数的果蝇精英池；通过果蝇精英池的个体采用差分变异算子改进最优个体的寻优行为；在迭代后期通过评价函数计算果蝇精英池中个体的多样性来指导是否将整个种群分为优势群体和拓展群体，进而利用改进粒子群算法进化优势群体增强寻优精度，利用反向混沌算法进化拓展群体避免陷入局部最优解.

1 基本果蝇优化算法原理

1) 设定种群规模，最大迭代次数及误差精度，根据寻优范围随机生成位置矢量[X_axis，Y_axis].

2) 赋予果蝇个体利用嗅觉搜寻食物之随机方向与距离：

(1)

其中，rand()为搜索距离.

3) 利用式(2)预测它和原点的距离D_i，再利用式(3)计算味道浓度判定值：

(2)

(3)

4) 将式(3)计算的值代入味道浓度函数(适应度函数f_fitness)，得到果蝇所处位置的味道浓度：

(4)

5)计算所有果蝇的Q_i构成种群的适应度向量Q，在Q中求出味道浓度最大值的果蝇(当代最优个体)：

(5)

6) 保留最佳味道浓度值b_smell和位置信息X、Y，此时果绳群体依赖视觉器官向其飞去：

(6)

7) 进入迭代寻优，重复步骤2)~步骤5)，找到比上一次迭代更优的个体则执行步骤6)，满足最大迭代次数或预设精度则退出.

从FOA的原理可以看出，算法开始迭代是先随机生成一个位置，种群个体的进化是在这个位置的基础上通过随机扰动来完成个体位置的更新，进而完成寻优工作.以2维空间y=x₁²+x₂²，x∈[x_min，x_max]寻优为例(x_max、x_min分别为x的取值的上、下限，很容易扩展到N维空间)，根据式(1)，假定每一次迭代过程都会找到更优解，则[X_axis，Y_axi]就会在此基础上不断增加rand(< x_max)，经过L次迭代后果蝇个体位置为

(7)

从式(7)可知，S_i相当于其它智能算法的优化个体，适应度的取值依靠于S_i.由此可以得出2个结论：

1) 基本果蝇算法不能处理最优位置在负区间的优化问题^[15]；

2) 要使S_i=0，则需[X_axis，Y_axis]的区间很大或是L很大，才会使S_i逼近0.

假设x∈[0, 100]，L取值为1 000，则对于y=x₁²+x₂²问题，果蝇算法最大能求解的精度为e-11次方，而实际寻优精度为e-8次方；如果rand()每次扰动较小，则求解精度还会降低，这对于一些最优解在0点的优化函数尤其明显.无论是在全局或局部最优解附近，算法本身都不会再获得更好的求解精度，所以这就需要借助其它算法来增强寻优精度.基于上述讨论，本文提出了一种动态分组多策略果蝇优化算法.

2 动态分组多策略果蝇优化算法原理 2.1 基于佳点集理论的种群初始化

果蝇优化算法从随机初始一个位置矢量[X_axis，Y_axis]开始迭代，所有个体都是基于这个位置周围进行寻优.若这个位置在最优解附近，则能够加速算法收敛和提高寻优性能；否则会延缓收敛或陷入局部最优.所以，初期采用佳点集理论初始化所有个体的位置矢量，从中以最优个体的位置为寻优起始位置，有利于加速算法效率.佳点集理论已证明，当近似计算函数在s维欧氏空间单位立方体上积分时，用n个佳点构成的加权和比采用任何其它n个点所得到的误差都要小.已有学者^[16-17]将其应用到种群初始化，取得了很好的寻优效果，具体定义为：

设G_s是S维欧氏空间中的单位立方体，如果r∈G_s，形为p_n(k)={({r₁⁽ⁿ⁾k}，{r₂⁽ⁿ⁾k}，…，{r_s⁽ⁿ⁾k})，1≤k≤n}，其偏差φ(n)满足φ(n)=C(r，ε)n^-1+ε，其中C(r，ε)是只与r和ε(ε>0)有关的常数，则称p_n(k)为佳点集，r为佳点.一般情况下，取：

其中，p是满足的最小素数.

2.2 自适应分组策略

由FOA的进化原理可知，所有个体都向最优个体靠近，虽然加速了算法的效率，同时也降低了算法后期种群多样性和增加了陷入局部最优的概率.自然界中大多数生物的活动范围都具有一定领域性，子种群规模在某一时刻也相对固定.随着不断的觅食或是进化，其活动范围、规模和子群个数会随之发生变化.在进化过程中采用局部邻域则可有效地避免这种可能性.基于自然界中生物的领域特性，提出一种自适应分组策略来模拟这种特性，进而避免算法快速陷入局部最优，并且在进化过程中设置一个果蝇精英池(包含目前获得的C_num个最优个体)，具体分组方式为：

1) 将整个果蝇种群分成m个子群，每个子群包含n个果蝇.

2) 把果蝇种群内的个体按适应值降序排列，将前m个果蝇依次分配给m个子群，则第m+1个果蝇进入第1个子群，并采用贪心策略用当代最优个体更新果蝇精英池的个体.

3) 每迭代一次计算子群内果蝇个体的方差.用方差来衡量子群内个体的离散程度，方差越小说明离散程度越小，表明或是找到最优解，或是陷入局部最优.

4)递减子群个数m.令D_m^t(x)=[D₁^t(x)，D₂^t(x)，…，D_m^t(x)]为第t次迭代后的方差；，1≤i≤m.若存在一个远远小于其它α_k^t(x)(k∈{1，2，…，i-1，i+1，…，m})的α_i^t(x)，则说明该子群内的个体或是找到最优解，或是陷入局部最优，此时可以将该子群的个体分散到其它子群中，即m₁=m-1.针对寻优过程中可能存在各个子群内的α_i^t(x)相差不大的情况，若果蝇精英池里个体的方差也与α_i^t(x)相差不大，则说明整个种群或是已在最优解附近或是陷入局部最优，此时合并所有子群为1个群组；否则为了加速迭代需计算，其中，[]为取整函数，为初始的分组个数，迭代后期分组数设置为1.最后取m=min{m₁，m₂}.

这种分组方式使得在进化初期果蝇种群以子群方式在各自的领域活动；随着不断进化其子群个数逐渐减少，已找到全局最优解的子群个体分散到其它子群有利于加速迭代速度，对于陷入局部最优的子群则有利于其中的个体跳出局部最优解；依据上面的分组方式可知，在迭代后期所有个体会合并为一个种群进行寻优.

2.3 分组内个体进化方式

对于分组内非最优果蝇个体保持原有的进化方式，而对最优果蝇个体的更新方式进行改进.在基本果蝇算法中，最优个体通过随机移动位置来更新，若找到比当前位置更优的位置则代替，否则保持原个体，虽然可以保持个体的多样性，但同时也导致个体移动的盲目性.差分进化算法^[18]已被证明是进化算法中简单而最高效的算法^[19]，具有原理简单受控参数少的优势.其主要的变异操作在很大程度上影响着了该算法的性能^[20].采用式(8)更新组内个体：

(8)

其中，x_b、r₁、r₂分别为果蝇精英池内任意3个果蝇中适应度最优、较优和最差的果蝇；F为比例缩放因子，X_axisb和Y_axisb为适应度最优个体x_b的位置.如果适应度相差很小，说明两个果蝇个体在空间中相隔很近，则F_i应取较大值，以防止扰动量过小；如果适应度相差很大，说明两个果蝇个体在空间相隔很远，则F_i应取较小值，以限制扰动量过大，式(9)给出了一种确定方式：

(9)

其中，F_u、F_l为F_i的上限和下限，f_r1、f_r2、f_b分别为个体r₁、r₂和x_b的适应度.

2.4 迭代后期果蝇群体双子群进化原理

由果蝇算法的原理和文中分析可知，算法求解的精度在一定程度上受到随机扰动rand()和迭代次数L的制约；而且当到达某一迭代次数，其寻优精度在之后的迭代变化较小.出现这种情况的可能是由于：

1) 算法已经在全局最优解附近，只是FOA算法本身的原理造成很难再找到精度更高的解，这时需要通过另一种快速寻优算法来进行快速求精.

2) 算法已经陷入局部最优解，需要采用扰动技术来跳出局部最优.故本文在迭代后期通过将种群分为双子群来提高寻优效能，即分为优势子群和拓展子群.

2.4.1 双子群自适应分组方式

确定何时分组是分组的关键，根据上述果蝇算法的原理无论是找到全局最优解或是陷入局部最优解，其个体解的精度都是变化缓慢，而果蝇精英池里的个体是整个过程出现的最优个体集，如果这里的个体在一定迭代次数内精度不改变则可以将整个种群分为优势子群和拓展子群.具体分组方式如下：

step 1  统计果蝇精英池里的个体适应度精度不改变的次数，如果大于5次则执行step 2，否则不重新分组.

step 2  求解所有果蝇个体适应度值的平均值f_avg.

step 3  将适应度大于f_avg的果蝇个体分到优势子群；将适应度小于f_avg的果蝇个体分到拓展子群.

由于果蝇个体每次迭代都会对适应度排序，所以该分组方法对运行时间不会造成很大的影响.

2.4.2 优势子群进化方式

粒子群算法^[21]具有易实现、参数少和收敛速度快的优势. 表 1和表 2给出了PSO与FOA在求解(30维，最优值0)的对比结果，每个实验设置均独立运行20次，取20次的平均值作为最终的结果，种群个数为30.

从表 1和表 2可以看出，FOA在给定精度下求解速度较快，但是随着迭代次数的增加，FOA的求解精度变化不大；而PSO在达到给定精度后，则可以通过很少的迭代次数便可获得更高的精度.文中采用PSO进化优势群体中个体来提高求解精度.

将果蝇个体适应度计算过程中的S_i作为粒子群优化的个体，采用文[22]线性递减权值策略按照式(10)进行进化，同时也要把找到的最优值来更新果蝇精英池里的个体.

(10)

其中，r₁和r₂是(0，1)之间的随机数，c₁、c₂是加速常数，ω_max、ω_min分别是ω的最大值和最小值，t、t_max分别是当前迭代次数和最大迭代次数，P_g(t)为精英池里的最优个体，P_p(t)为个体最优值.

2.4.3 拓展子群进化方式

拓展子群用于跳出局部最优解，在拓展子群迭代期间获得的最优解仍采用贪心策略来更新精英果蝇群中的个体，进而可以影响优势子群的进化. Rahnamaya证明反向学习算法具有较快的学习速度和更强的优化能力^[23].

定义1  对于1维空间中任意一点x∈[a，b]，如果x′=a+b-x，则称x′为x的反向点.类似地，反向点也可以定义到高维空间中.

针对拓展子群内连续迭代3次没有改善的果蝇个体，按式(11)和式(12)计算新个体的位置(为了处理最优个体在负区间的优化问题，将式(3)中的S_i乘上一个sgn(·)函数)：

(11)

(12)

(13)

混沌映射产生的个体具有遍历性、随机性和多样性^[24]，可有效地在收敛区域以外空间搜索全局最优位置.文[25]的研究表明，偶数阶的Chebyshev映射可以生成随机性较好的个体.

2.5 算法流程

step 1  参数初始化，设置种群个数、最大迭代次数和精度.

step 2  利用佳点集理论初始化果蝇种群的初始位置.

step 3  按照自适应分组策略进行多子群寻优.

step 4  分组内个体采用2.3节算法完成个体进化，并利用2.2节策略完成子群的合并.

step 5  判断是否满足求解精度或是达到最大迭代次数.若满足，则退出.否则，判断是否需要将种群分成2个子群：如果需要，则按照2.4节算法来完成迭代后期果蝇群体双子群进化，跳转到step 6；否则跳转到step 3；

step 6  对于优势种群个体采用式(10)进化，变异种群个体采用式(11)~式(13)进化，跳转到step 5.

3 实验仿真

运行的实验环境为：Windows 7操作系统，Intel酷睿i5处理器，主频2.5 Hz，4 G内存，开发工具为Matlab.测试函数的选取具有一定的代表性，f₁~f₄的极值在0点，用于测试DGM-FOA寻优精度；f₅~f₆在定义域的正区间，f₇~f₈在定义域的负区间，用于测试DGM-FOA在负区间的寻优性能.通过10个求解函数极值优化的例子来验证算法的优化性能，将所提算法与万有引力算法^[26](GSA)、经典果蝇算法(FOA)、文[8]的DDSCFOA(dynamic double subgroups cooperative fruit fly optimization algorithm)和文[9]的LFOA(double subgroups FOA with the characteristics of lévy flight)进行性能比较.

3.1 固定迭代次数和精度的性能测试

种群大小都设置为50，最大迭代次数设置为2 000，精度满足10e-12，优化函数维数30，对优化函数独立运行20次. GSA参数设置：G₀=100，α=20；DGM-FOA的参数设置：c₁=1.496 18，c₂=1.496 18，ω_max=0.9，ω_min=0.3.对比5种优化算法获得的最优结果、最差结果、平均结果、平均运行时间和方差.其中，最优结果、最差结果反映解的质量，平均结果显示算法所能达到的精度，平均时间反映算法的收敛速度，方差反映算法的稳定性和鲁棒性.测试函数分别为

其全局最优值为x^*=[0，…，0]，f(x^*)=0.

其全局最优值为x^*=[0，…，0]，f(x^*)=0.

其全局最优值为x^*=[0，…，0]，f(x^*)=0.

其全局最优值x^*=[0，…，0]，f(x^*)=0.

其全局最优值为x^*=^{[1, 1, 1, 1]}，f(x^*)=0.

其全局最优值为x^*=[1，…，1]，f(x^*)=0.

其全局最优值为x^*=[-2.903 534，…，-2.903 534]，f(x^*)=-39.165 99n.

其全局最优值为x^*=[0.089 83，-0.712 6]，[-0.089 83，0.712 6]，f(x^*)=-1.031 628 423.

3.2 高维函数上的优化性能测试

对优化函数f₁、f₂、f₃、f₄在维度为N=100、N=200的条件下对比DGM-FOA与经典的GSA和FOA的性能，各类算法的运行参数设置见3.1节，最大迭代次数为1 000，误差精度为10e-6.函数在每个算法中独立运行20次，计算平均结果、方差和平均时间.

从仿真结果对比可以看出，所提的动态分组多策略果蝇优化算法具有很好的求解精度和求解速度.分析原因，主要有3个方面：

1) 从最优结果、最差结果、平均结果可以看出，DGM-FOA寻优结果最好，主要因为：采用佳点集理论增加了个体接近最优解的机会，前期引入的动态分组和差分变异算子可以加速算法寻优，后期引入的粒子群算法可以增加寻优精度，混沌理论使算法进化后期很好地避免陷入局部最优，进而克服了算法在求解某些复杂函数时收敛速度慢、容易陷入局部最优的缺点.从f₇和f₈的运行结果可以看出，DGM-FOA的结果要优于DDSCFOA和LFOA，主要是由于DGM-FOA在负区间进行寻优的效果得到增强，克服了原有FOA不能求解负区间的问题.

2) 从方差和时间可以看出，DGM-FOA的运行时间和方差都优于前几种算法，分析其原因是：GSA的进化思想与FAO相类似，都是利用吸引方式使非优解向最优解靠近，但由于GSA的进化原理相对复杂，故其运行时间较多.而DGM-FOA的进化原理简单、计算量少，加速了算法的求解速度，同时利用小生镜的方式进行寻优，分组个数随着迭代过程逐渐减少，这样有利于前期进行全局寻优，后期进行局部精细挖掘且DGM-FOA在进化过程中采用差分变异和混沌策略使得个体更新时既保持了随机性，又使得个体变化带有确定性，与经典算法的随机方式相比更易向最优解方向靠近，而优势种群个体借用PSO的优势可以提高算法精度，其收敛的速度得到很大提高，使得运行时间相对较短.分析DGM-FOA的计算复杂度可知，虽然在分组方面增加了算法的计算量，但依据算法渐近复杂性理论可知，并未增加基本果蝇算法的时间复杂度，但是由于分组寻优和个体进化方式的改进大大地提高了DGM-FOA在每个迭代周期里的寻优性能，避免了FOA在迭代后期多次迭代计算寻优精度不高的问题，故获得了较好的寻优精度和速度.

3) 从高维函数测试的优化效果可知，随着维度的增加，经典GSA的运行时间增加幅度较大且求解精度下降，而DGM-FOA依靠FOA求解简单、寻优速度快的特点，利用PSO的优势和小生镜技术大大地改进了经典FOA的不足，同时加速了寻优速度和精度，尤其是在高维函数寻优性能的稳定性上得到了很大的改进.由于实验设定迭代次数为1 000，造成GSA的表现性能不是很好，通过进一步增加迭代次数发现，算法的寻优结果也会得到改善，这也说明本文所提算法在较短的迭代周期内能获得较好的寻优速度和精度.

4 结束语

本文提出一种动态分组多策略果蝇优化算法，并将自适应小生镜、差分变异等算法引入到个体更新过程中.基于高维测试函数的仿真实验结果表明，算法在整体上具有较好的全局寻优能力且收敛速度较快.今后将对算法在实际应用的适应性方面进一步展开研究，同时对果蝇优化算法理论分析及与其它算法进行优势融合等方面进行探索.