许江湖，黄 亮，刘 忠

(海军工程大学 电子工程学院，湖北 武汉430033)

0 引 言

粒子滤波又称序贯蒙特卡罗方法，是一种基于蒙特卡罗方法和递推贝叶斯估计的统计滤波方法。粒子滤波完全突破了Kalman 滤波理论框架，对系统的过程噪声和量测噪声没有任何限制。粒子滤波(PF)作为解决非线性、非高斯动态系统的参数估计和状态滤波问题的有效方法，近年来随着计算机运算能力的急剧增长和计算成本的不断降低，已成为研究热点［1－3］。

粒子退化是标准粒子滤波算法的主要缺陷。采用重采样方法在一定程度上可以抑制粒子退化现象的发生。然而重采样带来的新问题是:权值越大的粒子的子代越来越多，而权值较小的粒子被剔除，最糟糕的情形是新的粒子集实际都是一个权值最大的粒子的子代，即所谓“样本枯竭”现象，从而导致粒子集的多样性变差，不足以用来近似表征后验密度，难以保证估计精度，特别是在样本受限条件下，这种粒子多样性减弱对滤波精度的影响更为突出，甚至导致滤波发散现象［4］。为此，不少学者尝试利用进化算法(包括遗传算法、进化策略、进化规划)来解决粒子滤波的退化问题［4－8］，并取得了一定的理论成果。2006 年，Mehrabian 和Lucas 提出了一种新颖的数值优化算法，称为入侵野草(杂草)优化(IWO)算法［9］。同进化算法一样，IWO算法也是一种随机搜索仿生学优化算法，该算法模仿了野草入侵的种子空间扩散、生长、繁殖和竞争性消亡的基本过程，具有很强的鲁棒性和自适应性。与进化算法相比，IWO 算法简单易于实现，不需要遗传操作算子，能简单而有效地收敛于问题的最优解，是一种强有力的智能优化算法。研究表明，IWO 算法在性能上优于进化算法和人工蜂群克隆算法，并且在高维问题上优于粒子群算法［10］。因此，IWO 算法自提出以来，一直受到学者们的关注和运用［10－15］。

本文将IWO 算法与粒子滤波算法相结合，提出基于IWO 算法的粒子滤波算法(IWOPF)。该算法将IWO 应用于粒子重采样，以保证粒子的有效性和多样性。最后通过计算机仿真比较该算法与基于进化算法的粒子滤波算法以及传统粒子滤波算法的滤波性能和计算时。

1 粒子滤波简介

离散时间非线性动态系统的状态方程和量测方程分别为:

式中:k 为采样时刻;xk∈Rnx为k 时刻的系统状态向量;fk:Rnx×Rnv→Rnx为系统状态xk-1的非线性函数;vk为过程噪声，其协方差为Qk，均值为0;nx和nv分别为状态和过程噪声的维数;zk∈Rnz为k 时刻系统状态的量测向量;hk:Rnx×Rnn→Rnz为系统状态xk的非线性函数;nk为量测噪声，其协方差为Rk，均值为0，且与vk相互独立;nz和nn分别为量测值和量测噪声的维数。

滤波过程的任务是通过可获得的系统观测值zk估计出系统状态xk，也即要求得到系统状态的后验概率分布p(xk| z1:k)。粒子滤波的核心思想是利用一系列随机样本的加权和表示状态后验概率密度:

通常很难从p(x0:k| z1:k)中直接采样，解决方法是先从一个已知的、容易采样且尽量接近后验概率分布的重要性概率密度函数q(x0:k| z1:k)中采样，这时权值的递推公式为:

标准粒子滤波算法选择最易于实现的先验概率密度作为重要密度函数，即

这时，式(4)可以进一步简化为:

当前时刻粒子的权重被评估后，通过引入重采样技术来改善粒子退化问题。

2 IWO 算法

IWO 算法中，“野草”表示随机产生的可行解，“种子”表示野草的后代，“种群”表示所有野草的集合。一般而言，IWO 算法的执行过程要经历以下4 个步骤:

1)初始化种群

在这个步骤中，需要确定最大种群数目Pmax、最大迭代次数itermax、问题维数D、最大和最小可生成种子数Smax和Smin、非线性调节指数n、标准差初始值σinit和最终值σfinal以及初始搜索空间X，并随机生成N0个解。

2)繁殖

各野草产生的种子个数为:

式中:f 为当前野草的适应度值;fmax和fmin分别为当前种群中野草对应的最大和最小适应度值。

从式(7)可以看出，种群中的成员能够散播的种子数是根据该成员的适应度值以及种群所有成员的最大和最小适应度值来决定的。在用优化算法求解问题过程中，可能会直觉地认为可行解比不可行解具有更好的适应度值，因此会放弃不可行解。然而，这种做法忽视了进化算法具有概率性，其产生的解是在不可行和可行之间不断转化的。Mehrabian和Lucas 认为，在进化过程中一些不可行解可能带有更多的有用信息，如果它可能穿过一个不可行区域(特别是非凸的可行搜索空间)，则系统更容易到达最优点。因此，在IWO 算法中，繁殖过程按照自然界中的繁殖法则，给予不可行的个体生存和繁殖的机会，只是这种机会相对较小。

3)空间散布

空间散布体现了算法的随机性和适应性。种群产生的种子个体按正态分布N(0，σ)在其父代野草个体附近的D 维空间进行散布。每次迭代对应不同的标准差，随着迭代的进行，标准差从初始值σinit减小到最终值σfinal，当前迭代的标准差为:

式(8)确保了在较远区域产生种子的概率以非线性的方式逐渐降低，以使适应度值好的个体聚集在一起。

4)竞争性生存

经过数代繁殖后，产生的后代数目将超过环境资源的承受能力，通过预先设定的最大种群数目Pmax对种群数量进行控制。在算法迭代过程中，种群中的所有野草及其后代按适应度值从大到小进行排序，只有适应度值最好的前Pmax个个体可以生存下来，其余的个体被清除。

综合上述步骤可知:在算法运行过程中，一个野草个体可以有多个种子后代，种子按正态分布在父代野草周围。只有相对较优秀的种子才有机会进入下一轮迭代，一旦种子存活下来进入一轮迭代，所有存活下来的野草和种子共同构成一轮迭代的种群。这种机制给予那些适应度值低的个体繁殖的机会，如果它们的后代适应度值更好，这些后代就可以生存下来。当算法运行到预先设定的最大迭代次数itermax时，算法终止。

3 IWOPF 算法

前面已经述及，粒子退化是标准粒子滤波算法的主要缺陷。而粒子滤波与IWO 算法的相似之处在于它们都有一个初始化的群体，每个个体代表系统的一个可能解，这些个体都根据一定的规则进行状态转变，它们都对适应度较高的个体进行复制。因此，用IWO 算法来解决粒子滤波的退化问题具有可行性。

IWOPF 算法将IWO 算法应用于粒子重采样以解粒子滤波的退化问题。即通过IWO 算法中的繁殖、空间散布、竞争性生存等操作来保证粒子的多样性和有效性。具体而言，IWOPF 算法的执行步骤如下:

1)初始化

设置粒子数目N，从先验分布p(x0)中采集粒子令确定最大迭代次数itermax、问题维数D、最大和最小可生成种子数Smax和Smin、非线性调节指数n、标准差初始值σinit和最终值σfinal。而最大种群数目Pmax= N。

for k = 1，2，…。

2)重要性采样

3)更新权值

根据当前观测值zk，计算每个粒子的权值，并归一化:

4)基于IWO 算法的重采样

②繁殖:根据式(7)计算每个粒子产生的种子数;

③空间散布:根据式(8)计算当前迭代的标准差;

④竞争性生存:把所有粒子及其后代的适应度值从大到小进行排序，只有适应度值最好的前Pmax= N 个粒子可以生存下来，并重新定义这些粒子为| i = 1，2，…，N};

⑤判断算法运行是否达到预先设定的最大迭代次数itermax，如果是，则转步骤5，并令否则转步骤4 中的①;

5)状态估计

4 仿真结果与分析

为了验证本文算法的有效性，通过2 个仿真实例比较本文提出的IWOPF、标准PF、文献［4］提出的基于进化采样的粒子滤波 (ESPF)以及文献［5］提出的遗传粒子滤波(GPF)的滤波性能以及仿真时间。2 个仿真实例采用的运动模型以及初始条件均相同，但量测模型不同。

运动模型为:

其中:

采样周期T = 1 s，仿真时间为80 s，转弯角速度为目标初始位置为(7，8)km，初始速度(－0.08， －0.06)km/s，系统过程噪声是均值为0，方差为Q = diag {［3，3］}的加性高斯白噪声;

仿真实例1 的量测模型为:

其中，量测噪声是均值为0，方差为R = diag{［200，0.005］}的加性高斯白噪声;

仿真实例2 的量测模型为:

其中，量测噪声是均值为0，方差为R = 0.005 的加性高斯白噪声。

进行50 次蒙特卡罗仿真。仿真中，粒子初始分布为高斯分布，其均值为［7.3，- 0.06，7.7，-0.08］× 103，方差为diag［100，4，100，4］。IWOPF有关参数如表1 所示。图1 和图2 分别为粒子数N =400 时，蒙特卡罗仿真次数为50 次，实例1 基于X 轴方向和Y 轴方向目标位置的均方根误差(RMSE)曲线。表2 和表3 分别给出了不同粒子数目情况下，4 种滤波算法对实例1 的滤波平均RMSE 和50次仿真所用的时间。其中，平均RMSE 的定义如下［16］:平均

式中:MC 为仿真次数;L 为仿真长度;x(k)为真实值;)为估计值。

表4 和表5 则是针对实例2 的滤波情况。

图1 实例1 的X 轴方向位置RMSE 曲线Fig.1 RMSE in position on X axis for example 1

图2 实例1 的Y 轴方向位置RMSE 曲线Fig.2 RMSE in position on Y axis for example 1

表1 IWOPF 参数表Tab.1 IWOPF parameter values

表2 不同粒子数目情况下仿真实例1 的位置估计平均RMSE 比较Tab.2 The mean comparison of RMSE in position of example 1 for different sample size 单位:m

表3 不同粒子数目情况下仿真实例1 的50 次仿真所用时间Tab.3 The computation time of 50 Monte Carlo simulations of example 1 for different sample size 单位:s

表4 不同粒子数目情况下仿真实例2 的位置估计平均RMSE 比较Tab.4 The mean comparison of RMSE in position of example 2 for different sample size 单位:m

表5 不同粒子数目情况下仿真实例2 的50 次仿真所用时间Tab.5 The computation time of 50 Monte Carlo simulations of example 2 for different sample size 单位:s

从图1 ～图2、表2 及表4 可看出，本文提出的IWOPF 算法明显优于另外3 种粒子滤波算法。而从表3 和表5 可看出，随着粒子数目的增加，标准PF计算时间基本上是线性增加，而ESPF、GPF 和IWOPF 则是非线性增加。另外，IWOPF 的计算时间明显少于ESPF 和GPF，这是由于IWOPF 没有交叉和变异这2 种遗传操作算子，算法相对简单。综上所述，IWOPF 继承了IWO 算法简单而有效的优点，相对于基于进化算法的粒子滤波，可以在大幅度缩短计算时间的情况下，有效提高滤波精度。

5 结 语

IWO 是近年来提出一种简单、有效的基于种群的新颖数值优化算法。自提出以来，一直受到国内外学术界的关注，并在许多领域得到成功运用。本文将IWO 与PF 相结合，提出了一种基于IWO 算法的PF算法，该算法将IWO 运用于粒子滤波的重采样环节，以保证粒子有效性和多样性。计算机仿真结果表明，基于IWO 算法的PF 算法继承了IWO 算法简单而有效的优点，相对于基于进化算法的粒子滤波，可以在大幅度缩短计算时间的情况下，有效提高滤波精度。由于IWO 算法是近年来才提出一种智能优化算法，虽然其在许多应用研究领域取得了长足的发展，便远未达到成熟的阶段，其与粒子滤波相结合也有许多问题值得深入地分析与探讨。例如:算法中的有一组参数需要预先设置，如何根据不同的情况设置合理的参数组合是下一步深入研究的问题。

［1］李远征，卢朝阳，高全学，等．基于多特征融合的均值迁移粒子滤波跟踪算法［J］． 电子与信息学报，2010，32(2):411 －415．LI Yuan-zheng，LU Zhao-yang，GAO Quan-xue，et al．Particle filter and mean shift tracking method based on multi-feature fusion ［J］． Journal of Electronics ＆Information Technology，2010，32(2):411 －415．

［2］VILA J P．Enhanced consistency of the resampled convolution particle filter［J］．Statistics and Probability Letters，2012，82:786－797．

［3］PARK C B，LEE S W．Real-time 3D pointing gesture recognition for mobile robots with cascade HMM and particle filter［J］．Image and Vision Computing，2011(29):51－63．

［4］胡振涛，潘泉，梁彦，等．基于进化采样的粒子滤波算法［J］．控制理论与应用，2009，26(3):269 －273．HU Zhen-tao，PAN Quan，LIANG Yan，et al． The particle filter algorithm based on evolution sampling［J］． Control Theory ＆ Applications，2009，26(3):269 －273．

［5］朱志宇．粒子滤波算法及其应用［M］． 北京:科学出版社，2010:73 －76．

［6］李翠芸，姬红兵．快速Metropolis－Hastings 变异的遗传重采样粒子滤波器［J］．系统工程与电子技术，2009，31(8):1968－1972．LI Cui-yun，JI Hong-bing．Genetic resampling particle filter based on fast Metropolis-Hastings mutation［J］． Systems Engineering and Electronics，2009，31(8):1968 －1972．

［7］叶龙，王京玲，张勤． 遗传重采样粒子滤波器［J］． 自动化学报，2007，33(8):885 －887．YE Long，WANG Jing-ling，ZHANG Qin． Genetic resampling particle filter［J］． Acta Automatica Sinica，2007，33(8):885 －887．

［8］PARK S，HWANG J，ROU K，et al． A new particle filter inspired by biological evolution: genetic filter ［C］//Proceedings of World Academy of Science，Engineering and Technology，Bangkok，Thailand:IEEE，2007(21):459－463．

［9］MEHRABIAN A R，LUCAS C．A novel numerical optimization algorithm inspired from weed colonization［J］．Ecological Informatics，2006，1(4):355 －366．

［10］张帅，王营冠，夏凌楠．离散二进制入侵杂草算法［J］．华中科技大学学报(自然科学版)，2011，39(10):55－60．

［11］韩毅，蔡建湖，李延来，等．野草算法及其研究进展［J］．计算机科学，2011，38(3):20 －23．HAN Yi，CAI Jian-hu，LI Yan-lai，et al． Invasive weed optimization and its advances［J］．Computer Science，2011，39(10):55 －60．

［12］MOHAMADI M F，KOMJANI N，MOUSAVI P．Application of invasive weed optimization to design a broadband patch antenna with symmetric radiation pattern［J］．IEEE Antennas and Wirwless Propagation Lwtters，2011(10):1369－1372．

［13］GOURAB G R，SWAGATAM D，PRITHWISH C，et al．Design of non-uniform circular antenna arrays using a modified invasive weed optimization algorithm［J］． IEEE Transactions on Antenns and Propagation，2011，59(1):110－118．

［14］MEHRABIAN A R，YOUSEFI－Koma A．A novel technique for optimal placement of piezoelectric actuators on smart structures［J］．Journal of the Franklin Institute，2011(348):12－23．

［15］KUNDU D，SURESH K，GHOSH S，et al． Multi-objective optimization with artificial weed colonies［J］． Information Sciences，2011(181):2441 －2454．

［16］胡士强，敬忠良．粒子滤波原理及其应用［M］．北京:科学出版社，2010:70 －71．