摘要：針對(duì)粒子濾波算法在進(jìn)行目標(biāo)狀態(tài)估計(jì)過程中所出現(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)的估計(jì)精度，充分保留了有效粒子的數(shù)量；在降低了算法的計(jì)算復(fù)雜程度的同時(shí)提高了算法的魯棒性和實(shí)時(shí)性。

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

1引言

近年來，粒子濾波算法[1-3](Particlefilter-PF)在計(jì)算機(jī)視覺領(lǐng)域范圍內(nèi)有著廣泛的應(yīng)用與研究價(jià)值。粒子濾波算法其本質(zhì)是一種基于貝葉斯推理[4]和蒙特卡洛方法的一種統(tǒng)計(jì)濾波方法。它將蒙特卡洛的抽樣原理與貝葉斯推理進(jìn)行有效的結(jié)合，解決了卡爾曼濾波的線性高斯約束問題，為非線性高斯問題提供了一個(gè)簡單處理、操作方便的解決環(huán)境。但原始的粒子濾波算法在運(yùn)行過程中會(huì)出現(xiàn)粒子退化和匱乏的問題，會(huì)使得粒子的多樣化喪失，從而造成算法陷入了局部最優(yōu)解，大大降低了目標(biāo)狀態(tài)估計(jì)精度。因此，許多學(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)行過程中會(huì)出現(xiàn)早熟的現(xiàn)象；螢火蟲算法(GSO)是一種模擬自然界中螢火蟲生活行為活動(dòng)的智能優(yōu)化算法。該算法具有優(yōu)化速度快，計(jì)算過程簡單的優(yōu)點(diǎn)。但算法的計(jì)算精度以及收斂速度是其最大的弊端；粒子群算法(PSO)有效的抑制了原始粒子濾波算法的粒子退化問題，但該算法存在著計(jì)算量大、計(jì)算時(shí)間長，重采樣粒子分布帶寬發(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ì)是一種基于貝葉斯估計(jì)理論和蒙特卡洛重要性采樣方法的具有非線性、非高斯的濾波方法。其中心思想是在狀態(tài)空間鄰域內(nèi)隨機(jī)抽取的一組稱為“粒子”的離散型隨機(jī)樣本的，通過對(duì)這些“粒子”加權(quán)后所得到的相對(duì)密度分布來估計(jì)目標(biāo)狀態(tài)的后驗(yàn)概率分布。當(dāng)樣本的數(shù)量足夠多時(shí)，這些“粒子”的后驗(yàn)概率分布會(huì)越來越逼近于真實(shí)的后驗(yàn)概率分布。

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

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

                                   （1）

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

                                  （2）

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

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

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

                                  （3）

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

                                  （4）

其中，是已知的的，表示k時(shí)刻的先驗(yàn)概率分布，是一階馬爾可夫過程，通過目標(biāo)的模型方程與噪聲統(tǒng)計(jì)所得到的概率分布。是系統(tǒng)的觀測(cè)似然函數(shù),由公式(2)推導(dǎo)而得。但通常情況下，由于系統(tǒng)狀態(tài)的先驗(yàn)概率分布到求解后驗(yàn)概率分布的最優(yōu)估計(jì)過程存在著復(fù)雜的積分運(yùn)算，因此需要采用序列重要性采樣這一基于蒙特卡洛的隨即抽樣方法，用一個(gè)能夠方便采樣的概率密度分布函數(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)化算法。該算法融入布谷鳥的繁殖策略思想，同時(shí)該算法還引入了其他種群普遍具有的隨即飛行行為，即萊維飛行機(jī)制。布谷鳥算法的仿生思想是：布谷鳥將自己所產(chǎn)的卵寄居在與自己食性、身體顏色、以及的形狀都相似的宿主巢內(nèi)，這樣可以在一定程度上保留了自己卵的存活幾率。如若被宿主發(fā)現(xiàn)，宿主或者將布谷鳥所產(chǎn)的卵“丟棄”，或者舍棄鳥巢重建新窩。因此，布谷鳥所寄居卵的的存活概率的高低往往是由其寄居宿主巢的優(yōu)劣所決定，若與所寄居的宿主的習(xí)性以及卵的形狀等特性越接近，布谷鳥后代的存活概率則越高。

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

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

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

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

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

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

s表示步長。

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

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

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

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

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

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

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

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

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

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

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

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

                                  （13）

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

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

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

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

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

                                  （14）

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

                                  （15）

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

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

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

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

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

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

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

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

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

5.結(jié)論

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