基于社會(huì)蜘蛛群優(yōu)化的粒子濾波算法研究

谷旭平，唐大全

(海軍航空大學(xué)航空作戰(zhàn)勤務(wù)學(xué)院，山東 煙臺(tái) 264001)

0 引言

解決非線性問(wèn)題，一般采用擴(kuò)展卡爾曼濾波的方法，并且其隨機(jī)量須符合高斯分布。但粒子濾波(particle filter,PF)的出現(xiàn)打破了解決非線性問(wèn)題的桎梏[1]。粒子濾波在解決非線性、非高斯問(wèn)題上的突破，使其應(yīng)用范圍異常廣泛。粒子濾波在視覺(jué)跟蹤領(lǐng)域，目標(biāo)定位、導(dǎo)航、跟蹤領(lǐng)域以及通信與信號(hào)處理領(lǐng)域都發(fā)揮著重要作用[2-5]。

粒子退化是標(biāo)準(zhǔn)粒子濾波器的主要缺陷[6-7]，解決方法之一就是重采樣。但重采樣會(huì)降低粒子多樣性，難以保證估計(jì)精度。文獻(xiàn)[8]在重采樣之后加入馬爾科夫鏈蒙特卡洛(Markov chain Monte Carlo,MCMC)移動(dòng)處理，減少了粒子相關(guān)性，使粒子分布與狀態(tài)概率密度函數(shù)一致，保證了粒子分布的合理性；但算法的收斂性很難保證，且計(jì)算量大。文獻(xiàn)[9]利用正規(guī)則方法計(jì)算粒子的后驗(yàn)概率密度，有效地緩解了重采樣帶來(lái)的樣本枯竭與粒子退化問(wèn)題，但高維的正規(guī)則難以實(shí)現(xiàn)。文獻(xiàn)[10]在重采樣前，依據(jù)似然值的大小對(duì)原粒子權(quán)值進(jìn)行修正，保證重采樣后粒子向高似然區(qū)域移動(dòng)。該算法在重采樣后，更接近狀態(tài)真值，但每個(gè)粒子需要計(jì)算兩次權(quán)值以及似然值。這就伴隨著大計(jì)算量的問(wèn)題，難以保證算法的實(shí)時(shí)性。文獻(xiàn)[11]～文獻(xiàn)[17]依據(jù)自然界生物種群的尋優(yōu)特性，對(duì)粒子濾波的重采樣過(guò)程進(jìn)行改進(jìn)，在一定程度上改善了算法的濾波精度，提高了粒子多樣性。

本文將社會(huì)蜘蛛群的尋優(yōu)特性[18-19]引入粒子濾波的重采樣過(guò)程中。一方面，依據(jù)有效粒子數(shù)判斷是否進(jìn)行重采樣；另一方面，在復(fù)制大權(quán)重粒子時(shí)，在其期望值附近添加隨機(jī)粒子以保證粒子多樣性。同時(shí)，利用群體突變、動(dòng)態(tài)自適應(yīng)權(quán)重調(diào)節(jié)，以及將遺傳算法中的交叉概率[20]引入蜘蛛群繁殖的過(guò)程中，保證了算法的全局以及局部收斂能力。

1 粒子濾波原理

粒子濾波的基本思想是：根據(jù)系統(tǒng)狀態(tài)的經(jīng)驗(yàn)分布在狀態(tài)空間產(chǎn)生的粒子集，不斷調(diào)整粒子的權(quán)重和位置，通過(guò)調(diào)整的粒子信息修正最初的經(jīng)驗(yàn)分布。

狀態(tài)空間的狀態(tài)轉(zhuǎn)移模型以及量測(cè)模型為：

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

(1)

zk=h(xk,nk)

(2)

式中：xk∈Rnx為k時(shí)刻的狀態(tài)向量；zk∈Rnz為k時(shí)刻的量測(cè)值；vk∈Rnv和nk∈Rnn為過(guò)程和量測(cè)噪聲，f:Rnx→Rnx,h:Rnz→Rnz為有界非線性映射。

(3)

式中：權(quán)值由重采樣選擇。

(4)

重要性密度函數(shù)分解為：

q(x0:k|z1:k)=q(xk|x0:k-1,z1:k)q(x0:k-1|z1:k-1)

(5)

后驗(yàn)概率密度函數(shù)可表示為：

(6)

將式(4)、式(5)代入式(6)，即可得到重要性權(quán)重的計(jì)算公式：

(7)

(8)

選擇易于實(shí)現(xiàn)的先驗(yàn)概率密度作為重要性密度函數(shù)。將式(8)代入式(7)，則重要性權(quán)重簡(jiǎn)化為：

(9)

權(quán)重歸一化，即：

(10)

后驗(yàn)概率密度p(xk|z1:k)為：

(11)

則k時(shí)刻狀態(tài)的估計(jì)值為：

(12)

2 社會(huì)蜘蛛群優(yōu)化算法

蜘蛛群優(yōu)化(social spider optimization,SSO)算法將優(yōu)化空間抽象為一張信息交流網(wǎng)，蜘蛛通過(guò)身體接觸以及網(wǎng)的振動(dòng)來(lái)傳遞信息。

2.1 蜘蛛群分工

在社會(huì)蜘蛛群體中，雌雄蜘蛛比重不同，一般雌蜘蛛占整個(gè)種群數(shù)量N的65%～90%。雌、雄蜘蛛種群數(shù)量Nf、Nm分別為：

Nf=floor[(0.9-r×0.25)×N]

(13)

Nm=N-Nf

(14)

式中:r為[0,1]之間的隨機(jī)數(shù)；floor()為向下取整函數(shù)。

雌、雄蜘蛛的初始位置fi,j、mg,j分別為：

(15)

(16)

蜘蛛個(gè)體權(quán)重為：

(17)

式中：J(si)為第i只蜘蛛的適應(yīng)度。

bs、ws分別為適應(yīng)度的極大值與極小值：

(18)

(19)

2.2 蜘蛛的移動(dòng)

2.2.1 移動(dòng)的誘因

社會(huì)蜘蛛在信息交流網(wǎng)中通過(guò)彼此之間的振動(dòng)，感知對(duì)方位置。蜘蛛個(gè)體的權(quán)重以及彼此的距離是影響振動(dòng)的關(guān)鍵因素。振動(dòng)表達(dá)式為：

(20)

式中：di,j=‖si-sj‖為蜘蛛個(gè)體i、j的歐式距離。

蜘蛛個(gè)體接收到的振動(dòng)來(lái)源有3種：

①權(quán)重較大，距離較近的雌蜘蛛個(gè)體為：

(21)

②權(quán)重最大的蜘蛛個(gè)體為：

(22)

③權(quán)重較大，距離最近的雄蜘蛛個(gè)體為：

(23)

2.2.2 雌雄蜘蛛位置移動(dòng)

蜘蛛個(gè)體位置的移動(dòng)主要體現(xiàn)在對(duì)同性和異性的排斥上，其位置移動(dòng)算式為：

(24)

(25)

2.3 蜘蛛種群的更新

在交配半徑范圍內(nèi)的雌雄蜘蛛個(gè)體，通過(guò)交配產(chǎn)生新蜘蛛個(gè)體。新個(gè)體的權(quán)重受到上一代個(gè)體權(quán)重影響。新個(gè)體與種群質(zhì)量較輕的個(gè)體進(jìn)行比較，淘汰其中權(quán)重較輕的個(gè)體來(lái)保持種群數(shù)量不變。交配半徑R以及蜘蛛影響概率pi為：

(26)

(27)

3 社會(huì)蜘蛛群優(yōu)化的粒子濾波算法

蜘蛛群的尋優(yōu)過(guò)程就是粒子濾波的重采樣過(guò)程，通過(guò)對(duì)SSO進(jìn)行改進(jìn)，來(lái)保持粒子多樣性以及算法的收斂能力。

3.1 粒子多樣性的改進(jìn)

重采樣不僅使粒子多樣性下降，也增加了計(jì)算量，影響粒子濾波的實(shí)時(shí)性能。采用有效粒子數(shù)Neff來(lái)衡量粒子多樣性。有效粒子數(shù)的計(jì)算式為：

(28)

由于噪聲干擾和其他原因，全局最優(yōu)粒子權(quán)重可能不是最大的。重采樣可能導(dǎo)致丟棄全局最優(yōu)粒子，不能收斂到真實(shí)狀態(tài)。因此在復(fù)制大權(quán)重粒子時(shí)，根據(jù)復(fù)制數(shù)量在期望值附近添加少量隨機(jī)粒子。在粒子不發(fā)散的情況下，增加大權(quán)重粒子周圍的粒子以保持多樣性，以避免出現(xiàn)次優(yōu)結(jié)果。

重采樣時(shí)，記錄刪除的小權(quán)重粒子Ndel的數(shù)量，從大權(quán)重粒子中選擇Nx個(gè)粒子，并使用式(29)，獲得可復(fù)制粒子數(shù)M。將大權(quán)重粒子的權(quán)重作為平均值，并使其成為標(biāo)準(zhǔn)的高斯分布。從高斯分布中隨機(jī)選擇M個(gè)粒子作為重采樣結(jié)果。

(29)

3.2 收斂性能的改進(jìn)

3.2.1 群體突變

在迭代前期，為避免算法陷入局部最優(yōu)解，在保證最優(yōu)粒子的前提下，對(duì)其余粒子進(jìn)行群體突變。引入動(dòng)態(tài)的次數(shù)因子temp。因?yàn)槊總€(gè)計(jì)算周期中，粒子收斂的迭代次數(shù)之和是不一樣的，當(dāng)?shù)螖?shù)累計(jì)到預(yù)先規(guī)定的數(shù)值temp時(shí)，就初始化粒子。這可使粒子持續(xù)地在較大的空間內(nèi)尋優(yōu)，避免算法陷入局部最優(yōu)。

(30)

3.2.2 動(dòng)態(tài)自適應(yīng)權(quán)重調(diào)節(jié)

①尋優(yōu)速度因子。

在粒子尋優(yōu)的過(guò)程中，全局最優(yōu)值取決于個(gè)體最優(yōu)值的變化，也反映了粒子運(yùn)動(dòng)效果。在優(yōu)化過(guò)程中，當(dāng)前迭代的全局最優(yōu)值大于或等于上一輪迭代的全局最優(yōu)值。

定義尋優(yōu)速度因子Mspeed：

(31)

式中:Nbest為當(dāng)前迭代最優(yōu)值;pbest為上一輪迭代最優(yōu)值。

Mspeed值越小，表示尋優(yōu)速度越快。經(jīng)過(guò)一定迭代次數(shù)，該值會(huì)保持在1，表示算法找到最優(yōu)解。

②尋優(yōu)程度因子。

定義尋優(yōu)程度因子Gather：

(32)

XP=exp{min[(Nbest×N-Nsum),(Nsum-

Nbest×N)]}

(33)

式中：Nsum為當(dāng)前迭代次數(shù)粒子的適應(yīng)度之和;Gather為粒子的尋優(yōu)程度，0≤Gather≤1。

Gather在一定程度上反映了粒子的多樣性。Gather值越大，粒子的尋優(yōu)程度越好，粒子多樣性越差。經(jīng)過(guò)一定的迭代次數(shù)后，Gather值會(huì)保持在1。如果此時(shí)算法陷入局部最優(yōu)，那么不容易跳出局部最優(yōu)。

③權(quán)重調(diào)節(jié)。

根據(jù)重采樣的特點(diǎn)，蜘蛛群優(yōu)化算法中的粒子權(quán)重w應(yīng)依據(jù)粒子的尋優(yōu)速度以及程度的變化而變化。粒子的尋優(yōu)速度越快，粒子越可保持大范圍尋優(yōu)，其全局尋優(yōu)能力越強(qiáng)。當(dāng)粒子尋優(yōu)速度變慢時(shí)，通過(guò)調(diào)整w的大小，可保證粒子在小范圍空間內(nèi)搜索，從而提高其局部收斂能力。

粒子越分散，算法就不易陷入局部最優(yōu)。但是隨粒子的尋優(yōu)程度的不斷提高，算法易陷入局部最優(yōu)。此時(shí)可增大粒子的搜索范圍，從而提高粒子的全局收斂能力。

綜上，粒子的權(quán)重w為：

w=1-wa×Mspeed+ws×Gather

(34)

式中：wm和wg為常數(shù)，wm∈[0.4，0.6]，wg∈[0.05，0.20]。

3.2.3 新粒子生成速度

為了進(jìn)一步保證算法的收斂能力，將遺傳算法[21]中改進(jìn)的交叉操作引入SSO。交叉操作的作用主要是限制子蜘蛛的誕生速度。在算法迭代初期，為了提高SSO全局尋優(yōu)效率，一般交叉概率選取較大值；隨著迭代次數(shù)的逐漸增加，為了保證SSO局部尋優(yōu)能力，選取較小的交叉概率。交叉操作的計(jì)算式為：

(35)

式中：PS為自適應(yīng)交叉概率；PSO為自適應(yīng)參數(shù)；γ為迭代次數(shù);kmax為設(shè)置度量。

本文取PSO=0.85、kmax=20。

3.3 改進(jìn)的粒子濾波算法步驟

改進(jìn)的社會(huì)蜘蛛群粒子濾波算法步驟如下。

(1)初始化。在k=0時(shí)刻，依據(jù)先驗(yàn)概率分布p(x0)進(jìn)行采樣，選取N個(gè)初始樣本，并根據(jù)式(13)、式(14)初始化雌、雄蜘蛛粒子數(shù)目Nf、Nm。然后，根據(jù)式(15)、式(16)初始化雌、雄蜘蛛的位置fi,j、mg,j，設(shè)定temp。

(3)采用改進(jìn)的SSO算法來(lái)優(yōu)化粒子的重采樣過(guò)程。

①依據(jù)式(28)判斷是否進(jìn)行重采樣。

②根據(jù)式(17)、式(20)～式(23)計(jì)算每個(gè)蜘蛛的振動(dòng)強(qiáng)度。

③若當(dāng)前迭代次數(shù)大于temp，在保持最優(yōu)粒子位置不變的情況下，依據(jù)式(30)進(jìn)行小權(quán)重粒子位置移動(dòng)；否則，依據(jù)式(24)、式(25)移動(dòng)雌、雄蜘蛛的位置。

④根據(jù)式(26)、式(27)，雌、雄蜘蛛在給定交配半徑內(nèi)產(chǎn)生新的粒子，并依據(jù)式(35)維持不同時(shí)期新粒子產(chǎn)生的速率，保證不同時(shí)期的收斂速度。

⑤依據(jù)式(31)～式(34)，動(dòng)態(tài)調(diào)整粒子權(quán)重。

(4)計(jì)算迭代截止時(shí)粒子的權(quán)重，并用式(10)進(jìn)行歸一化處理。

(5)根據(jù)式(12)，輸出狀態(tài)估計(jì)值。

3.4 改進(jìn)粒子濾波算法收斂性驗(yàn)證

(36)

式中：t為蜘蛛粒子個(gè)體到達(dá)局部最優(yōu)位置的時(shí)間；若E(t)存在且有界，則該算法是全局收斂的。

條件1說(shuō)明了蜘蛛粒子個(gè)體與最優(yōu)位置之間的距離在一個(gè)多項(xiàng)式的范圍內(nèi)。條件2說(shuō)明蜘蛛粒子個(gè)體不斷趨于最優(yōu)位置時(shí)，蜘蛛粒子群的移動(dòng)在一個(gè)多項(xiàng)式倒數(shù)的范圍內(nèi)。

當(dāng)滿足上述兩個(gè)條件時(shí)，E(t)存在且有界，蜘蛛群算法的時(shí)間估計(jì)為：

(37)

本文對(duì)SSO進(jìn)行改進(jìn)，但在每一次迭代后，蜘蛛粒子群體必將進(jìn)入最優(yōu)狀態(tài)，因此優(yōu)化后算法依然滿足上述條件；采用遺傳算法的交叉概率，動(dòng)態(tài)自適應(yīng)調(diào)整權(quán)重，群體突變，蜘蛛粒子群整體的移動(dòng)并沒(méi)有改變，因此依然滿足上述條件。綜上所述，改進(jìn)的SSO依然保持著全局收斂能力，且該算法是收斂的。

4 仿真分析

本試驗(yàn)選用一維系統(tǒng)來(lái)仿真基本粒子濾波，鴿群優(yōu)化粒子濾波(pigeon-inspired optimization-PF,PIO-PF)，改進(jìn)的磷蝦優(yōu)化粒子濾波(improved krill herd optimization-PF,IKH-PF)，布谷鳥(niǎo)群優(yōu)化粒子濾波(cuckoo search optimization-PF,CS-PF)，改進(jìn)的社會(huì)蜘蛛優(yōu)化粒子濾波(improved social-spider optimization-PF,ISSO-PF)在狀態(tài)估計(jì)精度、實(shí)時(shí)性等方面的綜合指標(biāo)。

選用的一維非線性系統(tǒng)方程與觀測(cè)方程為:

x(k)=0.9+cos(0.04πk)+0.4x(k-1)+w(k)

(38)

(39)

式中：w為服從伽馬分布Λ～Γ(3,2)的過(guò)程噪聲；v為符合均值為0、方差為R的高斯分布的噪聲。

系統(tǒng)的初始狀態(tài)為x(0)=0.1，仿真步長(zhǎng)T=100。

4.1 算法精度測(cè)試

(1)在粒子數(shù)不同的情況下，濾波狀態(tài)估計(jì)和估計(jì)誤差絕對(duì)值分別如圖1、圖2所示。

①粒子數(shù)N=50、方差R=1時(shí)，仿真結(jié)果與估計(jì)誤差絕對(duì)值如圖1、圖2(a)所示。

圖1 濾波狀態(tài)估計(jì)(N=50,R=1)

②粒子數(shù)N=100、方差R=1時(shí)，估計(jì)誤差絕對(duì)值如圖2(b)所示。

③粒子數(shù)N=150、方差R=1時(shí)，估計(jì)誤差絕對(duì)值如圖2(c)所示。

④粒子數(shù)N=200、方差R=1時(shí)，估計(jì)誤差絕對(duì)值如圖2(d)所示。

圖2 估計(jì)誤差絕對(duì)值

(2)在R=5的條件下，再進(jìn)行一組試驗(yàn)，整體誤差對(duì)比如表1所示。

表1 整體誤差對(duì)比

4.2 粒子空間分布

R=1時(shí)，選取不同的粒子總數(shù)，粒子的狀態(tài)空間分布如圖3所示。

圖3 粒子的狀態(tài)空間分布

4.3 運(yùn)行時(shí)間對(duì)比

針對(duì)上述不同的仿真情況，對(duì)各算法的運(yùn)行時(shí)間進(jìn)行統(tǒng)計(jì)。

運(yùn)行時(shí)間對(duì)比如表2所示。

表2 運(yùn)行時(shí)間對(duì)比

4.4 試驗(yàn)結(jié)果分析

從圖1可以看出，5種算法都很好地跟蹤了系統(tǒng)的真實(shí)狀態(tài)。從圖2可以看出，對(duì)比5種濾波算法的誤差絕對(duì)值，ISSO-PF算法的誤差一直處于較低的水平，其他濾波算法均存在不同程度的誤差起伏。從表1可以看出，整體的改進(jìn)濾波算法要比普通的粒子濾波算法的誤差更小，精度更高。算法誤差從低到高依次為ISSO-PF、IKH-PF、PIO-PF、CS-PF、PF。

從粒子的狀態(tài)空間分布可以直觀地看出粒子的狀態(tài)估計(jì)情況，從圖3可以看出，ISSO-PF可以很好地跟蹤真實(shí)值，而且隨著粒子數(shù)的增加，粒子的分布越廣，在真實(shí)值附近分布的粒子數(shù)越多。所以ISSO-PF算法在提高濾波精度、改善粒子貧化、增加粒子多樣性方面，均有很好的效果。

算法的運(yùn)行時(shí)間能夠很好地體現(xiàn)算法的開(kāi)銷問(wèn)題。在算法實(shí)時(shí)性要求較高的情況下，該指標(biāo)尤為重要。從表2可以看出，整體的計(jì)算時(shí)間消耗最低的是PF,然后依次是ISSO-PF、PIO-PF、CS-PF、IKH-PF。由此可知，濾波精度的提高是以運(yùn)算時(shí)間為代價(jià)的，但是ISSO-PF的實(shí)時(shí)性能較其他改進(jìn)算法，還是有較大改善的。

5 結(jié)論

為了改善粒子濾波的粒子退化、增強(qiáng)粒子多樣性，本文結(jié)合了SSO與粒子濾波算法的特點(diǎn)，采用改進(jìn)的SSO優(yōu)化粒子濾波的重采樣過(guò)程。為了改善粒子退化：一方面，依據(jù)有效粒子數(shù)，選擇是否進(jìn)行重采樣；另一方面，在重采樣復(fù)制大權(quán)重粒子的過(guò)程中，在大權(quán)重粒子附近添加隨機(jī)粒子，保證粒子的多樣性。同時(shí)，利用群體突變、動(dòng)態(tài)自適應(yīng)權(quán)重調(diào)節(jié)，以及將遺傳算法中的交叉概率引入蜘蛛群繁殖的過(guò)程中，保證了算法的全局以及局部收斂能力。試驗(yàn)結(jié)果表明，ISSO-PF算法提高了濾波精度，改善了粒子退化，增加了粒子多樣性。