改進的布谷鳥算法優化粒子濾波研究

王曉華，聶騰騰

西安工程大學 電子信息學院，西安710048

1 引言

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

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

2 主要算法基本原理

2.1 布谷鳥算法

劍橋大學學者Yang和Deb通過對布谷鳥尋窩產卵行為的模擬，提出了一種全局搜索的布谷鳥搜索（Cuckoo Search，CS）算法[14-15]。布谷鳥也叫杜鵑。該算法是受一些杜鵑種群的行為和Lévy飛行的啟發而發展起來的。

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

其中，t是迭代次數，u和v都遵循正態分布。

對于第k個宿主鳥窩，迭代時第d維的位置更新為：

其中，bnestd是第d維度中全局最佳鳥窩的位置；r是正態分布后的隨機數，均值為0，方差為1；c1是步長系數，通常設置為0.01。宿主巢中的每個布谷鳥的卵都有可能被其宿主鳥發現，被發現的概率為pα。

2.2 改進布谷鳥搜索算法

CS是一種簡單，參數少，易于實現的算法，但在算法后期會出現算法搜索速度慢、精度不高等缺點，所以需要通過優化CS來提高算法的性能[16-18]。優化的目的是提高布谷鳥的全局搜索能力，通過考慮正確的產卵時間來提高布谷鳥卵的繁殖力，以及剛孵出的布谷鳥雛鳥所采取的行為。布谷鳥優化的所采取的假設是：

（1）將鳥卵放在隨機選擇的巢中。

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

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

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

所以關鍵在于調整pα和α。為了提高CS算法的性能并消除考慮pα和α的固定值所導致的缺點，改進的算法使用變量pα和α。

通過改進的布谷鳥搜索算法中pα和α的值，根據公式（4）～（6）每次迭代進行調整。

其中，變量c是當前迭代次數，所選常量n是迭代總次數。其中尋找到最佳鳥窩位置時迭代的總次數就是改進布谷鳥算法停止尋優的標準。

2.2.1 改進CS收斂速度

改進的布谷鳥的收斂性相對于CS算法收斂速度提高了，因為迭代次數減少了。通過調整pα和α的值，避免了因pα和α的值過大或過小而導致算法的收斂性降低，如pα的值如果很小而α的值很大，則算法的性能將很差并且導致迭代次數的顯著增加，收斂速度慢；如果pα的值很大而α的值很小，則收斂速度很快，但可能無法找到最佳解。所以動態調整pα和α的值，可以加快算法的收斂速度。

2.2.2 改進CS種群多樣性

改進的CS算法種群多樣性提高。首先鳥窩更新迭代后通過式（4）～（6）來進行算法改進；然后根據迭代次數動態地計算鳥窩放棄概率pα，通過不同的概率來動態地調整不同時期的種群多樣性，使得算法可以靈活地調整種群多樣性，提高了算法的收斂速度。

2.3 基本的粒子濾波

2.3.1 標準粒子濾波

粒子濾波器最初由Gordon于1993年引入，作為用于估計非線性和非高斯狀態的自舉濾波器[19]。下面簡要介紹粒子濾波的過程[20]，粒子濾波算法過程圖如圖1所示。

粒子濾波器的遞歸過程包括兩個步驟：

圖1 粒子濾波算法過程圖

（1）預測。

（2）更新。根據給定的在線測量序列zm={zi:i=1,2,…,m}進行更新。

在預測步驟中，在時刻m被確定為：

使用公式（7）給預測的粒子分配標準化的權重：

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

2.3.2 粒子多樣性度量

文獻[10-11]講述了生物智能算法會增加粒子濾波中的粒子多樣性，文獻[8]給出了粒子多樣性度量的指標。

2.4 改進布谷鳥搜索算法與粒子濾波結合

為克服傳統的粒子濾波算法中存在的粒子貧化問題，本文將改進的布谷鳥算法引入到粒子濾波算法的重采樣過程中。改進CS-PF算法具體實現步驟如下：

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

（2）設置每個粒子的權重為wj=1/N。

（3）采用改進的CS來優化粒子，模擬布谷鳥優化算法的全局搜索行為：

①進入優化的初始粒子

②將該粒子樣本引入改進CS中，根據式（4）～（6）對每次迭代進行調整，得到進化后的新粒子集，當迭代到鳥窩的位置越來越接近最佳位置時，步長越小，當迭代到鳥窩的位置離最佳位置較遠時，步長越大。這樣，根據上一次迭代的結果來動態更新本次迭代的移動步長，算法的搜索速度和尋優精度都有較大的提高。在改進的布谷鳥算法中，所采用的適應度函數為：

③改進的CS的搜索策略去執行粒子濾波重采樣過程。

（4）計算新粒子的重要性權值并進行歸一化處理。

（5）輸出粒子狀態。求改進的CS-PF后輸出粒子的均值。

2.4.1 改進CS-PF收斂性分析

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

定理1當鳥窩位置的群體內部迭代趨于無窮次時，群體狀態序列必將進入最優狀態集H。

定理2改進的CS-PF算法收斂于全局最優。

證明 首先改進的CS-PF算法每次迭代都保存了群體最優位置，保證了適應值的非增性，所以隨機算法的收斂滿足條件1。其次由定理1知，改進CS-PF算法經過連續無窮次迭代，鳥窩位置的群體序列必將進入最優狀態，所以，連續無窮次搜索不到全局最優解的可能性是0。因此，滿足隨即算法的收斂條件2，故改進的CS-PF算法收斂于全局最優。

2.4.2 改進CS-PF時間復雜度

標準粒子濾波的時間復雜度受初始化粒子個數N和重采樣粒子數N1時的影響，粒子數越多，時間復雜度越高，所以它的時間復雜度為T(n)=O( N+N1)。

從改進CS-PF的詳細過程來分析，影響算法效率的因素主要有兩個：一是粒子數N2；二是宿主發現卵的概率為pα和隨機步長α。計算給定個體的目標函數的執行時間是個體維數n的函數f(n)，時間復雜度為O( n+f(n))，則總體時間時間復雜度為T(n)=O( N2+n+f(n ))。其中N2＜N，大多數情況下，給定個體的目標函數的執行時間是個體維數n較小，所以改進的CS-PF具有較低的時間復雜度。

3 實驗仿真

實驗環境是在Inter Core i5-3230M，內存8 GB的華碩筆記本上運行的，軟件環境Matlab2014b，本文仿真對象采用的非線性系統模型如下：

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

通過實驗仿真的方法，確定重要參數pα的取值范圍，并驗證算法的有效性。

pα的合適區域為（0.2～0.3）。如圖2所示：pα的值影響著算法的運算量。當pα＜0.2時，高似然區的粒子數平均有44.37個，粒子平均更新的次數是42.38次，這樣使得算法運算量增加，粒子多樣性喪失，如果增加粒子數，算法的實時性也會受到影響。當pα＞0.45時，大部分粒子沒有更新，在高似然區的粒子數也較少，這樣會使算法精度降低。所以要保證粒子足夠獨多分布在高似然區，且運算量不能太高，要保證算法的實時性，即選擇合適區域為（0.2～0.3）。

實驗中使用的粒子數為N=200個，觀測時間為T=60，濾波步數k=100,pα=0.25，將改進的CS-PF與標準的PF、EK-PF、CS-PF、ICS-PF進行100次獨立實驗，實驗的目的是比較各算法的非線性系統狀態估計及均方根誤差。均方誤差定義為：

實驗結果由圖3可以看出，改進的CS-PF算法精度高，EK-PF、CS-PF、ICS-PF算法精度較高，而PF算法精度較差。這是因為PF算法采用了先驗概率轉移密度作為重要性采樣，忽略了當前時刻的測量值，所以精度較差；而改進的算法均結合了當前系統的測量值信息的重要性采樣密度，所以精度相對較高。

圖2 粒子數隨著pa值變化的曲線圖

表1 不同算法估計誤差對比

表1是經過100次獨立實驗得出的不同重要性采樣密度的粒子濾波算法的均方誤差的均值以及運行時間的均值對比結果。對于不同的粒子數，基本PF算法的均方誤差最高；EK-PF低于PF算法，但相比CS-PF、ICS-PF、改進CS-PF算法相比要高，其中改進的CS-PF的RMSE值最低。其中，對于不同的粒子數，改進的CS-PF雖然濾波精度比基本PF低，但運行時間卻高。

為進一步比較標準PF算法與改進CS-PF算法的粒子多樣性，選取粒子N=50、100、150、200，觀察粒子在空間的狀態如圖3所示。

圖3 狀態估計結果對比圖

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

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

表2 PF與改進CS-PF多樣性指標ρ對比

4 結論

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

圖4 粒子空間圖