基于自適應(yīng)遺傳算法的粒子濾波器

杜正聰, 鄧 尋

(攀枝花學院，四川 攀枝花 617000)

基于自適應(yīng)遺傳算法的粒子濾波器

杜正聰, 鄧 尋

(攀枝花學院，四川 攀枝花 617000)

針對重采樣導致的權(quán)值退化問題，應(yīng)用遺傳算法的進化思想來優(yōu)化重采樣算法，將粒子權(quán)值作為適應(yīng)度值，合理設(shè)定閾值，利用最佳個體保存法保存高適應(yīng)度粒子，利用自適應(yīng)交叉、變異操作對低適應(yīng)度粒子進行進化，將高適應(yīng)度粒子與進化粒子組合成新的粒子集進行狀態(tài)估計。仿真實驗表明，該算法具有良好的實時性和估計精度，其狀態(tài)估計精度比標準粒子濾波提高近24倍，比無跡卡爾曼粒子濾波提高近4倍，耗時約為無跡卡爾曼粒子濾波的1/10。

粒子濾波；選擇；交叉；自適應(yīng)遺傳算法

非線性、非高斯系統(tǒng)的狀態(tài)估計問題已經(jīng)成為現(xiàn)代信號處理的主要任務(wù)之一，擴展卡爾曼濾波(EKF)是處理該問題的常用手段。對于強非線性系統(tǒng)，EKF的濾波精度較低，尋找精度更高的非線性濾波器至關(guān)重要。粒子濾波[1](PF)是基于Monte Carlo思想的Bayes估計算法，已在信號處理[2]、目標跟蹤[3]、模式識別以及無線通信等領(lǐng)域得到普遍應(yīng)用；但粒子濾波仍有許多問題亟待解決。粒子濾波通過數(shù)次迭代后，會出現(xiàn)權(quán)值退化現(xiàn)象，即僅有少量大權(quán)值粒子，大多數(shù)粒子的權(quán)值幾乎為零，導致算法的有效性和實時性降低。為了解決這些問題，鄒國輝等[4]改進了粒子濾波重采樣算法，通過線性組合大權(quán)值粒子與被丟棄的粒子來獲取新的粒子，降低了粒子樣本匱乏；但步長系數(shù)值的選取是一個難點。張琪等[5]通過引入克隆操作和變異操作來緩解粒子濾波的權(quán)值退化問題；但算法的計算復雜度較高。方正等[6]利用粒子群來優(yōu)化重采樣操作，可有效提升算法的全局搜索能力，增加算法的狀態(tài)估計精度；但算法易產(chǎn)生局部最優(yōu)。王龍生等[7]采用基于微分進化思想的組合重采樣技術(shù)來緩解粒子濾波的權(quán)值退化；但比例因子F和交叉概率Cr的選取是一個難點。朱志宇[8]利用遺傳算子來維持粒子的多樣性，規(guī)避了重采樣；但賭盤法的隨機性選擇將丟失粒子群中的優(yōu)秀粒子，恒定的交叉概率以及變異概率會降低粒子濾波算法的有效性。于金霞等[9]利用自適應(yīng)優(yōu)化算法改進了粒子濾波算法的建議分布及重采樣，能適當增加樣本的多樣性；但計算過程比較復雜。

針對粒子濾波的權(quán)值退化問題，本文在汪榮貴等[10]研究的基礎(chǔ)上，應(yīng)用遺傳算法的進化思想，采用選擇、交叉、變異操作來改進傳統(tǒng)的重采樣技術(shù)，提出了一種優(yōu)化的自適應(yīng)遺傳粒子濾波算法(IAG-PF)。將粒子權(quán)值作為適應(yīng)度值，合理設(shè)定閾值，通過最佳個體保存法取得若干數(shù)量的大權(quán)值粒子進入下一次循環(huán)，利用自適應(yīng)交叉、變異操作對低適應(yīng)度粒子進行進化，高適應(yīng)度粒子與進化粒子組合成的新粒子集較之于未做進化處理的粒子集會更加接近于從真實后驗概率分布取樣得到的粒子集。IAG-PF算法能在基本不增加運算復雜度的前提下有效維持粒子多樣性、緩解權(quán)值退化、提高狀態(tài)估計精度。

1 粒子濾波

粒子濾波的實質(zhì)是Bayes估計理論在非線性、非高斯系統(tǒng)中的一種Monte Carlo實現(xiàn)，其核心思想是用獨立抽取至狀態(tài)空間的樣本序列的均值來近似后驗概率分布[11]。即

(1)

(2)

(3)

利用Bayes準則，得到重要性權(quán)值的計算公式如(4)式

(4)

式(3)和(4)即為基本粒子濾波算法的關(guān)鍵操作。

2 遺傳粒子濾波算法

Holland教授于1975年提出的遺傳算法(GA)是一種通過模擬自然進化過程搜索最優(yōu)解的方法，將待求解問題模擬成一個生物進化的過程，通過復制、交叉、突變等操作來迭代更新，逐步淘汰適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解，經(jīng)過N代進化后就很有可能會進化出高適應(yīng)度函數(shù)值的個體。朱志宇[8]將遺傳變異思想引入基本粒子濾波器,提出了遺傳粒子濾波算法(GPF)。其基本運算如下。

a.選擇運算：將選擇算子作用于粒子集，獲取若干數(shù)量的粒子樣本并組合成新的樣本集。

(5)

(6)

c.變異運算：任意選取一個粒子，根據(jù)(7)式作變異操作

(7)

3 自適應(yīng)遺傳算法

交叉算子與遺傳算子的選擇對遺傳算法性能有很大影響?；具z傳算法中pc與pm一般取定值，對復雜系統(tǒng)的狀態(tài)估計會出現(xiàn)精度低、性能差，甚至算法發(fā)散等問題。為此，Srinivas等[12]提出自適應(yīng)遺傳算法(AGA)，通過個體適應(yīng)度值來調(diào)節(jié)交叉概率pc和變異概率pm，可增強算法的收斂速度及全局搜索能力。其實現(xiàn)方式為

(8)

(9)

其中:fmax表示最大適應(yīng)度值；favg表示平均適應(yīng)度值；f′表示2個做交叉操作的個體較大的適應(yīng)度值；f表示變異個體的適應(yīng)度值。通過設(shè)定k1、k2、k3、k4，就可以實現(xiàn)pc和pm的自適應(yīng)調(diào)整。

經(jīng)公式(8)和(9)的處理后，算法對適應(yīng)度較低的粒子采用適當高的概率進行交叉、變異，對適應(yīng)度較高的粒子運用相反的概率進行交叉、變異，一定程度上實現(xiàn)了算法的自適應(yīng)，尤其是在進化的后期有利于保持粒子的適應(yīng)度值。但對于進化的初期，特別是在高適應(yīng)度值粒子數(shù)量較多的情況下，算法容易陷入局部最優(yōu)[10]。

為克服上述不足，對公式(8)和(9)做如下改進

(10)

(11)

其中pc1和pm1為[0,1]內(nèi)的數(shù)。對比式(10)、(11)和式(8)、(9)得知，改進算法在保存高適應(yīng)度值粒子的同時可有效維持全體粒子的進化，增強算法的全局搜索能力。

4 自適應(yīng)遺傳粒子濾波器

綜上所述，通過引入自適應(yīng)遺傳算法的選擇、交叉和變異操作可有效緩解傳統(tǒng)粒子濾波重采樣導致的權(quán)值退化問題，提高算法效率和估計精度。為克服遺傳算法中賭盤式選擇操作的隨機性選擇可能導致的大適應(yīng)度值粒子丟失，本文引入文獻[13, 14]的最優(yōu)保存方案來進行選擇操作。將粒子按適應(yīng)度值從大到小排列，保存一定比例大權(quán)值粒子，不進行交叉、變異運算直接參與下一步迭代。低適應(yīng)度值粒子經(jīng)交叉、變異運算后再進入迭代環(huán)節(jié)，可在保證算法收斂性的同時提高全局最優(yōu)概率。

IAG-PF算法運算

步驟2：計算重要性權(quán)值，并歸一化。

(12)

(13)

步驟3：遺傳運算。

a.選擇：選取高適應(yīng)度值粒子按最佳個體保存方案進行運算。

c.變異：按公式(11)計算變異概率pm。為避免IAG-PF算法產(chǎn)生非目標性收斂，本文采用以下公式來進行變異操作[15]。

(14)

其中β可視情況確定，一般選擇為隨機正實數(shù)。

d.對按上述a-c步操作形成的粒子集計算權(quán)值并做歸一化處理。

步驟4：按式(15)運算并令k=k+1，直至運算結(jié)束。

(15)

5 算法性能驗證與分析

下面，采用式(16)和(17)所示動態(tài)狀態(tài)空間模型對上述算法性能進行驗證。

xt=1+sin(0.4π(t-1))+0.5xt-1+wt-1

(16)

(17)

其中觀測噪聲vt～N(0,10-5)，過程噪聲wt-1～N(3/2, 3/4)，設(shè)初始狀態(tài)x0=1，時間T=50，仿真軟件為Matlab7.0。為驗證本文所述算法的性能，分別采用PF算法、GPF算法、UPF算法和IAG-PF算法對式(16)和(17)所示狀態(tài)空間模型進行狀態(tài)估計。圖1為4種算法某次獨立仿真實驗的狀態(tài)估計結(jié)果。

圖1 PF、GPF、UPF和IAG-PF的狀態(tài)估計Fig.1 The state estimation results of PF, GPF, UPF and IAG-PF

仿真結(jié)果表明，因粒子權(quán)值退化問題未得到有效處理，PF算法的狀態(tài)估計精度無法得到保證，時有估計結(jié)果偏離真實狀態(tài)的情況；GPF算法因引入遺傳算法來進化粒子，估計精度高于PF算法；UPF算法因引入最新觀察函數(shù)值來優(yōu)化抽樣函數(shù)，能有效緩解粒子權(quán)值退化現(xiàn)象，狀態(tài)估計精度好于GPF算法；IAG-PF算法因最佳保存策略和自適應(yīng)操作的引入，在高效利用高適應(yīng)度值粒子的同時合理進化低適應(yīng)度值粒子，可有效抑制權(quán)值退化與樣本衰竭，增強算法的全局搜索能力，較之于前述3種算法有著更好的濾波性能。

為了更好地驗證PF算法、GPF算法、UPF算法及IAG-PF算法的狀態(tài)估計性能，定義均方根誤差公式如式(18)，采用多次Monte Carlo仿真實驗估計值與真實值之間的均方根誤差的均值與方差來評價算法性能。

(18)

圖2 PF、GPF、UPF和IAG-PF的均方根誤差曲線Fig.2 The RMSE curves of PF, GPF, UPF and IAG-PF

表1 50次Monte Carlo實驗的RMSE均值、方差和平均耗時Table 1 The mean value, variance of RMSE and average time from 50 Monte Carlo experiments

分析仿真結(jié)果可看出，較之于其他3種算法，IAG-PF算法的RMSE均值與方差皆為最小，其狀態(tài)估計值最逼近真實值，算法性能最好。在相同仿真實驗條件下，IAG-PF算法的運算時間與PF大體相當，但前者的RMSE均值與方差均遠小于后者；UPF算法在耗時遠大于IAG-PF算法的情況下，前者的RMSE均值與方差仍遠大于后者；將IAG-PF算法與GPF算法比較也能得到類似的結(jié)果。

6 結(jié) 論

本文在前人研究[9-10,14-15]的基礎(chǔ)上，針對粒子濾波重采樣導致的粒子權(quán)值退化問題，采用遺傳算法的進化思想來優(yōu)化重采樣算法，將粒子權(quán)值作為適應(yīng)度值，合理設(shè)定閾值，利用最佳個體保存法來保存高適應(yīng)度值粒子，通過自適應(yīng)交叉、變異操作對低適應(yīng)度粒子進行進化，將高適應(yīng)度粒子與進化粒子組合成新的粒子集進行狀態(tài)估計。仿真實驗表明，IAG-PF算法有較快的收斂速度及良好的全局搜索性能，相較于PF算法、UPF算法和GPF算法，IAG-PF算法在處理非線性、非高斯系統(tǒng)的狀態(tài)估計問題具有優(yōu)良的實時性和濾波精度。

[1] Gordon N J, Salmond D J, Smith A F M. Novel approach to nonlinear non-Gaussian Bayesian state estimation [J]. IEEE-Proceedings-Radar, Sonar and Navigation, 1993, 140(2): 107-113.

[2] Laska B N M, Bolic M, Goubran R A. Particle filter enhancement of speech spectral amplitudes[J]. IEEE Transactions on Audio, Speech, and Language Processing, 2010, 18(8): 2155-2167.

[3] 陳志敏,薄煜明,吳盤龍,等.基于自適應(yīng)粒子群優(yōu)化的新型粒子濾波在目標跟蹤中的應(yīng)用[J].控制與決策,2013,28(2):193-201. Chen Z M, Bo Y M, Wu P L,etal. Novel particle filter algorithm based on adaptive particle swarm optimization and its application to radar target tracking[J]. Control and Decision, 2013, 28(2): 193-201. (in Chinese)

[4] 鄒國輝,敬忠良,胡洪濤.基于優(yōu)化組合重采樣的粒子濾波算法[J].上海交通大學學報,2006,40(7):1135-1139. Zou G H, Jing Z L, Hu H T. A particle filter algorithm based on optimizing combination resampling[J]. Journal of Shanghai Jiaotong University, 2006, 40(7): 1135-1139. (in Chinese)

[5] 張琪,胡昌華,喬玉坤.基于權(quán)值選擇的粒子濾波算法研究[J].控制與決策,2008,23(1):117-120. Zhang Q, Hu C H, Qiao Y K. Particle filter algorithm based on weight selected[J]. Control and Decision, 2008, 23(1): 117-120. (in Chinese)

[6] 方正,佟國峰,徐心和.粒子群優(yōu)化粒子濾波方法[J].控制與決策,2007,22(3):273-278. Fang Z, Tong G F, Xu X H. Particle swarm optimized particle filter[J]. Control and Decision, 2007, 22(3): 273-278. (in Chinese)

[7] 王龍生,顧浩,余云智.基于微分進化的組合重采樣粒子濾波算法[J].光電與控制,2012,19(11):43-47. Wang L S, Gu H, Yu Y Z. A new combined particle filter based on differential evolutionary algorithm resample and residual resample[J]. Electronics Optics & Control, 2012, 19(11): 43-47. (in Chinese)

[8] 朱志宇.粒子濾波算法及其應(yīng)用[M].北京:科學出版社,2010:74-77. Zhu Z Y. Particle Filter Algorithm and Its Application[M]. Beijing: Science Press, 2010: 74-77. (in Chinese)

[9] 于金霞,湯永利,許景民.一種改進的自適應(yīng)優(yōu)化粒子濾波算法研究[J].小型微型計算機系統(tǒng),2013,34(6):1446-1450. Yu J X, Tang Y L, Xu J M. Research on an improved particle filter algorithm based on adaptive optimization mechanism[J]. Journal of Chinese Computer Systems, 2013, 34(6): 1446-1450. (in Chinese)

[10] 汪榮貴,李孟敏,吳昊,等.一種新型的基于自適應(yīng)遺傳算法的粒子濾波算法[J].中國科技大學學報,2011,41(2):134-141. Wang R G, Li M M, Wu H,etal. A new particle filter algorithm based on the adaptive genetic algorithm[J]. Journal of University of Science and Technology of China, 2011, 41(2): 134-141. (in Chinese)

[11] 杜正聰,唐斌,李可.混合退火粒子濾波器[J].物理學報,2006,55(3):999-1003. Du Z C, Tang B, Li K. The hybrid annealed particle filter[J]. Acta Physica Sinica, 2006, 55(3): 999-1003. (in Chinese)

[12] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems, Man and Cybernetics, 1994, 24(4): 66-667.

[13] 孟慶春,紀洪波,董浩.帶有對稱編碼的基因算法中的優(yōu)良個體成員選取和保存技術(shù)[J].計算機研究與發(fā)展,1997,34(增刊):28-31. Meng Q C, Ji H B, Dong H. Techniques of selecting and safeguarding the good members in genetic algorithm with symmetric code[J]. Computer Research & Development, 1997, 34(Suppl.): 28-31. (in Chinese)

[14] 王蕾,沈庭芝,招楊.一種改進的自適應(yīng)遺傳算法[J].系統(tǒng)工程與電子技術(shù),2002, 24(5):75-78. Wang L, Shen T Z, Zhao Y. An improved adaptive genetic algorithm[J]. Systems Engineering and Electronics, 2002, 24(5): 75-78. (in Chinese)

[15] 張敬海.基于遺傳算法的粒子濾波算法研究[D].天津:天津大學檔案館,2009. Zhang J H. Research on Particle Filtering Based on Genetic Algorithm[D]. Tianjin: The Archive of Tianjin University, 2009. (in Chinese)

Particlefilterbasedonadaptivegeneticalgorithm

DU Zhengcong, DENG Xun

PanzhihuaUniversity,Panzhihua617000,China

An improved adaptive genetic particle filter algorithm is proposed in order to alleviate weights degradation of particle filtering algorithm. Particle weight is regarded as fitness values, and a percentage of big weight particles are obtained with the best individual preservation method. Crossover and mutation operations are adopted for the remaining particles. Then formed a new set of particles with saved particles, crossover and mutation particles, and state estimation calculations is done. Maintaining the diversity of the particles at the same time, it avoids algorithm falling into local optimum and improves the global search ability of the algorithm. The simulation results show that, compared with the standard particle filter, the proposed algorithm can improve the accuracy of state estimation by nearly 24 times, 4 times higher than that of the Kalman particle filter, and it has high real-time performance and good estimation accuracy.

particle filtering; choice; cross; adaptive genetic algorithm

TN957.51 [

] A

10.3969/j.issn.1671-9727.2017.05.14

1671-9727(2017)05-0636-05

2015-10-14。

四川省應(yīng)用基礎(chǔ)研究項目(2011JY0115)。

杜正聰(1975-),男,博士,教授，研究方向：非線性、非高斯信號處理, E-mail:duzc@163.com。