以生物智能为依托的智能优化在漫长历程中已得到快速发展^{[1, 2, 3, 4]}，大量源于生物灵感的新型优化算法不断涌现，以至于探讨收敛速度快的微种群优化算法已成为智能优化的发展趋势. 特别，依据果蝇觅食行为机制产生的基本果蝇优化算法(basic fly optimization algorithm，BFOA)^[5]，因其结构简单、 可操作性强等优点^[7]，已受到较多学者的足够重视. 该算法的设计初衷是以果蝇嗅觉感知食物远近和以视觉感知食物所在方向为生物理论基础，以解决连续函数优化问题为目的. 继后，围绕算法的收敛性和单、 多果蝇的位置更新策略，国内外对其展开了一系列研究^[7-19]，且部分成果在控制设计、 预测、 故障诊断、 支持向量机等方面已得到应用^[20-22]. 研究工作集中在探讨改进型、 新型、 混合型果蝇优化算法和算法的应用.

鉴于BFOA要求个体评价量大，个体更新规则对果蝇与食物源位置之间的距离依赖程度高、 个体间信息交互能力弱等缺陷，目前主要集中在探讨BFOA的改进型算法^[7-15]； 例如，针对局部搜索、 收敛精度等^{[7-8, 10, 14]}，通过引入细菌迁徙操作、 混沌变异、 混合蛙跳更新策略等，提高种群多样性，增强局部搜索能力； 针对种群的初始位置以及固定搜索步长对寻优效率和收敛速度的影响^{[9, 11, 12, 15]}，通过融入Logisitic映射、 种群划分以及动态递减步长的更新策略，加快算法的寻优效率和收敛速度； 针对果蝇浓度值始终为非负的问题，文^[13]将决策区间转化为对称区间，克服了目标函数的变量值被要求为非负的限制. 近年来，新型果蝇优化算法的研究也已取得一定进展，主要集中在利用果蝇协同觅食行为探讨协同进化果蝇优化算法^[16-17]. 主要目的在于通过引入协同进化的更新策略，增强算法跳出局部搜索的能力. 例如，文^[16]通过动态划分子群，引入混沌映射，不同子群执行不同进化策略，有效弥补了寻优精度低、 易陷入局部搜索的不足，但因群体规模较大，搜索效率受到影响； 文^[17]结合进化过程中产生的最好与最差个体，对进化个体进行更新，一定程度上缓解了早熟现象.

综上，果蝇优化算法的研究仍处于初步阶段，新型果蝇优化算法、 算法收敛速度和理论分析以及算法处理高维优化问题的优势与缺陷等研究均有待陆续展开. 基于此，本文借鉴果蝇的嗅觉对事物的感知行为和视觉神经的方向选择特征，以小种群进化为载体，依据果蝇协同觅食的生物特征设计进化框架，力求探讨具有种群规模小、 参数少、 收敛速度快的小种群果蝇优化算法，简称微果蝇优化算法(micro fly optimization algorithm，μFOA). 比较性的数值实验结果显示，该算法在解的搜索质量方面具有明显优势，对高维函数优化问题的求解具有一定的应用潜力.

考虑如下静态优化问题(P)

果蝇通过嗅觉和视觉^[23]感知附近食物源的大体方位和远近，利用复眼捕捉周围环境信息. 就嗅觉而言，果蝇的嗅觉器官能很好地搜集到漂浮在空气中的气味分子. 研究表明，果蝇的嗅神经元能被用于检测和识别已感知到的化学气味分子，这些气味信息在嗅神经元内转换成神经电信号，并经嗅神经元的轴突传递到触角叶，再经投射神经元将信息送至高级中枢，最终引发行为反应. 另一方面，果蝇的复眼是一种极为重要的光感受器，其由一个个独立的小眼构成，是快速获取信息的中心^[24]. 总之，视觉和嗅觉是决定果蝇能否准确定位和快速发现食物源的重要生理器官. 果蝇通过接收的视觉信号并多次评估，决定何时延伸足部开始着陆. 之后，利用背景中的视觉信号定位食物源的大致方位； 利用嗅觉信号判断食物源的远近. 凭借视觉和嗅觉信号，不断调整觅食的行为，逐渐靠近食物源的位置.

μFOA主要由群体划分和子群进化两个模块构成，如图 1所示. 群体划分主要依据群体中个体的适应度，将进化群体划分为优质子群(种群A)、 中等子群(种群B)和劣质子群(种群C). 种群进化中产生的最好个体被视为可能的食物源，各种群依据特定的变异方式和历史信息更新自身位置，并产生新一代群体. 为便于算法描述，将果蝇(个体)与以上问题(P)的候选解对应，食物源视为该问题本身. 结合图 1和以上果蝇生物行为特性，μFOA的具体描述如下：

图 1 μFOA的流程图 Fig. 1 Flowchart of μFOA

图选项

Step 1 输入参数： 群体规模N，迭代数G_max，选择率α，β.

Step 2 置t←1，随机产生N个个体构成初始群体P(t)，依据个体适应度，将P(t)中最好、 最差个体分别作为当前最好个体x_best和最差个体x_worst.

Step 3 依据个体适应度升幂排列P(t)中所有个体，个体排序后，前面的αN个个体构成优质种群A、 后面的βN个个体构成劣质种群C，其余的构成中等种群B.

Step 4 种群A、 B、 C分别执行如下更新步骤：

Step 4.1 种群A中个体x按如下方式更新

Step 4.2 种群B执行如下变异策略：

Step 4.3 种群C执行如下变异：

Step 4.4 组合种群A^*、 B^*和C^*为p(t+1).

Step 4.5 经由Step 4.1至Step 4.3中最好和最差个体，对x_best和x_worst分别实施更新.

Step 5 若t<G_max，则t←t+1，转Step 3； 否则，输出x_best.

在以上算法设计中，种群A中个体利用单点多项式变异执行局部搜索，此模拟果蝇着陆后，借助视觉信号捕捉食物源的大致方位，使个体逐渐向食物源(最优解)所在方向转移； B种群利用非均匀变异使个体向最好个体附近转移，产生优质和多样的个体，此模拟果蝇嗅觉对食物源的感知行为，借以增强群体多样性； 受果蝇视觉和嗅觉综合行为特征的启发，种群C利用类似于均匀变异的变异方式，使种群个体在最优个体best与最差个体worst间发生变异，扩大个体的搜索范围，并不断向最优个体的位置靠近. 在设计上，与BFOA相比，回避了利用食物源的味道浓度及果蝇与食物源的距离确定决策变量值的限制. 此算法的结构较为简单，可调参数仅有α，β，各子群体的更新方式不同，群体的进化具有较好的自适应性.

定理1 μFOA的计算复杂度为O(N(ln N+p)).

证明 μFOA的计算复杂度由Step 3、 Step 4决定. 在迭代周期内，Step 3需对个体排序，其计算复杂度为O(Nln N)； Step 4.1中，种群A的每个个体均需执行1次变异和计算适应度，因此需运行2αN次； 在Step 4.2中，每个个体均需执行变异和计算适应度，计算次数为(p+1)(1-α-β)N. Step 4.3的运行次数为(p+1)βN. 因此，在一个运行周期内，μFOA的计算复杂度为

以上表明，μFOA的计算复杂度由问题维数和群体规模确定，加之群体规模设置为较小值，因此该算法的运行速度能得到保证.

在Window XP/CPU 2.50 GHz/RAM 3.0 GB/VC++环境下展开数值实验. 选择具有竞争力的2种新的果蝇优化算法FFO(fruit fly optimization)^[5-6]和IFFO(improved fruit fly optimization)^[18]参与比较分析. 测试问题包括13个单模态优化问题(F1~F13)^[18]和7个多模态函数优化问题(F14~F20)^[18]，见附录. 每种测试问题的维数取30、 50、 100或200. 各算法求解每种测试问题100次，其种群规模均为6，单次运行的总评价数为1 200. FFO和IFFO的参数最佳设置与相应文献的相同. μFOA仅包含两个可调参数，算法调试后，对于各测试问题均设置α=β=0.2. 为充分检测μFOA的行为特性，算法比较分析包括： 研究以上算法求解偏低维(30或50)、 偏高维(100或200)测试问题时的性能差异，依据算法运行时间比较搜索效率差异，以及借助假设检验，分析这些算法在搜索效果方面的显著差异性.

在维数设定为30、 50前提下，以上算法分别独立求解每个测试问题100次后，获得的统计结果如表 1、2所示. 以F5、 F15为例，各算法获得的目标值的平均搜索曲线如图 2、 3所示. 图中，f_n表示100次运行下第n代群体的最小目标值的均值.

图 2 30维的F5、 F15的平均搜索曲线比较 Fig. 2 Comparison of average search curves for F5 and F15 with 30 dimensions

图选项

图 3 50维的F5、 F15的平均搜索曲线比较 Fig. 3 Comparison of average search curves for F5 and F15 with 50 dimensions

图选项

由表 1中平均值可知，当处理以上30维优化问题时，μFOA除了求解F19的优势不十分突出外，求解其它测试问题均有明显的优势，此说明该算法的局部和全局搜索能力强. FFO求解F8、 F15获得的效果与IFFO的差异较小，且求解F2、 F13获得的效果比IFFO的效果要好，但求解其它问题获得的均值都较大，说明此算法易陷入局部搜索. 导致此现象的主要原因在于该算法的个体更新方式单一，制约了算法的搜索效果，因此该算法的进化能力和群体多样性均有待改善； IFFO求解以上20个30维测试问题，获得的效果均差于μFOA的效果，求解9个测试问题(例如F3、 F5、 F9)获得的效果比FFO获得的效果要好(见图 2). 另外，从表 1中均方差获知，FFO和IFFO的搜索效果极不稳定，且较容易陷入局部搜索，特别是求解多模态函数优化问题(F14~F20)，获得的效果极不理想. 然而，μFOA除了求解F17、 F18获得的均方差偏大外，求解其它问题获得的效果均相对较为稳定. 图 2反映了FFO和IFFO易陷入局部搜索.

通过对比表 1、 表 2说明随着维数的增加，FFO和IFFO的寻优能力逐渐退化，主要原因在于它们的算法结构导致它们易陷入局部搜索和全局开采能力弱(见图 3). 可是，μFOA借助自适应更新方式，几乎都能获得理想的目标值，极大减少了陷入局部搜索的可能性，其获得的解的质量受到维数的影响较小； 图 2、 3表明该算法仅出现寻优速度变慢的现象(除F4及F12外). 对于以上全局最优解的位置在坐标原点的优化问题，FFO和IFFO均较难获得近似解，说明此两种算法在搜索后期的局部勘测能力弱，获得的最好解与理论最优解相距较远. 另外，对于全局最优解的位置不在坐标原点且目标值为0的优化问题(如F6、 F20)，FFO和IFFO在算法运行初期就已陷入局部搜索，因此这两种算法的进化方式有待改善. 另外，以上均方差表明，FFO和IFFO易于陷入局部搜索且搜索效果不稳定； 除F4、 F12和F20外，μFOA均能稳定地获得较为理想的结果，此进一步说明该算法求解50维以下的单、 多模态函数优化问题能获得满意效果.

取定维数为100、 200，以上3种算法各自求解F1~F20之后，获得的统计结果如表 3、 4所示. 以F14~F19为例，各算法的平均搜索曲线如图 4、 5所示.

图 4 100维的F14~F19的平均搜索曲线比较 Fig. 4 Comparison of average search curves for problems F14 to F19 with 100 dimensions

图选项

图 5 200维的F14~F19的平均搜索曲线比较 Fig. 5 Comparison of average search curves for problems F14 to F19 with 200 dimensions

图选项

经由表 3获知，FFO和IFFO求解绝大部分测试问题，获得的均值与理论上的最小值相差较大，仅有求解F8、 F15、 F19能获得相对较小的平均目标值. 它们求解测试问题获得的效果几乎都差于μFOA获得的效果，此说明FFO和IFFO求解100维的单、 多峰值优化问题的能力较弱，而μFOA的寻优能力受到维数影响尚小(除F4和F12外). 另外，表 3中的均方差和图 4表明，μFOA的寻优效果整体上较稳定，获得的解质量较高，收敛速度快，而另外两种算法的寻优效果较差，主要源于FFO更新方式单一，进化群体中的个体以相同方式向当前最优个体位置靠近； IFFO的进化群体中的个体都在最优个体附近执行单点变异，降低了种群的多样性，致使算法易陷入局部搜索.

表 4说明，随着维数增大，FFO和IFFO几乎不能有效求解以上测试问题，仅有求解F8、 F15、 F19时，获得的平均目标值偏小，此进一步反映了它们的整体搜索能力弱和多样性差； 当然，μFOA不能有效求解的问题个数也在增加(F14~F19). 由此看出，求解高维多峰值优化的全局最优解具有极大的挑战性. 经由图 5，μFOA获得的解质量较高、 收敛速度快，而FFO和IFFO极易陷入局部搜索，寻优能力有待增强，此与以上实验获得的结论一致.

综上，当处理偏高或高维单、 多峰值优化问题时，无论是解质量还是搜索效果的稳定性方面，μFOA均表现出明显的优越性，且在维数低于100情形下，其寻优能力几乎不因维数的增大而受到影响； 可是，由于IFFO和FFO的全局搜索能力和群体多样性有待增强，其寻优质量受到维数的影响较大. 总体上，针对以上20个测试问题，在维数为30、 50、 100、 200情形下，μFOA的寻优能力最强，IFFO总体上比FFO获得的效果要好一些.

为便于比较分析算法的执行效率，在给定维数下，将以上每种算法独立求解F1~F20中每个测试问题100次所需平均运行时间陈列于表 5.

由表 5知，各算法所消耗的平均运行时间随维数加大而增加. FFO和IFFO的执行效率基本相同. μFOA在模块设计上，需依个体适应度进行个体排序，因此，在一定程度上增加了计算量. μFOA比FFO和IFFO的平均运行时间稍长，但基本持平，且此3种算法的运行效率处于同一个数量级.

给定维数下，将以上每种算法求解F1~F20中每个测试问题获得的平均目标值作为样本，借助这些样本和多比较方法(Friedman与Friedman秩检验^[25])，分析算法获得的解质量是否存在显著性差异. 取显著性水平α=5％，通过查表获知，Χ²_1-α/2=5.99. 检验结果如表 6所示.

经由表 6获知，在给定维数下，μFOA获得的F值和FA值均分别小于另外两种算法获得的对应的值，再加上表中统计值(Statistic)均大于5.99，表明μFOA的解质量与其它两种算法的解质量具有显著性差异. 另外，FFO和IFFO的F值、 FA值均没有明显区别，因此，它们的解质量没有明显差异. 总体上，μFOA较参与比较的FFO和IFFO在所获解的质量方面存在显著性差异； 再结合以上实验结果获知，μFOA在求解质量方面具有明显优势.

基于果蝇的嗅觉和视觉觅食的行为特征，获得种群规模小、 可调参数少的微果蝇优化算法. 该算法利用优质子群进行局部搜索，增强局部搜索能力. 同时，此子群引导中等子群实施更新； 劣质子群中的个体在当前最好和最差个体之间进行大范围转移，增强群体的多样性. 理论分析表明，该算法的计算复杂度由群体规模和问题的维数确定. 比较性的数值实验表明，此算法在求解质量、 搜索效果的稳定性方面均具明显优势，是一种具有竞争力的小种群果蝇优化算法.

附录 最小化测试问题

类型	函数	决策区域	最优解x*	最小值
f1		xi∈[-10， -2]	(-2， -2， …， -2)	2(n+2)(n-1)
f2		xi∈ [-10， 10]	0	0
f3		xi∈ [-1， 1]	0	-1
f4		xi∈ [-100， 100]	0	0
f5		xi∈ [-1.28， 1.28]	0	0
f6		xi∈ [-30， 30]	(1， 1， …， 1)	0
f7		xi∈ [-100， 100]	0	0
f8		xi∈ [-100， 100]	0	0
f9		xi∈ [-10， 10]	0	0
f10		xi∈ [-100， -1]	(-1， -1， …， -1)	n
f11		xi∈ [-100， 100]	0	0
f12		xi∈ [1， 10]	(1， 1， …， 1)	n
f13		xi∈ [1， 30]	(1， 1， …， 1)	n(n+1)/2
f14		xi∈ [-10， 10]	0	0
f15		xi∈ [-32， 32]	0	0
f16		xi∈ [-600， 600]	0	0
f17		xi∈ [-n， n2]	x*i=i(n+1-i)
f18		xi∈ [-5.12， 5.12]	0	0
f19		xi∈ [-5， 5]	0	1-n
f20		xi∈ [-100， 100]	(1， 1， …， 1)	0

表选项