分数阶策略和带有Lévy飞行的螺旋蝙蝠算法

李苗苗，王秋萍，惠 蕙

西安理工大学 理学院，西安710054

近年来，模拟自然现象的群智能算法常被用于解决优化问题，以达到预期目的。群智能算法结构简单，具有并行和分布式特点，解决复杂问题时的效率和稳定性高，而被广泛用于实际优化问题。

蝙蝠算法[1]是一种基于群体智能的启发式搜索算法，可以有效地搜索全局最优解。它是一种随机搜索算法，通过模拟蝙蝠的回声定位以检测猎物并避开障碍物，并且结合现有优化算法的优点，使其在解决优化问题方面更具优势。基于BA的算法已应用于多个领域，例如优化节能系统[2]、神经网络模型[3]、多级图像阈值处理[4]等。与其他传统的优化技术相比，BA算法具有较强的优势，但存在陷入局部极值的可能，从而会降低收敛速度和准确性。因此，国内外学者对其进行了各种改进研究。Paiva等[5]使用柯西突变算子和精英反向学习策略来提高BA的多样性和收敛速度。Cai等[6]提出了具有高斯随机游走的BA算法，以增强局部搜索能力。Cui等[7]提出了一种具有惯性权重的蝙蝠算法，该算法可以控制每个蝙蝠先前速度的惯性影响，并提高了局部搜索能力。

上述基于蝙蝠算法的改进，从不同方面提高了算法的性能。为了进一步提升算法性能，本文提出一种新的改进的蝙蝠算法，具体改进如下：利用分数阶对历史经验的记忆性，自适应调整阶次，增强种群多样性，加快了算法收敛速度；将Lévy飞行与阿基米德螺旋结合产生局部新解，增强了算法的局部开发和跳出局部最优能力；为更好地平衡算法的探索和开发能力，采用新的动态机制调节响度和脉冲发射率。最后，将FOSBA在CEC2014测试集和减速器设计问题上进行对比实验，验证其有效性。

1 蝙蝠算法

1.1 基本的蝙蝠算法

蝙蝠算法[1]是在理想状态下，利用蝙蝠在觅食时所发出的脉冲频率、响度、脉冲发射率的变化而设计的一种群智能算法。蝙蝠使用声波回声定位、检测猎物、躲避障碍，并且在逼近目标时会增大脉冲发射率，减小响度。蝙蝠寻找猎物理想化过程如下：

（1）蝙蝠使用回声定位来确定与目标的距离。

（2）蝙蝠以速度vi向一个位置xi飞行，并通过不同波长(λ)和响度(A)搜索位置，在给定的频率间隔(fmin,fmax)内发射，以检测猎物或躲避障碍。

（3）蝙蝠在计算与目标的距离时，可以调节信号的波长和脉冲速率。

（4）A从最大值(Amax)降到最小值(Amin)。当Amin=0意味着蝙蝠刚刚找到了猎物，暂时停止发出任何声音。在d维搜索空间中，第i只蝙蝠在第t次迭代中的位置和速度更新公式为：

其中，β是[0，1]均匀分布的随机数；fi是蝙蝠的搜索脉冲频率，fi∈[fmin,fmax]；x∗是当前最好的解。

对于算法的局部搜索，一旦从当前解集选取最好的解，那么通过随机游走产生新解：

这里ε∈[-1,1]是服从均匀分布的随机数，At是所有蝙蝠在t次迭代中的平均响度。响度和脉冲发射率的更新公式为：

1.2 改进的蝙蝠算法

蝙蝠算法是基于蝙蝠回声定位设计的一种随机搜索算法，具有较好的搜索能力。然而，同其他智能优化算法一样，基本的蝙蝠算法在优化过程中存在收敛速度低，易陷入局部极值等不足，譬如在蝙蝠的位置中，个体的位置与速度有关，而速度依赖于当前全局最好解，每次进行全局位置更新时，就会受上一代位置与当前最好解位置的距离牵制，导致算法的全局搜索能力不足，易陷入局部最优；另外，基本的蝙蝠算法在迭代后期响度趋于零，脉冲发射率趋于最大值，如果产生的优良新解，由于不满足条件而不能被接受，就会导致算法早熟。

针对上述问题，本文将分数阶策略、带有Lévy飞行的阿基米德螺旋策略以及动态调整响度和脉冲发射率进行结合，其目的是提高算法的收敛速度，加强算法的局部开发和跳出局部极值能力，避免迭代后期出现早熟，具体的改进策略如下。

1.2.1 基于分数阶的改进策略

分数微积分是公认的有效工具，可用来描述自然的行为，以及许多研究领域的实际问题，如工程、数学、物理、金融领域等[8]。其中，Grunwald Letnikov分数阶微积分形式[9]如下：

其中，Dβ(z(t))是Grunwald Letnikov（GL）的β阶导数，Γ是伽马函数。

从式（7）可以得到，整数阶导数具有有限项，而分数阶导数具有无限项，因此，整数导数是局部算子，而分数导数对所有过去事件具有记忆性。然而，对过去事件的影响随着时间的推移而减小。基于式（7），离散Grunwald Letnikov分数阶微积分可表述如下：

其中，P是采样周期，r为截断阶次，β表示阶次。

在基本蝙蝠算法中，蝙蝠位置更新如式（3）所示，将其变形为式（9）：

考虑前四项微分，得到本文的蝙蝠位置更新式如式（13）：

分数阶的阶次β影响着蝙蝠的位置更新，当β很小时，将忽略蝙蝠先前的活动容易陷入局部极值，但β太大，算法的复杂度会增加，花费时间更多。因此，本文采用式（14）调整分数阶阶次β,β取值范围为[0.4，0.6][9]，式中T是最大迭代次数。

基于上述分析，将分数阶微积分嵌入到蝙蝠算法[9]，在搜索前期，分数阶微积分凭借自身的记忆特性，可以提升算法的探索能力，随迭代次数增加，分数阶阶次不断减小，有利于后期算法开发。因此结合阶次自适应调整的分数阶策略，可以增强种群多样性，提高算法的收敛速度，获得高质量的解。

1.2.2 结合Lévy飞行的阿基米德螺旋策略

阿基米德螺线[10]是以恒定角速度绕固定点旋转并不断远离固定点而产生的的轨迹。在极坐标中，(R,θ)的定义如式（15）所示：

式中，θ是极角；参数a为起始点与极坐标中心的距离；参数b控制螺线间的螺距。本文将Lévy飞行与阿基米德螺旋结合产生局部新解，如式（16）所示：

其中，x∗是当前所有蝙蝠中的最好解，xlevy是基于Lévy飞行[11]产生的解，l,ε是[-1,1]内均匀分布的随机数，At是所有蝙蝠在t次代里的平均响度，λ是[λmin,λmax]范围内的随机数，xrr是在蝙蝠种群中随机选取的个体，μ和v服从正态分布，v~N(0,1)，即标准正态分布，μ~

其中，Γ为伽马函数，通常η的取值范围为(0,2][11]。

该螺旋策略以一定的旋转角度进行搜索，最大限度地避免了生成重复个体，能够有效提升算法的局部开发能力。Lévy飞行是一种随机游走方式，并且在随机游走过程中偶尔会出现长跳跃，在搜索过程中，Lévy飞行能够扩大群体搜索范围，协助算法在必要时跳出局部最优。与其他螺旋方式不同的是，本文在算法的局部位置更新中将Lévy飞行与阿基米德螺旋相结合，生成局部新解，该策略不但可以增强算法的局部开发能力，而且能有效协助算法跳出局部最优，提升算法搜索性能。

1.2.3 新的动态调节机制

脉冲发射率控制是否在当前全局最好解附近进行局部搜索，响度和个体适应值控制是否接受由局部更新产生的新解，基本的蝙蝠算法在迭代后期响度趋于零，如果产生的优良新解，由于不满足条件而不能被接受，就会导致算法出现早熟现象。受文献[12]的启发，采用式（19）、（20）更新响度和脉冲发射率，以此来平衡算法的探索和开发。改进后的脉冲发射率r″和原始脉冲发射率r、改进后的响度A″和原始响度A分别随迭代次数t的变化曲线，分别如图1和图2所示。改进后r随t的增加逐渐增加，且r″≤r,那么P(rand>r″)≥P(rand>r),此时有更高的概率在全局最好解附近进行局部搜索，有利于寻找最优解。原始A随t的增加逐渐趋于0，rand

图1 r″和r随迭代次数的变化Fig.1 r″and r with the number of iterations

图2 A″和A随迭代次数的变化Fig.2 A″and A with the number of iterations

其中，Amax=0.5,Amin=0.2,rmax=0.7,rmin=0.1[12]，c是控制参数。在算法在迭代前期，通过使用较低的脉冲发射率，从局部随机游走推进全局搜索，可以有效地探索解空间；在迭代后期，脉冲发射率取较大的值，可以提高开发能力。

1.3 改进的算法步骤

步骤1初始化参数，如种群规模n，速度vi(i=1,2,…,n)，响度Ai和脉冲发射率ri，蝙蝠位置xi，最大迭代次数T。

步骤2计算每只蝙蝠适应度，并找出当前最优值x∗。

步骤3当前迭代次数小于最大迭代次数时，根据式（1）、（2）、（13）更新蝙蝠速度和位置。

步骤4产生随机数rand1，若rand1>ri，则利用公式（16）在当前最优值附近产生一个局部新解。

步骤5产生随机数rand2，若rand2

步骤6将所有蝙蝠适应值排序，找出当前最优解x∗。

步骤7更新算法迭代次数，判断是否满足终止条件，如果满足，则停止迭代输出最优解，否则转至步骤3，直到满足终止条件。

2 数值实验

为了评估本文算法（FOSBA）的数值优化性能，选取CEC2014基准测试函数进行实验，该测试集包含30个不同类型函数，其中F1~F3是单峰函数，F4~F16是多峰函数，F17~F22是混合型函数，F23~F30是复合型函数。所有的数值实验在Matlab 2013（a）中进行。实验分为2个部分：第一，选取奇数组测试函数，将FOSBA与其他改进的蝙蝠算法进行实验对比；第二，选取偶数组测试函数，将FOSBA与其他智能算法进行实验对比，并对实验结果统计分析。

2.1 FOSBA与改进的BA比较

本部分实验选取全局混沌蝙蝠优化算法（GCBA）[13]、自适应改进的蝙蝠算法（ICBA）[14]、基于横向交叉策略的蝙蝠算法（IBA）[15]，与FOSBA在CEC2014奇数组测试函数上进行实验对比。为保持实验的客观性，4个算法基本参数设置相同，脉冲频率取值范围为(0,2),r0=0.7,A0=0.2,α=β=0.9；n=30,T=500,D=30，其中GCBA算法学习因子c1=c2=1.496 18,本文的控制参数c=1.3，每个函数运行51次，并记录各算法结果的均值、标准差，结果如表1所示，其中最好的结果以粗体显示，表中均值反映了算法的优化能力，标准差反映了算法稳定性。

表1结果显示，FOSBA在多数函数上的寻优结果都要优于对比算法。对单峰函数F1、F3，FOSBA的均值和标准差都是最小的，说明该算法全局搜索能力较强。在多峰函数F5、F7、F9、F13、F15上，FOSBA优化结果精度和标准差均是最好的，说明该算法具有一定的探索能力和跳出极值点的能力。在测试函数F11上，GCBA表现出较强的寻优能力，在测试函数F13上，FOSBA与GCBA寻找到同样的结果，但FOSBA的标准差较小。在复合函数F17~F21上，FOSBA较其他算法，无论是均值或标准差都具有明显优势，说明带有Lévy飞行螺旋策略和非线性转换机制具有较强的适应性，从而能快速寻找最优解。

表1 FOSBA与改进BA结果比较Table 1 Comparison of FOSBA and improved BA

2.2 FOSBA与其他智能算法的比较

本部分实验选取差分进化算法[16]（DE）、细菌觅食算法[17]（BFA）、正余弦算法[18]（SCA）与FOSBA在CEC2014偶数组测试函数上进行实验对比，各算法的具体参数设置和参考文献相同。以上算法参数设置n=30,T=500,D=30，各算法独立运行51次，记录各算法结果均值、标准差，结果如表2所示，其中最好结果以粗体显示。

根据表2结果，FOSBA在多数函数上的寻优效果优于其他对比算法，并且在函数F2、F4、F12、F14、F30上的收敛精度明显提高且标准差相对较小。在多峰函数上F12、F14上，FOSBA的平均值与标准差更加优异，说明该算法能够有效避免局部最优，进而说明带有Lévy飞行的螺旋策略的有效性。在混合复合函数F18、F24、F26上，FOSBA具有显著优势，说明本文新的非线性转换机制能够有效平衡算法的探索和开发能力。而SCA在函数F6、F20的寻优效果优于FOSBA，表现出较好的寻优能力。

表2 FOSBA与其他智能算法结果比较Table 2 Comparison of FOSBA and other intelligent algorithms

图3给出了各算法在CEC2014测试函数上的部分收敛曲线图，直观反映了各算法的收敛性能。在单峰函数F1、F2上，FOSBA的收敛曲线下降快且曲线位于最下方，具有更高的寻优精度。SCA和FOSBA在F4上的曲线收敛值接近，但FOSBA在前期收敛速度快。在多峰函数F4、F15上，其他对比算法出现了一定程度的停滞，出现陷入局部极值情况，而FOSBA在后期仍能继续搜索，这归因于带有Lévy飞行的螺旋机制，加强了算法跳出局部最优的能力，提高了算法的局部开发能力。在混合和复合函数F18、F30上，FOSBA具有较好的稳定性，在搜索后期可能搜索速度稍慢，但寻优精度优于其他对比算法，说明新的动态调节机制可以有效平衡算法的探索和开发。

图3 各算法在CEC2014测试函数上的部分收敛曲线图Fig.3 Partial convergence curve of each algorithm on CEC2014 test function

采用Friedman秩方差检验分析FOSBA与其智能优化算法结果在统计上有无显著差异，取显著性水平为0.05。Friedman检验统计量S：

如果经过Friedman检验证明多样本存在显著性差异，再考虑Hollander-Wolfe检验来分析两两算法间的差异性。式（22）为两样本之间的比较公式：

其中，R.g和R.k为第g与第k个样本的秩和，如果|Dgk|≥Z1-α*时，表示两样本之间有差异，反之则无差异，α*=α/m(m-1)，α是显著性水平，Z1-α*为标准正态分布分位数。

表3 两两算法处理的Hollander-Wolfe计算表Table 3 Pairwise algorithm processing Hollander-Wolfe calculation table

2.3 算法复杂度分析

算法的复杂度是评估算法的重要指标之一，下面分析算法迭代一次的复杂度。更新全局位置和基于变量的上下界修正蝙蝠位置的复杂度是O(N)；计算适应度值和更新全局最优位置的复杂度是O(N)；采用分数阶策略更新全局位置的复杂度为O(TNr)；采用阿基米德螺旋局部更新蝙蝠位置的复杂度是O(ND)；对响度和脉冲发射率更新的复杂度是O(N)；则算法迭代一次的复杂度是O(N)+O(N)+O(TNr)+O(ND)+O(N)=O(TNDr)。因此该算法的整体复杂度是O(TNDr)，其中N是种群规模，D是维数，T是最大迭代次数。

3 算法应用

在本章中，选取机械工程优化中的减速器设计问题，以进一步验证所提出算法解决实际工程约束优化问题的能力。由于工程问题的约束不同，罚函数法是常用的约束处理方法，在目标函数添加惩罚项，将问题转化成无约束优化问题进行求解，本章中应用罚函数法解决减速器设计问题。

如图4所示，该设计是非线性有约束的优化问题，目标是使减速器重量达到最小[19]，该问题有7个设计变量，分别是齿面宽x1，齿轮模数x2，小齿轮齿数x3，轴承之间的第一轴的长度x4，轴承之间的第二轴的长度x5，第一轴直径x6和第二轴的直径x7。具体数学模型如下：

图4 减速器问题示意图Fig.4 Schematic diagram of speed reducer design optimization problem

将FOSBA用于解决该非线性问题，种群规模为30，最大迭代次数为500，独立运行30次，并将实验结果与文献[20]、文献[21]、文献[22]进行比较，记录了各设计变量的取值以及最好的适应值，比较结果如表4所示，FOSBA的优化结果优于其他对比算法。

表4 减速器设计问题优化结果比较Table 4 Comparison of results for speed reducer design optimization problem

4 结论

本文提出一种改进的蝙蝠算法（FOSBA），依据分数阶对历史事件的记忆性，在蝙蝠位置更新中引入分数阶微积分，增加群体多样性，提高了算法收敛速度；将Lévy飞行与阿基米德螺旋结合产生局部新解，增强算法的开发能力，同时Lévy飞行协助算法跳出局部最优；通过新的方式动态调节响度和脉冲发射率来平衡全局勘探和局部开发能力。在CEC2014基准测试集上和减速器设计问题上进行实验，结果表明本文算法具有较高的寻优精度和收敛速度，并用Firedman统计分析证实了本文算法有效性和优越性。最后，将FOSBA用于减速器设计问题，验证了本文算法优良性能。