论文部分内容阅读
摘要：非线性非高斯状态空间模型的最优估计问题在多个领域具有重要的应用，基本粒子滤波算法存在的最大问题是粒子退化，针对这一问题， 对重要性函数选取这一影响粒子滤波器性能的关键技术进行了深入分析，在此基础上，描述一种改进的粒子滤波算法。该算法将无迹卡尔曼滤波算法(UKF)、混合遗传模拟退火算法和基本粒子滤波算法相结合，应用无迹卡尔曼滤波算法获得重要性函数，提高了粒子的使用效率；应用混合遗传模拟退火算法的进化思想，提高了粒子的多样性。
关键词：粒子滤波；无迹卡尔曼滤波；混合遗传模拟退火算法
中图分类号：TP311 文献标识码：A 文章编号：1009-3044(2011)35-0000-0c
A Combined Particle Filter Algorithm
WU Xiao-tun
(School of Communication and Information Engineering,Xi’an University of Posts and Telecommunicationgs, Xi’an 710121, China)
Abstract：PF can be typically used to describe any complex nonlinearities and non-Gaussian distributions and compute any statistical estimates, such as mean and variance, more accuracy. the study of PF is just in the primary stage, and there still exists many critical problems need to be investigated. The sample degeneracy is the critical problem existed in particle filter. In order to solve this problem, a new combined particle filter algorithm, based on the genetic simulated annealing algorithm and unscented Kalman filter algorithm, is presented . In the proposed algorithm, unscented Kalman filter algorithm is used to generate the importance proposal distribution which can match the true posterior distribution more closely.
Key words: particle filter; unscented kalman filter; genetic simulated annealing algorithm
1. 概述
1.1 研究背景和意义
粒子滤波器是20 世纪 90 年代出现的一种基于贝叶斯递推和蒙特卡罗方法的实时在线仿真算法，该算法不受模型线性、高斯假设的约束，适用于任意非线性非高斯动态系统。
应用粒子滤波方法进行非线性系统的状态估计，得到的统计特性比传统的参数化线性近似方法更为准确，近些年来已成为多个领域新的研究热点。
1.2 粒子滤波技术的研究现状
粒子滤波是一种新兴技术，当前研究主要集中在两个方面：
1) 提高性能，这是本文讨论的内容。
2) 扩展它的应用领域。
2. 粒子滤波算法分析
2.1粒子滤波算法分析
在粒子滤波算法[1]中，重要性函数的选取和重采样方法都对粒子退化有重要的影响。
重要性函数的选取标准是尽量使重要性权值的方差变小。先验分布和最优分布是目前最常用的两种重要性。先验分布虽易于实现，但由于不考虑当前时刻的测量值，没有最新的量测信息，使得抽取的样本与真实后验概率分布存在较大偏差，特别是当似然函数位于系统状态转移概率密度的尾部或观测精度较高时，这种偏差非常明显，甚至某些权值很小的样本成为无效样本，导致这种算法性能较低。最优分布依赖已有样本和最新的观测数据来产生下一个预测样本，该方法能够最小化重要性权值的方差，但计算比较复杂。
2.2 UKF 算法
UKF算法[2]采用类似Monte Carlo仿真的思想，利用一系列选取好的Sigma采样点，对状态向量的后验概率密度进行近似，然后对这些Sigma点应用UT变换进行更新，更新后的Sigma点的后验均值和协方差能够精确到真实后验分布的二阶距。由于不需要经过将非线性系统线性化的过程，故很容易进行非线性系统的状态估计。
2.3 遗传模拟退火算法
2.3.1 遗传算法
遗传算法（GA）是一种通过模拟自然进化过程搜索最优解的方法，它通过对一群编码化的种群的更新与迭代来搜索全局最优解。
遗传算法是以决策变量的编码作为运算对象，以目标函数作为搜索信息，可同时使用多个搜索点的搜索信息，并且使用概率搜索信息。遗传算法的优点是不受搜索空间的约束，不必要求问题的连续性、倒数存在和单峰的假设，具有内在的并行性和较快的收敛速度。
2.3.2 模拟退火算法
模拟退火算法是一种新的组合优化方法。1982 年，Kirkpatrick等将热力学中的退火思想引入组合优化领域，提出一种解大规模组合优化问题，特别是NP完全问题的有效近似算法—模拟退火(SimulatedAnnealing, SA)算法。它源于对固体退火过程的模拟，采用Metropolis接收准则，并用一组称为进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。
模拟退火算法依据 Metropolis 准则接受新解，因此除接受优化解外，还在一个限定范围内接受恶化解，这正是模拟退火算法与局部搜索算法的本质区别所在。开始时 t 值大，可能接受较差的恶化解；随着 t 值的减小，只能接受较好的恶化解；最后在 t 值趋于零值时，就不再接受任何恶化解了。这就使模拟退火算法既可以从局部最优的“陷井”中跳出，更有可能求得组合优化问题的整体最优解，又不失简单性和通用性。
此外，模拟退火算法的收敛速度取决于参数的选择。模拟退火算法的主要优点就是能以一定的概率接收性能较差的状态。即算法收敛路径不唯一，使算法即便落入局部最优的陷阱中，理论上经过足够长的时间也可跳出，从而收敛到全局最优解。模拟退火算法的主要缺点是解的质量与运算时间之间的矛盾。为求得一个近似最优解，需进行多次反复运算，当问题规模增大时缺乏可行性。
2.3.3 遗传模拟退火算法
混合遗传模拟退火算法[3]是结合了遗传算法与模拟退火算法的特点产生的一种优化算法。它是以遗传算法为主体流程，把模拟退火算法融入其中，用以进一步调整优化群体。即整个算法的执行过程由两部分组成，首先通过遗传算法的选择、交叉、变异等遗传操作来产生一组新的个体，然后再独立地对所产生出的各个个体进行模拟退火过程，以其结果作为下一代群体中的个体。其中模拟退火操作针对一定规模的基因个体进行一定的“扰动”而产生恶化解，这一设计引用了遗传算法中的变异和倒位思想，从对全局最优解的搜索角度和算法的进化速度上来提高遗传算法的性能。
遗传算法使得模拟退火算法既可以从局部最优的“陷井”中跳出，又能求得组合优化问题的整体最优解，有效利用了模拟退火算法的爬山特性，提高了算法的收敛速度。
2.4 改进粒子滤波算法
这种改进的粒子滤波算法，首先，应用无迹卡尔曼滤波(UKF)来产生重要性采样函数，充分利用了最新观测数据，使得抽取的样本与真实后验分布产生的样本更相近，即使在似然函数位于系统状态转移概率密度函数的尾部，或观测精度要求较高时，都能很好的逼近真实后验分布。
然后，应用遗传算法中的复制、重组、变异等操作，使得在保证权值高的粒子被大量复制的同时，也有一些权值小的粒子破例入选的可能；然后对更新过的粒子进行模拟退火过程，对每个粒子（染色体个体）进行一定的“扰动”，依据Metropolis准则接受新的个体，运行过程反复迭代，直到满足权值方差条件。与简单的重取样方法相比，混合遗传模拟退火算法，更好的提高了粒子的多样性。
2.4.1 改进粒子滤波算法分析
这种算法应用 UKF 产生重要性采样函数，提高了粒子的使用效率；应用混合遗传模拟退火算法进行重采样，在保证权值高的粒子被大量复制的同时，依据Metropolis 准则以一定概率接收新的粒子种群，保持了粒子的多样性。通过对这两点进行提高改进，这种改进粒子滤波算法应该会表现出更高的滤波精度和更强的抗噪声性能。
下一步的工作，应该是利用一个较常用的非线性系统对 PF 算法和改进算法进行了性能仿真比较。用仿真结果验证了改进算法在提高粒子滤波性能方面的有效性。
3 小结
本文重点研究了两种改进粒子滤波算法针对基本粒子滤波存在的粒子退化问题，描述了一种改进的粒子滤波算法。该算法应用 UKF 产生重要性采样函数；应用混合遗传模拟退火算法进行重采样。
参考文献:
[1] 孙毅.基于贝叶斯原理和蒙特卡罗方法的高分辨方位估计新方法研究[D].西北工业大学,2003.
[2] 周明,孙树栋.遗传算法原理及其应用[M].北京:国防工业出版社,1999:12-44.
[3] 陶海红,廖桂生,王伶.基于混合遗传算法的 m-序列波形优化设计[J].电波科学学报,2004, 19(3):253-257.
关键词：粒子滤波；无迹卡尔曼滤波；混合遗传模拟退火算法
中图分类号：TP311 文献标识码：A 文章编号：1009-3044(2011)35-0000-0c
A Combined Particle Filter Algorithm
WU Xiao-tun
(School of Communication and Information Engineering,Xi’an University of Posts and Telecommunicationgs, Xi’an 710121, China)
Abstract：PF can be typically used to describe any complex nonlinearities and non-Gaussian distributions and compute any statistical estimates, such as mean and variance, more accuracy. the study of PF is just in the primary stage, and there still exists many critical problems need to be investigated. The sample degeneracy is the critical problem existed in particle filter. In order to solve this problem, a new combined particle filter algorithm, based on the genetic simulated annealing algorithm and unscented Kalman filter algorithm, is presented . In the proposed algorithm, unscented Kalman filter algorithm is used to generate the importance proposal distribution which can match the true posterior distribution more closely.
Key words: particle filter; unscented kalman filter; genetic simulated annealing algorithm
1. 概述
1.1 研究背景和意义
粒子滤波器是20 世纪 90 年代出现的一种基于贝叶斯递推和蒙特卡罗方法的实时在线仿真算法，该算法不受模型线性、高斯假设的约束，适用于任意非线性非高斯动态系统。
应用粒子滤波方法进行非线性系统的状态估计，得到的统计特性比传统的参数化线性近似方法更为准确，近些年来已成为多个领域新的研究热点。
1.2 粒子滤波技术的研究现状
粒子滤波是一种新兴技术，当前研究主要集中在两个方面：
1) 提高性能，这是本文讨论的内容。
2) 扩展它的应用领域。
2. 粒子滤波算法分析
2.1粒子滤波算法分析
在粒子滤波算法[1]中，重要性函数的选取和重采样方法都对粒子退化有重要的影响。
重要性函数的选取标准是尽量使重要性权值的方差变小。先验分布和最优分布是目前最常用的两种重要性。先验分布虽易于实现，但由于不考虑当前时刻的测量值，没有最新的量测信息，使得抽取的样本与真实后验概率分布存在较大偏差，特别是当似然函数位于系统状态转移概率密度的尾部或观测精度较高时，这种偏差非常明显，甚至某些权值很小的样本成为无效样本，导致这种算法性能较低。最优分布依赖已有样本和最新的观测数据来产生下一个预测样本，该方法能够最小化重要性权值的方差，但计算比较复杂。
2.2 UKF 算法
UKF算法[2]采用类似Monte Carlo仿真的思想，利用一系列选取好的Sigma采样点，对状态向量的后验概率密度进行近似，然后对这些Sigma点应用UT变换进行更新，更新后的Sigma点的后验均值和协方差能够精确到真实后验分布的二阶距。由于不需要经过将非线性系统线性化的过程，故很容易进行非线性系统的状态估计。
2.3 遗传模拟退火算法
2.3.1 遗传算法
遗传算法（GA）是一种通过模拟自然进化过程搜索最优解的方法，它通过对一群编码化的种群的更新与迭代来搜索全局最优解。
遗传算法是以决策变量的编码作为运算对象，以目标函数作为搜索信息，可同时使用多个搜索点的搜索信息，并且使用概率搜索信息。遗传算法的优点是不受搜索空间的约束，不必要求问题的连续性、倒数存在和单峰的假设，具有内在的并行性和较快的收敛速度。
2.3.2 模拟退火算法
模拟退火算法是一种新的组合优化方法。1982 年，Kirkpatrick等将热力学中的退火思想引入组合优化领域，提出一种解大规模组合优化问题，特别是NP完全问题的有效近似算法—模拟退火(SimulatedAnnealing, SA)算法。它源于对固体退火过程的模拟，采用Metropolis接收准则，并用一组称为进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。
模拟退火算法依据 Metropolis 准则接受新解，因此除接受优化解外，还在一个限定范围内接受恶化解，这正是模拟退火算法与局部搜索算法的本质区别所在。开始时 t 值大，可能接受较差的恶化解；随着 t 值的减小，只能接受较好的恶化解；最后在 t 值趋于零值时，就不再接受任何恶化解了。这就使模拟退火算法既可以从局部最优的“陷井”中跳出，更有可能求得组合优化问题的整体最优解，又不失简单性和通用性。
此外，模拟退火算法的收敛速度取决于参数的选择。模拟退火算法的主要优点就是能以一定的概率接收性能较差的状态。即算法收敛路径不唯一，使算法即便落入局部最优的陷阱中，理论上经过足够长的时间也可跳出，从而收敛到全局最优解。模拟退火算法的主要缺点是解的质量与运算时间之间的矛盾。为求得一个近似最优解，需进行多次反复运算，当问题规模增大时缺乏可行性。
2.3.3 遗传模拟退火算法
混合遗传模拟退火算法[3]是结合了遗传算法与模拟退火算法的特点产生的一种优化算法。它是以遗传算法为主体流程，把模拟退火算法融入其中，用以进一步调整优化群体。即整个算法的执行过程由两部分组成，首先通过遗传算法的选择、交叉、变异等遗传操作来产生一组新的个体，然后再独立地对所产生出的各个个体进行模拟退火过程，以其结果作为下一代群体中的个体。其中模拟退火操作针对一定规模的基因个体进行一定的“扰动”而产生恶化解，这一设计引用了遗传算法中的变异和倒位思想，从对全局最优解的搜索角度和算法的进化速度上来提高遗传算法的性能。
遗传算法使得模拟退火算法既可以从局部最优的“陷井”中跳出，又能求得组合优化问题的整体最优解，有效利用了模拟退火算法的爬山特性，提高了算法的收敛速度。
2.4 改进粒子滤波算法
这种改进的粒子滤波算法，首先，应用无迹卡尔曼滤波(UKF)来产生重要性采样函数，充分利用了最新观测数据，使得抽取的样本与真实后验分布产生的样本更相近，即使在似然函数位于系统状态转移概率密度函数的尾部，或观测精度要求较高时，都能很好的逼近真实后验分布。
然后，应用遗传算法中的复制、重组、变异等操作，使得在保证权值高的粒子被大量复制的同时，也有一些权值小的粒子破例入选的可能；然后对更新过的粒子进行模拟退火过程，对每个粒子（染色体个体）进行一定的“扰动”，依据Metropolis准则接受新的个体，运行过程反复迭代，直到满足权值方差条件。与简单的重取样方法相比，混合遗传模拟退火算法，更好的提高了粒子的多样性。
2.4.1 改进粒子滤波算法分析
这种算法应用 UKF 产生重要性采样函数，提高了粒子的使用效率；应用混合遗传模拟退火算法进行重采样，在保证权值高的粒子被大量复制的同时，依据Metropolis 准则以一定概率接收新的粒子种群，保持了粒子的多样性。通过对这两点进行提高改进，这种改进粒子滤波算法应该会表现出更高的滤波精度和更强的抗噪声性能。
下一步的工作，应该是利用一个较常用的非线性系统对 PF 算法和改进算法进行了性能仿真比较。用仿真结果验证了改进算法在提高粒子滤波性能方面的有效性。
3 小结
本文重点研究了两种改进粒子滤波算法针对基本粒子滤波存在的粒子退化问题，描述了一种改进的粒子滤波算法。该算法应用 UKF 产生重要性采样函数；应用混合遗传模拟退火算法进行重采样。
参考文献:
[1] 孙毅.基于贝叶斯原理和蒙特卡罗方法的高分辨方位估计新方法研究[D].西北工业大学,2003.
[2] 周明,孙树栋.遗传算法原理及其应用[M].北京:国防工业出版社,1999:12-44.
[3] 陶海红,廖桂生,王伶.基于混合遗传算法的 m-序列波形优化设计[J].电波科学学报,2004, 19(3):253-257.