基于改進適應度函數和搜索策略的差分進化粒子濾波算法

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