一種新型的簡(jiǎn)化群優(yōu)化粒子濾波算法

張義群，林培杰，程樹英

(福州大學(xué)物理與信息工程學(xué)院, 福州大學(xué)微納器件與太陽(yáng)能電池研究所，福建 福州 350116)

一種新型的簡(jiǎn)化群優(yōu)化粒子濾波算法

張義群，林培杰，程樹英

(福州大學(xué)物理與信息工程學(xué)院, 福州大學(xué)微納器件與太陽(yáng)能電池研究所，福建 福州 350116)

針對(duì)粒子濾波的粒子退化和貧化問(wèn)題，將新興的簡(jiǎn)化群優(yōu)化(SSO)算法引入到粒子濾波的重采樣階段.SSO算法結(jié)構(gòu)簡(jiǎn)單，在保留優(yōu)良粒子的基礎(chǔ)上，增加一項(xiàng)粒子隨機(jī)運(yùn)動(dòng)過(guò)程，以提供粒子多樣性. 實(shí)驗(yàn)結(jié)果表明，新算法不僅有效提高了對(duì)非線性系統(tǒng)狀態(tài)的估計(jì)精度，而且具有更高的運(yùn)算速度.

粒子濾波； 簡(jiǎn)化群優(yōu)化； 粒子群優(yōu)化； 重采樣； 粒子退化

0 引言

粒子濾波(particlefiltering，PF)是基于蒙特卡洛與遞推貝葉斯估計(jì)的一種統(tǒng)計(jì)濾波方法[1]，使用粒子集表征概率，然后從后驗(yàn)概率中抽取隨機(jī)狀態(tài)粒子來(lái)表示其分布情況. 當(dāng)粒子數(shù)足夠多時(shí)，這種蒙特卡洛描述就近似于真實(shí)的后驗(yàn)分布，是全局近似最優(yōu)濾波. 粒子濾波在處理非線性、非高斯系統(tǒng)的狀態(tài)估計(jì)問(wèn)題時(shí)具有優(yōu)越的性能[2-3]，但在粒子數(shù)少的情況下，會(huì)出現(xiàn)粒子退化和樣本貧化的問(wèn)題[2-4]，這是制約粒子濾波發(fā)展的關(guān)鍵. 而如果采用龐大的粒子數(shù)來(lái)提高狀態(tài)估計(jì)的精度，計(jì)算將會(huì)很復(fù)雜，相當(dāng)耗時(shí)，難以應(yīng)用于實(shí)際工程中.

為解決這一問(wèn)題，國(guó)內(nèi)外許多學(xué)者將智能優(yōu)化算法應(yīng)用于粒子濾波中粒子分布的迭代重采樣，主要分為兩種： 一種是基于遺傳算法的粒子濾波算法[5-6]，通過(guò)遺傳算法的選擇、交叉和變異操作，可有效抑制粒子匱乏現(xiàn)象； 另一種是基于粒子群優(yōu)化的粒子濾波算法[4]，通過(guò)對(duì)粒子所處的位置及其速度的更新來(lái)增加有效粒子數(shù)，可有效減輕粒子退化和匱乏的現(xiàn)象. 之后，學(xué)者們分別對(duì)GA和PSO算法作了改進(jìn)，應(yīng)用于粒子濾波的重采樣階段，以更有效地解決粒子退化和貧化問(wèn)題，提高濾波估計(jì)精度. 如，汪榮貴等[3]設(shè)計(jì)了一種可自適應(yīng)調(diào)節(jié)概率的遺傳操作來(lái)對(duì)粒子進(jìn)行移動(dòng)，得到了較好的估計(jì)精度； 陳志敏等[7]將慣性權(quán)重引入粒子群優(yōu)化算法的速度更新公式，利用更新權(quán)重和優(yōu)化粒子范圍的方法，改善了局部最優(yōu)現(xiàn)象，得到了較好的估計(jì)精度. 雖然GA本身的選擇、交叉和變異操作可提高粒子多樣性，但同時(shí)也增加了算法的復(fù)雜度，并且GA在尋優(yōu)過(guò)程中并未考慮群體的全局信息以及粒子個(gè)體的局部信息，使得收斂速度較慢. 因此，基于遺傳算法的粒子濾波方法難以得到很好的實(shí)際應(yīng)用. 而PSO具有全局尋優(yōu)和快速收斂的優(yōu)點(diǎn)，通過(guò)不斷更新粒子的速度和位置來(lái)搜索空間中的最優(yōu)解，類似于PF中粒子位置和權(quán)重的不斷更新來(lái)逼近系統(tǒng)的后驗(yàn)概率分布. 因此，基于粒子群優(yōu)化的粒子濾波算法得以廣泛研究[7-13].

盡管PSO算法在初始階段收斂速度較快，但是在尋優(yōu)中后期很容易陷入局部最優(yōu)[7]，并且整個(gè)尋優(yōu)過(guò)程都需要同時(shí)計(jì)算更新粒子的位置和速度，使得計(jì)算復(fù)雜且耗時(shí). 為此，Yeh[14]在2009年提出了一種簡(jiǎn)化的群優(yōu)化(simplifiedswarmoptimization，SSO)算法，來(lái)解決PSO算法存在的缺點(diǎn). 在此基礎(chǔ)上，Yeh和其它學(xué)者對(duì)SSO算法的研究逐漸深入，SSO已被證明在許多優(yōu)化問(wèn)題上是一種有效的智能優(yōu)化算法[15-22].

本研究將SSO用于粒子濾波的重采樣階段，提出一種新的基于簡(jiǎn)化群優(yōu)化的粒子濾波(SSO-PF)算法. 通過(guò)SSO算法對(duì)初始粒子分布進(jìn)行迭代重采樣，通過(guò)三段式搜索策略，加快粒子分布的收斂. 由于PSO的學(xué)習(xí)因子決定了粒子本身經(jīng)驗(yàn)信息和其他粒子的經(jīng)驗(yàn)信息對(duì)粒子飛行軌跡的影響，采用帶壓縮因子的PSO算法[23]可以有效控制粒子的飛行速度，有效平衡粒子的全局探測(cè)和局部開采之間的關(guān)系，減小粒子陷入局部最優(yōu)的可能性. 同時(shí)通過(guò)仿真實(shí)驗(yàn)，將SSO-PF與PF以及帶壓縮因子的粒子群優(yōu)化粒子濾波算法(將帶壓縮因子的PSO算法作為PF的重采樣技術(shù)，實(shí)驗(yàn)仿真中簡(jiǎn)稱PSO-PF)作對(duì)比，對(duì)所提算法進(jìn)行性能驗(yàn)證.

1 粒子濾波算法

預(yù)測(cè)方程為：

更新方程為：

2 基于SSO的粒子濾波算法

2.1 SSO算法

新興的智能優(yōu)化算法SSO類似于PSO[23]，在迭代過(guò)程中也需要根據(jù)粒子(個(gè)體)的適應(yīng)值來(lái)計(jì)算粒子集中，每個(gè)粒子的局部最優(yōu)解和整個(gè)粒子集的全局最優(yōu)解，加快收斂速度.SSO算法狀態(tài)更新定義為：

2.2 SSO-PF改進(jìn)算法

第一階段，提高隨機(jī)運(yùn)動(dòng)的概率(cw1)，以提高算法在初期可以最大限度地尋找最優(yōu)解； 第二階段，降低隨機(jī)運(yùn)動(dòng)的概率(cw2)，提高保留全局最優(yōu)解的選擇概率(cg2)，以提高算法保留優(yōu)良粒子的能力； 第三階段，決定算法是否既保留優(yōu)良粒子，又有效跳出局部最優(yōu)，在該階段需要設(shè)置合理的cg3、cp3和cw3，來(lái)權(quán)衡個(gè)體經(jīng)驗(yàn)與全局經(jīng)驗(yàn)對(duì)粒子位置更新的影響，以及粒子跳出局部最優(yōu)的能力，因此該階段迭代次數(shù)占了總次數(shù)的一半，以幫助粒子有足夠的時(shí)間跳出局部極值. 這三個(gè)階段的概率參數(shù)之間的關(guān)系為：

的具體實(shí)現(xiàn)步驟如下：

4) 若滿足停止條件(可使用預(yù)設(shè)精度或最大迭代次數(shù)，這里使用最大迭代次數(shù)作為停止條件)，停止迭代，跳到Step5. 否則令t=t+ 1，并判斷t屬于哪個(gè)迭代區(qū)間，以選擇對(duì)應(yīng)的概率參數(shù)，并返回Step4中2)，繼續(xù)搜索最優(yōu)值.

Step 6令k=k+ 1，返回Step 2，進(jìn)行下一時(shí)刻狀態(tài)估計(jì).

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)中所有程序均使用MatlabR2014a編寫，沒有進(jìn)行任何針對(duì)特殊硬件的優(yōu)化，測(cè)試使用的PC機(jī)主要性能指標(biāo)為IntelCorei5@2.70GHz、4G內(nèi)存，操作系統(tǒng)為Windows7.

為驗(yàn)證本算法性能，選取單變量非靜態(tài)增長(zhǎng)數(shù)據(jù)模型[24]作仿真比較. 該模型高度非線性，似然函數(shù)呈雙峰狀，已經(jīng)被廣泛應(yīng)用于粒子濾波性能評(píng)測(cè)[2-3, 7, 23]. 其狀態(tài)方程和量測(cè)方程為：

式中：wk為過(guò)程噪聲，vk為觀測(cè)噪聲，且都是零均值高斯噪聲，用來(lái)表征實(shí)際狀態(tài)轉(zhuǎn)移在噪聲干擾下的隨機(jī)性，以驗(yàn)證粒子濾波算法的估計(jì)性能. 由于傳統(tǒng)的濾波方法難以處理該非線性系統(tǒng)，本研究使用PF、PSO-PF[23](采用帶壓縮因子PSO)和SSO-PF這三種方法進(jìn)行狀態(tài)估計(jì)比較. 每個(gè)粒子的權(quán)值計(jì)算公式為：

輸出結(jié)果采用加權(quán)方式進(jìn)行狀態(tài)估計(jì)，本設(shè)計(jì)采用均方根誤差(RMSE)作為算法估計(jì)精度的評(píng)價(jià)指標(biāo)：

(12)

令PF、PSO-PF和SSO-PF的過(guò)程噪聲方差Q=10，觀測(cè)噪聲方差R=1，初始估計(jì)方差P=5，時(shí)間步長(zhǎng)k=50，目標(biāo)初始狀態(tài)x0=0. 實(shí)驗(yàn)所比較的帶壓縮因子PSO，相比標(biāo)準(zhǔn)PSO可以提高解的精度，為防止粒子過(guò)早收斂到局部最小值，帶壓縮因子PSO的參數(shù)取值與文[23]一致，即取學(xué)習(xí)因子c1=2.8，c2=1.3，則C=4.1，壓縮因子為0.729. SSO算法參數(shù)設(shè)置為： 第一階段概率參數(shù)cg1=0.25、cp1=0.4和cw1=0.5； 第二階段概率參數(shù)cg2= 0.35、cp2= 0.6和cw2= 0.7； 第三階段概率參數(shù)cg3=0.4、cp3=0.8和cw3=0.9； 下界LB=-3，上界UB=3. 實(shí)驗(yàn)中采用最大迭代次數(shù)作為當(dāng)前時(shí)刻的尋優(yōu)停止條件.

1) 令PF、PSO-PF和SSO-PF三種算法中的粒子數(shù)N=100，PSO-PF和SSO-PF的最大迭代次數(shù)G=50. 仿真結(jié)果如圖1、2所示.

圖1 在N=100和G=50條件下濾波結(jié)果比較Fig.1 Comparison of filtering results under N=100 and G=50

圖2 在N=100和G=50條件下均方根誤差比較Fig.2 Comparison of RMSE under N=100 and G=50

從圖1可以看出，SSO-PF的濾波精度明顯高于PSO-PF和PF兩種算法. 這是由于SSO算法中在狀態(tài)更新過(guò)程中加入了粒子的隨機(jī)運(yùn)動(dòng)過(guò)程，有助于粒子跳出局部極值. 又由于粒子位置更新以及粒子跳出局部最優(yōu)的能力會(huì)受到個(gè)體經(jīng)驗(yàn)與全局經(jīng)驗(yàn)的影響，而個(gè)體經(jīng)驗(yàn)與全局經(jīng)驗(yàn)又受到了粒子慣性的影響. 因此，采用有效的三段式搜索策略，可提高收斂精度. 表1給出了三種算法在N=100和G=50條件下，進(jìn)行20次獨(dú)立實(shí)驗(yàn)取均值所得的結(jié)果.

從表1可以看出標(biāo)準(zhǔn)粒子濾波算法運(yùn)算速度最快，這是由于PF只需要簡(jiǎn)單復(fù)制高權(quán)值粒子剔除低權(quán)值粒子，但是精度不高，而本算法SSO-PF精度最高.SSO-PF相比PF，精度提高了72.77%； 相較于PSO-PF，精度提高了67.51%，并且運(yùn)算時(shí)間僅是PSO-PF的62.92%. 而PSO-PF耗時(shí)較多是因?yàn)樵诿看蝺?yōu)化過(guò)程中都必須重新定位粒子的位置和速度，而SSO則不需要更新粒子速度.

2) 令PF、PSO-PF和SSO-PF三種算法中的粒子數(shù)N=100，PSO-PF和SSO-PF的最大迭代次數(shù)G=100. 該條件下，進(jìn)行20次獨(dú)立實(shí)驗(yàn)取均值所得的結(jié)果見表2, 仿真結(jié)果如圖3、4所示.

表1 在N=100和G=50條件下仿真結(jié)果數(shù)據(jù)比較

表2 在N=100和G=100條件下仿真結(jié)果數(shù)據(jù)比較

圖3 在N=100和G=100條件下，濾波結(jié)果比較Fig.3 Comparison of filtering results under N=100 and G=100

圖4 在N=100和G=100條件下，均方根誤差比較Fig.4 Comparison of RMSE under N=100 and G=100

從圖3、圖4以及表2可以看出SSO-PF算法的估計(jì)精度明顯優(yōu)于其它兩種算法. 但是總迭代次數(shù)由G=50增加到G=100時(shí)，三種算法的濾波效果并沒有得到明顯改善. 因此，迭代次數(shù)并不是越多越好.

從以上圖表可見，本研究SSO-PF算法在較少的粒子和迭代次數(shù)的情況下，也可以實(shí)現(xiàn)較好的估計(jì)效果，相較于帶壓縮因子的PSO-PF和PF具有更高的估計(jì)精度，并且相對(duì)PSO-PF縮短了計(jì)算時(shí)間.

4 結(jié)語(yǔ)

通過(guò)分析粒子濾波以及PSO算法的不足，提出一種新型簡(jiǎn)化群優(yōu)化粒子濾波(SSO-PF)算法. 通過(guò)SSO算法實(shí)現(xiàn)對(duì)粒子分布的重采樣，通過(guò)三段式尋優(yōu)搜索策略，擴(kuò)大了粒子對(duì)目標(biāo)的搜索范圍，不僅可以保留優(yōu)良粒子，還可避免粒子匱乏，改善局部最優(yōu)現(xiàn)象以提高濾波精度. 理論分析與實(shí)驗(yàn)結(jié)果驗(yàn)證了本算法的估計(jì)效果要優(yōu)于PF和帶壓縮因子的PSO-PF，在相同情況下，SSO-PF可以更容易地跳出局部極值，而更準(zhǔn)確地收斂于真實(shí)狀態(tài).

考慮到PF算法中各個(gè)粒子的獨(dú)立性，PF算法可以被分解為采樣、權(quán)值計(jì)算、重采樣三個(gè)基本步驟. 而SSO作為PF算法的重采樣技術(shù)，算法結(jié)構(gòu)簡(jiǎn)單，易于FPGA硬件實(shí)現(xiàn). 因此，在未來(lái)的工作中，我們將對(duì)SSO算法作改進(jìn)，以提高收斂速度，并將每個(gè)粒子的狀態(tài)轉(zhuǎn)移與觀測(cè)視作一條流水線，采用FPGA并行處理所有粒子，實(shí)現(xiàn)優(yōu)化算法的硬件加速，以便于實(shí)際工程應(yīng)用.

[1]POLSONNG,STROUDJR,MüLLERP.Practicalfilteringwithsequentialparameterlearning[J].JournaloftheRoyalStatisticalSociety, 2003, 70(2): 413-428.

[2]ARULAMPALAMMS,MASKELLS,GORDONN,etal.Atutorialonparticlefiltersforonlinenonlinear/non-GaussianBayesiantracking[J].IEEETransactionsonSignalProcessing, 2002, 50(2): 174-188.

[3] 汪榮貴, 李孟敏, 吳昊, 等. 一種新型的基于自適應(yīng)遺傳算法的粒子濾波算法[J]. 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào), 2011, 41(2): 134-141.

[4] 方正, 佟國(guó)峰, 徐心和. 粒子群優(yōu)化粒子濾波方法[J]. 控制與決策, 2007, 22(3): 273-277.

[5]PARKS,HWANGJ,ROUK,etal.Anewparticlefilterinspiredbybiologicalevolution:geneticfilter[J].WorldAcademyofScience,EngineeringandTechnology, 2007, 33: 83-87.

[6] 葉龍, 王京玲, 張勤. 遺傳重采樣粒子濾波器[J]. 自動(dòng)化學(xué)報(bào), 2007, 33(8): 885-887.

[7] 陳志敏, 薄煜明, 吳盤龍, 等. 收斂粒子群全區(qū)域自適應(yīng)粒子濾波算法及其應(yīng)用[J]. 南京理工大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 36(5): 861-868.

[8]YANGX.Particleswarmoptimisationparticlefilteringfordualestimation[J].SignalProcessing,IET, 2012, 6(2): 114-121.

[9]THIDAM,ENGHL,MONEKOSSODN,etal.Aparticleswarmoptimisationalgorithmwithinteractiveswarmsfortrackingmultipletargets[J].AppliedSoftComputing, 2012, 13(6): 3 106-3 117.

[10]ZHANGM,XINM,YANGJ.Adaptivemulti-featuretrackinginparticleswarmoptimizationbasedparticlefilterframework[J].JournalofSystemsEngineeringandElectronics, 2012, 23(5): 775-783.

[11] 姚海濤, 朱福喜, 陳海強(qiáng). 一種自適應(yīng)的PSO粒子濾波人臉視頻跟蹤方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2012, 37(4): 492-495.

[12] 陳志敏, 薄煜明, 吳盤龍, 等. 基于自適應(yīng)粒子群優(yōu)化的新型粒子濾波在目標(biāo)跟蹤中的應(yīng)用[J]. 控制與決策, 2013, 28(2): 193-200.

[13] 劉宇, 呂明偉, 李維佳, 等. 基于物種的自適應(yīng)多模態(tài)粒子群優(yōu)化算法[J]. 山東大學(xué)學(xué)報(bào)(理學(xué)版), 2011, 46(5): 91-96； 122.

[14]YEHWC.Atwo-stagediscreteparticleswarmoptimizationfortheproblemofmultiplemulti-levelredundancyallocationinseriessystems[J].ExpertSystemswithApplications, 2009, 36(5): 9 192-9 200.

[15]AZIZIPANAH-ABARGHOOEER,NIKNAMT,GHARIBZADEHM,etal.Robust,fastandoptimalsolutionofpracticaleconomicdispatchbyanewenhancedgradient-basedsimplifiedswarmoptimisationalgorithm[J].GenerationTransmission&DistributionIet, 2013, 7(6): 620-635.

[16]AZIZIPANAH-ABARGHOOEER.Anewhybridbacterialforagingandsimplifiedswarmoptimizationalgorithmforpracticaloptimaldynamicloaddispatch[J].InternationalJournalofElectricalPower&EnergySystems, 2013, 49(5): 414-429.

[17]QUANH,SRINIVASAND,KHOSRAVIA.Short-termloadandwindpowerforecastingusingneuralnetwork-basedpredictionintervals[J].IEEETransactionsonNeuralNetworks&LearningSystems, 2014, 25(2): 303-315.

[18]ROSSIF,VELZQUEZD,MONEDEROI,etal.ArtificialneuralnetworksandphysicalmodelingfordeterminationofbaselineconsumptionofCHPplants[J].ExpertSystemswithApplications, 2014, 41(10): 4 658-4 669.

[19]YEHWC.Novelswarmoptimizationforminingclassificationrulesonthyroidglanddata[J].InformationSciences, 2012, 197: 65-76.

[20]YEHWC.Optimizationofthedisassemblysequencingproblemonthebasisofself-adaptivesimplifiedswarmoptimization[J].IEEETransactionsonSystemsManandCybernetics(PartASystemsandHumans), 2012, 42(1): 250-261.

[21]YEHWC.Simplifiedswarmoptimizationindisassemblysequencingproblemswithlearningeffects[J].Computers&OperationsResearch, 2012, 39(9): 2 168-2 177.

[22]YEHWC.Newparameter-freesimplifiedswarmoptimizationforartificialneuralnetworktraininganditsapplicationinthepredictionoftimeseries[J].IEEETransactionsonNeuralNetworks&LearningSystems, 2013, 24(4): 661-665.

[23] 戴曼娜, 林培杰, 程樹英, 等. 應(yīng)用粒子群優(yōu)化的高斯粒子濾波[J]. 福州大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 43(1): 54-60.

[24]KITAGAWAG.Non-Gaussianstate-spacemodelingofnonstationarytimeseries[J].JournaloftheAmericanStatisticalAssociation, 1987, 82(400): 1 032-1 041.

(責(zé)任編輯： 沈蕓)

A new particle filter algorithm based on simplified swarm optimization

ZHANGYiqun,LINPeijie,CHENGShuying

(CollegeofPhysicsandInformationEngineering,InstituteofMicro-NanoDevicesandSolarCells,FuzhouUniversity,Fuzhou,Fujian350116,China)

Anewparticlefilterbasedonthesimplifiedswarmoptimization(calledSSO-PF)isproposedforsolvingthedegeneracyandimpoverishmentproblemintheparticlefilter.TheproposedalgorithmusestheemergingSSOthatissimpleastheresamplingstageofparticlefilter.ArandommovementisaddedtoSSOtomaintainparticlesdiversity.Experimentalresultsshowthattheproposedalgorithmnotonlyeffectivelybooststheestimationaccuracyofthenonlinearsystemstate,butalsohasahighercomputingspeed.

particlefilter;simplifiedswarmoptimization;particleswarmoptimization;resampling;particledegeneracy

10.7631/issn.1000-2243.2017.01.0102

1000-2243(2017)01-0102-06

2015-12-09

程樹英(1966-)，教授，博士生導(dǎo)師, 主要從事光伏應(yīng)用系統(tǒng)研究，sycheng@fzu.edu.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目(61574038)； 福建省科技廳工業(yè)引導(dǎo)性重點(diǎn)基金資助項(xiàng)目(2015H0021)，福建省教育廳省屬高?；鹳Y助項(xiàng)目(JK2014003)

TP391

A