改進(jìn)的布谷鳥(niǎo)算法優(yōu)化粒子濾波研究

王曉華，聶騰騰

西安工程大學(xué) 電子信息學(xué)院，西安710048

1 引言

粒子濾波器（Particle Filter，PF）是非線性和非高斯?fàn)顟B(tài)估計(jì)最有用的工具之一[1-3]。但由于重采樣引起的樣本貧化缺陷限制了估計(jì)的準(zhǔn)確性[4-5]，學(xué)者們采取了很多辦法來(lái)改進(jìn)濾波器性能。傳統(tǒng)方法[6-7]是通過(guò)改進(jìn)重采樣來(lái)優(yōu)化粒子濾波。近年來(lái)，將生物智能算法[8-9]如螢火蟲(chóng)、蝙蝠、布谷鳥(niǎo)算法等被引進(jìn)到粒子濾波中，解決粒子貧化退化等問(wèn)題，具有良好的發(fā)展前景。文獻(xiàn)[10]利用螢火蟲(chóng)算法迭代尋優(yōu)的思想優(yōu)化粒子分布，但螢火蟲(chóng)算法本身存在著對(duì)于初始解分布的依賴(lài)性；文獻(xiàn)[11]提出了基于自控蝙蝠算法優(yōu)化粒子濾波的機(jī)動(dòng)目標(biāo)跟蹤方法，但蝙蝠個(gè)體本身缺乏變異機(jī)制，一旦受到某個(gè)局部極值約束后自身很難擺脫。CS算法參數(shù)較少：除了種群規(guī)模之外，CS算法基本上只有一個(gè)參數(shù)pα需要調(diào)整。而算法的收斂速度對(duì)參數(shù)pα不敏感，這意味著CS算法的通用性很好，魯棒性較強(qiáng)，易于與粒子濾波結(jié)合。Han等[12]結(jié)合布谷鳥(niǎo)搜索算法與粒子濾波器（CS-PF）來(lái)估計(jì)測(cè)量信號(hào)的缺陷輪廓，并成功應(yīng)用于故障檢測(cè)中，所提的方法明顯優(yōu)于單獨(dú)使用布谷鳥(niǎo)算法，但算法的搜索效率還有待提高。黃辰等[13]將多策略差分變異過(guò)程引入布谷鳥(niǎo)算法中，增加排隊(duì)優(yōu)選機(jī)制，并將改進(jìn)的布谷鳥(niǎo)算法應(yīng)用到粒子濾波（ICS-PF）中，解決了粒子濾波算法中的粒子貧化問(wèn)題。但上述方法，并未解決算法局部尋優(yōu)與全局尋優(yōu)的矛盾。

為協(xié)調(diào)布谷鳥(niǎo)算法局部尋優(yōu)與全局尋優(yōu)的能力，本文對(duì)布谷鳥(niǎo)算法進(jìn)行改進(jìn)：一方面，在Lévy飛行過(guò)程中改變步長(zhǎng)值α，以保證全局搜索時(shí)的種群多樣性；另一方面，改進(jìn)布谷鳥(niǎo)算法的宿主鳥(niǎo)卵的概率pα，以調(diào)整局部隨機(jī)搜索獲得最優(yōu)解的能力，并將改進(jìn)的布谷鳥(niǎo)算法用來(lái)優(yōu)化粒子濾波，提出一種改進(jìn)的布谷鳥(niǎo)算法優(yōu)化粒子濾波方法（Particle Filter Based on Cuckoo Search，CS-PF），算法的局部尋優(yōu)與全局尋優(yōu)得到平衡，能夠更有效地探索搜索空間，進(jìn)一步提高了估計(jì)精度。

2 主要算法基本原理

2.1 布谷鳥(niǎo)算法

劍橋大學(xué)學(xué)者Yang和Deb通過(guò)對(duì)布谷鳥(niǎo)尋窩產(chǎn)卵行為的模擬，提出了一種全局搜索的布谷鳥(niǎo)搜索（Cuckoo Search，CS）算法[14-15]。布谷鳥(niǎo)也叫杜鵑。該算法是受一些杜鵑種群的行為和Lévy飛行的啟發(fā)而發(fā)展起來(lái)的。

布谷鳥(niǎo)執(zhí)行Lévy飛行以尋找新巢，公式（1）是尋找宿主鳥(niǎo)窩的位置和路徑的更新公式：

其中，t是迭代次數(shù)，u和v都遵循正態(tài)分布。

對(duì)于第k個(gè)宿主鳥(niǎo)窩，迭代時(shí)第d維的位置更新為：

其中，bnestd是第d維度中全局最佳鳥(niǎo)窩的位置；r是正態(tài)分布后的隨機(jī)數(shù)，均值為0，方差為1；c1是步長(zhǎng)系數(shù)，通常設(shè)置為0.01。宿主巢中的每個(gè)布谷鳥(niǎo)的卵都有可能被其宿主鳥(niǎo)發(fā)現(xiàn)，被發(fā)現(xiàn)的概率為pα。

2.2 改進(jìn)布谷鳥(niǎo)搜索算法

CS是一種簡(jiǎn)單，參數(shù)少，易于實(shí)現(xiàn)的算法，但在算法后期會(huì)出現(xiàn)算法搜索速度慢、精度不高等缺點(diǎn)，所以需要通過(guò)優(yōu)化CS來(lái)提高算法的性能[16-18]。優(yōu)化的目的是提高布谷鳥(niǎo)的全局搜索能力，通過(guò)考慮正確的產(chǎn)卵時(shí)間來(lái)提高布谷鳥(niǎo)卵的繁殖力，以及剛孵出的布谷鳥(niǎo)雛鳥(niǎo)所采取的行為。布谷鳥(niǎo)優(yōu)化的所采取的假設(shè)是：

（1）將鳥(niǎo)卵放在隨機(jī)選擇的巢中。

（2）只有具有最佳卵的巢才能讓下一代存活下來(lái)。

（3）預(yù)先確定宿主巢（通常是其他物種）的數(shù)量，并且估計(jì)宿主發(fā)現(xiàn)卵的概率為pα∈(0,1)。

CS中引入的參數(shù)pα、λ和α分別幫助算法找到全局和局部改進(jìn)的解。參數(shù)pα和α是解向量微調(diào)的非常重要的參數(shù)，可以用于調(diào)整算法的收斂速度。傳統(tǒng)的CS算法對(duì)pα和α都使用固定值。這些值在初始化步驟中設(shè)置，并且在新一代中不能更改，該方法的主要缺點(diǎn)出現(xiàn)在尋找最優(yōu)解的迭代次數(shù)中，這可能需要更多次迭代才能找到最優(yōu)解。如果pα的值很小并且α的值很大，則算法的性能將很差并且導(dǎo)致迭代次數(shù)的顯著增加。如果pα的值很大而α的值很小，則收斂速度很快，但可能無(wú)法找到最佳解。

所以關(guān)鍵在于調(diào)整pα和α。為了提高CS算法的性能并消除考慮pα和α的固定值所導(dǎo)致的缺點(diǎn)，改進(jìn)的算法使用變量pα和α。

通過(guò)改進(jìn)的布谷鳥(niǎo)搜索算法中pα和α的值，根據(jù)公式（4）～（6）每次迭代進(jìn)行調(diào)整。

其中，變量c是當(dāng)前迭代次數(shù)，所選常量n是迭代總次數(shù)。其中尋找到最佳鳥(niǎo)窩位置時(shí)迭代的總次數(shù)就是改進(jìn)布谷鳥(niǎo)算法停止尋優(yōu)的標(biāo)準(zhǔn)。

2.2.1 改進(jìn)CS收斂速度

改進(jìn)的布谷鳥(niǎo)的收斂性相對(duì)于CS算法收斂速度提高了，因?yàn)榈螖?shù)減少了。通過(guò)調(diào)整pα和α的值，避免了因pα和α的值過(guò)大或過(guò)小而導(dǎo)致算法的收斂性降低，如pα的值如果很小而α的值很大，則算法的性能將很差并且導(dǎo)致迭代次數(shù)的顯著增加，收斂速度慢；如果pα的值很大而α的值很小，則收斂速度很快，但可能無(wú)法找到最佳解。所以動(dòng)態(tài)調(diào)整pα和α的值，可以加快算法的收斂速度。

2.2.2 改進(jìn)CS種群多樣性

改進(jìn)的CS算法種群多樣性提高。首先鳥(niǎo)窩更新迭代后通過(guò)式（4）～（6）來(lái)進(jìn)行算法改進(jìn)；然后根據(jù)迭代次數(shù)動(dòng)態(tài)地計(jì)算鳥(niǎo)窩放棄概率pα，通過(guò)不同的概率來(lái)動(dòng)態(tài)地調(diào)整不同時(shí)期的種群多樣性，使得算法可以靈活地調(diào)整種群多樣性，提高了算法的收斂速度。

2.3 基本的粒子濾波

2.3.1 標(biāo)準(zhǔn)粒子濾波

粒子濾波器最初由Gordon于1993年引入，作為用于估計(jì)非線性和非高斯?fàn)顟B(tài)的自舉濾波器[19]。下面簡(jiǎn)要介紹粒子濾波的過(guò)程[20]，粒子濾波算法過(guò)程圖如圖1所示。

粒子濾波器的遞歸過(guò)程包括兩個(gè)步驟：

圖1 粒子濾波算法過(guò)程圖

（1）預(yù)測(cè)。

（2）更新。根據(jù)給定的在線測(cè)量序列zm={zi:i=1,2,…,m}進(jìn)行更新。

在預(yù)測(cè)步驟中，在時(shí)刻m被確定為：

使用公式（7）給預(yù)測(cè)的粒子分配標(biāo)準(zhǔn)化的權(quán)重：

其中，j∈1,2,…,N,δ()?由xm-1和wk-1值所表示的狄拉克函數(shù)δ。在重抽樣中，新樣本通過(guò)重新采樣N次生成估計(jì)的，以便對(duì)于任何j

2.3.2 粒子多樣性度量

文獻(xiàn)[10-11]講述了生物智能算法會(huì)增加粒子濾波中的粒子多樣性，文獻(xiàn)[8]給出了粒子多樣性度量的指標(biāo)。

2.4 改進(jìn)布谷鳥(niǎo)搜索算法與粒子濾波結(jié)合

為克服傳統(tǒng)的粒子濾波算法中存在的粒子貧化問(wèn)題，本文將改進(jìn)的布谷鳥(niǎo)算法引入到粒子濾波算法的重采樣過(guò)程中。改進(jìn)CS-PF算法具體實(shí)現(xiàn)步驟如下：

（1）初始化。在初始時(shí)刻k=0時(shí)按照初始樣本分布p(x0)進(jìn)行采樣，產(chǎn)生的N個(gè)粒子作為初始樣本{ xm(0)}( m=1,2,…,N)，xm(k)服從重要性密度函數(shù)。

（2）設(shè)置每個(gè)粒子的權(quán)重為wj=1/N。

（3）采用改進(jìn)的CS來(lái)優(yōu)化粒子，模擬布谷鳥(niǎo)優(yōu)化算法的全局搜索行為：

①進(jìn)入優(yōu)化的初始粒子

②將該粒子樣本引入改進(jìn)CS中，根據(jù)式（4）～（6）對(duì)每次迭代進(jìn)行調(diào)整，得到進(jìn)化后的新粒子集，當(dāng)?shù)进B(niǎo)窩的位置越來(lái)越接近最佳位置時(shí)，步長(zhǎng)越小，當(dāng)?shù)进B(niǎo)窩的位置離最佳位置較遠(yuǎn)時(shí)，步長(zhǎng)越大。這樣，根據(jù)上一次迭代的結(jié)果來(lái)動(dòng)態(tài)更新本次迭代的移動(dòng)步長(zhǎng)，算法的搜索速度和尋優(yōu)精度都有較大的提高。在改進(jìn)的布谷鳥(niǎo)算法中，所采用的適應(yīng)度函數(shù)為：

③改進(jìn)的CS的搜索策略去執(zhí)行粒子濾波重采樣過(guò)程。

（4）計(jì)算新粒子的重要性權(quán)值并進(jìn)行歸一化處理。

（5）輸出粒子狀態(tài)。求改進(jìn)的CS-PF后輸出粒子的均值。

2.4.1 改進(jìn)CS-PF收斂性分析

其中，uk(B)為算法D第k次迭代的結(jié)果在集合B上的概率測(cè)度。

定理1當(dāng)鳥(niǎo)窩位置的群體內(nèi)部迭代趨于無(wú)窮次時(shí)，群體狀態(tài)序列必將進(jìn)入最優(yōu)狀態(tài)集H。

定理2改進(jìn)的CS-PF算法收斂于全局最優(yōu)。

證明 首先改進(jìn)的CS-PF算法每次迭代都保存了群體最優(yōu)位置，保證了適應(yīng)值的非增性，所以隨機(jī)算法的收斂滿(mǎn)足條件1。其次由定理1知，改進(jìn)CS-PF算法經(jīng)過(guò)連續(xù)無(wú)窮次迭代，鳥(niǎo)窩位置的群體序列必將進(jìn)入最優(yōu)狀態(tài)，所以，連續(xù)無(wú)窮次搜索不到全局最優(yōu)解的可能性是0。因此，滿(mǎn)足隨即算法的收斂條件2，故改進(jìn)的CS-PF算法收斂于全局最優(yōu)。

2.4.2 改進(jìn)CS-PF時(shí)間復(fù)雜度

標(biāo)準(zhǔn)粒子濾波的時(shí)間復(fù)雜度受初始化粒子個(gè)數(shù)N和重采樣粒子數(shù)N1時(shí)的影響，粒子數(shù)越多，時(shí)間復(fù)雜度越高，所以它的時(shí)間復(fù)雜度為T(mén)(n)=O( N+N1)。

從改進(jìn)CS-PF的詳細(xì)過(guò)程來(lái)分析，影響算法效率的因素主要有兩個(gè)：一是粒子數(shù)N2；二是宿主發(fā)現(xiàn)卵的概率為pα和隨機(jī)步長(zhǎng)α。計(jì)算給定個(gè)體的目標(biāo)函數(shù)的執(zhí)行時(shí)間是個(gè)體維數(shù)n的函數(shù)f(n)，時(shí)間復(fù)雜度為O( n+f(n))，則總體時(shí)間時(shí)間復(fù)雜度為T(mén)(n)=O( N2+n+f(n ))。其中N2＜N，大多數(shù)情況下，給定個(gè)體的目標(biāo)函數(shù)的執(zhí)行時(shí)間是個(gè)體維數(shù)n較小，所以改進(jìn)的CS-PF具有較低的時(shí)間復(fù)雜度。

3 實(shí)驗(yàn)仿真

實(shí)驗(yàn)環(huán)境是在Inter Core i5-3230M，內(nèi)存8 GB的華碩筆記本上運(yùn)行的，軟件環(huán)境Matlab2014b，本文仿真對(duì)象采用的非線性系統(tǒng)模型如下：

此模型是研究各種PF算法性能時(shí)的常用模型。其中x(t)是系統(tǒng)t時(shí)刻的狀態(tài)，u(t)是系統(tǒng)狀態(tài)方程中的零均值高斯噪聲，y(t)是系統(tǒng)t時(shí)刻的測(cè)量值，v(t)是測(cè)量方程中的零均值高斯噪聲。初始狀態(tài)x=0.1，過(guò)程噪聲和測(cè)量噪聲分別是1，粒子數(shù)N=200，取不同的pα值，觀察高似然區(qū)平均粒子數(shù)M1和每次平均更新的粒子次數(shù)M2。

通過(guò)實(shí)驗(yàn)仿真的方法，確定重要參數(shù)pα的取值范圍，并驗(yàn)證算法的有效性。

pα的合適區(qū)域?yàn)椋?.2～0.3）。如圖2所示：pα的值影響著算法的運(yùn)算量。當(dāng)pα＜0.2時(shí)，高似然區(qū)的粒子數(shù)平均有44.37個(gè)，粒子平均更新的次數(shù)是42.38次，這樣使得算法運(yùn)算量增加，粒子多樣性喪失，如果增加粒子數(shù)，算法的實(shí)時(shí)性也會(huì)受到影響。當(dāng)pα＞0.45時(shí)，大部分粒子沒(méi)有更新，在高似然區(qū)的粒子數(shù)也較少，這樣會(huì)使算法精度降低。所以要保證粒子足夠獨(dú)多分布在高似然區(qū)，且運(yùn)算量不能太高，要保證算法的實(shí)時(shí)性，即選擇合適區(qū)域?yàn)椋?.2～0.3）。

實(shí)驗(yàn)中使用的粒子數(shù)為N=200個(gè)，觀測(cè)時(shí)間為T(mén)=60，濾波步數(shù)k=100,pα=0.25，將改進(jìn)的CS-PF與標(biāo)準(zhǔn)的PF、EK-PF、CS-PF、ICS-PF進(jìn)行100次獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)的目的是比較各算法的非線性系統(tǒng)狀態(tài)估計(jì)及均方根誤差。均方誤差定義為：

實(shí)驗(yàn)結(jié)果由圖3可以看出，改進(jìn)的CS-PF算法精度高，EK-PF、CS-PF、ICS-PF算法精度較高，而PF算法精度較差。這是因?yàn)镻F算法采用了先驗(yàn)概率轉(zhuǎn)移密度作為重要性采樣，忽略了當(dāng)前時(shí)刻的測(cè)量值，所以精度較差；而改進(jìn)的算法均結(jié)合了當(dāng)前系統(tǒng)的測(cè)量值信息的重要性采樣密度，所以精度相對(duì)較高。

圖2 粒子數(shù)隨著pa值變化的曲線圖

表1 不同算法估計(jì)誤差對(duì)比

表1是經(jīng)過(guò)100次獨(dú)立實(shí)驗(yàn)得出的不同重要性采樣密度的粒子濾波算法的均方誤差的均值以及運(yùn)行時(shí)間的均值對(duì)比結(jié)果。對(duì)于不同的粒子數(shù)，基本PF算法的均方誤差最高；EK-PF低于PF算法，但相比CS-PF、ICS-PF、改進(jìn)CS-PF算法相比要高，其中改進(jìn)的CS-PF的RMSE值最低。其中，對(duì)于不同的粒子數(shù)，改進(jìn)的CS-PF雖然濾波精度比基本PF低，但運(yùn)行時(shí)間卻高。

為進(jìn)一步比較標(biāo)準(zhǔn)PF算法與改進(jìn)CS-PF算法的粒子多樣性，選取粒子N=50、100、150、200，觀察粒子在空間的狀態(tài)如圖3所示。

圖3 狀態(tài)估計(jì)結(jié)果對(duì)比圖

由圖4可以看出，隨著粒子數(shù)的增多，改進(jìn)的CS-PF粒子在狀態(tài)空間的分布更加廣泛，在高概率值的附近粒子數(shù)較多，低概率值旁粒子較少，所以改進(jìn)的CS-PF算法能夠減少粒子貧化，增加粒子的多樣性。

由表2觀察ρ值可以得知，改進(jìn)的CS-PF比PF的粒子多樣性更好，說(shuō)明改進(jìn)的CS-PF算法增加了粒子多樣性，從而保證估計(jì)精度的提高。

表2 PF與改進(jìn)CS-PF多樣性指標(biāo)ρ對(duì)比

4 結(jié)論

布谷鳥(niǎo)算法是一種全局尋優(yōu)能力強(qiáng)，參數(shù)少，易于與其他算法結(jié)合但也存在收斂速度慢、種群多樣性較差等問(wèn)題，為改善算法本身的不足，通過(guò)改進(jìn)pα和α值來(lái)改進(jìn)布谷鳥(niǎo)算法，平衡布谷鳥(niǎo)算法局部尋優(yōu)與全局尋優(yōu)，然后用改進(jìn)的CS的搜索策略來(lái)取代粒子濾波重采樣步驟，以避免粒子樣本貧化。粒子通過(guò)模擬布谷鳥(niǎo)個(gè)體，使粒子在全局搜素范圍內(nèi)尋找到最優(yōu)的位置，也就是使粒子更準(zhǔn)確地分布在真實(shí)值的附近。仿真結(jié)果表明：改進(jìn)的布谷鳥(niǎo)優(yōu)化粒子濾波，能有效解決粒子在濾波過(guò)程中出現(xiàn)的粒子貧化的問(wèn)題，增加粒子的多樣性，運(yùn)算精度也較大提高。

圖4 粒子空間圖