反向煙花算法及其應用研究

李浩,柏鵬,張輝,金宏斌,薛俊杰

(1.空軍工程大學裝備發(fā)展與應用研究中心,710051,西安;2.中國人民解放軍空軍預警學院預警情報系,430019,武漢)

?

反向煙花算法及其應用研究

李浩1,2,柏鵬1,張輝2,金宏斌2,薛俊杰1

(1.空軍工程大學裝備發(fā)展與應用研究中心,710051,西安;2.中國人民解放軍空軍預警學院預警情報系,430019,武漢)

針對煙花算法性能提升瓶頸和收斂速度較慢的問題,通過引入反向?qū)W習策略,提出了一種自適應反向?qū)W習算子,并進行了相關收斂性理論證明。通過反向?qū)W習算子與煙花算法相結(jié)合,構(gòu)建了反向煙花算法組,并通過典型測試函數(shù)進行仿真實驗。結(jié)果表明:在相同實驗設置下,反向煙花算法可在原算法尋優(yōu)性能上至少提升10-2精度,并加快了收斂速度。針對混沌同步與控制系統(tǒng)中常見的參數(shù)辨識問題,以混沌同步控制中Lorenz混沌系統(tǒng)參數(shù)辨識問題為應用背景,通過實驗仿真,驗證了反向煙花算法可用于混沌控制系統(tǒng)參數(shù)估計,與現(xiàn)有方法相比較,估計誤差低至10-11,具有較高的估計精度,是一種新的有效的混沌控制系統(tǒng)參數(shù)估計方法,拓展了算法工程應用的范圍。

反向?qū)W習;煙花算法;混沌控制;參數(shù)辨識

群體智能算法原理簡單,具有潛在的并行和分布式特點,通過協(xié)作完成復雜問題的求解,在機器人控制、無人交通駕駛、社會行為預測、通信網(wǎng)絡加強和電力系統(tǒng)調(diào)度等工程領域得到了廣泛運用。受夜空中煙花爆炸現(xiàn)象的啟發(fā),Tan等在2010年提出了一種新的群體智能算法——煙花算法(FWA)[1]。煙花算法具有局部搜索能力和全局搜索能力自調(diào)節(jié)機制,自提出后受到廣泛關注,幾種改進算法相繼被提出。其中,Zheng等對煙花算法的爆炸算子、變異算子、選擇策略和映射規(guī)則等進行了細致的分析,針對存在缺陷提出了增強型煙花算法(EFWA)[2];Zheng等根據(jù)火花適應度值動態(tài)變化來動態(tài)計算煙花爆炸半徑,并提出了動態(tài)搜索煙花算法(dynFWA)[3];Li等根據(jù)最優(yōu)個體和特定個體之間距離來確定煙花爆炸半徑,提出了自適應煙花算法(AFWA)[4]。然而,煙花算法尚處于發(fā)展期,須進一步研究以提升算法的性能。

本文提出了一種自適應反向?qū)W習算子,首先進行收斂性理論證明,然后通過反向算子與煙花算法相結(jié)合,構(gòu)建了反向煙花算法組,并通過實驗仿真驗證了反向煙花算法性能的提升。最后,結(jié)合工程應用中混沌同步與控制系統(tǒng)中常見的參數(shù)辨識問題,以典型的Lorenz混沌控制系統(tǒng)為例,對其參數(shù)辨識問題進行了求解,并通過與多種經(jīng)典算法的實驗仿真比較,驗證了反向煙花算法的有效性、估計精度和魯棒性,拓展了算法的應用范圍。

1 煙花算法

1.1 算法模型

煙花算法來自于對煙花爆炸過程的模擬,算法的執(zhí)行流程如圖1所示[5]。

圖1 煙花算法流程圖

1.2 爆炸算子

在煙花算法中,第i(i=1,2,…,N)個煙花Xi產(chǎn)生的爆炸火花個數(shù)Si的計算公式為

(1)

式中:m為常數(shù);Yworst為當前種群中最差適應度值;f(Xi)為個體Xi的適應度值;ξ為計算機所能表示的一個極小正常數(shù)。同時,為防止生成的Si過多或過少,對Si進行如下修正

(2)

式中:rou(·)為取整函數(shù);a、b為給定常數(shù)。Xi爆炸半徑的計算公式為

(3)

(4)

式中:ran(·)為隨機函數(shù)。

1.3 變異算子

變異算子用來產(chǎn)生高斯火花,目的是為了增加種群多樣性。按照預設參數(shù)產(chǎn)生M個高斯火花,第j(j=1,2,…,M)個火花的第k(k=1,2,…,z)維坐標公式為

(5)

式中:Gau(·)為高斯函數(shù)。

1.4 映射規(guī)則

映射規(guī)則用來修正在坐標更新中超出取值范圍的坐標,公式為

(6)

1.5 選擇策略

在煙花算法中,采用精英保留策略,適應度最好的火花自動保留到下一代,剩下的個體選擇采用輪盤賭的方式,被選擇的概率為

(7)

(8)

式中:R(Xi)為個體Xi與其他個體距離之和;d(Xi,Xj)為個體Xi和Xj之間的歐式距離;K為爆炸和變異算子產(chǎn)生的火花總數(shù)。

2 反向煙花算法

2.1 反向?qū)W習概念

反向?qū)W習(OBL)最初由Tizhoosh于2005年提出,是增強各種優(yōu)化算法尋優(yōu)能力的有效方法[6]。OBL的主要思想是:同時計算候選解及其反向解,將會增加發(fā)現(xiàn)更接近于全局最優(yōu)解的有效解的概率,最終加速優(yōu)化算法的收斂。

定義1 反向數(shù)(opposite number):令實數(shù)x∈[a,b],則x的反向數(shù)為

(9)

類似地,將定義1推廣至更高維的D維空間,就可得到定義2。

(10)

在OBL基礎上,文獻[7]提出尋優(yōu)效率更優(yōu)的準反向數(shù)(quasi-opposite number)為

(11)

文獻[8]提出的準反射反向數(shù)(quasi-reflection opposite number)為

(12)

2.2 自適應反向?qū)W習

由2.1節(jié)定義,一維空間反向數(shù)如圖2所示。

圖2 一維空間反向數(shù)示意圖

[7-8]中,QOBL和QROBL相對于OBL的收斂性已經(jīng)得到證明。因此,只需要證明AOBL收斂性優(yōu)于QOBL、QROBL即可。

(13)

(14)

(15)

(16)

為了更加直觀形象地說明AOBL的收斂性,選取二維Egg函數(shù)f(Z)=X2+Y2+25(sin2X+sin2Y)進行演示,其中X,Y∈[-2π,2π]。該函數(shù)在中心點(0,0)的位置取得全局最小值0,隨機產(chǎn)生規(guī)模N=30的個體分布在解空間,隨后分別利用OBL和AOBL對初始個體進行處理,結(jié)果如圖3所示。

(a)函數(shù)三維圖 (b)隨機初始化個體分布

(c)OBL個體分布 (d)QOBL個體分布

(e)QROBL個體分布 (f)AOBL個體分布圖3 目標函數(shù)及各種反向個體分布圖

由圖3可以看出,經(jīng)過各種反向算子處理之后的個體會比之前更接近于全局最優(yōu)點,OBL比隨機更接近最優(yōu)點,而經(jīng)過本文AOBL處理之后的群體最為密集接近全局最優(yōu)點,直觀地說明了AOBL的收斂性更好,也間接印證了定理1和定理2的正確性。

2.3 反向煙花算法設計

為了詳細論證反向?qū)W習與煙花算法結(jié)合的性能,文中使用OBL和AOBL分別與EFWA煙花算法按照排列組合形成反向煙花算法,形成的反向煙花算法按照“算法名稱-算子名稱”進行編排和命名,如EFWA-OBL表示EFWA與OBL生成的反向增強煙花算法,EFWA-AOBL表示EFWA與AOBL生成的自適應反向增強煙花算法。

2.4 仿真及分析

為充分驗證算法的性能,分別采用以下4個典型標準函數(shù)進行計算。

Matyas函數(shù)為

-10≤xi≤10

Sphere函數(shù)為

Quadric函數(shù)為

Ackley函數(shù)

(a)Matyas函數(shù)尋優(yōu)結(jié)果 (b)Sphere函數(shù)尋優(yōu)結(jié)果

(c)Quadric函數(shù)尋優(yōu)結(jié)果 (d)Ackley函數(shù)尋優(yōu)結(jié)果圖4 基于EFWA的反向煙花算法測試結(jié)果

由圖4可以看出,在計算次數(shù)較小的情況下,通過引入基本反向?qū)W習算子OBL,對于單峰的Matyas和Sphere函數(shù),確實可以提高算法性能,但提升有限,對于多峰的Quadric和Ackley函數(shù),OBL對煙花算法提升效果不明顯。本文提出的自適應反向算子AOBL與EFWA融合形成的EFWA-AOBL則能大幅度提升算法性能,在所有4個測試函數(shù)上均獲得了最好結(jié)果。從圖4中可以看出,融入了自適應反向算子AOBL之后,算法保持了優(yōu)良域的開采性能,具有良好持續(xù)的最優(yōu)解尋優(yōu)能力,這與自適應反向算子的機理有關。由理論證明可知,融入AOBL的種群比未融入AOBL和融入基本OBL的種群更為接近最優(yōu)解。

3 算法應用研究

3.1 應用流程

對于n維系統(tǒng)

(17)

式中:X=(x1,x2,…,xn)T為原系統(tǒng)n維狀態(tài)變量;X0為系統(tǒng)初始狀態(tài);θ=(θ1,θ2,…,θn)T為混沌系統(tǒng)參數(shù)的真實值。在系統(tǒng)結(jié)構(gòu)已知的前提下,估計系統(tǒng)為

(18)

(19)

圖5 混沌控制系統(tǒng)參數(shù)估計原理圖

3.2 仿真及分析

為充分驗證算法應用的有效性,選取經(jīng)典的Lorenz系統(tǒng)作為實驗對象。由于針對單、雙參數(shù)估計的研究相對較多,而3個參數(shù)完全未知的研究較少且更為復雜,所以直接對Lorenz系統(tǒng)進行3個參數(shù)完全未知情況下的參數(shù)估計。Lorenz系統(tǒng)狀態(tài)方程為

(20)

式中:x、y、z為系統(tǒng)狀態(tài)變量,取a=10、b=28、c=8/3為參數(shù)真實值。采用FWA、EFWA、dynFWA、AFWA和EFWA-AOBL對3個參數(shù)均未知情況下的Lorenz系統(tǒng)參數(shù)進行估計。待估計參數(shù)的初始范圍為:9≤a≤11,20≤b≤30,2≤c≤3。FWA、EFWA、dynFWA和AFWA的參數(shù)按照參考文獻[1-4]進行設置,蒙特卡洛仿真20次統(tǒng)計平均值,并與文獻[9]中的遺傳算法(GA)、地理生物優(yōu)化算法(BBO)、粒子群算法(PSO)和差分進化算法(DE)分別參照文獻[9-12]進行最優(yōu)設置,具體是:GA個體總數(shù)為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。參數(shù)仿真結(jié)果如圖6和表1所示。

由圖6和表1可知,在小規(guī)模種群、較少迭代次數(shù)、較大范圍尋優(yōu)空間的情況下,基本煙花算法FWA對復雜混沌系統(tǒng)參數(shù)估計能力不足,這是因為FWA中最優(yōu)個體容易陷入局部極值。典型改進算法EFWA、dynFWA和AFWA都能夠用于混沌系統(tǒng)參數(shù)估計,且性能高于文獻[9-12]中的GA、PSO、BBO和DE算法,但求解精度有限,在3個參數(shù)均未知的情況下,估計值與系統(tǒng)真實值仍有微小差距。融入AOBL的EFWA-AOBL算法能夠準確估計Lorenz系統(tǒng)的參數(shù),目標函數(shù)的尋優(yōu)精度最好可達到10-11數(shù)量級,最差也可達到10-9數(shù)量級,在迭代10余次之后即能迅速收斂到真實值附近。與GA、PSO、BBO、DE、FWA、EFWA、dynFWA和AFWA這8種算法相比,無論從得到的最優(yōu)值、平均值還是最差值都要相對更優(yōu),特別是EFWA-AOBL與EFWA算法相比,融入AOBL之后,其最優(yōu)值、平均值和最差值都要高近10-3數(shù)量級,突顯了算法的求解精度和計算的穩(wěn)定性,也側(cè)面印證了AOBL算子對于煙花算法性能提升的明顯作用,同時也證明了煙花算法在混沌控制系統(tǒng)參數(shù)估計中應用的可能性。

4 結(jié) 論

本文針對煙花算法性能提升瓶頸和收斂速度較慢的問題,通過引入反向?qū)W習策略,提出了一種自適應反向?qū)W習算子,并進行了相關收斂性理論證明,進而將其引入煙花算法中,構(gòu)建了反向煙花算法,并通過典型測試函數(shù)驗證了反向煙花算法性能的提升。

(a)適應度J收斂曲線圖

(b)參數(shù)a收斂曲線

(c)參數(shù)b收斂曲線

(d)參數(shù)c收斂曲線

參數(shù)算法GAPSOBBODEFWAEFWAdynFWAAFWAEFWA-OABL最優(yōu)值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最優(yōu)值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最優(yōu)值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最優(yōu)值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

最后針對混沌同步與控制系統(tǒng)中常見的參數(shù)辨識問題,以典型的Lorenz混沌系統(tǒng)為例,驗證了煙花算法可用于混沌系統(tǒng)參數(shù)估計,并通過與已有多種算法的仿真比較可知,本文提出的反向煙花算法具有較高的估計精度,估計誤差最低可達到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] 戴棟, 馬西奎, 李富才, 等. 一種基于遺傳算法的混沌系統(tǒng)參數(shù)估計方法 [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]林劍, 許力. 基于混合地理優(yōu)化的混沌系統(tǒng)參數(shù)估計 [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.

[本刊相關文獻鏈接]

王安麟,孟慶華,李文嘉,等.液力變矩器機構(gòu)變量交互作用研究.2015,49(9):1-7.[doi:10.7652/xjtuxb201509001]

仲繼澤,徐自力,方宇,等.葉片有限元分析中彈塑性過渡區(qū)應力奇異產(chǎn)生原因及解決方法.2015,49(9):47-51.[doi:10.7652/xjtuxb201509009]

薛詠,馮博琴,武艷芳.ABox推理計算實體相似度.2015,49(9):70-76.[doi:10.7652/xjtuxb201509013]

丁建坤,韓德強,楊藝.最短特征線段多分類器系統(tǒng)設計.2015,49(9):77-83.[doi:10.7652/xjtuxb201509014]

周遠,周玉生,劉權(quán),等.一種適用于圖像拼接的DSIFT算法研究.2015,49(9):84-90.[doi:10.7652/xjtuxb201509015]

毛彥斌,張選平,楊曉剛.偽DNA密碼圖像加密算法研究.2015,49(9):91-98.[doi:10.7652/xjtuxb201509016]

龐霞,劉凌,劉崇新,等.利用異結(jié)構(gòu)同步對鐵磁混沌電路的非線性反饋控制.2015,49(4):18-23.[doi:10.7652/xjtuxb 201504004]

孟慶虎,孟慶豐,朱永生,等.用于機械系統(tǒng)固有頻率及阻尼比計算的改進頻域方法.2015,49(8):1-5.[doi:10.7652/xjtuxb201508001]

張東偉,郭英,齊子森,等.采用空間極化時頻分布的跳頻信號多參數(shù)聯(lián)合估計算法.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