双策略协同进化果蝇优化算法及其应用

石建平,刘国平,李培生,陈冬云,刘 鹏

(1.贵阳学院 电子与通信工程学院，贵州 贵阳 550005；2.南昌大学 机电工程学院，江西 南昌 330031；3.河北地质大学 宝石与材料工艺学院，河北 石家庄 050031)

0 引言

果蝇优化算法(Fruit fly Optimization Algorithm，FOA)是台湾学者PAN[1]受果蝇觅食行为的启发而提出的一种新型群智能优化算法，该算法具有寻优机制简单、控制参数少、容易编程实现以及较好的收敛效果等优点，从而在财务危机预警建模[1]、多维背包问题[2]、神经网络训练[3]、电力负荷预测[4]、PID参数整定[5-6]、联合补给问题[7]、函数优化[8]及调度问题[9-10]等诸多领域得到应用推广。然而，如同FOA的优点一样，该算法的不足同样也很明显：首先，FOA中的气味浓度判定值不能取负值，导致算法不能优化具有负值搜索空间的优化问题；其次，FOA采用非线性的候选解产生机制，使得算法无法在指定区域内按均匀分布搜索；再次，FOA在寻优过程中采取只向种群最优个体学习的简单搜索方式，导致种群的容易丧失多样性而陷入早熟收敛；最后，FOA缺乏逃离局部极值束缚的机制，导致算法的全局探索能力不强。

为克服FOA的上述不足，广大学者围绕FOA的改进展开了深入的研究，提出了许多有效的改进方案。文献[6]将细菌趋化理论引入果蝇优化算法，提出了多驱逐剂与多引诱剂的概念，进而提出了双重驱动的改进果蝇优化算法；文献[7]从种群多样性的保持、避免局部最优的智能搜索以及通过随机扰动增强算法跳出局部极值的能力等多方面来改善算法的收敛质量；文献[8]借助一个控制参数实现在群位置附近自适应调整搜索范围，并提出了新的候选解生成方法来提升算法的收敛精度与收敛速度；文献[11]基于果蝇个体历史最佳记忆信息和种群全局历史最佳记忆信息构建了多策略混合协同进化的搜索机制，进而提出了用于解决约束优化问题的改进果蝇优化算法；文献[12]通过引入一个逃逸参数解决了气味浓度判定值不能取负值的不足，并将果蝇个体的搜索范围拓展至三维空间；文献[13]提出一种基于候选解线性产生机制的改进果蝇优化算法，该算法同样解决了气味浓度判定值不能取负值的不足，同时引入一个惯性权重因子来平衡算法的全局与局部搜索；文献[14]将文献[13]中的惯性权重取值与算法的最大迭代次数相关联，并引入前N个优秀候选解的平均候选解来取代种群中的一个候选解，提高了算法的搜索效率及可靠性；文献[15]提出一种基于多子群进化的改进果蝇优化算法，通过各子群在搜索空间的独立搜索有效提高了算法的收敛性能；文献[16]引入一个具有混沌行为的参数来改善算法的寻优性能，进而提出了混沌果蝇优化算法；文献[17]提出了新的气味浓度判定值生成方案，并借助不同个体间的差异信息来引导果蝇位置的更新；文献[18]提出一种具有智能选择进化方向的改进果蝇优化算法；文献[19]提出了基于双子群和分区采样的果蝇优化算法，该算法将果蝇种群分为搜索子群和跟随子群，并采用分区采样的搜索果蝇位置更新策略；文献[20]通过多尺度协同变异操作来扩展果蝇的搜索空间并改善种群的多样性，从而有效提高了算法的全局搜索能力；文献[21]借助符号参数使得气味浓度判定值能够在负值空间中取值，但其取值仍基于非线性产生机制，无法在指定区域内均匀搜索的问题依然存在；文献[22]从搜索方向与搜索步长的优化选择和自适应调整、自适应交叉与变异、双子群协同进化等多方面对FOA进行综合改进，使得算法的寻优质量得到较大提升；文献[23]提出一种自适应果蝇优化算法，该算法根据成功的历史经验来得到一个适当的决策变量，然后依据该决策变量自适应产生新的候选解；受正弦余弦算法的启发，文献[24]通过果蝇个体向外或向内飞行的方式来寻找全局最优解；文献[25]提出了基于随机游走的果蝇优化算法，该算法利用随机游走机制动态调整果蝇种群的位置，从而增强了算法的全局寻优能力。

针对基本FOA的上述不足，本文提出一种基于双策略协同进化的果蝇优化算法(Double Strategies Co-evolutionary Fruit Fly Optimization Algorithm, DSCFOA)，该算法采用将果蝇位置直接赋值给气味浓度判定值的候选解线性生成机制，使得候选解可以取负值并能均匀分布于指定的搜索区域；DSCFOA将从种群的初始化、双策略协同嗅觉搜索、实时视觉更新以及果蝇位置的越界处理等多方面进行综合改进，从而较好地兼顾了种群的多样性与收敛性，使得算法的整体收敛质量有较大幅度提升。用典型的基准测试函数验证了DSCFOA的可行性与有效性，并将其应用于解决冗余机械臂的逆运动学问题，检验了该算法解决实际工程优化问题的能力。

1 果蝇优化算法

根据文献[1]，FOA的优化过程简述如下：

步骤1种群位置(X_axis,Y_axis)的初始化。

步骤2更新果蝇i的位置(Xi,Yi)。

(1)

式中RandomValue为位置更新的随机步长值。

步骤3计算果蝇i的气味浓度值Smelli。

Smelli=F(Si)；

(2)

(3)

式中：F(·)为适应度函数；Si为果蝇i的气味浓度判定值；Disti为果蝇i相对于坐标原点的距离。

步骤4针对最小优化问题，由式(4)找出当前代种群中具有最高气味浓度值的果蝇bestIndex。

[bestSmellbestIndex]=min(Smelli)。

(4)

式中：bestSmell为最高气味浓度值；bestIndex为与bestSmell对应的果蝇个体序号；min(·)为求最小值函数。

步骤5按式(5)保存最高气味浓度值及其对应的位置坐标，果蝇种群利用视觉飞向该位置。

(5)

步骤6重复循环步骤2～步骤4，与上一代种群的最高气味浓度值相比，若当前代种群具有更高的气味浓度值且迭代次数小于最大迭代次数，则转步骤5；若算法迭代次数达到最大值，则输出寻优结果并退出迭代循环。

2 改进的果蝇优化算法

2.1 基于佳点集的种群初始化

个体在搜索空间内的均匀分布能够使得种群具有更强的多样性，进而有助于改善算法的全局搜索能力。佳点集是一种有效的均匀选点方法，以二维单位搜索空间为例，根据文献[26]的佳点集产生原理得到的点分布和采用随机方法得到的点分布如图1所示。显然，与随机初始化种群相比，佳点集方法能够使得初始种群均匀地分布在搜索空间中。因此，本文利用佳点集方法对DSCFOA进行种群的初始化。

2.2 双策略嗅觉搜索

在FOA中，整个果蝇种群只向当前最优果蝇个体学习，即在当前最优果蝇位置附近的固定范围内进行局部随机搜索，若该位置是搜索空间中的局部最优位置，则算法很难逃离局部最优的束缚而陷入早熟收敛。为增强算法的全局搜索能力，应该充分挖掘并利用所有果蝇个体的成功搜索经验。为此，本文对整个果蝇种群进行等级划分，将其分为精英领导层果蝇个体和普通果蝇个体，领导层由种群P中的前3个具有最高气味浓度值的果蝇构成，领导层负责集体引导果蝇种群的嗅觉寻优搜索。同时引入双策略协同进化的嗅觉搜索机制，使其形成优势互补以更好地平衡算法的全局探索与局部开发。具体的嗅觉搜索算子如下：

(6)

(7)

(8)

式中：P′1、P′2及P′3分别代表种群P中适应度最优的前3个果蝇个体，他们构成了果蝇种群的领导层；N(0,1)为D维的随机向量，由服从标准正态分布的一个随机变量扩充而成，即N(0,1)的各分量相同；r1是在(1,2,…,m)中随机选择且满足r1≠i的一个整数；r1、r2及r3为[0,1]内均匀分布的随机变量；ω为扰动比例因子，同时也决定了进化策略的选择概率；t为算法的当前迭代次数，tmax为算法的最大迭代次数。

在双策略嗅觉搜索方案中，策略1(XL+2×r1×(Pr1(t)-Pi(t))+N(0,1)×ω)由3部分构成：第1部分是由领导层精英个体构成的中心位置向量XL，第2部分是利用不同果蝇个体间的差异信息构成的随机差分向量2×r1×(Pr1(t)-Pi(t))，第3部分是由一个服从标准正态分布的随机变量扩充而成的D维随机向量N(0,1)×ω。 策略1使得当前果蝇向领导层精英个体学习，且种群中不同个体间的差异信息以及D维随机向量N(0,1)×ω确保了学习结果的多样性，从而有效避免了FOA只向最优个体学习所导致的早熟收敛现象，使得算法的全局搜索能力得到有效提高。双策略嗅觉搜索方案中的策略2 ((1-ω)×P′1+ω×(Pi(t)-Xi(t)))由历史最优果蝇个体得到扰动中心位置(1-ω)×P′1，利用个体的记忆信息构建差分向量ω×(Pi(t)-Xi(t))用于对该中心位置进行扰动搜索，该策略使得果蝇个体通过向种群最优个体及自身成功历史经验的学习来引导其嗅觉搜索，可以有效加快算法的收敛速度。根据式(6)，算法按概率随机选择其中的一个策略作为当前果蝇个体的嗅觉搜索算子，两个策略的随机交替使用能够较好地避免单一进化策略易导致算法早熟收敛而陷入局部最优。另外，根据ω的取值规律，算法在进化的前期阶段以较大的概率选择策略2作为当前果蝇的嗅觉搜索算子，有助于在进化的前期阶段加速算法的收敛速度；而在进化的后期阶段，由于果蝇种群逐渐向最优个体附近聚集而呈现趋同现象，此时算法以较大的概率选择策略1作为当前果蝇的嗅觉搜索算子，有助于改善算法的全局搜索性能。总之，改进算法的嗅觉搜索融合了人类认知过程中的自我学习与社会学习思想，实现了进化过程中的信息增值，从而有效兼顾了算法的收敛性与种群的多样性。

设算法的最大迭代次数tmax=600，根据式(8)可得比例因子ω在一次进化过程中的取值演变过程，如图2所示。可见，通过引入随机因子r3，使得比例因子ω在逐渐向下压缩的范围内随机取值。这种取值方式使得算法在进化的前期阶段具有较大的扰动范围，从而具有较强的全局搜索能力；而在进化的后期阶段，算法的局部搜索能力得到增强，从而达到进一步提升算法收敛精度的目的。

2.3 实时视觉更新

FOA中，视觉搜索是指式(1)中种群位置(X_axis,Y_axis)的更新。而在DSCFOA中，视觉搜索是指式(6)中扰动中心位置向量XL与(1-ω)×P′1的更新。本文按式(9)对果蝇位置进行实时评估并更新其最佳历史信息，同时对种群的领导层进行动态实时更新，以充分利用每个果蝇个体的成功搜索经验。

(9)

通过上述果蝇个体的实时评估与更新，间接实现了嗅觉搜索算子式(6)中扰动中心位置向量的实时更新，同时充分利用了所有果蝇个体的成功搜索经验，有效提高了算法的收敛速度。

2.4 越界处理

为进一步改善种群的多样性，针对在搜索过程中个体位置超出搜索空间范围的现象，按下式进行处理：

(10)

式中：r4为[0,1]内均匀分布的随机变量；Xmax,j为搜索空间上边界向量Xmax的第j维分量；Xmin,j为搜索空间下边界向量Xmin的第j维分量。

2.5 算法步骤

DSCFOA的进化流程如图3所示。

DSCFOA的进化步骤如下：

步骤1设置果蝇个体位置的搜索范围、种群规模、算法的最大迭代次数等相关参数，用佳点集方法初始化果蝇种群，设置i=1，t=1，Pi=Xi。

步骤2将种群P按适应值从小到大进行排序，选择适应值最小的前3个果蝇个体为种群的当前领导层。

步骤3果蝇i按照式(6)～式(8)执行嗅觉搜索，按式(10)进行越界处理。

步骤4对果蝇i的位置进行实时评估，按式(9)实时更新果蝇个体的历史最佳信息，实时更新种群的领导层。

步骤5i=i+1，若i

步骤6若t

2.6 算法的时间复杂度与计算成本

时间复杂度是评判一个算法性能优劣的重要指标之一，它反映了算法的收敛速度。已知种群规模、搜索空间的维度以及算法的最大迭代次数分别为m、D及tmax，设产生佳点每一维分量的时间为t1，由佳点分量初始化果蝇个体位置分量的时间为t2，计算目标函数适应值的时间为f(D)，对果蝇种群按适应值从小到大进行排序的时间为t3，则DSCFOA种群初始化的时间复杂度为：

O(m(Dt1+Dt2+f(D))+t3)=O(D+f(D))。

(11)

设产生果蝇个体位置分量的时间为t4，对果蝇个体位置分量进行越界处理的时间为t5，适应值比较与更新的时间为t6，则DSCFOA在循环迭代阶段的时间复杂度为：

O(tmaxm(Dt4+Dt5+f(D)+t6+t3))=O(D+f(D))。

(12)

于是，DSCFOA总的时间复杂度为：

T(D)=O(D+f(D))+O(D+f(D))=O(D+f(D))。

(13)

在FOA中，设产生种群位置分量的时间为t′1，则FOA种群初始化的时间复杂度为：

O(Dt′1+f(D))=O(D+f(D))。

(14)

设产生气味浓度判定值每一维分量的时间为t′2，寻找种群中最优个体的时间为t′3，适应值比较与更新的时间为t′4，则FOA在循环迭代阶段的时间复杂度为：

O(tmax(m(Dt′2+f(D))+t′3+t′4))=O(D+f(D))。

(15)

于是，可得FOA总的时间复杂度为：

T(D)=O(D+f(D))+O(D+f(D))=O(D+f(D))。

(16)

由式(13)和式(16)可知，DSCFOA和FOA具有相同的时间复杂度，即上述改进策略并没有增加DSCFOA的时间复杂度。

最后，从算法的计算成本来看，以种群规模m=60和最大迭代次数tmax=600为例，DSCFOA循环迭代阶段的函数总评估次数为60×600=36 000次，与FOA循环迭代阶段的函数总评估次数相同。因此，DSCFOA与FOA具有相当的计算成本。

3 基准函数测试

3.1 基准函数与参数设置

用表1中8个经典的基准测试函数来检验DSCFOA的收敛性能。表中：前4个函数为单峰函数，用于检验算法的收敛精度与收敛速度；后4个为具有多个局部极值的多峰函数，用于检验算法的全局搜索能力。

表1 基准测试函数

DSCFOA涉及的参数有种群规模m和最大迭代次数tmax，用表1中的函数f2和f6来讨论这两个参数对算法收敛性能的影响。设函数的维度D=30，最大迭代次数tmax=600，不同种群规模时算法连续独立运行30次的最优适应值(Best)、平均适应值(Mean)、最差适应值(Worst)、标准差(Std.)以及收敛于理论最优值的函数平均总评估次数(TNE)如表2所示；设函数的维度D=30，种群规模m=60，不同最大迭代次数时算法连续独立运行30次的收敛性能统计如表3所示。表中“—”表示在该组试验中存在算法不能收敛于函数理论最优的情形，故未统计该组试验的TNE值。

表2 不同种群规模的算法收敛性能

表3 不同迭代次数的算法收敛性能

续表3

根据表2和表3可知，当种群规模m≥40时，算法都能够稳定收敛于函数f2和f6的理论最优值，且随着种群规模的增大，算法的有效函数评估次数也随之增加(有效函数评估次数是指算法收敛于函数理论最优所需的最少评估次数)；对于函数f2，当最大迭代次数tmax>300时，算法能够稳定收敛于函数的理论最优值(继续增大算法的最大迭代次数，则算法的有效评估次数也随之增加)；对于函数f6，算法只需迭代一次即可稳定收敛于函数的理论最优值，因此算法的有效评估次数变化不大。由于表2和表3中的试验结果只是为算法的参数设置提供了一个指导性的建议，欲寻求一个对所有优化问题都达到最佳优化效果的参数值是不现实的。因此，在本文的后续试验中，为兼顾算法在解决文中所涉及优化问题时的收敛质量与计算成本，将DSCFOA的种群规模和最大迭代次数分别设置为60和600。

3.2 DSCFOA与其他优化算法的比较

为验证DSCFOA的有效性，将DSCFOA与FOA、LGMS-FOA(linear generation mechanism of candidate solution-based FOA)[13]、AE-LGMS-FOA(LGMS-FOA with an additional averager engine)[14]、IFOA (improved FOA)[7]及SFOA (signed FOA)[21]进行试验对比分析。所有算法的种群规模和最大迭代次数分别为60和600；FOA的随机初始化种群位置范围为[0,10]，果蝇觅食的随机方向和距离为[-1,1]；LGMS-FOA算法中ω0=1、α=0.95、n=0.005；AE-LGMS-FOA中p=0.005、ω0=1、n=10，且用种群的前80%优秀个体来产生XAv；IFOA中设置50%的果蝇个体朝最优解飞行，其余果蝇执行随机飞行，扰动放大系数ω=0.3。

考虑基准函数的维度D=30，各算法分别连续独立运行30次的寻优结果统计如表4所示，各函数的平均适应值收敛曲线如图4所示。

表4 不同算法的基准函数寻优统计结果

续表4

由表4可知，DSCFOA在8个函数中能够稳定收敛于其中7个函数(f1～f6及f8)的理论最优值；对于函数f7，DSCFOA也获得了较高的收敛精度，且各项性能指标都远优于其他算法；其他算法都未能收敛于函数的理论最优值(LGMS-FOA能够收敛于f5、f6及f83个函数的理论最优值)，说明DSCFOA具有较强的全局搜索能力，与其他算法相比，DSCFOA的优势比较明显。从图4可知，DSCFOA的平均适应值收敛曲线具有最快的下降速度，并获得了最低的下降位置(为便于显示和观察，本文将所有函数的适应值取以10为底的对数)，说明了DSCFOA具有收敛速度快、收敛精度高的优点。对于函数f1、f3、f5、f6及f8，因为DSCFOA只需进化一代便收敛于函数的理论最优值，所以图中未显示DSCFOA的平均适应值收敛曲线。

根据前述分析，在相同迭代次数的前提下， DSCFOA与FOA的计算成本相当，而DSCFOA快速的收敛速度使得其有效函数评估次数大幅度降低。因此，在相同函数评估次数的前提下， DSCFOA具有比FOA更高的收敛质量。

3.3 DSCFOA的高维函数优化性能分析

为检验DSCFOA算法解决高维优化问题的能力，考虑表1中测试函数的维度分别为100、200、300、400及500维的情形。DSCFOA的参数设置与前述相同，各函数分别连续独立运行30次，算法的寻优结果如表5所示。

表5 DSCFOA对高维函数的寻优统计结果

根据表5可知， DSCFOA在8个函数中能够稳定收敛于其中7个函数(f1～f6及f8)的理论最优值，且对于不同维度的同一函数，算法的有效函数评估次数差别不大；对于函数f7，DSCFOA也获得了较高的收敛精度，且寻优结果稳定性好。可见，DSCFOA在解决高维优化问题中同样表现出了较强的全局寻优能力。

4 用DSCFOA求解机械臂逆运动学问题

机器人的逆运动学问题本质上是一个复杂非线性超越方程组的求解，该问题是研究机器人动态特性分析、轨迹规划和运动控制的基础。近年来，群智能优化算法[27-34]被广泛应用于机器人的逆运动学求解，为解决机器人逆运动学问题提供了有效的解决方案。本文采用平面冗余机械臂来验证所提算法在逆运动学求解中的可行性与有效性。

4.1 正向运动学方程与目标函数

本文采用D-H法为机械臂模型各连杆建立的坐标系如图5所示。机械臂的正向运动学方程是以关节角为自变量的复杂非线性方程组，其表达式如下：

(17)

(18)

4.2 仿真试验及其分析

设机械臂末端执行器的期望位姿为：

各算法分别独立连续进行100次仿真试验，其寻优结果如表6所示，各算法的平均适应值收敛曲线如图6所示，各算法最优适应值对应的一组运动学逆解如表7所示，各逆解对应的位姿误差如表8所示，各逆解对应的实际位姿如图7所示。

表6 不同算法的适应值统计结果

表7 不同算法的一组最优运动学逆解

表8 不同算法的位姿误差

由表6和图6可知，DSCFOA求得的机械臂运动学逆解能够使得末端执行器稳定收敛于期望位姿，其收敛质量远优于其他算法；AE-LGMS-FOA获得了仅次于DSCFOA的收敛性能，LGMS-FOA的收敛性能又略差于AE-LGMS-FOA；FOA、IFOA及SFOA的寻优效果不够理想。由表8的位姿误差来看，DSCFOA的位姿误差为0；AE-LGMS-FOA和LGMS-FOA的最优逆解也获得了较高的位姿收敛精度；FOA、IFOA及SFOA的位姿误差明显大于DSCFOA、AE-LGMS-FOA和LGMS-FOA，特别是其位置误差尤为突出。从图7可直观观察表7中各逆解所对应的实际位姿，进一步验证了上述结论。综上所述，本文提出的DSCFOA可有效解决机械臂的逆运动学问题。

5 结束语

针对基本FOA的气味浓度判定值不能取负值的不足，提出一种改进的FOA，即DSCFOA。DSCFOA的嗅觉搜索环节利用双策略混合协同进化机制形成优势互补，实现了搜索过程的信息增值，进而在增强算法全局探索能力的同时可在局部进一步深度开发质量更高的候选解；通过佳点集方法初始化种群以及领导层集体引导策略的构建，有效保持了种群的多样性，较好地克服了早熟收敛现象的发生；视觉搜索环节的实时更新方案则进一步加快了算法的收敛速度。利用典型的基准测试函数来验证DSCFOA的可行性与有效性，结果表明：与FOA及其4个改进的算法相比，DSCFOA具有收敛速度快、收敛精度高及寻优结果稳定性好的优点，且DSCFOA对于高维复杂优化问题同样具有较强的全局搜索能力。最后，以冗余机械臂的逆运动学求解为例进行仿真分析，DSCFOA的求解质量同样远优于其他算法，说明该算法具有较强的解决实际工程优化问题的能力。

未来将继续利用DSCFOA来解决其他工程优化问题，以进一步拓展该算法的应用领域。