摘要：針對粒子濾波算法在進行目標狀態估計過程中所出現的粒子退化問題，本文提出了一種基于粒子多樣性優化的粒子濾波算法。在傳統粒子濾波算法(ParticleFilter-PF)的重采樣過程中，融入了布谷鳥搜索優化算法(CuckooSearch-CK)，該算法利用萊維飛行機制(LevyFlight)擴大了搜索范圍，充分的增加了有效粒子的數量，保留了粒子的多樣性，解決了傳統粒子濾波算法陷入局部最優的困境。實驗表明：本文提出的算法有效的改善了粒子退化現象，提高了目標狀態的估計精度，充分保留了有效粒子的數量；在降低了算法的計算復雜程度的同時提高了算法的魯棒性和實時性。

關鍵詞：粒子退化,智能優化算法,粒子濾波,布谷鳥搜索算法,萊維飛行機制

1引言

近年來，粒子濾波算法[1-3](Particlefilter-PF)在計算機視覺領域范圍內有著廣泛的應用與研究價值。粒子濾波算法其本質是一種基于貝葉斯推理[4]和蒙特卡洛方法的一種統計濾波方法。它將蒙特卡洛的抽樣原理與貝葉斯推理進行有效的結合，解決了卡爾曼濾波的線性高斯約束問題，為非線性高斯問題提供了一個簡單處理、操作方便的解決環境。但原始的粒子濾波算法在運行過程中會出現粒子退化和匱乏的問題，會使得粒子的多樣化喪失，從而造成算法陷入了局部最優解，大大降低了目標狀態估計精度。因此，許多學者提出了利用智能優化算法來解決粒子的退化問題，常用的優化算法如遺傳算法[5](GeneticAlgorithm-GA)、螢火蟲算法[6](GlowwormSwarmOptimization-GSO)粒子群算法[7](ParticleSwarmOptimization-PSO)等。遺傳算法(GA)是模擬生物進化原理的一種啟發式算法，是目前應用最為廣泛的智能優化算法之一，該算法有著良好的全局搜索能力，解決了算法陷入局部最優的現象，能夠快速的搜索出最優解。但該算法的局部搜索能力較弱，因為在算法的運行過程中會出現早熟的現象；螢火蟲算法(GSO)是一種模擬自然界中螢火蟲生活行為活動的智能優化算法。該算法具有優化速度快，計算過程簡單的優點。但算法的計算精度以及收斂速度是其最大的弊端；粒子群算法(PSO)有效的抑制了原始粒子濾波算法的粒子退化問題，但該算法存在著計算量大、計算時間長，重采樣粒子分布帶寬發散，粒子分布方差變化大的缺點。

本文提出了一種基于粒子多樣性優化的粒子濾波算法，有效的解決了粒子退化與匱乏的問題。在原始粒子濾波重采樣過程中引入基于群體智能化的布谷鳥搜素優化算法[8-11](CuckooSearch-CK)，該算法利用萊維飛行機制[12-13](LevyFlight)擴大了搜索范圍，充分的增加了有效粒子的數量，保留了粒子的多樣性，解決了傳統粒子濾波算法陷入局部最優的困境。

2理論基礎

2.1粒子濾波

粒子濾波算法其本質是一種基于貝葉斯估計理論和蒙特卡洛重要性采樣方法的具有非線性、非高斯的濾波方法。其中心思想是在狀態空間鄰域內隨機抽取的一組稱為“粒子”的離散型隨機樣本的，通過對這些“粒子”加權后所得到的相對密度分布來估計目標狀態的后驗概率分布。當樣本的數量足夠多時，這些“粒子”的后驗概率分布會越來越逼近于真實的后驗概率分布。

粒子濾波是實現通過對系統初始狀態所獲得的先驗知識的不斷更新后所獲得系統后驗概率分布的一個遞歸的過程。其數學模型建立過程如下：

目標的狀態方程：

                                   （1）

目標的觀測方程：

                                  （2）

其中，分別代表了目標的狀態模型和觀測模型，是m維空間下的非線性函數。表示k時刻下系統的狀態，表示k時刻下系統的觀測值。分別表示目標的系統白噪聲和觀測噪聲。

在系統的先驗概率分布已知的情況下，通過獲取新的觀測值并實時更新，由貝葉斯狀態估計遞推出系統狀態的后驗概率分布，其中。假設系統的初始狀態為，通過系統的狀態預測以及狀態更新兩個步驟遞推得到目標狀態的后驗概率分布：

目標狀態預測：

                                  （3）

目標狀態更新：

                                  （4）

其中，是已知的的，表示k時刻的先驗概率分布，是一階馬爾可夫過程，通過目標的模型方程與噪聲統計所得到的概率分布。是系統的觀測似然函數,由公式(2)推導而得。但通常情況下，由于系統狀態的先驗概率分布到求解后驗概率分布的最優估計過程存在著復雜的積分運算，因此需要采用序列重要性采樣這一基于蒙特卡洛的隨即抽樣方法，用一個能夠方便采樣的概率密度分布函數來代替難以采樣的先驗概率密度分布。便于采樣的概率密度函數就叫做重要性函數。重要性函數通過抽取的采樣點的加權求和近似得到原概率密度函數：

                                  （5）

其中為狄克拉函數，也叫單位脈沖函數，且。二者之間的聯系由公式(5)可以看出，重要性函數的加權求和就可近似得到原先驗概率密度分布。

根據貝葉斯定理，目標的后驗概率密度函數可近似表示為：

                                  （6）

權值更新公式為：

                                  （7）

權值歸一化為：

                                  （8）

則目標狀態的后驗概率分布可近似為：

                                  （9）

2.2CuckooSearch

布谷鳥搜索算法（CuckooSearch-CS）是由Yang和Deb在2009年提出的一種元啟發式優化算法。該算法融入布谷鳥的繁殖策略思想，同時該算法還引入了其他種群普遍具有的隨即飛行行為，即萊維飛行機制。布谷鳥算法的仿生思想是：布谷鳥將自己所產的卵寄居在與自己食性、身體顏色、以及的形狀都相似的宿主巢內，這樣可以在一定程度上保留了自己卵的存活幾率。如若被宿主發現，宿主或者將布谷鳥所產的卵“丟棄”，或者舍棄鳥巢重建新窩。因此，布谷鳥所寄居卵的的存活概率的高低往往是由其寄居宿主巢的優劣所決定，若與所寄居的宿主的習性以及卵的形狀等特性越接近，布谷鳥后代的存活概率則越高。

布谷鳥搜索算法充分的體現了物種自然選擇的優化機制，該算法主要遵循三個原則：

(1)每一個布谷鳥一次僅可產一顆卵，并將其寄宿在隨機選擇的宿主巢中；

(2)若所寄居的巢的宿主與布谷鳥的習性具有高相似性，既布谷鳥的卵具有高存活率，并產生布谷鳥的下一代。

(3)宿主巢的數量是固定的，設宿主所發現布谷鳥寄宿的卵的發現概率為，若此情況發生時，宿主或將布谷鳥的卵扔出，或舍棄該巢重建新巢。

設原宿主巢內的卵代表一個解，布谷鳥隨機寄宿的卵為一個新的解，該算法最終的優化目標則是由通過選取布谷鳥寄宿在巢內的最好的卵來代替原巢內的卵，進而產生一個新的最優解。為了充分的實施上訴的三個原則，該算法的數學模型建立如下：

定義1.應用萊維飛行機制(LevyFlight)表達宿主巢更新公式為：

s表示步長。

CS算法的優化過程如下：

Step1初始時，布谷鳥隨機選擇一定數量的宿主巢并產卵，并評估這些宿主巢且保留當前最好的巢從而使得下一代得以存活；

Step2根據公式(10)或(12)來更新巢的位置；

Step3優勝劣汰。布谷鳥所產的卵若被宿主發現(發現概率為Pa)，宿主則丟棄鳥巢重建新巢或者選擇更新的巢。

Step4評估。對所有的宿主巢進行評估，獲得當前最佳的宿主巢位置，若該位置優于初始時的最佳位置，則進行替換。

Step5若當前的搜索精度大于所設定的最大搜索次數T,則輸出最優值，反之,則重復Step2，繼續下一代的搜索。

3基于多樣性優化的粒子濾波模型建立

系統目標狀態估計的精準度與粒子數量的選擇有著密切直接的聯系，理論上講，隨機抽取的粒子數量越多，系統的后驗概率密度分布估計就越準確，但選擇過多的粒子進行狀態的估計不僅會無限增加算法的計算復雜度，并且很大程度上的降低了算法的實時性，同時還會將算法陷入局部最優。本文所提出的基于粒子多樣性優化的粒子濾波算法中，融入布谷鳥搜索優化算法僅選擇少量的最優粒子，在布谷鳥搜索過程中，每一個粒子都表示一個宿主巢，并執行巢的位置更新的萊維飛行機制，最后集合所有的巢并選擇出一個最優的宿主巢。本文算法實現流程如下：

Step1初始采樣粒子：從先驗概率密度函數中隨機抽取N個獨立分布的粒子樣本。

Step2根據公式(3)、(4)建立系統狀態模型

Step3由系統的先驗概率分布和當前觀測值，并由公式（7）計算并更新每個粒子的權值：

Step4重采樣判定：計算當前有效粒子個數：

                                  （13）

圖1本文算法實現流程圖

4實驗結果分析

實驗一.目標狀態估計比較

將本文所提出的算法與原始的粒子濾波算法以及基于粒子群優化的粒子濾波算法(PSO-PF)在一維非穩態、非線性的環境下，利用Matlab語言進行編程實現，用Matlab對三種算法的目標狀態估計結果進行比較，由此來驗證本文算法的有效性。

設目標模型的狀態轉移模型如下：

                                  （14）

系統的觀測模型為：

                                  （15）

圖2粒子濾波算法狀態估計圖

圖3PSO-PF算法狀態估計圖

圖4本文算法狀態估計圖

由圖2-4可以看出，采用原始的粒子濾波算法不能夠有效并精準的進行狀態估計，而PSO-PF算法隨較原始的粒子濾波算法在目標的狀態估計有了很大的提高，但本文算法的目標狀態估計相比仍存在較大的誤差，因此，本文提出的算法所進行的目標狀態估計最接近于真實的目標狀態。

由于在原始的粒子濾波算法中經常會出現粒子退化問題，通過算法的多次迭代，粒子的數量會低于最初所抽取的數量，同時很大程度的喪失了粒子的多樣性。按照實驗一中的系統模型參數設置，圖5所示為采用原始的粒子濾波算法在每一個狀態下所剩余粒子的數量；圖6所示為采用本文算法在每一個狀態下所剩余的粒子數量；表1所示為三種算法執行的運行時間與均方根誤差。

圖5粒子濾波算法在不同狀態下的有效粒子數量

圖6本文算法在不同狀態下的有效粒子數量

由圖5-6可以看出，圖5所采用粒子濾波算法所進行的狀態估計粒子退化的現象明顯，在對目標狀態估計的許多情況下，粒子退化程度趨近于零，使得算法時而失效，不能很好的估測出真實的目標狀態；圖6所采用的本文算法中，粒子的數量在各個狀態估計下幾乎都趨近于初始數量500，僅有少數次狀態估計時粒子喪失接近于零。由此可見，本文所采用的算法能夠更好的保持著粒子的數量，同時充分的保留的粒子的多樣性，使得算法更有效的對目標狀態進行估計，具有很高的準確率和優化效率。

由表1可以看出，本文所采用的算法相對于PF和PSO-PF算法，在運行過程中能夠產生較小的誤差，算法運行時間較短，失誤率小，從而有著良好的狀態估計效果和良好的實時性。

5.結論

本文所提出的基于粒子多樣性優化的粒子濾波算法，融入了基于種群優化機制的布谷鳥搜索算法，克服了傳統粒子濾波算法由于自身存在的粒子退化問題而不能夠準備的進行狀態估計的難題。仿真實驗中通過與傳統PF算法以及PSO-PF算法在目標的狀態估計、粒子退化數量、運行時間以及產生的均方根誤差比較得出：采用本文所提出的算法進行狀態估計更能夠接近目標的真實狀態，有著很高的狀態估測效率；充分保留粒子多樣性以及粒子樣本數量的同時有著良好的實時性和較小的誤差率。

參考文獻(References):

[1]XuX,LiB.AdaptiveRao–BlackwellizedParticleFilterandItsEvaluationforTrackinginSurveillance[J].Proceedingsof2007

16thIEEEInternationalConferenceonImage,2007,16(3):838-849.

[2]LepoutreA,RabasteO,LeGlandF.AparticlefilterfortargetarrivaldetectionandtrackinginTrack-BeforeDetect[C].Proceedings

of20128thIEEEInternationalConferenceonSensorDataFusion:Trends,Solutions,Applications,2012:13-18.

[3]HouYB,TangSY.BreedingEstimatedParticleFilter[J].AdvancedMaterialsResearch,2013:332-337.

[4]PrakashJ,GopaluniRB,PatwardhanSC,etal.NonlinearBayesianstateestimation:Reviewandrecenttrends[C].Proceedingsof

201115thIEEEInternationalConferenceonAdvancedControlofIndustrialProcesses,2011:450-455.

[5]El-DahshanEA.GeneticalgorithmandwavelethybridschemeforECGsignaldenoising[J].TelecommunicationSystems,2011,

46(3):209-215.

[6]劉長平,葉春明.一種新穎的仿生群智能優化算法:螢火蟲算法[J].計算機應用研究,2011,(9):3295-3297

[7]BagheriA,PeyhaniHM,AkbariM.FinancialforecastingusingANFISnetworkswithQuantum-behavedParticleSwarmOptimiza

-tion[J].ExpertSystemswithApplications,2014,41:6235–6250.

[8]Jr.IF,YangX,FisterD,etal.CuckooSearchandFireflyAlgorithm[M].SpringerInternationalPublishing,2014:49-62.

[9]ValianE,TavakoliS,MohannaS,etal.Improvedcuckoosearchforreliabilityoptimizationproblems[J].ComputersandIndustrial

Engineering,2013,(1):459-468.

[10]MohamadA,ZainAM,BazinNEN,etal.CuckooSearchAlgorithmforOptimizationProblems-ALiteratureReview[J].Appli

-edMechanicsandMaterials,2013:502-506.

[11]宋玉堅,葉春明,黃佐钘.多資源均衡優化的布谷鳥算法[J].計算機應用,2014,34(1):189-193.

[12]DasS,DasguptaP,PanigrahiBK.Swarm,Evolutionary,andMemeticComputing[M].SpringerInternationalPublishing,2013:

515-526.

[13]SenthilnathJ,DasV,N.OmkarS,etal.ClusteringUsingLevyFlightCuckooSearch[M].Proceedingsof20137thIEEEInternati

-ionalConferenceonBio-InspiredComputing:TheoriesandApplications.India,IEEEPress,2013:65-75.