第 33 卷 第 8 期 2007 年 8 月 自 动 化 学 报 ACTA AUTOMATICA SINICA Vol. 33, No. 8 August, 2007 遗传重采样粒子滤波器 叶 龙 1 王京玲 1 张 勤 1 摘 要 粒子退化现象是影响粒子滤波器性能的一个重要因素. 本文针 对粒子退化, 将遗传机制应用于粒子重采样, 以进化设计解决退化问题. 分析并给出了平衡粒子集的有效性与多样性的手段以取得最佳性能的遗 传粒子滤波结构的方法. 关键词 粒子滤波器, 粒子退化, 遗传机制, 有效性粒子, 多样性粒子 中图分类号 TP3 Genetic Resampling Particle Filter YE Long1 WANG Jing-Ling1 ZHANG Qin1 Particle degeneration is a key issue in the perfor- Abstract mance of a particle filter. In this paper we introduce genetic mechanism into particle resampling process. It is shown that the new particle filter can effectively eliminate particle degeneration and reduce its dependency on the particle validity. Furthermore, the new genetic particle filter can be optimized by three key ge- netic factors – selection, crossover and mutation probabilities. Key words mechanism, effective particle, diversiform particle Particle filter, particle degeneration, genetic 1 引言 近 年 来, 针 对 状 态 估 计 与 运 动 跟 踪, 粒 子 滤 波 器[1∼3](Particle filter) 由于采用蒙特卡罗采样 (Monte Carlo sampling) 结构而在非线性、非高斯系统状态跟踪上体现出 越来越大的优越性, 并得到了广泛的应用[4, 5]. 粒子退化[3] 是粒子滤波器中不可避免的、同时严重影响粒子滤波器性 能的现象, 在粒子滤波器经过几次迭代之后, 很多粒子只有 很小甚至接近于零的权值, 这些权值在进行粒子的重要度更 新的时候虽然还要计算但是对整个系统的帮助很小, 基本 上属于无用的粒子, 这样一方面浪费了大量计算资源, 同时 也容易造成跟踪的精度降低甚至目标丢失. 粒子重采样是解 决粒子退化问题的一种重要方法, 常用的重采样算法有累 积分布重采样[2](Binary search)、系统重采样[6](Systematic resampling)、剩余重采样[7](Residual resampling) 等. 这些 算法通过增加粒子的有效性解决了粒子退化问题, 但是在实 际应用中可影响系统的鲁棒性. 重采样完成后, 重要度高的 粒子通过重采样被多次选取, 这在一定程度上丢失了粒子的 多样性, 由此造成的后果就是一旦目标丢失或跟踪精度不够, 系统自动收敛的可能性很小. 针对这一问题, 本文将遗传机制[8] 应用于粒子重采样, 利用进化思想解决粒子退化问题, 即针对重采样中粒子有效 性与多样性的两个矛盾, 提出了一种新型的在保证粒子有效 性的同时科学地增加粒子多样性的方法 —遗传重采样算法. 同时通过单变量与多变量跟踪问题的实例, 给出了针对具体 问题寻找最佳遗传系统的方案, 通过引入置信区间分析并演 收稿日期 2006-2-16 收修改稿日期 2007-4-19 Received February 16, 2006; in revised form April 19, 2007 国家自然科学基金 (60572041) 资助 Supported by National Natural Science Foundation of China (60572041) 1. 中国传媒大学信息工程学院 北京 100024 1. Information Engineering School, Communication University of China, Beijing 100024 DOI: 10.1360/aas-007-0885 示了多样性粒子与有效性粒子的比例对于跟踪准确性的影 响. 2 遗传重采样算法与遗传粒子滤波器 假设一个动态状态空间中的目标状态方程与观测方程定 义如下 xk = f (xk−1, vk) (1) zk = h(xk, uk) (2) 其中, xk 与 zk 分别表示目标状态值与观测值, fk : Rns × Rnv → Rns 表示目标状态非线性转移函数, vk 为状态转移 噪声, ns 与 nv 分别表示目标状态矢量维数与状态噪声矢量 维数；hk : Rns × Rnu → Rnz 表示目标状态非线性观测函 数, uk 为观测噪声, nz 与 nu 分别表示目标观测矢量维数与 观测噪声矢量维数, 跟踪的目的就是通过目标的观测状态 zk 得到 xk 的估计. 粒子滤波器是通过递归蒙特卡罗采样实现跟踪的一种统 计计算方法, 其算法包括两个主要步骤：预测和更新. 预测是 指根据 Chapman-Kolmogorov 方程得到目标运动的先验概 率密度函数 (Probability density function, PDF)；而更新是 指通过贝叶斯公式与目标状态似然度对先验 PDF 做出的修 正. 在粒子滤波器中, PDF 用带有权值的粒子组成的粒子集 近似表示, 因此粒子滤波器是一种通过粒子状态与权值的预 测与更新而实现目标状态后验概率密度估计的方法. 粒子退 化是粒子滤波器中一个不可避免的问题. 在粒子状态更新后, 为解决粒子退化问题, 需要对粒子集合进行重采样操作以去 除不重要的粒子, 但是这种去除往往使粒子集丢失其多样性 (如引言中所述). 因此, 在本文中, 我们将遗传操作引入了粒 子重采样, 解决了这一问题. 将遗传机制应用于粒子的重采样. 首先, 作为一种进化 思想的理论基础, 遗传机制为解决粒子退化问题提供了重要 的指导思想; 其次, 遗传机制不仅仅通过选择算子[8]Ts 遴选 优良个体, 还可以通过重组算子 Tc 与变异算子 Tm 操作产 生新的个体. 因此, 适当地优化调整选择概率 Ps、重组概率 Pc 以及变异概率 Pm, 可以在保证粒子有效性的同时兼顾粒 子的多样性. 遗传重采样过程是遗传机制的执行过程, 即针 对每一个带有权值的粒子状态, 首先对状态进行二进制编码, 然后按照设定的选择、交叉、变异概率对于粒子集依次进行 相应的算子计算, 得到的粒子集合在二进制解码后得到最终 的重采样粒子集. 因此, 遗传重采样下的粒子滤波器算法可 以描述为算法 1. 算法 1. 遗传重采样粒子滤波器算法 (GRPF) [{xi k, ωi k}N i=1] = GRPF[{xi k−1}N i=1, zk] 步骤 1. 初始化粒子集 {xi for k = 1 : K 步骤 2. 粒子状态预测 k, xi k ∼ P (xi xi k−1) 步骤 3. 粒子状态权衡 (更新) k−1, ωi 0}i=1:N 0, ωi i = 1 : N k−1P (zk|xi k) k ∝ ωi ωi i k = ω N ωi k ωi k 步骤 4. 遗传粒子重采样 i=1 

886 自 动 化 学 报 33 卷 do while i < N Ps Ts : SN → Rj // 选择操作 // 表示说明：S 表示原粒子, R 表示重 采样粒子集, N 表示粒子总数, 此操作表示从 N 个粒子的粒子集中通过 选择算子得到新粒子集中的第 j 个粒子. (下同) j = j + 1 end do do while i < N Pc/2 Tc : SN = Rj:j+1 j = j + 2; // 交叉操作 end do do while i < N Pm // 变异操作 end do Tm : SN → Rj j = j + 1; {wi}i=1,2,··· ,N = 1 N end 注. 本算法中, 在进行粒子权值更新时假设重要度函数 取目标运动的前向概率密度函数. 3 遗传粒子滤波器的性能分析与优化方法 本文选用粒子滤波器性能评测时常用的两个应用[6] 进 行遗传粒子滤波器的性能分析, 即单变量的非平稳经济学变 化估计问题与多变量 Bearings-only 跟踪问题. 1) 单变量经济学变化估计 该问题的运动模型与观测模型按式 (3) 与 (4) 得出. x(t) = 0.5x(t − 1) + 25x(t − 1) 1 + x(t − 1)2 + 8 cos(1.2(t− 1)) + ω(t) z(t) = x(t)2 20 + ν(t) (3) (4) 其中, ω(t) 与 ν(t) 为零均值高斯噪声, 方差分别为 10 与 1, 初始状态取 x0 = 0.1. 本文中对于粒子状态进行 [-20 20] 区 间内位数为 9 的二进制编码. 跟踪输出采用最大后验概率密 度输出法 (Maximum a posterior, MAP)[9]. 我们参照文献 [6] 中的方法设定后验概率密度分布中 2.5%至 97.5%的间隔范围为置信度 95%的置信区间, 高置信 水平的代价是宽的置信区间, 有效性粒子与多样性粒子数目 分配的最佳即通过保证置信区间最有效的包含目标状态的真 实值而使目标估计具有最小的误差. 本文选择采用累积分布重采样、ps = 0.6 与 ps = 0.8 的 遗传重采样的三种形式的粒子滤波器对同一状态变化进行估 计, 粒子个数取 500, 跟踪结果如图 1. 由图 1 可以看出, 与累计分布重采样相比, Ps = 0.8 的 遗传重采样算法通过增加粒子集中多样性粒子数目扩大了估 计的置信区间, 在使置信区间更好地包含状态真实值的同时 也使跟踪准确性有所增加. 但当 Ps = 0.6 时, 多样性粒子数 目的增加虽然扩大了估计的置信区间, 但是导致准确性降低. 这说明, 在有效性粒子与多样性粒子之间存在着一个使跟踪 性能最优的最佳分配问题. 为研究这一问题, 我们针对 10 个选择概率取值分析, 跟 踪误差取 10 次跟踪过程的误差平均值. 如图 2(a) 所示, 选择 概率取值 0.8 时跟踪性能最好, 此时粒子集中新旧粒子数之 比为 8 : 2. 需要说明的一点是, 0.8 只是在本仿真中特定条件 下的最佳值, 在不同的应用场合下, 最佳选择概率会随预测 模型的准确性的不同, 预测模型与观测模型中信噪比的不同 而相应变化. (a) 累积分布重采样 (b) Ps = 0.8 GRPF (c) Ps = 0.6 GRPF 图 1 跟踪效果的置信区间分析图 Fig. 1 Believing range analysis of tracking 图 2 (a) 遗传重采样粒子滤波器中跟踪误差 — 选择概率曲线 Fig. 2 (a) Tracking error-Ps curve of GRPF 图 2 (b) 各种重采样算法的性能比较图 Fig. 2 (b) Performance comparison between GRPF and other resampling algorithms 

8 期 叶 龙等：遗传重采样粒子滤波器 887 2) Bearings-only 模型 Bearings-only 运动模型与观测模型按式 (5) 与 (6) 得出 X(t) = φX(t − 1) + w(t) (5) 样性的矛盾问题, 提高了跟踪的准确度并增加了跟踪的鲁棒 性. 针对粒子有效性与多样性两种矛盾的概念, 本文还通过 仿真实例给出了遗传粒子滤波器优化设计方法, 使遗传粒子 滤波器能够达到最佳跟踪与最良好的系统鲁棒性. 其 中 Xt = (x, vx, y, vy)t, φ 为 状 态 转 移 矩 阵, ω(t) 为 (0, 0.001) 高斯噪声. z(t) = tan −1(y/x) + v(t) (6) 其中 v(t) 为 (0, 0.005) 高斯噪声. 状态初始值与转移矩阵按 文献 [6] 中仿真方案取值. 与单变量估值问题不同, 对于高维变量使用遗传重采样 算法需要解决状态编码的问题, 在 Bearings-only 模型中, vx 与 vy 的状态只与自身前一时刻的状态相关, 而 x 与 y 状态 除与自身状态相关外, 还与 vx 与 vy 状态相关, 变化复杂度 相对较高, 并且观测值的确定也只与 x 和 y 有关. 因此在进 行遗传重采样的交叉与变异操作时, 对于需要操作的父代个 体, 我们只针对其状态中的 x 与 y 进行操作. 跟踪过程中, 选 择概率 Ps = 0.8, 总粒子个数 1000. 跟踪结果如图 3 所示. 图 3 (a) 遗传重采样粒子滤波器高维跟踪效果图 Fig. 3 (a) GRPFs performance in multi-dimensions tracking area 图 3 (b) 各状态变量跟踪曲线 Fig. 3 (b) Tracking curves of state element 4 结论 本文针对粒子滤波器中的退化现象, 通过改进重采样算 法, 设计出遗传粒子滤波器结构, 以进化设计解决了退化问 题. 给出了一种在保证粒子有效性的同时科学地增加粒子多 样性的算法, 解决了粒子滤波器跟踪问题中粒子有效性与多 References 1 Huang A J. A tutorial on Bayesian estimation and track- ing techniques applicable to non-linear and non-Gaussian process [Online], available: http://www.mitre.org/work/ tech papers/tech papers 05/05 0211/05 0211.pdf, February 11, 2005 2 Doucet A, Godsill S, Chistophe A. On sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing, 2000, 10(3): 197∼208 3 Isard M, Blake A. Condensation-conditional density propa- gation for visual tracking. International Journal of Computer Vision, 1998, 29(1): 5∼28 4 Cho J U, Jin S H, Pham X D, Jeon J W, Byun J E, Kang H. A real-time object tracking system using a particle filter. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2006. 2822∼2827 5 Haykin S, Huber K, Chen Z. Bayesian sequential state es- timation for mimo wireless communications. Proceedings of the IEEE, 2004, 92(3): 439∼454 6 Gordon N, Salmond D J, Smith A F M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F Radar and Signal Processing, 1993, 140(2): 107∼113 7 Liu J S, Chen R, Logvinenko T. A theoretical framework for sequential importance sampling and resampling. Sequential Monte Carlo in Practice. New York: Springer-Verlag, 2001. 225∼246 8 Zhang Wen-Xiu, Liang Yi. Mathematical Foundation of Ge- netic Algorithms. Xian: Xian Jiaotong University Press, 2000. 15∼45 (张文修, 梁怡. 遗传算法的数学基础. 西安: 西安交通大学出版社, 2000. 15∼45) 9 Doucet A, Godsill S J, West M. Monte Carlo filtering and smoothing with application to time-varying spectral esti- mation. In: Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing. IEEE, 2000. 1701∼1704 叶 龙 助理研究员. 主要研究方向为计算机视觉、统计计算和数学建模. E-mail: yelong@cuc.edu.cn (YE Long vision, statistical modeling, and computing.) Lecturer. His research interest covers computer 王京玲 教授. 主要研究方向为计算机视觉、统计计算和通信. 本文通信 作者. E-mail: wjl@cuc.edu.cn (WANG Jing-Ling Professor. Her research interest covers computer vision, statistical modeling, and telecommunications. Corresponding author of this paper.) 张 勤 教授. 主要研究方向为多媒体信号处理和通信. E-mail: zhangqin@cuc.edu.cn (ZHANG Qin media signal processing and telecommunications.) Professor. His research interest covers multi-