杜正聰, 鄧 尋

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

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

杜正聰, 鄧 尋

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

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

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

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

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

1 粒子濾波

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

(1)

(2)

(3)

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

(4)

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

2 遺傳粒子濾波算法

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

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

(5)

(6)

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

(7)

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

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

(8)

(9)

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

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

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

(10)

(11)

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

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

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

IAG-PF算法運(yùn)算

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

(12)

(13)

步驟3：遺傳運(yùn)算。

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

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

(14)

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

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

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

(15)

5 算法性能驗(yàn)證與分析

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

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，時(shí)間T=50，仿真軟件為Matlab7.0。為驗(yàn)證本文所述算法的性能，分別采用PF算法、GPF算法、UPF算法和IAG-PF算法對式(16)和(17)所示狀態(tài)空間模型進(jìn)行狀態(tài)估計(jì)。圖1為4種算法某次獨(dú)立仿真實(shí)驗(yàn)的狀態(tài)估計(jì)結(jié)果。

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

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

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

(18)

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

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

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

6 結(jié) 論

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

[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)化的新型粒子濾波在目標(biāo)跟蹤中的應(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].上海交通大學(xué)學(xué)報(bào),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ìn)化的組合重采樣粒子濾波算法[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].北京:科學(xué)出版社,2010:74-77. Zhu Z Y. Particle Filter Algorithm and Its Application[M]. Beijing: Science Press, 2010: 74-77. (in Chinese)

[9] 于金霞,湯永利,許景民.一種改進(jìn)的自適應(yīng)優(yōu)化粒子濾波算法研究[J].小型微型計(jì)算機(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].中國科技大學(xué)學(xué)報(bào),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].物理學(xué)報(bào),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] 孟慶春,紀(jì)洪波,董浩.帶有對稱編碼的基因算法中的優(yōu)良個(gè)體成員選取和保存技術(shù)[J].計(jì)算機(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] 王蕾,沈庭芝,招楊.一種改進(jìn)的自適應(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].天津:天津大學(xué)檔案館,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ǔ)研究項(xiàng)目(2011JY0115)。

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