吴经纬，杨 靖，龙道银，王 霄，覃 涛，余玲珍

（1.贵州大学 电气工程学院，贵州 贵阳 550025；2.中国电建集团贵州工程有限公司，贵州贵阳 550001）

0 引言

果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）由潘文超于2011 年提出，是一种模仿果蝇觅食行为而推演的智能群体算法［1］。与其它群体智能算法相比，FOA 具有寻优机制简单、容易理解、程序代码易于实现和所需调整的参数较少［2］等优点。当前，FOA 已成功应用于传感器网络节点定位［3］、股票价格预测模型［4］、光伏发电功率预测［5］和路径覆盖测试［6］等方面。

FOA 算法由于优化过程中的随机性，在搜寻过程中存在盲目搜索，会导致算法早熟收敛、陷入局部最优等不足。与其它典型群智能算法类似，FOA 算法相关参数设置决定了该算法性能。在近几年研究中，刘晓悦等［7］利用Logistic混沌搜索初始化果蝇群位置，提高了初始解的随机性和遍历性，从而提高FOA 初始种群的多样性；战非等［8］通过Lo⁃gistic 映射对算法初值进行优化，改进果蝇算法对初值的敏感性和不稳定性；时文峰等［9］引入混沌序列Logistic 映射以改进果蝇算法早熟收敛问题；张小平等［10］引入Logistic映射，解决果蝇算法早熟收敛问题。

上述基于混沌的改进算法尽管优化了FOA 算法性能，但是采用的是Logistic 映射，而该映射在［0，0.1］和［0.9，1］两个区域内有较高的取值率，因此该映射遍历不均匀性导致算法收敛速度较慢，造成算法执行效率降低。本文提出一种基于混沌映射Sinusoidal 的果蝇优化算法SFOA。①设计了一个与混沌相结合的参数α，通过提高种群位置的多样性以改善算法全局搜索能力；②将引入混沌参数α的改进FOA 算法与其它4 种混沌映射相结合，通过仿真实验，对比分析后得到最优算法，即SFOA 算法；③将混沌果蝇算法SFOA 与其它果蝇优化算法在7 种基本测试函数上相比较，仿真结果表明本文提出的改进果蝇优化算法具有更好的寻优精度和更快的收敛速度。

1 基本果蝇优化算法

果蝇优化算法（FOA）是一种源于果蝇觅食行为演化而来的新的全局优化进化算法。果蝇拥有在嗅觉和视觉上优于其它物种的特性，果蝇群体通过嗅觉有效地收集漂浮在空气中的各种气味，并往食物的方向靠近，然后利用敏锐的视觉辨别食物和同伴的位置，往食物味道浓度高的位置聚合，再利用嗅觉各自沿随机方向飞出以寻找食物，如此循环直到找到食物为止［11］。

FOA 可以总结为7 个步骤：

步骤1：初始化种群规模数sizepop、最大迭代数Maxgen和随机初始化果蝇群体位置X_axis、Y_axis。

步骤2：为果蝇方向和距离分配随机参数，产生新位置。

步骤3：估算果蝇与原点之间的距离Disti，再计算味道浓度判定值Si。

步骤4：将Si分别代入味道浓度判定函数，求出果蝇位置味道浓度Smelli。

步骤5：寻找该果蝇群体中味道浓度（适应度）最佳的果蝇个体。

步骤6：根据最佳果蝇位置，此时所有果蝇利用视觉向最佳位置飞去。

步骤7：最后迭代运算，重复步骤2—步骤5，在寻优过程中判断当前最佳味道浓度是否优于上一迭代结果，且判断当前迭代次数是否小于最大迭代数；若是则执行步骤6，否则结束。

2 混沌果蝇优化算法

2.1 混沌优化

果蝇群体位置对收敛速度和寻优结果有重大影响，基本果蝇优化算法的初始果蝇种群是随机的，在处理复杂非线性问题时，效果往往不太理想［12］。混沌是一种按照特定规律运行的非线性现象，具有较大的随机性和遍历性，利用混沌搜索的这些特性在生成果蝇种群位置时提高其多样性。为了提高FOA 的收敛速度和寻优精度，引入了一个由混沌优化的新参数α用于更新果蝇种群，相较于原公式可有效降低其寻优过程中陷入局部最优的可能，将式（2）改为：

式中，Xi,j、Yi,j为当前果蝇个体位置，Xj、Yj为当前最佳果蝇位置，SP为种群数量，n为维度。

2.2 SFOA 算法步骤

基于基本果蝇优化算法原理及上述改进方法，本文提出的混沌优化果蝇算法具体步骤如下：

步骤1：初始化种群规模sizepop、最大迭代次数Maxgen、维度n，根据式（1）确定随机种群位置等。

步骤2：估算果蝇与原点之间的距离Disti，再计算味道浓度判定值Si。

步骤3：将Si分别代入味道浓度判定函数，求出果蝇位置味道浓度Smelli。

步骤4：寻找该果蝇群体中味道浓度（适应度）最佳的果蝇个体。

步骤5：根据最佳果蝇位置，此时所有果蝇利用视觉向最佳位置飞去。

步骤6：根据式（8）对果蝇种群位置进行更新后再进行迭代运算，重复步骤2—步骤5，在寻优过程中判断当前最佳味道浓度是否优于上一迭代结果，且判断当前迭代次数是否小于最大迭代数；若是则执行步骤5，否则结束。

SFOA 算法运行伪代码如下：

3 仿真实验与结果分析

3.1 实验设计

为了验证基于混沌映射的改进果蝇算法SFOA 的优化性能，4 种混沌映射名称及表达式如表1 所示。本文对7个基准测试函数进行了求最小值问题的优化仿真实验，测试函数如表2 所示。

Table 1 Four chaotic maps表1 4 种混沌映射

Table 2 Test functions and parameter setting表2 测试函数及参数设定

本文具体参数设置为：种群规模sizepop=30，最大迭代数Maxgen=1 000。所有算法采用Matlab R2016b 进行编程，计算机配置为：Intel Core（TM）i5-8250U、1.6GHz、4GB内存、Windows10 操作系统。

实验内容如下：①将基于混沌映射的4 种改进果蝇算法 即Logistic-FOA、Tent-FOA、Circle-FOA 和Sinusoidal-FOA 进行对比实验，以确定性能最佳的混沌果蝇算法SFOA；②将确定的混沌果蝇算法SFOA 与基本果蝇算法FOA 和其它参考文献的改进果蝇算法进行对比实验；③SFOA 算法与基本果蝇算法FOA 和其它参考文献算法在高维、多峰函数上进行性能比较分析。

3.2 实验评价标准

实验中各算法独立运行20 次，设置终止条件为迭代次数达到1 000 次。为评价算法优化效果，本文给出如下3 个判定标准：①优化均值（MEAN），算法运行20 次后得到的最优值的期望，用来衡量算法寻优平均质量；②标准差（STD），算法运行20 次后得到的最优值与平均最优值之间的标准差，评价算法寻优稳定性；③全局最优解（BEST），算法运行20 次得到的全局最优解。

3.3 实验结果与分析

3.3.1 基于混沌映射的果蝇改进算法性能比较

7 个测试函数的进化迭代次数固定为1 000，分别采用4 种基于混沌映射的改进果蝇算法对其进行求解，各算法独立运行20 次，其实验结果如表3 所示。

Table 3 Performance comparison of four chaotic fruit-fly algorithms表3 4 种混沌果蝇算法性能比较

从表3 可以看出，4 种混沌果蝇算法相比，基于混沌映射为Sinusoidal 的改进果蝇算法比其它3 种混沌映射的整体性能更好，更接近理论最优值，其求解得到的平均最优值（MEAN）、标准差（STD）、全局最优值（BEST）均优于其它3 种混沌映射。

比其它混沌映射具有更高的精度以及更好的稳定性，也进一步说明该算法的可行性和有效性。

3.3.2 固定进化迭代次数收敛速度与精度

将7 个测试函数F1～F7 固定迭代次数为1 000 次，分别采用FOA、CDSFOA［13］、CSFOA［14］、VSFOA［15］和SFOA 算法经过20 次独立运行，并分别将运行得到的优化均值（MEAN）、标准差（STD）和最优值（BEST）进行表征，维数均设置为30，得到的实验结果如表4 所示，图1 是算法寻优测试曲线。

Table 4 Comparison of the performance of the reference algorithms表4 与参考文献算法性能比较

由表4 可知，对7 个基准测试函数的实验结果中，SFOA 的3 项评价指标均优于FOA 算法、CDSFOA 算法、CSFOA 算法和VSFOA 算法。具有较好的优化均值和较小的测试标准差，尤其对于单峰函数F1、多峰函数F4、F5、F6和F7 而言，SFOA 算法的优化均值和测试标准差的数量级都远高于其它4 种算法，在单峰函数F2 的优化上，SFOA算法的均值优化与其它算法均在一个数量级，但测试标准差比其它算法更优，单峰函数F3 的优化均值和测试标准差与CSFOA 算法和VSFOA 算法的数量级一样，但SFOA算法仍更接近理论值，说明SFOA 算法在整体上具有较好的优化精度和较强的鲁棒性；并且具有最优的BEST 指标，尤其对于测试函数F1、F4、F6 和F7 而言，SFOA 算法的全局最优值均优于其它算法，在单峰函数F2 和F3 优化上，SFOA 算法的全局最优虽与其它算法在同一数量级，但仍更接近理论值，对于多峰函数F5 而言，SFOA 算法的全局最优与CSFOA 算法和VSFOA 算法相比均在同一数量级，但仍优于FOA 算法和CDSFOA 算法，表明本文改进算法保证了较好的最优预测性能。

为了对比5 种算法对各测试函数的迭代寻优性能，绘制了5 种算法的迭代寻优对比曲线，如图1 所示。

Fig.1 Optimization test curves of five algorithms图1 5 种算法的寻优测试曲线

由图1 可以看出，在对各测试函数的迭代寻优过程中，SFOA 算法与其它算法相比不仅保证了算法前期较好的全局寻优性能和较快的收敛速度，而且在算法后期也有效实现了进一步局部搜索。因此，在一定程度上说明改进算法SFOA 具有较好的迭代寻优性能。其中，虽然对于单峰测试函数F3 和多峰测试函数F5 而言，SFOA 算法略逊于CSFOA 算法和VSFOA 算法，但SFOA 算法的收敛速度仍远远高于其它算法。而且对于单峰测试函数F1、多峰测试函数F4、F6 和F7 的优化，SFOA 算法的收敛速度和寻优效果都远高于其它4 种算法。因此，SFOA 算法不仅对单峰测试函数具有较好的寻优性能，而且对Ackly、Griewank、Rastrigin 和Solomon Problem 多峰测试函数也表现出较好的寻优性能和收敛精度，进一步验证了SFOA 算法的优良寻优性能。

3.3.3 算法在高维、多峰函数上的性能对比

全局优化算法普遍存在易陷入局部最优，导致后期收敛速度变慢、收敛精度变低的问题，尤其上对于高维、多峰复杂优化问题。将FOA、CDSFOA［13］、CSFOA［14］、VSFOA［15］和SFOA 在不同测试函数上，对维数依次递增的情况下各算法的优化均值（MEAN）进行实验比较。在不同测试函数条件下，对各算法独立运行20 次，结果如表5 所示。

Table 5 Comparison of optimization mean values on multi-dimensional and peak functions表5 在多维、高峰函数上的优化均值比较

由表5 可知，对于多峰测试函数Griewank 和Rastri⁃gin，SFOA 算法的优化均值显著优于FOA、CDSFOA［13］、CS⁃FOA［14］和VSFOA［15］，并且随着测试函数维数的增加，SFOA算法的优化均值基本在同一数量级内变化，比较接近理论最优值，而且对于多峰函数F5 而言，SFOA 算法随着维数的增加，其优化均值不仅没有远离理论最优值，而且随着维数的增加而减少，但FOA 算法和其它改进果蝇算法则随着维数的增加，其优化均值逐渐远离理论最优均值。这表明随着维数的增加，SFOA 算法对高维的复杂函数仍保持平稳且较高精度的寻优性能。

3.3.4 算法时间复杂度分析

时间复杂度是指算法执行所需要的计算工作量，主要取决于问题重复执行次数，在SFOA 算法中，时间复杂度主要受到种群规模sizepop、迭代次数Maxgen和维度n的影响，在计算时间复杂度时，种群规模为N，迭代次数为M，维度为n，因此SFOA 算法的时间复杂度为O（M×N×n）。

4 结语

本文针对FOA 寻优精度低和易陷入局部最优等缺陷，引入与混沌相结合的新参数，提出一种混沌果蝇优化算法——SFOA 算法，利用混沌搜索的随机性和遍历性这些特性，在更新果蝇种群的初始位置时提高其多样性，达到优化全局搜索能力的目的。通过7 个基本测试函数测试，基于Sinusoidal 映射的改进果蝇算法具有更好的优化性能，仿真结果表明，本文提出的算法SFOA 相比基本果蝇算法和参考文献的改进果蝇算法，测试指标至少高出3 个数量级，尤其针对高维、多峰函数，SFOA 算法的测试指标至少高出了2 个数量级，说明该算法比其它算法的性能更佳。下一步研究的重点是将SFOA 算法应用于实际工程领域中的约束优化问题和多目标问题等。