一种新型的果蝇优化算法

张晓茹，张著洪

(1.贵州大学 理学院，贵州 贵阳 550025；2.贵州大学 大数据与信息工程学院，贵州 贵阳 550025)



一种新型的果蝇优化算法

张晓茹1，张著洪2*

(1.贵州大学 理学院，贵州 贵阳 550025；2.贵州大学 大数据与信息工程学院，贵州 贵阳 550025)

针对维数较高的单目标非约束函数优化问题, 探讨一种易于应用的新型果蝇优化算法。算法设计中，优质种群经由局部变异增强探测能力；中等种群经由优质种群有引导性地实现个体转移；劣质种群经由均匀变异展开多方位搜寻多样个体。比较性的数值实验显示, 该算法求解偏高维函数优化问题具有一定的优势。

果蝇优化; 函数优化; 多模态

基本果蝇优化算法(Basic Fly Optimization Algorithm, BFOA)[1]因其结构简单、可操作性强等优点，已受到智能优化学者的足够重视。该算法主要涉及果蝇嗅觉感知食物远近和视觉感知食物所在方位等生物机理，被用于解决决策区域为对称区域的连续函数优化问题[2]。但此算法极大依赖于果蝇与食物源之间的距离且算法中个体间信息交互能力弱等，使得其易于陷入局部搜索。如何通过个体多样化的更新策略，增强算法跳出局部搜索的能力，以及深入研究算法的理论基础、群体多样性、算法应用，均有待开展。

本文借鉴果蝇嗅觉对事物的感知行为和视觉的方向选择特征，以小种群为进化载体，依据果蝇协同觅食的生物特征设计进化框架，力求提出新型果蝇优化算法 (Fly Optimization Algorithm, FOA)，解决维数偏高的函数优化问题。比较性的数值实验结果显示，该算法获得的解质量具有明显优势，对偏高维函数优化有一定的应用潜力。

1　问题描述与果蝇基本理论

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

其中，D是Rp中有界闭区域，x∈D为候选解，x=(x1,x2,…,xp)，f(x)为D上有界、非线性连续函数。由于D为有界闭区域，所以问题(P)必存在最优解。

果蝇是一种微小的生物体，能通过嗅觉和味觉感知附近食物源的大体方位和远近，通过复眼捕捉周围环境信息。就果蝇的嗅觉而言，嗅觉器官依据食物源的远近，能嗅到40 km以外的食物源[3]；另一方面，果蝇的复眼是一种极为重要的光感受器，其两只复眼是由数千只小眼组成的两个半球，对称地分布在头部的两侧，每只复眼都像一个探测器，可探测视角区内的目标。

2　算法原理与算法设计

FOA由群体分割和种群进化两个模块构成。群体分割依据个体适应度将进化群体划分为优质、中等、劣质子群；各子群依据特定变异方式和历史信息更新自身位置，并产生新群体。在此，将果蝇视为个体，并与以上问题(P)的候选解对应，食物源被视为该问题本身。FOA的描述与设计如下：

步1输入参数：群体规模N, 迭代数Gmax，选择率α、β、pm；

步2置n←1,随机产生N个个体构成初始群体An，依据个体适应度，将An中最好个体作为当前最好个体xbest；

步3An中α%个较好个体构成优质子群A、β%个较差个体构成劣质子群C，其余个体构成中等子群B；

步4优质子群A更新：对于A中每一个体x，对xbest进行单点随机变异，例如对第j个基因变异：

(1)

步5中等子群B更新：对于B中每个个体x，随机抽取A中一个个体y，并与xbest一起对x实施更新：

x′←y+λ(xbest-x)

(2)

获群体B*，在此λ是0～1之间的随机数；

步6 种群C中个体依据概率pm执行如下变异：

x′←(1-Δ)ηx+Δη(b-a)

(3)

步7利用A*∪ B*∪ C*中最好个体更新xbest；

步8An+1←A*∪B*∪ C*; 若n

该算法借助果蝇嗅觉特征，将当前最好个体视为可能的食物源，群体进化中的个体在此个体位置和方向的引导下，逐渐向食物源所在方向转移。优质子群A中的个体被认为距离食物源较近，仅作局部变异；中等子群B在A中个体的引导下，逐渐向该子群转移；然而，劣质子群C则通过均匀变异增加发现食物源的机会和增强群体多样性的能力，防止算法陷入局部搜索。

3　数值实验

在Window XP/CPU 2.50GHz /RAM 3.0GB /VC++环境下展开数值实验。选择3种近年被报道的新果蝇优化算法FFO[1,3]、IFFO[2]和MFOA[4]参与FOA的比较分析。各算法求解以下各测试问题的种群规模均为10，最大迭代数为300，且均独立求解每种测试问题100次。参与比较的算法的参数设置与相应文献的相同；FOA中三个可调参数设置为α=0.2,β=0.2,pm=0.4。

文献[2]中的测试问题F1至F4被用于检测以上4种算法的性能：

函数F1

最优解x*=(-2,…,-2), 最小值2(n+2)(n-1)。

函数F2

最优解x*=0, 最小值-1。

函数F3

-600≤xi≤600,

最优解x*=0, 最小值0。

函数F4

最优解x*=0, 最小值1-n。

F1和F2是单模态函数优化问题；虽然均各自仅有1个最优解，但在维数较大的情形下，目标函数在决策区域的大部分区域上的函数值较大，算法收敛速度受到极大影响；F3和F4是极为困难的多峰值函数优化问题，其决策变量的耦合性强，多个局部最优解严重干扰算法的全局搜索，加之，当维数较高时，目标函数在多个子决策区域的函数值较大，特别是F3的决策区域较大，使得算法求解变得极为困难。

3.130维测试问题的实验结果分析

在F1至F4的维数均为30下，以上4种算法分别独立求解每个测试问题100次后，统计结果如表1所示；以F1、F4为例，各算法求解每个测试问题获得的100个目标值形成的箱线图如图1所示，图中AE表示各算法获得的目标值与理论最小值的绝对误差。

表1　30维测试问题的统计结果比较

注：μ为独立运行100次后获得的100个目标值的均值，σ为独立运行100次后获得的100个目标值的均方值

图1　求解30维测试问题获得的箱线图比较

由表1的均值可知，从获得的解质量看，FOA优于其它算法；MFOA求解F1-F3 获得的解质量优于FFO和IFFO获得的解质量；FFO最差。从搜索效果的稳定性看，基于表中的均方差，FOA的搜索效果最稳定，MFOA次之，IFFO却表现出极不稳定的搜索行为。另一方面，经由图1获知，求解F1、F4的最小值时，FOA获得的中位线均较其它算法获得的中位线低，也即所获得的目标值距离理论最优值较近，搜索效果最好；再从箱线图的中位线距离下四分位线的远近得知，FOA的搜索效果较稳定，FFO次之。

3.2100维测试问题的实验结果分析

类似于以上实验，4种算法的统计结果如表2所示，获得的箱线图如图2所示。

表2　100维测试问题的统计结果比较

图2　求解100维测试问题获得的箱线图比较

与表1中的结果相比，表2表明，随着维数的增加，各算法的搜索效果均有不同程度的退化(除FOA求解函数F1之外)，尤其是求解F2、F3，参与比较的算法的退化现象较为严重，但FOA整体效果较为稳定，受维数增加的影响较小；从获得的均方值看，各算法的稳定性也有所下降，尤其体现在F1和F3上。FOA除F4外，获得其它函数的均方值均较小，尤其求解F1获得的均方值与其它算法获得的均方值有较为明显的差异；经由图2不难发现，由于FFO、IFFO及MFOA的个体更新方式单一、群体中个体整体向当前最优个体靠近，致使最终获得的目标值与理论极值的偏差较大(如F1)。

综上，从以上4种算法对以上4个问题在不同维数下进行求解获得的结果可以看出，FOA的寻优效果和算法稳定性均有一定的优势，但算法的进化能力有待进一步增强。

4　结论

基于果蝇嗅觉和视觉觅食的行为特征，获得可调参数少且具有协同进化特点的新型果蝇优化算法。该算法利用优质子群进行局部搜索，增强局部搜索能力；利用当前最好个体和优质子群引导中等子群向最优解所在区域转移；劣质子群通过特定的变异方式，增强群体多样性和提供发现最优解的机会。比较性的数值实验表明，此算法是一种具有竞争力的果蝇优化算法。虽然该算法结构简单，处理偏高维优化问题已呈现了一定的优势，但算法中个体自身进化的历史信息未被利用，个体间的竞争、合作协同进化尚未充分体现，有待进一步改进该算法的进化能力。

[1] W T Pan. A new fruit fly optimization algorithm: Taking the financial distress model as an example [J]. Knowledge-Based Systems, 2012, 26: 69-74.

[2] Q K Pan, H Y Sang, J H Duan, et al. An improved fruit fly optimization algorithm for continuous function optimization problems [J]. Knowledge-Based Systems, 2014, 62: 69-83.

[3] 潘文超. 果蝇最佳化演算法—最新演化式计算技术 [M]. 台北: 沧海书局, 2011: 1-12.

[4] X Yuan, X Dai, J Zhao, et al. On a novel multi-swarm fruit fly optimization algorithm and its application [J]. Applied Mathematics & Computation, 2014, 233(3): 260-271.

(责任编辑：曾晶)

A New Fly Optimization Algorithm

ZHANG Xiaoru1, ZHANG Zhuhong2*

(1.College of Science, Guizhou University, Guiyang 550025, China; 2.College of Big Data & Information Engineering, Guizhou University, Guiyang 550025, China)

For the problem of single-objective non-constrained higher-dimensional function optimization, this work investigates a new applicable fly optimization algorithm. In the design of algorithm, a local mutation strategy ensures the elitist sub-population to achieve strong exploitation; the medium sub-population transforms its individuals towards specific directions upon such elitist sub-population; the inferior sub-population creates diverse individuals along multiple directions. Comparatively numerical results have showed that the proposed algorithm is of potential for higher-dimensional function optimization problems.

fly optimization; function optimization; multi-modality

1000-5269(2016)02-0093-04

10.15958/j.cnki.gdxbzrb.2016.02.21

2015-10-08

国家自然科学基金(61563009)；教育部博士点基金 (20125201110003); 贵州大学研究生创新基金 (研理工2015057)

张晓茹(1987-), 女, 在读硕士, 研究方向: 智能优化算法，Email: xiaoruzh@163. com.

张著洪，Email：sci. zhzhang@gzu. edu. cn.

TP301.6

A