一种改进的蝴蝶算法优化粒子滤波算法

张威虎 郭明香 贺元恺 孙小婷 朱代先

摘 要：传统的粒子滤波算法在重采样期间丢弃小重量粒子，因此重要性权重落在极少数粒子上。这会导致采样粒子贫化、粒子多样性缺失以及需要大量粒子才能进行比较准确的状态估计等问题，针对这些问题，提出了一种改进的蝶式算法优化粒子滤波算法。首先，将最新时刻观测信息引入蝴蝶香味公式中，以提高滤波精度;其次，引入吸引半径参数来控制蝴蝶种群寻优的搜索范围，降低算法的复杂度，进而提高算法的实时性;最后，将改进的蝴蝶种群位置更新公式用于优化迭代更新。实验结果表明，与经典粒子滤波器和现有蝶形优化算法相比，改进算法具有更低的均方误差和运行时间。并且在粒子数较少的情况下，可以实现更准确的状态估计，并改善传统滤波器的粒子耗尽现象，保证了粒子多样性。

关键词：粒子滤波;粒子贫化;状态估计;蝴蝶算法;滤波精度

中图分类号：TP 391.4 文献标志码：A

DOI：10.13800/j.cnki.xakjdxxb.2019.0117文章编号：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]

是一种處理非线性、非高斯系统的滤波方法，在故障诊断、目标跟踪、信号处理、机器人定位以及航空航天等领域均有广泛的应用[2]。但是它的一个缺点就是粒子退化的问题，即经过多次迭代以后，重要性权重集中在非常少的粒子个体上，这会导致粒子匮乏，粒子多样性缺失等问题。针对这些问题，大量学者提出改进算法。Gordon等引入了“重采样思想”[3]，在算法中，多次复制权重大的粒子，抛弃权重小的粒子[4]，来缓解粒子权重退化问题[5]。但该方法又带来样本多样性缺失的问题，影响了滤波的准确性。张琪等提出了一种权值选择的粒子滤波算法[6]，根据粒子权重的大小，对粒子进行取舍，选择较好的粒子用于滤波，来增加样本的多样性，进而提高滤波的准确性。但是这些算法丢弃了部分粒子个体信息，不能从根本上解决粒子滤波的粒子退化问题。使用种群智能优化算法来优化粒子滤波已成为解决粒子退化问题的一个热点方向，即使用运动定律的生物学优化使得粒子分布更加合理。由于群智能算法优化的粒子滤波主要是通过迭代寻优来改变粒子个体分布的位置，进而改善粒子的分布，不对粒子的信息进行舍弃，因此可以从根本上解决粒子耗尽现象。许多国内外学者引入形式各异的粒子滤波算法和群智能算法[7-11]来解决粒子匮乏、提高精度等，但是存在容易陷入局部极小值、计算量大、实时性较差等问题。刘云涛提出的基于蝴蝶优化的粒子滤波算法[12]，利用蝴蝶的全局优化能力，有效地控制了粒子匮乏问题，但是在局部搜索，粒子间吸引时需要全部任意两个粒子之间交互运算，实时性较差。

针对上述问题，在王航星等基于自适应吸引半径的萤火虫优化粒子滤波[13]的启发下，提出一种改进的蝴蝶算法优化粒子滤波算法。首先，将当前时刻的最新观测值引入蝴蝶香味公式，然后，引入新的参数吸引半径来控制蝴蝶种群个体寻优的范围，最后，使用改进的蝴蝶种群位置更新公式进行迭代更新，将改进的算法与经典粒子滤波（PF）、蝴蝶优化的粒子滤波算法[12]（BAPF）进行了比较，此算法在改善粒子退化和滤波精度的同时，具有更低的误差和运行时间。

1 粒子滤波算法

假设此非线性系统模型为

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

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

式中 f（·）和h（·）分别为状态转移方程和观测方程;xt和zt为系统在t时刻的状态变量和观测值;wt和vt为2个独立的噪声，即过程噪声和观测噪声;ut为系统在t时刻的输入量。在此模型下，假设k-1时刻状态后验分布的粒子集为

{xit-1，wit-1}，相应的粒子滤波算法可参考文献[1]。

2 蝴蝶算法

蝴蝶算法（Butterfly Algorithm，BA）[14]是一种基于蝴蝶觅食行为的全局优化算法。算法的收敛精度和速度优于其它算法。它主要模仿蝴蝶种群寻找食物，每只蝴蝶都散发出一定浓度的香气，每只蝴蝶都会感受到周围其它蝴蝶的味道，并朝着那些散发更多香味的蝴蝶移动。蝴蝶的香味取决于3个因素：感知形态、刺激强度以及幂指数。用方程表示为

F=cIa式中 F为香气的浓度;c为感知形式;I为刺激强度;a为幂指数。

已知目标函数f（x），蝴蝶算法的步骤如下

1）初始化蝴蝶种群，并通过目标函数f（xi）确定每只蝴蝶xi的刺激强度Ii;

2）计算蝴蝶种群的个体适应度值，找到最佳位置的蝴蝶;

3）计算蝴蝶散发的香味。为减少外界环境因素的影响，随机数P用于确定蝴蝶的搜索方法是执行局部搜索还是全局搜索;

4）全局搜索，低香味的蝴蝶个体飞向全局适应度最高的蝴蝶，全局搜索表示为

式中 xit为第i只蝴蝶在第t次迭代的解向量;g*为当前所有蝴蝶中的最优解。

5）局部搜索，蝴蝶个体进行Lévy随机飞行。局部搜索可以表示为

式中 xit，xjt，xkt分别为第i只、第j只、第k只蝴蝶在第t次迭代的解向量;xjt， xkt为随机个体。

为了避免蝴蝶进入局部最优，Lévy飞行被引入到算法中

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

3 改进算法

将蝴蝶算法引入粒子滤波算法，其思想是将粒子滤波器中的粒子视为蝴蝶群体中的个体，并且蝴蝶被彼此之间的香味所吸引，算法中的个体通过迭代将其位置向适应度最高的蝴蝶移动，类似于粒子滤波中的粒子不断接近实际系统状态的粒子的后验概率分布，而蝴蝶算法中适应度的最高值，可视为粒子滤波中权重最大的粒子最可能处于真实的后验概率分布。

如果直接将蝴蝶算法引入粒子滤波，会造成信息丢失、运算复杂等问题，因此，文中引入蝴蝶算法并做如下修改

传统的算法中，由于选取次优的重要性概率密度函数，丢弃了最新时刻的观测值，导致算法的准确性低下等问题。文中引入粒子滤波中当前时刻的观测值，定义蝴蝶算法的刺激强度公式为

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

式中 R为观测噪声的方差;Znew为最新观测值;Zpred为预测的观测值; Ii为刺激强度。

刺激强度最终反映蝴蝶个体香味的大小，相对于原始的公式而言，改进后的公式利用每个时刻每个粒子自身的观测值与预测值之间的差值平方来表示粒子每个时刻的刺激强度，不再需要将全部粒子与最优粒子进行比较计算，减少了算法在迭代寻优过程中的计算量。同时，通过加入粒子观测值信息的策略，将算法预测值与观测值的差值实时地反映在刺激强度中，有效地提高了算法的滤波精度。

3.1 引入自适应吸引半径参数

蝴蝶算法的全局优化能力很强，但随着个体数量的增加，时间复杂度会急剧增加。因此，文中设计一个新的参数——吸引半径，吸引半径的作用是用来限制蝴蝶个体间相互吸引的吸引范围和粒子数目。香味浓度的大小决定了吸引半径的大小，香味越大，粒子吸引半径越大。

如图1所示，a，b，c分别为香味F（a），F（b），F（c）的3只蝴蝶個体，吸引半径为

rb>rc>ra.对于蝴蝶b，c，由rb>rbc，即蝴蝶c在蝴蝶b的吸引范围内，所以蝴蝶c会被蝴蝶b吸引并更新位置;但对于蝴蝶a，尽管其香味最小，但由于它不在蝴蝶个体b，c的吸引范围内，便不会被b，c吸引，位置不更新。因此，对于两只香味不同的蝴蝶，只有当蝴蝶间距离小于较香蝴蝶的吸引半径时才会发生位置更新，否则不更新。

根据以上分析，定义吸引半径计算公式为

r=0.3Fi（7）

式中 r为相对吸引半径;Fi为种群个体的香味值。引入参数后，粒子间的相互吸引，不再需要将每一个粒子与其他粒子之间比较，而是只需要将在吸引半径内的粒子进行香味比较，同时更新粒子位置，引入参数后的算法，提高准确性，减少错误率和运行时间。

3.2 位置更新公式

蝴蝶种群中的个体在相互吸引中更新位置，从而不断地向香味更高的区域靠拢。文中，将位置更新公式设置为

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

式中 xit+1为个体i在t+1时刻的解向量;xit，xjt为个体i，j在t时刻的解向量;Lévy为随机飞行;Fi为每只蝴蝶的香味。

综上，改进后算法如下

1）初始化。由先验概率p（x0）产生初始粒子群{xi0，i=，…，N}，所有粒子初始权重设置为1/N.设置初始化参数迭代次数t，粒子数目N，蝴蝶算法中各参数感知形态c，幂指数a等参数;

2）预测。根据式（1）计算t+1时刻粒子预测值;

3）初始化蝴蝶算法。将粒子滤波中的粒子视为蝴蝶群体中的蝴蝶。根据式（6）计算每只蝴蝶的刺激强度，根据式（2）计算每只蝴蝶的香味;

4）使用改进后的蝴蝶算法进行迭代优化。根据式（7）计算吸引半径r，计算xit，xjt两只蝴蝶之间的距离rij=（xi-xj）2.如果rij

5）更新权值并归一化;

6）重采样及状态输出。

4 实验结果及分析

实验的硬件环境为台式电脑（Intel Core i 5处理器、4GB内存），实验环境为MATLAB 2016b，

将文中算法与传统粒子滤波算法（PF）、现有蝴蝶优化算法[12]（BAPF）相比，本文采用的系统的状态方程和观测方程为

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）

此模型是一个典型的非线性、非高斯系统模型，算法中，取w（t）为服从均匀分布的噪声;v（t）为服从（1，t）高斯分布的噪声。各滤波算法的性能用参数均方根误差

ERMSE来衡量。公式表示为

ERMSE=

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

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

从图2～4可以看出，改进后算法的状态值预估精度和误差率都得到了提高，这是因为改进算法在PF的基础上，引入蝴蝶寻优算法，不存在对粒子进行舍弃，它可以从根本上改善粒子匮乏问题，使粒子分布更加合理。

由于实验会存在噪声因素，为提高数据的准确性，本实验数据是在大量实验的基础上，取其平均值做一对比。从表中可以看出，当N逐渐增加，这3种算法的ERMSE值均减小，这与粒子滤波理论一致。文中算法与经典粒子滤波，BAPF算法相比，在保证算法精度的基础上，均方误差和运行时间上也都有所改善，效果均优于其他算法，这是因为本算法引入了参数吸引半径，大大简化了程序的运行时间，蝴蝶算法由于引进了Lévy随机飞行，它避免了粒子陷入局部最优的问题，提高了算法的准确性。当N=20，50时，在少量粒子情况下，可以实现更精确的滤波精度，它能从根本上解决粒子滤波匮乏的现象，改善粒子的多样性。

5 结 论

1）引入蝴蝶算法优化粒子滤波，使得远离真实状态的粒子向高似然区域移动，从根本上解决了粒子退化的问题，提高了算法的准确性;

2）引入吸引半径参数，控制粒子的吸引范围，大大缩短程序的运行时间，在保证精度的基础上，降低了误差和运行时间;

3）此算法能在粒子数量少的情况下保证滤波精度，还缩短了运行时间，提高实时性，因此具有实用价值。后续重点研究将改进算法应用到移动机器人SLAM中。

参考文献（References）：

[1] 王法胜，鲁明羽，赵清杰，等.粒子滤波算法[J].计算机学报，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].兰州理工大学学报，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]史卓瑛.面向空曠场景基子移动设备的室内定位与导航系统[D].杭州：浙江大学，2018.

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

[6]张 琪，胡昌华，乔玉坤.基于权值选择的粒子滤波研究[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]韩 锟，张 赫.基于鸽群优化改进的粒子滤波算法[J].传感器与微系统，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]梁 楠，岳鵬飞，乔彦超.基于粒子群优化粒子滤波的目标跟踪方法[J].河南科学，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].计算机科学与探索，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]陈志敏，吴盘龙，薄煜明，等.基于自控蝙蝠算法智能优化粒子滤波的机动目标跟踪方法[J].电子学报，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]田梦楚，薄煜明，陈志敏，等.萤火虫算法智能优化粒子滤波[J].自动化学报，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]刘云涛.基于蝴蝶优化的粒子滤波算法[J].信息技术与网络安全，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]王航星，潘 巍.基于自适应吸引半径的萤火虫算法的粒子滤波[J/OL].计算机应用研究，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.