混沌动态步长果蝇优化算法*
2019-08-15廖建庆王咸鹏
廖建庆， 王 涵， 王咸鹏
(1.宜春学院 物理科学与工程技术学院，江西 宜春 336000； 2.海南大学 南海海洋资源利用国家重点实验室，海南 海口 570228)
0 引 言
果蝇算法[1](fruit fly optimization algorithm，FOA)是台湾学者潘文超首次提出的一种新的群智能算法。该算法是一种基于果蝇觅食行为而推演出的全局优化算法，已成功应用于求解函数优化[2]、PID控制参数优化[3]、支持向量机参数优化[4]等领域。由于FOA起步较晚，虽然国内外相关研究成果比较多，对算法的改进研究也比较成熟，但较少有文献从理论上对FOA及其改进算法的收敛性方面做深入研究。相较其他群智能算法，FOA具有结构和计算简单、运行时间和可调参数少等优点[5]。比如FOA仅有4个参数需要调整，而有些优化算法需要调整的参数相对较多，较多的参数不仅增大了调整工作量，而且还给算法分析带来巨大困难，有时甚至还会出现使用一种算法去优化另一种算法参数的情况。当然，由于算法自身的特点，FOA与其他优化算法一样，也存在局部最优、早熟收敛等不足。
本文提出了一种混沌动态步长改进的果蝇优化算法(modified fruit fly optimization algorithm with chaotic dynamical step factor,CDSFOA)，通过利用混沌特性来提高果蝇种群的多样性和搜索的遍历性，引入混沌扰动变量来提高算法的持续搜索能力；同时，通过引入动态步长调节因子对果蝇搜索步长进行随机动态调节，使得算法的收敛速度得到进一步提高。因此，提出算法能有效地提高种群的多样性和搜索的遍历性，进而提高算法精度，避免陷入局部最优。
1 标准果蝇优化算法[6]
1)初始化:种群规模数、最大迭代次数和随机初始化果蝇群体位置;
2) 给果蝇方向和距离分配随机参数，产生新位置;
3)估算果蝇与原点之间距离Disti，再计算味道浓度判定值Si;
4) 将Si分别代入味道浓度判定函数，求出果蝇位置味道浓度Smelli;
5)对Smelli值进行排序，找出当前Smelli最大的果蝇个体;
6) 根据最佳果蝇序号和位置，此时所有果蝇利用视觉向最佳位置飞去;
7) 最后迭代运算，重复步骤(2)～步骤(5)，在寻优过程中判断当前最佳味道浓度是否优于上一迭代结果，且判断当前迭代次数是否小于最大迭代数；若是则执行步骤(6)，否则结束。
2 混沌动态步长果蝇优化算法
2.1 动态步长调整策略
在基本FOA中，迭代步长的选择直接影响最佳浓度位置，进而影响算法收敛速度和精度。本文借鉴文献[7]的思想，引入一种动态步长因子(dynamic step factor，DSF)来动态地调节搜索步长，即对方向与距离产生的随机搜索步长(Randvalue)分配不同的步长调节因子w(n)来实现对其自适应地动态调节
w(n)=w0·exp[-20(n/M)a]
(1)
Randvalue=w(n)×(2·rand-1)
(2)
式中n为迭代次数，M为最大迭代次数Maxgen，w(n)为动态步长调节因子，a为调节参数，是可视具体情况取值范围为[1,30]的整数[8]，rand∈[0,1]为随机函数。则果蝇个体利用嗅觉搜寻食物的随机方向与距离表达式调整为
式中 (X0，Y0)为随机初始化果绳群体位置。则动态步长调节因子w(n)随迭代次数的动态变化。
2.2 混沌优化
混沌优化算法[9]是一种利用混沌运动特性进行优化搜索方法，本文引入Logistic映射，其数学模型为
x(k+1)=μx(k)[1-x(k)]
(4)
式中k为迭代次数，x(k)∈[0,1],μ为控制变量，研究表明，当x(k)≠0,1时，Logistic映射处于混沌状态[10]。依据式(4)，混沌变量Cxj(k)的一种变换式为
Cxj(k+1)=4Cxj(k)(1-Cxj(k))
(5)
式中Cxj为第j个混沌变量，显然当Cxj(0)≠0,1时，将产生混沌现象。式(5)中的优化变量xj(k)∈[xL,j,xU,j]，利用式(6)和式(7)与混沌变量Cxj(k+1)进行往返映射
Cxj(k)=(xj(k)-xL,j)/(xU,j-xL,j)
(6)
式中xL,j和xU,j(j=1,2,…,n)分别为第j维变量的搜索上界和下界；x′j(k)为经混沌映射后的第j个混沌变量Cxj(k)转化为优化变量而获得的值。
2.3 CDSFOA算法步骤
1)初始化群体规模、最大迭代次数、随机种群位置、混沌遍历次数和味道浓度方差阈值分别设置为Sizepop,Maxgen,X0,Y0,M和H。
2)执行基本果蝇优化算法步骤(3)～步骤(6)。
3)根据式(1)～式(3)对更新搜寻步长和位置分别进行更新后再进行迭代运算，重复步骤(2)。
4)计算Smellavrage和味道浓度方差d2
5)若满足条件d2
6)计算新位置(X′i,Y′i)与原点之间Dist′i和S′i
7)根据S′i求解果蝇个体Smell′i
Smell′i=Function(S′i)
(10)
8)判断Smell′i和Smellbest二者大小，前者大于后者，则转到步骤(9)，否则Smellbest=Smell′i，(X0,Y0)=(X′i,Y′i)，然后转到步骤(5)。
9) 判断Smellbest是否为定值，若是则按式(11)引入混沌扰动，然后转步骤(4)，否则执行步骤(10)
Xaxist=Xi(bestIndex)+tCx′i,
Yaxist=Yi(bestIndex)+tCy′i
(11)
式中Cx′i和Cy′i为当前最优解位置的混沌扰动变量，t<1为扰动调节参数。
10)进入迭代寻优，重复执行步骤(3)～步骤(9)，并记录每代Smellbest和(X′i,Y′i)，判断Smellbest是否为最优解，如果是则停止，否则，重复上述步骤直到当前迭代次数等于最大迭代次数，搜索结束。
3 仿真实验与结果分析
3.1 实验设计
选取f1～f8分别为Sphere,Griewank,Rosenbrick,Rastrigin,Apline,Schwefel,Ackley,Schaffer进行测试函数，各函数形式、搜索范围、理论最优值和峰值见文献[9]。其中，f1和f3是单峰函数，f2和f4～f8为多峰函数。这些函数都具有很好的测试性能，通常用来测试难度较大的复杂优化问题，能够有效地检验CDSFOA算法的优化性能及收敛性。
通过与粒子群算法(PSO)、蝙蝠算法(BA)、协方差矩阵自适应进化策略算法(CMA-ES)、FOA算法的实验结果进行比较，用以验证CDSFOA算法优化性能。上述4种算法的种群规模设置为30，维数设置为30。各算法参数设置为：1)PSO算法：c1=c2=1.5，w=0.75，vmax=0.66(最大速度)；2)BA算法：A=0.25，alf=0.85，BAma=0.02，r=0.50；3)CMA-ES算法：其参数设置参见文献[10]；4)FOA算法：随机初始化果蝇群体位置参见文献[9]中各测试函数的自变量搜索范围；5)CDSFOA算法：步长调节参数a=5，混沌遍历次数M=5，适应度方差阈值H=0.000 1，若经过3次迭代后最优解仍相同，则引入混沌扰动，扰动调节参数t=0.2，随机初始化果蝇群体位置参见文献[9]中各测试函数的自变量搜索范围。
3.2 结果与分析
3.2.1 固定进化迭代次数的性能验证
将6个测试函数f1～f6固定进化次数为1 000次，分别采用PSO，BA，CMA-ES，FOA和CDSFOA算法经过20次独立运行，并分别将运行得到的最优Smellbest值进行最优值(best)、优化均值(mean)、计算以及平均运行时间来表征，维数均设置为30，得到的实验结果如表,1所示。
表1 各算法性能比较
由此可见，与PSO，BA，CMA-ES，FOA算法相比，本文提出的CDSFOA算法都能找到或更接近理论的最优值，其求解得到的最优值、最差值、优化均值和标准方差均优于POS、BA、FOA算法；该算法搜索时间比PSO、BA和CMA-ES三种算法都要短，虽然CDSFOA算法相比FOA算法的搜寻最优值时间都要长，这主要是因为CDSFOA算法对果蝇群体进行了自适应动态步长的调节操作和引入了混沌扰动操作，但可以发现，本算法在时间上只是略长于FOA算法(0.01～1.0 s)，但本算法所获得的寻优精度确是FOA算法精度的几个数量级，这说明本算法相比其它优化算法具有更高的精度以及更好的鲁棒性和稳定性。同时也进一步说明CDSFOA算法的复杂度较低及其可行性和有效性。
3.2.2 算法在多维和单、多峰函数上的性能验证
为了比较和突出CDSFOA算法在不同维、单峰和多峰函数上的优越性能，将4种算法与CDSFOA算法在不同测试函数上，对维数D依次递增的情况下各算法的优化均值(Mean)进行试验比较。在不同测试函数条件下，对各算法独立运行20次，算法参数设置同前所述。各测试函数的维数从最低维(D=20)依次递增至最高维(D=150)，各算法之间的优化均值(Mean)进行比较， 结果如表2所示。
表2 在多峰函数和高维上的优化均值比较
可知，随着测试函数的高维数D的增加，CDSFOA算法的优化均值基本在同一数量级内变化，且比较接近理论最优值，但PSO，BA，CMA-ES，FOA算法则随着维数D的增加，其优化均值逐渐远离理论最优均值，当维数D增加至大于100以后，其优化均值则以一个甚至几个数量级的速度远离最优值，BA算法甚至在高维情况下还出现了“维数灾难”。这表明随着维数的增加，特别是维数高于100时，CDSFOA算法对高维的复杂函数仍保持平稳且较高精度的寻优性能。
4 结 论
根据FOA的特点，引入动态步长调节因子与混沌优化理论相结合，提出了一种具有分工明确、优势互补的果蝇优化改进算法。一方面利用混沌特性提高了算法的种群多样性，通过引入混沌扰动量将果蝇个体跳出局部最优，使得算法具有持续的全局搜索能力；另一方面，通过引入动态步长调节因子对果蝇个体的搜索步长进行随机动态调节，使得算法具有更快的收敛速度。仿真实验验证结果表明：相较PSO、BA、CMA-ES、FOA算法，CDSFOA具有较高的收敛速度和寻优精度，尤其针对高维、多峰函数，该算法比其他算法的优越性能更佳。
