第42卷第3期 2017年6月
广西大学学报（自然科学版）
Journal of Guangxi U niversity(Nat Sci E d)
V o l.42 No.3
June2017
d o i:10. 13624/jki.issn. 1001-7445. 2017. 1137
基于遗传算法的蝙蝠优化算法研究
翁健高，白琳，易向阳，李道丰
(广西大学计算机与电子信息学院，广西南宁530004)
摘要：针对基本蝙蝠算法后期收敛速度不够快、早熟、寻优精度不髙、容易出现局部最优问题等情况，提出与遗 传算法相结合的优化蝙蝠算法（G A B A)。该优化算法嵌人了竞争机制以及遗传算法，利用遗传算法具有的全 局搜索性能，让种进化时具有更丰富的多样性，在解决算法早熟问题的同时，提髙了
局部广度搜索性能，避 免产生局部最优问题。M a tla b环境下的仿真实验结果表明：与基本B A算法对比，改进后算法（G A B A)在收 敛速度及精度上均有明显提髙，特别在髙维函数上的搜索能力更为明显，可针对工程应用过程中出现的髙维 多极值复杂函数进行优化。
关键词：蝙蝠算法；选择；交叉；变异因子；竟争机制；收敛速度；遗传算法
中图分类号:TP301. 6文献标识码:A文章编号:1001-7445(2017)03-1137鄄08
R e s e a r c h o n o p t i m i z a t i o n o f b a t a l g o r i t h m b a s e d
o n genetic a l g o r i t h m
WENG Jian-gao，BAI Ling，YI Xiang-yang，LI Dao-feng
(School of Computer，Electronics and Im form ation，Guangxi U niversity，Nanning530004, China)
A b s t r a c t:I n o rd e r to so lve th e d is a d v a n ta g e s of b a s ic b a t-in s p ire d a lg o r ith m，su ch as p re m a tu re
c o n v e rg e n c e，s lo w e r c o n v e rg e n c e spee
d a n d lo c a l o p tim a l s o lu tio n，a n o p tim iz
e d b a t-in s p ire d
a lg o rith m
b ased o n g e n e ti
c a lg o rith m is p ro p o s e d.T h e a lg o rith m ta ke s a
d va nta g
e o
f
g lo b a l search
p e rfo rm a n c e of th e g e n e tic a lg o rith m a n d th e c o m p e titiv e m e c h a n is m to im p ro v e th e p e rfo rm a n c e of th e b a t-in s p ire d b ased a lg o rith m.I t in s u re s g re a te r d iv e rs ity of th e e v o lu tio n p ro ce ss a n d solves p re m a tu re c o n v e rg e n c e，w h ile im p ro v in g lo c
a l se a rch p e rfo rm a n c e a n d a v o id in g lo c a l o p tim a l p ro b le m.T h e M A T L A B s im u la tio n re s u lts show th a t th e p re s e n te d a lg o rith m has b e tte r p e rfo rm a n c e in c o n v e rg e n c e speed a n d p re c is io n c o m p a re d w ith th e b a s ic b a t-in s p ire d a lg o r ith m，e s p e c ia lly in th e
sea rch c a p a b ility in th e h ig h d im e n s io n a l d a ta，w h ic h is h e lp fu l fo r o p tim iz a tio n of h ig h d im e n s io n a l
a n d m u lti-e x tre m u m c o m p le x fu n c tio n s in e n g in e e rin g a p p lic a tio n s.
K e y w o r d s:b a ts a lg o r ith m；s e le c tio n；c ro s s o v e r；m u ta tio n fa c to r；c o m p e titio n m e c h a n is m；c o n v e r
g ence r a te;g e n e tic a lg o rith m
收稿日期:2017-02-25 ；修订日期:2017-03-29
基金项目：国家自然科学基金资助项目（61362010 )；广西自然科学基金项目（2011GXNSFA018152)
通讯作者：李道丰（1974—），男，广西上林人，广西大学副教授;E-m a il:ld f_0123@163。
引文格式：翁健高，白琳，易向阳，等.基于遗传算法的蝙蝠优化算法研究[J].广西大学学报（自然科学版），2017, 42(3) :1137-1144.
1138广西大学学报（自然科学版)第42卷
0引言
蝙蝠算法B A(b a t a lo g rith m)在2010年被提出，提出者是X in-S h e Y a n g，其针对大自然里蝙蝠的回声定位搜索目标进行了模拟，并以此而研发出了智能优化算法，该算法具有模型简单，参数配置少，收敛速度快等优点，在多目标优化，神经网络优化，复杂多维函数寻优[13] ,0-1规划和分类[4]等问题中，已获得成功应用，已经是智能计算领域里极为受关注的研究内容。不仅如此，该算法和别的智算法相同，会有迭代后期多样性差，并且很容易产生早熟、局部最优等问题，而很多研究人员都根据以上问题进行了探讨分析，以便对算法进行完善。刘长平等[5]提出了优化蝙蝠局部搜索性能的算法，即利用逻辑自映射函数来形成混沌序列，以便针对蝙蝠算法里的优秀个体进行相应优化处理，在动态搜索空间中能够提高算法的收敛速度；屈迟文等[6]提出了与入侵杂草生长繁殖局部搜索相结合的优化算法，在蝙蝠算法里新增了入侵杂草算法中的竞争机制以及空间扩散和生长繁殖等方法，通过对杂草空间扩散算子标准差进行相应调整，提高全局搜索性能，并且能够有效增强局部搜索性能，其稳定性及精度都有了很大提升；肖辉辉等[7]提出了与差分进化算法相结合的蝙蝠算法，在蝙蝠算法中应用其变异、选择、交叉
机制，让蝙蝠算法也具备变异性能，以丰富蝙蝠算法多样性；孙文捷等[8]通过F u c h映射，针对蝙蝠频率变化区间、局部最优解领域做了相应的混沌遍历搜索，根据其频率产生变化的情况，让蝙蝠速度得到整体改变，蝙蝠最初发射的脉冲速率较低的阶段，通过F u c h映射来完成搜索任务，可以避免局部最优的问题产生；郑云水等[9]提出了结合高斯变异混合蛙跳蝙蝠算法（S F L B A W G M)，其主要是针对复杂函数问题进行求解，通过混合蛙跳算法（S F L A)更新子代，实现蝙蝠个体的局部深入搜索任务，可以让S F L-B A W G M不但具有B A的全局搜索性能还有较快的收敛性能，让算法中局部深度搜索的能力得到了增强，同时在算法和变异条件相符的情况下，可针对当下全局最优个体进行高斯变异；岳小雪等[10]研究出具备了自适应变异机制的优化蝙蝠算法，通过K-m e a n s聚类初始化蝙蝠种，确保种能够均匀分布在搜索空间里，再按照迭代次数自适应变化概率进行高斯变异操作，可以丰富种多样性，并且能够有效避免局部最优的问题，使得蝙蝠算法整体得到了优化。
笔者针对前人所提出的蝙蝠优化算法进行了分析，并根据算法中存在的不足之处，提出了结合遗传算法的优化蝙蝠算法，以提高基本蝙蝠算法的局部搜索能力，使其能够适用于工程应用中高维多极值复杂函数的优化问题。
1蝙蝠算法的原理
1.1蝙蝠算法
蝙蝠在寻以及捕食的时候都是通过回声定位系统完成的，利用超声波脉冲频率结合音强，能够在可见度极低的条件下准确捕食，并能准确避开障碍物。蝙蝠觅食的过程中，其超声波脉冲大约为10〜20个/s、音强110 d B/s，而且其发射声波频率f在25〜100 k H z范围内，当蝙蝠逼近猎物时发出的声波频率比距离猎物较远时高2 ~4倍。脉冲音强最大是在开始搜索食物的时候，在与目标逐渐趋近的过程中就逐渐下降，脉冲频率则开始提高。蝙蝠利用发出与回声接收所经过的时间，明确目标距离以及位置和目标移动速度等，在脉冲频率比较高的情况下，对于目标定位更有利，脉冲音强高，对于搜索距离较大的目标有利。
蝙蝠算法原理即运用蝙蝠的搜索性能来寻空间个体，可对其在复杂环境中的目标搜索过程进行模拟，以解决相关问题[6]。
B A算法的具体步骤如下：
S te p 1：参数初始化：迭代次数最大值N_i t e r，着，表示搜索精度，而搜索的种规模为n，与之对应的脉冲频率范围是[Q mill，Qrnax]，最大脉冲音强A0，最大脉冲频度r0。
S te p 2：初始化蝙蝠位置毛(i= 1,2,3….n)，寻目前种里最优蝙蝠个体X*。
S te p 3：种迭代的时候，根据式（1)〜式(3)更新其空间位置X,、脉冲频率认，飞行速度V，等。
南宁电子科技广场第3期 翁健髙等：基于遗传算法的蝙蝠优化算法研究 1139
Q i= Q m i n+ (K m i J x r a n d,⑴
V：= V："'+( V：-X*)x Q i,(2)
X：= X-'+V i,(3)其中：V：、Vt-l、X:、X:-1即蝙蝠个体：分别处于：次迭代及：-1次迭代情况下的空间位置、飞行速度;X*表
示当前全局最优位置;Q：表示蝙蝠个体：对猎物进行搜索时的脉冲频率,Q mill臆Q：臆Q_。
S te p 4 ：可得到随机数r a n d l，如果r a n d l>r0，那么就通过式(4)完成局部搜索，并将目前位置信息进行有效更新。
X new(：) =X*+ 0.01X ra n d re(1,d),(4)其中X*表示当前最优解,r a n d n为产生均值为0，方差滓2= 1，标准差滓=1的正态分布的随机变量,d为 蝙蝠种的维数。
S te p 5：生成随机数rand2。在rand2<A0的情况下，同时蝙蝠所在的位置有了变化，那么表明该解有效。
S te p6：根据适应度值来评估蝙蝠体，并对现在最优蝙蝠个体的位置信息和适应度进行记录。
S te p 7：然后迭代寻优，重复第三个步骤，在达到最大迭代次数N_i t e r或是到与精度着1相符的个体，即可停止，进行下一步操作。
S te p8：终止算法，得到最优函数值和与之对应的蝙蝠个体位置信息。
1.2基本蝙蝠算法易陷局部最优分析
从式(2)和式(3)来看，算法进行迭代的时候，其种易聚拢于最优蝙蝠个体方向，如果X：聚集位置处于目前最优个体X*位置，那么蝙蝠位置的更新速度就会降低，并且逐渐停止更新，导致蝙蝠的寻优停止，即产生了局部最优问题，此时，蝙蝠会在相应区域过度遍历，就无法跳脱原来的搜索区域，导致种多样性受到影响，从而影响了蝙蝠的进化，使得基本蝙蝠算法容易陷入早熟现象，即使在算法中对脉冲频度和音响参数进行更新，早熟问题的优化并不明显，其实大部分优化函数位于全局最优点周边本身能够搜索到大量局部最优点，通过原来的蝙蝠算法，就会导致局部最优的问题产生，使得算法寻优精度下降，尤其是较为复杂的函数，基本蝙蝠算法有时很难达到求解问题的要求。
2基于遗传算法的优化蝙蝠算法
2.1算法改进的策略
基本蝙蝠算法（B A)通过式(2)和式(3)可对蝙蝠个体的速度以及方向进行对应调整，而且优化了
算法收敛速度，基本蝙蝠算法进化后期，蝙蝠个体逐渐向最优蝙蝠聚拢，蝙蝠种全部飞到相同区域中，尤其是高维搜索里这种现象更为明显，导致寻优种多样性不足，产生了局部最优问题，降低了收敛精度。遗传算法具有自组织、自适应和自学习的随机全局搜索、优化以及不依赖具体问题和潜在的并行操作的特点，因此在工程应用过程中常被用于非线性钢结构模糊控制和带模糊时间窗冷链配送等问题[1112]。针对基本蝙蝠算法存在的后期收敛速度不够快、早熟、寻优精度不高、容易出现局部最优问题等情况，本文结合了遗传算法中的相关优势，对基本蝙蝠算法进行改进。运用遗传算法的变异、交叉、选择机制，部分蝙蝠个体在进行局部搜索时采用遗传算法和式(4)的随机产生的后代相竞争方式产生，以 此增加蝙蝠种的多样性，提高算法的全局随机搜索能力，让蝙蝠种模拟自然界中自然选择的方法产生后代，得到更加适应环境的最优后代，从而到问题的全局最优解。
在基本蝙蝠算法中，蝙蝠种进行局部搜索时，一般是通过当前的最优值作随机变化进行子代的产生，而本算法在种局部搜索时，采用遗传算法产生的最好子代与基本蝙蝠算法产生的子代进行再竞争的方法，让算法在后期依然能够具备丰富的种多样性，解决了早熟问题，避免局部最优出现。在进行遗传算法操作时，将当前蝙蝠种及适应度值作为遗传算法的初始种和初始适应度值，初始种按照适应度，分别进行选择、交叉、变异，以形成子代，通过离差的方法选取与全局最优值差异最小的子代和基本蝙蝠算法的随机生成子代分别计算适应度值并比较，适应度值小的子代作为蝙蝠局部搜索的备选
1140广西大学学报（自然科学版)第42卷
蝙蝠，因而结合遗传算法中的选择、交叉、变异机制能够丰富种多样性，避免局部最优问题发生，还能
提高后期收敛速度。
2.2算法的描述
改进算法的具体实现步骤如下：
S te p 1：参数初始化操作：针对种规模n进行初始化操作，其中涉及到了脉冲频率Q_和Q_，交
叉概率p c ro s s，迭代次数N_ite i■，数据范围b o u n d，脉冲频度r0，遗传算法的进化代数m a x g e n，音强A0，种 规模s iz e p o p，变异概率p m u ta tio n。
S t e p2：随机生成n个蝙蝠。于对应空间内产生n个蝙蝠，设定第i只蝙蝠是1,2,…，n),
针对与之对应的适应度值F itn e s s(X,)进行计算，然后即可获得全局最优适应度值/_、最优蝙蝠位置X*。
S te p 3：更新蝙蝠的空间位置。按照式(2)调整蝙蝠速度以及方向，再根据式（3)对蝙蝠信息位置
进行更新。
S te p 4 ：随机产生一•随机数ra n d1，若ra n d1>r0，则：
①通过式(4)生成与之对应的最优个体，然后完成局部搜索，同时计算出适应度值，也就是f i t b 该值即备选最优位置。
②用遗传算法产生的最优个体进行局部搜索。遗传算法里，其初始种、初始适应度即蝙蝠种和与之对应的适应度，初始种按照适应度可分别完成选择、交叉、变异以形成更多子代。为了减少算
法的时间复杂度，增加算法的通用性、适应性和健壮性，本算法通过离差的方法选取与全局最优值差异
最小的后代作为最优子代并计算适应度值，记为fitg a b a。
③比较f i t b a和fitg a b a，最小值记为F_，选择适应度值较小的个体作为局部搜索后的蝙蝠位置并记录。
④为了直观观察比较两种局部扰动对算法的贡献效果，分别统计每100次迭代中有效的更次数。
S te p 5 ：随机生成ra n d2，如果ra n d2<A0，对比目前蝙蝠位置适应度是否产生变化，如果有所变化，就 将其移动到与之对应的更新处。
S te p6：针对现在蝙蝠位置适应度Fnew和全局最优适应度/_进行比较，若是F_<=/_，那么就要将
全局最优值X*、全局最优适应度值/min—起进行更新。
S te p7：针对搜索精度有没有达到着，或其进行搜索的次数有没有达到最大进行判断，如果与相应要
求一致，就进行下一个步骤，如果不满足，那么就回到step3。
S te p8：把最优蝙蝠位置、与之相应的最小值变化图、适应度变化图都输出。
针对G A B A算法中的时间复杂度进行分析时，需要通过对比G A B A算法在进行迭代的过程和B A
算法一一进行对比,G A B A算法在完成了B A算法以后，通过step4，其遗传算法操作只用进行一次，因为 遗传算法中，染体适应值在进行计算时采用离差方法来获取最优子代，与普通的B A算法对比而言，G A B A算法进行迭代的时候时间复杂度最多增加O(n2)+1。实际应用时，因为n的值并不大，同时算法
计算工作量所针对的是目标仿真实验和函数适应度计算数量，而本算法在遗传算法操作中通过离差的
方法仅须增加1次的函数适应度值计算来筛选子代，所以，寻优适应度值对应的计算量不多，G A B A时 间复杂度没有很大变化。
3仿真结果与分析
3.1测试函数
针对笔者所提出的G A B A算法进行验证，证明其有效性以及适应性，即通过对比G A B A算法和基
本B A算法的效果、计算性能等，笔者进行的模仿实验中利用6个常规算法测试函数进行了检验，其中，/5属于2维寻优函数；而/, ~/4/6都是高维寻优函数，/4属于高维单峰函数，全局最优点的搜索难度比
第3期翁健髙等：基于遗传算法的蝙蝠优化算法研究1141
较大,/，属于高维单峰函数,/6属于高维多极值函数，其局部最优值较为丰富,/2属于多孔或峰的高维下 陷函数。测试函数如表1所示：
表1
测试函数
T a b . 1 Test fu n ction s
函数名测试函数
维数
搜索范围最小值
/, Sphere
移
i = 1
10
[-100,100]0
/2 Ackley
/(x ) = - 2〇e
.2
1 l X 2
1 l c o s ( 2仔X •)
-e '.=1 • + 22. 712 82
20[-32, 32]0
/3 Rastrigrin
移[x f - 10cos (2仔
X i ) + 10]i = 110[-5. 12, 5. 12]0
/4 Rosenbrock
n — 1
移[100( Xi +1 — X 2 )2 + (X i — 1 )2 ]
20[-30, 30]0
Schaffer
sin ^/x j + x2
[1 + 0.001( X ；—0.5
0. 5
+ x 2 ) ]22[-100, 100]-1
/6 Griewank
1 +401)0
- X •
-n —f )i =1 i
10[-600, 600]
3. 2实验环境
算法选择的测试环境：W in d o w s 7,C P U 为英特尔i 3 3220双核3. 30 G H z ，内存4 G B ,M a tla b 7. 0。初始
化蝙蝠种数量为n =10，最大音响A 0 =0.25，最大脉冲频度r 0 =0. 5，遗传算法的进化代数m a x g e n =10，脉 冲频率Q m in =0, Q m a x =2，种规模sizepop = 10，交叉概率pcross = 0. 3，变异概率p m u ta tio n = 0. 1，数据范围
b 〇u n d = [-3 3]，迭
代次数N _ite r = 5 000，在迭代次数固定时，评价算法的稳定性、收敛速度和寻优精度。
3. 3仿真结果与分析
测试迭代次数是5 000次，运行次数是30次,B A 算法和G A B A 算法在标准测试函数中所得到结果
见表2，图1〜图6表示的是与之对应的寻优收敛曲线，图7〜图12是6个测试函数在每100次迭代中 两种局部搜索对算法的影响效果曲线。从表2可知,2种算法都能针对/5在最优值中搜索获得对应个 体，也就是说其在低维函数中，搜索效果良好，但最差值和平均值却相差较大。
表2
测试函数实验比较
T a b . 2 Test fu n ction s exp e rim e n tal com parison
函数算法
最优值最差值平均值方差/
BA 1.08E -04
930. 089 2308. 826 41. 26E +05GABA
8. 64E -10
7. 16E -093. 05E -091. 42E -17/2
BA 16. 392 219. 246 2
17. 983 70. 966 9GABA
4. 27 E -048. 08E -04
5. 93E -043. 64E -07/
BA 29. 868 491. 546 653. 344 1368. 818 4GABA 9. 22 E -084. 51E -06
1. 56E -064. 02E -12/4
BA 15. 290 788. 177 6
24. 842 5448. 412 4GABA
0. 01781. 984 820. 142 91. 33E +03/
BA -0.921 8-0.512 9-0. 765 60. 013GABA -0. 990 3-0. 962 8-0. 984 80. 969 9/6
BA 27. 962 5130. 406 571. 054 1996. 930 5GABA
0. 009 9
0. 196 6
0. 089 3
0. 010 4
针对高维寻优函数/, ~ /4以及/6，按照表2来看，B A 算法平均寻优结果分别为308. 826 4、 17. 983 7、53. 344 1、24. 842 5、71. 054 1。但在G A B A 算法里，其平均寻优精度只有/4相差不大，其他/,、
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论