自适应多普勒补偿与变异选择的蝙蝠算法*

王永贵，张博雅，吕欢欢

辽宁工程技术大学 软件学院，辽宁 葫芦岛125105

1 引言

元启发式算法是随机算法与局部搜索算法相结合的产物，可以在全局搜索和局部搜索之间取得平衡。元启发式算法由适者生存和随机选择两部分组成，适者生存确保可行解收敛到最优值，而随机选择可使搜索方式在局部搜索和全局搜索间相互转换，增加可行解的多样性，避免陷入局部极值。由于元启发式算法可在合理的时间和空间开销下获得问题的可行解，不受搜索空间限制条件（如不可微、非凸、多峰）的约束且不需要梯度等其他辅助信息，其作为主流优化方法受到广泛的关注。近年来，许多学者从自然界中得到启发，模仿生物行为或自然现象，以种群为基础提出了各种新型元启发式算法。其中，蝙蝠算法[1]（bat algorithm，BA）是一种基于群体智能的新型元启发式算法，它是根据蝙蝠利用回声定位搜寻猎物和避开障碍物的特性发展而来。目前，BA已被广泛应用在风能开发[2]、模型预测[3]、无人机路径规划[4]、经济调度[5]等领域。虽然BA 具有收敛迅速、参数少、鲁棒性强等优点，但和其他元启发式算法一样，BA 不可避免地存在易陷入局部最优和求解精度不高的缺点。为了克服这些缺点，提高全局探索和局部开发能力，目前一些学者主要从以下四方面对BA 作出改进。

（1）融合其他进化算法。充分发挥其他算法的优点弥补自身的不足。例如文献[6]结合和声搜索的音调微调算子产生变异的蝙蝠个体，根据精英选择策略保留能进入下一代的最优个体，从而改善对搜索空间的探索。文献[7]采用差分进化中rand/1/bin、randToBest/1/bin、best/1/bin 和best/2/bin 四种不同的变异策略替换BA 原有的局部搜索模式，增加种群多样性来提高搜索效率。文献[8]引入蛙跳算法，考虑个体与群体间的信息交流，加快全局收敛。

（2）利用混沌映射。混沌是非线性系统的一个特征，由简单的确定性系统随机产生。例如文献[9]用混沌映射结合线性函数替换响度和脉冲发射率中的随机数，研究了11 种不同混沌映射对BA 优化效率的影响；文献[10]通过Logistic 映射对精英个体进行混沌优化，有效利用了混沌算法的局部搜索能力，避免BA 过早陷入局部最优。

（3）优化搜索方式。通过修改频率和速度方程，进而控制个体的搜索位置。例如文献[11]简化了位置方程，去除速度参数，新位置的产生取决于最优解和随机解，并根据平均解和最优解调整频率，提高收敛效率。文献[12]设计了最佳觅食策略来指导蝙蝠的移动方向，将历史最优位置替换为由最佳觅食策略产生的位置，并采用随机扰动策略加强蝙蝠之间的信息共享。文献[13]根据轮盘赌选择机制和概率方法，设计了四种不同的速度更新策略，加强蝙蝠的自我学习能力。文献[14]利用迭代局部搜索，当搜索陷入局部最优解时，对最优解进行适当的随机移动，从而突破当前空间获得新解，逃出局部极值区域，并引入随机惯性权重更新速度方程，在一定程度上继承历史速度的影响，稳定寻优结果。

（4）模拟生物行为。从生物学角度进一步模仿蝙蝠行为，使算法更符合自然规律。例如文献[15]分别设计了具有机械性能和量子特性的飞行策略，用来模拟蝙蝠在不同栖息地之间的移动，并在机械飞行中引入多普勒效应更新个体频率。文献[16]对蝙蝠产生两个不同的飞行方向，一个向着最优区域，另一个向着随机区域，通过比较随机个体与当前个体的优劣决定最终的飞行方向，在一定程度上模拟了蝙蝠利用回声之间的延迟来预测猎物位置的特性。文献[17]引入许多动物都存在的Lévy 飞行特征，搜索中经过一系列较小步长的移动后，突然转变方向产生一个较大的跳跃，从而拓展搜索空间，有效避免蝙蝠个体被局部极值束缚。

除此之外，还有学者从其他角度对BA 进行改进。例如文献[18]使用邻域搜索和动态惯性权重策略，提出了一种改进的二进制蝙蝠算法。文献[19]通过变异开关函数对满足条件的蝙蝠个体进行变异，保持较高的种群活跃性。文献[20]引入外部子群和内部子群，两个子群共同演化协作，分别增强探索与开发能力。文献[21]提出均衡负载的初始化策略，针对离散蝙蝠算法设计了新的搜索算子，最后应用于求解柔性作业车间调度问题。文献[22]结合三种局部搜索策略与和声搜索机制，使用新的随机游走法则改善搜索能力，并用于求解无容量设施选址问题。

以上改进算法虽从不同角度提高BA 的性能，但在高维问题下仍难以准确收敛到理论最优值并存在早熟收敛的现象。从直观来说，算法越符合自然规律，就越能高效地解决问题，而BA 算法本质上是对自然界蝙蝠行为的简化与抽象，因此对BA 算法的改进仍需进一步研究。本文提出自适应多普勒补偿与变异选择的蝙蝠算法（Doppler and mutant bat algorithm，DMBA），该算法首先根据蝙蝠较自身相对猎物距离的远近变化，对频率进行自适应多普勒补偿，进一步模拟回声特性，同时利用种群平均速度产生速度偏移，修正飞行方向。其次，提出柯西和高斯变异机制，使最优个体在开发的不同时期自适应选择变异策略，避免陷入局部极值从而精确搜寻最优值。最后，通过调节响度和脉冲发射率，使算法前期执行全局探索，后期执行局部开发，有效平衡探索和开发能力。

2 蝙蝠算法与多普勒效应2.1 蝙蝠算法

BA 算法[1]是在理想状态下，简化回声定位的特征，模拟蝙蝠在捕食飞行中发出声波的响度和脉冲发射率的变化，接收频率、速度和位置信息搜寻最优解。在D维下，记f(x)为目标函数，分别为第t代中第i只蝙蝠的位置和速度，fi和分别为蝙蝠的频率和响度，为脉冲发射率。在完成以上参数的初始设置后，算法进入以下4 个迭代过程：

（1）随机飞行。蝙蝠的空间位置通过下式更新：

其中，fmin和fmax分别是最小和最大频率值，β∈[0,1]是服从均匀分布的随机数，x*代表当前搜寻到的全局最优解。

其中，ϵ是随机向量，ϵj∈[-1,1],j=1,2,…,D，At是平均响度，rand1是[0,1]内服从均匀分布的实数。

（3）接受新解。通过式（1）或式（2）产生新个体后，如果并且，则接受，其中rand2是[0,1]内服从均匀分布的随机数。

（4）参数调整。当新个体得到改进时，响度和脉冲发射率才会通过下式更新：

其中，α和γ都是常数，0 ＜α＜1,γ＞0,当蝙蝠逼近目标时，响度逐渐减小，不易被猎物察觉，而脉冲发射率逐渐增大，发出急促的脉冲信号，迅速定位猎物位置。当Ai减小到0 时意味着蝙蝠捕获到猎物，停止发声。

2.2 多普勒效应

事实上，蝙蝠能够通过目标昆虫翅膀颤动率引起的多普勒效应的变化来区分目标。这里将能够发射声波的物体称为声源，能接收声波的物体称为观察者。研究发现，当声源与观察者之间存在相对运动时，观察者听到的声音频率就会不同于声源的发射频率，这种现象就是多普勒效应。假定f为声源和观察者之间没有相对运动时，观察者听到的声音频率，即声源的发射频率；f′为声源和观察者有相对运动时，观察者听到的声音频率，若观察者的运动速度为v，声源的运动速度为u，声音在空气中传播的速度为c时，f′和f存在如下关系：

当观察者靠近声源时，v用“+”号，远离时用“-”号；当声源靠近观察者时，u用“-”号，远离时用“+”号。由于多普勒效应的作用，当观察者与声源互相靠近时，接收频率大于发射频率，观察者与声源互相远离时，接收频率小于发射频率。

3 本文算法3.1 自适应多普勒补偿

从式（1）可以看出频率本质上控制蝙蝠飞行的速度和位置，蝙蝠和猎物二者相对空气都在运动，因此声波的频率存在多普勒效应，而BA 算法的频率是在一个区间内随机取值，忽略了这种效应。在实际捕食中，蝙蝠本身会对频率进行多普勒补偿，通过调整频率获知猎物的精确位置。在文献[15]引入的多普勒效应中，蝙蝠与猎物向量在各维上差值的大小并不能准确反映二者的位置变化。因为根据多普勒原理，频率是随着观察者与声源在某一时刻前后相对位置的变化而改变的。因此为使算法接近实际，本文对频率自适应补偿策略的表达式如下：

其中，因为式（4）的频率和速度是标量，而算法中的频率是标量，速度是向量，所以用速度的模长代表速度值的大小。,v*表示当前猎物即最优个体的速度，代表当前时刻蝙蝠到猎物的距离，代表前一时刻蝙蝠到猎物的距离。该补偿策略参照了蝙蝠在上一次迭代中的位置，频率的自适应调整取决于蝙蝠与猎物间距离的相对变化，具体远近的程度是根据蝙蝠在先前迭代中的位置而言的。当蝙蝠向猎物发射一定频率的超声波后，在等待接收猎物反射回的超声波这一时期内，蝙蝠作为观察者，猎物作为声源。当蝙蝠与猎物不存在相对运动时，蝙蝠的发射频率等于猎物接收的频率，通常认为入射波的频率等于反射波的频率，故此时猎物作为声源发射的频率即为。因此对频率进行自适应调整的原理在于：如果，则表示当前蝙蝠个体相比前一时刻已远离了猎物，相当于观察者逐渐远离声源，根据式（4），二者从前后时刻来说相互远离，故取“-”号，v*取“+”号。此时蝙蝠接收到较低频率的超声波，应当放慢飞行速度，围绕在猎物周围细细探寻；如果，说明前后时刻二者的距离不变，既没有远离也没有接近，或者在迭代后期蝙蝠已经捕获到猎物，即找到最优解，此时应保持当前的频率不再作调整；如果，则表示当前蝙蝠个体相比前一时刻更加接近猎物，相当于观察者逐渐接近声源，根据式（4），二者从前后时刻来说相互靠近，故取“+”号，v*取“-”号。此时蝙蝠会接收到更高频率的超声波，从而加速飞向猎物。之所以考虑先前迭代与当前迭代中蝙蝠和猎物的距离，是因为在每一次迭代中，猎物的位置是变化的，蝙蝠自身的位置也是在变化，当前时刻下二者间距离的远近是基于前一时刻各自的位置而言的。

另外，频率和速度共同影响了新解的位置，并且BA 算法中蝙蝠的飞行具有很强的随机性，影响自身对最优解的搜寻。定义式（1）为方式1，文献[23]指出根据方式1 产生的新位置会使算法发散，并证明其收敛区域为空集。因此，本文对速度产生偏移，结合补偿后的频率的位置更新方程如下：

其中，w是[0,1]上服从均匀分布的随机数，vm表示种群平均速度。定义式（6）为方式2，不同于方式1，方式2 的速度更新策略引入vm作为种群对个体自身速度的影响，并将方式1 的改为，从而修正飞行方向，确保算法产生的新解能在一个封闭区域内收敛，通过特征方程法证明其收敛的过程如3.5 节所述。

Fig.1 Two ways of generating new position图1 两种方式产生新位置

经过多普勒补偿后的频率控制了飞行速度的快慢，进而影响个体在搜索空间中的新位置，为直观描述补偿策略指导新解的准确性，将向量空间简化到二维平面。图1 表示在t-1 时刻，固定相同位置、速度和猎物x*时，蝙蝠利用两种方式产生新位置的差异。在方式1 中，蝙蝠的频率fi没有经过多普勒补偿，而是在上下区间内取随机值，因此频率可大可小，如图1（a）所示，没能修正新速度的模长和方向，最终使新位置远离猎物x*。在方式2 中，根据个体与猎物在前后时刻相对远近的变化，蝙蝠的频率受到多普勒效应的自适应调整。图1（b）表示当蝙蝠个体远离猎物时，经过补偿策略的影响，接收到更低的频率。较小的频率作用于交换顺序后的位移偏差，最终与速度偏差共同决定新速度，此时的模长小于旧速度的模长，方向比向着猎物x*，围绕在猎物周围减速飞行。图1（c）表示当蝙蝠个体接近猎物时，同样受到补偿策略的影响，此时接收到更高的频率，结合速度和位移偏差产生新速度，其模长大于的模长，方向比更加接近x*，从而加速飞向猎物。从图1（b）和图1（c）可知，个体在接收到更低或更高频率时，通过方式2 产生的要比方式1 接近x*，促使蝙蝠努力朝最优解的方向飞行。

根据多普勒效应自适应补偿频率，调整飞行速度的大小和方向，尽可能地模拟蝙蝠在捕食中发生的自然行为，产生更接近猎物的新个体，从而快速定位到全局最优区域，提高全局探索能力。

3.2 变异选择策略

BA 算法根据式（2）进行局部搜索，然而响度随着迭代逐渐递减到0，对最优个体的扰动步长也逐渐减小，由于缺乏有效的变异机制，最终使种群在前期容易陷入局部极值。为此，已有很多方法对种群实行变异，例如使用和声[6]或差分[7]等算子能有效避免局部极值的吸引，增加种群多样性。从另一角度来说，这些算子可能会额外增加算法的负担。差分算子涉及突变、交叉和选择操作，和声算子涉及微调扰动和随机选择操作，可能会在一定程度上增加计算量，并且其各自参数如交叉概率和微调概率取值的不同，也可能会影响最终结果。因此为使算法易于操作并具有通用性，本文利用柯西和高斯分布的特性，在局部搜索中对最优个体提出柯西变异和高斯变异两种变异机制。图2 给出了标准柯西分布和标准高斯分布密度函数曲线的差异。可以看出，两种分布的密度函数相似，但从垂直方向上看，柯西分布在中心值附近的峰值小于高斯分布，在两端的峰值高于高斯分布；从水平方向上看，柯西分布越接近水平轴的两端，曲线下降越缓慢，而高斯分布的曲线趋近水平轴的两端。

Fig.2 Probability density of Cauchy and Gaussian图2 标准柯西与高斯概率密度

（1）柯西变异。由于柯西分布具有较高的两翼概率特性，它比高斯分布更容易产生具有更宽分布范围和远离原点的随机数。在局部搜索的前期，对最优个体进行柯西扰动，使蝙蝠个体能以大幅度的步长在最优区域附近探寻，拓展搜索空间，增大逃离局部极值的概率。本文根据标准柯西密度函数的特性，对最优个体构造柯西变异的方程如下：

其中，r是(0,1)上服从均匀分布的随机数，t是当前迭代次数，Tmax是最大迭代次数，C(1,0)是服从标准柯西分布的随机变量。

（2）高斯变异。由于高斯分布在中心值附近产生随机数的概率较高，在局部搜索的后期对最优个体进行高斯变异，使蝙蝠个体在最优值附近以小幅度的步长游走，对最优区域进行精细搜寻，准确寻找全局最优值。本文根据标准高斯密度函数的特性，对最优个体构造高斯变异的方程如下：

其中，r是(0,1)上服从均匀分布的随机数，N(0,1)是服从标准高斯分布的随机变量。

式（7）、式（8）中的1-t/Tmax是在[0,1]内的单调递减函数，在开发初期，t值较小，因此1-t/Tmax取值较大，当其大于在[0,1]内随机产生的数r时，算法对蝙蝠群的当前最优位置按照式（7）进行柯西变异扰动。在开发前期，柯西变异产生的较大变异步长能避免种群聚集在最优值附近，降低陷入局部极值的风险。随着迭代推进到开发的后期，t值增大，因此1-t/Tmax的取值逐渐变小，当其小于随机数r时，算法对最优位置按照式（8）进行高斯变异扰动。在开发后期，高斯变异产生的较小变异步长能使种群保持对最优解附近区域的空间开采能力，从而实行深度搜寻。两种变异机制互相协作配合，在开发阶段促使蝙蝠个体依据迭代的推进自适应选择变异策略，提高算法的整体收敛速度和寻优精度。

3.3 平衡探索与开发

3.3.1 响度和脉冲发射率更新策略

在DMBA 算法中，为了有效平衡算法的探索和开发能力，利用个体的脉冲发射率控制算法是执行全局探索还是局部开发，利用响度进一步决定是否接收具有更优适应度的新解，因此本文对响度和脉冲发射率提出如下更新策略：

其中，Amax和Amin分别是响度的最大值和最小值，rmax和rmin分别是脉冲发射率的最大值和最小值，tmax是最大迭代次数。

3.3.2 参数取值范围分析

根据式（9）当t′=tmax/2 时（tmax≫1），此时(rmax+rmin)/2，为实现探索到开发的转换，且和rand1都在[0,1]内，rand1服从均匀分布，应落到区间中点附近内，在t＞t′时提高发生转换的概率，即，解得0.8-rmax≤rmin≤1.2-rmax。而在初期要保证探索，rmax应取较大的值，即rmax∈[0.8,1.0]，此时对应的rmin∈[0,0.2]。对于响度，在成立的同时也要满足成立，获得改进的新解才能进入到下一代。根据式（9）递减到Amin，赋予其较大的值使成立即可，因为若过小，即使新解获得了改进，也不能被保留到下一次迭代，故取，即Amax=1，Amin=0.8。

为了确定rmin∈[0,0.2]和rmax∈[0.8,1.0]的最优参数值，需要分析在Amax=1，Amin=0.8 时，rmax和rmin分别取不同的值对算法寻优性能的影响。本文DMBA算法给出来自标准函数[24]的Schwefel 2.22（记为f1）和Quartic（记为f2）在100 维下，当rmax和rmin取不同值时求得的平均适应值fit 和标准差std 的比较结果，如表1所示。其中虚拟蝙蝠的数目为40，最大迭代次数为500，每个函数独立运行50 次。Schwefel 2.22 函数和Quartic 函数分别为单峰和多峰函数，其全局最优值均是0，因此算法求解结果的平均适应值越接近0，说明求解精度越高，标准差越小，收敛结果越稳定。

从表1 中可以看出，参数rmax和rmin的取值即共有9 种组合，整体来说，算法在各组合下的寻优效果相似。其中在[0,0.8]下，算法的寻优效果最好，另外[0.1,0.8]和[0.2,0.8]下的平均适应值和标准差在整体上的寻优效果更优于其他6 种组合。的范围在[0,0.8]、[0.1,0.8]和[0.2,0.8]内时，算法的寻优性能均具有优势，因此通过上述分析，本文DMBA 算法脉冲发射率的范围取[0,0.8]，响度的范围取[0.8,1.0]。

Table 1 Comparison of performance in value range of 表1 取值范围对算法寻优性能的对比

Table 1 Comparison of performance in value range of 表1 取值范围对算法寻优性能的对比

3.4 算法流程

本文DMBA 算法的执行流程如图3 所示。

Fig.3 Procedure of DMBA图3 DMBA 算法流程

步骤1初始化参数，包括蝙蝠个体数、变量维数、最大迭代次数、目标函数F(x)等。

步骤2产生初始种群，根据F(x)计算每只蝙蝠的适应度值，并记录最优个体x*。

步骤3遍历所有个体，依据式（5）和式（6）更新频率、速度和位置信息，产生新个体xnew。

步骤4生成随机数R1，若R1＞ri，则按照式（7）或式（8）选择变异机制，将变异个体赋值给xnew。

步骤5生成随机数R2，若R2＜Ai&F(xnew)＜F(xi)，则将xi替换为xnew，然后按照式（9）更新A和r。

步骤6对所有蝙蝠个体的适应值排序，更新当前最优解x*。

步骤7判断迭代次数是否达到最大次数或者能否求出满足精度要求的解，若是则输出最优解x*及对应的适应度，退出；否则重复步骤3～步骤7。

相对于上级的协调作用，采油厂是各项勘探开发行为运行的主体。各勘探、开发项目的经理及具体组成人员都来自于采油厂。直接掌握着各项目的投资及成本运行、进度运行、质量运行、各相关方关系运行等。

3.5 全局收敛性分析

根据式（6），即利用方式2 产生新解体现了算法的全局搜索能力，本文对此进行收敛性分析。尽管和是多维变量，但各维度下分量间均是相互独立的，故可以简化到一维进行分析[23]。为简化计算，假设在某一时刻下，个体频率记为常数e，种群最优解位置和平均速度不变，分别记为常数g和m。

定义1对于DMBA 算法，当采用方式2 产生新解时，极限在一个封闭区域内收敛。

证明由式（6）可得个体位置递推公式：

这是一个二阶常系数非齐次差分方程，利用特征方程法求其通解，对应特征方程如下：

记Δ=(1+w-e)2-4w，仿照二阶常系数齐次微分方程，分别求出通解。先由初始化时的x0、v0根据式（6）计算x1和x2：

（1）Δ＞0 时，，此时xt=C0+，C0为特解，C1、C2为待定系数，通过x0、x1、x2求出C0=x0-C1-C2，，。

由于t=0,1,…，故当t→+∞时，若要保证xt极限存在，由洛必达法则可知收敛条件是λ1,2＜1，解得-3 ＜w-e＜1，2w-e+2 ＞0，e＞0。

（2）Δ=0 时，λ=λ1=λ2=，此时xt=C0+(C1+C2t)λt，求出C0=x0-C1，C1=，。

当t→+∞时，xt收敛的条件是λ＜1，解此不等式得-3 ＜w-e＜1。

当t→+∞时，xt收敛的条件是0 ＜w＜1。

经过上述分析可以得到如下结论：

当Δ＞0 时，收敛区域为(1+w-e)2-4w＞0,2w-e+2 ＞0 和e＞0 所围成的区域。

当Δ=0 时，收敛区域为(1+w-e)2-4w=0 和-3 ＜w-e＜1 所围成的区域。

当Δ＜0 时，收敛区域为(1+w-e)2-4w＜0 和0 ＜w＜1 所围成的区域。

综合上面三种情况，DMBA 算法的收敛区域为2w-e+2 ＞0,-3 ＜w-e＜1,0 ＜w＜1和e＞0 所围成的区域，此时定义1 得证。 □

3.6 运算复杂性分析

下面将本文提出的改进蝙蝠算法DMBA 和标准BA 算法的运算复杂度进行分析和对比。

设第i次迭代中算法获得的最优解为1,2,…,M)，M为最大迭代次数。令ε为收敛阈值，若在第m次(m≤M)迭代中，，则认为满足收敛精度要求，终止迭代，否则继续迭代直到M次结束，记m为终止迭代次数。标准BA 算法和DMBA算法每一次迭代中的虚拟蝙蝠数量不变，均记为Pb，每只虚拟个体每一次迭代需要的运行时间为Ti(i=1,2,…,m)。设BA 算法的终止迭代次数为m1，则其时间复杂度为O(m1PbTi)；设DMBA 算法的终止迭代次数为m2，则其时间复杂度为O(m2PbTi)，故两者运行时间性能的差异主要决定于迭代次数m上，即语句执行次数。由3.1 节分析可知，对于每一次迭代下的每一只虚拟蝙蝠，BA 算法中个体位置的更新具有很强的随机性，致使新位置逐渐偏离最优解，而DMBA 算法受自适应多普勒补偿的作用，全局探索中个体的新位置逐渐向最优解靠拢，即在相同迭代次数下，DMBA 算法的运行结果会比BA 算法更加接近理论结果，比BA 算法先满足阈值要求，提前终止迭代，故m1＞m2（4.2 节实验表明，整体上减少运行时间。DMBA 算法相比标准BA 算法新改变的计算式如式（5）、式（9）均为常数级计算，式（7）或式（8）本质上与BA 算法的式（2）具有相同的计算结构，均为向量求和运算，对时间复杂度带来的增量远远小于语句执行次数带来的减量，可以忽略。因此DMBA 算法的时间复杂度O(m2PbTi)小于BA 算法的时间复杂度O(m1PbTi)，而增加的计算部分使得新解在搜索空间中的分布更加合理，解的适应性更好。

在空间复杂度方面，本文DMBA 算法比标准BA算法在每次迭代中增加了常数量级的中间变量如式（5）中的，式（6）中的vm等，以及与之相关的临时变量的存储，但整体上DMBA 算法的终止迭代次数远小于BA 算法的终止迭代次数，语句执行次数的降低减少了存储的中间变量和临时变量，因此空间复杂度相比BA 算法有所降低。

本文算法属于元启发式算法，这一类算法不能保证获得理论最优解，而是获得接近理论值的近似解。对于许多优化问题，使用确定性算法虽能获得理论最优解，但计算复杂（例如计算梯度等信息），运行时间很长，以致时间复杂度的代价极大，有时需要保存很多的变量，导致空间复杂度也较大。而随着问题复杂性的增加，求解工程实际问题往往并不需要得到理论最优解，只需要一个能逼近理论值的近似解就能解决问题，故元启发式算法比确定性算法更加适用。因此通过设置一定的满足条件如收敛阈值，使算法在获得一个符合实际需求的近似解的同时，能够提前终止迭代，避免往后不必要的运算，从而缩短运行时间，减少存储空间。

3.7 综合分析4 实验与结果分析4.1 测试函数

本文选取12 个标准函数[24]，大部分函数存在很多局部极值，故准确找到理论最优值具有一定难度，适合充分考察算法的寻优能力。如表2 所示，在所有测试函数中，f1～f6为单峰函数，主要用于测试算法的寻优精度和收敛速度；f7～f12为多峰函数，主要用于测试算法的全局搜索和跳出局部极值避免早熟收敛的能力。本文的所有测试均在Intel Core i5-4200M，2.5 GHz，8 GB 内存的PC Windows 7 机器上进行，编写的程序在Matlab R2016a上实现。

Table 2 Benchmark functions表2 标准测试函数

4.2 数值结果及分析

为了评价DMBA 算法在高维度下的寻优性能，本文除了选取BA 算法[1]，还选取近两年的NBA（novel bat algorithm）算 法[15]、dBA（directional bat algorithm）算法[16]和UGBA（uniform mutant and Gaussian mutant bat algorithm）算法[19]进行比较。

实验中所有算法的蝙蝠个数设置为40，最大迭代次数Tmax为500，各算法的具体参数设置如表3 所示。为了更清晰地表达算法寻优效果，设置误差值e=1.0E-100,当第t次迭代的结果时，可认为其达到全局最优值f(x*)（-1.0、0 或0.9），此时终止迭代，并记录迭代次数和运行时间，否则继续迭代直到Tmax时结束迭代。

Table 3 Algorithm parameter setting表3 算法参数设置

5 种算法针对12 个标准函数分别在100 维、500维和1 000 维上独立运行50 次后，通过计算平均寻优值mean、标准差std、平均终止迭代数iter 和平均运行时间time（s）考察算法性能。实验中最好的结果用粗体显示，Inf 表示正无穷，NaN 表示由Inf 参与运算得到的非数。

根据表4～表6，从收敛精度上分析可知，DMBA算法在不同维数下的寻优效果具有明显的优势，其他4 种算法的求解精度整体上随着维数的增加而降低。对于单峰函数f1～f6，随着维数的增加，DMBA算法均达到收敛阈值从而获得了理论最优值和标准差；UGBA 和NBA 算法均在f1获得了理论最优值和标准差。对于f2，UGBA 算法在100 维度下获得了理论最优值和标准差，但在500 维和1 000 维上其求解精度降低。对于f5和f6，BA、dBA 和NBA 算法的寻优结果逐渐偏离理论值，精度上的偏差在高维度下进一步扩大，在1 000 维下的平均适应值均是正无穷；NBA 算法在500 维和1 000 维下同样不能得出确切的运算结果。对于多峰函数f7～f12，在不同维数下，DMBA 算法在除f9外的函数上均达到收敛阈值从而求解到理论最优值和标准差；UGBA 算法在f8上均能求解到理论最优值，在100 维下求解f10获得了理论最优值；对于f8、f9和f10，BA、dBA 和NBA算法的求解精度随着维度的升高明显下降，与理论值的偏离程度增大。

从收敛快慢上分析可知，DMBA 算法收敛到阈值所需的终止迭代次数最少，对于f1、f2、f7、f8、f10和f12，其终止迭代数iter近似等于最大迭代数Tmax的1/25 ；对于f3、f4和f6，其所需的iter 近似等于Tmax的1/6 ；对于f5和f11，iter 近似等于Tmax的1/3，有效减少了迭代过程，缩短算法重复执行的时间。另外，UGBA 算法在f1和f8上获得理论最优值时的终止迭代数稍高于DMBA 算法，NBA 算法在f1上的终止迭代数要高于DMBA 和UGBA 算法，其在500维和1 000 维下的iter 约占Tmax的1/2。BA 和dBA 算法对所有函数没能求解到收敛阈值，因此直到Tmax时终止迭代。

整体而言，BA 算法的求解精度与理论值有较大的偏差，在除f12外的函数上的寻优效果偏低。dBA、NBA 和UGBA 算法的求解结果优于BA 算法，这3 种算法在不同函数下的寻优性能又互有优劣，在大部分函数上的寻优结果没能达到收敛阈值，其获得的平均寻优值和标准差随着维数的增加而明显降低。DMBA 算法在除f9以外的函数上均能快速求解到收敛阈值，并且不受维度变化的影响。因此随着维数的增加，在100 维、500 维和1 000 维的测试函数上，DMBA 算法表现出比BA、dBA、NBA 和UGBA 算法更强的全局收敛能力，证明了DMBA 算法求解高维复杂函数的有效性。

Table 4 Performance comparison of 5 algorithms in dealing with 100 dimensional test functions表4 5 种算法求解100 维测试函数的性能比较

Table 5 Performance comparison of 5 algorithms in dealing with 500 dimensional test functions表5 5 种算法求解500 维测试函数的性能比较

Table 6 Performance comparison of 5 algorithms in dealing with 1000 dimensional test functions表6 5 种算法求解1 000 维测试函数的性能比较

为了进一步分析DMBA 算法在高维度下的寻优性能，本文给出5 种算法在100 维度下求解标准函数的收敛曲线，衡量算法的收敛性能，如图4～图15 所示。由于不同算法的收敛结果存在较大差异，对f2～f7和f9～f12函数曲线图的纵坐标作取对数处理，曲线在某一点处消失说明在该时期的适应值满足收敛阈值，获得理论最优值，从而终止迭代。

Fig.4 Convergence curve of f1function图4 f1函数收敛曲线

Fig.5 Convergence curve of f2function图5 f2函数收敛曲线

Fig.6 Convergence curve of f3function图6 f3函数收敛曲线

Fig.7 Convergence curve of f4function图7 f4函数收敛曲线

Fig.8 Convergence curve of f5function图8 f5函数收敛曲线

Fig.9 Convergence curve of f6function图9 f6函数收敛曲线

Fig.10 Convergence curve of f7function图10 f7函数收敛曲线

Fig.11 Convergence curve of f8function图11 f8函数收敛曲线

Fig.12 Convergence curve of f9function图12 f9函数收敛曲线

Fig.13 Convergence curve of f10function图13 f10函数收敛曲线

Fig.14 Convergence curve of f11function图14 f11函数收敛曲线

Fig.15 Convergence curve of f12function图15 f12函数收敛曲线

分析图4～图15，由于BA 算法的搜索算子具有很强的随机性，新解的位置大幅偏离全局最优，造成新解的适应值较差，开发中对最优值的扰动越来越小，易产生聚集现象而陷入局部极值，从f2～f7和f9～f12可以看出，BA 算法的寻优曲线处于停滞状态，基本上停止寻优无法跳出局部极值的束缚，寻优质量较差。dBA 算法产生新解具有选择性，利用在搜索空间中随机选择的一个较优解的信息指导其进入下一步的搜索，否则向最优解靠拢。但这种选择机制忽略了速度对位置的影响，在一定程度上降低了解的多样性，开发中采用线性递减的扰动策略，同样会使新解聚集在局部极值附近，在高维度下易造成早熟收敛的现象，因此dBA 算法的收敛曲线较平缓。NBA 算法一方面通过量子行为拓展个体的搜索范围，提高了种群的多样性；另一方面结合多普勒效应指导其产生新解，该策略没有利用个体与最优解在空间位置上距离的远近信息，不能有效地调整新解的位置，因而在单峰函数上的寻优效果较为有效，在部分复杂多峰函数如f10～f12上的求解效果较弱，但整体上的寻优性能优于BA 和dBA 算法。对于f1，NBA 算法在迭代50 次左右时获得理论最优值；对于f2，NBA 算法在迭代300 次左右时获得理论最优值；对于f3、f4、f7和f9，NBA 算法的收敛曲线的下降幅度明显优于BA 和dBA 算法。UGBA 算法引入变异开关函数，使所有个体在任何时期都有机会发生变异，突破了传统的只在算法后期对最优解进行变异的界限，具有较高的种群多样性，但忽略了对全局搜索算子的改进，依靠强大的变异机制产生仅次于DMBA 算法的收敛性能。对于f1和f8，UGBA 算法在迭代25 次左右时获得理论最优值；对于f2和f10，UGBA 算法在迭代100 次左右时获得理论最优值。DMBA 算法先根据距离的变化自适应补偿频率，并结合速度偏移机制产生更靠近最优解的新解；其次在局部搜索中引入的柯西和高斯变异策略，在最优区域分别进行大步长和小步长的精细探寻，摆脱局部极值的束缚，最终迅速收敛，提前终止迭代。从图4～图15 可明显看出，不管是求解单峰函数还是多峰函数，DMBA 算法都具有更快的收敛速度和更高的收敛精度，在大部分函数上的收敛曲线更陡峭，下降幅度更明显。对于f1、f2、f7、f8、f10和f12，DMBA算法均在迭代50 次内收敛到理论最优值；对于f3、f4和f6，DMBA 算法在迭代100 次左右时收敛到理论值；对于f5和f11，DMBA 算法在迭代150 次左右时收敛到理论值。

综上所述，实验表明对于高维度多极值的单峰和多峰函数，DMBA 算法相比其他4 种算法在求解精度和速度上均具有良好的寻优效果，体现了DMBA算法有效地平衡全局探索和局部开发的能力，验证了DMBA 算法求解高维复杂函数的优势。

5 结论

针对基本蝙蝠算法在求解高维单目标优化问题时，存在寻优精度低和难以摆脱局部极值束缚的问题，本文提出一种自适应多普勒补偿与变异选择的蝙蝠算法。首先，为了准确模拟蝙蝠受到的多普勒效应，根据蝙蝠个体距离最优个体相对远近的变化自适应补偿频率，并结合平均速度对个体速度产生的偏差，共同修正飞行方向，产生更靠近最优个体的新个体。其次，为有效解决种群前期易陷入局部极值的问题，对最优个体提出柯西和高斯变异策略，先利用柯西变异产生较大的步长，提高摆脱局部极值束缚的概率，后利用高斯变异产生较小的步长，精细搜索最优区域。最后，利用合理范围内的响度和脉冲发射率，调控算法前期执行全局探索，后期执行局部开发，并提高接受较优新解的概率，平衡探索和开发能力。从理论上分析了本文算法收敛的可行性和运算的复杂性，利用12 个标准函数在不同维度下进行仿真实验，结果表明与最近文献的算法相比，本文算法在求解高维度优化问题时能有效提高收敛精度和速度。