106 北京理工大学学报 第30卷 贝叶斯估计[.其关键步骤是用随机采样点以及相 持一定程度的多样性。 应的权重来表示后验概率密度，并根据这些样本点 2.2GA-MCMC粒子重采样 和权重获得估计值， 交叉和变异是遗传算法的主要操作，通过交叉 1.1序贯重要性采样 保持粒子群的多样性，将马尔可夫链蒙特卡罗MC 粒子滤波的基础是序贯重要性采样(SIS)算法. MC方法]引入变异操作可有效威诚轻粒子贫化问 该算法采用一组加权随机样本{x4,)名：来近似 题，并通过选择操作将原来的粒子集合替换为新的 表征后验密度函数，其中{x,k,i=0,1,…,N,}是 更多样并且符合目标后验分布的粒子集合， 带有相应权重的支撑点的集合，其权重表示为{， 2.2.1交叉 i=1,2,…,N,},而xoa={x,j=0,1,…,k}表示到 每次对两个粒子进行交叉操作，产生的后代能 时刻时所有状态的集合，从而k时刻的后验概率 同时保持它们父代的两个粒子的特征.为防止近亲 密度可以近似表示为 繁殖，通过禁止父代粒子和同样的粒子配对来保持 N, 粒子群体的多样性。 p(x4|)≈∑8(x4-x), (1) 算法1：交叉算法/CROSSOVER算法 权值更新为 若随机数U.<P(交叉概率P。子代粒子的数 w wh p(ai)p(il (2) 目和总粒子数的比值)，则 q(ri,) =ar+(1-a)xR, (3) 式中：权重满足归一化∑，w=1p(,zi)为时 If=ar +(1-a)xA. (4) 刻观测状态z4的似然函数：q(x|x1,)为重要 式中：a为交叉因子：x公和x为k时刻父代粒子： 性密度函数.可以证明，随着N,→∞，式(1)的近 x和x为子代粒子. 似结果将逐渐趋近于真实的后验概率密度p(x。丨 p(z)>max(p(z),p( 21:）. x)},接受x,否则以以下概率接受 1.2重采样 p(z)/maxip(zrA),p(z)). SIS的一个严重缺陷是退化问题，即重要性权 (5) 值的方差随着时间是递增的，经过多次迭代后，集 对x的操作也以同样的方式进行 中对大多数权值过小的粒子进行计算没有意义，这 2.2.2变异 时要用到重采样技术，基本思想是抑制或剔除小权 Markov链产生来自目标分布的样本，并且具 值粒子，对于大权值粒子则依其权值大小进行复制， 有很好的收敛性，能将粒子推向更接近状态概率密 从而把处理资源按照粒子权值的大小进行分配.但 度函数(PDF)的地方，使样本分布更合理.Metrop- 是重采样后保留了大量的大权值粒子，这样就引起 olis-Hastings算法8]是一种模拟上述马尔可夫链的 了粒子的贫化，使粒子缺乏多样性. 方法. 算法2：Metropolis-Hastings/MH变异 2GA-MCMC粒子滤波 Metropolis-Hastings/,MH变异步骤如下. 为了解决在迭代过程中出现的粒子退化和贫化 ①用建议密度产生候选值y,建议密度为 问题，作者利用遗传算法)全局寻优和保持子代多 q(x,y)=q(lz-y 1)oc exp[(x-y)2/20]. 样性的特性，以及马尔可夫链蒙特卡罗方法的收敛 (6) 性，完成粒子滤波中的重采样步骤. ②计算接受概率p, 2.1遗传算法与粒子滤波的相似性 p(z,y)=min[x(y)q(y,x)/n(z)q(z,y),1]. 粒子滤波算法和遗传算法在结构上是一致 (7) 的们，将粒子视为染色样本，每个粒子对应的重要 式中：(y)和π(x)分别为y和x的分布. 性权值视为染色样本对应的适应度函数，将标准粒 ③若u≤a(x,y),4~4(0,1),则x1=y,否 子滤波器中的再采样部分改进为遗传算法的交叉、 则x+1=x. 变异和选择过程，在状态估计问题中朝全局寻优的 2.2.3选择 方向进行，并通过交叉和变异步骤使得染色样本保 根据权值，利用轮盘赌的方法对粒子进行 万方数据北京理工大学学报 第30卷 贝叶斯估计‘41．其关键步骤是用随机采样点以及相 应的权重来表示后验概率密度，并根据这些样本点 和权重获得估计值． 1．1序贯重要性采样 粒子滤波的基础是序贯重要性采样(SIS)算法． 该算法采用一组加权随机样本{z；∽硼：)川Ns来近似 表征后验密度函数，其中{z；川i=0，1，…，N。)是 带有相应权重的支撑点的集合，其权重表示为{训：， i=1，2，…，N。}，而z啡={z—j-----0，1，…，k}表示到 惫时刻时所有状态的集合．从而k时刻的后验概率 密度可以近似表示为 Ns p(x^I z1：t)≈2：硼翘(z^一z：)， (1) i=l 权值更新为劭：。C叫卜i。丝斗窖萼掣．(2) q～z々I工卜l’z^， 式中：权重满足归一化≥：。础：一l；户(z。l z：)为k时 刻观测状态‰的似然函数；q(x'k z0，，孙)为重要 性密度函数．可以证明，随着N。一。。，式(1)的近 似结果将逐渐趋近于真实的后验概率密度p(xt Z1：t)． 1．2重采样 SIS的一个严重缺陷是退化问题，即重要性权 值的方差随着时间是递增的．经过多次迭代后，集 中对大多数权值过小的粒子进行计算没有意义．这 时要用到重采样技术，基本思想是抑制或剔除小权 值粒子，对于大权值粒子则依其权值大小进行复制， 从而把处理资源按照粒子权值的大小进行分配．但 是重采样后保留了大量的大权值粒子，这样就引起 了粒子的贫化，使粒子缺乏多样性． 2 GA—MCMC粒子滤波 为了解决在迭代过程中出现的粒子退化和贫化 问题，作者利用遗传算法[7]全局寻优和保持子代多 样性的特性，以及马尔可夫链蒙特卡罗方法的收敛 性，完成粒子滤波中的重采样步骤． 2．1 遗传算法与粒子滤波的相似性 粒子滤波算法和遗传算法在结构上是一致 的[7]，将粒子视为染色样本，每个粒子对应的重要 性权值视为染色样本对应的适应度函数，将标准粒 子滤波器中的再采样部分改进为遗传算法的交叉、 变异和选择过程，在状态估计问题中朝全局寻优的 方向进行，并通过交叉和变异步骤使得染色样本保 持一定程度的多样性． 2．2 GA-MCMC粒子重采样 交叉和变异是遗传算法的主要操作，通过交叉 保持粒子群的多样性，将马尔可夫链蒙特卡罗MC— MC方法Ⅲ引入变异操作可有效减轻粒子贫化问 题，并通过选择操作将原来的粒子集合替换为新的 更多样并且符合目标后验分布的粒子集合． 2．2．1交叉 每次对两个粒子进行交叉操作，产生的后代能 同时保持它们父代的两个粒子的特征．为防止近亲 繁殖，通过禁止父代粒子和同样的粒子配对来保持 粒子群体的多样性． 算法1：交叉算法／CROSSOVER算法 若随机数U。<P。(交叉概率P。子代粒子的数 目和总粒子数的比值)，则 z量’=凹量+(1一口)z}， (3) z}’一axB，+(1一a)x2． (4) 式中：a为交叉因子；z量和z}为k时刻父代粒子； z2’和z2’为子代粒子． 若p(zI z拿。)>max{p(z^I x2)，p(z女I z#))，接受z}’，否则以以下概率接受 p(z。l z量’)／max{p(z。；z套)，p(z^{z￡)}． (5) 对z￡’的操作也以同样的方式进行． 2．2．2变异 Markov链产生来自目标分布的样本，并且具 有很好的收敛性，能将粒子推向更接近状态概率密 度函数(PDF)的地方，使样本分布更合理．Metrop— olis—Hastings算法‘81是一种模拟上述马尔可夫链的 方法． 算法2：Metropolis—Hastings／MH变异 Metropolis—Hastings／MH变异步骤如下． ①用建议密度产生候选值Y，建议密度为 q(x，y)=口(f z—Y f)oC exp[(x—y)2／2a2]． (6) ②计算接受概率P， p(x，y)=min[n(y)q(y，z)／兀(z)口(z，了)，1]． (7) 式中：丌(3，)和丌(z)分别为y和z的分布． ③若“≤a(x，y)，“～u(O，1)，则Xk+1=Y，否 则z‘十1=z． 2．2．3选择 根据权值W：，利用轮盘赌的方法对粒子进行 万方数据