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

杜先君 韓曉礦

（蘭州理工大學(xué)電氣工程與信息工程學(xué)院 蘭州 730050）

1 引言

在許多實(shí)際工程系統(tǒng)中，如目標(biāo)跟蹤、無(wú)線電通信、工業(yè)故障診斷和計(jì)算機(jī)視覺(jué)系統(tǒng)，物理模型通常是非線性的［1～2］。粒子濾波（PF）是一種基于蒙特卡羅方法的遞推貝葉斯濾波算法，被認(rèn)為是非線性非高斯?fàn)顟B(tài)估計(jì)的有用的工具之一［3］。近年來(lái)，PF在許多領(lǐng)域得到了廣泛的應(yīng)用［4］。然而，PF中粒子的貧化問(wèn)題，降低了算法的性能［5］。粒子貧化問(wèn)題是由于重采樣過(guò)程不合理導(dǎo)致粒子多樣性的匱乏。重采樣過(guò)程中，高質(zhì)量的粒子會(huì)被保留，而低質(zhì)量的粒子會(huì)被舍棄［6］。雖然低質(zhì)量粒子對(duì)狀態(tài)估計(jì)的影響較小，但仍含有有用的粒子狀態(tài)信息。因此，粒子的多樣性喪失問(wèn)題使得算法的性能大大降低。

許多學(xué)者在降低樣品貧化的影響方面做了大量的工作。為了解決重采樣步驟中遇到的粒子貧化問(wèn)題，文獻(xiàn)［7］在輔助粒子濾波器（APF）在中引入粒子索引作為重采樣的附加變量。文獻(xiàn)［8］中推導(dǎo)出一種精細(xì)的重采樣算法，該算法分階段比較粒子的權(quán)值，并基于擬蒙特卡洛方法構(gòu)造新的粒子。上述方法著重于改進(jìn)粒子濾波重采樣過(guò)程，然而，樣本貧化的問(wèn)題并未完全解決。

近年來(lái)，集群優(yōu)化算法的出現(xiàn)，為解決PF的粒子貧化問(wèn)題打開(kāi)了一扇新的大門［9］。在本文中，使用改進(jìn)的蝴蝶優(yōu)化算法（HBOA）來(lái)優(yōu)化PF的重采樣過(guò)程，提高PF算法的狀態(tài)估計(jì)精度，解決PF算法的粒子貧化問(wèn)題。

2 粒子濾波算法

粒子濾波算法是一種遞歸濾波算法，通過(guò)一組具有權(quán)重的隨機(jī)樣本來(lái)表示隨機(jī)事件的后驗(yàn)概率，從含有噪聲或不完整的觀測(cè)序列，估計(jì)出系統(tǒng)的狀態(tài)。

非線性系統(tǒng)的狀態(tài)空間模型表示為

設(shè)狀態(tài)初始概率密度函數(shù)為p(x0|y0)=p(x0)，則狀態(tài)預(yù)測(cè)方程為

狀態(tài)更新方程為

設(shè)重要性函數(shù)為q(x0;k|y1:k)，將其改寫為

權(quán)值公式為

從p(xk-1|y1:k-1)中采樣N個(gè)樣本點(diǎn)，則概率密度為

其中，δ(·)為狄拉克函數(shù)。

概率密度更新公式為

狀態(tài)估計(jì)為

3 改進(jìn)的蝴蝶優(yōu)化算法

3.1 蝴蝶優(yōu)化算法

Arora［10］提出了一種新的自然啟發(fā)式算法—蝴蝶優(yōu)化算法（Butterfly Optimization Algorithm，BOA）。在BOA中，每一只蝴蝶都會(huì)產(chǎn)生與蝴蝶的適應(yīng)度相關(guān)的香味。當(dāng)蝴蝶從一個(gè)地方移動(dòng)到另一個(gè)地方時(shí)，它的適應(yīng)能力也會(huì)隨之改變。這種香味會(huì)向蝴蝶的四周分散出去，使得其余的蝴蝶可以通過(guò)感官嗅到它。這樣，蝴蝶群中的蝴蝶通過(guò)散發(fā)各自的香味來(lái)共享各自間的信息。當(dāng)一只蝴蝶能夠感覺(jué)到任何其他蝴蝶的香味時(shí)，它就會(huì)向其他蝴蝶移動(dòng)，進(jìn)行全局搜索。當(dāng)一只蝴蝶感覺(jué)不到香味時(shí)，它就會(huì)在空間中自由飛行，進(jìn)行局部搜索。

由上述敘述，可將蝴蝶的行為理想化如下特征。

1）所有的蝴蝶都可以散發(fā)能吸引其他個(gè)體的香味。

2）每只蝴蝶有兩種運(yùn)動(dòng)方式：隨機(jī)飛行或者朝向香味強(qiáng)度最高的蝴蝶飛行。

3）蝴蝶的刺激強(qiáng)度由目標(biāo)函數(shù)決定。

在BOA中，每個(gè)蝴蝶個(gè)體都有著獨(dú)特的香味和個(gè)體感知能力，體現(xiàn)出BOA算法與其他智能優(yōu)化算法的不同。蝴蝶個(gè)體散發(fā)的香味強(qiáng)度數(shù)學(xué)公式如下：

其中，f為感知到的香味大小，即蝴蝶感知香味的強(qiáng)弱；c為感官因子，通常取0.01；I為刺激強(qiáng)度，與適應(yīng)度值有關(guān)；a為依賴于形態(tài)的指數(shù)，通常取0.1。說(shuō)明蝴蝶對(duì)香味的吸收程度不同。

在算法的初始階段，隨機(jī)產(chǎn)生蝴蝶的位置，由式（10）計(jì)算蝴蝶在各自為位置產(chǎn)生的香味，然后算法進(jìn)入全局尋優(yōu)和局部尋優(yōu)階段。在全局尋優(yōu)階段，蝴蝶個(gè)體朝向香味最強(qiáng)的蝴蝶g*飛行，可以表示為

局部尋優(yōu)階段可以表示為

其中，xj和xk是從尋優(yōu)空間中選取的第j和第k個(gè)蝴蝶。r是［0，1］之間的隨機(jī)數(shù)。

通常蝴蝶尋找食物可以在局部和全局范圍內(nèi)發(fā)生，可通過(guò)設(shè)置切換概率p來(lái)決定它的飛行方式，通常取為0.8。

3.2 蝴蝶優(yōu)化算法的改進(jìn)

針對(duì)標(biāo)準(zhǔn)BOA算法存在的依賴初始種群、容易誤入局部最優(yōu)和后期尋優(yōu)速度低等問(wèn)題，本文從兩個(gè)方面對(duì)蝴蝶算法進(jìn)行了改進(jìn)。首先通過(guò)引入對(duì)立學(xué)習(xí)策略對(duì)蝴蝶種群進(jìn)行優(yōu)化處理；然后通過(guò)引入自適應(yīng)權(quán)重因子來(lái)調(diào)節(jié)蝴蝶算法的全局尋優(yōu)與局部尋優(yōu)過(guò)程，提高它的尋優(yōu)性能?；谝陨蟽煞N策略，本文提出了混合蝴蝶優(yōu)化算法（Hybrid BOA，HBOA）。

1）對(duì)立學(xué)習(xí)策略初始化種群

基本的BOA算法在尋優(yōu)前期采用隨機(jī)化的方法產(chǎn)生蝴蝶個(gè)體，使得蝴蝶的初始種群不具有全局最優(yōu)的信息。對(duì)于蝴蝶優(yōu)化算法而言，其尋優(yōu)的基本策略為將前代產(chǎn)生的優(yōu)秀個(gè)體保留到下一代中，循環(huán)地進(jìn)行優(yōu)中選優(yōu)，最終得到最優(yōu)個(gè)體。若種群中優(yōu)秀蝴蝶個(gè)體較少，則會(huì)影響算法的快速性和準(zhǔn)確性。因此本文將對(duì)立學(xué)習(xí)策略應(yīng)用到蝴蝶種群的初始化進(jìn)程中，提高算法的尋優(yōu)性能。

對(duì)立學(xué)習(xí)（opposition-based learning，OBL）是由學(xué)者Tizhoosh在2005年首次提出的概念［11］。其主要思想是在一定的空間內(nèi)，對(duì)當(dāng)前的可行解產(chǎn)生對(duì)應(yīng)的對(duì)立解，然后同時(shí)對(duì)可行解和對(duì)應(yīng)的對(duì)立解進(jìn)行評(píng)估，挑選之中的高質(zhì)量個(gè)體代替當(dāng)前的可行解。

設(shè)在定義域[l，u]上存在數(shù)x，則數(shù)x的對(duì)立點(diǎn)為x′=l+u-x。將定義域擴(kuò)展到n維空間，設(shè)p=(x1，x2，…，xn)為n空間的一點(diǎn)，其中xi∈[li，ui]，i=1，2，…，n，則其對(duì)立點(diǎn)為，其中［11］。

由定義可對(duì)蝴蝶初始種群進(jìn)行對(duì)立學(xué)習(xí)策略處理。

（1）在優(yōu)化空間中，隨機(jī)初始化N個(gè)蝴蝶的位置，N為蝴蝶個(gè)體數(shù)量。

（2）產(chǎn)生N個(gè)蝴蝶的對(duì)立個(gè)體，表示為。

（3）將兩個(gè)種群進(jìn)行合并，并求取個(gè)體適應(yīng)度值，對(duì)其排序并取最優(yōu)的前N個(gè)個(gè)體作為初始化種群。

2）自適應(yīng)慣性權(quán)重

慣性權(quán)重最早是由Shi在1998年提出的，用來(lái)調(diào)節(jié)優(yōu)化算法的全局尋優(yōu)和局部尋優(yōu)能力［12］。當(dāng)慣性權(quán)重較大時(shí)，算法的全局尋優(yōu)能力較強(qiáng)，使得算法能夠?qū)ふ倚碌奈粗獏^(qū)域，增加解的多種可能性；當(dāng)慣性權(quán)重較小時(shí)，算法具有較強(qiáng)的局部尋優(yōu)能力，使得搜索精度變強(qiáng)。該策略已被許多學(xué)者用于改進(jìn)群體優(yōu)化算法。

受此啟發(fā)，本文將慣性權(quán)重應(yīng)用到BOA的全局尋優(yōu)中，提高算法的尋優(yōu)性能。自適應(yīng)慣性權(quán)重隨著算法循環(huán)次數(shù)的上升呈現(xiàn)下降趨勢(shì)，其設(shè)置如式（3）所示：

其中，ωmax為迭代初始階段的慣性權(quán)重，ωmin為迭代結(jié)束時(shí)的慣性權(quán)重，T為算法運(yùn)行的最大迭代次數(shù)，t為當(dāng)前運(yùn)行的迭代次數(shù)。慣性權(quán)重ωmax取0.9，ωmin取0.5時(shí)，算法具有最佳的性能。

此時(shí)，算法的全局搜索可表示為

4 基于HBOA的PF

HBOA優(yōu)化PF的思想是粒子作為初始的蝴蝶個(gè)體，通過(guò)目標(biāo)函數(shù)分別計(jì)算蝴蝶個(gè)體的適應(yīng)度值，得到蝴蝶個(gè)體的香味濃度，然后將香味濃度最高的蝴蝶個(gè)體選為最優(yōu)值。通過(guò)選擇概率來(lái)確定蝴蝶個(gè)體進(jìn)行全局尋優(yōu)還是局部尋優(yōu)。經(jīng)過(guò)一定的迭代次數(shù)，使得蝴蝶種群向最優(yōu)的位置靠近，最終取得全局最優(yōu)值。這樣，粒子集會(huì)不斷的高似然區(qū)靠近，使得濾波算法性能得到提升。

設(shè)置蝴蝶個(gè)體的香味刺激強(qiáng)度表示為

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

綜上，HBOA-PF步驟如下。

步驟1：參數(shù)初始化。設(shè)置HBOA的尋優(yōu)代數(shù)max，設(shè)置蝴蝶個(gè)體數(shù)為N；設(shè)置切換概率P，設(shè)置濾波步數(shù)T。

步驟2：算法初始時(shí)，從先驗(yàn)信息中采樣N個(gè)粒子作為算法的初始粒子。

步驟3：模擬HBOA算法，指導(dǎo)粒子移動(dòng)。

1）使用對(duì)立學(xué)習(xí)方法處理蝴蝶樣本。

2）然后根據(jù)式（15）計(jì)算所有蝴蝶個(gè)體的刺激強(qiáng)度，由式（10）計(jì)算蝴蝶個(gè)體的香味濃度，選取香味濃度最強(qiáng)的最為全局最優(yōu)解。

3）若轉(zhuǎn)換概率p>rand，則按式（14）進(jìn)行全局尋優(yōu)，更新蝴蝶位置，若轉(zhuǎn)換概率p

步驟4：滿足最大尋優(yōu)次數(shù)時(shí)，結(jié)束優(yōu)化，否則跳轉(zhuǎn)到2）中。

步驟5：計(jì)算粒子權(quán)值并歸一化。

步驟6：狀態(tài)估計(jì)：

步驟7：輸出濾波結(jié)果。

5 仿真實(shí)驗(yàn)分析

為了驗(yàn)證把本文提出算法的性能，將其與PF和BOAPF［13］相比較，本文選取測(cè)試模型的數(shù)學(xué)表達(dá)式如下：

式中，w(t)和v(t)為零均值高斯噪聲，設(shè)系統(tǒng)噪聲w(t)的方差為Q=10，測(cè)量噪聲v(t)的方差為R=1，仿真步長(zhǎng)T設(shè)置為60，初始化蝴蝶種群數(shù)量N=50，慣性權(quán)重ωmax取0.9，ωmin取0.5，感官因子c取0.01；形態(tài)指數(shù)取0.1。均方根誤差計(jì)算公式為

5.1 狀態(tài)估計(jì)精度測(cè)試

1）當(dāng)粒子數(shù)N=20，Q=10，仿真結(jié)果如圖1和圖2所示。

圖1 系統(tǒng)狀態(tài)估計(jì)（N=20，Q=10）

圖2 估計(jì)誤差絕對(duì)值（N=20，Q=10）

2）當(dāng)粒子數(shù)N=100，Q=10時(shí)，仿真結(jié)果如圖3、圖4所示。

圖3 系統(tǒng)狀態(tài)估計(jì)（N=100，Q=10）

由圖1～4可知，隨著粒子個(gè)數(shù)的增加，三種算法的狀態(tài)估計(jì)結(jié)果都有顯著的改善，但本文算法的狀態(tài)估計(jì)精度更高，估計(jì)誤差更小。

5.2 粒子多樣性測(cè)試

選取粒子數(shù)N=100，Q=10，對(duì)k=10、k=25、k=50的粒子分布多樣性進(jìn)行研究，仿真結(jié)果如圖5～7所示。

圖5 k=10時(shí)的粒子狀態(tài)分布圖

圖6 k=25時(shí)的粒子狀態(tài)分布圖

圖7 k=50時(shí)的粒子狀態(tài)分布圖

從圖5～7可以看出，相對(duì)于PF，BOAPF和HBOA-PF在粒子迭代過(guò)程中對(duì)粒子的多樣性都有改善，但HBOA-PF的對(duì)粒子的多樣性提升更加顯著。

6 結(jié)語(yǔ)

本文提出了一種改進(jìn)蝴蝶算法優(yōu)化粒子濾波算法，通過(guò)加入對(duì)立學(xué)習(xí)策略和自適應(yīng)權(quán)重策略，增加了種群的多樣性，提高了算法的狀態(tài)估計(jì)精度。選取非線性系統(tǒng)為仿真對(duì)象，對(duì)PF、BOAPF和本HBOA-PF進(jìn)行對(duì)比，結(jié)果表明本文提出的算法狀態(tài)估計(jì)能力更強(qiáng)，精度更高，并選取k=10、k=25、k=50的粒子狀態(tài)分布進(jìn)行測(cè)試，結(jié)果顯示本文算法的粒子多樣性更加豐富。