基于果蝇优化算法改进的粒子滤波及其在目标跟踪中的应用

韩锟 张赫

摘 要：针对粒子滤波算法重采样导致的样本贫化问题，提出一种基于果蝇优化思想的粒子滤波算法.该方法视粒子权值为个体适应度值，并将果蝇不断从低浓度的地方飞向高浓度的地方的觅食寻优过程引入到粒子滤波当中，驱使粒子不断向高似然区域移动，提高了粒子群的整体质量.为了解决标准果蝇优化算法易陷入早熟的问题，将遗传算法中的交叉、变异操作自适应地应用到果蝇优化算法寻优过程当中.首先通过交叉操作改善粒子分布，当果蝇优化算法陷入局部最优时，再采用柯西变异扰动，促使算法快速跳出局部极值并继续搜索全局极值.通过非线性模型仿真以及目标跟踪实验表明该算法有效提高了非线性系统状态估计精度，具有较好的稳定性，同时降低了状态估计所需的粒子数量.

关键词：粒子滤波；样本贫化；果蝇优化算法；非线性系统；状态估计

中图分类号：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

粒子滤波是一种用于求解后验概率的方法，它通过非参数化蒙特卡洛模拟方法实现递推贝叶斯滤波[1].由于粒子滤波摆脱了传统解决非线性滤波问题时，随机量必须满足高斯分布的制约条件[2]，使其能够在非线性、非高斯系统下，相较于基于卡尔曼滤波框架的滤波算法，展現出明显的优越性.目前粒子滤波在无线定位、金融与经济学、参数估计、目标跟踪[3-6]等领域，都具有非常广阔的应用前景.然而，传统的粒子滤波还存在着一些不足，需要加以改善，例如序列重要性采样会带来粒子退化问题，即经过若干次循环递推后，粒子集中绝大多数粒子权值变得很小，甚至接近于零，只有少数粒子具有非零权值，造成粒子集无法表达实际的后验概率分布[7].虽然通过重采样[8]复制权重较大粒子、删除低权值粒子能够在一定程度上抑制粒子退化问题，却在同时也破坏了粒子多样性，导致粒子出现贫化现象[9].

近年来，为了解决粒子滤波算法存在的这些问题，国内外学者提出了很多改进方法，主要是以优化重采样的角度来改进滤波精度.例如，Li等[10]提出确定性重采样，利用粒子空间信息和状态值进行重采样，避免盲目丢弃低权重的粒子，从而保证了粒子的多样性，但是对于权值较大的粒子，直接进行了权值平均，并没有有效利用它们所具有的信息.程水英等[11]提出在重采样前进行权值排序列、裂变繁殖、权值归一的预处理，以平滑权值差异使得更多的样本能够进行重采样，这样虽然能延迟贫化时间，但无法从根本上避免贫化.张光等[12]采用正则化方法，引入核密度函数和核带宽系数以连续形式计算状态后验概率，有效缓解粒子退化问题，但无法保证样本粒子都能近似表示后验概率，因而对非线性系统参数估计不能达到最优.

将群体智能优化算法与粒子滤波结合是目前粒子滤波发展的一个较新的思路[13].采用智能优化算法来避免粒子贫化问题，主要是将标准粒子滤波中的每个粒子看作生物群体的每个个体，通过模拟生物集群的运动规律来调整粒子的分布，使粒子群体向高似然区域移动，更加接近真实后验分布，由于其过程并未舍弃权重低的粒子，因而能够从根本上避免粒子贫化现象[14].目前，已经有多种基于群智能优化算法的粒子滤波被提出，例如，田梦楚等[14]提出基于萤火虫算法的粒子滤波，引入了萤火虫群体的优胜劣汰机制以及萤火虫个体的吸引和移动的行为，使粒子向高似然区域移动，从而提高估计精度.汪荣贵等[15]将自适应遗传算法应用到粒子滤波相，依据粒子的适应度值自适应确定对粒子进行遗传操作的概率，然后对选出的粒子实施交叉、变异操作来移动粒子，增加粒子多样性.Tian等[16]将人工鱼群算法和无迹粒子滤波结合，利用人工鱼群算法优化采样过程，克服样本贫化问题.

果蝇优化算法[17]由台湾学者潘文超博士于2011年提出，是通过模拟自然界果蝇觅食行为而推演出来的群智能优化算法，也是迄今为止所需调整参数最少、进化方程最为简单的群体智能优化算法之一[18].本文结合果蝇优化算法迭代寻优机制以及粒子滤波的特点，对果蝇优化算法寻优机制加以改进，引入自适应交叉和变异操作，保障粒子多样性，并将结合交叉、变异的果蝇优化算法到融入粒子滤波当中，提出基于改进的果蝇优化思 想的粒子滤波算法.通过模型仿真以及目标跟踪实验，表明本文所提算法在保证粒子多样性的同时也能够很好的提高状态估计精度与稳定性.

1 粒子滤波算法

2 果蝇优化算法（FOA）

果蝇优化算法是一种源于果蝇觅食行为推演出寻求全局优化的群体智能算法[17].FOA的仿生原理是将种群数量为N的果蝇个体映射为搜索空间中的N个可行解，整个迭代寻优以及搜索过程模拟成果蝇群体觅食过程.果蝇本身在感官知觉上优于其它物种，尤其是在嗅觉与视觉上，果蝇的嗅觉器官能够较好地搜集漂浮在空气中的各种气味，根据果蝇个体感知到的食物味道浓度的大小来衡量每个果蝇个体所处位置的优劣，味道浓度越大，则表明该果蝇位置距离食物越近.果蝇觅食的过程就是果蝇不断从浓度低的地方飞向浓度高的地方，飞近食物位置后亦可使用敏锐的视觉发现食物与同伴聚集的位置，且往该方向飞去，直到找到食物.

依据果蝇搜索食物的特征行为，果蝇优化算法基本流程主要由以下3个步骤构成：

1） 种群初始化：确定果蝇群体数量N、最大迭代次数m以及初始化果蝇个体觅食位置X0，Y0.

2） 觅食活动：果蝇群体从初始位置出发，利用嗅觉搜寻食物，每个个体的搜索方向与距离皆为设定范围的随机数.根据当前的位置Xi，Yi，计算每个果蝇适应度值fi（味道浓度值），找出其中适应度值最大（或最小）的个体，然后群体利用视觉向该个体位置飞去.

3） 种群位置更新：每一次迭代过程即每一次从当前最佳适应值位置飞出到下一最佳位置的过程，若下一次最佳适应度值大于前一次最佳适应度值，则群体更新最佳适应度值点为新的觅食位置X0，Y0，所有个体向该位置飞去，然后再飞出继续搜索.如此反复，直到达到最大迭代次数或设定精度为止.

3 果蝇优化粒子滤波（FOAPF）

3.1 整体改进原理

传统粒子滤波算法的重采样过程通过复制大权重粒子、删除小权值粒子来解决粒子匮乏现象，但经过多次迭代后，又会带来粒子贫化问题.

针对上述问题，本文将果蝇优化算法融入到粒子滤波中改善采样过程.算法具体思路如下：在标准粒子滤波过程中，当经过重要性采样得到N个粒子后，根据个体的位置以及设定的适应度函数计算每个粒子的适应度值，如果粒子集分布在真实状态附近，那么，粒子群中每个粒子的适应度值都很高；反之，如果粒子群中的适应度最优值很低，则说明粒子集没有分布在真实状态附近，此时，利用FOA算法对粒子分布进行优化，粒子不断向适应度值高的地方飞去，使得粒子不断向真实状态靠近，从而提高粒子群整体样本的质量.当粒子集的最优值达到设定的阈值ε时，则说明粒子集已经分布在真实状态附近，此时即可停止优化.

通过上述优化过程，驱使粒子集合不断向高似然区域靠近，从而解决粒子贫乏问题.然而，果蝇优化算法也存在着一些不可避免的问题，即在整个寻优过程中果蝇只向当前味道浓度最高的个体飞去，所有粒子分布随机在最优值附近，无法保证粒子多样性.而且如果该个体不是全局最优值，极易使算法陷入局部最优，从而降低收敛速度和收敛精度，带来早熟收敛的问题.因而直接将果蝇优化算法融入到粒子滤波中并不一定会得到理想的效果，需要对果蝇优化过程进行适当的改进，采用一种机制，让算法在出现早熟收敛时，能够跳出局部最优，并进入解空间的其它区域继续进行搜索，直到找出全局最優解[19].本文采取在果蝇优化算法中引入自适应交叉算子、自适应变异机制，首先对粒子群体进行自适应交叉操作，增加粒子多样性，可以在在一定程度减小陷入局部最优几率.然后判断算法是否陷入早熟收敛，若是，则复制一些当前最优粒子，对这些粒子进行柯西变异操作，可以促使算法跳出局部最优，继续搜索全局极值.

3.2 适应度函数设计

从图1～6可以看出，本文所提基于改进的果蝇优化算法的粒子滤波（FOAPF），相较于标准PF以及GAPF，状态预测曲线与实际状态相似程度最高，其估计值更接近真实值，这是因为FOAPF在PF的基础上，通过对重要性采样后的粒子进行引入交叉、变异操作的果蝇迭代寻优，使粒子向高似然区域运动的同时，保证了样本多样性，从而提高粒子分布的合理性.表1、表2中数据为每种算法独立运行50次后的均方根误差平均值以及方差，从中可以看出，3种算法随着粒子数的增加，均方根误差以及方差大体上皆呈现减小的趋势，这与粒子滤波的粒子数越多则估计精度越高的理论是相符的.而在三种算法中，FOAPF的均方根误差以及方差最低，且是唯一一个在粒子数为100时两者皆小于1的，当粒子数为50时，其误差值也比粒子数为100的PF算法低，与GAPF也只有不到0.2的差距，说明FOAPF能够用较少的粒子达到所需的精度.而均方根误差方差体现算法预测的稳定性，FOAPF也是最低的，当粒子数越多时更为明显.综上分析，FOAPF具有更好的估计精度以及稳定性.

4.2 粒子多樣性测试

为测试FOAPF滤波时的粒子多样性，设置粒子数为100，取PF和FOAPF滤波器在迭代过程第20和45步时的粒子分布情况，如图7～8所示，可以看出，FOAPF与标准PF相比，具有更宽的粒子分布，除了在高似然区域存在较多粒子，周边区域也分布着部分粒子，说明FOAPF在预测精度优于PF的同时，粒子多样性并没有降低，这是因为对果蝇寻优过程进行了自适应的交叉与变异操作，保证了粒子多样性不下降，而且本文并没有进行重采样操作，也能够有效地避免粒子贫化现象的出现.

5 目标跟踪实验

目标跟踪在计算机视觉领域中有着广泛的应用前景和商业价值，包括智能监控、人机交互、视频检索等.快速移动的目标往往具有非线性、非高斯的特点，跟踪要求有较高的实时性、鲁棒性.近年来，基于相关滤波[21]的判别式跟踪方法以其优越的跟踪速度、出色的跟踪性能及高效的鲁棒性得到了广泛关注和应用.为检验本文所提算法在目标跟踪应用中的实际效果，将本文所提方法与相关滤波算法分别应用到视频目标跟踪当中，并对结果进行分析.

6 结 论

1）本文算法FOAPF通过单变量非静态增长模型进行了仿真，粒子数为100时，实验结果均方根误差均值为0.729 5，均方根误差方差为0.454 4，表明本文算法精度、稳定性均高于标准粒子滤波和基于遗传算法的粒子滤波算法，粒子分布图进一步说明本文算法有效保证了粒子的多样性.

2）将FOAPF算法运用到视频目标跟踪实验中，与相关滤波算法跟踪结果进行比较，实验结果表明本文算法对目标快速移动以及被遮挡的情况都具有良好的跟踪效果.

参考文献

[1]

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

[2] 王法胜， 鲁明羽， 赵清杰，等.粒子滤波算法[J].计算机学报， 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] 李天成，范红旗，孙树栋.粒子滤波理论、方法及其在多目标跟踪中的应用[J].自动化学报， 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] 朱志宇. 粒子滤波算法及其应用[M].北京：科学出版社，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].电子学报，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]. 探测与控制学报，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]田梦楚，薄煜明，陈志敏，等.萤火虫算法智能优化粒子滤波[J].自动化学报，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]汪荣贵，李孟敏，吴昊，等.一种新型的基于自适应遗传算法的粒子滤波算法[J].中国科学技术大学学报，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]韓虎. 果蝇优化算法的分析[J]. 计算机系统应用，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]吕振肃，侯志荣. 自适应变异的粒子群优化算法[J]. 电子学报，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]韩俊英，刘成忠. 自适应变异的果蝇优化算法[J]. 计算机应用研究，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.