基于混合策略改进的果蝇优化算法

李良光，朱 丽，邢丽坤

(安徽理工大学 电气与信息工程学院，安徽 淮南 232001)

0 引 言

果蝇优化算法(fruit fly optimization algorithm，FOA)和其它智能优化算法相比有许多明显的优点，例如结构简单、易于实际应用、求解速度快、计算成本低等[1,2]，因此,在许多领域都得到了成功的应用。其中，Li等[3]将FOA应用于解决炼钢系统中混合流车间重调度问题，得到了不错的实验结果。Zhang等[4,5]将FOA引入服务计算，并对其性能进行了实验分析。Zheng等[6]设计了一种新的编码方案和多组技术，提高了解决半导体最终测试调度问题的效率。

然而，与其它优化算法一样，FOA也有其局限性。因此，近年来许多研究人员都在尝试改进FOA。其中文献[7]提出融合禁忌搜索的混合果蝇优化算法，即将“禁忌”与“特赦”思想引入果蝇算法，从而避免算法陷入局部收敛；文献[8]提出了一种基于极值优化的果蝇算法，将极值动态算法的基本思想引入FOA，通过改变初始分布策略，随机替换个体来提高果蝇种群的多样性，从而防止局部最优和提高收敛精度；文献[9]提出基于自适应改变迭代步长值的果蝇优化算法，根据群体每次迭代的历史记忆动态自适应地调整群体范围参数，采用更准确的精英策略，因此非常有效地加速群体向全局最优前端的收敛。

为了克服FOA的缺点同时保留其优点，本文提出混合策略改进的果蝇优化算法(mixed strategy based improved fruit fly optimization algorithm，MS-FOA)。采用搜索包围和螺旋上升组合搜索的方法，对果蝇个体历史最优位置进行更新，加快算法收敛速度；引入自适应加权系数提高算法的优化精度；结合多尺度高斯变异算子克服局部最优的限制。

1 基本果蝇优化算法

果蝇算法是根据果蝇在自然界中的觅食行为，果蝇以独特的嗅觉和视觉以及气味浓度来决定食物的位置。FOA的优化过程包括以下7个步骤：

步骤1 初始化种群大小Sizepop，最大迭代数Maxgen，随机生成群体位置X_axis、Y_axis；

步骤2 给出果蝇随机搜寻食物的方向和距离；

步骤3 计算食物位置与原点的距离Di，并使用倒数作为果蝇个体的气味浓度判定值Si；

步骤4 将果蝇个体的气味浓度判定值Si带入气味函数(或称适应度函数)，求出个体气味浓度值smelli；

步骤5 找出该果蝇群体中气味浓度最低的果蝇(求最小值)；

步骤6 保留已识别的最佳气味浓度值并更换群体位置；

步骤7 进入迭代优化求出最优值。

2 混合策略改进的果蝇优化算法

本文针对果蝇算法收敛速度慢，易陷入局部最优，寻优精度不高等问题，引入3种改进策略，提出一种基于混合策略改进的果蝇优化算法(mixed strategy based improved fruit fly optimization algorithm，MS-FOA)，算法的流程如下所示：

步骤1 初始化果蝇种群大小Sizepop，最大迭代数Maxgen，最大权重因子wmax、最小权重因子wmin和常量系数b，随机生成群体坐标X_axis、Y_axis；

步骤2 执行FOA算法中的步骤2～步骤5；

步骤3 计算自适应权重w；

步骤4 将种群划分为N个子种群，计算各子种群的变异因子,对每个果蝇进行高斯变异；

步骤5 对个体的历史最优位置，使用搜索包围和螺旋上升公式，进行加速搜索；

步骤6 按照更新后的位置公式自适应更新果蝇的位置；

步骤7 进入迭代寻优重复执行算法流程中的步骤2～步骤6，直到达到最大迭代数。

2.1 自适应权重系数

为了解决算法过早收敛的问题，将粒子群算法(PSO)惯性权重因子w[10]引入果蝇位置更新公式中。然而，随着迭代次数的增加传统惯性权重因子呈线性递减，这种变化易使得算法收敛速度过慢。因此，受文献[11]中改进策略的启发，本文在不改变原始权重因子变化趋势的情况下，引入非线性调整策略，综合利用了种群的惯性因子以及果蝇的适应度, 更加灵活有效地调节算法的局部和全局搜索能力,其公式可以表示为

(1)

(2)

其中，smelli是当前果蝇的适应度值，smellavg是果蝇种群的平均适应度值，smellav1，smellav2分别是适应度值大于果蝇种群平均适应度值的所有果蝇的平均适应度值，小于果蝇种群平均适应度值的所有果蝇的平均适应度值,wmax为最大权重因子，wmin为最小权重因子，r是[0,1]之间的随机数。

2.2 搜索包围和螺旋式上升

目前针对FOA的改进方法大多都是对步长值或果蝇全局搜索能力的调整，来提高算法的收敛精度和稳定性，然而，它忽略了果蝇算法的缺陷，那就是收敛速度慢的问题。受鲸鱼捕食猎物的启发[12]，本文在对个体历史最优位置的更新中，采用搜索包围和螺旋式上升组合搜索加快果蝇迭代速度。具体方法如下：

(1)搜索包围机制

a=2-2g/Maxgen

(3)

A=2a·rand-a

(4)

C=2·rand

(5)

(6)

(7)

(8)

(9)

(2)螺旋更新位置

(10)

(11)

对两种搜索策略选择相同的概率p进行位置更新，其数学模型表示如下

(12)

(13)

为了避免过早收敛、平衡算法探索和开发能力，将自适应权重系数引入历史最优位置更新公式中以提高算法的寻优精度，因此，变化后的位置更新公式为

(14)

(15)

2.3 多尺度高斯变异算子

2.3.1 多尺度协同变异

果蝇算法与其它智能算法一样，容易陷入局部收敛，为了克服对群体初始位置依赖引起的局部最优限制，提出多尺度协同变异。当算法达到局部极值时，会改变群体的位置，以避开局部最优。然后根据群体的新位置，迭代地寻找一个新的极值来寻找全局最优。

但是一个适当的突变尺度不能预先确定，必须考虑以下几个问题：

(1)如果突变尺度过大，可能会跳过一些极值点，包括全局极值；

(2)如果变异尺度太小，则可能需要大量迭代才能遍历整个搜索空间。这会大大降低算法的收敛速度。

为了解决上述问题，本文使用了一个具有不同尺度方差的高斯突变算子来逃离局部最优。

2.3.2 高斯变异算子

假设总共有M个突变尺度。初始化高斯变异算子的方差

(16)

(1)根据适应度值对群体中的果蝇进行分类；

(2)将排序后的果蝇分组生成M个子群，每个子群中有P=N/M个果蝇，计算每个子群的适应度值如下

(17)

(1)得到了所有子群的最大值和最小值，分别表示为Fitmax、Fitmin；

(2)每个子组的适应度值在第t次迭代中根据式(18)～式(20)设置

(18)

(19)

(20)

随着算法的迭代，变异算子可能变得非常大。因此，需要变异算子的标准差来规范变异算子

(21)

(3)根据各子群的标准差，将种群位置定义为

(22)

(23)

3 实验及结果分析

3.1 实验设计

为了研究MSFOA的性能，本文设计了两个对比实验：①FOA优化实验；②MSFOA 优化实验。通过对比实验来验证所提出的MSFOA算法的可靠性。实验选用6个著名的函数作为测试函数，测试函数的具体参数设置见表1。

表1 6个测试函数的参数设置

为了比较和突出MSFOA算法的优化结果，本文选择了具有更高要求的实验参数，两个参数可以设置为：初始种群数Sizepop=30，最大寻优数Maxgen=200，参照表1中每个函数的搜索区间随机初始化果蝇种群位置。

算法性能评估采用的方法：①固定寻优次数，评估算法的寻优能力和稳定性，并与参考文献[11]自适应粒子群优化算法APSO和文献[12]的鲸鱼优化算法WOA进行比较；②固定收敛精度目标值，比较MSFOA和FOA算法在不同高维情况下的运行时间，分析MSFOA的时间复杂度。

3.2 实验结果与分析

3.2.1 固定进化迭代次数的收敛速度和精度

6个测试函数的迭代次数设置为200，通过6个基准函数进一步比较FOA、WOA、MSFOA、和APSO 算法的性能。4种算法的个性化参数值的设置见表2。为了保证结果的可靠性，对每个测试函数独立运行20次，得到 20次的最优结果见表3。从表3中可以看出，使用改进后的MSFOA算法对单峰函数和多峰函数的均值和标准差都有明显改善。对于单峰函数f5，MSFOA比FOA的收敛精度和标准差提高了55个数量级，对于单峰函数f6，MSFOA的寻优精度更高，达到了e-207，比FOA和WOA高了207个数量级，比APSO算法高了95个数量级，并且MSFOA的收敛标准差为0，说明MSFOA达到目标精度后保持了良好的收敛状态；对于多峰函数f1,MSFOA的均值和标准差均达到了理论最优值0，对于多峰函数f3，MSFOA 和APSO的均值和标准差相同，其均值都优于FOA和WOA 16个数量级，充分说明MSFOA比FOA、WOA、和APSO收敛精度更高，收敛平稳性更好。

表2 4种对比算法参数设定

表3 算法优化性能比较

为了清晰地反映出改进算法的优化效果，图1～图6显示了6个测试函数的适应度进化曲线图(为了方便显示和观察收敛曲线，本文将函数的适应度作为基数10的对数)，形象对比了FOA、WOA、MSFOA和APSO算法在不同函数中迭代200次的收敛曲线。从6个函数收敛曲线中可以明显看出：对于多峰函数f1、f2、f3和f4，MSFOA比FOA、WOA和APSO稳定且逐渐接近全局最优；对于单峰函数f5和f6，MSFOA也能快速收敛，并且对于其它3种算法都会出现收敛停滞，陷入局部最优的情况，这明确地说明了MSFOA逃离局部最优并逐步接近全局最优的能力。总体来说，MSFOA算法具有更好的优化性能。

3.2.2 算法时间复杂度的分析

大多数的改进算法往往只注重提高算法的性能，却没有考虑算法运行的时间。然而一个可靠的改进算法还应该具有较低的时间复杂度。本小节选用3个比较典型的多模函数f1，f3和f4 来测试和分析时间复杂度。设置种群大小Sizepop=30，最大迭代数Maxgen=200，独立运行20次，为了验证本文改进的算法对于提升算法收敛速度的有效性，将函数设置在不同维度(30维、100维和300维)来计算两种算法的平均运行时间，D为维度，测试结果见表4。

图1 Rastrigin函数适应度进化曲线

图2 Schaffer函数适应度进化曲线

图3 Ackley函数适应度进化曲线

图4 Griewank函数适应度进化曲线

图5 Quartic函数适应度进化曲线

图6 Sphere函数适应度进化曲线

表4 f1、f3、f4的平均运行时间对比

从表4中可以看出，MSFOA在达到目标精度下所需的平均时间均比FOA少，对于30维函数，MSFOA和FOA所需的平均时间差不多,但是在计算高维函数时，MSFOA运行时间明显比FOA少，说明MSFOA在处理高维函数时复杂度更低，进而验证了本文在对个体历史最优位置的更新中，采用搜索包围和螺旋式上升组合搜索的方法，加快果蝇搜索迭代速度是可行有效的。

4 结束语

在保持传统果蝇算法良好性能的基础上提出了混合策略改进的果蝇优化算法，采用搜索包围和螺旋上升组合搜索的方法，能够快速找到全局最优解，将自适应权重系数引入位置更新公式中，融合多尺度高斯变异算子，使得改进后的算法克服了局部最优的限制，避免了过早收敛。通过对6个测试函数的仿真实验，仿真结果表明，本文所提出的MSFOA算法有效地提高了收敛精度，同时也保持了较低的复杂度。