文章快速检索 高级检索

Application of the improved bat algorithm in numerical integration
XIAO Huihui , DUAN Yanming
College of Computer and Information Engineering, Hechi University, Yizhou 546300, China
Abstract: The bat optimization algorithm is a new swarm intelligence algorithm that has appeared in recent years. It is a kind of intelligent optimization tool with very good and strong optimization ability. This algorithm has characteristics including fast convergence, potential distribution and parallelism. However, it also has shortcomings including low precision in optimizing, low convergence speed in later periods, ease of falling into local optimization, etc. To overcome the shortcomings of current numerical integration methods and the bat algorithm, by fusing the differential evolution algorithm that has excellent abilities of local searching and global optimizing into the bat algorithm, this paper presents an improved bat algorithm based on the differential evolution algorithm that is applied to solving the numerical integration of any function. This algorithm not only can solve the definite integral for any function of common sense, but it can also calculate the oscillatory integrals and singular integrals. By comparing six different examples with current numerical integration methods, the simulations show that the improved algorithm is efficient and feasible. It is able to compute the numerical integration of any function. Meanwhile, it extends the application field of the bat algorithm.
Key words: bat algorithm     numerical integration     differential evolution algorithm     convergence speed     fitness     function

1 蝙蝠优化算法 1.1 基本蝙蝠优化算法

1.2 具有差分进化策略的蝙蝠算法

1.2.1 差分进化算法

1.2.2 DEBA算法的设计思想

DEBA算法的设计思想：在基本的蝙蝠算法基础上，经过演化后的蝙蝠位置xit不是直接进入下一次(t+1)迭代，而是继续对其进行差分进化，通过变异机制来获得种群中优秀个体与当前个体之间的差异，从而引导个体的演化方向，使其向种群中的优秀个体靠近，在得到新的蝙蝠位置后，再进入下一次迭代，继续利用基本的蝙蝠算法进行搜索和位置更新。这样就增加了种群的多样性，使其避免陷入局部最优而获得全局最优解，同时也提高了收敛速度和收敛精度。

1.2.3 DEBA算法实现步骤

DEBA算法的具体实施步骤如下：

1)初始化DEBA算法的各个参数。

2)根据目标函数计算种群个体的适应度函数值，确定当前的最优值及最优解。

3)利用式(1)~(3)对蝙蝠的搜索脉冲频率、速度和位置进行更新：

 (1)
 (2)
 (3)

4)对当前最优解进行随机扰动，产生一个新的解，并对新的解进行越界处理。

5)生成均匀分布随机数rand，如果rand < Aif(xi) < f(x*)，则接受4)产生的这个新解，然后按式(4)~(5)对riAi进行更新：

 (4)
 (5)

6)利用差分进化算法以每一个蝙蝠位置为初始点进行变异、交叉、选择操作，得到新的蝙蝠位置。

7)根据种群蝙蝠个体的适应度值优劣，来更新种群的最优值和种群的最优解。

8)在算法完成一次迭代后，进入下一次迭代之前，判断算法是否满足终止条件，如满足条件，则退出程序并输出种群的最优解及种群的最优值，否则，转3)。

2 DEBA算法性能实验仿真与分析

1) Sphere函数：D=10, -100≤xi≤100，函数的理论最优值为0。

2) Rastrigrin函数：D=10, -5.12≤xi≤5.12，函数的理论最优值为0。

3) Rosenbrock函数：D=10, -30≤xi≤30，函数的理论最优值为0。

4) Schaffer F6函数：D=2, -100≤xi≤100，函数的理论最优值为-1。

2.1 固定演化迭代次数的性能比较

 函数 算法 最优值 平均值 最差值 标准差 f1(x) DEBA 9.69563834601188E-19 5.84379322609028E-18 1.62619389692447E-17 4.83833694643861E-18 BA 2.16605159265E+03 1.24378646804E+04 3.68689654162E+04 7.91305595959E+03 f2(x) DEBA 0 0 0 0 BA 4.87664433735E+01 9.77629405876E+01 1.78104931825E+02 3.24392513245E+01 f3(x) DEBA 22.86069418838456 55.24989150912832 88.59947945489543 17.80577852011065 BA 4.13821313748E+03 1.01326679645E+07 5.38275134994E+07 1.37257696079E+07 f4(x) DEBA -1 -0.99992590333598 -0.99943890712016 1.32120767991106e-04 BA -0.92181081785627 -0.64017500307743 -0.51119158750609 1.2404397445565 e-01

 图 1 DEBA与BA的收敛曲线对比 Fig. 1 Comparison of convergence curves of DEBA and BA
2.2 算法复杂度的分析

 维数 DEBA BA 10 0.9555 0.3276 30 1.0109 0.3526 50 1.1069 0.3853

3 DEBA算法求解数值积分算法

1)在积分区间随机生成NP个D维个体的种群，并确定种群中的每个个体的表达式，个体的表示形式为(X, V)=((x1x2，…，xD)，(v1v2，…，vD))。

2)计算适应度。对积分区间内的每个个体的D维分量进行升序排列，接着分别计算D+2个节点相邻之间的距离djj=1，2, …，D+1，然后计算D+1个小段中间节点和D+2个节点的函数值，并比较每小段中间节点、左端点和右端点的函数值，记下最大的函数值为Maxj，最小的函数值为Minj, j=1, 2, …, D+1，每个个体的适应度定义为：f(i)=，设定一个很接近0的值ε作为程序的终止条件，当最小适应度小于ε时程序运行终止，适应度越接近于0，表明该个体越优良。

3)对算法的终止条件进行判断，假如终止条件不成立，则算法往下继续执行，如终止条件满足，算法停止运行，并输出种群的最优个体，同时求出函数的积分值。

4)更新蝙蝠种群。

5)重复运行4)，直到终止条件满足为止，输出种群的最优个体，并把它作为结果。

6)算法停止执行时，算法最终所求出的函数积分值近似于

 (6)

4 数值积分仿真实验与分析

 函数 x2 x4 1/1+x sin(x) ex 精确值 2.667 6.400 2.958 1.099 1.416 6.389 本文算法 2.666 985 73 6.401 201 2.958 169 0 1.098 754 1.416 082 6.388 921 IWO 2.666 33 6.398 65 2.957 81 1.098 59 1.416 32 6.388 73 PSO 2.666 6.398 2.958 7 1.098 5 1.416 6.388 7 AFS 2.666 593 6.399 501 2.957 868 1.098 598 1.416 173 6.388 949 FN 2.667 6.399 5 2.957 89 1.098 6 1.416 6.389 ES 2.666 6.398 2.957 7 1.098 1.416 6.388 NN 2.665 6.393 2.959 1.101 1.415 6.388 Simpson 2.667 6.667 2.964 1.111 1.425 6.421 梯形法 4.000 16.000 3.326 1.333 0.909 8.389

 图 2 函数x4的积分误差变化曲线 Fig. 2 The integral error change curve of function x4
 图 3 函数的积分误差变化曲线 Fig. 3 The integral error change curve of function

 算法 函数积分值 本文算法 1.546 038 834 576 7 ES[4] 1.545 980 5 PSO[5] 1.546 032 AFS[6] 1.546 032 61 IWO[7] 1.545 994 NN[19] 1.546 7 FN[20] 1.546 04

 图 4 例2的积分误差变化曲线 Fig. 4 The integral error change curve of example 2

 算法 函数积分值 本文算法 0.746 826 954 460 4 PSO 0.746 866 IWO 0.746 834 AFS 0.7468 273 04 ES 0.746 83 矩形法 0.777 82 梯形法 0.746 21 Simpson 0.746 83

 图 5 例3的积分误差变化曲线 Fig. 5 The integral error change curve of example 3

 算法 函数积分值 本文算法 58.470 505 372 351 PSO 58.470 24 IWO 58.470 492 AFS 58.470 444 83 ES 58.470 65 FN 58.470 5 梯形法 58.520 9 Simpson 58.470 821 5

 图 6 例4的积分误差变化曲线 Fig. 6 The integral error change curve of example 4

 图 7 例5的积分误差变化曲线 Fig. 7 The integral error change curve of example 5

 图 8 例6的积分误差变化曲线 Fig. 8 The integral error change curve of example 6

5 结束语

 [1] 薛密. 数值数学和计算[M]. 上海: 复旦大学出版社, 1991 : 191 -195. [2] 刘玉琏, 傅沛仁. 数学分析讲义[M]. 北京: 高等教育出版社, 1992 : 309 -342. [3] 华东师范大学数学系. 数学分析[M]. 北京: 高等教育出版社, 2001 : 106 -109. [4] 周永权, 张明, 赵斌. 基于进化策略方法求任意函数的数值积分[J]. 计算机学报 , 2008, 31 (2) : 196-205 ZHOU Yongquan, ZHANG Ming, ZHAO Bin. Solving numerical integration based on evolution strategy method[J]. Chinese Journal of Computers , 2008, 31 (2) : 196-205 [5] 韦杏琼.基于粒子群算法的数值方法研究[D].南宁:广西民族大学, 2009: 11-15. WEI Xingqiong. Research on numerical methods based on PSO[D]. Nanning: Guangxi Uiversity for Nationalities, 2009: 11-15. http://cdmd.cnki.com.cn/article/cdmd-10608-2009255027.htm [6] 聂黎明, 周永权. 基于人工鱼群算法求任意函数的数值积分[J]. 数学的实践与认识 , 2009, 39 (19) : 127-134 NIE Liming, ZHOU Yongquan. Solving numerical integration based on artificial fish-swarm algorithm[J]. Mathematics in Practice and Theory , 2009, 39 (19) : 127-134 [7] 陈欢.杂草优化算法的改进分析及应用研究[D].南宁:广西民族大学, 2013:34-39. CHEN Huan. Improvements and applications of invasive weed optimization algorithm[D]. Nanning: Guangxi University for Nationalities, 2013: 34-39. http://cdmd.cnki.com.cn/Article/CDMD-10608-1013247163.htm [8] YANG Xinshe. A new metaheuristic bat-inspired algorithm[C]//Nature Inspired Cooperative Strategies for Optimization. Berlin: Springer-Verlag, 2010: 65-74. [9] 盛晓华, 叶春明. 蝙蝠算法在PFSP调度问题中的应用研究[J]. 工业工程 , 2013, 16 (1) : 119-124 SHENG Xiaohua, YE Chunming. Application of bat algorithm to permutation flow-shop scheduling problem[J]. Industrial Engineering Journal , 2013, 16 (1) : 119-124 [10] KOMARASAMY G, WAHI A. An optimized k-means clustering technique using bat algorithm[J]. European Journal of Scientific Research , 2012, 84 (2) : 263-273 [11] YANG X S, GANDOMI A H. Bat algorithm: a novel approach for global engineering optimization[J]. Engineering Omputation , 2012, 29 (5) : 464-483 DOI:10.1108/02644401211235834 [12] YANG X S. Bat algorithm for multi-objective optimization[J]. International Journal of Bio-Inspired Computation , 2011, 3 (5) : 267-274 DOI:10.1504/IJBIC.2011.042259 [13] 刘长平, 叶春明. 具有Levy飞行特征的蝙蝠算法[J]. 智能系统学报 , 2013, 8 (3) : 240-246 LIU Changping, YE Chunming. Bat algorithm with the characteristics of Levy flights[J]. CAAI Transaction on Intelligent System , 2013, 8 (3) : 240-246 [14] STORM R, PRICE K. Differential evolution dash a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization , 1997 (11) : 341-359 [15] HAUPT R L, HAUPT S E. Practical genetic algorithm[M]. New Jersey: John Wiley & Sons, 2004 : 1 -25. [16] 李明, 曹德欣. 混合CS算法的DE算法[J]. 计算机工程与应用 , 2013, 49 (9) : 57-60 [17] 刘佳昆, 周永权. 一种最大最小萤光素值人工萤火虫算法[J]. 计算机应用研究 , 2011, 28 (10) : 3662-3664 LIU Jiakun, ZHOU Yongquan. Glowworm swarm optimization algorithm based on max-min luciferin[J]. Application Research of Computers , 2011, 28 (10) : 3662-3664 [18] BURDEN R L, FSIRES J D. Numerical Analysis[M]. Toronto: Thomson Brooks/Cole, 2001 : 206 -212. [19] WANG X H, HE Y G, ZENG Z Z. Numerical integration study based on triangle basis neural network algorithm[J]. Journal of Electronics & Information Technology , 2004, 26 (3) : 394-299 [20] 韦修喜, 周永权, 蓝晓玲. 一种基于泛函网络求数值积分方法研究[J]. 计算机科学 , 2009, 36 (4) : 224-226, 238 WEI Xiuxi, ZHOU Yongquan, LAN Xiaoling. Numerical integration method study based on function network[J]. Computer Science , 2009, 36 (4) : 224-226, 238 [21] 丁丽娟, 程杞元. 数值计算方法[M]. 北京: 北京理工大学出版社, 2005 : 165 -204. [22] 徐理英, 李立军. 数值积分的神经网络算法研究[J]. 系统仿真学报 , 2008, 20 (7) : 1922-1924 XU Liying, LI Lijun. Neural network algorithm for solving numerical integration[J]. Journal of System Simulation , 2008, 20 (7) : 1922-1924
DOI: 10.3969/j.issn.1673-4785.201310014

0

#### 文章信息

XIAO Huihui, DUAN Yanming

Application of the improved bat algorithm in numerical integration

CAAI Transactions on Intelligent Systems, 2014, 9(3): 364-371
http://dx.doi.org/10.3969/j.issn.1673-4785.201310014