局部深度搜索的混合果蝇优化算法

摘 要：针对基本果蝇优化算法（FOA）局部深度搜索能力较差且易陷入局部最优的缺点，提出了局部深度搜索的混合果蝇优化算法（SFOALDS）。通过借鉴混合蛙跳算法（SFLA）的更新策略，循环进行局部深度搜索操作，使得SFOALDS既保持了FOA较快的收敛速度，又增强了FOA局部深度搜索能力，有效避免了基本FOA易陷入局部最优的缺点，提高了进化后期算法的收敛速度和精度。仿真实验结果表明，SFOALDS比基本FOA和SFLA有较强的全局寻优性能，并且在高维函数上的优势更加明显。

关键词：果蝇优化算法；混合蛙跳算法；群体智能；局部搜索；早熟收敛

0 引言

果蝇优化算法（Fruit fly Optimization Algorithm，FOA）由潘文超于2011年6月提出，是一类新的全局优化群智能算法，源于对果蝇觅食行为的模拟[1-3]，可广泛应用于科学和工程领域，也可混合其他的数据挖掘技术一起使用。目前，其已经成功应用于如求解数学函数极值[2]；微调ZSCORE模型系数，提高企业财务危机预警的准确率[2]；优化广义回归神经网络进行企业经营绩效评估[3]和四川省新政航电工程3台机组5个不同部位的振动序列峰峰值预测[4]；优化最小二乘支持向量机（Least Squares Support Vector Machines，LSSVM）用于建立回转干燥窑干燥速率模型[5]；辨识船舶操纵运动响应模型的结构参数，并用得到的响应模型进行自航模变Z形试验预报[6]；分离盲源语音信号[7]等。

FOA与其他群智能算法相比，不但算法简单，容易理解（如粒子群算法（Particle Swarm Optimization， PSO）的优化方程是二阶微分方程[8]，而FOA的优化方程是一阶微分方程），程序代码易于实现，运行时间较少，对搜索空间有一定的自适应能力，具有较强的鲁棒性和较好的收敛性能；而且FOA所需调整的参数比较少，仅有3个，而其他经典智能优化算法所需调整的参数至少为5个（如PSO需调整5个参数[8]、人工鱼群算法（Artificial Fish Swarm Algorithm， AFSA）需调整5个参数[9]、蚁群算法（Ant Colony Optimization，ACO）需调整7个参数[10]、遗传算法（Genetic Algorithm，GA）需调整5个参数[11]、细菌觅食优化算法需调整11个参数[11]等），各个参数对算法性能的影响、参数之间的相互影响和复杂关系及对算法性能的二次影响很难研究清楚，一般都是通过大量实验总结出来的经验数值，但参数的取值不当，会严重影响算法的性能，并且导致分析算法复杂度变得异常困难。

但同时FOA与其他全局优化算法（如GA、PSO）类似，易陷入局部最优，导致后期收敛速度变慢，收敛精度降低，尤其是对于高维多极值复杂优化问题。根据没有免费的午餐理论[12]，每种进化算法都有各自的优缺点，因此，如何将FOA与其他智能优化算法融合是一个重要的研究方向。

混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）[13]是一种基于群体的亚启发式协同搜索算法，该算法在群中个体所在的模因组内进行局部深度搜索，然后利用模因组混合实现全局信息交换[14]。本文针对FOA局部深度搜索能力较差，迭代后期易陷入局部最优的缺点，借鉴SFLA模因组内的局部深度搜索策略，提出一种果蝇优化算法和混合蛙跳算法相融合的新算法――局部深度搜索的混合果蝇优化算法（Shuffled Fruit Fly Optimization Algorithm with Local Deep Search，SFOALDS）。该算法既保持了FOA原有的较强的全局搜索能力和较快的收敛速度，又增强了FOA的局部深度搜索能力，从而有效平衡了整个种群的“探索”和“开发”能力，提高了算法的收敛速度和精度。用FOA、SFLA和SFOALDS对5个高维基准测试函数进行仿真实验的结果表明，本文算法收敛速度和寻优精度均优于FOA和SFLA。

7）进入迭代寻优，重复执行步骤2）～5），并判断最佳味道浓度是否优于前一迭代最佳味道浓度，并且若当前迭代次数小于最大迭代数Maxgen，则执行步骤6）；否则，结束算法。

3 局部深度搜索的混合果蝇优化算法

FOA具有较强的全局搜索能力和较快的收敛速度，但迭代寻优时，向最优个体的聚集行为，极易导致种群多样性的损失，若该个体并不是全局最优，极易使算法陷入局部最优，带来早熟收敛的问题。

SFLA迭代寻优时，利用模因组内的局部深度搜索策略和模因组混合策略的循环交替，实现全局寻优的目的，因而具有较强的局部深度搜索能力，并且为与其他算法的融合提供了方便。

基于上述分析，本文提出了局部深度搜索的混合果蝇优化算法SFOALDS，该算法将FOA和SFLA进行融合，充分发挥FOA和SFLA各自的优势，既保持FOA原有的较强的全局搜索能力和较快的收敛速度，又恰当引入SFLA模因组内的局部深度搜索策略，从而平衡整个种群的“探索”和“开发”能力，有效避免了基本FOA易陷入局部最优的缺点。

SFOALDS以FOA的运算流程为主体流程， SFOALDS流程如图1所示。

4 仿真实验及结果分析

4.1 实验设计

以求5个基准测试函数最小值为例，进行仿真实验，来验证并比较本文提出的SFOALDS的性能。函数名称、函数形式、搜索区间、函数最小值和峰值见表1，所有函数均为高维函数。测试软件平台为Windows XP，Matlab 7.1，机器主频为3.3GHz， 内存为2GB。

设计了三个算法的优化实验来验证并比较本文算法的性能：1）FOA优化实验；2）SFLA优化实验；3）SFOALDS优化实验。具体实验参数设置为：群体规模Sizepop=200，最大混合迭代数Maxgen1=500，最大内迭代数Maxgen2=10，模因组数m=20，每个模因组内的个体个数n=10，果蝇优化迭代步进值RandomValue∈[-1，1]；随机初始化果蝇群置为各函数的搜索区间。

4.2 实验结果与分析

4.2.1 算法在高维函数上的优化性能对比分析

智能优化算法普遍存在易陷入局部最优，导致后期收敛速度变慢，收敛精度降低的问题，尤其对于高维、多峰复杂优化问题[15-16]，该实验均在高维函数上完成。

以100维的单峰函数f1和多峰函数f2为例，分别采用FOA、SFLA和SFOALDS三种算法对其进行优化，全局寻优函数最小值，从而测试本文算法在高维函数上的优化性能。经过30次连续运行后的平均最优适应值（全局寻优函数最小值的算术平均）进化曲线如图2所示，图中纵坐标用平均最优适应值的常用对数表示，横坐标为进化代数。从图2中可以看出，SFOALDS的收敛性能和优化精度明显优于FOA和SFLA，尤其是对于f2，SFOALDS依然能很快达到理论极小值0，有效避免了FOA和SFLA陷入局部最优的缺点。

以高维、多峰函数f2、f4和f5为例，函数维数从40～100维变化，分别采用FOA、SFLA和SFOALDS三种算法全局寻优函数最小值，从而测试本文算法性能随函数维数增加而变化的情况，以优化均值和相对变化率作为评价指标。经过30次连续运行后的实验结果如表2所示，表中优化均值=全局寻优函数最小值的算术平均，相对变化率=|40维的优化均值-100维的优化均值|/40维的优化均值。从表2中可以看出，随着函数维数的增加，三种算法的优化性能都普遍降低了，即优化均值都增大了；但不论维数如何变化，三种算法中依然是SFOALDS的优化性能最好，即优化均值最小；还可以看出，三种算法中SFOALDS的相对变化率也是最小的，这说明随着函数维数的增加，SFOALDS优化性能相对降低得最少，从而也说明，随着函数维数的增加，SFOALDS相对于FOA和SFLA的优化性能的优势会更加突出。

三种算法在f4和f5上的优化均值随函数维数变化而变化的趋势线如图3和图4所示，图中纵坐标用优化均值表示，横坐标为函数维数。从图3、4中可以看出，FOA和SFLA优化均值随函数维数增加单调递增，并且维数越大，优化均值的增长率越大；SFOALDS优化均值随函数维数增加不是单调递增的，甚至当函数维数增加时优化均值反而减小了。

需特别指出，SFOALDS特别适用于优化f2，不论函数维数如何变化，优化均值都为0。

5 结语

针对果蝇优化算法局部深度搜索能力较差和易陷入局部最优的缺点，将混合蛙跳算法的局部深度搜索策略融入到果蝇优化算法中，提出了一种局部深度搜索的混合果蝇优化算法。该算法充分发挥了FOA和SFLA各自的优势，既保持了FOA原有的较强的全局搜索能力和较快的收敛速度，又平衡了整个种群的“探索”和“开发”能力，有效避免了基本FOA易陷入局部最优的缺点。通过优化5个测试函数的仿真结果表明，本文算法收敛速度和寻优精度均优于FOA和SFLA，且该算法具有简单、高效的特点，适用于解决实际工程问题。

参考文献：

[1]PAN WT. A new fruit fly optimization algorithm： taking the financial distress model as an example [J].KnowledgeBased Systems， 2012， 26： 69-74.

Wen-Tsao Pan

[2]PAN WT. Fruit fly optimization algorithm [M]. Taipei： Tsang Hai Book Publishing Co.， 2011： 10-12. （潘文超.果蝇最佳化演算法[M].台北：沧海书局，2011：10-12.）

[3]PAN WT. Using fruit fly optimization algorithm optimized general regression neural network to construct the operating performance of enterprises model [J]. Journal of Taiyuan University of Technology：Social Sciences Edition， 2011， 29（4）： 1-5.（潘文超.应用果蝇优化算法优化广义回归神经网络进行企业经营绩效评估[J].太原理工大学学报：社会科学版，2011，29（4）：1-5.）

[4]TIAN Y， ZHANG B， LIU D， et al. Condition trend prediction of hydroelectric sets based on fruit fly optimization algorithm optimized GRNN [J]. Water Resources and Power， 2012， 30（12）：127-129. （田源，张彼德，刘代伟，等.基于果蝇优化算法的GRNN水电机组状态趋势预测[J].水电能源科学，2012，30（12）：127-129.）

[5]WANG X， DU K， QIN B， et al. Drying rate modeling based on FOALSSVR [J]. Control Engineering of China， 2012， 19（4）： 630-633. （王欣，杜康，秦斌，等.基于果蝇优化算法的LSSVR干燥速率建模控制工程[J].控制工程，2012，19（4）：630-633.）

[6]WANG X， ZOU Z. Identification of ship manoeuvring response model based on fruit fly optimization algorithm [J]. Journal of Dalian Maritime University， 2012， 38（3）： 1-5. （王雪刚，邹早建.基于果蝇优化算法的船舶操纵响应模型的辨识[J].大连海事大学学报，2012，38（3）：1-5.）

[7]XIAO Z. Application of improved FOA on audio signal blind separation [J]. Computer Engineering and Applications， 2013， 49（16）： 201-204. （肖正安.改进FOA算法在语音信号盲分离中的应用[J].计算机工程与应用，2013，49（16）：201-204）

[8]HU W， LI Z. A simpler and more effective particle swarm optimization algorithm [J]. Journal of Software， 2007， 18（4）： 861-868. （胡旺，李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报，2007，18（4）：861-868.）

[9]WANG L， HONG Y， SHI Q. Global edition artificial fish swarm algorithm [J].Journal of System Simulation， 2009，21（23）：7483-7486. （王联国，洪毅，施秋红.全局版人工鱼群算法[J].系统仿真学报，2009，21（23）：7483-7486.）

[10]MA D， GUO X， DENG L. Ammunition scheduling of carrier-based aircraft based on modified ant colony algorithm [J]. Journal of System Simulation， 2012， 24（6）： 1207-1211.（马登武，郭小威，邓力.基于改进蚁群算法的舰载机弹药调度[J].系统仿真学报，2012，24（6）：1207-1211.）

[11]HU J. Research on the modified bacteria foraging optimization algorithm and its application [D]. Wuhan： Wuhan University， 2012. （胡洁.细菌觅食优化算法的改进及应用研究[D].武汉：武汉大学，2012.）

[12]WOLPENT D H， MACREADY W G. No free lunch theorems for optimization [J]. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 67-82.

[13]EUSUFF M M， LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm [J]. Journal of Water Resources Planning and Management， 2003， 129（3）： 210-225.

[14]CUI W， LIU X， WANG W， et al. Survey on shuffled frog leaping algorithm [J]. Control and Decision， 2012， 27（4）： 481-487. （崔文华，刘晓冰，王伟，等.混合蛙跳算法研究综述[J].控制与决策，2012，27（4）：481-487.）

[15]LI M， JI T， TANG W， et al. Bacterial foraging algorithm with varying population[J]. BioSystems， 2010， 100（3） ：185-197.

[16]JIN Q， ZHAO Z， SU X， et al. PSO algorithm with high speed convergence based on particle health [J]. Journal of Chemical Industry and Engineering， 2011， 62（8）： 2328-2333. （靳其兵，赵振兴，苏晓静，等.基于粒子健康度的快速收敛粒子群优化算法[J].化工学报，2011，62（8）：2328-2333.）

[17]LIN C， FEND Q. New adaptive particle swarm optimization algorithm [J]. Computer Engineering， 2008， 34（7）： 181-183. （林川，冯全源.一种新的自适应粒子群优化算法[J].计算机工程，2008，34（7）：181-183.）

[18]MENG Q， WANG L. Shuffled frog leaping algorithm based on neighborhood orthogonal crossover operator [J]. Computer Engineering and Applications， 2011， 47（36）： 54-56. （孟庆莹，王联国.基于邻域正交交叉算子的混合蛙跳算法[J].计算机工程与应用，2011，47（36）：54-56.）

[19]LIU Y. Shuffled frog leaping algorithm with selection and adaptive mutation mechanism [J]. Computer Engineering， 2012， 38（23）： 206-210. （刘悦婷.带有选择和自适应变异机制的混合蛙跳算法[J].计算机工程，2012，38（23）：206-210.）

[20]ZHAO P， SHAO Z. Novel improved shuffled frog leaping algorithm [J]. Computer Engineering and Applications， 2012， 48（8）： 48-50. （赵鹏军，邵泽军.一种新的改进的混合蛙跳算法[J].计算机工程与应用，2012，48（8）：48-50.）