蝙蝠算法的一种改进

薛威力，贺兴时，杨新社,2

(1.西安工程大学 理学院，西安 710048；2. 密德萨斯大学 科学与技术学院，英国伦敦NW4 4BT)



蝙蝠算法的一种改进

薛威力1，贺兴时1，杨新社1,2

(1.西安工程大学 理学院，西安 710048；2. 密德萨斯大学 科学与技术学院，英国伦敦NW4 4BT)

为了保持蝙蝠算法快速搜索能力，并提高算法寻优精度和搜索能力，分析蝙蝠算法适应度值方差与搜索过程中影响蝙蝠音量和脉冲发生率变化的参数的关系，为了维持解的多样性，动态调整蝙蝠算法搜索过程中影响蝙蝠音量和脉冲发生率变化的参数，并对适应度值进行扰动，提出了一种基于方差改进的蝙蝠算法(The improved Bat Algorithm based on the Variance，VBA)，并通过7个标准测试函数分别对BA和VBA进行测试，结果表明，VBA的寻优性能优于BA.

蝙蝠算法；调整参数；自适应蝙蝠算法；适应度值方差

蝙蝠算法是Xin-she Yang在2010年基于回声定位特性提出的一种算法[1].在适当简化下的特殊情况.为了提高蝙蝠算法性能，已研究出各种进化的、有效的变种蝙蝠算法.如杨新社[2]提出了多目标蝙蝠算法(MOBA)，且已证明其在解决工程中一些设计基准问题上的有效性，Lin等人[3]提出了一种利用Levy飞行和混沌映射实现动态生物系统参数估计的CBA算法，WANG G 等人[4]将和声搜索算法与蝙蝠算法相结合, 得到了用于优化函数基准数值的混合蝙蝠算法. 贺兴时等人[5]提出了基于模拟退火高斯扰动的蝙蝠优化算法.由于蝙蝠算法的具有快速收敛、效率高等特点，使该算法在多个学科和工程领域得到了广泛的应用[6-8].然而，如果我们允许通过快速改变和使算法快速切换到开发阶段，将导致算法在一些初始阶段之后出现停滞.本文提出通过维持解的多样性来提高算法的寻优精度.

1 蝙蝠算法

蝙蝠算法的思想首先设定以下理想的规则：

1) 所有的蝙蝠利用超声波回音的感觉差异来判断食物/猎物和障碍物之间的差异；

2) 蝙蝠是以速度vi，位置xi和固定频率fmin(或波长λ)随机飞行的，并用不同的波长λ(或频率f)和音量A0来搜索猎物.它们会根据猎物的接近程度自动调整他们发出脉冲的波长(或频率)；

3) 虽然音量在不同形式下变化不同，这里我们假设音量是随着从一个很大的(正数)A0到最小值Amin的变化.

另一个明显的简化是用无限追踪来估计时间的延迟和三维地形的.虽然它在几何计算中的应用非常好，但是我们还是用不到它，因为我们面临的大多是多维问题.

fi=fmin+(fmax-fmin)β

(1)

(2)

(3)

其中:β∈[0,1]是一个服从均匀分布的随机向量.此处的x*表示当前全局最优位置(解)，它是在所有n只蝙蝠搜索到的解中进行比较而得到的位置.

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

xnew=xold+εAt

(4)

在一定程度上，BA可以看作是标准粒子群优化和强化的局部搜索的平衡结合，其平衡是受音量和脉冲发生率的控制.当蝙蝠找到猎物时，音量就会降低，同时脉冲发生率就会增加，音量会以任意简便的值改变. 音量Ai和脉冲发生率ri按照以下迭代过程更新.

(5)

(6)

其中:α和γ为常量.实际上，α类似于本文中前面讨论过的模拟退火中一个冷却过程的冷却因素.对任意的0<α<1,γ>0，有

(7)

最简单的情况是令α=γ，在我们的实现中，使用的是α=γ=0.9.

2 改进的蝙蝠算法(VBA)

为使蝙蝠算法保持高效，结合适应度值方差提出使参数α和γ随算法进程动态变化的策略：在算法前期α相对小的值，被更新音量的变化量相对大，使算法保持很强的全局搜索能力；在算法后期此时适应度值多样性减小，α相对大的值，提高算法的局部搜索能力.提出用式(9)实现参数α的自适应策略：

(8)

α=αmax-αmin*ec*NI

(9)

其中:NI为当前迭代次数,maxgen为最大迭代次数.实现了在算法前期以全局搜索为主、局部搜索为辅，以期能在全局范围内快速锁定最优值可能存在的若干区域；而后对算法保持一定全局搜索能力的同时，局部搜索逐渐加强，以期能提高收敛的速度和精度，又不至于陷入局部最优，从而从整体上提升算法的性能.

γ的取值将影响脉冲发生率的变化快慢，间接影响种群多样性，自适应调整γ的值：γ增大时意味着脉冲发生率ri变化速度减慢，使搜索更加精细，则

(10)

在算法后期，种群多样性减小，计算适应度值的方差，当方差变化较小时，在调整参数的基础上对下一次迭代产生的新解分别施行Levy飞行扰动[9]和高斯扰动，干扰种群多样性，使算法有效跳出局部最优，以达到精确搜索的目的.

(11)

(12)

当对算法的解施行Levy飞行扰动和高斯扰动时，分别产生一组新的解，进行比较后将每个位置对应的最好解保留，作为下一次搜索的最优解使用.利用Levy飞行和高斯扰动的特点能使算法搜索有效跳出早熟.

改进的蝙蝠算法(VBA)的基本步骤概括如下[4]：

step1：初始化蝙蝠种群的规模n、第i只蝙蝠的位置x(i),(i=1,2,…,n)和速度v(i),i=1,2,…,n、脉冲发射率r、脉冲响度A(i)、脉冲频率F(i)、适应度值fitness(i),(i=1,2,…,n)、当前最优位置fbest、当前最优位置xbest；

step2：通过公式(1)(2)(3)产生新解；

step3：判断新解的值是否满足Znew≤fitness(i)，满足则将执行step4，否则转入step2；

step4：比较新解和当前最优解适应度值是否满足fbest≥Znew，如果满足则更新当前最优适应度值及最优位置；

step5：计算每次迭代所得适应度值的方差，当前适应度值的方差与上一次适应度值方差的差值小于ε时,通过公式(9)(10)更新参数，并通过(1)(2)(11)，(1)(2)(12)分别产生新的解，比较原始解与扰动后得到的两组新解，保留最优的适应度值，并更新对应的解；

step6：若算法满足停止准则，则停止；否则更新参数并转至step3；

Step7：输出全局最优值gbest，算法结束.

3 仿真实验

本文选取7个测试函数分别对BA和VBA对进行了仿真试验，7个测试函数均来自全局优化测试函数库[11]，如表1所示.各参数设置为n=50，A=0.25，r=0.5.实验硬件环境为Intel(R) Core(TM)2 Duo CPU T5900 @ 2.20 GHz 2.00GB，操作系统Window 7，利用Matlab编程实现.

表1 测试函数

在同等实验条件下，设定10维时最大迭代次数为100，15，30维时最大迭代次数为200，(Zakharov函数在最大迭代次数为200)独立运行50次，计算最优值、平均最优值、均方误差及达优率(说明f1～f5的达优率是参考各自最优值相差5倍的数量级得到的结果，f6～f7是与测试函数最优值进行比较得到的结果)，见表2.

表2 测试结果

从表2的结果可以看出，基于方差改进的蝙蝠算法提高了f1,f2～f5函数最优值的精度，使蝙蝠算法的寻优能力得到了提高并且能保持较高的达优率；函数f2的达优率虽然略低于蝙蝠算法，但VBA可以搜索到精确度更高的最优值，对于该测试函数VBA一定程度上提高了蝙蝠算法的寻优能力；对f6测试函数维数较低时，VBA的达优率高于蝙蝠算法，而高维时虽然达优率略有降低，但是算法寻优精度得到了提高；对函数f7在一定程度上提高了算法的达优率.总体上说明了在搜索过程中改进后的算法可以有效地跳出局部最优寻找到全局最优值.

测试VBA的性能，对表2所示测试函数f1～f5进行仿真模拟，得到算法的进化曲线对比图(作图过程中由于数量级比较小对函数f3～f5迭代过程对应的函数值取对数).进化曲线的横轴表示进化的迭代次数，纵轴表示目标函数的适应度值(作图过程中由于数量级比较小对函数f3～f5迭代过程对应的函数值取对数).BA和VBA进化曲线对比的图像如图1.

图1 Ackely函数

Ackley函数是多模态函数，有少数的局部最小值.从图1可以看出，对于Ackely函数来说，在整个进化过程中VBA对个体优化质量优于BA，在算法中期BA陷入局部最优点无法跳出，表现出了早熟的特点，而VBA在低维和高维两种情况都出现拐点，跳出局部最优，最终收敛到了更加精确的全局最优值. 从图2可以看出，BA对于Ronsebrock函数高维时寻优能力比较差，在整个进化过程中VBA对个体优化质量优于BA，在算法中期BA陷入局部最优点无法跳出，表现出了早熟的特点，VBA在低维出现拐点，跳出局部最优，最终收敛到了更加精确的全局最优值，但在高维时VBA虽然在拐点处跳出局部最优但再一次出现早熟的现象，优化表现不明显仅在寻优速度上有所提高.

图2 Ronsebrock函数

从图3～5可以看出，对Sphere函数、Griewank函数、Zakharov函数，BA寻优都会陷入局部最优，虽然在迭代中出现拐点但仍然无法跳出局部最优，而VBA可以在拐点处跳出局部最优，寻找到精度更大的全局最优值.

图3 Sphere函数

图4 Griewank函数

图5 Zakharov函数

由以上所有函数的测试结果及进化曲线对比可以得到以下结论: 本文提出的改进算法的特点主要体现在搜索过程中算法能有效地跳出局部最优，搜索精度有明显的提高，并且寻优速度也有所提高，所以基于方差改进的蝙蝠优化算法是合理并且有效地一种进化算法.

4 结 语

本文在蝙蝠算法的基础上提出了一种自适应参数调整的蝙蝠优化算法.分析表明适应度值方差反映种群多样性，通过适应度值方差变化动态的调整算法参数，并提出对适应度值进行扰动增加解的多样性的思想，从而寻求最优位置.测试表明，改进算法提高了寻优精度及寻优速度，并使算法后期能有效地跳出局部最优，提高了蝙蝠群体的搜索能力.本算法也适合一般的函数优化.如何进一步使用方差的其他特征调整算法，并高效处理普通问题及多目标问题，将是下一步的研究工作.

[1] YANG X S. Nature inspired cooperative strategies for optimization (NICSO 2010) [M]. Berlin: Springer Berlin Heidelberg, 2010. 65-74.

[2] YANG X S. Bat algorithm for multi-objective optimization [J]. International Journal of Bio-Inspired Computation, 2011, 3(5):267-274.

[3] LIN J H, CHOU C W, YANG C H. A chaotic Levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems [J]. Computer and Information Technology.2012, 2(2): 56-63.

[4] WANG G, GUO L. A Novel Hybrid Bat Algorithm With Harmony Search for Global Numerical Optimization [J]. Journal of Applied Mathematics, 2013, 21(1): 233-256.

[5] 贺兴时, 丁文静, 杨新社. 基于模拟退火高斯扰动的蝙蝠优化算法 [J]. 计算机应用研究, 2014, 31(2): 392-397.

[6] 肖辉辉, 段艳明. 基于DE算法改进的蝙蝠算法的研究及应用[J].工业工程, 2014, 31(1): 272-277.

[7] 刘长平, 叶春明. 具有Levy飞行特征的蝙蝠算法[J].智能系统学报, 2013, 8(3): 240-246.

[8] 谢 健, 周永权, 陈 欢. 一种基于Levy飞行轨迹的蝙蝠算法[J].模式识别与人工智能, 2013, 19(2): 51-54, 81.

[9] YANG X S. Nature-inspired metaheuristic algorithms [M].[S.l.], Luniver Press, 2010. 14-16.

[10] VALIAN E, MOHANNA S, TAVAKOLI S. Improved cuckoo search algorithm for global optimization [J]. International Journal of Communications and Information Technology, 2011, 1(1): 31-44.

[11] JAMIL M, YANG X S. A literature survey of benchmark functions for global optimization problems [J]. International Journal of Mathematical Modelling and Numerical Optimization, 2013, 4(2): 1-47.

Study on improved bat algorithm

XUE Wei-li1, HE Xing-shi1, YANG Xin-she1,2

(1. School of Science Xi’an Polytechnic University, Xi’an 710048, China;2. School of Science and Technology, Middlesex University, London NW4 4BT, UK)

In order to make the Bat Algorithm maintaining the strong search ability, and to improve the local search ability and the accuracy of the search for the optimal solution. An improved bat algorithm was proposed—the improved bat algorithm based on the variance (VBC). In this paper, the relationship between the parameters and the fitness variance of bat algorithm was analyzed. In order to maintain the diversity of solution it is to adjust parameters that affect the bat's volume and pulse generating at the search process of bat algorithm and to disturb the values. And it used BA and VBA to carry out numerical experiments for 7 test benchmarks. The results showed that VBA was superior to the BA.

bat algorithm; adjusted parameters; adaptive of bat algorithm; fitness variance

2015-10-14.

陕西省自然科学基础研究计划项目(2014JM1006)；陕西省教育厅专项科研计划项目(14JK1282).

薛威力(1989-)，男，硕士，研究方向：智能优化算法.

TP18

A

1672-0946(2016)06-0706-07