基于果蠅優化算法改進的粒子濾波及其在目標跟蹤中的應用

韓錕 張赫

摘 要：針對粒子濾波算法重采樣導致的樣本貧化問題，提出一種基于果蠅優化思想的粒子濾波算法.該方法視粒子權值為個體適應度值，并將果蠅不斷從低濃度的地方飛向高濃度的地方的覓食尋優過程引入到粒子濾波當中，驅使粒子不斷向高似然區域移動，提高了粒子群的整體質量.為了解決標準果蠅優化算法易陷入早熟的問題，將遺傳算法中的交叉、變異操作自適應地應用到果蠅優化算法尋優過程當中.首先通過交叉操作改善粒子分布，當果蠅優化算法陷入局部最優時，再采用柯西變異擾動，促使算法快速跳出局部極值并繼續搜索全局極值.通過非線性模型仿真以及目標跟蹤實驗表明該算法有效提高了非線性系統狀態估計精度，具有較好的穩定性，同時降低了狀態估計所需的粒子數量.

關鍵詞：粒子濾波；樣本貧化；果蠅優化算法；非線性系統；狀態估計

中圖分類號：TP391.41 文獻標志碼：A

Abstract：A particle filter method based on fruit fly optimization algorithm is proposed to alleviate the sample impoverishment caused by resampling. When fruit flies forage， they usually fly from low concentration areas to high concentration areas efficiently and constantly. This optimum process is introduced into the particle filter to drive particles towards the high likelihood areas ceaselessly， and thus improves the overall quality of the particle swarm. Considering that the premature convergence is always associated with the fruit fly optimization algorithm， crossover and mutation operations of genetic algorithms are applied herein adaptively to keep the diversity of samples. Firstly， the particle distribution is improved by cross operation. When the algorithm falls into the local optimum， the Cauchy mutation perturbation is then used to help the fruit fly optimization algorithm jump out of the local optimal point effectively and continue searching for global extremum. The nonlinear simulations and target tracking experiments show that the proposed algorithm improves the estimation accuracy of the nolinear systems state， and it has better stability and reduces the number of particles required for state estimation at the same time.

Key words：particle filter； sample impoverishment； fruit fly optimization algorithm； nonlinear systems； state estimation

粒子濾波是一種用于求解后驗概率的方法，它通過非參數化蒙特卡洛模擬方法實現遞推貝葉斯濾波[1].由于粒子濾波擺脫了傳統解決非線性濾波問題時，隨機量必須滿足高斯分布的制約條件[2]，使其能夠在非線性、非高斯系統下，相較于基于卡爾曼濾波框架的濾波算法，展現出明顯的優越性.目前粒子濾波在無線定位、金融與經濟學、參數估計、目標跟蹤[3-6]等領域，都具有非常廣闊的應用前景.然而，傳統的粒子濾波還存在著一些不足，需要加以改善，例如序列重要性采樣會帶來粒子退化問題，即經過若干次循環遞推后，粒子集中絕大多數粒子權值變得很小，甚至接近于零，只有少數粒子具有非零權值，造成粒子集無法表達實際的后驗概率分布[7].雖然通過重采樣[8]復制權重較大粒子、刪除低權值粒子能夠在一定程度上抑制粒子退化問題，卻在同時也破壞了粒子多樣性，導致粒子出現貧化現象[9].

近年來，為了解決粒子濾波算法存在的這些問題，國內外學者提出了很多改進方法，主要是以優化重采樣的角度來改進濾波精度.例如，Li等[10]提出確定性重采樣，利用粒子空間信息和狀態值進行重采樣，避免盲目丟棄低權重的粒子，從而保證了粒子的多樣性，但是對于權值較大的粒子，直接進行了權值平均，并沒有有效利用它們所具有的信息.程水英等[11]提出在重采樣前進行權值排序列、裂變繁殖、權值歸一的預處理，以平滑權值差異使得更多的樣本能夠進行重采樣，這樣雖然能延遲貧化時間，但無法從根本上避免貧化.張光等[12]采用正則化方法，引入核密度函數和核帶寬系數以連續形式計算狀態后驗概率，有效緩解粒子退化問題，但無法保證樣本粒子都能近似表示后驗概率，因而對非線性系統參數估計不能達到最優.

將群體智能優化算法與粒子濾波結合是目前粒子濾波發展的一個較新的思路[13].采用智能優化算法來避免粒子貧化問題，主要是將標準粒子濾波中的每個粒子看作生物群體的每個個體，通過模擬生物集群的運動規律來調整粒子的分布，使粒子群體向高似然區域移動，更加接近真實后驗分布，由于其過程并未舍棄權重低的粒子，因而能夠從根本上避免粒子貧化現象[14].目前，已經有多種基于群智能優化算法的粒子濾波被提出，例如，田夢楚等[14]提出基于螢火蟲算法的粒子濾波，引入了螢火蟲群體的優勝劣汰機制以及螢火蟲個體的吸引和移動的行為，使粒子向高似然區域移動，從而提高估計精度.汪榮貴等[15]將自適應遺傳算法應用到粒子濾波相，依據粒子的適應度值自適應確定對粒子進行遺傳操作的概率，然后對選出的粒子實施交叉、變異操作來移動粒子，增加粒子多樣性.Tian等[16]將人工魚群算法和無跡粒子濾波結合，利用人工魚群算法優化采樣過程，克服樣本貧化問題.

果蠅優化算法[17]由臺灣學者潘文超博士于2011年提出，是通過模擬自然界果蠅覓食行為而推演出來的群智能優化算法，也是迄今為止所需調整參數最少、進化方程最為簡單的群體智能優化算法之一[18].本文結合果蠅優化算法迭代尋優機制以及粒子濾波的特點，對果蠅優化算法尋優機制加以改進，引入自適應交叉和變異操作，保障粒子多樣性，并將結合交叉、變異的果蠅優化算法到融入粒子濾波當中，提出基于改進的果蠅優化思 想的粒子濾波算法.通過模型仿真以及目標跟蹤實驗，表明本文所提算法在保證粒子多樣性的同時也能夠很好的提高狀態估計精度與穩定性.

1 粒子濾波算法

2 果蠅優化算法（FOA）

果蠅優化算法是一種源于果蠅覓食行為推演出尋求全局優化的群體智能算法[17].FOA的仿生原理是將種群數量為N的果蠅個體映射為搜索空間中的N個可行解，整個迭代尋優以及搜索過程模擬成果蠅群體覓食過程.果蠅本身在感官知覺上優于其它物種，尤其是在嗅覺與視覺上，果蠅的嗅覺器官能夠較好地搜集漂浮在空氣中的各種氣味，根據果蠅個體感知到的食物味道濃度的大小來衡量每個果蠅個體所處位置的優劣，味道濃度越大，則表明該果蠅位置距離食物越近.果蠅覓食的過程就是果蠅不斷從濃度低的地方飛向濃度高的地方，飛近食物位置后亦可使用敏銳的視覺發現食物與同伴聚集的位置，且往該方向飛去，直到找到食物.

依據果蠅搜索食物的特征行為，果蠅優化算法基本流程主要由以下3個步驟構成：

1） 種群初始化：確定果蠅群體數量N、最大迭代次數m以及初始化果蠅個體覓食位置X0，Y0.

2） 覓食活動：果蠅群體從初始位置出發，利用嗅覺搜尋食物，每個個體的搜索方向與距離皆為設定范圍的隨機數.根據當前的位置Xi，Yi，計算每個果蠅適應度值fi（味道濃度值），找出其中適應度值最大（或最小）的個體，然后群體利用視覺向該個體位置飛去.

3） 種群位置更新：每一次迭代過程即每一次從當前最佳適應值位置飛出到下一最佳位置的過程，若下一次最佳適應度值大于前一次最佳適應度值，則群體更新最佳適應度值點為新的覓食位置X0，Y0，所有個體向該位置飛去，然后再飛出繼續搜索.如此反復，直到達到最大迭代次數或設定精度為止.

3 果蠅優化粒子濾波（FOAPF）

3.1 整體改進原理

傳統粒子濾波算法的重采樣過程通過復制大權重粒子、刪除小權值粒子來解決粒子匱乏現象，但經過多次迭代后，又會帶來粒子貧化問題.

針對上述問題，本文將果蠅優化算法融入到粒子濾波中改善采樣過程.算法具體思路如下：在標準粒子濾波過程中，當經過重要性采樣得到N個粒子后，根據個體的位置以及設定的適應度函數計算每個粒子的適應度值，如果粒子集分布在真實狀態附近，那么，粒子群中每個粒子的適應度值都很高；反之，如果粒子群中的適應度最優值很低，則說明粒子集沒有分布在真實狀態附近，此時，利用FOA算法對粒子分布進行優化，粒子不斷向適應度值高的地方飛去，使得粒子不斷向真實狀態靠近，從而提高粒子群整體樣本的質量.當粒子集的最優值達到設定的閾值ε時，則說明粒子集已經分布在真實狀態附近，此時即可停止優化.

通過上述優化過程，驅使粒子集合不斷向高似然區域靠近，從而解決粒子貧乏問題.然而，果蠅優化算法也存在著一些不可避免的問題，即在整個尋優過程中果蠅只向當前味道濃度最高的個體飛去，所有粒子分布隨機在最優值附近，無法保證粒子多樣性.而且如果該個體不是全局最優值，極易使算法陷入局部最優，從而降低收斂速度和收斂精度，帶來早熟收斂的問題.因而直接將果蠅優化算法融入到粒子濾波中并不一定會得到理想的效果，需要對果蠅優化過程進行適當的改進，采用一種機制，讓算法在出現早熟收斂時，能夠跳出局部最優，并進入解空間的其它區域繼續進行搜索，直到找出全局最優解[19].本文采取在果蠅優化算法中引入自適應交叉算子、自適應變異機制，首先對粒子群體進行自適應交叉操作，增加粒子多樣性，可以在在一定程度減小陷入局部最優幾率.然后判斷算法是否陷入早熟收斂，若是，則復制一些當前最優粒子，對這些粒子進行柯西變異操作，可以促使算法跳出局部最優，繼續搜索全局極值.

3.2 適應度函數設計

從圖1～6可以看出，本文所提基于改進的果蠅優化算法的粒子濾波（FOAPF），相較于標準PF以及GAPF，狀態預測曲線與實際狀態相似程度最高，其估計值更接近真實值，這是因為FOAPF在PF的基礎上，通過對重要性采樣后的粒子進行引入交叉、變異操作的果蠅迭代尋優，使粒子向高似然區域運動的同時，保證了樣本多樣性，從而提高粒子分布的合理性.表1、表2中數據為每種算法獨立運行50次后的均方根誤差平均值以及方差，從中可以看出，3種算法隨著粒子數的增加，均方根誤差以及方差大體上皆呈現減小的趨勢，這與粒子濾波的粒子數越多則估計精度越高的理論是相符的.而在三種算法中，FOAPF的均方根誤差以及方差最低，且是唯一一個在粒子數為100時兩者皆小于1的，當粒子數為50時，其誤差值也比粒子數為100的PF算法低，與GAPF也只有不到0.2的差距，說明FOAPF能夠用較少的粒子達到所需的精度.而均方根誤差方差體現算法預測的穩定性，FOAPF也是最低的，當粒子數越多時更為明顯.綜上分析，FOAPF具有更好的估計精度以及穩定性.

4.2 粒子多樣性測試

為測試FOAPF濾波時的粒子多樣性，設置粒子數為100，取PF和FOAPF濾波器在迭代過程第20和45步時的粒子分布情況，如圖7～8所示，可以看出，FOAPF與標準PF相比，具有更寬的粒子分布，除了在高似然區域存在較多粒子，周邊區域也分布著部分粒子，說明FOAPF在預測精度優于PF的同時，粒子多樣性并沒有降低，這是因為對果蠅尋優過程進行了自適應的交叉與變異操作，保證了粒子多樣性不下降，而且本文并沒有進行重采樣操作，也能夠有效地避免粒子貧化現象的出現.

5 目標跟蹤實驗

目標跟蹤在計算機視覺領域中有著廣泛的應用前景和商業價值，包括智能監控、人機交互、視頻檢索等.快速移動的目標往往具有非線性、非高斯的特點，跟蹤要求有較高的實時性、魯棒性.近年來，基于相關濾波[21]的判別式跟蹤方法以其優越的跟蹤速度、出色的跟蹤性能及高效的魯棒性得到了廣泛關注和應用.為檢驗本文所提算法在目標跟蹤應用中的實際效果，將本文所提方法與相關濾波算法分別應用到視頻目標跟蹤當中，并對結果進行分析.

6 結 論

1）本文算法FOAPF通過單變量非靜態增長模型進行了仿真，粒子數為100時，實驗結果均方根誤差均值為0.729 5，均方根誤差方差為0.454 4，表明本文算法精度、穩定性均高于標準粒子濾波和基于遺傳算法的粒子濾波算法，粒子分布圖進一步說明本文算法有效保證了粒子的多樣性.

2）將FOAPF算法運用到視頻目標跟蹤實驗中，與相關濾波算法跟蹤結果進行比較，實驗結果表明本文算法對目標快速移動以及被遮擋的情況都具有良好的跟蹤效果.

參考文獻

[1]

DOUCTE A， DE FREITAS N， GORDON N. Sequential Monte Carol methods in practice[M]. New York： SpringerVerlag，2001.

[2] 王法勝， 魯明羽， 趙清杰，等.粒子濾波算法[J].計算機學報， 2014， 37（8）：1679-1694.

WANG F S， LU M Y， ZHAO Q J， et al. Particle filter algorithm[J]. Journal of Computer Science， 2014， 37（8）：1679-1694.（In Chinese）

[3] GUSTAFSSON F. Particle filter theory and practice with positioning applications[J]. Aerospace & Electronic Systems Magazine IEEE， 2010， 25（7）：53-82.

[4] 李天成，范紅旗，孫樹棟.粒子濾波理論、方法及其在多目標跟蹤中的應用[J].自動化學報， 2015， 41（12）：1981-2002.

LI T C， FAN H Q， SUN S D. Particle filtering： theory， approach， and application for multitarget tracking[J]. Acta Automatica Sinica， 2015， 41（12）： 1981-2002. （In Chinese）

[5] GAO M， ZHANG H. Sequential Monte Carlo methods for parameter estimation in nonlinear statespace models[J]. Computers & Geosciences， 2012， 44（13）：70-77.

[6] CREAL D. A survey of sequential Monte Carlo methods for economics and finance[J]. Serie Research Memoranda， 2009， 31（3）：245-296.

[7] 朱志宇. 粒子濾波算法及其應用[M].北京：科學出版社，2010：27-31.

ZHU Z Y. Particle filter algorithm and its application[M]. Beijing： Science Press， 2010：27-31. （In Chinese）

[8] ARULAMPALAM M S， MASKELL S， GORDON N， et al. A tutorial on particle filters for online nonlinear/nongaussisan Bayesian tracking[J]. IEEE Transactions on Signal Processing，2002，50（2）：174-188.

[9] FOO P H， NG G W. Combing the interacting multiple model method with particle filters for manoeuvring target tracking[J]. IET Radar， Sonar and Navigation，2011，5（3）：234-255.

[10]LI T C， SATTAR T P， SUN S D. Deterministic resampling ：unbiased sampling to avoid sample impoverishment in particle filters[J]. Signal Processing，2012，92（7）：1637-1645.

[11]程水英，張劍云.裂變自舉粒子濾波[J].電子學報，2008，36（3）：500-504.

CHENG S Y， ZHANG J Y. Fission bootstrap particle filter[J]. Journal of Electronics， 2008，36（3）：500-504. （In Chinese）

[12]張光，張英堂，任國全，等.基于正則化粒子濾波的磁梯度張量跟蹤方法[J]. 探測與控制學報，2014（2）：0050-0053.

ZHANG G， ZHANG Y T， REN G Q， et al. Tracking method of magnetic gradient tensor based on RPF[J]. Journal of Detection & Control， 2014（2）：0050-0053. （In Chinese）

[13]YU Y， ZHENG X. Particle filter with ant colony optimization for frequency offset estimation in OFDM systems with unknown noise distribution[J]. Signal Processing， 2011， 91（5）：1339-1342.

[14]田夢楚，薄煜明，陳志敏，等.螢火蟲算法智能優化粒子濾波[J].自動化學報，2016，42（1）：89-97.

TIAN M C， BO Y M， CHEN Z M， et al. Firefly algorithm intelligence optimized particle filter[J]. Acta Automatica Sinica， 2016，42（1）：89-97. （In Chinese）

[15]汪榮貴，李孟敏，吳昊，等.一種新型的基于自適應遺傳算法的粒子濾波算法[J].中國科學技術大學學報，2011，41（2）：134-141.

WANG R G， LI M M， WU H， et al. 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）

[16]TIAN Y， LU C， WANG Z， et al. Artificial fish swarm algorithmbased particle filter for liion battery life prediction[J]. Mathematical Problems in Engineering， 2014（3）：1-10.

[17]PAN W T. A new fruit fly optimization algorithm： taking the financial distress model as an example[J]. KnowledgeBased Systems， 2012， 26（2）：69-74.

[18]韓虎. 果蠅優化算法的分析[J]. 計算機系統應用，2017，26（2）：9-17.

HAN H. Analysis on fruit fly optimization algorithm[J].Journal of Computer Applications，2017，26（2）：9-17. （In Chinese）

[19]呂振肅，侯志榮. 自適應變異的粒子群優化算法[J]. 電子學報，2004，32（3）：416-420.

L Z S， HOU Z R. Particle swarm optimization with adaptive mutation[J].Acta Electronica Sinica，2004，32（3）：416-420. （In Chinese）

[20]韓俊英，劉成忠. 自適應變異的果蠅優化算法[J]. 計算機應用研究，2013，30（9）：2641-2644.

HAN J Y， LIU C Z. Fruit fly optimization algorithm with adaptive mutation[J].Application Research of Computers，2013，30（9）：2641-2644. （In Chinese）

[21]HENRIQUES J F， RUI C， MARTINS P， et al. Highspeed tracking with kernelized correlation filters[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2014， 37（3）：583-596.