蝙蝠算法的一种改进方法

魏三强，张 超

(1.宿州职业技术学院计算机信息系，安徽 宿州 234101；2.中国矿业大学信息与控制工程学院，江苏 徐州 221116)

蝙蝠算法的一种改进方法

魏三强1，2，张 超1

(1.宿州职业技术学院计算机信息系，安徽 宿州 234101；2.中国矿业大学信息与控制工程学院，江苏 徐州 221116)

针对蝙蝠算法在进行局部搜索时，易使算法陷入局部极值的束缚，导致算法收敛精度不高的缺陷，提出了使用t-分布对局部搜索时的最优解进行变异操作.为最优解各维度增加t分布型随机扰动项，选取7个经典测试函数做仿真实验.实验结果表明：改进的蝙蝠算法在收敛精度和速度上有显著提升，说明通过对最优解实施t-分布扰动能够使算法摆脱局部极值的束缚，显著提高收敛精度.

蝙蝠算法；t分布；收敛精度；群体多样性；智能算法

0 引言

X.S.Yang[1]根据自然界的蝙蝠能够利用其发出声波的回声，从而准确定位猎物位置的特征，于2010年提出了一种群智能优化算法——蝙蝠算法(Bat Algorithm，BA).该算法能模拟蝙蝠在飞行或捕捉猎物时的回声定位行为，每个蝙蝠通过改变声波的频率、音响强度、脉冲发射率来控制其飞行位置和速度，追随最优蝙蝠在解空间搜索最优解.文献[1-5]通过大量数值实验得出蝙蝠算法在寻找最优解的成功率上优于粒子群算法、和声算法及遗传算法.鉴于此，近年来蝙蝠算法在神经网络优化[6]、资源调配[7]等领域已被应用，但蝙蝠算法也存在收敛精度不高、易陷入局部极值点等缺陷[8]，为此，学者们对蝙蝠算法进行了相关的改进工作.改进的策略主要集中在蝙蝠算法的两个主要过程：个体飞行和局部搜索.在个体飞行方面，刘长平等[9]提出使用Levy飞行取代原算法的速度和位置更新方式；谢健等[10]在原算法速度和位置更新方式上，对组成蝙蝠速度和位置的各维度添加Levy分布变异.在局部搜索方面，李雅梅等[11]引入Powell机制提高蝙蝠算法的局部搜索能力；刘万军等[12]对最优个体进行SQP局部搜索，提高蝙蝠算法的局部深度搜索能力；陈梅雯等[13]使用随机蝙蝠来引导个体飞行和局部搜索，以提高种群多样性；臧慧芳等[14]通过引入早熟判断机制，将差分进化算法思想融入到蝙蝠算法中.这些改进策略在不同程度上提升了蝙蝠算法的收敛精度.

蝙蝠算法在局部搜索时采用随机游走方式，通过对组成最优解的各维度增加随机数进行扰动，在最优蝙蝠个体附近生成局部新解.当局部搜索条件成立，算法进行局部搜索时，容易被局部极值点吸引，导致算法不一定收敛到局部最优，并且，随着迭代进程的推进，当到达中后期阶段时，蝙蝠个体集中在局部最优解附近，致使种群多样性消耗过快，易陷入局部最优，从而导致算法不能够收敛到全局最优解，收敛精度不高.本文提出使用学生t-分布(简称t分布)变异代替原算法的局部新解生成方式，即在最优解best的基础上增加t分布型随机扰动项best⊗t(Iteration)，对最优解各维度进行基于迭代次数Iteration为t分布自由度的自适应变异.选用7个经典测试函数做仿真实验，以验证本文提出改进策略的有效性.

1 蝙蝠算法

1.1 蝙蝠算法基本原理

蝙蝠算法模拟蝙蝠的回声定位行为，通过改变声波的频率、音响强度、脉冲发射率来控制其飞行位置和速度，追随最优蝙蝠在解空间搜索最优解.蝙蝠算法可以归纳出如下7个步骤：

(1) 初始化参数.设置种群规模为sizepop、最大迭代次数为maxgen(或目标精度)、脉冲频率范围为[fminfmax]、最大脉冲频度为r0、最大脉冲音强为A、音强衰减系数为α、频度增加系数为γ、搜索变量的维度为d.

(2) 蝙蝠种群初始化.在搜索范围内随机初始化蝙蝠个体位置xi(i=1，…，d)，找出当前搜索中最佳蝙蝠位置x*.

(3) 种群迭代.蝙蝠个体飞行按照

(1)

对脉冲频率fi，蝙蝠t时刻的速度vi，位置xi进行更新.其中x*是当前搜索全局最优解，rand∈[0，1]的随机数.

(4) 生成随机数rand.如果rand>ri，选择最优蝙蝠个体，按照

xnew=xold+ε×At，

(2)

(5)再次生成随机数rand.如果rand

(3)

增大ri和减小Ai的值.其中t为当前迭代次数，α和γ为常量.

(6) 对蝙蝠种群的适应度值进行排序.记录当前最优蝙蝠位置及其适应度值.

(7) 重复执行步骤(3)—(6).进入迭代寻优，直至满足最大迭代次数或设定精度停止算法，输出全局最优值及对应蝙蝠位置.

1.2 改进的蝙蝠算法

蝙蝠算法在局部搜索时采用随机游走方式，通过对组成最优解的各维度增加随机数进行扰动，在最优蝙蝠个体附近生成局部新解，当算法进行局部搜索靠近极值点时，容易被极值点吸引，致使种群多样性消耗过快，导致算法收敛精度不高.本文使用t分布变异策略对原算法的局部搜索方式进行改进.

1.2.1 t分布

t分布是英国统计学家Gosset于1908年以笔名“Student”提出的，因此称学生氏t分布，简称t分布.t分布曲线是左右对称的，围绕平均数向两侧递降.t分布受自由度参数df=n-1的制约，每个自由度都有一条t分布曲线.和正态分布相比，t分布的顶部偏低，尾部偏高.自由度df越小，t分布曲线越低平；自由度df越大，t分布曲线越接近正态分布.柯西分布和高斯分布是t分布的两个边界特例.当t分布自由度df=1时，t分布曲线和柯西分布曲线重合；当自由度df>30时，t分布曲线开始与正态分布曲线接近；当df∞时，t分布曲线和高斯分布曲线重合.

1.2.2 自适应t分布变异蝙蝠算法

由于t分布随着自由度的增加能够在柯西分布和高斯分布之间转换，柯西分布变异具有良好的全局开发能力，而高斯变异具有稳定的局部搜索能力.因此，文献[15]将t分布应用到人工鱼群算法的改进中，提出将算法的迭代次数作为t分布的自由度参数，对除了最优鱼之外的非最优鱼进行t分布变异.文献[16]将t分布引入到蝙蝠算法的改进中，对除了最优蝙蝠之外的非最优蝙蝠进行t分布变异.从文献[15-16]的结果看出，经过对非最优解进行t分布变异后，提高了算法的收敛精度和速度.本文使用

xnew=xold+xold⊗t(Iteration)

(4)

代替公式(2)，即提出使用t分布对最优解进行变异，进行局部搜索生成新解的方式.其中⊗为点乘符号，t(Iteration)是以算法的迭代次数Iteration为自由度的t分布.

改进策略在蝙蝠算法迭代初期，Iteration值较小，通过对最优解进行近似柯西分布变异能够产生远离最优解的下一代点，提高种群多样性，避免算法过早早熟，陷入局部最优.算法运行后期，Iteration的取值较大，对最优解进行t分布变异近似高斯分布，具有较好的局部搜索能力，能够提高算法的收敛精度.

改进的算法记为TBA.改进的算法使用公式(4)进行局部搜索，其执行流程与原算法一致.

2 实验与结果分析

2.1 实验方案设计和部署

本文从两方面对改进的算法性能进行仿真实验：(1)对BA和TBA做对比实验；(2)将TBA与其他改进BA的结果进行比较.

为了便于与其他改进BA的比较，本文选用7个测试函数，使用比较苛刻的参数设置，函数的表达式、变量范围、理论极值和目标精度见表1.实验在主频2.50 GHz的CPU、2 GB内存、32位Win7操作系统的计算机上使用Matlab R2012a编程实现仿真程序.

算法参数设置：蝙蝠种群规模sizepop=20，迭代次数maxgen=1 000，脉冲频率范围为[0，2]，音强衰减系数α=0.95，频度增加系数γ=0.05，每个蝙蝠的脉冲频度ri∈[0，1]，脉冲音强Ai∈[1，2].

表1 测试函数的参数

2.2 实验结果分析与比较

2.2.1 TBA与BA性能比较分析

对表1中的7个测试函数按照指定维度和变量范围，使用BA和TBA仿真程序，分别随机独立连续运行20次.固定迭代次数下的实验结果见表2.由表2可见，改进的蝙蝠算法TBA在衡量算法性能的4个指标上均明显优于BA，收敛精度显著提高.图1为TBA和BA的适应度收敛进化曲线(为了便于观察，对Michalewicz函数除外的其他6个函数的适应度值取10为底的对数处理).从图1中可以看出，TBA较BA收敛速度有大幅提升.函数f1，f5，f6和f7理论极值为0， TBA在这4个函数上的适应度进化曲线出现间断，表明已经找到该函数的理论极值0，因为对数的真数为0时不显示.

表2 BA和TBA的实验结果

图1 BA和TBA的适应度值进化收敛趋势比较

表3为固定精度下的BA算法和TBA算法的平均迭代次数和成功率.数值采用 “平均迭代次数/成功率”表示，1代表百分之百成功.从表3中可知，BA在预设精度下，均不能收敛到固定精度，而TBA在比较苛刻的精度设定下，均能百分百成功收敛到固定精度.从而说明TBA有效地提高了算法的收敛速度.

表3 固定精度下平均迭代次数与成功率

2.2.2 TBA与其他BA改进算法性能比较分析

为了将本文提出的改进算法与其他蝙蝠改进算法进行比较，选取近两年改进效果较好的4个改进算法：IBA[13]、CDEBA[14]、TMBA[16]、VBA[17].文献[13]中f1，f2，f3，f4，f5，f6，f7函数变量范围分别为±600，±15，[-5，10]，[0，π]，±600，±32.768，±15，种群规模sizepop=20，maxgen=3 000；文献[14]中f1，f5，f6，f7函数变量范围分别为±100，±600，±32，±5.12，种群规模sizepop=50，maxgen=200；文献[16]中f1，f3，f5，f6，f7函数变量范围分别为±5.12，[-5，10]，±600，[-15，30]，±15，种群规模sizepop=50，maxgen=1 000；文献[17]中f1，f4，f5，f6函数变量范围分别为±5.12，[0，π]，±600，±32，种群规模sizepop=50，maxgen=200.

TBA是在种群规模、迭代次数、测试函数变量范围等指标比较苛刻的约束设定下进行的仿真.对比结果及对比算法的搜索空间维度见表4.从表4可知，除了Rosenbrock 函数外，本文的TBA适应度平均值明显优于其他算法，并在f1，f5，f6，f74个函数上均能收敛到理论极值0.文献[13] 提出的IBA在Rosenbrock 函数上的收敛精度优于TBA，但在其他6个函数收敛精度上远低于本文提出的TBA.文献[14]提出的CDEBA在搜索维度为2的情况下，能够收敛到Griewank函数的理论极值0，但随着维度的增加收敛精度明显下降.

表4 TBA(30维)与其他蝙蝠改进算法优化平均值比较

综上所述，本文提出的对原算法局部搜索使用的随机游走方式进行自适应t分布变异能够有效摆脱局部极值的束缚，避免算法“早熟”，在迭代早期近似柯西分布的t分布变异拓展了种群的多样性，从而提高了算法的收敛精度和速度.

3 结论

对蝙蝠算法进行局部搜索时的最优解进行t-分布变异操作后的改进算法，在Sphere、Griewank、Ackley、Rastrigin函数上均能收敛到函数的理论极值0，在Zakharov、Michalewicz函数上的收敛精度也明显优于其他算法.结果表明，通过过对最优解进行t-分布扰动能够使算法摆脱局部极值的束缚，显著提高收敛精度.

[1] YANG X S.A new metaheuristic bat-inspired algorithm[J].Nature Inspired Cooperative Strategies for Optimization(NICSO 2010)，2010，284：65-74.

[2] YANG X S.Bat algorithm for multi-objective optimization[J].Int J Bio-Inspired Computation，2011，3(5)：267-274.

[3] YANG X S，GANDOMI A H.Bat algorithm：a novel approach for global engineering optimization[J].Engineering Computation，2012，29(5)：267-289.

[4] 李煜，马良.新型全局优化蝙蝠算法[J].计算机科学，2013，40(9)：225-229.

[5] 刘长平，叶春明，刘满成.来自大自然的寻优策略：像蝙蝠一样感知[J].计算机应用研究，2013，30(5)：1320-1322，1356.

[6] 孔令春，孙琼琼，杨照峰.蝙蝠算法优化极限学习机的电力负荷预测模型[J].辽宁工程技术大学学报(自然科学版)，2016，35(1)：89-92.

[7] 刘长平，陈伟达.求解零等待流水车间调度问题的改进蝙蝠算法[J].数学的实践与认识，2016，46(11)：38-46.

[8] 尚俊娜，刘春菊，岳克强，等.具有自学习能力的变异蝙蝠优化算法及性能仿真[J].系统仿真学报，2017，29(2)：301-308.

[9] 刘长平，叶春明.具有Lévy飞行特征的蝙蝠算法[J].智能系统学报，2013，8(3)：240-246.

[10] 谢健，周永权，陈欢.一种基于Lévy飞行轨迹的蝙蝠算法[J].模式识别与人工智能，2013，26(9)：829-837.

[11] 李雅梅，曹益华.基于Powell机制的改进蝙蝠算法[J].微电子学与计算机，2015，32(3)：73-76，80.

[12] 刘万军，杨笑，曲海成.基于SQP局部搜索的蝙蝠优化算法[J].计算机工程与应用，2016，52(15)：183-189.

[13] 陈梅雯，钟一文，王李进，等.一种求解多维全局优化问题的改进蝙蝠算法[J].小型微型计算机系统，2015，36(12)：2749-2753.

[14] 臧慧芳，高岳林.基于混沌和差分进化的混合蝙蝠算法[J].兰州理工大学学报，2016，42(5)：90-94.

[15] 王波.基于自适应t分布混合变异的人工鱼群算法[J].计算机工程与科学，2013，35(4)：120-124.

[16] 常青，贺兴时.基于t分布变异的蝙蝠算法[J].西安工程大学学报，2015，29(5)：647-653.

[17] 薛威力，贺兴时，杨新社.蝙蝠算法的一种改进[J].哈尔滨商业大学学报(自然科学版)，2016，32(6)：706-712.

Animprovedmethodforbatalgorithm

WEI San-qiang1，2，ZHANG Chao1

(1.Department of Computer and Information，Suzhou Vocational and Technological College，Suzhou 234101，China；(2.School of Information and Control Engineering，China University of Mining and Technology，Xuzhou 221116，China)

When the bat algorithm performs local search，random numbers are added to the optimal solution of each dimension.This mechanism makes the bat algorithm fall into local extremum，which leads to the low precision of the algorithm.In view of the shortcomings of the bat algorithm.This paper proposes a modified algorithm，which employed a student’st-distribution mutation operator to disturb the optimal solution of each dimension.The experimental results of seven function show that the modified algorithm improves the convergence precision and speed.Therefore，the modified algorithm whicht-distribution mutation operator is added can improve the abilities of seeking the global excellent result and evolution speed.

bat algorithm；student’st-distribution；convergence precision；population diversity；intelligence algorithm

1000-1832(2017)04-0076-06

10.16163/j.cnki.22-1123/n.2017.04.015

2017-04-12

国家自然科学基金资助项目(61572036)；安徽省高校自然科学研究重点项目(KJ2016A781).

魏三强(1980—)，男，副教授，博士研究生，主要从事智能算法、云计算研究.

TP 301.6学科代码520·10

A

(责任编辑：石绍庆)