融合正弦余弦的蝙蝠算法
2018-09-05韩斐斐刘升王兴凡
韩斐斐 刘升 王兴凡
文章编号： 2095-2163（2018）03-0122-06中图分类号： 文献标志码： A
摘要： 关键词： （School of Management Shanghai University of Engineering Science， Shanghai 201620， China）
Abstract： Bat Algorithm （BA） is a novel random search optimization algorithm. In order to overcome the shortcomings of slow convergence speed and poor optimization accuracy of bat algorithm， bat algorithm （SCABA） based on sine cosine is proposed， In the later iteration， the sine cosine operation is introduced to update the current individual position of the bat， thereby enhancing the diversity of the population， avoiding the algorithm getting into the local optimum and enhancing the global optimization ability of the algorithm. The improved algorithm， MFBA and basic BA are tested by six standard test functions. The simulating results show that the improved algorithm is feasible and effective. Compared with the basic BA algorithm， the convergence precision and robustness have been greatly improved .
Key words：
基金項目：
作者简介：
通信作者：
收稿日期： 引言
优化问题广泛存在于科学研究和工程优化等领域，传统的优化方法已经不能满足解决复杂优化问题的需要。受自然界生物群体智能行为和自然界进化规律的启发，国内外学者们提出了多种基于仿生学的群体智能优化算法，如蚁群算法（Ant Colony Algorithm，ACA）[1]来自于蚁群寻找食物的行为，蚂蚁根据信息素的浓度选择觅食路径；粒子群算法（Particle Swarm Optimization， PSO）[2]的基本思想来源于鸟群的信息交流和觅食行为；入侵杂草优化（Invasive Weed Optimization，IWO）[3]算法模拟自然界中杂草的入侵繁殖、空间扩散和优胜劣汰法则；花授粉算法（Flower Pollination Algorithm ， FPA）[4]模拟异花授粉为全局寻优，自花授粉为局部寻优。群智能算法已成为了智能优化领域的研究热点和重要研究方向，并广泛应用于大数据处理[5]、组合优化[6]、文本聚类[7]等领域。
2010年，学者Yang提出了蝙蝠算法[8]，其模拟自然界中蝙蝠利用回声定位机制寻找猎物的特性，是在特定理想化规则下简化而来的一种全局优化算法。目前，BA作为一种新的群智能优化算法，已成功用于路径规划[9]、图像压缩[10]、生产调度[11]等问题中。蝙蝠算法模型简单、算法参数少、通用性强，但也存在易陷入局部最优、收敛精度低、算法后期收敛速度慢等不足，针对这些不足，国内外众多学者根据不同的改进策略对其进行改进，文献[12]把差分进化算法中的变异、交叉、选择机制应用于蝙蝠算法，使蝙蝠算法具有变异机制，增强了算法的寻优能力；文献[13]把模拟退火算法和高斯扰动融入基本蝙蝠算法，使算法不仅具有较好的全局搜索能力，而且加快了算法的收敛速度；文献[14]赋予蝙蝠个体以随机的速度，同时利用速度纠正因子限制蝙蝠的移动步长，既提高了蝙蝠种群的多样性，又使得算法具有自适应性。本文针对蝙蝠算法的不足，把正弦余弦算法中的正弦余弦操作应用于蝙蝠算法，从而避免种群个体陷入局部最优，增强算法全局寻优能力。对6个标准测试函数进行测试，仿真结果表明，改进后算法的收敛速度、寻优精度和鲁棒性均有了明显的提高。
1蝙蝠算法BA
蝙蝠一般在夜间活动，在黑暗中发出短促、频率高的声音脉冲，通过对接收到的声波回声进行分析来判别方向、避开阻碍物以及寻找食物的位置。随着蝙蝠与搜索猎物的距离减小，为了捕食到猎物，脉冲的发射率不断增加，发出声音的响度不断减小。蝙蝠通过发出和接收声波回声的时间差，来确定目标距离、目标方位及目标移动速度。将蝙蝠寻找食物过程理想化如下：
（1）所有的蝙蝠都利用回声定位机制感知目标距离，且能够区分食物与障碍物。
（2）蝙蝠在位置xi以速度vi随意飞行，以固定频率fi、可变化波长λ和响度A0搜索食物；同时根据目标距离来调整发射出的脉冲波长（或频率），在靠近食物时调整发射脉冲的频度γ，γ（0，1）。
（3）响度从最大值Amax变化到最小值Amin。
设蝙蝠在d维空间中搜索食物，在t-1时刻，蝙蝠i的位置和飞行速度分别为xt-1i和vt-1i，在t时刻，蝙蝠i的位置xti、速度vti更新公式如下：fi=fmin+fmax-fminβ（1）
vti=vt-1i+（xt-1i-x*）fi（2）
xti=xt-1i+vti（3）其中，fmin和fmax分别为蝙蝠发出声波的最小和最大频率，每只蝙蝠发射声波的频率初始值在范围[fmin， fmax]内均匀随机分布；β∈[0，1]是服从均匀分布的随机变量；x*是蝙蝠种群中的全局最优解。
对于局部搜索，在[0，1]之间产生一个随机数rand1，如果rand1>ri，则对当前最优解按式（4）进行随机扰动，产生一个新解xnew，并对新解做越界处理。产生一个随机数rand2，如果rand2>Ai且f（xnew） At+1i=αAti（5） rt+1i=r0i1-exp-γt（6）其中，ε∈[-1，1]是一个服从均匀分布的随机数；At= 2融合正弦余弦的蝙蝠算法SCABA 2.1正弦余弦算法 2016年，格里菲斯大学教授Mirjalili提出正弦余弦算法（Sine and Cosine Algorithm，SCA）[15]，其结构简单、鲁棒性好、容易实现，利用正弦函数和余弦函数的性质迭代以达到寻找最优解的目的。算法中几个关键的参数提升了其寻优性能，有效地平衡了“局部开发”和“全局探索”。在SCA中，随机生成一个含有N个个体的初始种群Pt={Xti}，其中Xti=xti1，xti2，…，xtij，…，xtid， j=1，2，…，d； i=1，2，…，N，N为种群大小；d为待优化函数所含决策变量的个数，即维数；t代表当前进化代数。 首先，计算种群中每个个体的适应度值，根据适应度值的大小对种群中个体进行排序，并记录当前最优个体及其位置，在每一次迭代中，种群个体位置更新如下： xt+1i=xti+r1*sinr2*r3*x*-xti，r4<0.5 xti+r1*cosr2*r3*x*-xti，r4>0.5（7） xt+1i代表第t+1次循环下的第i个个体；xti代表第t次循环下第i个个体；x*是适应度值最优的个体；r1是控制搜索方向的参数；r2是控制搜索距离的参数；r3是一个随机惯性权重；r4的大小决定下一代进行余弦操作或者正弦操作，具体计算如下：r1=a-a*〖SX（〗t〖〗maxt〖SX）〗； r2=rand（0，2π）；r3=rand（0，2）；r4=rand（0，1）[JY]（8）SCA伪代码算法设计随机生成初始种群计算每个蝙蝠个体的适应度值及最佳位置x*while（终止准则不满足）for i=1 to nfor k=1 to d根据式（8）计算参数r1，r2，r3，r4的值if r4<0.5根据式（7）中正弦部分更新位置else根据式（7）中余弦部分更新位置end forend forend while[BT5]2.2融合正弦余弦的蝙蝠算法SCABA在本文提出的混合正弦余弦算法的蝙蝠算法中，算法迭代后期，經过进化的蝙蝠位置不是直接进入下一次迭代，而是对种群中个体的位置进行正弦、余弦操作，得到新的蝙蝠位置，再进入（t+1）次迭代。由于正弦余弦算法利用正弦函数和余弦函数值的变化来达到寻优的目的，且正弦（余弦）函数值的大小是在[-1，1]之间，因此将正弦余弦融合到BA中，可以有效提升BA的收敛速度。另外，SCA有几个关键的参数，r1指引着个体搜索的方向，r2控制着个体寻优的移动距离，因此在SCABA中，蝙蝠个体的搜索距离和方向能够被控制并朝向最优个体，这降低了个体寻优的盲目性，提高了个体寻优的效率。SCABA将正弦余弦算法和蝙蝠算法各自的优点充分融合，使算法不仅具有强大的全局寻优能力，同时也具有强大的局部搜索能力，其运行步骤描述如下：[WT5HZ][ST5HZ]Step 1[WT5BZ][ST5BZ]初始化SCABA的各个参数，在d维空间中随机生成初始种群蝙蝠的位置xi，其中i=1，2，…，n，同时计算相应蝙蝠的适应度，随机产生脉冲发射的速率R0和声音响度A0，并把群体中的最优蝙蝠初始位置作为x*的初值；[WT5HZ][ST5HZ]Step 2[WT5BZ][ST5BZ]根据式（1）～（3）更新蝙蝠个体的速度和位置，产生新一代个体，并计算其适应度；[WT5HZ][ST5HZ]Step 3[WT5BZ][ST5BZ]如果随机数rand1>ri，则从当前种群的最优解集中选择一个解，使用式（4）通过施加扰动，产生新个体xnew来替代当前解；[WT5HZ][ST5HZ]Step 4[WT5BZ][ST5BZ]若随机数rand2>Ai且f（xnew） 由表2可以看出，对于6个测试函数，无论是简单的单峰函数，还是存在大量局部极值的非线性多峰函数，本文提出的融合正弦余弦的蝙蝠算法（SCABA）最优解、最差解、平均值及标准方差的精度均明显高于基本蝙蝠算法（BA）和采用机动飞行的蝙蝠算法（MFBA）。对于函数f2，存在找到最优解的情况，对于函数f1，f3，f4，f5，f65个函数，最多相差47个数量级，这充分证明了改进算法的寻优精度和鲁棒性比其它2种算法有很大程度的提高。为了更直观比较SCABA与其它2种算法的寻优性能，图1给出了3种算法在6个测试函数上的收敛曲线，为了更方便对收敛曲线进行观察，对函数的最优值取以10为底的对数。从图1可以看出，SCABA具有更高的收敛精度，能够在较短的时间内接近于理论最优值，并且收敛速度快，f1，f2，f3，f4，f55个函数在迭代次数不到50次时，就能收敛到稳定的收敛精度，f6在迭代次数不到100次时，就能收敛到稳定的收敛精度。为了进一步验证改进算法的可行性和有效性，在100维和500维下分别运行50次，并计算6个函数的最优值、最差值、平均值及标准差，从表3可以看出，SCABA在低纬度下的寻优精度跟在高纬度下的求解精度相差不明显，不存在随着优化函数维数的增加而陷入“维灾难”的情况，这表明，在优化高维度的复杂函数时，SCABA也能呈现出良好的寻优性能。[FL）][PS韩斐斐1.EPS；S*2；X*2，BP#][HT6H][ST6HZ][WT6HX][WT5BZ][FL（2K2][BT4]4结束语针对BA存在收敛精度低、寻优速度慢、易陷入局部最优等的不足，本文提出了一种融合正弦余弦的蝙蝠算法—SCABA，在算法迭代后期，对种群中蝙蝠个体的位置进行正弦、余弦操作，得到新的蝙蝠位置。通过对6个测试函数的测试，仿真结果表明，SCABA具有较高的收敛速度和较好的优化精度，在很大程度上可避免陷入局部最优，具有较强的全局搜索能力。如何使改进算法表现出更优的寻优结果以及将改进算法应用到具体的领域，是下一步的重点研究内容。[HS2][HT5H]
参考文献[HT][WT6B1][ST6BZ][HT6SS]
[1] [ZK（#〗[HJ*2] [JP3]Colorni A. Distributed Optimization by Ant Colonies[C]// European Conference on Artificial Life. The MIT Press， 1991.[JP]
[2] Kennedy J， Eberhart R. Particle swarm optimization[C]// IEEE International Conference on Neural Networks， 1995. Proceedings. IEEE， 2002，4：1942-1948.[3] [JP3]Mehrabian A R， Lucas C. A novel numerical optimization algorithm inspired from[JP] weed colonization[J]. Ecological Informatics， 2006， 1（4）：355-366.[ZK）][HT5SS][ST5BZ][WT5BZ][JY][FL）][WT6B1][ST6BZ][HT6SS]
[4] [ZK（#〗[HJ*2] Yang Xinshe. Flower pollination algorithm for global optimization[C]//LNCS 7445： Proceedings of the 11th Internation Conference on Unconventional Computation and Natural Computation， Orléan， France， Sep 3-7， 2012. Berlin， Heidelberg： Springer， 2012： 240-249.
[5] Cheng S， Zhang Q， Qin Q. Big data analytics with swarm intelligence[J]. Industrial Management & Data Systems， 2016， 116（4）：646-666.
[6] 冯翔，张进文，虞慧群. 仿生蚊子追踪算法[J]. 计算机学报，2014，37（8）：1794-1808.
[7] 乔莹莹，宋威，马伟. 基于GA优化QPSO算法的文本聚类[J]. 计算机应用研究，2014，31（10）：2912-2915.
[8] Yang X S. A New Meta-heuristic Bat-Inspired Algorithm[J]. Computer Knowledge & Technology， 2010， 284：65-74.
[9] Wang G G， Chu H C E， Mirjalili S. Three-dimensional path planning for UCAV using an improved bat algorithm[J]. Aerospace Science & Technology， 2016， 49：231-238.
[10]Karri C， Jena U. Fast vector quantization using a Bat algorithm for image compression[J]. Engineering Science & Technology An International Journal， 2016， 19（2）：769-781.
[11]姚妮，李紅婵. 基于混合蝙蝠算法的多目标柔性作业车间调度问题[J]. 微电子学与计算机，2017，34（3）：25-29，34.
[12]肖辉辉，段艳明. 基于DE算法改进的蝙蝠算法的研究及应用[J]. 计算机仿真，2014，31（1）：272-277.[13]He X S， Ding W J， Yang X S. Bat algorithm based on simulated annealing and Gaussian perturbations[J]. Neural Computing & Applications， 2014， 25（2）：459-468. [14]裴宇航，刘景森，李煜. 一种动态调整惯性权重的自适应蝙蝠算法[J]. 计算机科学，2017，44（6）：240-244.[15][JP2]Mirjalili S. SCA： A Sine Cosine Algorithm for solving optimization problems[J]. Knowledge-Based Systems， 2016， 96：120-133.[JP][16]王文， 王勇， 王晓伟. 采用机动飞行的蝙蝠算法[J]. 计算机应用研究， 2014， 31（10）：2962-2964.[ZK）][FL）]
