一种改进重采样的粒子滤波算法✴

李善姬，禹爱兰

（延边大学工学院，吉林延吉133002）

一种改进重采样的粒子滤波算法✴

李善姬，禹爱兰

（延边大学工学院，吉林延吉133002）

粒子滤波算法中重采样是解决粒子退化的一种重要方法，但重采样会导致粒子多样性的损失。针对这一问题，对基本重采样算法进行了改进。改进算法首先按基本重采样思想找到权值大的粒子进行复制，然后借鉴遗传算法进行交叉和变异操作，其中变异由变异尺度因子和粒子集的均值来实现。利用改进重采样的粒子滤波算法对经典纯方位目标跟踪问题进行了仿真，仿真结果表明，改进算法具有更好的跟踪精度。

目标跟踪；粒子滤波；重采样；遗传算法

1 引言

粒子滤波器（Particle Filter）利用一些随机样本（粒子）来表示系统随机变量的后验概率分布，它不依赖于系统模型或观测方程的线性程度和状态的分布，克服了以往基于线性高斯滤波方法的缺点，适用于难以进行线性化、难以高斯近似处理以及处理后性能较差的情况。粒子滤波以其突出的优点成为当前非线性估计领域的一个热门研究方向，并得到了广泛的应用［1-3］。在粒子滤波器中，普遍存在的一个问题是粒子退化问题，即经过几次迭代之后，很多粒子的权值变得很小甚至接近于零，这些小权值粒子在重要度更新的时候虽然还要参与计算，但是对整个系统的贡献很小，基本上属于无用的粒子，这样不仅要浪费大量的计算资源，同时也容易造成跟踪精度降低甚至可能会丢失目标。粒子重采样是解决粒子退化的一种重要方法，常用的重采样算法有多项式重采样、残差重采样、分层重采样、系统重采样等。这些算法通过增加粒子的有效性解决了粒子退化问题。重采样后，重要度高的粒子通过重采样被多次选取，这在一定程度上损失了粒子的多样性，即所谓的粒子枯竭，会导致滤波性能下降。针对这一问题，有不少关于将遗传机制引入到重采样过程中的研究［4，5］。本文在改进重采样算法时，在基本重采样的基础上借鉴遗传算法中的交叉和变异操作，通过对粒子进行重组和变异，保证了粒子的多样性。利用改进算法对纯方位跟踪问题进行了仿真，结果表明了算法的有效性。

2 改进重采样的粒子滤波算法

2.1 粒子滤波及其存在的主要问题

粒子滤波是一种基于蒙特卡罗方法的贝叶斯状态估计算法，其中状态的后验概率密度p（xk｜z1：k）由一组具有权值的粒子

来近似。每一时刻从提议分布q（xik｜xik-1，z1：k）中采样新的粒子xik，并根据观测密度和贝叶斯规则计算新的权值wik，将权值归一化之后，k时刻的后验概率密度可以由一组新的粒子｛(xik，wik)，i=1，2，…，N｝来表达。

基本粒子滤波算法如下。

步骤1：初始化

k=0时刻，从初始的先验分布p（x0）采样N个初始粒子xi0（i=1，…，N）。

步骤2：状态更新

（1）k时刻采样粒子集xik～q（xik｜xi

k-1，z1：k）

（2）计算权值

（3）归一化权值

步骤3：重采样

从粒子集{xik}中根据权值{˜wik}重新采样得到新的N个粒子集{˜xik}，并重新分配粒子权值wik= ˜wik=1／N。

步骤5：k=k+1，返回步骤2。

在基本粒子滤波算法中，普遍存在的一个问题是粒子退化问题，即经过几次迭代之后，差不多所有粒子的权值都趋于零。已经证明，重要性权值的方差随着时间递增而增大，所以要完全消除退化现象是不可能的。粒子退化意味着大量的计算都用来更新粒子，而这些粒子对逼近后验概率密度p（xk｜z1：k）的贡献几乎为零。通过重采样后得到新的粒子和权值，可以有效地防止退化问题，但同时带来的另一个问题是会引起粒子的枯竭，也就是权值较小的粒子被去除，而权值较高的粒子被多次采样，这将导致采样结果中包含许多重复的粒子，会损失掉粒子的多样性，使得滤波性能下降。特别是在样本受限的条件下，粒子枯竭现象对于滤波精度的影响更为明显，甚至可能会导致滤波发散现象。

2.2 改进的重采样算法

为了改善重采样带来的粒子多样性损失，有不少研究是将遗传算法引入到粒子滤波的重采样过程中。文献［4］的遗传重采样粒子滤波器是首先对状态进行二进制编码，然后再按照设定的选择、交叉、变异概率对于粒子集依次进行相应的算子计算，最后对粒子集进行二进制解码后得到最终的重采样粒子集。文献［5］的遗传重采样是采用十进制对粒子进行编码，遗传过程首先进行选择操作，然后对被选择保留下来的个体点进行两两配对，按照一定概率进行交叉操作，最后根据某个概率，对个体进行十进制变异操作。本文在改进重采样算法时，借鉴遗传算法中交叉和变异的概念，在基本重采样的基础上对算法进行了改进。首先按基本重采样思想找到权值较大的粒子进行复制，然后按照某一交叉概率pc随机选择两个粒子按照下面的公式进行交叉：

上述交叉算法只是形式上解决了粒子枯竭问题，因为尽管所有粒子是不同的，但经过多次迭代后，它们将会非常接近，这对粒子的多样性是不利的。借鉴遗传算法中变异的概念在某一变异概率pm下再进行如下变异操作：

式中，a为变异尺度因子，b取粒子集x{}ik的均值。

上述借鉴遗传操作的改进重采样算法描述如下：（1）按基本重采样方法根据权值˜wik利用轮盘赌的方法选择N个粒子x{} ik；

（2）按交叉概率pc，根据式（4）进行交叉操作，得到交叉后的粒子集{xik}c；

（3）按变异概率pm，根据式（5）进行变异操作，得到变异后的粒子集{xik}m。

完成上述步骤的重采样后，重新计算权值并归一化。

3 仿真结果及分析

纯方位目标跟踪在许多领域尤其是军事领域（航空、航海、水下）具有非常广泛的应用，其基本问题是根据受到噪声污染的传感器方位数据来估计目标的轨迹（即位置和速度）。纯方位跟踪是一类典型的目标运动分析问题，可以使用非线性状态空间模型来描述，由于它具有可观测性较弱的特点，通常是一个非线性估计问题。有关基于粒子滤波的纯方位目标跟踪研究［6，7］也有不少。

下面利用本文提出的改进重采样的粒子滤波算法对经典的纯方位跟踪问题进行仿真，并将仿真结果与基本粒子滤波算法进行比较。

假设目标在x-y平面的运动方程为

Xk=[x，x˙，y，y˙]Tk表示目标k时刻的状态向量，uk=[ux，uy]Tk是系统噪声。x和y代表目标的位置，x˙和y˙代表目标的速度。系统噪声uk是零均值的高斯白噪声，协方差为

观测噪声vk也是零均值的高斯白噪声，方差为r= 0.0052。目标初始状态为

初始方差为

式中，σ1=0.001，σ2=0.002，σ3=0.002，σ4=0.001。仿真的时间步长为25，粒子数为100。为了定量比较算法性能，定义一次独立实验的均方根误差为

式中，T表示一次实验的时间步长，x＾k表示k时刻的估计值，xk表示k时刻的真实值。

图1为单次实验目标真实轨迹与基本重采样粒子滤波器跟踪结果，图2为单次实验目标真实轨迹与改进粒子滤波器（本文算法）跟踪结果。

图1 目标真实轨迹与PF跟踪轨迹Fig.1 Real target trajectory and PF tracking trajectory

图2 目标真实轨迹与改进PF跟踪轨迹Fig.2 Real target trajectory and improved PF tracking trajectory

表1表示20次独立实验后，两种（基本重采样和改进重采样）PF算法的x坐标和y坐标的均方根误差平均值。

表1 x、y坐标的MSETable 1 The MSE of x and y axis

从仿真结果可看出，采用改进重采样算法的PF跟踪结果在x坐标和y坐标上都具有更小的误差和更好的跟踪精度，说明了改进算法的有效性。虽然遗传代数不需要取较大的值，但是当粒子数增加时，改进算法的运算量和运算时间会有所增加。

4 结束语

本文对粒子滤波重采样算法进行了改进，在基本重采样算法的基础上，借鉴遗传算法中交叉和变异的概念对粒子进行重组和变异，改善了重采样带来的粒子多样性的损失。利用改进算法在MATLAB环境下对经典的纯方位跟踪问题进行了仿真，仿真结果说明利用改进算法的粒子滤波器具有较好的跟踪性能，但同时运算量也有所增加。

［1］Hue C，Cadre L.Sequential Monte Carlomethods formultiple target tracking and data fusion［J］.IEEE Transactions on Signal Processing，2002，50（2）：309-325.

［2］Arulampalam S，Maskell S，Gordon N，eta1.A tutorialon particle filters for on-line non-linear／non-Gaussian Bayesian tracking［J］.IEEE Transactions on Signal Processing，2002，50（2）：174-188.

［3］李勇，汪立新，郑海伟.一种改进的粒子滤波算法［J］.电讯技术，2009，49（1）：50-53. LIYong，WANG Li-xin，ZHENG Hai-wei.An Improved Particle Filter Algorithm［J］.Telecommunication Engineering，2009，49（1）：50-53.（in Chinese）

［4］叶龙，王京玲，张勤.遗传重采样粒子滤波器［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.（in Chinese）

［5］刘刚，梁晓庚.遗传重采样粒子滤波的目标跟踪研究［J］.计算机工程与应用，2010，46（19）：196-199. LIU Gang，LIANG Xiao-geng.Research on target tracking based on Gene Algorithm′s Resampling Particle Filter［J］. Computer Engineering and Applications，2010，46（19）：196-199.（in Chinese）

［6］匡兴红，邵惠鹤.改进的SRCDKF-PF算法及在BOT系统中的应用［J］.系统仿真学报，2008，20（6）：1508-1510，1514. KUANG Xing-hong，SHAO Hui-he.Application of Improved SRCDKF-PF for BOT System［J］.Journal of System Simulation，2008，20（6）：1508-1510，1514.（in Chinese）

［7］冯驰，吕晓凤，汲清波.粒子滤波理论及其在目标跟踪中的应用［J］.计算机工程与应用，2008，44（6）：246-248. FENGChi，LV Xiao-feng，JIQing-bo.Particle filtering theory and its application in target tracking［J］.Computer Engineering and Applications，2008，44（6）：246-248.（in Chinese）

LIShan-jiwas born in Yanji，Jilin Province，in 1959.She received the M.S.degree in 1997.She is now a professor and also the instructor of graduate students.Her research direction is signal and information processing.

Email：lishanji＠ybu.edu.cn

禹爱兰（1988—），女（朝鲜族），吉林松原人，2010年获学士学位，现为硕士研究生，主要研究方向为数字信号处理。

YU Ai-lan was born in Songyuan，Jilin Province，in 1988.She received the B.S.degree in 2010.She is now a graduate student. Her research direction is digital signal proc essing.

关于本刊编辑部授权中国知网优先数字出版的通知

根据期刊出版业态创新的需要，为了寻找新的发展空间和经营模式，争取成果首发权，提高期刊的国际竞争力，本刊编辑部已授权中国知网（www.cnki.net）对本刊所录用稿件优先数字出版。作者投稿时需按本刊网站“相关下载”栏目中“《电讯技术》数字优先出版论文模板.doc”格式进行排版。

谢谢支持与合作！让我们为《电讯技术》的发展而共同努力、携手共进！

《电讯技术》编辑部

An Im proved Resam pling Particle Filtering Algorithm

LIShan-ji，YU Ai-lan
（College of Engineering，Yanbian University，Yanji133002，China）

Resampling is an importantmethod to solve particle degradation in particle filtering（PF）algorithm. But resamplingwill lead to the loss of particle diversity.To solve this problem，the basic resampling algorithm is improved.The improved algorithm first findsweights to copy large particles according to the basic thinking of resampling，and then uses the genetic algorithm（GA）to cross and variate.The variation is realized by scale variation factor and themean of particle sets.The problem of classical Bearing-only target tracking is simulated with the improved resampling particle filter algorithm.Simulation results show that the improved algorithm has better tracking precision.

target tracking；particle filtering；resampling；genetic algorithm

TP391

A

10.3969／j.issn.1001-893x.2011.09.007

李善姬（1959—），女（朝鲜族），吉林延吉人，1997年获硕士学位，现为教授、硕士生导师，主要研究方向为信号与信息处理；

1001-893X（2011）09-0035-04

2011-04-11；

2011-06-02