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

關(guān)鍵詞：粒子退化,智能優(yōu)化算法,粒子濾波,布谷鳥搜索算法,萊維飛行機(jī)制

1引言

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

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

2理論基礎(chǔ)

2.1粒子濾波

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

粒子濾波是實(shí)現(xiàn)通過對系統(tǒng)初始狀態(tài)所獲得的先驗(yàn)知識的不斷更新后所獲得系統(tǒng)后驗(yàn)概率分布的一個遞歸的過程。其數(shù)學(xué)模型建立過程如下：

目標(biāo)的狀態(tài)方程：

                                   （1）

目標(biāo)的觀測方程：

                                  （2）

其中，分別代表了目標(biāo)的狀態(tài)模型和觀測模型，是m維空間下的非線性函數(shù)。表示k時刻下系統(tǒng)的狀態(tài)，表示k時刻下系統(tǒng)的觀測值。分別表示目標(biāo)的系統(tǒng)白噪聲和觀測噪聲。

在系統(tǒng)的先驗(yàn)概率分布已知的情況下，通過獲取新的觀測值并實(shí)時更新，由貝葉斯?fàn)顟B(tài)估計遞推出系統(tǒng)狀態(tài)的后驗(yàn)概率分布，其中。假設(shè)系統(tǒng)的初始狀態(tài)為，通過系統(tǒng)的狀態(tài)預(yù)測以及狀態(tài)更新兩個步驟遞推得到目標(biāo)狀態(tài)的后驗(yàn)概率分布：

目標(biāo)狀態(tài)預(yù)測：

                                  （3）

目標(biāo)狀態(tài)更新：

                                  （4）

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

                                  （5）

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

根據(jù)貝葉斯定理，目標(biāo)的后驗(yàn)概率密度函數(shù)可近似表示為：

                                  （6）

權(quán)值更新公式為：

                                  （7）

權(quán)值歸一化為：

                                  （8）

則目標(biāo)狀態(tài)的后驗(yàn)概率分布可近似為：

                                  （9）

2.2CuckooSearch

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

布谷鳥搜索算法充分的體現(xiàn)了物種自然選擇的優(yōu)化機(jī)制，該算法主要遵循三個原則：

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

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

(3)宿主巢的數(shù)量是固定的，設(shè)宿主所發(fā)現(xiàn)布谷鳥寄宿的卵的發(fā)現(xiàn)概率為，若此情況發(fā)生時，宿主或?qū)⒉脊萨B的卵扔出，或舍棄該巢重建新巢。

設(shè)原宿主巢內(nèi)的卵代表一個解，布谷鳥隨機(jī)寄宿的卵為一個新的解，該算法最終的優(yōu)化目標(biāo)則是由通過選取布谷鳥寄宿在巢內(nèi)的最好的卵來代替原巢內(nèi)的卵，進(jìn)而產(chǎn)生一個新的最優(yōu)解。為了充分的實(shí)施上訴的三個原則，該算法的數(shù)學(xué)模型建立如下：

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

s表示步長。

CS算法的優(yōu)化過程如下：

Step1初始時，布谷鳥隨機(jī)選擇一定數(shù)量的宿主巢并產(chǎn)卵，并評估這些宿主巢且保留當(dāng)前最好的巢從而使得下一代得以存活；

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

Step3優(yōu)勝劣汰。布谷鳥所產(chǎn)的卵若被宿主發(fā)現(xiàn)(發(fā)現(xiàn)概率為Pa)，宿主則丟棄鳥巢重建新巢或者選擇更新的巢。

Step4評估。對所有的宿主巢進(jìn)行評估，獲得當(dāng)前最佳的宿主巢位置，若該位置優(yōu)于初始時的最佳位置，則進(jìn)行替換。

Step5若當(dāng)前的搜索精度大于所設(shè)定的最大搜索次數(shù)T,則輸出最優(yōu)值，反之,則重復(fù)Step2，繼續(xù)下一代的搜索。

3基于多樣性優(yōu)化的粒子濾波模型建立

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

Step1初始采樣粒子：從先驗(yàn)概率密度函數(shù)中隨機(jī)抽取N個獨(dú)立分布的粒子樣本。

Step2根據(jù)公式(3)、(4)建立系統(tǒng)狀態(tài)模型

Step3由系統(tǒng)的先驗(yàn)概率分布和當(dāng)前觀測值，并由公式（7）計算并更新每個粒子的權(quán)值：

Step4重采樣判定：計算當(dāng)前有效粒子個數(shù)：

                                  （13）

圖1本文算法實(shí)現(xiàn)流程圖

4實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)一.目標(biāo)狀態(tài)估計比較

將本文所提出的算法與原始的粒子濾波算法以及基于粒子群優(yōu)化的粒子濾波算法(PSO-PF)在一維非穩(wěn)態(tài)、非線性的環(huán)境下，利用Matlab語言進(jìn)行編程實(shí)現(xiàn)，用Matlab對三種算法的目標(biāo)狀態(tài)估計結(jié)果進(jìn)行比較，由此來驗(yàn)證本文算法的有效性。

設(shè)目標(biāo)模型的狀態(tài)轉(zhuǎn)移模型如下：

                                  （14）

系統(tǒng)的觀測模型為：

                                  （15）

圖2粒子濾波算法狀態(tài)估計圖

圖3PSO-PF算法狀態(tài)估計圖

圖4本文算法狀態(tài)估計圖

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

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

圖5粒子濾波算法在不同狀態(tài)下的有效粒子數(shù)量

圖6本文算法在不同狀態(tài)下的有效粒子數(shù)量

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

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

5.結(jié)論

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

參考文獻(xiàn)(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]劉長平,葉春明.一種新穎的仿生群智能優(yōu)化算法:螢火蟲算法[J].計算機(jī)應(yīng)用研究,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]宋玉堅,葉春明,黃佐钘.多資源均衡優(yōu)化的布谷鳥算法[J].計算機(jī)應(yīng)用,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.