基于混沌的螢火蟲改進粒子濾波算法研究*

朱 超， 劉以安， 薛 松

(1.江南大學 物聯網工程學院，江蘇 無錫 214122； 2.中國艦船研究院，北京 100192)

計算與測試

基于混沌的螢火蟲改進粒子濾波算法研究*

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

(1.江南大學 物聯網工程學院，江蘇 無錫 214122； 2.中國艦船研究院，北京 100192)

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

混沌優化； 螢火蟲算法； 粒子濾波； 權值退化

0 引 言

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

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

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

1 粒子濾波算法

假設非線性系統的狀態方程和觀測方程如下

(1)

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

(2)

狀態更新方程為

(3)

設重要性函數為q(x0∶k-1|y1∶k)，則權值公式為

(4)

(5)

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

概率密度更新公式為

(6)

最后進行權值歸一化，并輸出狀態

(7)

(8)

2 螢火蟲算法

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

1)螢火蟲相對亮度為

I=I0×e-γrij

(9)

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

2)螢火蟲吸引度為

β=β0×e-γrij

(10)

式中 β0為最大吸引度。

3)螢火蟲位置更新為

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

(11)

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

3 混沌優化策略

文獻[8]對不同的混沌映射算法進行了性能分析。其中，Kent混沌映射在區間(0,1)具有更加優秀的遍歷均勻性。Kent混沌映射的數學表達式為

(12)

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

(13)

式中 [xmin,j,xmax,j]為第j維變量的搜索范圍；xg,j為當前的最優值；ρ為搜索因子

(14)

式中t為當前搜索次數。

4 混沌螢火蟲優化粒子濾波算法

4.1 優化策略

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

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

(15)

(16)

式中d為第d維。

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

β=β0×e-γr2i

(17)

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

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

(18)

4.2 算法實現步驟

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

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

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

3)將前10 %亮度的螢火蟲作為優秀粒子進行混沌細搜索優化，將亮度后10 %的螢火蟲作為劣質粒子用隨機產生新的螢火蟲替代。

4)計算新的螢火蟲種群的亮度值，更新全局最優值

(19)

5)若達到終止閾值ε或者最大迭代次數MaxGeneration，則算法迭代結束；否則，轉入步驟(2)。

6)由于每個粒子均進行了尋優移動，分布密度函數出現了變化，需要進行權值補償更新

(20)

7)權值按式(7)進行歸一化。

8)將歸一化后的權值以及優化后的粒子代入式(9)計算狀態輸出。

5 仿真實驗

實驗硬件條件為inteli5—4200H處理器，12GB內存，軟件環境為Matlab2014b，仿真的狀態模型和觀測模型

(21)

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

本文利用PF和CFA—PF算法進行實驗評估，其中，均方根誤差公式為

(22)

(23)

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

5.1 精度測試

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

圖1 N=20和100時PF算法和CFA—FA算法測試結果

從圖1可以看出：相對于標準的PF算法，CFA—FA算法在粒子數較少的情況下，均方根誤差要明顯小于PF算法，說明濾波精度優于PF算法，且CFA—FA算法的有效粒子數明顯高于PF算法，也更加穩定，可見CFA—FA算法可以有效地改善粒子權值退化問題。

5.2 粒子多樣性測試

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

圖2 k=30時粒子狀態分布情況

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

6 結 論

吸取了傳統粒子濾波的優點，引入了混沌優化策略，同時將螢火蟲算法進行改進，減少了常規的FA算法的運算復雜度，并將改進的螢火蟲算法融合到粒子濾波當中，實驗結果證明：其有效地提高了濾波精度，尤其在粒子比較少的情況下，濾波精度明顯高于常規的FA算法，同時改善了粒子權值的退化，并保持了一定的粒子多樣性。

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

[2] 劉 剛,彭 力.權值選優粒子濾波的無線傳感器網絡目標跟蹤[J].傳感器與微系統,2011,30(6):30-32，35.

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

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

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

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

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

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

[9] 王爾申,龐 濤,曲萍萍，等.基于混沌的改進粒子群優化粒子濾波算法[J].北京航空航天大學學報,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

國家自然科學基金資助項目(61170120)

TP 391

A

1000—9787(2017)09—0106—04

朱 超(1990-)，男，碩士研究生，主要研究方向為電子對抗和數據融合。

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