改進蝠鲼覓食優化的粒子濾波算法

陸星辰，靜大海，楊佳林，李文棟，黎 瑤

(河海大學 計算機與信息學院 陣列與信息處理實驗室，江蘇 南京 211100)

0 引 言

現代工程應用中，如目標跟蹤、聲吶探測、視覺定位、電池檢測等領域[1，2]，貝葉斯濾波[3]一直扮演著重要的作用。粒子濾波[4](PF)是使用序貫蒙特卡洛法代替貝葉斯估計的樣本積分的遞推濾波，用以解決線性非高斯系統的濾波問題。

粒子濾波存在著多次迭代使粒子退化[5，6]的問題，為解決以上問題，很多學者引入智能優化算法。遺傳算法[7]可以應用于粒子濾波，高權值的粒子交叉變異概率較高，這樣在不損失多樣性的條件下，代替傳統的重采樣方法[8]。文獻[9]通過自適應設定交叉概率和變異概率，在交叉步驟的相反方向選擇變異操作，增加了粒子的信息多樣性，緩解粒子的貧化。文獻[10]使用粒子群算法優化粒子濾波，每出現一個新觀測值，群中粒子便向高似然區移動，粒子適應度達到最高時獲得最優解，增強了估計的精確度和魯棒性。將蝙蝠算法[11]優化粒子濾波，可以使局部搜索以及全局搜索間相互轉換，粒子更容易向最優位置移動，擴展了粒子的狀態搜索空間。

以上方法一定程度上緩解了粒子退化的現象，避免因重采樣而造成的粒子貧化問題[12]，但是重要性函數[13，14]選取的不適會使粒子權系數方差變大，較多的迭代次數會提高算法的時間復雜度，降低運算效率。蝠鲼覓食優化算法[15]是最新提出的群智能算法，已經證明該算法在全局尋優、收斂精度等方面優于傳統的粒子群算法等智能優化算法，具有很強的實用性。基于此，本文采用蝠鲼覓食優化算法改進粒子濾波，既提高估計精度，加快迭代速度，又解決粒子濾波存在的問題，減少濾波誤差。

1 粒子濾波算法

貝葉斯估計理論[3]是將隨機變量的先驗分布結合傳感器得到的觀測值結合起來，得到隨機變量的后驗分布，估計方差最小。粒子濾波[4]是k時刻目標狀態后驗概率密度分布可以由樣本粒子集加權求和得到，后驗概率密度p如表達式(1)所示

(1)

粒子濾波(SIR)[4]基本步驟如下：

(2)

步驟3 對重要性權值進行歸一化

(3)

(4)

步驟5 結合權值進行提取狀態估計

(5)

2 蝠鲼覓食優化算法

蝠鲼覓食優化算法(MRFO)[15]是基于海洋里蝠鲼捕魚進食的運動規律而獲得的求取最優解的搜索算法，其在避免局部最優、收斂速度和收斂精度等方面優于傳統智能算法。該算法由三階段組成，分別是鏈式覓食、螺旋覓食、翻滾覓食。

(1)鏈式覓食：當蝠鲼進行捕獵時，該群體會以一定的概率一只只排成一排，向獵物位置游動，即鏈式捕食。領頭的蝠鲼以獵物位置為目標，不斷向其游動，位置不斷更新，緊鄰的前一只蝠鲼和獵物位置決定了接在后面的蝠鲼移動方向和步長。搜索模型如表達式(6)所示，參數α由表達式(7)決定

(6)

(7)

(2)螺旋覓食：除了鏈式覓食，蝠鲼群體也按一定概率進行螺旋覓食，蝠鲼個體按首尾相接進行螺旋前進且不斷地向獵物靠近，每一只蝠鲼的螺旋游動方向和步長由緊鄰的前一只蝠鲼和隨機的新位置決定，則此算法就具備了全局搜索的搜索能力，可以搜索到全局最優解。其搜索模型如式(8)所示，β是螺旋游動的權重系數，如表達式(10)所示

(8)

(9)

(10)

除了具備搜索全局最優解的能力，還應有局部搜索的能力，當算法迭代到一定次數時，將獵物位置隨機替換為一個獵物位置，圍繞這個位置再進行螺旋覓食，以此增強算法最優解鄰域內的局部搜索能力，其搜索模型如表達式(11)所示

(11)

(3)翻滾覓食：在蝠鲼覓食算法中，翻滾覓食過程是最后一道過程，也是必須要經歷的一段過程。蝠鲼個體以獵物位置為中心點，通過旋轉游動，隨即到達一個新位置。搜索空間的大小由個體位置到獵物位置距離決定，兩者距離比較大，說明翻滾之后位置到獵物位置距離也比較大，搜索空間變大；反之，搜索空間變小。搜索模型如表達式(12)所示

(12)

式中：S為翻滾因子，取常數2；r是0到1的均勻分布隨機數。

3 蝠鲼覓食優化的粒子濾波算法

本文選取蝠鲼覓食優化算法[15]改進粒子濾波(MRFO-PF)，該優化算法所用參數較少，通過鏈式覓食和螺旋覓食兩個過程在全局最優值的引導下，驅使粒子不斷地向高似然區移動，擁有出色的局部搜索能力、收斂性以及穩定性且求得的最優解的數值精度高于其它的智能優化算法，但是該算法僅在螺旋覓食時有一定概率引入隨機點擾動，這樣優化算法仍然易陷于局部最優的情況，需要對蝠鲼覓食優化算法進行針對性的改進。本文加入粒子交叉和粒子分組兩項操作，以便加快收斂速度提高求解精度的同時更好地提升粒子濾波算法的性能。

3.1 粒子交叉

本文在前兩種覓食行為之后，引入橫向交叉[16]以增強優化算法全局搜索能力，保障粒子的多樣性，避免粒子過于集中。橫向交叉指的是搜索空間中兩個狀態不同的粒子進行的算術交叉過程。具體的操作是每一次迭代過程中，隨機選取當前時刻的粒子來組合配對，然后粒子之間以一定概率進行交叉來獲得的兩個新粒子，粒子的更新位置如表達式(13)和表達式(14)所示

(13)

(14)

通過表達式(13)和表達式(14)引入橫向交叉操作，將粒子的狀態信息有效地推廣傳播到整個濾波空間，同時此刻的最優粒子也具備更多的機會跳出當前的最優選擇。總體上來說，一方面，將橫向交叉同蝠鲼覓食優化算法結合起來，相較于原始優化算法降低了粒子陷于局部最優的概率，減少了對粒子空間盲點的處理，加快迭代收斂；另一方面，基于隨機交叉得到的新粒子增加了狀態信息的廣泛性，擴展了粒子的狀態搜索空間，同時也有利于后續的對粒子進行的分組操作，更好提升了粒子濾波的性能。

3.2 粒子分組

(15)

式中：x是運算粒子即預測觀測值，R是觀測噪聲的方差，zk是當前觀測值。高權值組的粒子按表達式(16)更新，表達式(16)受文獻[17]的啟發，本文進而對表達式(12)進行如下的改進

(16)

當hcos(r1) 處于1到2時，粒子在進行大范圍翻滾，保持全局狀態空間搜索，小于1時翻滾范圍較小，此時進行局部狀態空間開發，調節系數h決定了余弦波的振幅，影響著迭代時的搜索步長，慣性系數b增強算法靈活度，形成對全局最優值的擾動，兩者定義分別如表達式(17)和表達式(18)所示

(17)

(18)

其中，k和T分別是當前迭代次數和最大迭代次數，μ、ψ和λ分別取5、0.01、1.2。h是單調遞減的正切函數，數值迭代初期比較大，隨后數值逐漸遞減，這就實現了搜索步長從大到小的變化；相應地，初期收斂速度比較緩慢，伴隨著逐步的迭代，收斂速度逐漸加快，這樣既有利于粒子收斂到最終的最優位置，減少了算法收斂時間。慣性權重b是基于余弦函數選取的，起到調節迭代過程中全局和局部粒子的作用，提高收斂的精度。

考慮要到保留并改進低權值組的粒子，需要利用全局最優粒子對其進行線性組合從而產生新的粒子，區別于表達式(16)，表達式(12)做出如下的修改

(19)

(20)

其中，L表示移動的步長，N表示粒子總數目，q表示粒子在當前時刻全局最優值的空間鄰域內的分布概率。

由表達式(19)可以看出，低權值的粒子經當前時刻全局最優粒子的引導，慢慢地向高似然區方向靠攏，迭代過程中跳躍距離小且距離比較固定，粒子位置最終逐漸穩定；分布概率較大的低權值粒子要圍繞全局最優的粒子做左右跳躍，仍與最優粒子保持相應距離，保證了低權值的粒子不完全聚集在最優粒子附近。平衡高低權值的粒子是整個蝠鲼覓食優化算法優化粒子濾波算法的關鍵所在，對于解決粒子退化問題起決定性作用。基于此線性組合的方法使得MRFO-PF算法并不是簡簡單單地復制高權值的粒子，低權值的粒子既配合高權值的粒子快速地向最優粒子靠攏，同時自身又避免被剔除舍棄。改進的翻滾覓食方式使低權值的粒子以新粒子的形式存在于濾波之中，避免了重采樣，減少了粒子種類多樣性的損失，使迭代后的粒子分布更接近于實際的狀態后驗概率分布。

3.3 MRFO-PF算法基本步驟

改進的蝠鲼覓食優化粒子濾波算法具體步驟如下所示：

步驟2 第一個領頭的粒子依概率按表達式(6)和式(8)進行鏈式或螺旋覓食，接著身后粒子按表達式(6)和式(8)進行鏈式或螺旋覓食，迭代一定程度后表達式(8)轉式(11)進行螺旋覓食。

步驟3 按式(13)、式(14)隨機對粒子進行配對交叉。

步驟4 按適應度閾值對粒子群進行高低分組，高權值組和低權值組分別按表達式(16)和表達式(19)進行翻滾覓食。

步驟5 當高似然區粒子數達到規定數目(0.5N到0.05N)時，跳出循環停止迭代，如果沒有則轉步驟2繼續進行直到符合數目或達到迭代最大次數。

步驟6 按表達式(2)根據所獲得的粒子和當前時刻的觀測值重新計算重要性權值。

步驟7 按表達式(3)對重要性權值進行歸一化。

步驟8 結合各粒子權值按表達式(5)進行狀態提取并輸出。

MRFO-PF算法流程如圖1所示。考慮到算法的實時性，設置高似然區粒子數目閾值，當高權值組粒子數目符合條件即退出循環迭代，這樣一方面極大地提高了算法的運算效率，令一方面確保粒子不完全聚集于最優粒子附近。步驟3利用橫向交叉過程，擴大粒子的搜索范圍，增加粒子的多樣性，粒子之間的差異越大，所獲得的狀態信息將會越豐富，濾波也會獲得更好的效果，獲得令人滿意的估計精度；步驟4用粒子分組優化的方法代替傳統的重采樣算法，既緩解了部分粒子因權值過小而產生的粒子退化現象，真實做到讓每個粒子都可以起到更新迭代的作用，減少計算資源的浪費，同時又盡量避免了粒子貧化而產生的狀態信息缺失的問題，克服樣本的種類枯竭。

圖1 MRFO-PF算法的流程

4 實驗內容及結果

為了驗證MRFO-PF算法的有效性和時效性，本文將其與常規粒子濾波算法(PF)[4]、粒子群優化粒子濾波算法(PSO-PF)[10]、蝙蝠優化粒子濾波算法(BAT-PF)[11]進行仿真比較。具體是將這4種濾波算法分別在單變量一維非靜態增長模型和二維純角度觀測模型兩種非線性系統下進行對比實驗。

4.1 單變量一維非靜態增長模型

單變量一維非靜態增長系統的狀態模型x(t) 和觀測模型z(t) 如表達式(21)以及表達式(22)所示

(21)

(22)

其中，x和z分別是預測狀態量和觀測量，ω和v分別是均值為0的高斯噪聲，w是系統噪聲，其方差Q為1，v是觀測噪聲，其方差R為1。基于模型的建立和參數的選擇，該模型處于高度的非線性狀態，常規濾波算法解決起來有一定難度，所以適用于檢測和對比各濾波算法的作用和性能。

圖2至圖3是在粒子數N設置為100，濾波步長為50，數目閾值為0.4N的實驗條件下得到的各濾波器的仿真結果。圖2是4種濾波算法的濾波軌跡圖，顯示了真實的狀態，圖3表示4種濾波算法的距離誤差在各時間點的變化情況。

圖2 一維濾波軌跡

圖3 一維距離誤差

從圖2和圖3可以看出，通過對粒子的迭代，經過智能算法優化后的粒子濾波算法距離真值的誤差基本小于常規粒子濾波，MRFO-PF濾波曲線和真實值曲線擬合程度是最高的，其誤差曲線的起伏程度是濾波算法中最小的。這說明了優化算法在濾波過程中起到聚合粒子從而調整分布的作用，減少了由于重采樣產生的粒子種類缺失的問題。圖3更直接地表示出MRFO-PF濾波曲線比其它兩種優化后的算法更貼近系統真實值。以時刻43為例，其它時刻濾波誤差點都在MRFO-PF曲線上方，即同一時刻濾波估計值與真實值之間的距離誤差最小。誤差曲線直觀地表示了蝠鲼覓食優化的粒子濾波的濾波性能。

表1和表2分別是粒子數為100、50、20時4種算法的RMSE值以及單次濾波的運行時間，表中數據是做50次MCMC后取的平均值。觀察表格，橫向來看，隨著粒子數的減少，單次濾波的運行時間減少，各算法RMSE均有提高，故濾波性能下降，常規粒子濾波尤為明顯。縱向來看，相同的粒子數下，智能優化算法也要優于常規粒子濾波算法，其中MRFO-PF的RMSE較其它三者最少，濾波效果基本與圖片顯示結果一致。3種不同粒子數情況下，本文算法較常規粒子濾波算法濾波精度提高約30%，較PSO-PF算法提高約16%，較BAT-PF算法提高約12%，因此要和常規粒子濾波算法達到同等精度下，MRFO-PF減少了濾波所需的粒子數目。本文將權值小的粒子線性優化變成新粒子，故相較于拋棄權值小粒子的重采樣過程的粒子濾波算法，使起濾波作用的粒子并不僅僅局限于權值較大的粒子，粒子退化程度更小，同時保證粒子種類的多樣性，降低了濾波誤差。

表1 實驗4.1的RMSE結果對比/m

表2 實驗4.1平均單次濾波所需時間/10-3s

時間方面，由于粒子濾波沒有粒子尋優迭代的過程，所以其所需時間最少。本文算法改進了粒子尋優方式，加快了收斂速度，經過粒子交叉和粒子分組兩個操作后，相同的迭代次數下MRFO-PF的尋優精度最高，所以在滿足相同粒子數閾值的條件下MRFO-PF所需的迭代次數最少，這樣達到相同的濾波精度的所用時間較少，故MRFO-PF所需時間基本次優。總體來看，PSO-PF迭代次數平均要多于另外兩種濾波方法。本文算法由于迭代較少，具備一定的實時性。

4.2 二維純角度觀測模型

粒子濾波在雷達目標跟蹤中應用非常廣泛，這里使用在國防工業中應用廣泛的二維空間中純角度的跟蹤模型，確定站點的位置只測得目標的相對角度的觀測值而不能獲得距離的觀測值。相應的，系統的狀態模型如表達式(23)所示，觀測模型如表達式(24)所示

X(t+1)=FX(t)+Γω(t)

(23)

Z(t)=h(X(t))+v(t)

(24)

其中，X=[x，vx，y，vy]T，x、y分別是目標橫縱坐標，vx、vy分別是目標的水平和垂直方向上的分速度。此外

(25)

式中：觀測模型h是線性模型，x*、y*分別是站點橫縱坐標，T是單位時間。類似的，系統噪聲w均值為0，方差Q為10-4，觀測噪聲v均值為0，方差R為π/1800。

圖4～圖6是在粒子數為20，濾波步長為30，粒子數目閾值為0.1N的條件下得到的各濾波器的實驗結果，從而比較出MRFO-PF濾波性能。圖4表示各濾波算法的軌跡，圖5表示30步長內各濾波算法較真實值的距離誤差，圖6則表示每個采樣周期內各濾波算法的所用時間。圖4和圖5直觀地表現出隨著時間的增大，4種算法距離真實值的誤差越來越大，但是不難看出同一時刻本文算法比其它任何算法距離誤差更小，即更接近于真實值，誤差曲線基本位于其它曲線的下方，其較真實值的距離誤差最小；圖6表示本文算法運行時間基本少于其它智能算法優化濾波方法，僅高于缺少迭代常規粒子濾波算法，雖然犧牲了一定的時效性，但得到了更高的濾波精度和更低的濾波誤差。

圖4 二維濾波軌跡

圖5 二維距離誤差

圖6 單位周期內二維濾波各算法的時間對比

為方便比較不同濾波器的濾波效果，本文在100、50、20這3種不同粒子數下進行50次MCMC后取平均值，實驗的結果匯總成表3。從實驗得到的數據來分析，隨著粒子數的減少，各個分量上[x、vx、y、vy]的RMSE都在增大。以x方向上RMSE為例，在3種不同的粒子數下，對比PF、PSO-PF、BAT-PF這3種不同濾波算法，本文算法濾波誤差平均分別減少37%、28%、19%。同樣可以看出本文算法在其它分量上也基本優于其它算法，實驗4.2的數據結果基本與一維實驗一致，大量數據進一步地驗證了本文算法的有效性以及濾波的穩定性。

表3 實驗4.2的RMSE結果對比/m

5 結束語

經過兩組實驗對比，MRFO-PF算法濾波效果基本優于粒子濾波和其它智能優化的粒子濾波。從實驗結果來看，本文算法提高最優解的求解精度，減少估計誤差，降低運算時間。從實驗數據來看，本文算法濾波精度較常規粒子濾波提高30%，滿足濾波精度的條件下，減少所需粒子數目。

MRFO-PF算法優越處主要有以下幾點：①在鏈式覓食和螺旋覓食兩個過程后隨機對粒子進行橫向交叉，增大粒子搜索范圍，提高粒子種類，降低陷入局部最優的概率；②按適應度分組粒子，分別利用改進的翻滾過程更新，用全局最優值引導粒子，加快收斂速度，同時線性優化低權值組，保留并改進低權值粒子，改善粒子退化問題，避免因重采樣而造成的粒子貧化現象。有效性、實時性以及穩定性的提高使MRFO-PF算法具備理論意義和使用價值，具備較好的跟蹤性能，接下來的研究主要是考慮如何將MRFO-PF算法應用于實際的工程應用以及進一步地探索在不同的應用背景和濾波條件下粒子數該如何選取。