设为首页 加入收藏 期刊导航 网站地图
  • 首页
  • 期刊
    • 数学与物理
    • 地球与环境
    • 信息通讯
    • 经济与管理
    • 生命科学
    • 工程技术
    • 医药卫生
    • 人文社科
    • 化学与材料
  • 会议
  • 合作
  • 新闻
  • 我们
  • 招聘
  • 千人智库
  • 我要投搞
  • 办刊

期刊菜单

  • ●领域
  • ●编委
  • ●投稿须知
  • ●最新文章
  • ●检索
  • ●投稿

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
Computer Science and Applicatio n 计算机科学与应用, 2011, 1, 112-117
http://dx.doi.org/10.12677/csa.2011.13023 Published Online December 2011 (http://www.hanspub.org/journal/csa)
Copyright © 2011 Hanspub CSA
Optimization of the Particle Filter Algorithm*
Lei Liang1, Jie Cao 1, Lili Zhao2
1School of Computer and Communication, Lanzhou University of Technology, Lanzhou
2School of Economics and Management, Lanzhou University of Technology, Lanzhou
Email: llgyape@126.com; ll241gy@163.com
Received: Aug. 31st, 2011; revised: Sep. 27th, 2011; accepted: Oct. 19th, 2011.
Abstract: In this paper, two problems were explicated by the detailed presentation of basic concepts and prin-
ciples of the particle filter algorithm. One is particle impoverishment which dues to re-sampling, and another
is particle degeneracy. To overcome these problems, existed method s of particle filter optimization are analy-
zed. Finally, this paper presented a method that combine particle filter with intelligent algorithm, the combi-
nation algorithm can overcome the shortcomings of particle filter effectively. Simulation results show that it
is superior to the traditional particle filter optimization algorithm.
Keywords: Particle Filter; Particle Swarm Optimization; Genetic Algorithm; Particle Degeneracy; Particle
Impoverishment
粒子滤波算法的优化与改进*
梁 磊1,曹 洁1,赵丽丽 2
1兰州理工大学计算机与通信学院,兰州
2兰州理工大学经济管理学院,兰州
Email: llgyape@126.com; ll241gy@163.com
收稿日期:2011 年8月31 日;修回日期:2011 年9月27 日;录用日期:2011 年10 月19 日
摘 要:本文对粒子滤波的基本概念与算法原理进行了详细的介绍,分析了粒子滤波所存在的粒子退
化问题和重采样所导致的粒子匮乏问题,以及目前针对这两个问题所提出的粒子滤波的优化算法。最
后,给出了粒子滤波与智能算法相结合的方法。通过对粒子滤波与智能算法的结合,可以更有效的克
服粒子滤波的缺点,仿真结果表明,通过智能算法优化的粒子滤波的滤波性能优于传统的粒子滤波优
化算法。
关键词:粒子滤波;粒子群优化算法;遗传算法;粒子退化;粒子贫化
1. 引言
粒子滤波(particle filter,PF)于上世纪五十年代被
提出,虽然在统计学和自动控制领域得到了应用,但
由于没有解决粒子退化问题和计算量过大的制约,并
未引起科研者们足够的重视。直到1993 年,Gordon
等提出了自举粒子滤波算法[1],该算法在递推过程中
引入了重新采样思想以克服粒子退化问题,同时,计
算机运算能力的急剧增强也为粒子滤波提供了客观条
件,随后粒子滤波得到长足发展。
由于粒子滤波技术适用于任何能用状态空间模型
表示的非高斯背景的非线性随机系统,精度可以逼近
最优估计,更接近于工程现实。所以其应用极其广泛。
在目标跟踪、故障诊断、金融等领域都体现出其先进
的优越性。
2. 基本粒子滤波算法
粒子滤波是一种基于序贯蒙特卡罗方法和递推贝
叶斯估计的统计滤波方法[2]。其基本思想是:首先依
据系统状态向量的经验条件分布 ,在状态空间
产生一组随机样本的集合


0
px

1
0: ,
s
N
ii
kk
i
xw ,称这些样本为
粒子。然后根据量测不断调整粒子的权重和位置,通
*资助信息:甘省自然科学基金项目(1014ZSB064)。
梁磊等粒子滤波算法的优化与改进 113
过调整后的粒子信息修正最初的经验条件分布。当样
本容量很大时,可近似于状态变量真实的后验概率密
度

kk
px z。
2.1. 最优贝叶斯估计
设动态空间模型如下:


11
,
,
kkkk
kkkk
xfxv
zhxw





 (1)
若已知状态的初始概率密度函数为


00 0
px zpx,
则状态预测方程为:

1: 1111: 11
d
kkkkk kk
px zpx xpxzx


(2)
状态更新方程为:



1: 1
1:
1: 1
kkkk
kk
kk
pzxpx z
px zpz z


 (3)
其中

1: 11: 1d
kkkkkk
pz zpzxpx zx

k
,如 果
(2)、(3)表示的概率密度函数是线性高斯的,则其可由
均值和方差来表示。此时,应用 Kalman 滤波所得结
果可达到最优值。但如果是非线性非高斯模型,则很
难得到完整的解析式来描述这样的概率密度函数
2.2. SIS算法
采用蒙特卡罗方法可将积分运算转化为有限样本
点的求和运算,如果能从


0: 1:kk
px z中抽取 N个独立
的同分布的样本

0: ,1,,
ik
x
iN,那么状态概率分布
可用下面的经验概率分布近似表示:



0: 1:0:0:
1
Ni
kkkk k
i
px zwxx





i
N
(4)
权值满足 ,当 时,

1
1
Ni
k
i
w




0: 1:kk
px z绝
对收敛于

0: 1:kk
px z。
在采样时,直接从状态的概率密度函数中取出样
本是很困难的。但若从一个重要密度函数中采样则相
对简单。可从

0:1: 1kk
qx z


中独立抽取 N个样本

0: ,1,,
ik
x
iN,状态的概率密度函数逼近为





0: 1:0:0:
1
1
Nii
k
kkk k
i
N
iii
kkk
i
px zwxx
ww w















0: 1:
0: 1:
ikk
i
kikk
px z
wqx z

(5)
其中 称为重要性权值
估计,先取重要性分布函数为:
。为了递推




0:1:0: 11:0: 11: 1
,
kkk kkkk
qxzqx xzqxz


可以得
到新的粒子集


0: 1
s
N
iki
x

,重要性权值更新公式为:





1
1
1,
ii
kk kk
ii
kk ii
kk k
x
ww qx xz




归一化权值,即可得到一组加权的粒子
i
pz xpx (6)



0: ,,1,,
i
ik
k
x
wi N
算得出。
。状态的概率密度函
3. 粒
当用重要性函数
况是重要性函数非常接近后验概率分布,
为零,即
数可由(5)计
子滤波算法存在的主要问题
替代后验概率分布作为采样函数
时,理想情
也就是希望重要性函数的方差基本


0
i
k
Var w

。但由于没有考虑当前的量测值,从重要
性概
变得更加明显
率密度中取样得到的样本与从真实后验概率密度
采样得到的样本有很大偏差,特别是当似然函数呈尖
峰状态或在系统状态转移概率密度的尾部时,偏差就
。当重要性权重的方差随时间递增时,
粒子的权重集中在少数粒子上,甚至在几步递归后,
可能只有一个粒子有非零权值,从而使得大量的计算
工作都被浪费在用来更新那些对后验概率分 布


1:kk
px z的估计几乎不起作用的粒子上,结果粒子集
无法表达实际的后验概率分布,这就是粒子滤波算法
的退化问题[3]。
样
为避免退化现象的发生,引入了重采样技术。重
采样的基本思想是通过
3.1. 重采
后验概率

1:
s
N
kk
px z


1
ii
kk k
i
wx x


重采样
s
N次,产生新的
粒子集

*
1
s
N
i
xki

,使得


*ijj
px xw
。由于重采样是
kk k
独立同分布的,权值被重新设置为 1
j
k
s
w。判断是
的依 的退化程度
N
否重采样 据是粒子

2
1
1
eff k
i
,
s
Ni
Nw
首先设定
样本数 作为阈值,当
eff
N越小,意味着退化现象越严重。 一个有效
threshold
N

2
threshol
d
1
1s
Ni
eff k
i
N
wN



Copyright © 2011 Hanspub CSA
梁磊等粒子滤波算法的优化与改进
114
采样,从而能够自适应地根据样本情况决定是否要进
行重
采样 题,即粒子匮乏。由于
密度函数容易采样
系数的方差最小为准则。Doucet等给出了在
时,则进行重采样,这样就无需在每个时刻都进行重
采样,可以在一定程度上降低算法复杂度。
但重 也带来了新的问
较大权值的粒子被多次选择,采样结果中包含许多重
复点,降低了粒子的多样性[4]。
3.2. 重要密度函数
选取好的重要密度函数也可以改善粒子退化现
象。选取重要密度函数时以使重要
和使得权
给定

0: 11
s
N
i及的
ki
x1:k
z情形下使得权系数方差最小的
最优重要密度函数是:







11
11
,,
,
ii
kk kkk k
ii
kk kkk
qx xzpxxz
pz xxpxx




(7)
1
i
kk
pz x


将(7)式代入(6)式得:



11
11
d
ii i
kk kk
iiii
kkkkk
wwpzx
wpzxpxx x




i
k
(8)
,需要从可见,选取重要密度时


1,
i
kk k
px xz
抽
取样本并估算积分




1d
iii
kkkk k
pz xpx xx


i
。当 k
x
为
有限集或


1,
i
kk k
px xz
为高斯函数时这
在一般情况下,并不能直接解决这两个问题,得到最
优的 从目标概率中
取问题,目前较为热门的解
ss-hermite Particle
Filter,GHPF)[5],它采用 GH 来产生重要密度函数,
式,可以通过高斯
点变
是可行的,但
重要密度函数的困难程度与直接 抽
取样本的困难程度相同,但从最优重要密度函数的形
式可以看出,产生下一代预测样本依赖于已有的样本
和量测数据。由此可见,如何平衡效率和实现难易度
之间的矛盾,选择合适的重要密度函数是粒子滤波算
法设计中关键的步骤。
4. 粒子滤波算法的优化方法
4.1. 基于重要密度函数的改进
基于重要密度函数选
决方法有:高斯厄米粒子滤波(Gau
GH 积分公式是一种高斯型积分公
换公式

11
ii
kk kk
xpqx

提高代数精度;扩
展卡尔曼粒子滤波(Extended Kalman Particle Filter,
EKPF)[6],它是通过 EKF来更新粒子:





11
1
ii
k
ii1
,,,
N
Ni
i
k
kkk
x
w z

EKFxp












 (9)

1
1
ii
k
kk
xfx

 (10)
 
1
1
TT
iiii
kkkk kk
kk
PFPFFQF


i
(11)
 
11
TT
iii iii i
kkkkkk
T
k
kk
P H
kk
KPHURU H







 (12)
 

11
ii i
kkk kk
kk
xx Kzhx


 




(13)

1
iii
kkk
kk kk
PP KHP
1
i



EKF 是一种常用的非线性滤波方法,
原来的非线性系统进行一阶泰勒近似,将非线性系统
方程和量测方程近似线性化,然后用
方法进行状态估计。EKF 结合最新的量测值,通过高
斯近
(14)
主要通过对
常规卡尔曼滤波
似不断更新后验分布来实现递推估计;无味粒子
滤波是利用无味卡尔曼滤波(Unscented Kalm an Filter,
UKF)[7]方法来生成下一个预测粒子,由于充分考虑了
最新的观测值,从而提高了估计精度。其基本思想是
在使用 Unscented 变换的基础上,加入最新的观测量
并产生非线性粒子滤波的建议分布:


01,
1
k
kkj j j
j
qX Zqxqx XZ


 (15)
式中,


1, 2,kk
,
X
xx x和k

k1, 2,,
Z
zz z
测值序列,由于状态序
而建议分布
分别
表示
列服 一阶马
k
从
时刻所有状态序列和观
尔可夫过程,因


kk
X Zq
可分解成式(15)的形式。
4.2. 基于重采样的改进
为热门的
算法[8],在采样之后加上一
移动处理使粒子
集趋于平稳分布
基于重采样中粒子匮乏的问题,目前较
解决方法有:重采样移动
步MCMC(Markov chain Monte Carlo)




,,pzKzzpz Kzz



,减弱粒
子间
样前,AVPF 依据似然值的
的相关性;而且 Markov链能使粒子分布更加接
近状态概率密度函数分布,使样本分布更加合理;辅
助变量粒子滤波(Auxiliary Variable Particle Filter,
AVPF)[9],在重采 大小对
Copyright © 2011 Hanspub CSA
梁磊等粒子滤波算法的优化与改进 115
原粒子集中的各个权值进行修正,得到粒子集为



110:
1
,, ,
N
ii ii
kkkkk k
i
x
wqxz



,丢弃其中的辅助变
量1
i
k

可得到所需的粒子集



1
,
N
ii
kk
i
xw ,使得重采
样后的 子向似然函数的高值区移动。该算法从经 粒
此,可以获得更小的权值方差。
粒子需要
过平滑的后验密度中采样,更接近于状态的真值,因
但是,由于在 AVPF
算法的一次迭代中,对于每个 计算两次似
然函数和权值,所以 ,其计算量增大了。正则粒子滤
波(Regularized Particle Filter,RPF)[10],正则化方法
从后验概率

1:kk
px z的连续近似中进行重采样,


1:
Nii
kkkhk k
px zwKxx
通过引入核密度函数和
1
i
核带宽系数

1
x
hn
x
Kx K
h
h


以连续形式计算状态

后验概率,与标准粒子滤波的离散形式相比,该算法
可以有效缓解重采样过程造成
程噪声较小时可获得较好的滤波精度。
5. 粒子滤波算法与其它智能算法的结合
优化粒子滤
5.1.
美国心理学家 Kennedy 和电气工程师
PSO 算法是一种有
法,
随机初始化一个粒子群(数
量为 m),其中,每i个粒子在n维空间的位置表示为
的粒子退化问题,在过
近几年来,科研者们更多的关注于粒子滤波与其
它智能算法的结合。通过其它智能算法来
波,改善了粒子退化与粒子匮乏现象。并取得了一定
的成果。
粒子群优化粒子滤波
粒子群优化[11](Particle Swarm Optimization,PSO)
算法是由
Eberhart于1995 年提出的。标准的
效的全局寻优算法,它是基于群体智能理论的优化算
通过群体中粒子间的合作和竞争产生的群体指导
优化搜索。PSO 算法基于种群的全局搜索策略,将每
个个体微粒看作是在 n维搜索空间中的一个没有重量
和体积的微粒,并在搜索空间中以一定的速度飞行,
该飞行速度由个体的飞行经验和群体的飞行经验进行
动态调整。在每次迭代中,每个个体微粒根据下式来
调整其飞行速度和位置:
 

11
1
ijijj ijij
vtwvtcr ptxt
crgtx t

 


 (16)
 
11 (17)
PSO 算法可以表述为:
2ij ijij

ijij ij
xtxtvt


12
,,,
iii in
X
xx x
次迭代,粒子通过两个
优解,称为个体极值
,速度为
极值
一个是粒子本身从初始到当前迭代次数搜索产生的最
在找到这两个最优值后,每个粒子根据下式更新其速

12
,,,
iii in
Vvv v
来更新自己
12
,,
。每 一
的速度和位置:

12
,,,
iii in
Ppp p;另一个是
种群目前的最优解,称为全局极值

,
n
Ggg g。
度和位置:


Rand i
VwVc PX
cG
 
 (18)
ii

1
2Rand()
ii i
i
X 
X
XV

 (19)
Rand 是介于(0, 1)区间的随机数; 称为惯性系
数;
w
12
2cc


,PSO
动。选定一阈值
为学习因子。通过移动粒群向
子靠近算法实际是驱动所有粒 高似然区移
子
子向
最优粒

,当粒
则说明粒子群分布在真实状态附近,停止优化。再对
粒子集进行权重更新和归一化处理,为解决粒子退化
选择、交叉、变异 操作引入到粒
子滤波中,代替传统的样方法。具体 现步骤如下:
1) 选择操作。对 k权粒子集
子群的最优值与其符合时,
问题,需要选择和复制权重值较大的粒子,即对粒子
集进行重采样。在重采样之后,真实状态附近的粒子
权重值将会增大。通过上述优化过程,使得粒子集在
权值更新前更加趋向于高似然区域,从而解决了粒子
匮乏问题。
5.2. 遗传粒子滤波
遗传粒子滤波(GAPF)是遗传算法[12]与粒子滤波的
结合。遗传算法本身反映的 就是一种进化思想,针对 解
决标准粒子滤波算法中存在粒子退化及运算量过大的
问题,将遗传算法中的
重采 实
时刻加

1
,
s
N
i
xw
i
kk
i

, 视
为此粒子群中对应粒子的适应度,计 ,
也就是粒子重要性权值的方差。由
方差最小时,状态估计最接近真实状 适
选择操作,保留所有粒子, 、
变异操作,直接进入预测阶段;若方差 ,
跳过选择操作,直接进行交叉、变异 操
作。从粒子集中随机选取两个粒子
i
k
应度的方差大小来判断选择操作。若方差大小符合要
求,进行

s
N
mn
w
差
值的
根据
叉
要求
交叉
算适应度的方
于粒子重要性权
态。因此,
而不再进行交
大小不符合
操作。2)
,1
,
kk
mn
xx

,按照
Copyright © 2011 Hanspub CSA
梁磊等粒子滤波算法的优化与改进
116
下面两式进行交叉操作:


1
mmn
kkk
xax ax

  (20)


1
nnm
kkk
xaxax

 (21)
式中

~0,N

,

~0,1U

为若

交叉准则







max
mm
k
kkk
pz xpz x

,n
kk
pz x,则接受粒子

m
k
x
;
否则,接受概率为







max ,
m
k
kk
pz xpz xpz x
的粒子。接受和放弃粒子
mn
kkk

n
k
x
的方法与

m
k
x
相同。(3)变
异操作。从粒子集中随 择一个粒机选子

1
s
N
j
k
j
x

,按 照
下式进行变异操作:

jj
kk
xx

,变异准则为:如果




ij
k
kk
pz xpz xk
,则接受粒子

j
k
x
;否则,接受粒
子概率为




/
kk
ij
kk
过大的问题。
果与实验分析
本文选取非静态增长模型(UNGM 模型),应用
pz xpz x的粒子。将上述遗传算法
的选择、交叉与变异操作替换标准粒子滤波中的重采
样,可有效的改善粒子滤波算法中粒子退化与计算量
6. 仿真结
Matlab 软件进行仿真。系统过程模型与状态模型如下:
 


 


25 1
0.5 1xt 8cos 1.21
11
x
txxtwt
xt



(22)
 
220zt xtvt (23)
别为
的UPF、RPF OPF 和GPF算法
进行仿真比较。单次实验的均方根误差公式
本文选择在量测噪声方差 1R,过程噪声方差分
10Q
数分别取 N
的噪声条件下,来进行仿真实验。对粒子
、PS100
为:


12
2
1
1n
nn
i
RMSEx x
N






。平均有效样本数为 eff
N,
在同 ,
为5
面分
本文实验通过对同是改进粒子滤波重要性密度函
数部分的 UPF 和PSOPF 算法的对比、同是改进粒子
和G
精度
高于
等情况下,有效样本数越多 估计精度越高。时
间步长 0,仿真 50 次,算法终止条件设为迭代次
数50n次。下别给出UPF 和PSOPF、RPF 和
GPF 算法单次实验的估计仿真图1~2:
滤波重采样部分的RPF 和GPF 算法的对比,说明各
改进算法的滤波性能。图 1~2 中可以明显看出,PSOPF
算法 PF 算法的仿真估计曲线相比于 UPF 和RPF
更接近真实值,说明 PSOPF 和GPF算法的滤波
UPF 和RPF算法。表 1所统计的实验平均数据
可看出,在相同噪声环境,同等粒子数目条件下,
05 1015 20 25 30 35 40 4550
-30
-20
-10
0
10
20
30
󰿧
True stat e
PSOPF
UPF
󰌧󳌥/󱜃
Figure 1. State estimation of UPF and PSOP
图1. UPF与PSOPF 算法仿真实验图
051015 2025 303540 4550
-30
-20
-10
0
10
20
30
󰌧󳌥
/
󱜃
󰿧
True state
GP F
RP F
Figure 2. State estimation of RPF and GPF
图2. RPF与GPF 算法仿真实验图
Table 1. Statistics of Filter performance
表1. 滤波性能数据统计表
过程噪声方差为 10,量测噪声方差为1
算法 粒子数 N平均有效样本 RMSE 运行时间
UPF 0.3259
PSOPF100.4369
RPF 0.2495
GPF 100 20.189 1.6273 0.4172
100 15.452 2.4583
0 18.816 1.8617
100 16.547 2.2136
Copyright © 2011 Hanspub CSA
梁磊 等  粒子滤波算法的优化与改进
Copyright © 2011 Hanspub CSA
117
PSOPF 和G和RPF
说明它们有效地抑制了粒子退化现象,提高了粒子多
样性。且 PF 和G,说 们
的滤波精度更高,虽然在估计时间上有略有增长,但
并没超出实的要求
7. 语
助。为了提高粒子滤
法的运算速度和鲁棒性,研究粒子滤波的硬件实现方
。目前,粒子滤波算法在国外发展
快,
PF 的平均有效样本要多于 UPF ,[2
SOP A的RMSE也较小 明它
时性 。
结束
针对粒子滤波的退化与贫乏问题,科研者们提出
了许多改进的方法,但仍未能在数学上解决算法收敛
性的证明问题。若能有效解决收敛性问题,则对粒子
退化现象的抑制将有很大帮 波算
法也尤为关键得很 [1
并取得了许多研究成果。国内许多学者也开始积
极探索粒子滤波的各种改进算法,并成功地将粒子滤
波算法应用到人脸识别、语音增强、目标跟踪、故障
诊断等诸多领域,促进了国内粒子滤波算法理论和应
用研究的发展。
参考文献 (References)
[1] N. J. Gordon, D. J. Salmond and A. F. M. Smith. A novel appr oach
to nonlinear and non-Gaussian Bayesian state estimation. IEEE
Proceeding, 1993, 140:107-113.
] J. I. Ababneh, M. H. Batained. Linear phase FIR filter design
using particle swarm optimization and genetic algorithms. Digi-
tal Signal Processing, 2008, 18(4): 657-668.
[3] T. Bengtsson, P. Bickel. Curse-of-dimensionality revisited: Co-
llapse of the particle filter in very large scale systems. Institute of
Mathematical Statistics Collections, 2008, 2: 316-334.
[4] A. Bain, D. Crisan. A continuous time particle filter. Applica-
tions of Mathematics, 2009, 60: 221-256.
[5] 王宁. 基于高斯厄米粒子滤波的红外点目标跟踪算法研究[D].
南京航空航天大学, 2007.
[6] T.-Y. Xu, S.-L. Liu. Algorithm of 3-Dsingle observer passive
location with the extended dalman particle filter. IEEE Computer
Society Proceeding, 2009: 4704-4707.
[7] J. K. Lee, C. Jekeli. Rao-blackwellized unscented particle filter
for a handheld unexploded ordnance geolocation system using
IMU/GPS. Navigation, 2011, 64(2): 327-340.
[8] M. Johannes, N. Polson. Markov chain Monte Carlo. Mathema-
tics and Statistics, 2009, part 7: 1001-1013.
[9] W. Nick, S. Sumeetpal and G. Simon. Auxiliary particle imple-
mentation of probability hypothesis density filter. Aeropace and
Electronic Systems, 2010, 46(3): 1437-1454.
0] S.-K. Park, J. P. Hwang and E. Kim. A new evolutionary particle
filter for the prevention of sample impoverishment. Evolutionary
Computation, 2009, 13(4): 801-809
[11] Q.-K. Pan, M. F. Tasgetiren and Y.-C. Liang. A discrete particle
swarm optimization for the no-wait flowshop scheduling problem.
Computers & Operations Research, 2008, 35(9): 2807-2839.
[12] U. Maulik, S. Bandyopadhyay and A. Mukhopadhyay. Multi-
objective genetic algorithm-based fuzzy clustering. Computer Scien-
ce, 2011: 89-121.

版权所有:汉斯出版社 (Hans Publishers) Copyright © 2012 Hans Publishers Inc. All rights reserved.