一種基于自適應進化策略采樣的粒子濾波算法

黨 玲，紀 凱，許江湖

(1.海軍大連艦艇學院，遼寧 大連 116018;2.海軍工程大學電子工程學院，湖北 武漢 430033)

一種基于自適應進化策略采樣的粒子濾波算法

黨 玲1，紀 凱1，許江湖2

(1.海軍大連艦艇學院，遼寧 大連 116018;2.海軍工程大學電子工程學院，湖北 武漢 430033)

提出了一種自適應進化策略算法(AES)，該算法利用適應度值控制變異步長的自適應調整，從而提高了進化策略的搜索效率和精度。將AES算法和粒子濾波(PF)相結合，提出了基于自適應進化策略采樣的粒子濾波算法(AESPF)。該算法將AES應用于粒子重采樣，以保證粒子的有效性和多樣性。通過仿真計算表明，提出的算法可以有效提高濾波性能。

自適應進化策略;重采樣;粒子濾波

0 引言

隨著計算機運算能力的急劇增長和計算成本的不斷降低，粒子濾波(PF)已成為解決非線性、非高斯動態(tài)系統(tǒng)的參數估計和狀態(tài)濾波問題的有效方法［1］。粒子濾波又稱序貫蒙特卡羅方法，是一種基于蒙特卡羅方法和遞推貝葉斯估計的統(tǒng)計濾波方法。粒子濾波完全突破了Kalman濾波理論框架，對系統(tǒng)的過程噪聲和量測噪聲沒有任何限制。

粒子退化是標準粒子濾波算法的主要缺陷。采用重采樣方法在一定程度上可以抑制粒子退化現象的發(fā)生。而重采樣帶來的新問題是:權值越大的粒子的子代越來越多，而權值較小的粒子被剔除，最糟糕的情形是新的粒子集實際都是一個權值最大的粒子的子代，即所謂“樣本枯竭”現象，從而導致粒子集的多樣性變差，不足以用來近似表征后驗密度，難以保證估計精度，特別是在樣本受限條件下，這種粒子多樣性減弱對濾波精度的影響更為突出，甚至導致濾波發(fā)散現象［2］。

進化算法(包括遺傳算法、進化策略、進化規(guī)劃)是一種隨機搜索優(yōu)化技術。該算法根據生物中遺傳與進化的原理，仿效基因、染色體等物質表達所研究的問題，遵循達爾文“物競天擇，適者生存”原則，使隨機生成的初始解通過復制、交換、突變等遺傳操作不斷迭代進化，逐步逼近最優(yōu)解。粒子濾波與進化算法的相似之處在于它們都有一個初始化的群體，每個個體代表系統(tǒng)的一個可能解，這些個體均根據一定的規(guī)則進行狀態(tài)轉變，對適應度較高的個體進行復制。因此，用進化的思想來解決粒子濾波的退化具有可行性［2］。國內外學者也對此進行了一些努力和嘗試［3－9］。在3種進化算法中，遺傳算法是一種較為通用的求解方法，而進化策略和進化規(guī)劃更適宜求解函數優(yōu)化問題。進化策略還具有收斂速度快、運算簡單、易于實現、無需遺傳算法復雜的編解碼運算等優(yōu)點［10］。然而在進化策略的應用中，變異步長的選擇始終是個棘手的問題。變異步長選擇過大，會提高全局搜索能力，但是搜索精度不高;變異步長選擇過小，則容易陷入局部極小［11］。為此，本文首先提出了一種自適應進化策略算法(AES)，該算法利用適應度值控制變異步長的自適應調整，從而提高了進化策略的搜索效率和精度。然后將AES算法和粒子濾波(PF)相結合，提出了基于自適應進化策略采樣的粒子濾波算法(AESPF)。該算法將AES應用于粒子重采樣，以保證粒子的有效性和多樣性。通過仿真計算表明，提出的算法可以有效提高濾波性能。

1 粒子濾波

離散時間非線性動態(tài)系統(tǒng)的狀態(tài)方程和量測方程分別為:

其中:δ(·)為狄拉克函數，則fk(x0:k)的數學期望

可用如下形式的估計值來逼近:

式(5)的收斂性可由大數定律得到保證。然而，通常很難從p(x0:k|z1:k)中直接采樣，一種解決方法就是先從1個已知的且容易采樣且盡量接近后驗概率分布的重要性概率密度函數q(x0:k|z1:k)中采樣，并通過對采樣粒子進行加權近似

根據貝葉斯公式

式(7)又可以寫為

根據蒙特卡羅方法，fk(x0:k)的數學期望可以近似表示為:

表示每個粒子的權重，ω～ik表示歸一化后的權重。將上述原理以遞推形式給出，即為序貫重要性采樣(SIS)。若將重要性函數寫成以下的連乘形式:

假設狀態(tài)符合Markov過程，在給定狀態(tài)下，量測條件獨立，則可以得出:

以及

將式(12)～(14)代入式(11)，得到權值的遞推公式為

標準粒子濾波算法選擇最易于實現的先驗概率密度作為重要密度函數

這時，式(15)可以進一步簡化為

當前時刻粒子的權重被評估后，通過引入重采樣技術來改善粒子退化問題。

2 基于自適應進化策略采樣的粒子濾波算法

重采樣的負作用是樣本枯竭，即有較大權值的粒子被多次選擇，采樣結果包含了許多重復點，從而損失了粒子的多樣性，使得描述后驗概率密度函數的樣本點太少或者不充分。而用進化的思想來解決粒子濾波的退化具有可行性。在3種進化算法中，遺傳算法是一種較為通用的求解方法，而進化策略和進化規(guī)劃更適宜求解函數優(yōu)化問題。進化策略還具有收斂速度快、運算簡單、易于實現、無需遺傳算法復雜的編解碼運算等優(yōu)點。然而，在進化策略的應用中，變異步長的選擇始終是個棘手的問題。變異步長選擇過大，會提高全局搜索能力，但是搜索精度不高;變異步長選擇過小，則容易陷入局部極小。為此，下面首先提出一種自適應進化策略算法(AES)，該算法利用適應度值控制變異步長的自適應調整，從而提高了進化策略的搜索效率和精度。然后將AES應用于粒子濾波的重采樣中，提出基于自適應進化策略采樣的粒子濾波算法。

2.1 自適應進化策略算法

考慮一個連續(xù)參數優(yōu)化問題:

式中，f為適應度函數，S?Rn為Rn空間上的閉集。假設種群規(guī)模為μ，(Xi(t)，ηi(t))為第t代種群的第i個個體(i=1，2，…，μ)，n維向量Xi(t)=［xi1(t)，xi2(t)，…，xin(t)］，步 長 向 量 ηi(t)=［ηi1(t)，ηi2(t)，…，ηin(t)］，則求解式(18)的 ES步驟為:

1)初始化。產生μ個個體的初始群體，(Xi(t)，ηi(t))(i=1，2，…，μ)，當前代數t=1。

2)適應度計算。計算當前種群中所有個體的適應度值。

3)突變。進化策略的突變是在舊個體基礎上添加一個隨機量，從而形成新個體:

4)選擇。進化策略中的選擇類似于遺傳算法的復制，但是進化策略中的選擇是確定型操作，它嚴格根據適應度的大小，將劣質個體完全淘汰。選擇中不采用輪盤法那種隨機方式，而是使優(yōu)質個體100%地保留，劣質個體100%地被淘汰。進化策略的選擇有2種:一種為(μ+λ)選擇，另一種為(μ，λ)選擇。(μ+λ)選擇是從μ個父代個體及λ個子代新個體中確定性地擇優(yōu)選出μ個個體組成下一代群體。(μ，λ)選擇是從λ個子代新個體中確定性地擇優(yōu)選出μ個個體(要求λ＞μ)組成下一代群體。

從式(19)可以看出，影響進化策略搜索精度和結果的主要是變異步長的選擇，變異步長越大，個體變異的幅度越大。增大變異步長，會提高全局搜索能力和搜索效率，但搜索精度會變差;減小變異步長，則會提高搜索精度，但容易陷入局部極小。因此變異步長的大小必須根據搜索過程中的實時要求進行自適應調整。由于適應度反映了個體的目標函數值與最優(yōu)解的距離，本文通過適應度來控制變異步長的自適應調整:當適應度較大時，說明需要提高精度，應減小變異步長;當適應度較小時，需要擴大搜索范圍時，則應增大變異步長。具體調整方法如下:

式(20)中，Fitness表示適應度值，為了使算法有效運行，其值控制在0和1之間。C(0，1)表示參數分別為0和1的柯西分布。這里之所以采用柯西分布是由于它比高斯分布產生的隨機變量的范圍大，從而提高了搜索能力［12］。將式(20)代替式(19)就是本文提出的自適應進化策略(AES)。

2.2 算法步驟

基于自適應進化策略采樣的粒子濾波算法步驟如下:

3)自適應進化采樣。

①計算每個粒子的適應度值

②突變。根據Fik對每個粒子按式(20)進行突變操作。

③選擇。計算子代新粒子的適應度值，然后(μ+λ)選擇方法進行粒子優(yōu)選。

3 仿真結果與分析

為了驗證本文算法的有效性，通過2個仿真實例比較本文提出的 AESPF，PF以及文獻［3］提出的ESPF的濾波結果。

仿真實例1的系統(tǒng)狀態(tài)方程和量測方程為:

其中，過程噪聲和量測噪聲均為0均值白高斯噪聲，方差分別為10和1。蒙特卡羅仿真次數為50次，仿真步長為60 s，每步采樣間隔1 s。表1給出了不同粒子數目情況下，3種濾波算法對實例1的濾波平均均方根誤差(RMSE)［13］。

式中:MC為仿真次數;L為仿真長度;x(k)為真實值;x^j(k)為估計值。

表1 不同粒子數目情況下仿真實例1的平均RMSE比較Tab.1 The mean comparison of RMSE of example 1 for different sample size

從表1給出的數據可知，AESPF的濾波精度明顯優(yōu)于PF和ESPF。

仿真實例2的系統(tǒng)狀態(tài)方程和量測方程為:

圖1和圖2分別表示粒子數N取400時，實例2基于X軸方向和Y軸方向目標位置的RMSE曲線。表2分別給出了不同粒子數目情況下，3種濾波算法對實例2的濾波平均RMSE。

從圖1和圖2看出，本文提出的AESPF無論在收斂速度還是濾波精度都優(yōu)于PF和ESPF。而綜合表1和2的數據可以進一步看出，在高維非線性且粒子數目受限的情況下，AESPF相對于PF和ESPF具有更好的跟蹤效果。

圖1 實例2的X軸方向位置RMSE曲線Fig.1 RMSE in position on X axis for example 2

圖2 實例2的Y軸方向位置RMSE曲線Fig.2 RMSE in position on Y axis for example 2

表2 不同粒子數目情況下仿真實例2的位置估計平均RMSE比較Tab.2 The mean comparison of RMSE in position of example 2 for different sample size

4 結語

本文首先提出了一種自適應進化策略算法(AES)，該算法利用適應度值控制變異步長的自適應調整，從而提高了進化策略的搜索效率和精度。然后將AES算法與粒子濾波相結合，提出基于自適應進化策略采樣的粒子濾波算法(AESPF)。該算法將AES應用于粒子重采樣，以保證粒子的有效性和多樣性。最后通過仿真計算表明，提出的算法可以有效提高濾波性能。

［1］GORDON N J，SALMOND D J，SMITH A F M.Novel approach to nonlinear/non-Gaussian Bayesian state estimation［J］.IEE Proceedings－ F，1993，140(2):107 －113.

［2］朱志宇.粒子濾波算法及其應用［M］.北京:科學出版社，2010.

ZHU Zhi-yu.Particle filter algorithms with applications［M］.Beijing:Science Press，2010.

［3］胡振濤，潘泉，梁彥，等.基于進化采樣的粒子濾波算法［J］.控制理論與應用，2009，26(3):269 －273.

HU Zhen-tao，PAN Quan，LIANG Yan，et al.The particle filter algorithm based on evolution sampling［J］.Control Theory ＆ Applications，2009，26(3):269 －273.

［4］李翠蕓，姬紅兵.快速Metropolis-Hastings變異的遺傳重采樣粒子濾波器［J］.系統(tǒng)工程與電子技術，2009，31(8):1968－1972.

LI Cui-yun，JI Hong-bing.Genetic resampling particle filter based on fast Metropolis-Hastings mutation［J］.Systems Engineering and Electronics，2009，31(8):1968 －1972.

［5］李翠蕓，姬紅兵.新遺傳粒子濾波的紅外小目標跟蹤與檢測［J］.西安電子科技大學學報，2009，36(4):619－644.

LI Cui-yun，JI Hong-bing.IR dim target tracking and detection based on new genetic particle filter［J］.Journal of Xidian University，2009，36(4):619 －644.

［6］RONGHUA L，BINGRONG H.Coevolution based adaptive Monte Carlo localization［J］.International Journal of Advanced Robotic Systems，2004，1(3):183 －190.

［7］葉龍，王京玲，張勤.遺傳重采樣粒子濾波器［J］.自動化學報，2007，33(8):885 －887.

YE Long， WANG Jing-ling，ZHANG Qin.Genetic resampling particle filter［J］.Acta Automatica Sinica，2007，33(8):885 －887.

［8］PARK S，HWANG J，ROU K，et al.A new particle filter inspired by biologicalevolution:genetic filter［C］.Proceedings of World Academy of Science，Engineering and Technology，Bangkok，Thailand:IEEE，2007，21:459 －463.

［9］UOSAKI k，HATANAKA T.Evolutionstrategiesbased particle filters for fault detection［C］.Proceedings of the IEEE Symposium on Computational Intelligence in Image and Signal Processing.Hawaiian，USA:IEEE，2007，58 －65.

［10］王正志，薄濤.進化計算［M］.長沙:國防科技大學出版社，2000.

WANG Zheng-zhi，BO Tao.Evolutionary computing［M］.Changsha:NationalUniversityofDefenceTechnology Press，2000.

［11］李廣文，賈秋玲，劉小雄，等.基于反饋和混沌變異的自適應進化策略［J］.計算機應用研究，2009，26(6):2056－2061.

LIGuang-wen，JIA Qiu-ling，LIU Xiao-xiong，etal.Adaptive evolutionary strategy based on feedback and chaotic mutation［J］.Application Research of Computers，2009，26(6):2056 －2061.

［12］YAO X，LIU Y，LIN G M.Evolutionary programming made faster［J］.IEEE transactions on evolutionary，1999，3(2):82－102.

［13］胡士強，敬忠良.粒子濾波原理及其應用［M］.北京:科學出版社，2010.

HU Shi-qiang，JING Zhong-liang.Particle filter theory with application［M］.Beijing:Science Press，2010.

A particle filter algorithm based on adaptive evolution strategies sampling

DANG Ling1，JI Kai1，XU Jiang-hu2
(1.Dalian Naval Academy，Dalian 116018，China;2.College of Electronics Engineering，Naval University of Engineering，Wuhan 430033，China)

An adaptive evolution strategies(AES)algorithm is first proposed.In the algorithm，Adaptive adjustment of mutation step is controlled by fitness to improve searching efficiency and precision.Then a particle filter based on adaptive evolution sampling(AESPF)is proposed by combining AES and particle filter(PF)，AES is applied to particle resampling to keep the validity and variety of particles in the algorithm.Simulation results indicate the algorithm can effectively improve the filter performance.

adaptive evolution strategies;resampling;particle filter

TB11

A

1672－7649(2012)03－0054－05

10.3404/j.issn.1672－7649.2012.03.011

2011－06－14;

2011－07－07

中國博士后科學基金資助項目(20090461460);湖北省自然科學基金資助項目(2009CDB301)

黨玲(1964－)，女，副教授，研究方向為信號與信息處理技術。