一種新型的簡化群優化粒子濾波算法

張義群，林培杰，程樹英

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

一種新型的簡化群優化粒子濾波算法

張義群，林培杰，程樹英

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

針對粒子濾波的粒子退化和貧化問題，將新興的簡化群優化(SSO)算法引入到粒子濾波的重采樣階段.SSO算法結構簡單，在保留優良粒子的基礎上，增加一項粒子隨機運動過程，以提供粒子多樣性. 實驗結果表明，新算法不僅有效提高了對非線性系統狀態的估計精度，而且具有更高的運算速度.

粒子濾波； 簡化群優化； 粒子群優化； 重采樣； 粒子退化

0 引言

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

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

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

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

1 粒子濾波算法

預測方程為：

更新方程為：

2 基于SSO的粒子濾波算法

2.1 SSO算法

新興的智能優化算法SSO類似于PSO[23]，在迭代過程中也需要根據粒子(個體)的適應值來計算粒子集中，每個粒子的局部最優解和整個粒子集的全局最優解，加快收斂速度.SSO算法狀態更新定義為：

2.2 SSO-PF改進算法

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

的具體實現步驟如下：

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

Step 6令k=k+ 1，返回Step 2，進行下一時刻狀態估計.

3 實驗與分析

實驗中所有程序均使用MatlabR2014a編寫，沒有進行任何針對特殊硬件的優化，測試使用的PC機主要性能指標為IntelCorei5@2.70GHz、4G內存，操作系統為Windows7.

為驗證本算法性能，選取單變量非靜態增長數據模型[24]作仿真比較. 該模型高度非線性，似然函數呈雙峰狀，已經被廣泛應用于粒子濾波性能評測[2-3, 7, 23]. 其狀態方程和量測方程為：

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

輸出結果采用加權方式進行狀態估計，本設計采用均方根誤差(RMSE)作為算法估計精度的評價指標：

(12)

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

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

圖1 在N=100和G=50條件下濾波結果比較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算法中在狀態更新過程中加入了粒子的隨機運動過程，有助于粒子跳出局部極值. 又由于粒子位置更新以及粒子跳出局部最優的能力會受到個體經驗與全局經驗的影響，而個體經驗與全局經驗又受到了粒子慣性的影響. 因此，采用有效的三段式搜索策略，可提高收斂精度. 表1給出了三種算法在N=100和G=50條件下，進行20次獨立實驗取均值所得的結果.

從表1可以看出標準粒子濾波算法運算速度最快，這是由于PF只需要簡單復制高權值粒子剔除低權值粒子，但是精度不高，而本算法SSO-PF精度最高.SSO-PF相比PF，精度提高了72.77%； 相較于PSO-PF，精度提高了67.51%，并且運算時間僅是PSO-PF的62.92%. 而PSO-PF耗時較多是因為在每次優化過程中都必須重新定位粒子的位置和速度，而SSO則不需要更新粒子速度.

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

表1 在N=100和G=50條件下仿真結果數據比較

表2 在N=100和G=100條件下仿真結果數據比較

圖3 在N=100和G=100條件下，濾波結果比較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算法的估計精度明顯優于其它兩種算法. 但是總迭代次數由G=50增加到G=100時，三種算法的濾波效果并沒有得到明顯改善. 因此，迭代次數并不是越多越好.

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

4 結語

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

考慮到PF算法中各個粒子的獨立性，PF算法可以被分解為采樣、權值計算、重采樣三個基本步驟. 而SSO作為PF算法的重采樣技術，算法結構簡單，易于FPGA硬件實現. 因此，在未來的工作中，我們將對SSO算法作改進，以提高收斂速度，并將每個粒子的狀態轉移與觀測視作一條流水線，采用FPGA并行處理所有粒子，實現優化算法的硬件加速，以便于實際工程應用.

[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] 汪榮貴, 李孟敏, 吳昊, 等. 一種新型的基于自適應遺傳算法的粒子濾波算法[J]. 中國科學技術大學學報, 2011, 41(2): 134-141.

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

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

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

[7] 陳志敏, 薄煜明, 吳盤龍, 等. 收斂粒子群全區域自適應粒子濾波算法及其應用[J]. 南京理工大學學報(自然科學版), 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] 姚海濤, 朱福喜, 陳海強. 一種自適應的PSO粒子濾波人臉視頻跟蹤方法[J]. 武漢大學學報(信息科學版), 2012, 37(4): 492-495.

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

[13] 劉宇, 呂明偉, 李維佳, 等. 基于物種的自適應多模態粒子群優化算法[J]. 山東大學學報(理學版), 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] 戴曼娜, 林培杰, 程樹英, 等. 應用粒子群優化的高斯粒子濾波[J]. 福州大學學報(自然科學版), 2015, 43(1): 54-60.

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

(責任編輯： 沈蕓)

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-)，教授，博士生導師, 主要從事光伏應用系統研究，sycheng@fzu.edu.cn

國家自然科學基金資助項目(61574038)； 福建省科技廳工業引導性重點基金資助項目(2015H0021)，福建省教育廳省屬高校基金資助項目(JK2014003)

TP391

A