陈伟利,陈国华

　　(湖南人文科技学院 数学与计量经济系,湖南 娄底 417000)

      摘要：针对基本蝙蝠算法存在的易陷入局部最优、后期收敛速度慢等问题，提出动态双子群拟梯度蝙蝠算法。该算法利用蝙蝠脉冲发射频率将蝙蝠种群动态地划分为自由搜索种群和局部搜索种群两个子群,在局部搜索子群中利用拟梯度方向指导蝙蝠搜索。为了验证算法的有效性，通过对4个基准函数的实验测试，实验结果表明，该算法相对于基本蝙蝠算法具有较好的全局搜索能力和优化精度。

　　关键词：蝙蝠算法；拟梯度；基准函数；最优值

0引言

　　蝙蝠算法(Bat Algorithm, BA)是一种新颖的群智能优化算法，是由剑桥大学学者 Yang Xinshe在2010年通过模拟蝙蝠的捕食行为而提出的一种优化算法［1］。该算法将优化问题的解看作是搜索空间中的微蝙蝠，搜索最优解的过程看成是微蝙蝠寻找食物的过程。在一定程度上粒子群优化(PSO)算法和和声搜索(HS)算法是BA的一种特殊情况，而BA也被证明比粒子群优化算法和遗传算法具有更高的搜索性能［2］。自蝙蝠算法提出以来，已成功地运用于多种优化问题的解决，如多目标优化［3］、工程优化［4］、聚类方法［5］、调度问题［6］、经济负荷分配问题［7］等。参考文献［8］总结了蝙蝠算法取得的进展，并提出了蝙蝠算法进一步研究的主要方向。虽然蝙蝠算法在许多优化问题中取得了很好的效果，但其本身也存在后期收敛速度不快和易陷入局部最优等缺点。针对蝙蝠算法的这些缺陷，许多学者提出了各自的改进方法，如模糊蝙蝠算法［9］、混沌蝙蝠算法［10-11］、Lévy飞行蝙蝠算法［12-13］。在对蝙蝠算法的改进中，多数学者集中在蝙蝠初始化和飞行方式的改进上［10-15］，而对于改进蝙蝠的局部搜索策略的算法相对较少，基于此，本文提出动态双子群拟梯度蝙蝠算法(PGBA)。通过仿真实验表明，与基本的BA相比，PGBA具有更好的寻优能力和搜索精度。

1动态双子群拟梯度蝙蝠算法

　　1.1设计思想

　　蝙蝠算法能够成功地解决很多问题，但基本蝙蝠算法存在求解精度不高和收敛速度过慢的问题。笔者通过记录蝙蝠群体在飞行时的各种参数，并对参数进行了简单统计分析发现，控制蝙蝠群体自由飞行和局部搜索分配的脉冲发射频率更新速度较快，而响度的变化却并不大，这直接导致蝙蝠在局部寻优过程中由于飞行速度过快而不能很好地发现更优解。因此，为了提高蝙蝠的局部搜索能力，必须改变蝙蝠的响度更新方式。此外蝙蝠在局部搜索时是在最优解附近随机生成一个解，既然局部搜索的目的是发现更好的解，那为什么不朝着最有利的方向搜索？受梯度在传统算法中的高效性的启发，本文引入拟梯度定义，用于指示函数的大致上升或下降的方向，指导蝙蝠的局部搜索。

　　定义给定某常数h，p维函数f(X)在点(x1,x2,…,xp)的相对于h的拟梯度向量定义为：

　　V=(v1,…,vp)

　　其中，vi=f(x1,x2,…,xi+h,…,xp)－f(x1,x2,…,xi,…,xp)。

　　1.2动态双子群拟梯度蝙蝠算法步骤

　　综上所述，本文提出拟梯度蝙蝠算法的步骤如下：

　　（1）初始化蝙蝠种群参数(蝙蝠的位置、飞行频率、飞行速度、脉冲发射频率、响度)。

　　（2）计算每只蝙蝠的适应度值，并得到最优适应度对应的蝙蝠位置（bestx），记录最优适应度值。

　　（3）生成随机数，将蝙蝠种群分为脉冲发射频率小于随机数（记为第一类）和大于随机数（记为第二类）两类。

　　（4）自由飞行。对步骤（3）分出的第一类，按照基本蝙蝠算法进行自由飞行。

　　（5）拟梯度局部搜索。对步骤（3）分出的第二类，首先令h=loudness,计算其拟梯度v,在最优位置附近按拟梯度方向生成一个局部解，xnew=xbest－v 。

　　（6）如果局部搜索不能找到更优解，视为响度太大搜索失败，将该蝙蝠的响度更新为原先的α倍，即Anew=α×Aold。如果找到更优解，则更新蝙蝠位置，保持响度不变。

　　（7）对自由飞行和局部搜索之后的蝙蝠种群，如果找到更优解，则更新其脉冲发射频率。更新方法为：rt+1i=r0i(1+e－γ×t)。

　　（8）对当前蝙蝠重新排序，找到最优蝙蝠所在位置，记录最优值。

　　（9）满足结束条件（达到精度或最大迭代次数），转至步骤（10），否则转至步骤（3），进行下一轮迭代。

　　（10）输出相关结果。

2仿真实验

　　为了验证本文提出的算法的有效性，本文从相关文献中选取4个标准测试函数(包括单峰和多峰函数)进行仿真实验。

　　这是一个多峰函数，在x*=(0,0,…,0)取得理论最小值0。

　　利用拟梯度蝙蝠算法对4个标准的测试函数进行求解，并与基本的蝙蝠算法进行比较。算法的参数设置如下：在标准蝙蝠算法中，频率范围为［0,1］,α=γ=0.9,蝙蝠数量为40，r0=0.1,响度初始化为随机数，迭代次数为200次。拟梯度蝙蝠算法的参数设置与标准算法类似，仅改变脉冲发射频率和响度调整幅度，即rate0=0.5,α=0.5。在上述参数设置下，每种算法运行30次，将两种算法的最优结果、最差结果、平均结果和标准差统计如表1所示。 

　　从表1可以看出，与基本蝙蝠算法(BA)相比，拟梯度蝙蝠算法(PGBA)明显取得更好的寻优结果。从最优结果的角度看，BA在f1、f2、f4上都是成功的，但在f3上失败。与参考文献［15］中结果有差异，这里主要的原因在于种群的数量和迭代的次数设置不同； PGBA在4个函数上都取得成功，且其精度远远高于BA，尤其在函数f4上，其精度达到了10－16 。从平均结果看，PGBA在f3上表现欠佳，但仍远好于BA，而在其他函数上则取得了非常理想的结果。为了更清晰地对比BA和PGBA，图1~图4给出了两种算法在4个函数上的收敛曲线对比图。

　　通过两种算法的收敛曲线对比图，可以发现PGBA相对BA具有更好的寻优能力，在函数f1和f2上，PGBA相对于BA不仅达到了更高的精度，而且在收敛速度上明显要更快。而在f3和f4上，PGBA在开始迭代时其收敛速度并没有优势，但随着迭代次数的增加，PGBA表现出了较强的局部挖掘能力。

3结论

　　针对基本蝙蝠算法收敛速度较慢和易陷入局部最优的问题提出了动态双子群拟梯度蝙蝠算法。该算法动态地将基本蝙蝠种群划分为自由搜索和局部搜索两个不同的种群，在局部搜索种群中利用拟梯度方向指导蝙蝠的搜索。这一划分既保证了算法的全局搜索能力，又提高了算法的局部搜索能力。实验表明，该算法具有较好的全局搜索能力和较高的搜索精度。

参考文献

　　［1］ Yang Xinshe. A new metaheuristic batinspired algorithm［M］.Nature inspired cooperative strategies for optimization (NICSO 2010). Springer Berlin Heidelberg, 2010: 6574.

　　［2］ Yang Xinshe. Nature Inspired Metaheuristic Algorithms (2nd Edition)［M］. Frome, UK: Luniver Press, 2010: 97104.

　　［3］ Yang Xinshe. Bat algorithm for multiobjective optimization［J］.International Journal of BioInspired Computation, 2011, 3(5):267274.

　　［4］ Yang Xinshe, GANDOMI A H. Bat algorithm: a novel approach for global engineering optimization［J］. Engineering Computation, 2012, 29(5):267289.

　　［5］ KOMARASAMY G, WAHI A. An optimized kmeans clustering technique using bat algorithm［J］. European Journal of Scientific Research, 2012, 84(2):263273.

　　［6］ 盛晓华,叶春明. 蝙蝠算法在PFSP调度问题中的应用研究［J］. 工业工程,2013,16（1）:119124.

　　［7］ GHERBI Y A, BOUZEBOUDJA H, LAKDJA F. Economic dispatch problem using bat algorithm［J］. Leonardo Journal of Sciences, 2014, 13(24): 7584.

　　［8］ Yang Xinshe, He Xingshi. Bat algorithm: literature review and applications［J］. International Journal of BioInspired Computation, 2013, 5(3): 141149.

　　［9］ KHAN K, NIKOV A, SAHAI A. A fuzzy bat clustering method for ergonomic screening of office workplaces［M］. Third International Conference on Software, Seruices and Semantic Techdogies S3T 2011. Springer Berlin Heidelberg, 2011，101:5966.

　　［10］ LIN J H, CHOU C W, YANG C H, et al. A chaotic Levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems［J］. Computer and Information Technology, 2012, 2(2): 5663.

　　［11］ 刘长平, 叶春明. 具有混沌搜索策略的蝙蝠优化算法及性能仿真［J］. 系统仿真学报, 2013, 25(6):11831188.

　　［12］ 刘长平,叶春明. 具有Lévy飞行特征的蝙蝠算法［J］. 智能系统学报,2013,8（3）:240246.