反向烟花算法及其应用研究

李浩,柏鹏,张辉,金宏斌,薛俊杰

(1.空军工程大学装备发展与应用研究中心,710051,西安;2.中国人民解放军空军预警学院预警情报系,430019,武汉)



反向烟花算法及其应用研究

李浩1,2,柏鹏1,张辉2,金宏斌2,薛俊杰1

(1.空军工程大学装备发展与应用研究中心,710051,西安;2.中国人民解放军空军预警学院预警情报系,430019,武汉)

针对烟花算法性能提升瓶颈和收敛速度较慢的问题,通过引入反向学习策略,提出了一种自适应反向学习算子,并进行了相关收敛性理论证明。通过反向学习算子与烟花算法相结合,构建了反向烟花算法组,并通过典型测试函数进行仿真实验。结果表明:在相同实验设置下,反向烟花算法可在原算法寻优性能上至少提升10-2精度,并加快了收敛速度。针对混沌同步与控制系统中常见的参数辨识问题,以混沌同步控制中Lorenz混沌系统参数辨识问题为应用背景,通过实验仿真,验证了反向烟花算法可用于混沌控制系统参数估计,与现有方法相比较,估计误差低至10-11,具有较高的估计精度,是一种新的有效的混沌控制系统参数估计方法,拓展了算法工程应用的范围。

反向学习;烟花算法;混沌控制;参数辨识

群体智能算法原理简单,具有潜在的并行和分布式特点,通过协作完成复杂问题的求解,在机器人控制、无人交通驾驶、社会行为预测、通信网络加强和电力系统调度等工程领域得到了广泛运用。受夜空中烟花爆炸现象的启发,Tan等在2010年提出了一种新的群体智能算法——烟花算法(FWA)[1]。烟花算法具有局部搜索能力和全局搜索能力自调节机制,自提出后受到广泛关注,几种改进算法相继被提出。其中,Zheng等对烟花算法的爆炸算子、变异算子、选择策略和映射规则等进行了细致的分析,针对存在缺陷提出了增强型烟花算法(EFWA)[2];Zheng等根据火花适应度值动态变化来动态计算烟花爆炸半径,并提出了动态搜索烟花算法(dynFWA)[3];Li等根据最优个体和特定个体之间距离来确定烟花爆炸半径,提出了自适应烟花算法(AFWA)[4]。然而,烟花算法尚处于发展期,须进一步研究以提升算法的性能。

本文提出了一种自适应反向学习算子,首先进行收敛性理论证明,然后通过反向算子与烟花算法相结合,构建了反向烟花算法组,并通过实验仿真验证了反向烟花算法性能的提升。最后,结合工程应用中混沌同步与控制系统中常见的参数辨识问题,以典型的Lorenz混沌控制系统为例,对其参数辨识问题进行了求解,并通过与多种经典算法的实验仿真比较,验证了反向烟花算法的有效性、估计精度和鲁棒性,拓展了算法的应用范围。

1 烟花算法

1.1 算法模型

烟花算法来自于对烟花爆炸过程的模拟,算法的执行流程如图1所示[5]。

图1 烟花算法流程图

1.2 爆炸算子

在烟花算法中,第i(i=1,2,…,N)个烟花Xi产生的爆炸火花个数Si的计算公式为

(1)

式中:m为常数;Yworst为当前种群中最差适应度值;f(Xi)为个体Xi的适应度值;ξ为计算机所能表示的一个极小正常数。同时,为防止生成的Si过多或过少,对Si进行如下修正

(2)

式中:rou(·)为取整函数;a、b为给定常数。Xi爆炸半径的计算公式为

(3)

(4)

式中:ran(·)为随机函数。

1.3 变异算子

变异算子用来产生高斯火花,目的是为了增加种群多样性。按照预设参数产生M个高斯火花,第j(j=1,2,…,M)个火花的第k(k=1,2,…,z)维坐标公式为

(5)

式中:Gau(·)为高斯函数。

1.4 映射规则

映射规则用来修正在坐标更新中超出取值范围的坐标,公式为

(6)

1.5 选择策略

在烟花算法中,采用精英保留策略,适应度最好的火花自动保留到下一代,剩下的个体选择采用轮盘赌的方式,被选择的概率为

(7)

(8)

式中:R(Xi)为个体Xi与其他个体距离之和;d(Xi,Xj)为个体Xi和Xj之间的欧式距离;K为爆炸和变异算子产生的火花总数。

2 反向烟花算法

2.1 反向学习概念

反向学习(OBL)最初由Tizhoosh于2005年提出,是增强各种优化算法寻优能力的有效方法[6]。OBL的主要思想是:同时计算候选解及其反向解,将会增加发现更接近于全局最优解的有效解的概率,最终加速优化算法的收敛。

定义1 反向数(opposite number):令实数x∈[a,b],则x的反向数为

(9)

类似地,将定义1推广至更高维的D维空间,就可得到定义2。

(10)

在OBL基础上,文献[7]提出寻优效率更优的准反向数(quasi-opposite number)为

(11)

文献[8]提出的准反射反向数(quasi-reflection opposite number)为

(12)

2.2 自适应反向学习

由2.1节定义,一维空间反向数如图2所示。

图2 一维空间反向数示意图

[7-8]中,QOBL和QROBL相对于OBL的收敛性已经得到证明。因此,只需要证明AOBL收敛性优于QOBL、QROBL即可。

(13)

(14)

(15)

(16)

为了更加直观形象地说明AOBL的收敛性,选取二维Egg函数f(Z)=X2+Y2+25(sin2X+sin2Y)进行演示,其中X,Y∈[-2π,2π]。该函数在中心点(0,0)的位置取得全局最小值0,随机产生规模N=30的个体分布在解空间,随后分别利用OBL和AOBL对初始个体进行处理,结果如图3所示。

(a)函数三维图 (b)随机初始化个体分布

(c)OBL个体分布 (d)QOBL个体分布

(e)QROBL个体分布 (f)AOBL个体分布图3 目标函数及各种反向个体分布图

由图3可以看出,经过各种反向算子处理之后的个体会比之前更接近于全局最优点,OBL比随机更接近最优点,而经过本文AOBL处理之后的群体最为密集接近全局最优点,直观地说明了AOBL的收敛性更好,也间接印证了定理1和定理2的正确性。

2.3 反向烟花算法设计

为了详细论证反向学习与烟花算法结合的性能,文中使用OBL和AOBL分别与EFWA烟花算法按照排列组合形成反向烟花算法,形成的反向烟花算法按照“算法名称-算子名称”进行编排和命名,如EFWA-OBL表示EFWA与OBL生成的反向增强烟花算法,EFWA-AOBL表示EFWA与AOBL生成的自适应反向增强烟花算法。

2.4 仿真及分析

为充分验证算法的性能,分别采用以下4个典型标准函数进行计算。

Matyas函数为

-10≤xi≤10

Sphere函数为

Quadric函数为

Ackley函数

(a)Matyas函数寻优结果 (b)Sphere函数寻优结果

(c)Quadric函数寻优结果 (d)Ackley函数寻优结果图4 基于EFWA的反向烟花算法测试结果

由图4可以看出,在计算次数较小的情况下,通过引入基本反向学习算子OBL,对于单峰的Matyas和Sphere函数,确实可以提高算法性能,但提升有限,对于多峰的Quadric和Ackley函数,OBL对烟花算法提升效果不明显。本文提出的自适应反向算子AOBL与EFWA融合形成的EFWA-AOBL则能大幅度提升算法性能,在所有4个测试函数上均获得了最好结果。从图4中可以看出,融入了自适应反向算子AOBL之后,算法保持了优良域的开采性能,具有良好持续的最优解寻优能力,这与自适应反向算子的机理有关。由理论证明可知,融入AOBL的种群比未融入AOBL和融入基本OBL的种群更为接近最优解。

3 算法应用研究

3.1 应用流程

对于n维系统

(17)

式中:X=(x1,x2,…,xn)T为原系统n维状态变量;X0为系统初始状态;θ=(θ1,θ2,…,θn)T为混沌系统参数的真实值。在系统结构已知的前提下,估计系统为

(18)

(19)

图5 混沌控制系统参数估计原理图

3.2 仿真及分析

为充分验证算法应用的有效性,选取经典的Lorenz系统作为实验对象。由于针对单、双参数估计的研究相对较多,而3个参数完全未知的研究较少且更为复杂,所以直接对Lorenz系统进行3个参数完全未知情况下的参数估计。Lorenz系统状态方程为

(20)

式中:x、y、z为系统状态变量,取a=10、b=28、c=8/3为参数真实值。采用FWA、EFWA、dynFWA、AFWA和EFWA-AOBL对3个参数均未知情况下的Lorenz系统参数进行估计。待估计参数的初始范围为:9≤a≤11,20≤b≤30,2≤c≤3。FWA、EFWA、dynFWA和AFWA的参数按照参考文献[1-4]进行设置,蒙特卡洛仿真20次统计平均值,并与文献[9]中的遗传算法(GA)、地理生物优化算法(BBO)、粒子群算法(PSO)和差分进化算法(DE)分别参照文献[9-12]进行最优设置,具体是:GA个体总数为20,个体由20位的二进制编码表示,Pmin=2,Pmax=3,ε=0.000 1,交叉概率为0.8,变异概率为0.1;BBO种群大小为50,最大迁徙率E=I=1,最大变异率mmax=0.001,邻域搜索范围w=0.5;PSO种群大小为120,c1=c2=2.0,w=0.4,Pr=0.8,Pm=1;DE种群大小为120,缩放因子为0.8,交叉因子为0.1。参数仿真结果如图6和表1所示。

由图6和表1可知,在小规模种群、较少迭代次数、较大范围寻优空间的情况下,基本烟花算法FWA对复杂混沌系统参数估计能力不足,这是因为FWA中最优个体容易陷入局部极值。典型改进算法EFWA、dynFWA和AFWA都能够用于混沌系统参数估计,且性能高于文献[9-12]中的GA、PSO、BBO和DE算法,但求解精度有限,在3个参数均未知的情况下,估计值与系统真实值仍有微小差距。融入AOBL的EFWA-AOBL算法能够准确估计Lorenz系统的参数,目标函数的寻优精度最好可达到10-11数量级,最差也可达到10-9数量级,在迭代10余次之后即能迅速收敛到真实值附近。与GA、PSO、BBO、DE、FWA、EFWA、dynFWA和AFWA这8种算法相比,无论从得到的最优值、平均值还是最差值都要相对更优,特别是EFWA-AOBL与EFWA算法相比,融入AOBL之后,其最优值、平均值和最差值都要高近10-3数量级,突显了算法的求解精度和计算的稳定性,也侧面印证了AOBL算子对于烟花算法性能提升的明显作用,同时也证明了烟花算法在混沌控制系统参数估计中应用的可能性。

4 结 论

本文针对烟花算法性能提升瓶颈和收敛速度较慢的问题,通过引入反向学习策略,提出了一种自适应反向学习算子,并进行了相关收敛性理论证明,进而将其引入烟花算法中,构建了反向烟花算法,并通过典型测试函数验证了反向烟花算法性能的提升。

(a)适应度J收敛曲线图

(b)参数a收敛曲线

(c)参数b收敛曲线

(d)参数c收敛曲线

参数算法GAPSOBBODEFWAEFWAdynFWAAFWAEFWA-OABL最优值10.06719.995310.006810.000010.018810.000110.000610.000010.0000a平均值10.139810.018410.018310.01019.98429.999910.003210.000310.0000最差值10.929010.60829.944010.05419.890510.000910.026410.014610.0000最优值27.922128.007127.996827.999927.987527.999928.000428.000028.0000b平均值27.742727.993427.991327.993928.012028.000127.997627.999528.0000最差值26.127627.704428.036027.971828.207227.998927.977527.983928.0000最优值2.66352.66702.66672.66672.66902.66672.66662.66672.6667c平均值2.64862.66632.66712.66662.66542.66672.66762.66672.6667最差值2.56212.65722.65092.66552.66472.66672.67362.66782.6667最优值4.31070.04862.36×10-52.42×10-78.54×10-41.85×10-84.06×10-63.61×10-104.81×10-11J平均值943.76294.18280.00333.62×10-42.28×10-22.18×10-71.07×10-31.35×10-47.86×10-10最差值6461.48039.40600.02890.00171.01×10-12.66×10-63.75×10-36.39×10-44.45×10-9

最后针对混沌同步与控制系统中常见的参数辨识问题,以典型的Lorenz混沌系统为例,验证了烟花算法可用于混沌系统参数估计,并通过与已有多种算法的仿真比较可知,本文提出的反向烟花算法具有较高的估计精度,估计误差最低可达到10-11,进一步拓展了算法的应用范围。

致谢 感谢北京大学计算智能实验室谭营教授和余超同学在本文撰写过程中的悉心指导和帮助。

参考文献:

[1] TAN Y, ZHU Y C. Fireworks algorithm for optimization [C]∥Proceedings of 1st International Conference on Swarm Intelligence. Berlin, Germany: Springer, 2010: 355-364.

[2] ZHENG S Q, JANECEK A, TAN Y. Enhanced fireworks algorithm [C]∥Proceedings of 2013 IEEE Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 2013: 2069-2077.

[3] ZHENG S Q, JANECEK A, LI J. Dynamic search in fireworks algorithm [C]∥Proceedings of 2014 IEEE Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 2014: 3222-3229.

[4] LI J, ZHENG S Q, TAN Y. Adaptive fireworks algorithm [C]∥Proceedings of 2014 IEEE Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 2014: 3214-3221.

[5] TAN Y. Fireworks algorithm: a swarm intelligence optimization method [M]. Berlin, Germany: Springer, 2015: 20.

[6] TIZHOOSH H R. Opposition-based learning: a new scheme for machine intelligence [C]∥Proceedings of International Conference on Computing Intelligence for Modeling, Control and Automatic. Piscataway, NJ, USA: IEEE, 2005: 695-701.

[7] RAHNAMAYAN S, TIZHOOSH H R, SALAMA M A. Quasi-oppositional differential evolution [C]∥Proceedings of IEEE Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 2007: 2229-2236.

[8] ERGEZER M, SIMON D, DU D W. Oppositional biogeography-based optimization [C]∥Proceedings of IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ, USA: IEEE, 2009: 1009-1014.

[9] 戴栋, 马西奎, 李富才, 等. 一种基于遗传算法的混沌系统参数估计方法 [J]. 物理学报, 2002, 51(11): 2459-2462. DAI Dong, MA Xikui, LI Fucai, et al. An approach of parameter estimation for a chaotic system based on genetic algorithm [J]. Acta Physica Sinica, 2002, 51(11): 2459-2462.

[10]林剑, 许力. 基于混合地理优化的混沌系统参数估计 [J]. 物理学报, 2013, 62(3): 030505. LIN Jian, XU Li. Parameter estimation for chaotic systems based on hybrid biogeography-based optimization [J]. Acta Physica Sinica, 2013, 62(3): 030505.

[11]HE Q, WANG L, LIU B. Parameter estimation for chaotic systems by particle swarm optimization [J]. Chaos, Solitons & Fractals, 2007, 34(2): 654-661.

[12]PENG B, LIU B, ZHANG F Y, et al. Differential evolution algorithm-based parameter estimation for chaotic systems [J]. Chaos, Solitons & Fractals, 2009, 39(5): 2110-2118.

[本刊相关文献链接]

王安麟,孟庆华,李文嘉,等.液力变矩器机构变量交互作用研究.2015,49(9):1-7.[doi:10.7652/xjtuxb201509001]

仲继泽,徐自力,方宇,等.叶片有限元分析中弹塑性过渡区应力奇异产生原因及解决方法.2015,49(9):47-51.[doi:10.7652/xjtuxb201509009]

薛咏,冯博琴,武艳芳.ABox推理计算实体相似度.2015,49(9):70-76.[doi:10.7652/xjtuxb201509013]

丁建坤,韩德强,杨艺.最短特征线段多分类器系统设计.2015,49(9):77-83.[doi:10.7652/xjtuxb201509014]

周远,周玉生,刘权,等.一种适用于图像拼接的DSIFT算法研究.2015,49(9):84-90.[doi:10.7652/xjtuxb201509015]

毛彦斌,张选平,杨晓刚.伪DNA密码图像加密算法研究.2015,49(9):91-98.[doi:10.7652/xjtuxb201509016]

庞霞,刘凌,刘崇新,等.利用异结构同步对铁磁混沌电路的非线性反馈控制.2015,49(4):18-23.[doi:10.7652/xjtuxb 201504004]

孟庆虎,孟庆丰,朱永生,等.用于机械系统固有频率及阻尼比计算的改进频域方法.2015,49(8):1-5.[doi:10.7652/xjtuxb201508001]

张东伟,郭英,齐子森,等.采用空间极化时频分布的跳频信号多参数联合估计算法.2015,49(8):17-23.[doi:10.7652/xjtuxb201508004]

巴斌,郑娜娥,朱世磊,等.利用蒙特卡罗的最大似然时延估计算法.2015,49(8):24-30.[doi:10.7652/xjtuxb201508005]

(编辑 赵炜)

Backward Fireworks Algorithm and Application Research

LI Hao1,2,BAI Peng1,ZHANG Hui2,JIN Hongbin2,XUE Junjie1

(1. Equipment Development and Application Research Center, Air Force Engineering University, Xi’an 710051, China;2. Department of Intelligence, Air Force Early-Warning Academy, Wuhan 430019, China)

Aiming at the performance bottlenecks and slow convergence of fireworks algorithm (FWA), an adaptive backward learning operator (ABLO) is proposed through the introduction of backward learning strategy, and its convergence performance is proved theoretically. By combining FWA with ABLO, a set of hybrid FWA is proposed and verified by typical test functions. The results show that under the same experimental setup, the backward fireworks algorithm can improve the computation accuracy by at least 10-2in the optimization performance of original algorithm and the convergence rate is enhanced. Finally the algorithm is applied to identify the parameters of Lorenz chaotic system. Through simulation experiments, it is verified that this algorithm can be used for parameter identification of chaotic control systems. Compared with other swarm intelligence algorithms, its identification error is as low as 10-11. It is a novel and effective parameter identification method for chaotic control systems.

backward learning; fireworks algorithm; chaotic control; parameter identification

2015-04-09。

李浩(1981—),男,博士,讲师。

国家自然科学基金资助项目(61502522,61472442,61502534)。

10.7652/xjtuxb201511014

TP18;TP273

A

0253-987X(2015)11-0082-07