SIR粒子濾波的改進(jìn)算法

孔紅山，李小鵬，郁 濱

(信息工程大學(xué) 密碼工程學(xué)院，河南 鄭州 450001)

0 引 言

粒子濾波(particle filter，PF)不僅能處理噪聲服從高斯分布的線性系統(tǒng)，而且可以處理非高斯噪聲的非線性系統(tǒng)[1-3]。序貫重要性重采樣(sequential importance resampling，SIR)粒子濾波算法，通過在粒子濾波算法中加入重采樣環(huán)節(jié)解決粒子退化問題，但也帶來了粒子貧化問題。

為了解決SIR-PF算法的粒子貧化問題，很多學(xué)者進(jìn)行了改進(jìn)重采樣環(huán)節(jié)的相關(guān)研究。文獻(xiàn)[4]提出了一種基于分類重采樣的改進(jìn)粒子濾波算法；文獻(xiàn)[5]提出了利用鄰域搜索重采樣改進(jìn)粒子濾波算法，提高了粒子多樣性，但并沒有解決粒子貧化的問題。在基于重采樣的粒子濾波框架下進(jìn)行算法改進(jìn)，不能從本質(zhì)上解決粒子貧化問題，很多學(xué)者從交叉學(xué)科與粒子濾波相融合的角度進(jìn)行了研究。文獻(xiàn)[6-8]分別提出了基于遺傳算法、鴿群算法和螢火蟲算法的粒子重采樣算法，大大提高了粒子有效性和多樣性。通過引入人工智能優(yōu)化算法與粒子濾波相結(jié)合，是一種更加有效解決粒子貧化問題的思路。

粒子群優(yōu)化算法是一種有效的全局尋優(yōu)算法，文獻(xiàn)[9]提出基于高斯粒子群優(yōu)化算法的粒子濾波改進(jìn)方法，高斯粒子群優(yōu)化算法沒有慣性項(xiàng)，簡化了優(yōu)化計(jì)算過程，但也降低了全局搜索能力；文獻(xiàn)[10]提出基于標(biāo)準(zhǔn)粒子群優(yōu)化算法的粒子濾波改進(jìn)算法，但標(biāo)準(zhǔn)粒子群優(yōu)化算法容易陷入局部收斂。本文引入動(dòng)態(tài)調(diào)整慣性系數(shù)和變異算子對粒子群優(yōu)化算法進(jìn)行改進(jìn)搜索過程，提高算法的全局收斂速度、粒子多樣性，且避免陷入局部收斂，并在SIR-PF算法框架的基礎(chǔ)上，利用改進(jìn)的粒子群優(yōu)化算法對序貫重要性采樣后的粒子集進(jìn)行優(yōu)化，采用優(yōu)化后的粒子集進(jìn)行狀態(tài)變量估計(jì)，本文所提算法稱為基于改進(jìn)粒子群優(yōu)化的粒子濾波算法(IPSO-PF)。

1 IPSO-PF算法

1.1 基本思想

SIR-PF算法存在粒子貧化問題的根源是重采樣環(huán)節(jié)。重采樣使得高權(quán)重粒子被多次復(fù)制，低權(quán)重粒子被直接舍棄，造成重采樣后的粒子由大量重復(fù)的點(diǎn)構(gòu)成，帶來粒子貧化問題。為了解決粒子退化問題加入了粒子重采樣環(huán)節(jié)，取消重采樣環(huán)節(jié)就會(huì)導(dǎo)致計(jì)算資源的浪費(fèi)和估計(jì)結(jié)果的偏差。重采樣實(shí)際上是為了解決粒子的低效問題，而粒子數(shù)量又不能無限制的增加。引入粒子群優(yōu)化算法對序貫重要性采樣后的粒子分布進(jìn)行優(yōu)化，使得粒子集更加趨于向高似然區(qū)域移動(dòng)，提高粒子集中每個(gè)粒子的效用，又無需增加粒子數(shù)量，解決了粒子退化問題。同時(shí)，在粒子群優(yōu)化過程中，一是只存在粒子位置的變化，并且每個(gè)粒子位置變化是隨機(jī)的，二是每個(gè)粒子均得到了保留，有效解決了粒子貧化問題?？偨Y(jié)起來，通過粒子群對粒子分布的優(yōu)化既可以替代重采樣環(huán)節(jié)的作用，解決粒子退化問題，也可以解決粒子的貧化問題。IPSO-PF算法包括序貫重要性采樣、粒子群優(yōu)化過程和狀態(tài)估計(jì)3個(gè)環(huán)節(jié)。

1.2 改進(jìn)的粒子群優(yōu)化算法

假設(shè)在D空間中，隨機(jī)初始化一個(gè)粒子數(shù)為N的粒子種群N={p1,p2,…,pN}， 設(shè)第i個(gè)粒子的位置和速度分別為pxi=(xi1,xi2,…,xiD)T和pvi=(vi1,vi2,…,viD)T。 種群的個(gè)體極值表示為pbi=(pbi1,pbi2,…,pbiD)T， 全局極值表示為gb=(gb1,gb2,…,gbD)T， 粒子按照下式更新速度與位置

(1)

(2)

其中，r() 為(0，1)之間的隨機(jī)數(shù)；c1和c2為加速常數(shù)，分別代表粒子向個(gè)體極值和全局極值移動(dòng)的權(quán)重；w為慣性系數(shù)，w較大表示全局搜索能力強(qiáng)，w較小表示局部搜索能力強(qiáng)。

為了改進(jìn)搜索過程，提出一種動(dòng)態(tài)調(diào)整慣性系數(shù)的方法，使得搜索過程中慣性系數(shù)線性遞減。假設(shè)搜索的迭代次數(shù)為Maxgen，w的最大值為w_max，w的最小值為w_min， 那么迭代第ii次的慣性系數(shù)為

(3)

為了提高粒子多樣性和搜索速度，借鑒遺傳算法的變異思想，引入變異算子，每隔一定的周期L， 粒子狀態(tài)和速度按下式進(jìn)行一次更新

(4)

(5)

其中，randperm(n) 為產(chǎn)生一個(gè)[1，n]之間的整數(shù)數(shù)列。

1.3 適應(yīng)度函數(shù)

通過計(jì)算粒子集中每個(gè)粒子的適應(yīng)度值，把適應(yīng)度值最大的粒子認(rèn)定為最優(yōu)粒子，粒子群優(yōu)化算法驅(qū)使粒子向最優(yōu)粒子移動(dòng)。優(yōu)化過程使得那些遠(yuǎn)離真實(shí)狀態(tài)的粒子趨向于真實(shí)狀態(tài)出現(xiàn)概率較大的區(qū)域，進(jìn)而達(dá)到粒子分布優(yōu)化的目的。

定義粒子群優(yōu)化算法中粒子的適應(yīng)度函數(shù)為

(6)

1.4 粒子分布優(yōu)化過程

步驟2 利用式(6)計(jì)算每個(gè)粒子的適應(yīng)度值，并作為粒子局部極值；計(jì)算粒子集中的最優(yōu)適應(yīng)度值，作為粒子全局極值；

步驟3 判斷迭代次數(shù)是否能整除L， 若是，利用式(4)、式(5)更新粒子狀態(tài)和速度；若否，由式(3)得到慣性系數(shù)，由式(1)、式(2)得到粒子集迭代后的粒子狀態(tài)和速度。

步驟4 由式(6)計(jì)算當(dāng)前粒子集的適應(yīng)度值，依據(jù)適應(yīng)度值更新局部極值和全局極值。

步驟5 判斷迭代次數(shù)變量是否小于等于迭代次數(shù)Maxgen， 若是，迭代次數(shù)變量加1轉(zhuǎn)至步驟3；若否，粒子分布優(yōu)化過程結(jié)束，把當(dāng)前的粒子集送至算法下一環(huán)節(jié)處理。

1.5 算法流程

IPSO-PF算法完整的流程見表1。

2 仿真實(shí)驗(yàn)及分析

為了衡量IPSO-PF算法的濾波性能，采取典型的非線性系統(tǒng)進(jìn)行數(shù)值仿真實(shí)現(xiàn)，并與SIR-PF、PSO-PF、GPSO-PF這3種算法從濾波精度、粒子退化、粒子貧化和運(yùn)行時(shí)間4個(gè)方面進(jìn)行性能比較。

表1 IPSO-PF算法

該系統(tǒng)的過程方程和觀測方程分別為

xk=1+sin(0.04*π*k)+0.5xk-1+ωk

(7)

(8)

式中：ωk、vk分別為系統(tǒng)噪聲和觀測噪聲。

2.1 濾波精度

假設(shè)系統(tǒng)初始狀態(tài)x0=0.1， 系統(tǒng)噪聲為服從伽馬分布Γ(3,2) 噪聲，觀測噪聲方差為1的零均值高斯噪聲，粒子個(gè)數(shù)為50，仿真時(shí)間步數(shù)為60，采用IPSO-PF、SIR-PF、PSO-PF和GPSO-PF這4種算法對非線性系統(tǒng)濾波的仿真，其中IPSO-PF、PSO-PF和GPSO-PF這3種算法的加速常數(shù)和迭代次數(shù)相同，取值分別為c1=c2=2、Maxgen=20， IPSO-PF算法中慣性系數(shù)取值為w_max=0.9、w_min=0.4、L=4， PSO-PF算法中慣性系數(shù)取值為w=1.0， 4種算法的濾波估計(jì)值和誤差如圖1所示。

圖1 濾波估計(jì)值及誤差

從圖1(a)可知，4種算法在系統(tǒng)存在較大的非高斯噪聲條件下均能達(dá)到較好的濾波效果；從圖1(b)可知，SIR-PF算法的最大誤差約為6.08，PSO-PF算法的最大誤差約為6.06，GPSO-PF算法的最大誤差約為5.53，IPSO-PF算法的最大誤差約為5.50，SIR-PF算法的平均誤差約為0.96，PSO-PF算法的平均誤差約為1.03，GPSO-PF算法的平均誤差約為0.98，IPSO-PF算法的平均誤差約為0.92，與其它3種算法相比，IPSO-PF算法濾波精度稍優(yōu)。

為了比較不同算法濾波精度，引入均方根誤差RMSE作為評(píng)價(jià)指標(biāo)，其數(shù)學(xué)表達(dá)式為

(9)

圖2 均方根誤差

由圖2可知，SIR-PF算法的RMSE均值約為1.34，PSO-PF算法的RMSE均值約為1.40，GPSO-PF算法的RMSE均值約為1.34，IPSO-PF算法的RMSE均值約為1.33，4種算法濾波精度基本相同；SIR-PF算法的RMSE方差約為0.32，PSO-PF算法的RMSE方差約為0.21，GPSO-PF算法的RMSE方差約為0.19，IPSO-PF算法的RMSE方差約為0.17。與SIR-PF算法相比，3種粒子群算法穩(wěn)定性都得到大幅提高，而IPSO-PF算法穩(wěn)定性優(yōu)于另外兩種粒子群算法。

2.2 粒子退化

(10)

仿真參數(shù)不變，采用IPSO-PF、SIR-PF、PSO-PF和GPSO-PF這4種算法對非線性系統(tǒng)進(jìn)行一次濾波仿真，有效粒子數(shù)曲線如圖3所示。

圖3 有效粒子數(shù)

由圖3可知，SIR-PF算法的有效粒子數(shù)的平均值約為14.4，PSO-PF算法的有效粒子數(shù)的平均值為35.7，GPSO-PF算法的有效粒子數(shù)的平均值為46.3，而IPSO-PF算法的有效粒子數(shù)的平均值為48.6?？梢员砻鳎瑢χ匾圆蓸雍蟮牧Ｗ?，通過粒子群優(yōu)化算法進(jìn)行粒子分布優(yōu)化來代替重采樣環(huán)節(jié)，可以使濾波的有效粒子大大增加，是一種粒子解決粒子退化的有效辦法，與PSO-PF和GPSO-PF兩種算法相比，IPSO-PF算法的有效粒子數(shù)的平均值更大。

2.3 粒子貧化

仿真參數(shù)不變，采用IPSO-PF、SIR-PF、PSO-PF和GPSO-PF這4種算法對非線性系統(tǒng)濾波進(jìn)行一次仿真，取粒子在k為11和12兩個(gè)時(shí)刻的粒子真實(shí)值、IPSO-PF粒子狀態(tài)值、SIR-PF粒子狀態(tài)值、PSO-PF粒子狀態(tài)值和GPSO-PF粒子狀態(tài)值的分布情況，如圖4所示。

圖4 兩種算法的粒子狀態(tài)分布

由圖4可知，SIR-PF算法的粒子分布往往集中在少數(shù)幾個(gè)高權(quán)重狀態(tài)值上，粒子重復(fù)率高，降低了粒子的多樣性，不利于濾波的狀態(tài)估計(jì)。IPSO-PF、PSO-PF和GPSO-PF這3種算法粒子呈現(xiàn)出絕大部分粒子集中于真實(shí)值附近且粒子分布相對均勻，除此之外，仍然合理保留了少數(shù)低權(quán)重粒子，確保了粒子多樣性。與PSO-PF和GPSO-PF兩種算法相比，IPSO-PF算法在保證多樣性的同時(shí)，粒子更加集中于真實(shí)值附近。

2.4 運(yùn)行時(shí)間

在32位windows7操作系統(tǒng)、Intel酷睿i7-4500U處理器環(huán)境下，設(shè)置粒子個(gè)數(shù)分別為30、50、100、500，其它參數(shù)仿真保持不變，在MATLAB仿真運(yùn)行4種算法，運(yùn)行時(shí)間見表2。

表2 運(yùn)行時(shí)間

由表2可知，在不同粒子數(shù)目下，IPSO-PF、PSO-PF和GPSO-PF算法的運(yùn)行時(shí)間基本相同，且都大于SIR-PF算法，這是由于粒子群優(yōu)化過程代替重采樣過程，表明粒子群優(yōu)化過程的復(fù)雜度大于傳統(tǒng)的重采樣過程；IPSO-PF算法需要的粒子數(shù)量較小，這種情況下，IPSO-PF算法的運(yùn)行時(shí)間與SIR-PF算法相差不大，也能很好滿足濾波的實(shí)時(shí)性要求。

2.5 搜索過程

為了衡量IPSO-PF算法的搜索性能，仿真參數(shù)保持不變，抽取k=1時(shí)刻的序貫重要性采樣后的粒子集，采用IPSO-PF、PSO-PF和GPSO-PF這3種算法進(jìn)行粒子分布優(yōu)化的適應(yīng)函數(shù)值變化曲線如圖5所示。

圖5 適應(yīng)函數(shù)值變化曲線

由圖5可知，GPSO-PF算法收斂于局部最優(yōu)值0.3951，并且沒有改變，這是由于算法省略了慣性項(xiàng)，降低了全局搜索能力，易陷于局部最優(yōu)；PSO-PF算法在經(jīng)過一段時(shí)間后收斂于0.3989，算法具有較強(qiáng)的全局搜索能力，但收斂速度較慢，并且搜索過程后期由于粒子速度變慢也可能陷于局部最優(yōu)；IPSO-PF收斂速度較快，且具有較好的全局尋優(yōu)能力，這是由于引入動(dòng)態(tài)調(diào)整慣性系數(shù)和變異算子對粒子群優(yōu)化算法進(jìn)行改進(jìn)，提高了算法在搜索性能。

3 結(jié)束語

為解決SIR粒子濾波算法存在的粒子貧化問題，提出了基于粒子群優(yōu)化的SIR粒子濾波改進(jìn)算法IPSO-PF。與SIR-PF、PSO-PF、GPSO-PF這3種濾波算法相比，IPSO-PF算法濾波精度稍優(yōu)，且濾波穩(wěn)定度更好；在濾波過程中的有效粒子數(shù)的平均值更大，粒子退化問題也得到較好的解決；粒子大部分集中于高似然區(qū)域，但保留了少數(shù)低似然區(qū)粒子，并且粒子更加集中于真實(shí)值附近；運(yùn)行時(shí)間大于SIR-PF算法，但也能滿足實(shí)時(shí)性要求；收斂速度較快，且具有較好的全局尋優(yōu)能力。總體來講，IPSO-PF算法在增加部分運(yùn)算量的前提下，取得比SIR-PF、PSO-PF、GPSO-PF這3種算法更好的綜合濾波性能。下一步的研究重點(diǎn)是在IPSO-PF算法的基礎(chǔ)上進(jìn)行優(yōu)化，進(jìn)一步提高濾波精度和穩(wěn)定性，并降低其運(yùn)算復(fù)雜度。