0 引言

果蝇优化算法(Fruit Fly Optimization Algorithm, FOA)是一种新型的群智能优化算法，算法是根据果蝇的觅食行为进行推演形成的一种寻找全局最优解的新方法^[1-5]。该算法与粒子群优化(Particle Swarm Optimization, PSO)算法、人工鱼群算法(Artificial Fish Swarm Algorithm, AFSA)和遗传算法(Genetic Algorithm, GA)等相比具有计算量较小、参数少、结构简单、易于实现的特点，但同时该算法也存在不够稳定、易陷入局部最优的缺陷^[6]。为了改善原算法的性能，文献[7]提出了自适应步长的改进策略对原算法进行优化，其思路是在原算法的基础上加入果蝇因子，影响该因子的因素是果蝇当前位置与果蝇最佳位置，这样果蝇寻优步长会随着果蝇的位置自适应改变；文献[8]提出了递减步长的改进方法，该算法与果蝇的迭代次数有关，每进行一次迭代，步长都减小一个定值，定值的大小为初始步长与最大迭代次数的比；文献[9]提出了自适应调整参数的果蝇优化算法，该算法用逆向云发生器确定下代果蝇的飞行方向与距离；文献[10]用轮盘赌策略对果蝇的飞行方向进行选择，其思路是根据概率随机选择一个比当前位置好的果蝇作为下次迭代寻优的起始位置。文献[7-9]都是基于步长改进，影响的是果蝇的寻优速度，全局寻优能力没有改变；文献[10]的改进对果蝇历史最好位置依赖性大，如果上代果蝇陷入局部最优，则以后的寻优过程都很难跳出局部最优，因此效果也不是太好。

为了提高果蝇优化算法的收敛速度与全局寻优能力，本文采用非均匀变异的思想对果蝇寻优步长进行改进，以提高算法的收敛速度与精度。同时将模拟退火算法与果蝇算法进行结合，提出了基于模拟退火思想的果蝇优化算法(Simulate Anneal-Fruit fly Optimization Algorithm, SA-FOA)。改进后的算法可以以一定的概率吸收最差的解，并以最差解作为下代果蝇寻优的新起点，从而使算法跳出局部最优值，增强全局寻优的能力。

1 果蝇优化算法 1.1 果蝇优化算法的原理

果蝇在寻找食物时，会沿着食物味道浓度大的方向飞行，而味道浓度的大小和果蝇与食物的距离有关系，果蝇距离食物的位置越近，味道浓度就越大，也越容易找到食物^[1]。果蝇群体迭代寻优路线如图 1所示。

果蝇寻优原理为：随机初始果蝇群体的位置(x, y)，果蝇以该位置为起点随机飞行去寻找食物，当果蝇个体发现食物最佳位置时，其他果蝇也会向该位置聚拢(x₂, y₂)；然后再以这个新位置为起点进行下一次的寻优，直至找到食物的位置。

1.2 果蝇优化算法的步骤

1)随机初始果蝇群体的位置(X_axis, Y_axis)并设置种群规模与迭代次数。

2)以初始位置为起点，随机给定果蝇个体的飞行方向Random和寻优步长Value，以Random*value作为搜索距离。

3)计算味道浓度判定值s_i，该值是果蝇位置坐标与原点距离的倒数。

4)将味道浓度判定值代入味道浓度判定函数，求出果蝇个体的味道浓度。

5)找出果蝇群体中味道浓度最小的果蝇。

6)保留果蝇最小位置坐标，其他果蝇也向该位置飞去。

7)进入迭代寻优，重复执行步骤2)~5)，并判断味道浓度是否优于前一代：若是，则执行步骤6)；若否，则保留前一代的最小味道浓度，算法结束。

1.3 果蝇算法的应用

果蝇优化算法和其他群智能优化算法一样有着广泛的应用领域。果蝇优化算法不仅可以对维数众多、结构复杂的函数进行求解，还可以用于求解实际问题。例如，文献[7]将其与功能流算法相结合，并将改进算法应用在蛋白质交互网络中，通过仿真表明改进算法具有较高的正确率与收敛速度；文献[10]将改进算法应用于置换流水车间模型。通过仿真表明，果蝇算法可以有效地对车间调度问题进行优化；另外，将果蝇优化算法应用于旅行商问题模型，可以快速有效地找出相对合理的路径；将果蝇优化算法应用于神经网络中，可以对神经网络的参数进行优化，从而可以更好地将其应用于人工智能领域。果蝇优化算法作为一种较为新颖的群智能算法，在众多的领域都能够得以运用，因此值得进行更深入的探索研究。

2 模拟退火算法

模拟退火算法^[12-13]是根据炼熔金属中粒子的统计力学与复杂的自合优化问题的求解过程的相似性提出来的。

统计力学研究表明，在温度T，分子停留在状态r的概率满足Boltzmann概率分布：

$ p\left\{ {\overline E = E(r)} \right\} = \frac{1}{{Z(T)}}\exp ( - E(r)/({k_B}T)] $

(1)

$ Z(T) = \sum\limits_{s \in D} {\exp [ - E(s)/({k_B}T)]} $

(2)

其中：E(r)是状态r的能量; Z(T)是概率分布的标准化因子; k_B为大于0的Boltamann常数; T是绝对温度，量纲为1; D是分子状态空间。在同一温度T下，根据金属内部粒子的状态规律，Metropolis等提出以下准则：设在初始状态i, 分子的能量为E_i，然后在该状态下对其进行扰动得到状态j, j状态的能量为E_j。若E_j < E_i，则j状态可作为重要状态；若E_j>E_i，则要根据概率来判断该状态是否被接受。而状态i和状态j的概率比值和Boltzmann因子的比值是相等的，也就是：

$ r = \exp [({E_i} - {E_j})/({k_B}T);r < 1] $

(3)

用随机数ε(ε∈[0, 1])与r进行比较：如果r>ε，则视j为重要状态，并把j状态视为新的状态；若r≤ε，那么j状态不被接受，仍以i状态为当前状态。重复上述的扰动过程，系统最终会趋于能量较低的平衡状态，固体的状态概率分布趋于Boltzmann概率分布。

接收概率由广义Gibbs分布产生的概率P来确定，本文采用其中的一个特例，即:

$ p = \exp ( - \Delta E/T)$ $

(4)

其中ΔE是不同温度下分子状态的能量差。

模拟退火算法是对局部搜索算法的扩展，可以有效地使算法跳出局部最优^[11]。该算法中的扰动因子可以对原有模型进行扰动，从而可以产生新的模型，而新模型的接受与否则需要满足Metropolis准则^[11-13]。

3 基于模拟退火的果蝇优化算法 3.1 步长改进

由果蝇优化算法的原理可知，随着算法迭代次数的增加，果蝇会逐渐接近食物的位置，也就是会逐渐接近最优解。在FOA中步长是随机的，步长设定如下：

$ L = Random * Value $

(5)

其中：Value视为初始步长，为定值；Random是[0, 1]内的随机数，L的范围是[0, Value]，这种步长设定的弊端是，在搜索前期可能会因为选择步长较小而使效率降低，而在搜索的后期又因为步长较大而错过了最优解^[4]。但实际上在算法寻优的初期，我们需要有相对较大的寻优步长，这样可以提高效率，增强全局寻优的能力。在算法迭代寻优的后期，因逐渐接近最优值，则需要使算法具有较强的局部搜索能力，避免因为搜索步长过大而错过了最优解。

为解决上述问题，使算法具有更高的搜索效率与搜索精度，本文参考遗传算法中非均匀变异的思想^[11]对步长进行如下改进：

$ L' = n*{(1 - (g - 1)/maxgen)^\lambda })*{\mathop{\rm sgn}} (0.5 - r) $

(6)

其中：n为初始步长值，可根据最大的迭代次数maxgen进行设定；g为当前迭代次数; λ为非均匀变异因子，经测试知, λ最优值范围是^{[1, 5]}, 本文测试时取2；r∈[0, 1]内的随机数, sgn ()是符号函数。

从改进的步长公式可以看出，步长与当前迭代次数成反比，即随着步长会随着迭代次数的增加自适应地减小。改进后的步长公式可以在一定程度上提高寻优的效率与精度。

3.2 基于模拟退火的果蝇优化算法

本文将模拟退火的思想与果蝇优化算法相结合，改进后的算法步骤为：

1)初始果蝇群体的位置(X_axis，Y_axis)，并设置种群规模sizepop与迭代的次数maxgen；

2)初始化果蝇群体搜索食物的方向与距离：

$ \left\{ \begin{array}{l} {X_i} = {X_ - }axis + L\\ {Y_i} = {Y_ - }axis + L \end{array} \right. $

(7)

3)计算味道浓度判定值(s_i)：

$ {s_i} = 1/{[{({X_i})^2} + {({Y_i})^2}]^{1/2}} $

(8)

4)将味道浓度判定值代入味道浓度判定函数，求出果蝇个体的味道浓度(Smell)：

$ Smell = Function({s_i}) $

(9)

4)求出果蝇群体中味道浓度最小的果蝇(本文中测试函数极小值)，记为S(i)，S(i)为当前模型，并保留该模型位置坐标(X_i, Y_i)。

5)用式(6)再对当前位置(X_i, Y_i)进行一定次数的扰动得到新的模型S(i)′，其位置坐标记为(X_i′, Y_i′)；

$ \left\{ \begin{array}{l} {X_i}^\prime = {X_i} + L'\\ {Y_i}^\prime = {Y_i} + L' \end{array} \right. $

(10)

6)计算新旧模型的味道浓度差值Δs=S(i)′-S(i)：若Δs≤0，则新模型被接受。若Δs>0，则计算概率p=exp (-Δs/g), 若p>r(r是[0, 1]内的随机数)，则新模型被接受，并以(X_i′, Y_i′)为下次寻优的开始; 否则以原模型位置坐标进行下一次寻优。

7)重复步骤2)~6)，直到满足收敛条件。

原算法中果蝇群体都是以群体中最优果蝇的位置作为下一次迭代寻优的开始。这样的弊端是，当前一代果蝇陷入局部最优之后，后代果蝇就很难跳出局部最优。算法经过改进后，有两个优势：首先是步长随着迭代次数的增加呈现非均型性递减的特性，这样在寻优的初期因步长较大可以提高寻优效率，在迭代后期可以进行小步长精确寻优，从而避免原算法可能出现的步长过大错过最优解的可能。另外，算法与模拟退火的思想进行结合，以一定的概率吸收每次迭代出现的最差解，从而增加中间解的多样性，即寻优路径的多样性。这样算法在陷入局部最优解时，可以以最差解为新的起点，重新进行寻优，使得全局寻优的能力大幅提高。通过上述步长与寻优机制的改进，使得本文算法较原算法有更快的收敛速度与收敛精度。

4 实验仿真

为了测试FOA与SA-FOA两种算法的性能，本文从常用于优化算法比较的测试函数中选择4个来进行验证，函数名称、函数形式、搜索区间、理论极小值、函数维数如表 1所示。其中Sphere函数是单峰函数，其他的为多峰函数。另外，Ackley函数是几乎平坦的区域被余弦波调制成一个个的孔或峰，对其寻优非常困难，极易陷入局部最优，因此在对其进行寻优时难度大于另外3个函数。在进行测试时本文拟从两方面进行：第一，在种群规模和迭代次数一定的情况下，比较收敛速度与寻优精度；第二，在固定精度下，比较两种算法的迭代次数与运行时间。

4.1 迭代次数与种群规模固定时性能测试

在测试FOA与SA-FOA两种算法的收敛速度与寻优精度时，设定果蝇群体规模的大小为30，固定迭代次数为100。为使测试结果更具有说服力，本文用FOA与SA-FOA这两种算法对4个测试函数进行20次独立测试，测试结果如表 2和图 2所示。

表 2是对20次独立实验的结果进行统计分析，从最差值、最优值、平均值和方差四个方面来对测试结果进行对比，从而对两种算法的性能有更直观的认识。从表 2中可以看出, SA-FOA对函数f₁(x)、f₂(x)、f₄(x)的寻优精度比FOA高出了1个数量级；而对于结构复杂的f₃(x)，两种算法的寻优精度相同，但是优化效果仍然比FOA的效果好了3~4倍。在20次独立独立实验中SA-FOA对f₁(x)函数的寻优过程中出现一次最差解，使得两种算法的寻优精度的数量级相同，其他的实验结果都比FOA的优化结果高出1个数量。对比两种算法的平均值与方差值，可以看出，SA-FOA的平均值要远远低于FOA，更接近理论极小值；另外，SA-FOA的方差比FOA要低1~2个数量级，因此SA-FOA比FOA具有更好的稳定性。图 2表示的是寻优测试曲线与果蝇的寻优轨迹。从图 2中果蝇寻优迭代次数与最优值的变化曲线中可以看出，在迭代次数为100时，SA-FOA比FOA的收敛速度更快(接近最优解时FOA迭代的次数大约为98、94、90、80；SA-FOA迭代次数大约为48、48、60、24)，并且寻优精度比FOA要高出很多。由图 2(a)、图 2(b)、图 2(c)中可以看出，FOA与SA-FOA对单峰函数f₁(x)、多峰函数f₂(x)和f₄(x)都有较好的寻优效果，但是改进算法SA-FOA的效果更好；而对于结构相对复杂的多峰函数f₃(x)，两种算法在20次实验中都没有达到与另外三个函数相同的寻优效果，但是FOA的寻优精度仍然低于SA-FOA。

从果蝇飞行路线图中可以看出，迭代次数为100时，FOA搜索的距离与SA-FOA相差很大，另外可以看出FOA的迭代步长很小，这样就降低了搜寻范围，极易使算法陷入局部最优。而SA-FOA搜索步长随着迭代次数的增加大致是呈减小趋势，在迭代后期步长才表现出与FOA相似的规律。另外，从SA-FOA的果蝇飞行路线图中可以看出，在寻优过程中，有若干代果蝇的位置比较密集，即局部最优点。但随着迭代次数的增加，算法总能够跳出这些点。因此SA-FOA具有较高的效率，寻优结果也比较接近理论值。

4.2 目标精度下的性能测试

为测试在固定精度下两种算法的寻优能力，在测试时分别进行10次独立的实验，种群规模设为30，最后得到的迭代次数和耗时是10次测试的平均值，为方便比较，迭代次数的平均值进行了取整。因为f₃(x)函数要达到与另外3个函数相同的精度所需的迭代次数太大，因此将其目标精度设为10^-4，其他3个函数目标精度则都为10^-6。从表 3中可以看出，在目标精度相同的情况下，FOA的迭代次数是SA-FOA的3~5倍。两种算法对f₃(x)的寻优能力都要低于另外3个函数，而达到相同的目标精度条件时，对f₄(x)进行寻优的迭代次数要远远高于函数f₁(x)和f₂(x)。从达到目标精度所消耗的时间来比较，可以看出SA-FOA的耗时更少，效率更高，SA-FOA比FOA的时间效率分别高出21.952%、9.906%、67.623%、68.051%。

$ \eta = \left( {{t_1} - {t_2}} \right)/{t_1} $

(11)

其中：η表示时间效率，t₁表示FOA所用的平均时间，t₂表示SA-FOA所用的平均时间。由表 1可知，本文的改进算法收敛速度更快。

4.3 与参考文献中的算法性能对比

为测试本文算法与其他算法的性能优劣，本文将SA-FOA与其他几种算法的优化均值进行了对比。文献[9]中的自适应调整参数的果蝇优化算法(Fruit fly Optimization Algorithm with Adaptive Parameter，FOAAP)和文献[14]自适应混沌果蝇优化算法(Adaptive Chaos Fruit fly Optimization Algorithm，ACFOA)迭代次数均为2 000，种群规模为30，维数为30。其中ACFOA独立运行了20次，SPOS算法则独立运行50次，迭代次数3 000，本文实验约束条件和ACFOA相同。另外，本文引用文献[15]和文献[16]的几组数据进行比较，性能对比如表 4所示。

首先将本文算法SA-FOA与文献[9]中的算法FOAAP进行比较，可以看出本文算法对4个函数的寻优能力都远高于FOAAP，其中对于寻优最困难的函数f₃(x)，本文算法要高出FOAAP四个数量级。其原因是FOAAP的自适应参数调整其实只是对步长参数的调整，改变的是收敛速度，而对全局寻优能力没有较大的影响，因此本文算法的效果较好。通过对比本文算法与文献[15]的算法可知，本文算法除了对f₁(x)函数的寻优能力远低于SPOS算法之外，对其他函数的寻优能力都高于SPOS算法。其原因大致是SPOS算法中，下代粒子对群体历史最好位置和当前最好位置的依赖性比较大，也就是说该算法的局部搜索能力很强，因此对于单峰函数f₁(x)来说，SPOS算法具有较强的优势，而对于多峰来说，其寻优能力就比较弱。而文献[16]中的AFSA对四个函数的寻优结果都远低于本文算法，其原因也是因为全局搜索能力较弱。另外，通过对比本文算法与文献[14]的算法ACFOA可以看出，本文算法除了对f₃(x)的寻优能力远高于ACFOA之外，其他3个函数都低于ACFOA。这是因为f₃(x)函数是4个函数中结构最为复杂的，很难对其进行全局寻优，但是对比表中的所有算法可以看出，本文算法对于复杂函数的寻优能力是最强的。通过上述结果的分析可知，本文算法具有较高的寻优精度与全局搜索能力。

5 结语

果蝇优化算法属于演化式计算的范畴，也属于人工智能的领域，是群体智能的一种新方法。在军事、医学、科研、管理与财务等领域都可运用。另外，该算法还可以混合其他数据采集技术一起使用，如判定树、模糊数学、灰色系统与神经网络等。本文针对果蝇算法寻优精度不高、收敛速度较慢且易陷入局部最优的特点，提出了基于模拟退火思想的果蝇优化算法。算法以一定的概率接受恶化解，从而增加解的多样性，增强了全局寻优的能力；对寻优步长的改进，使算法具有较快的收敛速度与寻优精度。通过与原算法和参考文献中的算法对比表明，本文算法有效、可行。