一種基于自適應(yīng)進(jìn)化策略采樣的粒子濾波算法

黨 玲，紀(jì) 凱，許江湖

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

一種基于自適應(yīng)進(jìn)化策略采樣的粒子濾波算法

黨 玲1，紀(jì) 凱1，許江湖2

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

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

自適應(yīng)進(jìn)化策略;重采樣;粒子濾波

0 引言

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

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

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

1 粒子濾波

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

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

可用如下形式的估計(jì)值來逼近:

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

根據(jù)貝葉斯公式

式(7)又可以寫為

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

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

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

以及

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

標(biāo)準(zhǔn)粒子濾波算法選擇最易于實(shí)現(xiàn)的先驗(yàn)概率密度作為重要密度函數(shù)

這時(shí)，式(15)可以進(jìn)一步簡化為

當(dāng)前時(shí)刻粒子的權(quán)重被評估后，通過引入重采樣技術(shù)來改善粒子退化問題。

2 基于自適應(yīng)進(jìn)化策略采樣的粒子濾波算法

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

2.1 自適應(yīng)進(jìn)化策略算法

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

式中，f為適應(yīng)度函數(shù)，S?Rn為Rn空間上的閉集。假設(shè)種群規(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)初始化。產(chǎn)生μ個個體的初始群體，(Xi(t)，ηi(t))(i=1，2，…，μ)，當(dāng)前代數(shù)t=1。

2)適應(yīng)度計(jì)算。計(jì)算當(dāng)前種群中所有個體的適應(yīng)度值。

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

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

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

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

2.2 算法步驟

基于自適應(yīng)進(jìn)化策略采樣的粒子濾波算法步驟如下:

3)自適應(yīng)進(jìn)化采樣。

①計(jì)算每個粒子的適應(yīng)度值

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

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

3 仿真結(jié)果與分析

為了驗(yàn)證本文算法的有效性，通過2個仿真實(shí)例比較本文提出的 AESPF，PF以及文獻(xiàn)［3］提出的ESPF的濾波結(jié)果。

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

［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］朱志宇.粒子濾波算法及其應(yīng)用［M］.北京:科學(xué)出版社，2010.

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

［3］胡振濤，潘泉，梁彥，等.基于進(jìn)化采樣的粒子濾波算法［J］.控制理論與應(yīng)用，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］李翠蕓，姬紅兵.快速M(fèi)etropolis-Hastings變異的遺傳重采樣粒子濾波器［J］.系統(tǒng)工程與電子技術(shù)，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］李翠蕓，姬紅兵.新遺傳粒子濾波的紅外小目標(biāo)跟蹤與檢測［J］.西安電子科技大學(xué)學(xué)報(bào)，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］.自動化學(xué)報(bào)，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］王正志，薄濤.進(jìn)化計(jì)算［M］.長沙:國防科技大學(xué)出版社，2000.

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

［11］李廣文，賈秋玲，劉小雄，等.基于反饋和混沌變異的自適應(yīng)進(jìn)化策略［J］.計(jì)算機(jī)應(yīng)用研究，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］胡士強(qiáng)，敬忠良.粒子濾波原理及其應(yīng)用［M］.北京:科學(xué)出版社，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

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

黨玲(1964－)，女，副教授，研究方向?yàn)樾盘柵c信息處理技術(shù)。