基于混沌的螢火蟲改進(jìn)粒子濾波算法研究*

朱 超， 劉以安， 薛 松

(1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122； 2.中國艦船研究院，北京 100192)

計(jì)算與測試

基于混沌的螢火蟲改進(jìn)粒子濾波算法研究*

朱 超1， 劉以安1， 薛 松2

(1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122； 2.中國艦船研究院，北京 100192)

針對常規(guī)的粒子濾波算法存在粒子權(quán)值退化和采樣粒子貧化以及需要大量粒子才能進(jìn)行比較準(zhǔn)確的狀態(tài)估計(jì)的問題，提出了一種基于混沌的螢火蟲改進(jìn)粒子濾波算法。利用混沌系統(tǒng)所具有的遍歷性和隨機(jī)性初始化粒子群，使得初始粒子分布更加均勻，同時(shí)向常規(guī)粒子濾波算法中引進(jìn)螢火蟲算法的尋優(yōu)機(jī)制，使得粒子能夠向高似然區(qū)域運(yùn)動，提高了濾波精度，并對部分權(quán)值優(yōu)秀粒子進(jìn)行混沌細(xì)搜索，對部分權(quán)值低的粒子進(jìn)行再生，提高了種群多樣性。實(shí)驗(yàn)表明：該方法尤其是在粒子種群數(shù)量較小的情況下，較常規(guī)粒子濾波精度更高，并有效地改善了權(quán)值退化和樣本貧化問題。

混沌優(yōu)化； 螢火蟲算法； 粒子濾波； 權(quán)值退化

0 引 言

粒子濾波(particle filtering,PF)是一種基于蒙特—卡羅思想的貝葉斯濾波技術(shù)[1]。常規(guī)粒子濾波經(jīng)過多次迭代后，小權(quán)值粒子會發(fā)生權(quán)值退化，同時(shí)重采樣僅復(fù)制大權(quán)值的樣本，又會導(dǎo)致粒子樣本貧化。

針對粒子濾波的權(quán)值退化和樣本貧化問題，文獻(xiàn)[2]提出了一種改進(jìn)權(quán)值選優(yōu)粒子濾波，一定程度上改善了權(quán)值退化問題。文獻(xiàn)[3]提出了一種加權(quán)逼近的粒子濾波算法，緩解了權(quán)值退化，但在多次迭代后容易導(dǎo)致樣本貧化。文獻(xiàn)[4]提出了基于權(quán)值選擇的粒子濾波，通過對預(yù)測粒子集樣本進(jìn)行預(yù)處理來增加樣本有效數(shù)，但容易導(dǎo)致權(quán)值的退化。文獻(xiàn)[5]提出了一種螢火蟲智能優(yōu)化粒子濾波(firefly algorithm intelligence optimized particle filtering,FA-PF)算法，引進(jìn)了螢火蟲尋優(yōu)機(jī)制，然而對小權(quán)值的樣本吸引小，容易導(dǎo)致粒子權(quán)值退化。

本文通過在常規(guī)粒子濾波框架下引入螢火蟲算法尋優(yōu)機(jī)制，并利用混沌的遍歷性、隨機(jī)性的特點(diǎn)進(jìn)行優(yōu)化，用混沌序列初始化種群，使得初始粒子能夠更加平均地接近真實(shí)狀態(tài)[6]。對優(yōu)秀的螢火蟲進(jìn)行混沌細(xì)搜索，對相對較差的螢火蟲進(jìn)行隨機(jī)再生，從而在一定程度上保持了樣本的多樣性，減輕粒子權(quán)值退化程度，增加了濾波精度，尤其在粒子數(shù)較少的情況下，通過算法驗(yàn)證，能夠得到更高的濾波精度和穩(wěn)定性，從而減少了迭代次數(shù)和運(yùn)算量。

1 粒子濾波算法

假設(shè)非線性系統(tǒng)的狀態(tài)方程和觀測方程如下

(1)

式中 xk為狀態(tài)值；yk為觀測值；vk-1和wk分別為過程噪聲和量測噪聲。若初始概率密度為p(x0|y0)=p(x0)，則狀態(tài)方程的預(yù)測方程為

(2)

狀態(tài)更新方程為

(3)

設(shè)重要性函數(shù)為q(x0∶k-1|y1∶k)，則權(quán)值公式為

(4)

(5)

式中 δ(·)為狄拉克函數(shù)。

概率密度更新公式為

(6)

最后進(jìn)行權(quán)值歸一化，并輸出狀態(tài)

(7)

(8)

2 螢火蟲算法

算法描述:螢火蟲被比其亮度大的螢火蟲所吸引；螢火蟲的吸引度和亮度成正比，亮度隨著距離的增加而減少；如果沒有一個比其自身更亮的螢火蟲，將隨機(jī)移動。算法主要參數(shù)描述如下：

1)螢火蟲相對亮度為

I=I0×e-γrij

(9)

式中 I0為最大熒光亮度; γ為光強(qiáng)吸收系數(shù);rij為兩螢火蟲的空間距離。

2)螢火蟲吸引度為

β=β0×e-γrij

(10)

式中 β0為最大吸引度。

3)螢火蟲位置更新為

xi=xj+β(xi-xj)+α×(rand-0.5)

(11)

式中 xi,xj為螢火蟲位置;α為步長因子;rand為[0,1]上服從均勻分布的隨機(jī)數(shù)[7]。

3 混沌優(yōu)化策略

文獻(xiàn)[8]對不同的混沌映射算法進(jìn)行了性能分析。其中，Kent混沌映射在區(qū)間(0,1)具有更加優(yōu)秀的遍歷均勻性。Kent混沌映射的數(shù)學(xué)表達(dá)式為

(12)

混沌優(yōu)化策略：將待優(yōu)化值映射到混沌空間(0,1)上，代入式(12)得到混沌序列，再將混沌序列按照尺度變換還原到解空間中，重新計(jì)算函數(shù)值，如果出現(xiàn)更優(yōu)的解，則該解替代原解[9]。為了提高搜索效率，可以根據(jù)式(13)動態(tài)收縮搜索區(qū)域

(13)

式中 [xmin,j,xmax,j]為第j維變量的搜索范圍；xg,j為當(dāng)前的最優(yōu)值；ρ為搜索因子

(14)

式中t為當(dāng)前搜索次數(shù)。

4 混沌螢火蟲優(yōu)化粒子濾波算法

4.1 優(yōu)化策略

本文算法以粒子濾波作為濾波框架，使用Kent混沌初始化粒子群，使得初始的粒子能夠更加均勻地分布在真實(shí)解周圍。通過引進(jìn)螢火蟲尋優(yōu)機(jī)制，吸引粒子進(jìn)行尋優(yōu)運(yùn)動，并在螢火蟲尋優(yōu)過程中對優(yōu)秀的粒子進(jìn)行混沌細(xì)搜索，對劣等的粒子進(jìn)行隨機(jī)重生。然而傳統(tǒng)的螢火蟲算法由于在位置更新時(shí)需要各粒子間交互作用，會嚴(yán)重影響濾波的算法復(fù)雜度和濾波時(shí)間。針對這個問題，本文借鑒了粒子群智能算法的思路，設(shè)置全局最優(yōu)值，將各個迭代時(shí)刻的粒子目標(biāo)函數(shù)與最優(yōu)值進(jìn)行比較，得到一個全局最優(yōu)值，并不斷更新該值，用全局最優(yōu)值替代j和i螢火蟲進(jìn)行信息交互。本文對螢火蟲算法進(jìn)行了改進(jìn)，更新如下：

1)修正螢火蟲熒光亮度公式

(15)

(16)

式中d為第d維。

2)修正螢火蟲吸引度公式

β=β0×e-γr2i

(17)

式中ri為粒子i與全局最優(yōu)值gbestk之間的歐氏距離。

3)修正螢火蟲位置更新公式

(18)

4.2 算法實(shí)現(xiàn)步驟

1)隨機(jī)產(chǎn)生一個(0,1)之間的隨機(jī)數(shù)，代入式(10)求得N-1個混沌序列，將長度為N的混沌序列變換到解空間中作為初始粒子。

2)模擬螢火蟲優(yōu)化過程，更新粒子位置。

由式(17)計(jì)算粒子i與全局最優(yōu)值之間的吸引度；根據(jù)式(18)更新粒子位置。

3)將前10 %亮度的螢火蟲作為優(yōu)秀粒子進(jìn)行混沌細(xì)搜索優(yōu)化，將亮度后10 %的螢火蟲作為劣質(zhì)粒子用隨機(jī)產(chǎn)生新的螢火蟲替代。

4)計(jì)算新的螢火蟲種群的亮度值，更新全局最優(yōu)值

(19)

5)若達(dá)到終止閾值ε或者最大迭代次數(shù)MaxGeneration，則算法迭代結(jié)束；否則，轉(zhuǎn)入步驟(2)。

6)由于每個粒子均進(jìn)行了尋優(yōu)移動，分布密度函數(shù)出現(xiàn)了變化，需要進(jìn)行權(quán)值補(bǔ)償更新

(20)

7)權(quán)值按式(7)進(jìn)行歸一化。

8)將歸一化后的權(quán)值以及優(yōu)化后的粒子代入式(9)計(jì)算狀態(tài)輸出。

5 仿真實(shí)驗(yàn)

實(shí)驗(yàn)硬件條件為inteli5—4200H處理器，12GB內(nèi)存，軟件環(huán)境為Matlab2014b，仿真的狀態(tài)模型和觀測模型

(21)

式中v(k)和w(k)選取零均值高斯白噪聲；系統(tǒng)噪聲方差Q=1；量測噪聲方差R=1。在螢火蟲算法中參數(shù)設(shè)置參考現(xiàn)有文獻(xiàn)的通常參數(shù)，最大吸引度為1，步長因子為0.3，最大光強(qiáng)吸收系數(shù)為1。

本文利用PF和CFA—PF算法進(jìn)行實(shí)驗(yàn)評估，其中，均方根誤差公式為

(22)

(23)

式中 Neff為有效粒子數(shù)；round()函數(shù)為向最近的整數(shù)取整運(yùn)算[10]。

5.1 精度測試

取N=20，Q=1，結(jié)果如圖1(a);取N=100，Q=1，結(jié)果如圖1(b)。

圖1 N=20和100時(shí)PF算法和CFA—FA算法測試結(jié)果

從圖1可以看出：相對于標(biāo)準(zhǔn)的PF算法，CFA—FA算法在粒子數(shù)較少的情況下，均方根誤差要明顯小于PF算法，說明濾波精度優(yōu)于PF算法，且CFA—FA算法的有效粒子數(shù)明顯高于PF算法，也更加穩(wěn)定，可見CFA—FA算法可以有效地改善粒子權(quán)值退化問題。

5.2 粒子多樣性測試

取N=100，濾波器在t=30時(shí)刻的粒子分布情況如圖2所示。

圖2 k=30時(shí)粒子狀態(tài)分布情況

從圖2中可以看出：PF算法的粒子樣本發(fā)生貧化，而CFA—PF算法在低似然區(qū)域也保留了部分粒子，從而保證了樣本多樣性。

6 結(jié) 論

吸取了傳統(tǒng)粒子濾波的優(yōu)點(diǎn)，引入了混沌優(yōu)化策略，同時(shí)將螢火蟲算法進(jìn)行改進(jìn)，減少了常規(guī)的FA算法的運(yùn)算復(fù)雜度，并將改進(jìn)的螢火蟲算法融合到粒子濾波當(dāng)中，實(shí)驗(yàn)結(jié)果證明：其有效地提高了濾波精度，尤其在粒子比較少的情況下，濾波精度明顯高于常規(guī)的FA算法，同時(shí)改善了粒子權(quán)值的退化，并保持了一定的粒子多樣性。

[1] 李天成,范紅旗,孫樹棟.粒子濾波理論、方法及其在多目標(biāo)跟蹤中的應(yīng)用[J].自動化學(xué)報(bào),2015(12):1981-2002.

[2] 劉 剛,彭 力.權(quán)值選優(yōu)粒子濾波的無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤[J].傳感器與微系統(tǒng),2011,30(6):30-32，35.

[3] 寧小磊,王宏力,徐宏林，等.加權(quán)逼近粒子濾波算法及其應(yīng)用[J].控制理論與應(yīng)用,2011(1):118-124.

[4] 張 琪,胡昌華,喬玉坤.基于權(quán)值選擇的粒子濾波算法研究[J].控制與決策,2008(1):117-120.

[5] 田夢楚,薄煜明,陳志敏，等.螢火蟲算法智能優(yōu)化粒子濾波[J].自動化學(xué)報(bào),2016(1):89-97.

[6] 彭珍瑞,趙 宇,殷 紅，等.基于混沌猴群算法的傳感器優(yōu)化布置[J].傳感器與微系統(tǒng),2014,33(10):104-107.

[7] 程美英，倪志偉，朱旭輝.螢火蟲優(yōu)化算法理論研究綜述[J].計(jì)算機(jī)科學(xué),2015，42(4):19-24.

[8] 蘇有良,周德儉,吳兆華，等.不同映射的混沌免疫進(jìn)化算法性能分析[J].計(jì)算機(jī)工程,2010,36(21):222-224.

[9] 王爾申,龐 濤,曲萍萍，等.基于混沌的改進(jìn)粒子群優(yōu)化粒子濾波算法[J].北京航空航天大學(xué)學(xué)報(bào),2016(5):885-890.

Research of improved particle filtering algorithm for fireflies based on chaos*

ZHU Chao1， LIU Yi-an1， XUE Song2

(1.College of IOT Engineering,Jiangnan University,Wuxi 214122,China; 2.China Ship Research and Development Academe,Beijing 100192,China)

Aiming at problem exists in conventional particle filtering algorithm of particle weight degradation and sampling particle impoverishment and it needs for a large number of particles to achieve accurate state estimation a firefly improved particle filtering algorithm based on chaotic is proposed.By using the ergodic and random initialization particle swarm of the chaotic system,the initial particle distribution is more uniform.At the same time,the optimization mechanism of the firefly algorithm is introduced into the conventional particle filtering algorithm,which can make the particles move to the high likelihood region,so as to improve the precision of the filtering.Using chaos search on the part of the weight of the excellent particle at the same time,and regenerate part of low weight particles,to achieve demand of diversity of improving population.Experiments show that this method is more accurate than the conventional particle filtering,especially in the case of small populations,and effectively improve the weight degeneracy and sample impoverishment problem.

Chaos optimization; firefly algorithm; particle filtering; weight degeneracy

10.13873/J.1000—9787(2017)09—0106—04

2016—06—20

國家自然科學(xué)基金資助項(xiàng)目(61170120)

TP 391

A

1000—9787(2017)09—0106—04

朱 超(1990-)，男，碩士研究生，主要研究方向?yàn)殡娮訉购蛿?shù)據(jù)融合。

劉以安(1962-)，男，碩士生導(dǎo)師，主要從事電子對抗和數(shù)據(jù)融合的研究工作。