基于果蠅優(yōu)化算法改進的粒子濾波及其在目標跟蹤中的應(yīng)用

韓錕 張赫

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

關(guān)鍵詞：粒子濾波；樣本貧化；果蠅優(yōu)化算法；非線性系統(tǒng)；狀態(tài)估計

中圖分類號：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

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

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

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

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

1 粒子濾波算法

2 果蠅優(yōu)化算法（FOA）

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

依據(jù)果蠅搜索食物的特征行為，果蠅優(yōu)化算法基本流程主要由以下3個步驟構(gòu)成：

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

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

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

3 果蠅優(yōu)化粒子濾波（FOAPF）

3.1 整體改進原理

傳統(tǒng)粒子濾波算法的重采樣過程通過復(fù)制大權(quán)重粒子、刪除小權(quán)值粒子來解決粒子匱乏現(xiàn)象，但經(jīng)過多次迭代后，又會帶來粒子貧化問題.

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

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

3.2 適應(yīng)度函數(shù)設(shè)計

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

4.2 粒子多樣性測試

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

5 目標跟蹤實驗

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

6 結(jié) 論

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

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

參考文獻

[1]

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

[2] 王法勝， 魯明羽， 趙清杰，等.粒子濾波算法[J].計算機學(xué)報， 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] 李天成，范紅旗，孫樹棟.粒子濾波理論、方法及其在多目標跟蹤中的應(yīng)用[J].自動化學(xué)報， 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] 朱志宇. 粒子濾波算法及其應(yīng)用[M].北京：科學(xué)出版社，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].電子學(xué)報，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]. 探測與控制學(xué)報，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]田夢楚，薄煜明，陳志敏，等.螢火蟲算法智能優(yōu)化粒子濾波[J].自動化學(xué)報，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]汪榮貴，李孟敏，吳昊，等.一種新型的基于自適應(yīng)遺傳算法的粒子濾波算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報，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]韓虎. 果蠅優(yōu)化算法的分析[J]. 計算機系統(tǒng)應(yīng)用，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]呂振肅，侯志榮. 自適應(yīng)變異的粒子群優(yōu)化算法[J]. 電子學(xué)報，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]韓俊英，劉成忠. 自適應(yīng)變異的果蠅優(yōu)化算法[J]. 計算機應(yīng)用研究，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.