胡 飞, 孙自强

(华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237)

一种基于椋鸟群行为的改进型蝙蝠算法

胡 飞, 孙自强

(华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237)

蝙蝠算法是一种新兴的元启发式算法,基本蝙蝠算法(BA)存在寻优精度低、易陷入局部最优等缺点。将椋鸟群的集体性行为引入到基本蝙蝠算法中,有效地提高了算法的搜索范围;引入线性递减权重,用于平衡全局搜索和局部搜索。通过一些测试函数对该算法进行仿真研究,结果表明改进的蝙蝠算法有效地避免了种群个体陷入局部最优,提高了算法的寻优精度,优化效果得到改善。

蝙蝠算法(BA); 椋鸟群行为; 权重; 局部最优

蝙蝠算法是一种新兴的元启发优化算法,该算法可以看作是和声搜索算法和粒子群算法的混合[1]。目前,已有许多经典的优化算法应用于诸多方面。文献[2]将一种改进的混沌蜂群算法应用于流水车间调度,优化调度过程中的最大完成时间,优化效果较好。文献[3]针对化工过程的动态多目标问题,利用一种改进型粒子群算法对其进行优化,测试结果表明该算法能较好地解决工程问题。蝙蝠算法作为新兴的优化算法,同样具有较好的应用前景,已经广泛应用于工程和自然科学领域,如函数优化问题、生产调度问题以及多目标优化问题等。文献[4]将蝙蝠算法应用于一些工程函数寻优,结果表明该算法寻优精度较高。文献[5]将蝙蝠算法应用于混合流水车间调度问题,能够最小化车间调度的完工时间。文献[6]针对多目标优化问题提出了一种多目标蝙蝠算法,应用于一些多目标函数优化,寻优效果较佳。然而蝙蝠算法亦具有粒子群等优化算法的通病,即收敛速度慢、容易陷入局部最优、搜索精度较低。为了提高蝙蝠算法的控制效果,许多研究者对蝙蝠算法开展研究,并对其进行改进。刘长平等[7]提出基于Lévy飞行特征的蝙蝠算法,从算法仿生原理入手,采用Lévy飞行搜索策略,更真实地模拟蝙蝠的捕食行为。Topal 等[8]提出一种动态虚拟蝙蝠算法,将蝙蝠种群分成探索类和开拓类子种群,当探索类蝙蝠进行对外搜索最优值时,开拓类蝙蝠进行局部搜索,寻找最优值。李枝勇等[9]将量子计算引入到蝙蝠算法中,利用量子位对蝙蝠的位置进行编码,利用量子旋转门进行蝙蝠最优位置的搜索。Gandomi 等[10]提出具有混沌搜索策略的蝙蝠算法,并利用不同的混沌函数产生的混沌序列对精英个体进行混沌优化,验证了混沌策略的有效性。Niknam 等[11]提出了一种自适应蝙蝠算法,将自适应方法与蝙蝠算法结合,提高算法的种群多样性及搜索能力,并应用于电力系统中UC问题,能够快速解决UC问题。Wang等[12]提出将差分进化算法与蝙蝠算法相结合,并用于解决UCVA三维路径规划问题,结果表明控制效果较好。

当前针对蝙蝠算法的改进主要有两个方面:(1)针对蝙蝠算法自身机理存在的变量进行改进,包括参数自适应、辅助参数的引入以及搜索策略等;(2)将其他的优化算法与蝙蝠算法相结合,提高基本蝙蝠算法的控制效果[13]。本文提出的改进策略属于第1种,将椋鸟群行为引入到蝙蝠算法中,当全局最优值陷入局部最优时,根据椋鸟群的集体性行为对蝙蝠的位置和速度进行更新。

1 基本蝙蝠算法

1.1基本蝙蝠算法的位置和速度更新

将蝙蝠类比为在当前可行域内分布的搜索点,用目标函数值(适应度函数值)的大小来判断当前蝙蝠所处位置的优劣;将蝙蝠飞行移动探测目标的过程类比为搜索目标函数位置最优解的过程,则可用以下流程和公式来模拟蝙蝠回声定位的行为[14]。初始时刻,需对蝙蝠的频率进行初始化,同时,蝙蝠在飞行过程中也需对其速度和位置进行更新,两者的更新公式如式(1)～ 式(3)所示。

(1)

(2)

(3)

在搜索过程中还需进行局部搜索,公式如下:

(4)

其中:xnew为蝙蝠更新后的位置;xold为蝙蝠更新前的位置;ε∈[-1,1]为随机数;At为整个蝙蝠种群在t时刻的平均响度。

1.2响度和脉冲发射率

在蝙蝠搜寻目标猎物时,需对响度Ai和脉冲发射率ri进行更新。初始阶段,Ai较大,ri较小,搜寻到目标猎物后,Ai减小,ri增大[15]。Ai和ri更新公式如下:

(5)

(6)

2 改进的蝙蝠算法

2.1椋鸟群行为

椋鸟是一种群体性种群,在日常生活中会产生一些壮观的景象。当遇到天敌时,其中一些个体会改变飞行方向,并影响周围个体,如此使得整个种群方向迅速改变,从而躲避天敌的捕食。

由于每个个体都会与周围的个体交流信息,因此由该个体发出的信息会很快传播至整个种群,这种行为称为椋鸟群行为。在椋鸟群中,椋鸟个体一般与其附近的7个个体进行信息交流,这7个个体再分别与其附近的7个个体进行信息交流,进而遍布整个种群,达到整个种群的信息共享。一项分析表明,6个或7个个体组成一个群体交流网络将有效平衡整个种群凝聚性及个体交流,因此个体与其附近的7个个体进行信息交流足以影响整个种群的行为[16]。

2.2引入椋鸟群行为的蝙蝠算法[17](SFBA)

基本蝙蝠算法在搜索过程中易陷入局部最优,缺乏种群多样性。将椋鸟群行为引入基本蝙蝠算法中,有助于增加种群多样性,避免陷入局部最优。当种群迭代结果发生停滞或更差超过上限值(count_limit)时,挑选出一定数目(max_num)适应度值较差的个体,对这些个体的位置和速度进行变换,挑选出全局最优值,替换原先的种群全局最优值。

针对位置变换,依据式(7)对粒子i的位置进行更新。

(7)

针对速度变换,依据式(8)对粒子i的速度进行更新。

(8)

2.3针对位置和速度引入权重

由于固定的惯性权重控制精度不高,控制效果较差,本文针对蝙蝠算法速度和位置更新公式,分别引入权重w1和w2,见式(9)和式(10)。将权重w1由固定权重变为线性递减权重。起初权重较大,加强全局搜索,随着迭代次数的增加,迭代后期,权重减小,有利于提高局部搜索能力。线性递减的权重公式如下:

(9)

(10)

(11)

其中:wmax为w1的上限值;wmin为w1的下限值;Iter为当前迭代次数;Iter_max为最大迭代次数。

2.4SFBA算法流程

(2) 对所有蝙蝠个体计算适应度函数值f(x),找出当前位置最优解x*。

(3) 按照式(1)随机产生频率的新解。

(4) 根据式(9)和式(10)对蝙蝠的速度和位置进行更新,针对速度设置的权重w1使用线性递减权重,见式(11)。

(5) 产生一个随机值rand,若rand大于脉冲发射率ri,则根据式(4),从处在最佳位置的蝙蝠i个体中选取一个解,对该位置最优解进行随机扰动,产生一个局部解xnew替代蝙蝠i的当前位置。

(6) 计算适应度函数值(目标函数值);

(7) 若随机值rand小于响度Ai且更新位置后的目标函数值小于当前目标函数最优值,则接受这个位置新解,并增大脉冲发射率ri和响度Ai,见式(5)、式(6)。

(8) 对位置变动后的蝙蝠重新排列,找出当前位置最优解和适应度函数最优值。

(9) 判断当前适应度最优值是否大于或等于上一代适应度最优值,若是,则计数器count+1(count初始值设为0)。

(10) 判断count是否大于上限值count_limit,若是,则挑选出适应度较差的max_num个个体,利用式(7)与式(8)更新该部分个体位置和速度值,替换原先个体最优值,并从中找出全局最优值,作为当前种群全局最优值,并置count=0。

(11) 当迭代次数小于最大迭代次数时,回到步骤(2)继续迭代搜索最优解。

(12) 算法迭代结束,输出位置全局最优解。

3 算法的参数选择

SFBA算法参数主要包含w1,w2,count_limit,max_num,其中w1主要由wmax和wmin决定,因此需要选择的参数主要为wmax,wmin,w2,count_limit,max_num,这5个参数可以通过实验确定。以Sphere函数为基准进行实验,种群规模设为100,迭代次数Iter_max为500次,分别运行20次,取20次优化结果的平均值作为参考值,确定权值wmax,wmin以及w2的最优值。

表1示出了wmax为0.45、0.46、0.47、0.48、0.49、0.50、0.51、0.52、0.53、0.54、0.55,wmin=0.1,w2=0.50时的运行结果,可以看出,wmax=0.50时算法控制效果较好。

表2示出了wmin为0.05、0.06、0.07、0.08、0.09、0.10、0.11、0.12、0.13、0.14、0.15,wmax=0.50,w2=0.50时的运行结果,可以看出,wmin=0.10时算法控制效果较好。

表3示出了w2为0.45、0.46、0.47、0.48、0.49、0.50、0.51、0.52、0.53、0.54、0.55,wmax=0.50,wmin=0.10时的运行结果,可以看出,w2=0.50时算法控制效果较好。

表1 wmax参数取值表Table 1 Parameter value table of wmax

表2 wmin参数取值表Table 2 Parameter value table of wmin

表3 w2参数取值表Table 3 Parameter value table of w2

表4示出了count_limit为1、2、3、4、5时的运行结果,可以看出,count_limit=3时算法控制效果较好。

表5示出了max_num为13、17、19、22、23时的运行结果,可以看出,max_num=19时算法控制效果较好。

表4 count_limit参数取值表Table 4 Parameter value table of count_limit

表5 max_num参数取值表Table 5 Parameter value table of max_num

综上所述,对于改进型蝙蝠算法,取wmax=0.50,wmin=0.10,w2=0.50,count_limit=3,max_num=19,采用这组参数进行算法测试,可以进一步验证改进型蝙蝠算法的可行性。

4 测试结果

为了评估本文提出的改进型蝙蝠算法的寻优效果,选择5个标准测试函数(如表6所示)进行测试。

表6 标准测试函数Table 6 Benchmark functions

表7 标准测试函数寻优结果对比Table 7 Comparison of Benchmark functions optimization results

测试函数f1,f2,f3均为多峰值测试函数,BA寻优精度较低,控制效果较差,而SFBA均能取得较高的寻优精度,控制效果较好。测试函数f4是一种典型的病态非凸单模函数,难以极小化,从表7中数据可以看出BA和SFBA寻优效果均不理想。测试函数f5为简单的单峰值函数,在自变量取值范围内仅有一个全局极小值点,因而BA的寻优效果还可以,但是相比之下,SFBA的寻优精度更高,控制效果更好。限于篇幅,本文仅给出部分维度的寻优效果,测试函数迭代曲线对比如图1～图5所示。

图1 测试函数f1迭代曲线对比(d=20)Fig.1 Comparison of Benchmark functionf1′s iterative curves (d=20)

图2 测试函数f2迭代曲线对比(d=20)Fig.2 Comparison of Benchmark functionf2′s iterative curves (d=20)

为了进一步验证本文算法的可行性,将SFBA与文献[18]基于微分算子与Lévy飞行策略的蝙蝠算法(DLBA)及文献[19]基于遗传交叉因子的蝙蝠算法(GHBA)进行对比,结果如表8所示。从表8中数据可知,SFBA的寻优效果优于GHBA、DLBA。

图3 测试函数f3迭代曲线对比(d=10)Fig.3 Comparison of Benchmark functionf3′s iterative curves (d=10)

图4 测试函数f4迭代曲线对比(d=10)Fig.4 Comparison of Benchmark functionf4′s iterative curves (d=10)

图5 测试函数f5迭代曲线对比(d=10)Fig.5 Comparison of Benchmark functionf5′s iterative curves (d=10)表8 改进的BA算法在5个测试函数寻优结果对比Table 8 Comparison of improved BA algorithms in 5 Benchmark function optimization results

函数SFBAGHBADLBA最优值平均值最优值平均值最优值平均值f12.8040×10-121.1585×10-91.31×10-73.41×10-24.7174×10-76.4097×10-6f2003.65×10-71.41×10-51.3818×10-75.0103×10-6f300005.9998×10-84.4705×10-6f41.8935×101.8991×107.64×10-51.515.66727.3903f54.2686×10-222.7087×10-188.08×10-195.65×10-184.3057×10-84.8036×10-6

5 改进型蝙蝠算法在PID参数整定中的应用

为了进一步验证本文算法的有效性,将改进型蝙蝠算法应用于PID控制器参数优化中[20]。选取二阶被控对象,传递函数如下:

(12)

采样时间为2 ms,输入一个阶跃信号,采用误差绝对值时间积分性能指标作为参数选择的最小目标函数,为防止能量过大,在目标函数中加入控制输入平方项,最优指标如式(13)所示。

(13)

式中:J表示目标函数;e(t)表示系统误差;u(t)为控制器输出;tu为上升时间;w1,w2,w3为权重值。

为避免超调,采取惩罚功能,一旦出现超调,就将超调量作为最优指标中的一项,此时最优指标如式(14)所示。

ifey(t)<0

(14)

其中:w4为权重值,且w4>>w1;ey(t)=y(t)-y(t-1),y(t)为被控对象输出。

SFBA算法中,种群数为100,wmax=0.50,wmin=0.10,w2=0.5,count_limit=3,max_num=19,PID参数Kp,Ki,Kd取值范围分别为[0,40],[0,4],[0,4],取w1=0.999,w2=0.001,w3=100,w4=2.0。迭代100次后,用BA算法优化PID三参数优化后Kp=31.711 6,Ki=3.354 7,Kd=0.147 2,性能指标J=79.189 6,适应度函数J、Kp、Ki、Kd的优化过程如图6所示。用SFBA算法优化PID三参数优化后Kp=35.053 4,Ki=3.527 6,Kd=0.003 1,性能指标J=78.352 7,适应度函数J,Kp,Ki,Kd的优化过程如图7所示。BA和SFBA算法优化后,PID控制阶跃响应如图8所示。

由图8可知,SFBA算法优化效果优于BA算法,SFBA基本无超调,调节时间较短,响应速度较快。

图6 BA算法迭代曲线Fig.6 Iterative curves of BA algorithm

图7 SFBA算法的迭代曲线Fig.7 Iterative curves of SFBA algorithm

图8 BA算法与SFBA算法的阶跃响应曲线Fig.8 Unit-step response of BA algorithm and SFBA algorithm

6 结 论

本文针对BA算法收敛速度慢、容易陷入局部最优、搜索精度不高等缺点,提出了一种基于椋鸟群行为的蝙蝠算法(SFBA),同时引入线性递减权重平衡全局搜索与局部搜索。通过5个不同的单峰值和多峰值测试函数进行验证,与BA算法相比,SFBA算法优化效果较佳。此外,将SFBA算法应用于PID参数优化,结果表明SFBA算法优化效果优于BA算法。

[1] YANG X S.A new metaheuristic bat-inspired algorithm[J].Physics,2010,284:65-74.

[2] 刘华,顾幸生.改进的混沌蜂群算法在流水线调度中的应用[J].华东理工大学学报(自然科学版),2013,39(3):345-350.

[3] 王珊珊,杜文莉,陈旭,等.基于约束骨干粒子群算法的化工过程动态多目标优化[J].华东理工大学学报(自然科学版),2014,40(4):449-457.

[4] YANG X S,GANDOMI A H.Bat algorithm:A novel approach for global engineering optimization[J].Engineering Computation,2012,29(5):267-289.

[5] MARICHELVAM M K,PRABAHARAN T,YANG X S,etal.Solving hybrid flow shop scheduling problems using bat algorithm[J].International Journal of Logistics Economics & Globalisation,2013,5(1):15-29.

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

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

[8] TOPAL A O,ALTUN O.A novel meta-heuristic algorithm:Dynamic virtual bats algorithm[J].Information Sciences,2016,354:222-235.

[9] 李枝勇,马良,张惠珍.函数优化的量子蝙蝠算法[J].系统管理学报,2014(5):717-722.

[10] GANDOMI A H,YANG X S.Chaotic bat algorithm[J].Journal of Computational Science,2014,5(2):224-232.

[11] NIKNAM T,BAVAFA F,AZIZIPANAH-ABARGHOOEE R.New self-adaptive bat-inspired algorithm for unit comi--tment problem[J].IET Science Measurement Technology,2014,8(6):505-517.

[12] 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.

[13] AFRABANDPEY H,GHAFFARI M,MIRZAEI A,etal.A novel bat algorithm based on chaos for optimization tasks[C]//Iranian Conference on Intelligent Systems.USA:IEEE,2014:1-6.

[14] RAGHAVAN S,MARIMUTHU C,SARWESH P,etal.Bat algorithm for scheduling workflow applications in cloud[C]//International Conference on Electronic Design,Computer Networks & Automated Verification.USA:IEEE,2015:139-144.

[16] YOUNG G F,SCARDOVI L,CAVAGNA A,etal.Starling flock networks manage uncertainty in consensus at low cost[J].PloS Computational Biology,2013,9(1):e1002894.

[17] NETJINDA N,ACHALAKUL T,SIRINAOVAKUL B.Particle swarm optimization inspired by starling flock behavior[J].Applied Soft Computing,2015,35(C):411-422.

[18] XIE J,ZHOU Y,CHEN H.A novel bat algorithm based on differential operator and Lévy flights trajectory[J].Computational Intelligence & Neuroscience,2013(2013):453-812.

[19] 彭泓,丁玉成.基于遗传交叉因子的蝙蝠算法的改进[J].激光杂志,2015(2):23-26.

[20] 刘金琨.先进PID控制MATLAB仿真[M].北京:电子工业出版社,2004.

AnImprovedBatAlgorithmBasedonStarlingFlockBehavior

HUFei,SUNZi-qiang

(KeyLaboratoryofAdvancedChemicalProcessControlandOptimizationTechnology,MinistryofEducation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

Bat algorithm (BA) is a new metaheuristic algorithm.However,the standard BA has some shortcomings,e.g.,low convergence precision and easily relapsing into the local optima.In this work,by introducing the collective behavior of the starling group into BA algorithm,the searching range of the standard BA algorithm can be effectively improved.Besides,a linear decreasing weight is introduced to balance the global search and the local search.Simulation results from Benchmark functions show that the improved algorithm can effectively avoid the local optimum and attain higher convergence precision.

bat algorithm (BA); starling group behavior; weight; local optima

1006-3080(2017)04-0525-08

10.14135/j.cnki.1006-3080.2017.04.011

2016-11-01

胡 飞(1992-),男,安徽人,硕士生,研究方向为智能优化算法。 E-mail:xueshanfeihu1992@163.com

孙自强,E-mail:sunziqiang@ecust.edu.cn

TP301.6

A