一种改进的自适应变异蝙蝠算法_盛孟龙

计算机技术与发展

COMPUTEＲTECHNOLOGYANDDEVELOPMENT

Vol．24No．10Oct．2014

一种改进的自适应变异蝙蝠算法

盛孟龙，贺兴时，王慧敏

（西安工程大学理学院，陕西西安710048）

摘

要：针对蝙蝠算法在解决高维复杂问题时容易陷入局部最优解和精确度不高的问题，文中提出了一种改进的蝙蝠算

引入一种交叉变换的方式更新蝙蝠群体的位置，一方面是为了提高蝙蝠算法的遍历性，另外还可法。在原算法的基础上，

以减小蝙蝠算法陷入局部最优解的可能性。模拟蝙蝠发声的音量变化，采用自适应的变换的方式改进蝙蝠算法最优解的选择模式，达到提高算法的精度和收敛速度的目的。最后通过标准的测试函数对改进后的算法进行数值模拟，结果显示，改进后的算法较为有效。

关键词：蝙蝠算法；交叉变换；Beat分布；自适应变异中图分类号：TP301．6

文献标识码：A

文章编号：1673－629X（2014）10－0131－04

doi：10．3969/j．issn．1673－629X．2014．10．031

AnImprovedAlgorithmforAdaptiveMutationBat

SHENGMeng－long，HEXing－shi，WANGHui－min

（CollegeofScience，Xi’anPolytechnicUniversity，Xi’an710048，China）

Abstract：Inviewoftheproblemwhichiseasytofallintolocaloptimalsolutionandtheaccuracyisnothighinsolvinghigh－dimensionalcomplexproblemsforbatalgorithm，proposeanimprovedalgorithmofbatinthispaper．Onthebasisoftheoriginalalgorithm，introduceonehandistoenhancethetraversesofbatalgorithm，ontheotherhandcanacrosstransformtoupdatethelocationofthebatpopulation，

reducethepossibilityoffallingintolocaloptimalsolution．Analogbatsoundvolumechanges，usinganwayofadaptivetransformtoim-provetheselectionmodeofbatalgorithmoptimalsolution，achievingthepurposeofimprovingtheaccuracyandconvergencerate．Final-ly，thestandardtestfunctionisusedtoconductthenumericalsimulationfortheimprovedalgorithm，theresultsshowthattheimprovedal-gorithmismoreeffective．

Keywords：batalgorithm；cross－conversion；Beatdistribution；adaptivemutation

0引言

1

1．1

蝙蝠算法是YangXinshe在2010年提出的［1］，灵感是来源于自然界的蝙蝠觅食的过程。和粒子群优化算法一样，蝙蝠算法也是基于群体的随机搜索机制，区别在于蝙蝠算法的随机性更强，因此蝙蝠算法具有收敛速度快、鲁棒性好的优点［2］。由于蝙蝠算法具有的概念简单、易于实现、结构简洁等优势，使该算法在多个学科和工程领域得到了广泛的应用［3－7］。为了进一步提高蝙蝠算法的精度，文中将对蝙蝠算法做进一步研究，引入一种自适应和交叉变换的方法，一方面可以提高算法的精度，另一方面可以增加群体多样性。实验结果表明效果很好。

蝙蝠的行为及蝙蝠算法

蝙蝠的速度和位置更新

蝙蝠是靠一种声呐来探测猎物，躲避障碍物的。

利用回声定位的声学原理，蝙蝠通过调整发声的频率来判断猎物的大小，根据回声的变化探测目标物的距离、方向、移动速度、大小等，从而使蝙蝠能准确无误地与进行飞行和扑食［8－9］。根据蝙蝠的这种生活习性，目标优化问题相关联，2010年由YangXinshe提出了这种蝙蝠算法。算法给出了由n只蝙蝠组成的群体在飞行过程中更新速度、位置、响度及脉冲速率的数学表述形式：

fi=fmin+（fmax－fmin）β

（1）

收稿日期：2013－11－25修回日期：2014－03－03网络出版时间：2014－07－28

基金项目：陕西省软科学基金项目（2012KＲM58）；陕西省教育自然科学基金项目（12JK0744）

作者简介：盛孟龙（1987－），男，河南驻马店人，硕士，研究方向为智能算法、元启发式算法；贺兴时，教授，研究方向为智能计算、数据挖掘的理

论与方法、概率论与数理统计等。

网络出版地址：http：//www．cnki．net/kcms/detail/61．1450．TP．20140728．1222．013．html

·132·计算机技术与发展第24卷

vti=vti－1+（xti－x*）fixti=xti－1+vti

（2）（3）

vti=εvti－1+（xti－x*）fi

态分布的随机向量。

（8）

其中，1）是一个服从正ε为学习因子；ε∈N（0，由于算法的精确度是评估算法优劣的一个重要因素，所以在算法收敛过程中，对局部最优解的搜索直接影响到算法的精确度［10］。在蝙蝠算法中，局部搜索是通过对蝙蝠的平均音量来控制的。文中使用自适应变异的依据如下［11］

xnew=xold+σ'ij·Betarandj（）

（9）

'其中，1）+τ'Nj（0，1）），σij=σij*exp（τN（0，σij

xti和vti分别表示在d维搜索空间下蝙蝠群其中，

体中第i只蝙蝠的第t代的位置和速度，i=1，2，…，n；0，1］是一个服从均匀分布的随机向量；x*表示β∈［

当前全局最优位置（解），是在所有蝙蝠搜索到的解当中，通过比较得到的位置。由于λi*fi是速度增量，可以根据具体问题的需要，固定一个因素λi（或fi），同时使用另一个因素fi（或λi）来调整速度的改变。在实现过程中，依据问题需要搜索的范围大小，令fmin=fmax=O（1）。每只蝙蝠的初始化是按照［fmin，fmax］0，

间的均匀分布随机赋给一个频率。

对于局部搜索，一旦在当前最优解中选中了一个解，则每只蝙蝠将按照随机游走的方式产生局部新解。

xnew=xold+εAt

t

t

i

取值为蝙蝠的最低音量A=0．25，N（0，1）表示均值为0、标准差为1的正态随机数，Nj（0，1）表示针对每一

'

2n和个j的不同的伪随机数，τ和τ分别设置为1槡［12］

（4）

1槡2槡n，n为迭代次数；Betarandj（）是一个服从

其中，1］是一个随机数；A=＜A＞是ε∈［－1，所有蝙蝠在同一个时间段的平均音量。

蝙蝠的速度和位置更新步骤有些类似于标准粒子群优化，粒子群优化中的fi本质上是控制粒子群体的移动范围和空间的。在一定程度上，BA可以看作是标准粒子群优化和强化的局部搜索的平衡结合，其平衡受音量和脉冲发生率的控制。1．2

蝙蝠的音量和脉冲发生率

音量A和脉冲发生率f按照以下迭代过程更新。当蝙蝠找到猎物时，音量就会降低，脉冲发生率就会增加，音量会以任意简便的值改变。蝙蝠i的音量和脉冲发生率更新公式为：

Ati+1=αAti，rti+1=r01－exp（－γt）］i［其中，α和γ为常量。对任意的0＜α＜1，有γ＞0，

Ati→0，rti→r0t→#（6）i，as

最简单的情况是令α=γ，在实现中，文中使用的是α=γ=0．95。

（5）

'

Beta分布产生的随机数。σij·Betarandj（）表示音量A

随着在搜索最优解过程中不断的变化，最大值可达到给定的上限，最小值可非常接近0，随着搜索的不断进行，对局部的搜索也更为充分，从而达到更高精确度。

通过上述分析，文中提出了一种改进的蝙蝠算法—自适应变异蝙蝠算法。假设蝙蝠种群大小为n，搜索空间的维度为D，第i只蝙蝠的位置为x（i）=（xi1，xi2，…，xiD），其中i=1，2，…，n。自适应变异蝙蝠算法的基本步骤概括如下：

Step1：初始化种群蝙蝠规模和搜索空间维数，以及第i只蝙蝠位置：x（i）=randn（1，D），i=1，2，…，n；初始化速度v（i），i=1，2，…，n；初始化脉冲发射速率Ｒ，脉冲响度A（i），脉冲频率F（i），初始适应度值fitness（i）=Z（x（i））（i=1，2，…，n），当前最优适应度值fbest和当前最优位置（解）xbest；

Step2：利用式（2）～（4）产生新解；

Step3：判断是否满足变异条件rand＞Ｒ，如满足，则通过式（9）更新新解的位置xnew；否则转至Step4；

Step4：判断新解的值是否满足Znew≤fitness（i），如果满足，转至Step5，如果满足rand＜Ｒ，更新当前适应度值为新的位置xnew，否则转至Step5；

Step5：比较新适应度值和当前最优解适应度值是否满足fbest≤Znew，如果满足，则更新当前最优适应度值以及最优位置（解），否则转至Setp2；

Setp6：更新当前最优位置（解）x*，以及对应参数；判断是否满足终止条件，满足则返回Step2，否则算法结束，输出最优值。

2改进的蝙蝠算法（ABA）

为解决蝙蝠算法在高维问题上的弱势，引入一种

交叉变换的方式，影响蝙蝠的位置更新，即将式（7）中的均匀分布的随机向量β写成一个服从Beta分布的随机向量βi∈［0，1］，如此式（1）就变成了式（7）：

fi=fmin+（fmax－fmin）βi

（7）

Beta分布覆盖率包含了从均匀分布到正态分布及各种不对称的分布，是常见分布中少数取值在有限区1）的机率模式，具有间的分布，可用来当作取值在（0，广泛的应用前景和普适性。

为了使蝙蝠算法的位置更新更为灵活多样，将算法的速度更新公式变成以下形式：

3

3．1

实验设置及结果分析

测试函数

文中采用了通常进行优化算法实验的Benchmark

第10期盛孟龙等：一种改进的自适应变异蝙蝠算法·133·

函数进行实验。各函数公式如表1所示，所有函数都有相同的全局最小值0。其中Ackley和Griewank为多峰函数，在高维度的情况下，这两个函数是测试算法能否全局收敛的最好工具；Ｒonsebrock是非凸的病态函

表1

函数名称Ackley

数学表达式

数，以上三个均为极难找到全局最优解的函数；Sphere为单峰函数，是许多单峰函数以及一般优化函数代表，很容易找到全局最优解。

标准测试函数

维数

搜索空间（－32．758，32．758）

最优点位置最优值点（0，0）

0

f（x）=－20exp（－0．2

槡1

n

∑x2i）－exp（

1n

n

n1n

cos（2πxi））∑1xii槡n

+20+e

30

Griewankf（x）=

1

x2i－4000∑i=1

cos（∏i=1

2

）+130（－600，600）（0，0）0

ＲonsebrockSphere

f（x）=

［100（x2i∑i=1

n－1

－xi+1）x2i∑i=1

n－1

+（xi－1）2］3030

（－5，10）（－5．12，5．12）

（1，1，…，1）（0，0，…，0）

00

f（x）=

3．2实验结果分析

为了验证改进算法的有效性，文中采用了IPSO算

Ackley函数是指数函数叠加上适度放大的余弦而得到的连续型实验函数，其特征是一个几乎平坦的区域由余弦波调制形成一个个孔或峰，从而使曲面起伏因为一个严格的局不平。这个函数的搜索十分复杂，

部最优化算法在爬山过程中不可避免地要落入局部最优的陷阱，而扫描较大领域就能越过干扰的山谷，逐步达到较好的最优点。从图1中可以看出，对于Ackley函数来说，ABA整体上在整个搜索过程中，蝙蝠群体

CS0．34

ABA0．6

法［13］和保证全局收敛的CS算法［14］，以及文中改进的算法与原算法进行实验对比和分析。运行环境为Win7x64，Intel（Ｒ）P6100@2．00GHzMatlab2013，每分个函数在30维的情况下最大迭代次数为4000次，别运行50次。具体实验结果比较见表2。

表2

测试函数Ackley

指标达优率最优值达优率最优值达优率最优值达优率最优值

实验结果对比

BA0．117．8830．179．9020．0523．781

IPSO0．280．08420．30．01930．50．14341

收敛速度相对来说也较好，因的个体质量较优于CS，

为ABA中种群个体的交叉变异，以及CS中Levy飞行的特性，使得群体的多样性更好，搜索所覆盖的区域也更广。对于Ackley函数这种小范围内的多峰来说，使得这两种算法遇到的障碍也较小，从而能够达到较理想的精度值；而BA和IPSO的上述优势则不明显，对于该类函数不太理想。

1．57E－117．08E－140．3600．580．14971

0．8600．240．67651

Griewank

Ｒonsebrock

Sphere

9．73E－045．37E－022．18E－062．05E－08

随机选取函数运行过程中的图像如图1～图4所示。

图2Griewank函数

Griewank函数存在许多局部极小点，极小点的数目与问题的维数有关，全局最小值0在（0，0，…，0）处可以获得，此函数是典型的非线性多模态函数，具有广

图1

Ackley函数

泛的搜索空间，通常被认为是优化算法很难处理的复

·134·计算机技术与发展第24卷

杂多模态问题。然而从图2中可以看出，ABA和CS是相对出色的，分别在2500次和3300次时已经达到了全局最优。虽然两种算法在大概200到800次的时候可能会陷入局部最优，但是蝙蝠算法的自适应性使得蝙蝠群体很快避开了局部最优，解决了BA不能摆脱局部最优的缺点。IPSO虽然在100次以内时表现较好，但是在后期的种群进化中表现的不是太好，收敛速度较慢。

4结束语

针对BA算法在解决高维复杂函数的优化问题的

劣势，文中在原蝙蝠算法的基础上提出了一种自适应变异的蝙蝠算法。该算法提高了蝙蝠群体的多样性，强化算法在搜索空间中的搜索能力，并且对算法在适当的条件下进行变异操作，使蝙蝠进入其他新的领域进行搜索，跳出局部最优，算法的优化性能较好。另外，该算法也适合一般的函数优化。如何对BA算法与其他方法相结合，并用之解决实际应用问题，将是下一步的研究工作。

参考文献：

［1］

YangXinshe．Anewmetaheuristicbat－inspiredalgorithm［M］//Natureinspiredcooperativestrategiesforoptimiza-2010．tion．Berlin：Springer，

［2］YangXS，GandomiAH．Batalgorithm：anovelapproachfor

globalengineeringoptimization［J］．EngineeringComputa-tions，2012，29（5）：464－483．［3］李枝勇，马

良，张惠珍．0－1规划问题的元胞蝙蝠算法

图3Ｒonsebrock函数

［J］．计算机应用研究，2013，30（10）：2903－2906．

［4］盛晓华，叶春明．蝙蝠算法在PFSP调度问题中的应用研究

［J］．工业工程，2013，16（1）：119－124．

［5］张宇楠，刘付永．一种改进的变步长自适应蝙蝠算法及其

应用［J］．广西民族大学学报（自然科学版），2013，19（2）：51－54．

［6］韩福霞，刘宏志．基于蝙蝠算法的信息工程监理多目标优

化研究［J］．现代计算机：上下旬，2013（13）：3－6．

［7］刘长平，叶春明．具有混沌搜索策略的蝙蝠优化算法及性

能仿真［J］．系统仿真学报，2013，25（6）：1183－1188．［8］GrinnellAD．Hearinginbats：anoverview［M］//Hearingby

bats．NewYork：Springer，1995．

［9］MossCF，SinhaSＲ．Neurobiologyofecholocationinbats

［J］．CurrentOpinioninNeurobiology，2003，13（6）：751－758．

［10］YangXinshe．Batalgorithmformulti－objectiveoptimisation

［J］．InternationalJournalofBio－inspiredComputation，2011，3（5）：267－274．

［11］PantM，ThangarajＲ，AbrahamA．Particleswarmoptimization

C］//Procof19thinternationalwork-usingadaptivemutation［

shopondatabaseandexpertsystemsapplication．Turin：IEEE，2008：519－523．

［12］KennedyJ．ＲeviewofEngelbrecht＇sfundamentalsofcomputa-tionalswarmintelligence［J］．GeneticProgrammingandEvolvableMachines，2007，8（1）：107－109．

Ｒonsebrock函数的每个等高线大致呈抛物线形，其全局最小值位于抛物线形的山谷中。很容易找到这个山谷，但由于山谷内的值变化不大，要找到全局的最小值相当困难。从图3中可以看出，整体来说IPSO相对较优。BA和ABA在400次左右都出现了拐点，后之后趋于者在2600次和3000次左右也出现了拐点，平稳。由此可以得出ABA虽然有所突破，但还是不能很快地解决问题；另外两种算法的表现类似，在1400左右向较优的方向突破，而CS则相对落后。严格地说，以上特点是由函数的特性决定的，而这四种函数则是不偏好解决该类优化问题。

图4Sphere函数

［13］黄福员．一种改进的动量粒子群算法及实验分析［J］．计算

机应用与软件，2009，26（10）：57－59．［14］王

凡，贺兴时，王

燕，等．基于CS算法的Markov模型

及收敛性分析［J］．计算机工程，2012，38（11）：180－182．

从图4可以看出，类似Sphere这样的单峰函数，不管是低维还是高维的，大部分算法都能实现有效的优化效果，只不过有的精度相对高而已，比如ABA和CS。