基于改進麻雀搜索算法的粒子濾波研究

石 硬,韓玉蘭,薛 麗

(寧夏大學物理與電子電氣工程學院,寧夏銀川 750021)

0 引言

粒子濾波[1](particle filter,PF)技術在非線性、非高斯系統問題上表現出來的卓越性與優(yōu)異性使其被廣泛應用于各個領域,如雷達跟蹤[2]、工業(yè)領域的機器壽命預測[3]與電池壽命預測[4]、交通管制領域的人車追蹤[5-6]、室內機器人定位[7-8]等。但是粒子濾波存在退化現象[9],引入重采樣過程在減輕退化的同時又帶來了粒子貧化現象[10]。使用大量樣本雖可得到較好的預測結果但需較大的計算量,影響算法運行效率從而降低了算法性能。相關研究學者針對粒子貧化現象進行了大量的研究與改進[11-13],雖然相關改進算法都針對原有粒子濾波有所改進,但是改進后的算法仍無法完全避免重采樣過程。

群智能優(yōu)化算法的提出為改進粒子濾波的狀態(tài)估計過程提供了新的思路,目前已經有多種群智能優(yōu)化算法成功應用于粒子濾波[14-18],但群智能優(yōu)化算法本身也存在相應的缺點,如易局部收斂、全局搜索能力弱等,如何針對粒子濾波的狀態(tài)估計過程改進相關尋優(yōu)策略,快速準確地得到全局最優(yōu)解成為當前急需解決的問題。麻雀搜索算法[19](sparrow search algorithm,SSA)是一種提出于2020年的新型群智能優(yōu)化算法,仿真結果證明[19]麻雀搜索算法在精度、收斂速度、穩(wěn)定性和魯棒性方面均優(yōu)于灰狼優(yōu)化算法( GWO)、引力搜索算法( GSA)和粒子群優(yōu)化算法( PSO)等。目前還沒有麻雀搜索算法與粒子濾波結合的相關研究,將麻雀搜索算法應用于粒子濾波的狀態(tài)估計過程有助于群智能優(yōu)化理論算法與粒子濾波的進一步應用。

為了解決粒子濾波重采樣導致的粒子貧化問題,本文將麻雀搜索算法引入粒子濾波中,提出了一種基于改進麻雀搜索算法的粒子濾波算法(a particle filtering algorithm based on an improved sparrow search algorithm,SSA-PF)。SSA-PF將粒子狀態(tài)值看作麻雀個體位置,通過發(fā)現者、跟隨者、警戒者的迭代尋優(yōu)更新粒子位置,引導粒子群體逐漸向狀態(tài)估計的高似然域移動,整個過程保留了所有粒子信息,不需要重采樣過程,從根本上解決了粒子貧化問題。并且,為了進一步提高濾波性能,SSA-PF針對麻雀搜索算法直接應用于粒子濾波狀態(tài)估計時出現的全局搜索能力不足、樣本分布不合理等問題綜合粒子濾波求解思想進行了相應的改進:使用Logistic-tent map初始化分布以提高種群多樣性,幫助算法增強后續(xù)解的質量;加入比例系數以及使用新的發(fā)現者更新策略增強SSA-PF的全局搜索能力,同時引入動態(tài)權重協調前期全局大范圍搜索與后期局部精確搜索;改進麻雀搜索算法的追隨者更新策略,使粒子分布更趨于合理的同時提高樣本多樣性;引入螞蟻隨機游走策略增大搜索空間,進一步幫助算法跳出局部最優(yōu)。

1 傳統粒子濾波算法

貝葉斯濾波非線性動態(tài)過程表示為:

xk=f(xk-1,uk-1)

(1)

yk=h(xk,vk)

(2)

式中:xk與yk分別為k時刻對應的狀態(tài)值與觀測值;f(·)與h(·)分別為狀態(tài)函數與觀測函數;uk與vk分別為過程噪聲與測量噪聲。

為了方便表示,用Xk=x0∶k={x0,x1,…,xk}、Yk=y0∶k={y0,y1,…,yk}分別表示一段時間內的累計狀態(tài)與觀測。貝葉斯濾波的預測階段由k-1時刻的后驗概率密度p(xk-1|||Yk-1)得到當前時刻狀態(tài)量的預測概率密度p(xk|||Yk-1),預測方程為

(3)

貝葉斯濾波的更新階段由k時刻的觀測量p(yk|||xk)修正p(xk|||Yk-1)得到k時刻的后驗概率密度p(xk|||Yk):

(4)

貝葉斯濾波在在遇到復雜的概率分布形式時很難求出積分的解,常用基于蒙特卡洛原理的粒子濾波,將積分運算轉變?yōu)闃颖炯訖嗪瓦\算,使用易于采樣的重要性分布函數q(xk|||Yk)的樣本加權和來逼近后驗概率密度p(xk|||Yk):

(5)

最終輸出當前時刻狀態(tài)值:

(6)

然后進行重采樣過程后開始下一時刻的濾波過程。

2 麻雀搜索算法分析

為了更好地將麻雀搜索算法應用于粒子濾波的狀態(tài)估計過程,SSA-PF將每個粒子的狀態(tài)值看作麻雀種群的個體位置,位置越好的麻雀個體相當于權值越高的粒子,其中,位置越好的麻雀個體與真實值越接近,為了評價每個麻雀個體位置的好壞程度,本文結合最新觀測信息為SSA-PF設計了新的適應度函數:

f=|||znew-zpred|||

(7)

式中:znew為最新的測量值;zpred為預測值。

f值越小代表該麻雀的適應度越高,其表示的粒子與實際位置的觀測值越接近。

從式(6)可以看出粒子濾波的核心思路之一是利用粒子集合的均值作為濾波器的估計值,因此合理的分布需要粒子很好的“覆蓋”真實值,為了得到較好的濾波效果,麻雀群體需要找到最優(yōu)點的同時合理分布在最優(yōu)點附近,本節(jié)結合該思路對麻雀搜索算法進行分析,指出麻雀搜索算法直接指導粒子更新時存在的問題,以便后續(xù)進行相應的改進。

麻雀搜索算法中[19],假設種群有n只麻雀,則種群位置X可以表示為

(8)

式中:xij為第i只麻雀所處第j維中的位置;n為麻雀種群的數量;d為向量空間的維度。

個體各自對應的適應度函數F為

F=[f(x1),f(x2),f(x3),…,f(xn)]T

麻雀搜索算法中的發(fā)現者作為位置最好的一部分群體,主要為種群提供尋找食物的方向和大體位置。發(fā)現者的位置更新式(6)為

(9)

(a)Niter_max=1 000時y值的分布

除去位置最好的發(fā)現者,其他麻雀群體稱作跟隨者,他們主要跟隨發(fā)現者來獲取食物,發(fā)現者與跟隨者的身份是有可能發(fā)生轉換的,位置更新后適應度較高的跟隨者會變成發(fā)現者,但二者的比例是確定的。跟隨者的位置更新公式為

(10)

警戒者占種群比例的10%～20%,它們是隨機選擇的,既可以是發(fā)現者也可以是跟隨者,主要負責對種群的預警。三者通過位置及關系的不斷更替完成覓食過程。警戒者位置更新方式為

(11)

當fi≠fg時,表示該麻雀處于種群的外圍,易遭到攻擊,它將飛向最優(yōu)位置附近;當fi=fg時,意味著該麻雀處于種群中心,它將向其他麻雀靠攏來躲避捕食者。

3 麻雀搜索算法改進的粒子濾波

根據2小節(jié)的分析,本節(jié)對麻雀搜索算法進行相應的改進,保證快速準確找到全局最優(yōu)點的同時大部分群體也合理分布在最優(yōu)點附近,從而進一步提高麻雀搜索算法與粒子濾波的適配性,增強SSA-PF的綜合濾波性能。

3.1 Logistic-tent map初始化種群

混沌映射被用于生成混沌序列,在優(yōu)化領域,可根據混沌序列的遍歷性與隨機性代替?zhèn)坞S機數生成器初始化種群以提高種群多樣性。文獻[22]提出的Logistic-tent復合混沌系統融合了Logistic復雜的混沌動力學特性和Tent混沌系統較快的迭代速度等特點,將該混沌系統引入SSA-PF初始化種群有助于為算法全局搜索過程的種群多樣性奠定基礎,提高后續(xù)迭代尋優(yōu)所得解的質量。Logistic-tent數學表達式為

(12)

圖2分別為二維空間下隨機初始化種群分布與Logistic-tent map映射后的種群分布,從圖2可以看出經過Logistic-tent map映射后的初始化種群分布更分散,重合個體更少。

(a)隨機初始化分布

3.2 發(fā)現者位置更新公式改進

發(fā)現者在群體中起引領作用,其位置更新結果直接影響算法的尋優(yōu)性能,而發(fā)現者搜索范圍的廣度直接決定算法能否找到更好的位置。本文針對上述分析對SSA-PF發(fā)現者更新公式做了2方面的改進:一方面,針對麻雀搜索算法直接用于優(yōu)化粒子濾波狀態(tài)估計時,因Niter_max較少導致發(fā)現者收斂速度過快,缺少大范圍搜索進而影響狀態(tài)估計精度的問題,引入比例系數保證R2

(13)

式中:Y為比例系數;Niter_max為SSA-PF的最大迭代次數;M為1行d列矩陣,M的每個元素值服從期望為1、方差為ω2的正態(tài)分布,記為M～N(1,ω2);ω的值依賴當前迭代次數與最大迭代次數滿足ω=ωmax-[Niter(ωmax-ωmin)/Niter_max];Niter為當前迭代次數;ωmax、ωmin為權重的最大值、最小值。

通過調節(jié)Y可以控制SSA-PF的發(fā)現者收斂速度,避免當Niter_max較小時發(fā)現者收斂速度過快。使用ωmax、ωmin保證發(fā)現者進行適度的空間探索。采用自適應權重來動態(tài)調整高斯模型的標準差,迭代前期降低發(fā)現者個體對于自身位置的依賴性,使發(fā)現者前期進行更廣泛的搜索,減少發(fā)現者搜索時的盲點區(qū)域,后期隨著麻雀種群逐漸向目標值靠近,減小權重增強發(fā)現者的局部搜索能力,同時,相比于原來發(fā)現者更新時每個維度移動相同的距離,改進后的發(fā)現者更新公式使麻雀群分布更合理,種群多樣性更強。

3.3 跟隨者位置更新公式改進

(14)

3.4 螞蟻隨機游走策略

發(fā)現者、跟隨者、警戒者公式中都存在向零點或最優(yōu)位置收斂的行為,雖然存在相應的跳出局部最優(yōu)的措施,但是算法依然存在陷入局部最優(yōu)的風險,因此本文引入蟻獅優(yōu)化算法[23]中的螞蟻隨機游走策略對每次更新后的麻雀種群進行隨機游走,進一步擴大全局搜索范圍,降低算法陷入局部最優(yōu)的概率。隨機游走的過程在數學上可以表示為

X(t)={0,cussum[2r(t1)-1],…,cussum(2r(tn)-1}

(15)

式中:X(t)為螞蟻隨機游走的步數集;cussum為累加公式;t為隨機游走的步數;r(t)為取1或0的隨機函數。

由于可行域存在邊界,不能直接用式(15)更新螞蟻的位置。為確保螞蟻在可行域范圍內隨機游走,需根據式(16)對其進行歸一化:

(16)

3.5 算法實現步驟

(1)初始化麻雀搜索算法相關參數。

(2)使用式(12)Logistic-tent map初始化種群分布。

(5)開始循環(huán)迭代,利用式(11)、式(13)、式(14)引導麻雀群不斷進行位置更新,對更新后的麻雀群引入隨機游走策略,若游走后的適應度更高,則代替原有的麻雀位置。

(6)判斷是否滿足迭代次數閾值,不滿足則返回步驟(4)。

(8)權值歸一化處理并進行狀態(tài)輸出:

(17)

4 仿真實驗與分析

仿真硬件環(huán)境為Intel(R) Core(TM) i7-11700、8 GB內存臺式計算機,軟件環(huán)境為MATLAB R2019a。假設k=1時刻小車處于100 m×100 m場地中的(60 m,15 m)位置,通過預測小車在二維空間中的弧線運動驗證所提算法的濾波性能。使用的測量模型的狀態(tài)方程以及觀測方程為:

x(k)=x(k-1)+l[-cos(k-1)θ,sin(k-1)θ]

(18)

z(k)=x(k)+v(k)

(19)

式中:x(k)為k時刻小車在二維空間中的真實坐標位置;k∈[1,T],時間步長(小車移動總步數)T=20;l為小車每次移動的距離(步長);旋轉的角度θ=π/T(rad);z(k)為k時刻的觀測值;v(k)為一個噪聲強度為10lgR(dBw)的高斯白噪聲矩陣。

為有效驗證所提算法的綜合性能,實驗使用標準粒子濾波(PF)、灰狼算法優(yōu)化粒子濾波(GWO-PF)、粒子群優(yōu)化粒子濾波(PSO-PF)與所提算法做仿真對比。

4.1 算法濾波精度測試

使用均方根誤差評價實驗算法的濾波精度,均方根誤差公式為

(20)

(a)濾波狀態(tài)估計

(a)濾波狀態(tài)估計

(a)濾波狀態(tài)估計

從圖3～圖5可以看出,同等粒子數下SSA-PF的預測軌跡與實際軌跡的重合度最高且均方根誤差最小,這是因為除了麻雀搜索算法本身較強的尋優(yōu)機制,本文結合粒子濾波的求解過程對麻雀搜索算法更新策略進行了改進,在提高全局搜索能力的同時使用自適應權重平衡了前期全局搜索與后期局部搜索,保證粒子更新后更接近真實值,且合理分布在真實值周圍,最后引入螞蟻隨機游走策略控制粒子游走進一步提高濾波精度。另一方面,不同粒子數下SSA-PF都有著較低的均方根誤差,且隨著時間步長變化沒有較大起伏,雖然某些時候誤差稍高于其他對比算法,但總體誤差最低,體現出所提算法較好的穩(wěn)定性。

將每個算法的T個RMSE值求平均值得到表1所示的平均均方根誤差對比(T-RMSE),更為直觀精確地顯示不同算法濾波精度。

表1 平均均方根誤差對比

從表1可以看出,隨著粒子數的增加,各算法的濾波精度都有所提高,同等粒子數量下SSA-PF平均均方根誤差的平均值小于其他對比算法,且不需要較大的樣本數量時就能擁有較好的預測效果,綜合上述實驗證明了所提算法擁有較高的濾波精度和濾波穩(wěn)定性。

4.2 粒子多樣性測試

為了測試相關算法的粒子多樣性,令n=100,增加時間步長,T=50,降低步長l=1.5 m,觀察k=9,k=25,k=46時不同算法的粒子分布情況,結果如圖6所示。

(a)k=9時算法粒子狀態(tài)分布

從圖6可以看出3種時刻下,PF與GWO-PF粒子分布比較集中,本文提出的SSA-PF與PSO-PF的粒子大部分靠近在真實值附近,在其他區(qū)域也有一定的分布。這是由于PF的重采樣過程會逐漸去除低權值粒子,讓高權值粒子不斷復制使粒子逐漸集中在少數幾個狀態(tài)值上,因此與圖3～圖5的(a)圖對應,粒子濾波預測軌跡需要隨著小車的移動才會逐漸趨于穩(wěn)定,但這也導致粒子過度集中缺乏多樣性。本文提出的SSA-PF沒有使用傳統的重采樣過程,未涉及粒子的直接舍棄,有效避免了粒子貧化現象,同時使用改進后的發(fā)現者與跟隨者更新公式和麻雀搜索算法本身的警戒者機制使粒子始終有一個較好的分布,符合所述粒子濾波核心思想,即使在運行后期也能夠保持較好的樣本多樣性。

5 結束語

為了解決粒子貧化現象本文首次將麻雀搜索算法與粒子濾波結合提出了一種基于改進麻雀搜索算法的新型粒子濾波算法(SSA-PF),采用改進后的麻雀搜索算法優(yōu)化粒子濾波。麻雀搜索算法收斂速度快、穩(wěn)定性高、結構簡單但直接應用于粒子濾波求解時存在全局搜索范圍不足導致的局部最優(yōu)和中后期種群分布不符合粒子濾波求解思想等缺點。本文首先使用Logistic-tent混沌映射提高種群多樣性;為SSA-PF發(fā)現者更新公式加入比例系數穩(wěn)定收斂速度,同時提出了新的發(fā)現者策略更新粒子,提高全局搜索能力的同時保證了前期全局搜索與后期局部搜索;優(yōu)化跟隨者更新策略來進一步提高種群分布的合理性;最后使用螞蟻隨機游走策略進一步幫助算法跳出局部最優(yōu)。群智能優(yōu)化理論算法優(yōu)化粒子濾波能有效解決粒子貧化現象,本文所提算法不需要大量粒子即可達到較好的預測精度。仿真實驗結果證明:本文所提的SSA-PF相對其他對比算法濾波精度最高,粒子分布合理,狀態(tài)估計所需樣本數量較少,總體來說濾波性能較強。