改進的蝴蝶算法優化粒子濾波算法研究*

杜先君 韓曉礦

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

1 引言

在許多實際工程系統中，如目標跟蹤、無線電通信、工業故障診斷和計算機視覺系統，物理模型通常是非線性的［1～2］。粒子濾波（PF）是一種基于蒙特卡羅方法的遞推貝葉斯濾波算法，被認為是非線性非高斯狀態估計的有用的工具之一［3］。近年來，PF在許多領域得到了廣泛的應用［4］。然而，PF中粒子的貧化問題，降低了算法的性能［5］。粒子貧化問題是由于重采樣過程不合理導致粒子多樣性的匱乏。重采樣過程中，高質量的粒子會被保留，而低質量的粒子會被舍棄［6］。雖然低質量粒子對狀態估計的影響較小，但仍含有有用的粒子狀態信息。因此，粒子的多樣性喪失問題使得算法的性能大大降低。

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

近年來，集群優化算法的出現，為解決PF的粒子貧化問題打開了一扇新的大門［9］。在本文中，使用改進的蝴蝶優化算法（HBOA）來優化PF的重采樣過程，提高PF算法的狀態估計精度，解決PF算法的粒子貧化問題。

2 粒子濾波算法

粒子濾波算法是一種遞歸濾波算法，通過一組具有權重的隨機樣本來表示隨機事件的后驗概率，從含有噪聲或不完整的觀測序列，估計出系統的狀態。

非線性系統的狀態空間模型表示為

設狀態初始概率密度函數為p(x0|y0)=p(x0)，則狀態預測方程為

狀態更新方程為

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

權值公式為

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

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

概率密度更新公式為

狀態估計為

3 改進的蝴蝶優化算法

3.1 蝴蝶優化算法

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

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

1）所有的蝴蝶都可以散發能吸引其他個體的香味。

2）每只蝴蝶有兩種運動方式：隨機飛行或者朝向香味強度最高的蝴蝶飛行。

3）蝴蝶的刺激強度由目標函數決定。

在BOA中，每個蝴蝶個體都有著獨特的香味和個體感知能力，體現出BOA算法與其他智能優化算法的不同。蝴蝶個體散發的香味強度數學公式如下：

其中，f為感知到的香味大小，即蝴蝶感知香味的強弱；c為感官因子，通常取0.01；I為刺激強度，與適應度值有關；a為依賴于形態的指數，通常取0.1。說明蝴蝶對香味的吸收程度不同。

在算法的初始階段，隨機產生蝴蝶的位置，由式（10）計算蝴蝶在各自為位置產生的香味，然后算法進入全局尋優和局部尋優階段。在全局尋優階段，蝴蝶個體朝向香味最強的蝴蝶g*飛行，可以表示為

局部尋優階段可以表示為

其中，xj和xk是從尋優空間中選取的第j和第k個蝴蝶。r是［0，1］之間的隨機數。

通常蝴蝶尋找食物可以在局部和全局范圍內發生，可通過設置切換概率p來決定它的飛行方式，通常取為0.8。

3.2 蝴蝶優化算法的改進

針對標準BOA算法存在的依賴初始種群、容易誤入局部最優和后期尋優速度低等問題，本文從兩個方面對蝴蝶算法進行了改進。首先通過引入對立學習策略對蝴蝶種群進行優化處理；然后通過引入自適應權重因子來調節蝴蝶算法的全局尋優與局部尋優過程，提高它的尋優性能。基于以上兩種策略，本文提出了混合蝴蝶優化算法（Hybrid BOA，HBOA）。

1）對立學習策略初始化種群

基本的BOA算法在尋優前期采用隨機化的方法產生蝴蝶個體，使得蝴蝶的初始種群不具有全局最優的信息。對于蝴蝶優化算法而言，其尋優的基本策略為將前代產生的優秀個體保留到下一代中，循環地進行優中選優，最終得到最優個體。若種群中優秀蝴蝶個體較少，則會影響算法的快速性和準確性。因此本文將對立學習策略應用到蝴蝶種群的初始化進程中，提高算法的尋優性能。

對立學習（opposition-based learning，OBL）是由學者Tizhoosh在2005年首次提出的概念［11］。其主要思想是在一定的空間內，對當前的可行解產生對應的對立解，然后同時對可行解和對應的對立解進行評估，挑選之中的高質量個體代替當前的可行解。

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

由定義可對蝴蝶初始種群進行對立學習策略處理。

（1）在優化空間中，隨機初始化N個蝴蝶的位置，N為蝴蝶個體數量。

（2）產生N個蝴蝶的對立個體，表示為。

（3）將兩個種群進行合并，并求取個體適應度值，對其排序并取最優的前N個個體作為初始化種群。

2）自適應慣性權重

慣性權重最早是由Shi在1998年提出的，用來調節優化算法的全局尋優和局部尋優能力［12］。當慣性權重較大時，算法的全局尋優能力較強，使得算法能夠尋找新的未知區域，增加解的多種可能性；當慣性權重較小時，算法具有較強的局部尋優能力，使得搜索精度變強。該策略已被許多學者用于改進群體優化算法。

受此啟發，本文將慣性權重應用到BOA的全局尋優中，提高算法的尋優性能。自適應慣性權重隨著算法循環次數的上升呈現下降趨勢，其設置如式（3）所示：

其中，ωmax為迭代初始階段的慣性權重，ωmin為迭代結束時的慣性權重，T為算法運行的最大迭代次數，t為當前運行的迭代次數。慣性權重ωmax取0.9，ωmin取0.5時，算法具有最佳的性能。

此時，算法的全局搜索可表示為

4 基于HBOA的PF

HBOA優化PF的思想是粒子作為初始的蝴蝶個體，通過目標函數分別計算蝴蝶個體的適應度值，得到蝴蝶個體的香味濃度，然后將香味濃度最高的蝴蝶個體選為最優值。通過選擇概率來確定蝴蝶個體進行全局尋優還是局部尋優。經過一定的迭代次數，使得蝴蝶種群向最優的位置靠近，最終取得全局最優值。這樣，粒子集會不斷的高似然區靠近，使得濾波算法性能得到提升。

設置蝴蝶個體的香味刺激強度表示為

式中，R為觀測噪聲的方差；Znew為最新觀測值；Zpred為預測的觀測值；Ii為刺激強度。

綜上，HBOA-PF步驟如下。

步驟1：參數初始化。設置HBOA的尋優代數max，設置蝴蝶個體數為N；設置切換概率P，設置濾波步數T。

步驟2：算法初始時，從先驗信息中采樣N個粒子作為算法的初始粒子。

步驟3：模擬HBOA算法，指導粒子移動。

1）使用對立學習方法處理蝴蝶樣本。

2）然后根據式（15）計算所有蝴蝶個體的刺激強度，由式（10）計算蝴蝶個體的香味濃度，選取香味濃度最強的最為全局最優解。

3）若轉換概率p>rand，則按式（14）進行全局尋優，更新蝴蝶位置，若轉換概率p

步驟4：滿足最大尋優次數時，結束優化，否則跳轉到2）中。

步驟5：計算粒子權值并歸一化。

步驟6：狀態估計：

步驟7：輸出濾波結果。

5 仿真實驗分析

為了驗證把本文提出算法的性能，將其與PF和BOAPF［13］相比較，本文選取測試模型的數學表達式如下：

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

5.1 狀態估計精度測試

1）當粒子數N=20，Q=10，仿真結果如圖1和圖2所示。

圖1 系統狀態估計（N=20，Q=10）

圖2 估計誤差絕對值（N=20，Q=10）

2）當粒子數N=100，Q=10時，仿真結果如圖3、圖4所示。

圖3 系統狀態估計（N=100，Q=10）

由圖1～4可知，隨著粒子個數的增加，三種算法的狀態估計結果都有顯著的改善，但本文算法的狀態估計精度更高，估計誤差更小。

5.2 粒子多樣性測試

選取粒子數N=100，Q=10，對k=10、k=25、k=50的粒子分布多樣性進行研究，仿真結果如圖5～7所示。

圖5 k=10時的粒子狀態分布圖

圖6 k=25時的粒子狀態分布圖

圖7 k=50時的粒子狀態分布圖

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

6 結語

本文提出了一種改進蝴蝶算法優化粒子濾波算法，通過加入對立學習策略和自適應權重策略，增加了種群的多樣性，提高了算法的狀態估計精度。選取非線性系統為仿真對象，對PF、BOAPF和本HBOA-PF進行對比，結果表明本文提出的算法狀態估計能力更強，精度更高，并選取k=10、k=25、k=50的粒子狀態分布進行測試，結果顯示本文算法的粒子多樣性更加豐富。