萬有引力優(yōu)化的粒子濾波算法

劉潤邦， 朱志宇

(江蘇科技大學(xué) 電子信息學(xué)院，江蘇 鎮(zhèn)江 212003)

粒子濾波(Particle Filter, PF)是一種基于蒙特卡羅仿真的近似貝葉斯濾波算法，可以有效地處理非線性非高斯問題，目前已應(yīng)用于目標(biāo)跟蹤、軌跡規(guī)劃、故障檢測等領(lǐng)域．經(jīng)典粒子濾波主要存以下3個缺陷:粒子退化;粒子多樣性匱乏;濾波精度嚴(yán)重依賴于粒子數(shù)量[1-3]．

智能算法是一類模擬自然界生物規(guī)律的算法，近年來被廣泛地應(yīng)用于粒子濾波優(yōu)化問題中，并取得了良好的濾波改進(jìn)效果．目前，已有學(xué)者將蝙蝠算法[4]、粒子群算法[5-6]、螢火蟲算法[7-9]、人工物理優(yōu)化算法[10-11]與粒子濾波算法相結(jié)合，預(yù)防粒子退化的同時提高了粒子濾波的精度和粒子的多樣性．萬有引力搜索算法(Gravitational Search Algorithm，GSA)是Esmat等人于2009年提出的一種新型智能尋優(yōu)算法，該算法運(yùn)行的機(jī)制源于對牛頓萬有引力定律的模擬，已有文獻(xiàn)證明其全局尋優(yōu)能力明顯優(yōu)于粒子群等智能優(yōu)化算法[12-16]．

為此，筆者提出一種萬有引力優(yōu)化的粒子濾波算法(GSA-PF)．該算法將每個粒子看做一個具有質(zhì)量的點，引力大小正比于粒子的權(quán)值，它吸引著粒子向高似然區(qū)域移動，從而改善似然分布的建議密度，克服粒子退化問題; 同時對GSA進(jìn)行改進(jìn)，引入精英策略以加快粒子的收斂速度，并避免粒子集陷入局部最優(yōu); 引入感知模型以防止過度優(yōu)化而導(dǎo)致粒子擁擠或重疊，預(yù)防了粒子多樣性的喪失．仿真實驗表明，該算法具有較高的精度速度性價比．

1　粒子濾波算法

系統(tǒng)狀態(tài)模型和觀測模型可描述為

xk=f(xk-1，uk)，zk=h(xk，vk),

(1)

其中，xk為系統(tǒng)狀態(tài)向量，zk為觀測向量，uk為過程噪聲，vk為觀測噪聲，函數(shù)f為系統(tǒng)狀態(tài)轉(zhuǎn)移概率密度p(xk|xk-1)，h為系統(tǒng)觀測似然概率密度p(zk|xk)．

(2)

(3)

(4)

(5)

為克服粒子退化，常規(guī)粒子濾波流程需要對粒子集進(jìn)行重采樣運(yùn)算．

2　基于精英策略和感知模型的萬有引力優(yōu)化算法

GSA的機(jī)理主要源于對萬有引力定律和牛頓加速度定律的模擬．從GSA的運(yùn)行機(jī)制和PF存在的問題上看，可以考慮利用GSA優(yōu)化粒子濾波中的粒子集．為此，文中提出一種基于精英策略和感知模型的萬有引力優(yōu)化算法．

(6)

其中，ε是很小的常量，Rij為粒子間的歐氏距離，G為引力常數(shù):

G=G0exp(-αt/T),

(7)

其中，G0是常數(shù)初始值，α是G的衰減系數(shù)，T是最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)．

萬有引力算法的初衷是全局尋優(yōu)，粒子僅受引力的作用向適應(yīng)度較高的粒子移動，如直接應(yīng)用到粒子濾波當(dāng)中，不可避免地會導(dǎo)致粒子多樣性喪失．為此，引入了如下感知模型:

(8)

其中，c(xi，xj)為第i個和第j個粒子間的感知矩陣，R(i，j)為粒子間的歐氏距離，r為感知閾值．

若感知模型為1，則粒子間的引力作用正常; 若感知模型為0，則引力消失; 若第i個粒子所有引力合力為0，則粒子做無規(guī)則運(yùn)動．此模型可使粒子向高似然區(qū)域移動的同時保持自身的多樣性．

粒子的慣性質(zhì)量M可以由適應(yīng)度函數(shù)值計算得到．M越大，其產(chǎn)生的引力越大，所處的位置越接近最優(yōu)解．假設(shè)粒子引力和慣性質(zhì)量相等，Mai=Mpi=Mii=Mi，i=1，2，…，N，則

(9)

其中，si(t)表示第i個粒子在t時刻的適應(yīng)度值．對于求解最大值問題，b(t)和w(t)定義為

(10)

最小值的求解方法與之相反．在GSA中，每一個粒子均受到除自己以外其他所有粒子的吸引力，這極大地增加了算法的運(yùn)算量和復(fù)雜程度．在較多吸引力互相牽制的情況下，粒子易陷入局部最優(yōu)且收斂速度較慢．為此，需要將萬有引力合力的計算公式修正為

(11)

若每一個粒子僅受粒子集中質(zhì)量最大的前K個粒子的引力作用，且K(向上取整)是一個隨著尋優(yōu)次數(shù)不斷更新的數(shù)值，則K可表示為

K=(1-t/T)N+1．

(12)

在初始時刻，所有粒子均施加引力，隨著優(yōu)化次數(shù)的增加，產(chǎn)生有效引力的粒子數(shù)越來越少，直到最后僅有1個質(zhì)量最大的粒子對其他粒子產(chǎn)生引力．該策略能有效地加快粒子集向高似然區(qū)域的收斂速度，同時防止粒子陷入局部最優(yōu)．

根據(jù)牛頓第二定律，粒子的加速度為

(13)

在優(yōu)化的過程中，粒子的速度及位置更新準(zhǔn)則為

(14)

3　萬有引力優(yōu)化的粒子濾波算法步驟

對于每個濾波步長k，執(zhí)行以下步驟:

步驟3對新預(yù)測的粒子集進(jìn)行引力優(yōu)化處理:

(2) 記錄當(dāng)前優(yōu)化迭代次數(shù)t，利用式(7)、式(12)更新引力常數(shù)G和精英粒子數(shù)K．

步驟6判斷濾波程序是否結(jié)束，若是，則結(jié)束; 若不是，k=k+1，并返回步驟2．

4　仿真實驗與分析

為驗證文中算法(GSA-PF)的有效性，對單變量非靜態(tài)增長模型和純角度二維目標(biāo)跟蹤模型進(jìn)行了仿真實驗，并與常規(guī)粒子濾波算法(PF)和粒子群優(yōu)化粒子濾波算法(PSO-PF)進(jìn)行對比．

4.1　單變量非靜態(tài)增長模型

狀態(tài)方程為

x(t)=0.5x(t-1)+25x(t-1)/{1+[x(t-1)]2}+8 cos [1.2(t-1)]+w(t),

(15)

觀測方程為z(t)=x(t)2/20+v(t),

(16)

其中，w(t)和v(t)為高斯噪聲．該系統(tǒng)為觀測方程呈雙峰的高度非線性系統(tǒng)．引入單次濾波計算時間Tpf和均方根誤差RRMSE作為算法的評估標(biāo)準(zhǔn)，即

(17)

實驗中系統(tǒng)噪聲方差Q=10，觀測噪聲方差R=1，步長為50，粒子數(shù)分別為30、50、100，T=5，G0= 100，α=20，r=3．不同算法濾波精度對比仿真實驗結(jié)果如圖1和圖2所示．

圖1　濾波狀態(tài)估計結(jié)果

圖2　濾波誤差絕對值

各算法性能參數(shù)對比情況如表1所示．

由上述數(shù)據(jù)可知，GSA-PF的濾波精度明顯優(yōu)于PSO-PF和常規(guī)PF的．在相同粒子數(shù)的情況下，GSA-PF的單次濾波時間稍高于其他兩種算法的．當(dāng)粒子數(shù)為30和50時，GSA-PF的單次濾波時間基本接近于PSO-PF的，但濾波結(jié)果明顯優(yōu)于PSO-PF的．為此，GSA-PF的優(yōu)勢在于用最少的粒子達(dá)到最高的濾波精度，其更適合在粒子數(shù)較少的情況下使用，具有較高的精度速度綜合性價比．

表1　相同粒子數(shù)情況下各算法性能對比結(jié)果

表2　相同均方根誤差情況下各算法性能對比結(jié)果

表2為對比相同濾波誤差情況下各種算法所需要的粒子數(shù)及單次濾波時間．由于粒子濾波算法的計算存在一定的隨機(jī)性，所以粒子數(shù)僅精確到10數(shù)量級．由實驗數(shù)據(jù)可以看出，預(yù)達(dá)到相同的濾波均方根誤差值，GSA-PF所需要的粒子數(shù)最少，而常規(guī)PF所需的粒子數(shù)為GSA-PF的3倍，PSO-PF的粒子數(shù)則介于它們之間，因為所需粒子數(shù)最少，所以GSA-PF表現(xiàn)出最好的濾波速度．經(jīng)典粒子濾波中為得到較為準(zhǔn)確的后驗分布，可以采用增加粒子的方法，代價是計算量明顯增加，而文中提出的GSA-PF則在此問題上取得了較好的平衡．在相同濾波精度的情況下，GSA-PF可以在較少粒子數(shù)的情況下保持較高的濾波精度，同時能有效地克服粒子退化和貧化問題．

為證明GSA-PF能有效地保持粒子多樣性，截取的粒子數(shù)為100，仿真步長K=25，K=35，K=45 時粒子的分布狀況，并與常規(guī)粒子濾波算法中重采樣后的粒子集進(jìn)行對比，見圖3．

圖3　粒子集分布對比圖

由圖3可得，GSA-PF在優(yōu)化粒子向高似然區(qū)域移動的同時，保持了粒子的多樣性．優(yōu)化處理后的粒子集的分布情況較重采樣的分布情況有了較大的改善，保留了一些具有較好假設(shè)的粒子．

4.2　純角度二維目標(biāo)跟蹤模型

為驗證GSA-PF在粒子數(shù)較少情況下的良好濾波性能，仿真實驗將該算法應(yīng)用于目標(biāo)跟蹤的實際問題中并選擇純角度跟蹤模型．假設(shè)二維空間中目標(biāo)的狀態(tài)X(k)= [xp(k)，xv(k)，yp(k)，yv(k)]T，(xp(k)，yp(k))為k時刻目標(biāo)的坐標(biāo)，(xv(k)，yv(k))為k時刻目標(biāo)在水平和垂直方向的速度分量．

目標(biāo)的狀態(tài)方程為X(k+1)=ΦX(k)+w(k),

(18)

觀測方程為Z(k)=arctan((y(k)-y0)/(x(k)-x0))+v(k),

(19)

其中，Φ為狀態(tài)轉(zhuǎn)移矩陣，w(k)為高斯系統(tǒng)噪聲，v(k)為高斯觀測噪聲，x0和y0為觀測站的位置．跟蹤步長為50，粒子數(shù)為30，系統(tǒng)噪聲方差為0.01，觀測噪聲方差為0.001．單次跟蹤結(jié)果及誤差如圖4所示．

圖4　純角度二維目標(biāo)跟蹤結(jié)果

由圖4可知，GSA-PF的濾波性能明顯優(yōu)于其他兩種算法的．常規(guī)PF在跟蹤后程出現(xiàn)了較大的跟蹤誤差，其原因是粒子多樣性喪失，且粒子數(shù)量較少；GSA-PF在粒子數(shù)很少的情況下，保持了較高的跟蹤精度；PSO-PF的跟蹤效果則介于GSA-PF和PF之間．

5　結(jié) 束 語

文中根據(jù)萬有引力搜索算法的尋優(yōu)特點，提出一種萬有引力優(yōu)化的粒子濾波算法．該算法以粒子優(yōu)化代替?zhèn)鹘y(tǒng)的重采樣，將粒子看做有質(zhì)量的點，粒子間的引力吸引著它們向高似然區(qū)域逼近，解決粒子退化問題; 為提高算法實時性、加快粒子優(yōu)化速度并防止粒子陷入局部最優(yōu)，在萬有引力算法中引入了精英粒子策略; 同時引入感知模型預(yù)防粒子多樣性喪失．仿真對比試驗表明，萬有引力優(yōu)化的粒子濾波算法有效地克服了粒子退化、粒子貧化的問題，能夠在粒子數(shù)較少的情況下依然能保持較優(yōu)的濾波效果，表現(xiàn)出良好的精度速度性價比，具有較為廣泛的應(yīng)用前景．

參考文獻(xiàn)：

[1] 王澤玉, 李明, 張鵬. 一種新的進(jìn)化裂變粒子濾波算法[J]. 西安電子科技大學(xué)學(xué)報, 2014, 41(6): 31-36.

WANG Zeyu, LI Ming, ZHANG Peng. Novel Particle Filter Algorithm Based on Evolution Fission[J]. Journal of Xidian University, 2014, 41(6): 31-36.

[2]巨剛, 袁亮, 劉小月. 多方法融合的粒子濾波算法的神經(jīng)絲自動跟蹤[J]. 西安電子科技大學(xué)學(xué)報, 2016, 43(4): 184-190.

JU Gang, YUAN Liang, LIU Xiaoyue. Neurofilament Protein Automatic Tracking of the Particle Filter Algorithm Based on Multiple Methods Fusion[J]. Journal of Xidian University, 2016, 43(4): 184-190.

[3]別秀德, 劉洪彬, 常發(fā)亮, 等. 自適應(yīng)分塊的多特征融合多目標(biāo)跟蹤[J]. 西安電子科技大學(xué)學(xué)報, 2017, 44(2): 151-157.

BIE Xiude, LIU Hongbin, CHANG Faliang, et al. Multi-target Tracking Method Based on the Adaptive Fragment and Multi-feature Fusion[J]. Journal of Xidian University, 2017, 44(2): 151-157.

[4]陳志敏, 田夢楚, 吳盤龍, 等. 基于蝙蝠算法的粒子濾波法研究[J]. 物理學(xué)報, 2017, 66(5): 47-56.

CHEN Zhimin, TIAN Mengchu, WU Panlong, et al. Intelligent Particle Filter Based on Bat Algorithm[J]. Acta Physica Sinica, 2017, 66(5): 47-56.

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

WANG Ershen, PANG Tao, QU Pingping, et al. Improved Particle Filter Algorithm Based on Chaos Particle Swarm Optimization[J]. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(5): 885-890.

[6]ZHAO Z S, FENG X, LIN Y Y, et al. Improved Rao-blackwellized Particle Filter by Particle Swarm Optimization[J]. Journal of Applied Mathematics, 2013, 2013( 2) : 1-7.

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

TIAN Mengchu, BO Yuming, CHEN Zhimin, et al. Firefly Algorithm Intelligence Optimized Particle Filter[J]. Acta Automatica Sinica, 2016, 42(1): 89-97.

[8]GAO M L, LI L L, SUN X M, et al. Firefly Algorithm(FA) Based Particle Filter Method for Visual Tracking[J]. Optik, 2015, 126(18): 1705-1711.

[9]WANG H, WANG W J, ZHOU X Y, et al. Firefly Algorithm with Neighborhood Attraction[J]. Information Sciences, 2017, 382/383: 374-387.

[10]劉繁明, 錢東, 劉超華. 一種人工物理優(yōu)化的粒子濾波算法[J]. 控制與決策, 2012, 27(8): 1145-1148.

LIU Fanming, QIAN Dong, LIU Chaohua. An Artificial Physics Optimized Particle Filter[J]. Control and Decision, 2012, 27(8): 1145-1148.

[11]MORSHIDI M, TJAHJADI T. Gravity Optimised Particle Filter for Hand Tracking[J]. Pattern Recognition, 2014, 47(1): 194-207.

[12]DAS P K, BEHERA H S, PANIGRAHI B K. A Hybridization of an Improved Particle Swarm Optimization and Gravitational Search Algorithm for Multi-robot Path Planning[J]. Swarm and Evolutionary Computation, 2016, 28(1): 14-28.

[13]ALI A F, TAWHID M A. Direct Gravitational Search Algorithm for Global Optimisation Problems[J]. East Asian Journal on Applied Mathematics, 2016, 6(3): 290-313.

[14]馬力, 劉麗濤. 萬有引力搜索算法的分析與改進(jìn)[J]. 微電子學(xué)與計算機(jī), 2015, 32(9): 76-80.

MA Li, LIU Litao. Analysis and Improve of Gravitational Search Algorithm[J]. Microelectronics & Computer, 2015, 32(9): 76-80.

[15]SIDDIQUE N, ADELI H. Gravitational Search Algorithm and Its Variants[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2016, 30(8): 1639001.

[16]ZHANG A, SUN G, REN J, et al. A Dynamic Neighborhood Learning-based Gravitational Search Algorithm[J]. IEEE Transactions on Cybernetics, 2016, 99(1): 1-12.