一种混合蛙跳算法优化的粒子滤波方法

摘要：粒子滤波方法是一种适合于非线性、非高斯系统状态的滤波方法，在目标跟踪等领域有着广泛应用。但传统粒子滤波方法的粒子之间缺乏交互性与合作意识，很可能在寻优过程中陷入局部极值。针对这一问题，提出一种混合蛙跳算法优化的粒子滤波方法。混合蛙跳算法速度快，全局搜索能力强，可以在局部间进行信息传递，使算法跳出局部极值。因此采用混合蛙跳算法优化传统粒子滤波方法，可以构建多种粒子子集的分布体系，把原本不具备智能行为的粒子分别赋予分群、选择、信息交互和进化等机制，使粒子群体表现出智能行为，从而使寻优搜索向着全局最优方向进行。最后采用仿真实验进行比较，优化后的方法在性能上明显优于传统粒子滤波方法，取得了较好效果。

关键词：粒子滤波算法 混合蛙跳算法 交互性

中图分类号：TP18 文献标识码：A 文章编号：1007-9416（2013）11-0106-04

1 引言

粒子滤波方法是1993年由Gordon等提出的一种新的基于SIS的非线性滤波方法[1]，其核心思想是用一组称作粒子的加权随机样本来逼近所要估计状态的后验概率密度函数[2]，主要应用于目标跟踪[3-4]，组合导航[5]，金融数据分析[6]，计算机视觉[7]等领域。

混合蛙跳算法[8-10]是2003年由Eusuff和Lansey提出的一种新型的后启发式群体智能优化算法，它寻优能力强，参数少，计算速度快，它概念简单，参数少，全局寻优能力强[11]。目前国内外一些学者将混合蛙跳算法广泛应用于模式识别[12]，函数的优化[13-16]，求解有约束优化问题[17]，旅行商问题[18]等领域。

本文用混合蛙跳算法优化粒子滤波方法，构建多种粒子子集的分布体系，每个蛙群对应一个范围空间，在此空间中分布粒子子集，每个蛙群的空间就是粒子子集搜索范围，根据蛙群的行为状态，自适应建立粒子的搜索空间，取得了较好的效果。

2 粒子滤波算法分析

2.1 动态系统模型

3 混合蛙跳算法优化的粒子滤波方法

3.1 混合蛙跳算法基本原理

混合蛙跳算法的实现机理是通过模拟青蛙群体在觅食过程中所体现出来的协同行为来完成对问题的求解。在一定区域内，若干只结构相同的青蛙组成一个种群，每只青蛙被定义为问题的一个解。整个种群又分为不同的子群（称为memeplex），每个子群都有自己的思想，执行局部搜索策略。在每一个memeplex中，每只青蛙也都有自己的思想，同时还受其它青蛙思想的影响，并通过memetic进化来调整位置。经过一定数量的进化后，不同子群体间的青蛙通过跳跃过程来传递信息。这种局部进化和跳跃过程不断相间进行，直到满足收敛的结束条件为止。

具体来讲，首先随机初始化一组解来组成初始种群。

3.2 混合蛙跳算法优化的粒子滤波方法SFLA-PF

混合蛙跳算法最主要的特点[25]是全局信息交换和局部深度搜索策略的平衡操作，这使得算法能够跳出局部极值， 向着全局最优的方向进行。用混合蛙跳算法优化粒子滤波方法，有利于粒子朝着高似然区域移动。即把每一个不具备智能行为的粒子都看作觅食过程中的青蛙，在进化、跳跃的过程中将粒子赋予智能的行为，使其能够分子群进化，对最优解、最差解可以进行选择和淘汰，粒子之间具有交互性，可以进行信息传递，从而使进化过程在不断自我修正的基础上进行。

具体来讲：

（1）分群机制

执行分群操作，将N个粒子分为m群。将粒子按照适应度值降序排列，第一个粒子进入第一个子群，第二个粒子进入第二个子群，一直分配下去，直到第m个粒子进入第m个子群。随后，第m+1个粒子又进入第一个子群，第m+2个粒子进入第二个子群……如此循环分配下去。

（2）选择机制

记录全局最优个体。

记录每一个子群中的局部最优解和局部最差解。

（3）信息交互机制

根据最优解的信息来调整最差解的位置。调整之后，如果能够产生一个更好的解， 那么就用新的解取代原来的解，否则，用代替， 执行操作f （，），若能产生一个更好的解， 则取代原来的解，否则，随机生成一个新解取代原来的最差解。

（4）进化机制

为了比较算法的性能，本文中的实验均采用以上相同的非线性仿真实例。

采用50次蒙特卡罗仿真，取PF、SLFA-PF算法的粒子数N=90， 其中混合蛙跳算法参数种群数M=3，每个memeplex中允许的最大进化次数L=30。仿真结果如（图4）所示。其中X轴数据（time step）表示蒙特卡洛仿真次数，Y轴数据（state）分别表示真实状态和两种方法的估计状态。

如（图4）和（表1）所示，在粒子数N=90的情况下，混合蛙跳算法优化的粒子滤波方法（SFLA-PF）在算法性能上相对于传统粒子滤波（PF）算法有明显优势，算法方差有了明显降低，SFLA-PF算法的估计值要比PF算法的估计值更接近真实状态，并且由于SFLA-PF算法的一大特点就是局部优化，因此尽管引入智能机制，算法时间并无明显提高，几乎与原有算法持平。由此可见，SFLA-PF算法充分发挥了自身的优势，有利于粒子向着全局最优的方向进行，很大程度上降低了算法的方差RMSE，算法取得了良好的效果。

参考文献

[1]刘伟亭，戴晓强，朱志宇.非高斯条件下基于无味粒子滤波器的目标跟踪[J].江苏科技大学学报.2007，21（2）：45-48.陈真勇，唐龙，唐泽圣，熊璋.以鲁棒性为目标的数字多水印研究[J].计算机学报，2006，29（11）.

[2]王京玲，叶龙，张勤.基于遗传算法的粒子滤波器在目标跟踪中的应用[J].北京广播学院学报.2005，12（2）：23-28.

[3]胡士强，敬忠良.粒子滤波算法综述[J].控制与决策.2005，20（4）：361-371.

[4]刘文静，于金霞，汤永利.粒子滤波自适应部分系统重采样算法研究[J].计算机应用研究，2011，28（3）：912-914.

[5]Doucet A，Davy M.Particle filtering for multi-targettr acking and sensor management [A]. The 5th Int Confon Information Fusion[C].Annapolis，2002：474-481.

[6]Hue C，Cadr e J，Per ez P.Sequential Monte Car lomethods for multiple target tracking and data fusion[J].IEEE Trans on Signal Processing，2002，50（2）：309-325.

[7]薛丽，高社生，胡高歌.自适应Sage-Husa 粒子滤波及其在组合导航中的应用[J].中国惯性技术学报.2013，21（1）：84-88.

[8]Alireza R V，Ali H M.Solving a bi-criteria permutation flow-shop problem using shuffled frog-leaping algorithm[J].Soft computing，2008，12（5）：435-452.

[9]Eusuff M M，Lansey K E.Shuffled frog-leaping algorithm：a mimetic meta-heuristic for discrete optimization [J].Engineering optimization，2006，38（2）：129-154.

[10]Alireza R V，Ali H M.A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem [J].Computers &industrial engineering.2007， 53（4）：642-666.

[11]邹采荣，张潇丹，赵力.混合蛙跳算法综述[J].信息化研究.2012，38（5）：1-5.

[12]Huang C W，Jin Y， Zhao L. Automatic recognition of speech emotion using shuffled frog leaping algorithm[C].2010 3rd international congress on image and signal processing. Yantai， China， 2010：3505-3508.

[13]Li X，Luo J P，Chen M R，et al.An improved shuffled frogleaping algorithm with extremal optimisation for continuous optimisation[J].Informaton sciences，2012，192：143-151.

[14]林娟，钟一文，马森林.改进的反向蛙跳算法求解函数优化问题[J].计算机应用研究.2013， 30（3）：760-763.

[15]赵鹏军，邵泽军.一种新的改进的混合蛙跳算法[J].计算机工程与应用.2012，48（8）：48-50.

[16]何兵.改进混合蛙跳算法及其函数优化应用.泸州职业技术学院学报[J].2013（1）：37-42.

[17]张潇丹，赵力，邹采荣.一种改进的混合蛙跳算法求解有约束优化问题[J].山东大学学报（工学版）.2013，43（1）：1-8.

[18]王亚敏，潘全科，张振领.一种基于离散蛙跳算法的旅行商问题求解方法[J]. 聊城大学学报（自然科学版）.2009（1）：81-85.

[19]Isard M，Blake A.Condensa tion-conditional density propagation for visual tacking [J]. J of Computer Vision，1998，29（1）：5-28.

[20]Chib S，Nardar i F，Shephar d N. Mar kov chain MonteCarlo methods for stochastic volatility models[J].JofEconometr ics，2002，8（1）：281-316.

[21]ARULAM PPALAM M S， MASKELL S，GORDON N，et all.A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking[J].IEEE Trans on Signal Processing，2002， 50（2）：174-188.

[22]万莉，刘焰春，皮亦鸣.EKF、UKF、PF目标跟踪性能的比较[J].雷达科学与技术，2007，15（1）： 13-16.

[23]袁天鑫，最佳估计原理[M].北京：国防工业出版社，1980.

[24]Djuric P M，Kotecha J H，Jianqui Zhang et al.Particle filtering[J].Signal Processing Magazine，2003（5）：19-38.

[25]MUZAFFAR EUSUFF，KEVIN LANSEY，FAYZULPASHA. Shuffled frog-leaping algorithm： a memetie meta-heuristie for diserete optimization[J].Engineering Optimization，2005， 38（3）：129-154.

[26]Emad E1beltagi，Tarek Hegazy，Donald parison among five evolutionary-based optimization algorithms [J].Aavaneed Engineering Informatic，2005，19（1）：43-53.

[27]李景熹，王树宗.UPF算法及其在目标跟踪问题中的应用[J].系统仿真学报.2007，19（3）： 675-677.

[28]李英海，周建中，杨俊杰，刘力.一种基于阈值选择策略的改进混合蛙跳算法[J].计算机工程与应用.2007，43（35）：19-21.

[29]Kitagawa G.Monte Carlo filter and smoother for non-Gaussian nonlinear state space models[J].J Comput Graph Statist，1996，5（1）：l-25.

[30]罗雪晖，杨烨，李霞.改进混和蛙跳算法求解旅行商问题[J].通信学报.2009，30（7）：130-135.