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

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

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