基于改進適應(yīng)度函數(shù)和搜索策略的差分進化粒子濾波算法

基于改進適應(yīng)度函數(shù)和搜索策略的差分進化粒子濾波算法

顆粒濾波是一種使用顆粒作為可靠的后驗概率密度分布的序貫蒙特卡羅法。作為一種有效的方法，它可以處理非線性和非高斯狀態(tài)的評估問題。顆粒濾波廣泛應(yīng)用于數(shù)據(jù)處理、目標跟蹤、機器人定位、數(shù)據(jù)處理等領(lǐng)域。為了解決顆粒過濾權(quán)重值退化的問題，選擇了重采樣的大權(quán)重。重采樣時，許多重采樣結(jié)果中有許多重復(fù)點。經(jīng)過多次重復(fù)，當被重復(fù)使用時，顆粒集中在幾個地方，導(dǎo)致描述后的概率密度采樣點太少或不足，從而影響過濾的精度，尤其是在樣品有限的情況下。針對重采樣所造成的粒子多樣性減弱和濾波精度下降的問題,研究人員提出了粒子濾波的多種改進方法,其中將成熟的多種不同尋優(yōu)方法引入重采樣過程,以便快速地提取到反映系統(tǒng)概率特征的典型粒子逐漸成為重采樣方法的研究熱點.基于粒子群優(yōu)化的粒子濾波方法(POS-PF)作為其中的典型代表被深入研究,使得該方法在粒子多樣性和局部搜索能力上都有所提高.同時,文獻中將遺傳算法和蟻群算法與粒子濾波結(jié)合,有效抑制了粒子貧化的現(xiàn)象.文獻中將多智能體協(xié)同進化機制引入粒子濾波,通過粒子間的競爭、交叉、變異以及自學習等進化行為來實現(xiàn)重采樣過程.文獻中則采用人工物理優(yōu)化方法改進粒子濾波,通過模型定義了粒子間的吸引力與排斥力,使得粒子集的分布性更好.文獻中提出了DE-MC(DifferentEvolution-MarkovChain)粒子濾波,將微分進化算法與MH(MetropolisHastings)采樣方法相結(jié)合對粒子的分布進行優(yōu)化,并實現(xiàn)對三維空間中人體運動的跟蹤.文獻中則對比了差分進化粒子濾波在不同搜索策略下的濾波精度.上述的各類方法提升粒子濾波性能的關(guān)鍵在于通過優(yōu)化過程將粒子引導(dǎo)至后驗概率密度取值較高的位置,但是在后驗概率密度未知的情況下如何保證所提取的粒子更能反應(yīng)系統(tǒng)的后驗分布是上述方法能否優(yōu)化粒子的關(guān)鍵.適應(yīng)度函數(shù)是優(yōu)化算法中的一個重要概念,用于引導(dǎo)群體的優(yōu)化過程,目前已有的智能優(yōu)化粒子濾波僅依據(jù)似然函數(shù)或粒子權(quán)值優(yōu)化粒子,使得進化過程嚴重依賴于似然函數(shù)或粒子權(quán)值,且搜索策略具有一定的盲目性,造成大量無效粒子的產(chǎn)生,降低了粒子的利用效率,雖然粒子的多樣性有了顯著改善,但濾波精度并沒有大幅提升.基于此,本文通過自適應(yīng)融合系數(shù)融合粒子的權(quán)值和量測誤差定義了新的適應(yīng)度函數(shù),提出了一種改進差分進化的高精度粒子濾波算法(IDE-PF).該算法利用新定義的適應(yīng)度函數(shù)引導(dǎo)粒子的優(yōu)化過程,使粒子集向后驗概率密度取值較大的區(qū)域運動,同時利用新的搜索策略在保持粒子多樣性的同時,盡可能提高算法的收斂速度.結(jié)果表明,與POS-PF和DE-MCPF相比,本文算法既具有較好的局部搜索能力,同時改善了粒子濾波的樣本貧化現(xiàn)象,提高了濾波的精度,減少了算法的優(yōu)化時間.1顆粒過濾和重采樣1.1觀測方程和態(tài)態(tài)方程粒子濾波是貝葉斯估計基于抽樣理論的一種近似算法,其基本思想是尋找一組在狀態(tài)空間中的隨機樣本對條件后驗概率密度進行近似,用樣本均值代替積分運算,從而獲得對狀態(tài)的最小方差估計.假設(shè)狀態(tài)方程和觀測方程分別為:式中:xk為k時刻的狀態(tài)變量;yk為k時刻的觀測值;f和g為非線性函數(shù);vk和uk分別為系統(tǒng)噪聲和觀測噪聲,具有方差Qk和Rk.在k時刻,粒子濾波首先通過預(yù)測采樣獲得新的粒子集,即并利用下式近似該時刻的后驗概率密度:式中:N為k時刻的粒子數(shù)目;δ(·)為狄利克雷函數(shù);wki為權(quán)值.依據(jù)序貫重要性采樣原理,重要性權(quán)值的更新公式可表示為式中,q(xki|xik-1,yk)即為建議分布函數(shù),當采樣的粒子數(shù)目足夠多時,由重要性采樣定理即可保證粒子集{xki,wki}Ni=1所描述的分布逼近真實的后驗概率密度.1.2采用智能優(yōu)化算法優(yōu)化粒子濾波粒子濾波中一個普遍問題就是粒子退化現(xiàn)象,即經(jīng)多次迭代后,粒子的權(quán)重集中到少數(shù)粒子上,而其他粒子的權(quán)重很小,導(dǎo)致粒子集無法表達真實的后驗概率分布.重采樣是解決粒子退化問題的有效方法,該方法在評估粒子權(quán)值后,維持粒子總數(shù)不變的條件下刪減低權(quán)值的粒子,復(fù)制高權(quán)值的粒子,增強粒子的采樣效率,從而改善粒子退化現(xiàn)象,然而重采樣會引起樣本貧化的問題,其復(fù)制和刪減粒子的策略將必然導(dǎo)致粒子多樣性的減弱,在損失信息的同時增加了隨機采樣的不確定性.為了確定粒子的退化程度,常采用有效粒子數(shù)來衡量:智能優(yōu)化粒子濾波在解決粒子退化問題上具有較好的效果,在一定程度上提高了狀態(tài)估計的精度.但是,智能優(yōu)化算法在控制粒子的多樣性,以及對尋優(yōu)過程的引導(dǎo)能力上,尚有不足.依據(jù)已有重采樣的思想,在采用智能優(yōu)化算法優(yōu)化粒子濾波時,常以權(quán)值最大化作為優(yōu)化的目標,即k時刻第i個粒子的適應(yīng)度為當以先驗分布作為建議分布函數(shù)時,可得適應(yīng)度函數(shù)為式中:yki為xki對應(yīng)的量測.而另一種常用的適應(yīng)度函數(shù)為該適應(yīng)度函數(shù)將最新的量測值引入采樣優(yōu)化過程,增強了量測值的修正作用,故在量測精度高的場合可有較好的效果.2適應(yīng)度函數(shù)的引入依據(jù)已有的基于智能優(yōu)化思想的粒子濾波算法,式(7)和(8)都可以作為適應(yīng)度函數(shù)引導(dǎo)粒子的優(yōu)化,但是在不同的量測環(huán)境下兩者的優(yōu)化效果各不相同.因此,本文將上述2種適應(yīng)度函數(shù)按自適應(yīng)的比例進行融合,定義了一種新的適應(yīng)度函數(shù),并在差分進化算法中引入新的搜索策略,使得IDE-PF可以達到收斂速度與尋優(yōu)能力的最佳平衡,提高濾波器的性能.2.1個結(jié)論和一個變異個體差分進化算法(DE)是一種隨機的并行直接搜索算法,其基本思想是從某一隨機產(chǎn)生的初始種群開始,按照一定的操作規(guī)則不斷迭代,并根據(jù)每一個體的適應(yīng)度值,保留優(yōu)良個體,淘汰劣質(zhì)個體,引導(dǎo)搜索過程向最優(yōu)解逼近.算法具有結(jié)構(gòu)簡單、易于實現(xiàn)、無需梯度信息和參數(shù)較少等優(yōu)點,并具有多種不同的搜索策略.算法運行過程中保持種群規(guī)模不變,并定義了3種運算過程:(1)變異.對于個體Xi按下式生成變異個體:式中:Xr1、Xr2和Xr3為從進化種群中隨機選取的互不相同的3個個體;F為縮放比例因子,用于控制差向量的影響大小.(2)交叉.為增加種群的多樣性,引入下述交叉操作:式中,pCR∈[0,1]為交叉概率.(3)選擇.交叉后的個體和父代個體Xi按下式進行選擇操作生成子代個體:2.2改進差分進化算法粒子濾波中粒子的多樣性是濾波器性能的一個重要指標,多樣性程度越高濾波器的性能越好.同時,多樣性的程度還會影響優(yōu)化算法的尋優(yōu)速度和局部搜索能力,多樣性程度高,算法的全局尋優(yōu)能力強,但局部搜索能力和尋優(yōu)速度會下降.因此,如何在粒子多樣性與尋優(yōu)能力之間進行有效的權(quán)衡是提高算法性能的關(guān)鍵.差分進化算法具有多種不同的搜索策略,可分為2類:一類是基準粒子隨機選取,如式(8),此時算法的全局收斂性好,但是收斂速度慢;另一類是基準粒子選擇當前種群中適應(yīng)度值最大的粒子,雖然收斂速度快,但是易陷入局部最優(yōu).為此,Zhu等受粒子群優(yōu)化算法的啟發(fā)給出了一種新的搜索策略:式中:Xbest為當前種群中的適應(yīng)度值最大的粒子;F1為[-1,1]之間的隨機數(shù);F2為[0,1.5]之間的隨機數(shù).該搜索策略由于受最優(yōu)粒子的引導(dǎo),在保證尋優(yōu)能力的同時也能提高算法的收斂速度.2.3信度標準適應(yīng)度函數(shù)的引入適應(yīng)度函數(shù)是衡量粒子可信度的一個標準,若適應(yīng)度高,則粒子的可信度高;若適應(yīng)度低,則粒子的可信度低.依據(jù)差分進化算法的演化過程,適應(yīng)度低的粒子將逐步按照一定的概率被拋棄和替換,因此適應(yīng)度函數(shù)的設(shè)定會嚴重影響粒子集進化的結(jié)果.目前,式(7)和(8)是2種常被采用的適應(yīng)度函數(shù),相關(guān)文獻中對智能優(yōu)化粒子濾波如何定義適應(yīng)度函數(shù)并未做詳細討論.依據(jù)重采樣的思路,重采樣就是選擇大權(quán)值粒子、拋棄小權(quán)值粒子的過程,所以權(quán)值可以作為衡量粒子可信度的一個標準.其次,量測值可以反映實際狀態(tài)的信息,特別是在高精度的量測場合,故粒子的量測值與實際量測之間的差值的大小也可以作為衡量粒子可信度的標準.對于上述2種不同的可信度衡量標準,本文按照一定的比例系數(shù)將2種可信度標準進行融合,定義了新的適應(yīng)度函數(shù),并依據(jù)優(yōu)化的程度,定義了自適應(yīng)的融合系數(shù).定義新的適應(yīng)度函數(shù)為式中,σ為自適應(yīng)融合系數(shù),0<σ<1.通過σ可以調(diào)整2種可信度標準在最終的粒子可信度中所占的比重.令{xkg,i,i=1,2,…,N}表示k時刻進化至第g代的粒子集,g≤最大進化次數(shù)Gmax,N為粒子數(shù),其對應(yīng)的量測值表示為集合{ykg,i,i=1,2,…,N},量測值的均值:則融合系數(shù)的取值定義為式中,yk為k時刻的實際量測.在進化的初期,當部分粒子的量測嚴重偏離實際量測時,σ應(yīng)取接近于1的值,以便快速提取到量測偏差較小的粒子;當粒子的量測值均比較接近實際量測時,則σ取接近于0的值,以便提取權(quán)值更優(yōu)的粒子.從式(13)定義的適應(yīng)度函數(shù)可知,量測誤差|yk-yki|小的粒子適應(yīng)度高,這使得在多次優(yōu)化迭代后,量測值的均值yk-g逐漸接近實際量測值yk,故σ的取值在進化過程會逐步減小,滿足了從進化初期到進化后期對σ取值由大變小的要求.同時,當粒子的量測均值很接近實際量測時,可認為粒子已被優(yōu)化到了最佳的程度,故σ也被作為判斷進化過程是否終止的條件,當σ≤σmin時則終止進化.2.4計算相關(guān)系數(shù)的選取粒子集本文IDE-PF算法的計算過程如下:(1)初始化.在k=0時刻進行采樣,將所得N個粒子{x0i}Ni=1作為初始樣本,初始樣本的分布為x0i~p(x0).(2)重要性采樣.設(shè)定k=k+1,由重要密度函數(shù)抽取當前時刻的粒子{xki}Ni=1,并計算當前量測值{yki}Ni=1,重要性密度函數(shù)為(3)差分進化重采樣:(1)g=1,進化的初始粒子{xkg,i}Ni=1={xki}Ni=1;(2)對粒子集{xkg,i}Ni=1按式(12)進行變異操作,然后按式(10)進行交叉操作,得候選粒子集;(3)依據(jù)式(13)~(15)計算候選粒子集的適應(yīng)度值,并按式(11)進行選擇操作,所得粒子集為{xkg+1,i}Ni=1;(4)若g<Gmax且σ>σmin,設(shè)定g=g+1轉(zhuǎn)入(2);否則轉(zhuǎn)入下一步.(4)狀態(tài)輸出.將優(yōu)化后的粒子集作為等權(quán)的樣本{xki,wki=N-1}Ni=1,計算狀態(tài)估計:(5)判斷是否結(jié)束,若是,退出算法,否則轉(zhuǎn)入(2).3實驗結(jié)果與分析為驗證IDE-PF算法的精度和運算時間等基本性能,本文利用典型一維非線性系統(tǒng)模型對算法的性能進行仿真,并與PF、POS-PF和DE-MCPF進行對比.實驗環(huán)境為DELLInspiron1320,內(nèi)存2GB,CPU為Intel-T4400.一維非線性系統(tǒng)模型如下:模型的系統(tǒng)噪聲uk-1~Γ(3,2),總的觀測時間T=60,實驗中粒子數(shù)目分別設(shè)定為N=100和N=10,微分進化算法交叉概率pCR=0.9,最大進化迭代次數(shù)Gmax=10.實驗1(粒子優(yōu)化程度及粒子量測值的精度分析).在第k步預(yù)測中,重要性采樣得到的粒子集被當做微分進化的初始種群,之后在適應(yīng)度函數(shù)的引導(dǎo)下,通過多次迭代不斷地優(yōu)化種群的分布,直到進化代數(shù)達到規(guī)定的上限.本實驗取量測噪聲的分布為vk~N(0,0.00001),粒子數(shù)N=100,進化迭代上限Gmax=10,優(yōu)化迭代結(jié)束的閾值σmin=0.001.圖1給出了一次仿真中第20步預(yù)測(k=20)的迭代進化過程中粒子分布的變化,圖2則顯示了每次進化中粒子對應(yīng)的量測值的變化過程.從圖1中可以看到,g=1時,粒子為重要性采樣得到的粒子,此時粒子分布很分散,分布區(qū)間的長度為3,對應(yīng)的估計值與真實狀態(tài)之間的誤差達到了2.2,圖2中粒子集對應(yīng)的量測值與真實量測值的偏差也較大,最大偏差達到了1.9.在之后的多次進化過程中,圖1所顯示的粒子集分布區(qū)間長度逐漸縮小至2左右,且狀態(tài)估計值逐漸靠近真實狀態(tài),同時狀態(tài)估計值對應(yīng)的量測逐漸靠近實際量測.產(chǎn)生上述變化的原因是新定義的適應(yīng)度函數(shù)中量測值的修正作用.因為量測噪聲小,所以量測值的修正作用強,各粒子對應(yīng)的量測值不斷靠近真實的量測值,同時粒子的分布也逐漸向真實狀態(tài)靠近且分布相對較集中,從而對粒子的分布起到了很好的優(yōu)化作用.實驗2(跟蹤性能對比與分析).為對比4種算法的跟蹤性能,對每一種算法進行RMC=200次獨立蒙特卡洛仿真,并定義k時刻的均方根誤差為式中,xk,j和分別為第j次仿真中k時刻的實際和預(yù)測狀態(tài).實驗中量測噪聲vk~N(0,0.00001),圖3所示分別給出了粒子數(shù)N=100和N=10的2種設(shè)置下4種算法時刻均方根誤差的對比.同時,定義一次蒙特卡洛仿真的均方根誤差公式為取粒子數(shù)N=100,增加系統(tǒng)量測噪聲強度后,進行200次蒙特卡洛仿真并取平均值,實驗結(jié)果如表1所示.從圖3中可以看出,IDE-PF的時刻均方根誤差最小,說明其估計精度最高,且隨著粒子數(shù)的減少估計精度仍優(yōu)于另外3種算法.從表1實驗結(jié)果中可以看出,采用優(yōu)化算法的粒子濾波誤差明顯小于標準粒子濾波算法,這是由于尋優(yōu)過程提高了粒子的質(zhì)量.但是,優(yōu)化過程也增加了算法的執(zhí)行時間,IDE-PF在達到優(yōu)化需求的情況下即停止優(yōu)化,故運算時間少于POS-PF和DE-MCPF.每種方法優(yōu)化后的粒子濾波精度存在較大差別,IDE-PF的濾波精度最高,POS-PF的濾波精度高于DE-MCPF,但算法運行時間最長,由此可見粒子的多樣性與尋優(yōu)速度之間的平衡對最終的優(yōu)化效果具有顯著影響.本文所提IDE-PF算法在粒子數(shù)較少量測噪聲較大的情況下,跟蹤精度均好于其他3種算法.實驗3(粒子多樣性的對比和分析).量測噪聲的分布取為vk~N(0,0.00001),粒子數(shù)目N=100,圖4~7對比了PF、POS-PF、DE-MCPF和IDE-PF4種算法重采樣后得到的粒子集的分布與真實狀態(tài)之間的關(guān)系,以及粒子集的集中程度的對比.從圖4中可以發(fā)現(xiàn),PF算法在重采樣后粒子的分布非常集中,這說明在重采樣之前所得到的高權(quán)值的粒子數(shù)目少,而重采樣后