一種改進(jìn)的蝴蝶算法優(yōu)化粒子濾波算法

張威虎 郭明香 賀元愷 孫小婷 朱代先

摘 要：傳統(tǒng)的粒子濾波算法在重采樣期間丟棄小重量粒子，因此重要性權(quán)重落在極少數(shù)粒子上。這會(huì)導(dǎo)致采樣粒子貧化、粒子多樣性缺失以及需要大量粒子才能進(jìn)行比較準(zhǔn)確的狀態(tài)估計(jì)等問題，針對(duì)這些問題，提出了一種改進(jìn)的蝶式算法優(yōu)化粒子濾波算法。首先，將最新時(shí)刻觀測(cè)信息引入蝴蝶香味公式中，以提高濾波精度;其次，引入吸引半徑參數(shù)來控制蝴蝶種群尋優(yōu)的搜索范圍，降低算法的復(fù)雜度，進(jìn)而提高算法的實(shí)時(shí)性;最后，將改進(jìn)的蝴蝶種群位置更新公式用于優(yōu)化迭代更新。實(shí)驗(yàn)結(jié)果表明，與經(jīng)典粒子濾波器和現(xiàn)有蝶形優(yōu)化算法相比，改進(jìn)算法具有更低的均方誤差和運(yùn)行時(shí)間。并且在粒子數(shù)較少的情況下，可以實(shí)現(xiàn)更準(zhǔn)確的狀態(tài)估計(jì)，并改善傳統(tǒng)濾波器的粒子耗盡現(xiàn)象，保證了粒子多樣性。

關(guān)鍵詞：粒子濾波;粒子貧化;狀態(tài)估計(jì);蝴蝶算法;濾波精度

中圖分類號(hào)：TP 391.4?文獻(xiàn)標(biāo)志碼：A

DOI：10.13800/j.cnki.xakjdxxb.2019.0117文章編號(hào)：1672-9315（2019）01-0119-05

An improved butterfly algorithm optimizing particle filter algorithm

ZHANG Wei?hu，GUO Ming?xiang，HE Yuan?kai，SUN Xiao?ting，ZHU Dai?xian

（College of Communication and InformationEngineering，Xi’an University of Science and Technology，Xi’an 710054，China）

Abstract：Traditional particle filtering algorithms discard small weight particles during resampling，so importance weights fall on very few particles，leading to the problem of sampled particle depletion，lack of particle diversity，and the need for a large number of particles for more accurate state estimation.In this paper，an improved butterfly algorithm is proposed to optimize the particle filter algorithm.Firstly，the latest moment observation information is introduced into the butterfly flavor formula to improve the filtering accuracy; Secondly，the attraction radius parameter is introduced to control the search range of butterfly population optimization，which reduces the complexity of the algorithm and improves the real?time performance of the algorithm.Finally，the improved butterfly population location update formula is used to optimize iterative updates.The experimental results show that compared with the classical particle filter and the existing butterfly optimization algorithm，the improved algorithm has a lower mean square error and running time.And in the case of a small number of particles，more accurate state estimation can be achieved，and the particle depletion phenomenon of the conventional filter can be improved，and the particle diversity is ensured.

Key words：particle filtering;particle depletion;state estimation;butterfly algorithm;filtering accuracy

0?引?言

粒子濾波器（Particle Filter，PF）[1]

是一種處理非線性、非高斯系統(tǒng)的濾波方法，在故障診斷、目標(biāo)跟蹤、信號(hào)處理、機(jī)器人定位以及航空航天等領(lǐng)域均有廣泛的應(yīng)用[2]。但是它的一個(gè)缺點(diǎn)就是粒子退化的問題，即經(jīng)過多次迭代以后，重要性權(quán)重集中在非常少的粒子個(gè)體上，這會(huì)導(dǎo)致粒子匱乏，粒子多樣性缺失等問題。針對(duì)這些問題，大量學(xué)者提出改進(jìn)算法。Gordon等引入了“重采樣思想”[3]，在算法中，多次復(fù)制權(quán)重大的粒子，拋棄權(quán)重小的粒子[4]，來緩解粒子權(quán)重退化問題[5]。但該方法又帶來樣本多樣性缺失的問題，影響了濾波的準(zhǔn)確性。張琪等提出了一種權(quán)值選擇的粒子濾波算法[6]，根據(jù)粒子權(quán)重的大小，對(duì)粒子進(jìn)行取舍，選擇較好的粒子用于濾波，來增加樣本的多樣性，進(jìn)而提高濾波的準(zhǔn)確性。但是這些算法丟棄了部分粒子個(gè)體信息，不能從根本上解決粒子濾波的粒子退化問題。使用種群智能優(yōu)化算法來優(yōu)化粒子濾波已成為解決粒子退化問題的一個(gè)熱點(diǎn)方向，即使用運(yùn)動(dòng)定律的生物學(xué)優(yōu)化使得粒子分布更加合理。由于群智能算法優(yōu)化的粒子濾波主要是通過迭代尋優(yōu)來改變粒子個(gè)體分布的位置，進(jìn)而改善粒子的分布，不對(duì)粒子的信息進(jìn)行舍棄，因此可以從根本上解決粒子耗盡現(xiàn)象。許多國(guó)內(nèi)外學(xué)者引入形式各異的粒子濾波算法和群智能算法[7-11]來解決粒子匱乏、提高精度等，但是存在容易陷入局部極小值、計(jì)算量大、實(shí)時(shí)性較差等問題。劉云濤提出的基于蝴蝶優(yōu)化的粒子濾波算法[12]，利用蝴蝶的全局優(yōu)化能力，有效地控制了粒子匱乏問題，但是在局部搜索，粒子間吸引時(shí)需要全部任意兩個(gè)粒子之間交互運(yùn)算，實(shí)時(shí)性較差。

針對(duì)上述問題，在王航星等基于自適應(yīng)吸引半徑的螢火蟲優(yōu)化粒子濾波[13]的啟發(fā)下，提出一種改進(jìn)的蝴蝶算法優(yōu)化粒子濾波算法。首先，將當(dāng)前時(shí)刻的最新觀測(cè)值引入蝴蝶香味公式，然后，引入新的參數(shù)吸引半徑來控制蝴蝶種群個(gè)體尋優(yōu)的范圍，最后，使用改進(jìn)的蝴蝶種群位置更新公式進(jìn)行迭代更新，將改進(jìn)的算法與經(jīng)典粒子濾波（PF）、蝴蝶優(yōu)化的粒子濾波算法[12]（BAPF）進(jìn)行了比較，此算法在改善粒子退化和濾波精度的同時(shí)，具有更低的誤差和運(yùn)行時(shí)間。

1?粒子濾波算法

假設(shè)此非線性系統(tǒng)模型為

xt=f（xt-1，ut）+wt

zt=h（xt，ut）+vt（1）

式中?f（·）和h（·）分別為狀態(tài)轉(zhuǎn)移方程和觀測(cè)方程;xt和zt為系統(tǒng)在t時(shí)刻的狀態(tài)變量和觀測(cè)值;wt和vt為2個(gè)獨(dú)立的噪聲，即過程噪聲和觀測(cè)噪聲;ut為系統(tǒng)在t時(shí)刻的輸入量。在此模型下，假設(shè)k-1時(shí)刻狀態(tài)后驗(yàn)分布的粒子集為

{xit-1，wit-1}，相應(yīng)的粒子濾波算法可參考文獻(xiàn)[1]。

2?蝴蝶算法

蝴蝶算法（Butterfly Algorithm，BA）[14]是一種基于蝴蝶覓食行為的全局優(yōu)化算法。算法的收斂精度和速度優(yōu)于其它算法。它主要模仿蝴蝶種群尋找食物，每只蝴蝶都散發(fā)出一定濃度的香氣，每只蝴蝶都會(huì)感受到周圍其它蝴蝶的味道，并朝著那些散發(fā)更多香味的蝴蝶移動(dòng)。蝴蝶的香味取決于3個(gè)因素：感知形態(tài)、刺激強(qiáng)度以及冪指數(shù)。用方程表示為

F=cIa式中?F為香氣的濃度;c為感知形式;I為刺激強(qiáng)度;a為冪指數(shù)。

已知目標(biāo)函數(shù)f（x），蝴蝶算法的步驟如下

1）初始化蝴蝶種群，并通過目標(biāo)函數(shù)f（xi）確定每只蝴蝶xi的刺激強(qiáng)度Ii;

2）計(jì)算蝴蝶種群的個(gè)體適應(yīng)度值，找到最佳位置的蝴蝶;

3）計(jì)算蝴蝶散發(fā)的香味。為減少外界環(huán)境因素的影響，隨機(jī)數(shù)P用于確定蝴蝶的搜索方法是執(zhí)行局部搜索還是全局搜索;

4）全局搜索，低香味的蝴蝶個(gè)體飛向全局適應(yīng)度最高的蝴蝶，全局搜索表示為

式中?xit為第i只蝴蝶在第t次迭代的解向量;g*為當(dāng)前所有蝴蝶中的最優(yōu)解。

5）局部搜索，蝴蝶個(gè)體進(jìn)行Lévy隨機(jī)飛行。局部搜索可以表示為

式中?xit，xjt，xkt分別為第i只、第j只、第k只蝴蝶在第t次迭代的解向量;xjt， xkt為隨機(jī)個(gè)體。

為了避免蝴蝶進(jìn)入局部最優(yōu)，Lévy飛行被引入到算法中

Lévy飛行加速了局部搜索并提高了搜索效率。一般取λ為（1，3]。

3?改進(jìn)算法

將蝴蝶算法引入粒子濾波算法，其思想是將粒子濾波器中的粒子視為蝴蝶群體中的個(gè)體，并且蝴蝶被彼此之間的香味所吸引，算法中的個(gè)體通過迭代將其位置向適應(yīng)度最高的蝴蝶移動(dòng)，類似于粒子濾波中的粒子不斷接近實(shí)際系統(tǒng)狀態(tài)的粒子的后驗(yàn)概率分布，而蝴蝶算法中適應(yīng)度的最高值，可視為粒子濾波中權(quán)重最大的粒子最可能處于真實(shí)的后驗(yàn)概率分布。

如果直接將蝴蝶算法引入粒子濾波，會(huì)造成信息丟失、運(yùn)算復(fù)雜等問題，因此，文中引入蝴蝶算法并做如下修改

傳統(tǒng)的算法中，由于選取次優(yōu)的重要性概率密度函數(shù)，丟棄了最新時(shí)刻的觀測(cè)值，導(dǎo)致算法的準(zhǔn)確性低下等問題。文中引入粒子濾波中當(dāng)前時(shí)刻的觀測(cè)值，定義蝴蝶算法的刺激強(qiáng)度公式為

Ii=exp[-12R（Znew-Zpred）2]（6）

式中?R為觀測(cè)噪聲的方差;Znew為最新觀測(cè)值;Zpred為預(yù)測(cè)的觀測(cè)值; Ii為刺激強(qiáng)度。

刺激強(qiáng)度最終反映蝴蝶個(gè)體香味的大小，相對(duì)于原始的公式而言，改進(jìn)后的公式利用每個(gè)時(shí)刻每個(gè)粒子自身的觀測(cè)值與預(yù)測(cè)值之間的差值平方來表示粒子每個(gè)時(shí)刻的刺激強(qiáng)度，不再需要將全部粒子與最優(yōu)粒子進(jìn)行比較計(jì)算，減少了算法在迭代尋優(yōu)過程中的計(jì)算量。同時(shí)，通過加入粒子觀測(cè)值信息的策略，將算法預(yù)測(cè)值與觀測(cè)值的差值實(shí)時(shí)地反映在刺激強(qiáng)度中，有效地提高了算法的濾波精度。

3.1?引入自適應(yīng)吸引半徑參數(shù)

蝴蝶算法的全局優(yōu)化能力很強(qiáng)，但隨著個(gè)體數(shù)量的增加，時(shí)間復(fù)雜度會(huì)急劇增加。因此，文中設(shè)計(jì)一個(gè)新的參數(shù)——吸引半徑，吸引半徑的作用是用來限制蝴蝶個(gè)體間相互吸引的吸引范圍和粒子數(shù)目。香味濃度的大小決定了吸引半徑的大小，香味越大，粒子吸引半徑越大。

如圖1所示，a，b，c分別為香味F（a），F(xiàn)（b），F(xiàn)（c）的3只蝴蝶個(gè)體，吸引半徑為

rb>rc>ra.對(duì)于蝴蝶b，c，由rb>rbc，即蝴蝶c在蝴蝶b的吸引范圍內(nèi)，所以蝴蝶c會(huì)被蝴蝶b吸引并更新位置;但對(duì)于蝴蝶a，盡管其香味最小，但由于它不在蝴蝶個(gè)體b，c的吸引范圍內(nèi)，便不會(huì)被b，c吸引，位置不更新。因此，對(duì)于兩只香味不同的蝴蝶，只有當(dāng)蝴蝶間距離小于較香蝴蝶的吸引半徑時(shí)才會(huì)發(fā)生位置更新，否則不更新。

根據(jù)以上分析，定義吸引半徑計(jì)算公式為

r=0.3Fi（7）

式中?r為相對(duì)吸引半徑;Fi為種群個(gè)體的香味值。引入?yún)?shù)后，粒子間的相互吸引，不再需要將每一個(gè)粒子與其他粒子之間比較，而是只需要將在吸引半徑內(nèi)的粒子進(jìn)行香味比較，同時(shí)更新粒子位置，引入?yún)?shù)后的算法，提高準(zhǔn)確性，減少錯(cuò)誤率和運(yùn)行時(shí)間。

3.2?位置更新公式

蝴蝶種群中的個(gè)體在相互吸引中更新位置，從而不斷地向香味更高的區(qū)域靠攏。文中，將位置更新公式設(shè)置為

xit+1=xit+（xjt-xit）×|Lévy（λ）|×Fi（8）

式中?xit+1為個(gè)體i在t+1時(shí)刻的解向量;xit，xjt為個(gè)體i，j在t時(shí)刻的解向量;Lévy為隨機(jī)飛行;Fi為每只蝴蝶的香味。

綜上，改進(jìn)后算法如下

1）初始化。由先驗(yàn)概率p（x0）產(chǎn)生初始粒子群{xi0，i=，…，N}，所有粒子初始權(quán)重設(shè)置為1/N.設(shè)置初始化參數(shù)迭代次數(shù)t，粒子數(shù)目N，蝴蝶算法中各參數(shù)感知形態(tài)c，冪指數(shù)a等參數(shù);

2）預(yù)測(cè)。根據(jù)式（1）計(jì)算t+1時(shí)刻粒子預(yù)測(cè)值;

3）初始化蝴蝶算法。將粒子濾波中的粒子視為蝴蝶群體中的蝴蝶。根據(jù)式（6）計(jì)算每只蝴蝶的刺激強(qiáng)度，根據(jù)式（2）計(jì)算每只蝴蝶的香味;

4）使用改進(jìn)后的蝴蝶算法進(jìn)行迭代優(yōu)化。根據(jù)式（7）計(jì)算吸引半徑r，計(jì)算xit，xjt兩只蝴蝶之間的距離rij=（xi-xj）2.如果rij

5）更新權(quán)值并歸一化;

6）重采樣及狀態(tài)輸出。

4?實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)的硬件環(huán)境為臺(tái)式電腦（Intel Core i 5處理器、4GB內(nèi)存），實(shí)驗(yàn)環(huán)境為MATLAB 2016b，

將文中算法與傳統(tǒng)粒子濾波算法（PF）、現(xiàn)有蝴蝶優(yōu)化算法[12]（BAPF）相比，本文采用的系統(tǒng)的狀態(tài)方程和觀測(cè)方程為

x（t）=0.5x（t-1）+25x（t-1）1-[x（t-1）]2

+8cos[1.2（t-1）]+w（t）（9）

y（t）=x（t）220+v（t）（10）

此模型是一個(gè)典型的非線性、非高斯系統(tǒng)模型，算法中，取w（t）為服從均勻分布的噪聲;v（t）為服從（1，t）高斯分布的噪聲。各濾波算法的性能用參數(shù)均方根誤差

ERMSE來衡量。公式表示為

ERMSE=

1TNn=1（xnt-nt）212（11）

仿真圖如圖2，3，4所示。

從圖2～4可以看出，改進(jìn)后算法的狀態(tài)值預(yù)估精度和誤差率都得到了提高，這是因?yàn)楦倪M(jìn)算法在PF的基礎(chǔ)上，引入蝴蝶尋優(yōu)算法，不存在對(duì)粒子進(jìn)行舍棄，它可以從根本上改善粒子匱乏問題，使粒子分布更加合理。

由于實(shí)驗(yàn)會(huì)存在噪聲因素，為提高數(shù)據(jù)的準(zhǔn)確性，本實(shí)驗(yàn)數(shù)據(jù)是在大量實(shí)驗(yàn)的基礎(chǔ)上，取其平均值做一對(duì)比。從表中可以看出，當(dāng)N逐漸增加，這3種算法的ERMSE值均減小，這與粒子濾波理論一致。文中算法與經(jīng)典粒子濾波，BAPF算法相比，在保證算法精度的基礎(chǔ)上，均方誤差和運(yùn)行時(shí)間上也都有所改善，效果均優(yōu)于其他算法，這是因?yàn)楸舅惴ㄒ肓藚?shù)吸引半徑，大大簡(jiǎn)化了程序的運(yùn)行時(shí)間，蝴蝶算法由于引進(jìn)了Lévy隨機(jī)飛行，它避免了粒子陷入局部最優(yōu)的問題，提高了算法的準(zhǔn)確性。當(dāng)N=20，50時(shí)，在少量粒子情況下，可以實(shí)現(xiàn)更精確的濾波精度，它能從根本上解決粒子濾波匱乏的現(xiàn)象，改善粒子的多樣性。

5?結(jié)?論

1）引入蝴蝶算法優(yōu)化粒子濾波，使得遠(yuǎn)離真實(shí)狀態(tài)的粒子向高似然區(qū)域移動(dòng)，從根本上解決了粒子退化的問題，提高了算法的準(zhǔn)確性;

2）引入吸引半徑參數(shù)，控制粒子的吸引范圍，大大縮短程序的運(yùn)行時(shí)間，在保證精度的基礎(chǔ)上，降低了誤差和運(yùn)行時(shí)間;

3）此算法能在粒子數(shù)量少的情況下保證濾波精度，還縮短了運(yùn)行時(shí)間，提高實(shí)時(shí)性，因此具有實(shí)用價(jià)值。后續(xù)重點(diǎn)研究將改進(jìn)算法應(yīng)用到移動(dòng)機(jī)器人SLAM中。

參考文獻(xiàn)（References）：

[1] 王法勝，魯明羽，趙清杰，等.粒子濾波算法[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（8）：1679-1693.

WANG Fa?sheng，LU Ming?yu，ZHAO Qing?jie，et al.Particle filtering algorithm[J].Journal of Computer，2014，37（8）：1679-1693.

[2]曹?潔，荊銀銀，王進(jìn)花.基于改進(jìn)的螢火蟲算法優(yōu)化粒子濾波方法[J].蘭州理工大學(xué)學(xué)報(bào)，2018，44（4）：84-89.

CAO Jie，JING Yin?yin，WANG Jin?hua.Optimized particle filter algorithm based on improved firefly algorithm[J].Journal of Lanzhou University of Technology，2018，44（4）：84-89.

[3]Grodon N J，Slamond D J，Smith A F M.Novel approach to nonlinear/non?Gaussian Bayesian state estimation[J].Radar and Signal Processing，1993，140（2）：107-113.

[4]Li T，Bolic M，Djuric P M.Resampling methods for particle filtering：classification，implementation，and strategies[J].IEEE Signal Processing Magazine，2015，32（3）：70-86.

[5]史卓瑛.面向空曠場(chǎng)景基子移動(dòng)設(shè)備的室內(nèi)定位與導(dǎo)航系統(tǒng)[D].杭州：浙江大學(xué)，2018.

SHI Zhuo?ying.Indoor localization and navigation system for mobile devices in spacious environment[D].Hangzhou：Zhejiang University，2018.

[6]張?琪，胡昌華，喬玉坤.基于權(quán)值選擇的粒子濾波研究[J].控制與決策，2008，23（1）：117-120.

ZHANG Qi，HU Chang?hua，QIAO Yu?kun.Particle filter algorithm based on weight selected[J].Control and Decision，2008，23（1）：117-120.

[7]韓?錕，張?赫.基于鴿群優(yōu)化改進(jìn)的粒子濾波算法[J].傳感器與微系統(tǒng)，2018，37（11）：139-144.

HAN Kun，ZHANG He.Improved PF algorithm based on PIO[J].Sensors and Microsystems，2018，37（11）：139-144.

[8]梁?楠，岳鵬飛，喬彥超.基于粒子群優(yōu)化粒子濾波的目標(biāo)跟蹤方法[J].河南科學(xué)，2015，33（7）：1095-1099.

LIANG Nan，YUE Peng?fei，QIAO Yan?chao.Target tracking based on particle filter and particle swarm optimization[J].Henan Science，2015，33（7）：1095-1099.

[9]白曉波，邵景峰，田建剛.改進(jìn)的煙花算法優(yōu)化粒子濾波研究[J].計(jì)算機(jī)科學(xué)與探索，2018，12（11）：1827-1842.

BAI Xiao?bo，SHAO Jing?feng，TIAN Jian?gang.Research on optimizing particle filter based on improved fireworks algorithm[J].Computer Science and Exploration，2018，12（11）：1827-1842.

[10]陳志敏，吳盤龍，薄煜明，等.基于自控蝙蝠算法智能優(yōu)化粒子濾波的機(jī)動(dòng)目標(biāo)跟蹤方法[J].電子學(xué)報(bào)，2018，46（4）：886-893.

CHEN Zhi?min，WU Pan?long，BO Yu?ming，et al.Adaptive control bat algorithm intelligent optimization particle filter for maneuvering target tracking[J].Electronic Journal，2018，46（4）：886-893.

[11]田夢(mèng)楚，薄煜明，陳志敏，等.螢火蟲算法智能優(yōu)化粒子濾波[J].自動(dòng)化學(xué)報(bào)，2016，42（1）：89-97.

TIAN Meng?chu，BO Yu?ming，CHEN Zhi?min，et al.Firefly algorithm intelligence optimized particle filter[J].Journal of Automation，2016，42（1）：89-97.

[12]劉云濤.基于蝴蝶優(yōu)化的粒子濾波算法[J].信息技術(shù)與網(wǎng)絡(luò)安全，2018，37（7）：37-41.

LIU Yun?tao.Optimizing particle filter algorithm using butterfly algorithm[J].Information Technology and Network Security，2018，37（7）：37-41.

[13]王航星，潘?巍.基于自適應(yīng)吸引半徑的螢火蟲算法的粒子濾波[J/OL].計(jì)算機(jī)應(yīng)用研究，1-8[2018-12-20].

http：//kns.cnki.net/kcms/detail/51.1196.TP.20181009.1410.024.html.

WANG Hang?xing，PAN Wei.Particle filter based onfirefly algorithm with adaptive attraction radius[J/OL].Application Research of Computers：1-8[2018-12-20].

http：//kns.cnki.net/kcms/detail/51.1196.TP.20181009.1410.024.html.

[14]Aroras，Singhs.Butterfly algorithm with Lèvy Flights for global optimization[C]//International Conference on Signal Processing，Computing and Control.IEEE，2016：220-224.

[15]CalvetL E，Czellar V.Accurate methods for approximate bayesian computation filtering[J].Financial Econometrics，2015，13（4）：798-838.