基于改进适应度函数和搜索策略的差分进化粒子滤波算法

基于改进适应度函数和搜索策略的差分进化粒子滤波算法

颗粒滤波是一种使用颗粒作为可靠的后验概率密度分布的序贯蒙特卡罗法。作为一种有效的方法，它可以处理非线性和非高斯状态的评估问题。颗粒滤波广泛应用于数据处理、目标跟踪、机器人定位、数据处理等领域。为了解决颗粒过滤权重值退化的问题，选择了重采样的大权重。重采样时，许多重采样结果中有许多重复点。经过多次重复，当被重复使用时，颗粒集中在几个地方，导致描述后的概率密度采样点太少或不足，从而影响过滤的精度，尤其是在样品有限的情况下。针对重采样所造成的粒子多样性减弱和滤波精度下降的问题,研究人员提出了粒子滤波的多种改进方法,其中将成熟的多种不同寻优方法引入重采样过程,以便快速地提取到反映系统概率特征的典型粒子逐渐成为重采样方法的研究热点.基于粒子群优化的粒子滤波方法(POS-PF)作为其中的典型代表被深入研究,使得该方法在粒子多样性和局部搜索能力上都有所提高.同时,文献中将遗传算法和蚁群算法与粒子滤波结合,有效抑制了粒子贫化的现象.文献中将多智能体协同进化机制引入粒子滤波,通过粒子间的竞争、交叉、变异以及自学习等进化行为来实现重采样过程.文献中则采用人工物理优化方法改进粒子滤波,通过模型定义了粒子间的吸引力与排斥力,使得粒子集的分布性更好.文献中提出了DE-MC(DifferentEvolution-MarkovChain)粒子滤波,将微分进化算法与MH(MetropolisHastings)采样方法相结合对粒子的分布进行优化,并实现对三维空间中人体运动的跟踪.文献中则对比了差分进化粒子滤波在不同搜索策略下的滤波精度.上述的各类方法提升粒子滤波性能的关键在于通过优化过程将粒子引导至后验概率密度取值较高的位置,但是在后验概率密度未知的情况下如何保证所提取的粒子更能反应系统的后验分布是上述方法能否优化粒子的关键.适应度函数是优化算法中的一个重要概念,用于引导群体的优化过程,目前已有的智能优化粒子滤波仅依据似然函数或粒子权值优化粒子,使得进化过程严重依赖于似然函数或粒子权值,且搜索策略具有一定的盲目性,造成大量无效粒子的产生,降低了粒子的利用效率,虽然粒子的多样性有了显著改善,但滤波精度并没有大幅提升.基于此,本文通过自适应融合系数融合粒子的权值和量测误差定义了新的适应度函数,提出了一种改进差分进化的高精度粒子滤波算法(IDE-PF).该算法利用新定义的适应度函数引导粒子的优化过程,使粒子集向后验概率密度取值较大的区域运动,同时利用新的搜索策略在保持粒子多样性的同时,尽可能提高算法的收敛速度.结果表明,与POS-PF和DE-MCPF相比,本文算法既具有较好的局部搜索能力,同时改善了粒子滤波的样本贫化现象,提高了滤波的精度,减少了算法的优化时间.1颗粒过滤和重采样1.1观测方程和态态方程粒子滤波是贝叶斯估计基于抽样理论的一种近似算法,其基本思想是寻找一组在状态空间中的随机样本对条件后验概率密度进行近似,用样本均值代替积分运算,从而获得对状态的最小方差估计.假设状态方程和观测方程分别为:式中:xk为k时刻的状态变量;yk为k时刻的观测值;f和g为非线性函数;vk和uk分别为系统噪声和观测噪声,具有方差Qk和Rk.在k时刻,粒子滤波首先通过预测采样获得新的粒子集,即并利用下式近似该时刻的后验概率密度:式中:N为k时刻的粒子数目;δ(·)为狄利克雷函数;wki为权值.依据序贯重要性采样原理,重要性权值的更新公式可表示为式中,q(xki|xik-1,yk)即为建议分布函数,当采样的粒子数目足够多时,由重要性采样定理即可保证粒子集{xki,wki}Ni=1所描述的分布逼近真实的后验概率密度.1.2采用智能优化算法优化粒子滤波粒子滤波中一个普遍问题就是粒子退化现象,即经多次迭代后,粒子的权重集中到少数粒子上,而其他粒子的权重很小,导致粒子集无法表达真实的后验概率分布.重采样是解决粒子退化问题的有效方法,该方法在评估粒子权值后,维持粒子总数不变的条件下删减低权值的粒子,复制高权值的粒子,增强粒子的采样效率,从而改善粒子退化现象,然而重采样会引起样本贫化的问题,其复制和删减粒子的策略将必然导致粒子多样性的减弱,在损失信息的同时增加了随机采样的不确定性.为了确定粒子的退化程度,常采用有效粒子数来衡量:智能优化粒子滤波在解决粒子退化问题上具有较好的效果,在一定程度上提高了状态估计的精度.但是,智能优化算法在控制粒子的多样性,以及对寻优过程的引导能力上,尚有不足.依据已有重采样的思想,在采用智能优化算法优化粒子滤波时,常以权值最大化作为优化的目标,即k时刻第i个粒子的适应度为当以先验分布作为建议分布函数时,可得适应度函数为式中:yki为xki对应的量测.而另一种常用的适应度函数为该适应度函数将最新的量测值引入采样优化过程,增强了量测值的修正作用,故在量测精度高的场合可有较好的效果.2适应度函数的引入依据已有的基于智能优化思想的粒子滤波算法,式(7)和(8)都可以作为适应度函数引导粒子的优化,但是在不同的量测环境下两者的优化效果各不相同.因此,本文将上述2种适应度函数按自适应的比例进行融合,定义了一种新的适应度函数,并在差分进化算法中引入新的搜索策略,使得IDE-PF可以达到收敛速度与寻优能力的最佳平衡,提高滤波器的性能.2.1个结论和一个变异个体差分进化算法(DE)是一种随机的并行直接搜索算法,其基本思想是从某一随机产生的初始种群开始,按照一定的操作规则不断迭代,并根据每一个体的适应度值,保留优良个体,淘汰劣质个体,引导搜索过程向最优解逼近.算法具有结构简单、易于实现、无需梯度信息和参数较少等优点,并具有多种不同的搜索策略.算法运行过程中保持种群规模不变,并定义了3种运算过程:(1)变异.对于个体Xi按下式生成变异个体:式中:Xr1、Xr2和Xr3为从进化种群中随机选取的互不相同的3个个体;F为缩放比例因子,用于控制差向量的影响大小.(2)交叉.为增加种群的多样性,引入下述交叉操作:式中,pCR∈[0,1]为交叉概率.(3)选择.交叉后的个体和父代个体Xi按下式进行选择操作生成子代个体:2.2改进差分进化算法粒子滤波中粒子的多样性是滤波器性能的一个重要指标,多样性程度越高滤波器的性能越好.同时,多样性的程度还会影响优化算法的寻优速度和局部搜索能力,多样性程度高,算法的全局寻优能力强,但局部搜索能力和寻优速度会下降.因此,如何在粒子多样性与寻优能力之间进行有效的权衡是提高算法性能的关键.差分进化算法具有多种不同的搜索策略,可分为2类:一类是基准粒子随机选取,如式(8),此时算法的全局收敛性好,但是收敛速度慢;另一类是基准粒子选择当前种群中适应度值最大的粒子,虽然收敛速度快,但是易陷入局部最优.为此,Zhu等受粒子群优化算法的启发给出了一种新的搜索策略:式中:Xbest为当前种群中的适应度值最大的粒子;F1为[-1,1]之间的随机数;F2为[0,1.5]之间的随机数.该搜索策略由于受最优粒子的引导,在保证寻优能力的同时也能提高算法的收敛速度.2.3信度标准适应度函数的引入适应度函数是衡量粒子可信度的一个标准,若适应度高,则粒子的可信度高;若适应度低,则粒子的可信度低.依据差分进化算法的演化过程,适应度低的粒子将逐步按照一定的概率被抛弃和替换,因此适应度函数的设定会严重影响粒子集进化的结果.目前,式(7)和(8)是2种常被采用的适应度函数,相关文献中对智能优化粒子滤波如何定义适应度函数并未做详细讨论.依据重采样的思路,重采样就是选择大权值粒子、抛弃小权值粒子的过程,所以权值可以作为衡量粒子可信度的一个标准.其次,量测值可以反映实际状态的信息,特别是在高精度的量测场合,故粒子的量测值与实际量测之间的差值的大小也可以作为衡量粒子可信度的标准.对于上述2种不同的可信度衡量标准,本文按照一定的比例系数将2种可信度标准进行融合,定义了新的适应度函数,并依据优化的程度,定义了自适应的融合系数.定义新的适应度函数为式中,σ为自适应融合系数,0<σ<1.通过σ可以调整2种可信度标准在最终的粒子可信度中所占的比重.令{xkg,i,i=1,2,…,N}表示k时刻进化至第g代的粒子集,g≤最大进化次数Gmax,N为粒子数,其对应的量测值表示为集合{ykg,i,i=1,2,…,N},量测值的均值:则融合系数的取值定义为式中,yk为k时刻的实际量测.在进化的初期,当部分粒子的量测严重偏离实际量测时,σ应取接近于1的值,以便快速提取到量测偏差较小的粒子;当粒子的量测值均比较接近实际量测时,则σ取接近于0的值,以便提取权值更优的粒子.从式(13)定义的适应度函数可知,量测误差|yk-yki|小的粒子适应度高,这使得在多次优化迭代后,量测值的均值yk-g逐渐接近实际量测值yk,故σ的取值在进化过程会逐步减小,满足了从进化初期到进化后期对σ取值由大变小的要求.同时,当粒子的量测均值很接近实际量测时,可认为粒子已被优化到了最佳的程度,故σ也被作为判断进化过程是否终止的条件,当σ≤σmin时则终止进化.2.4计算相关系数的选取粒子集本文IDE-PF算法的计算过程如下:(1)初始化.在k=0时刻进行采样,将所得N个粒子{x0i}Ni=1作为初始样本,初始样本的分布为x0i~p(x0).(2)重要性采样.设定k=k+1,由重要密度函数抽取当前时刻的粒子{xki}Ni=1,并计算当前量测值{yki}Ni=1,重要性密度函数为(3)差分进化重采样:(1)g=1,进化的初始粒子{xkg,i}Ni=1={xki}Ni=1;(2)对粒子集{xkg,i}Ni=1按式(12)进行变异操作,然后按式(10)进行交叉操作,得候选粒子集;(3)依据式(13)~(15)计算候选粒子集的适应度值,并按式(11)进行选择操作,所得粒子集为{xkg+1,i}Ni=1;(4)若g<Gmax且σ>σmin,设定g=g+1转入(2);否则转入下一步.(4)状态输出.将优化后的粒子集作为等权的样本{xki,wki=N-1}Ni=1,计算状态估计:(5)判断是否结束,若是,退出算法,否则转入(2).3实验结果与分析为验证IDE-PF算法的精度和运算时间等基本性能,本文利用典型一维非线性系统模型对算法的性能进行仿真,并与PF、POS-PF和DE-MCPF进行对比.实验环境为DELLInspiron1320,内存2GB,CPU为Intel-T4400.一维非线性系统模型如下:模型的系统噪声uk-1~Γ(3,2),总的观测时间T=60,实验中粒子数目分别设定为N=100和N=10,微分进化算法交叉概率pCR=0.9,最大进化迭代次数Gmax=10.实验1(粒子优化程度及粒子量测值的精度分析).在第k步预测中,重要性采样得到的粒子集被当做微分进化的初始种群,之后在适应度函数的引导下,通过多次迭代不断地优化种群的分布,直到进化代数达到规定的上限.本实验取量测噪声的分布为vk~N(0,0.00001),粒子数N=100,进化迭代上限Gmax=10,优化迭代结束的阈值σmin=0.001.图1给出了一次仿真中第20步预测(k=20)的迭代进化过程中粒子分布的变化,图2则显示了每次进化中粒子对应的量测值的变化过程.从图1中可以看到,g=1时,粒子为重要性采样得到的粒子,此时粒子分布很分散,分布区间的长度为3,对应的估计值与真实状态之间的误差达到了2.2,图2中粒子集对应的量测值与真实量测值的偏差也较大,最大偏差达到了1.9.在之后的多次进化过程中,图1所显示的粒子集分布区间长度逐渐缩小至2左右,且状态估计值逐渐靠近真实状态,同时状态估计值对应的量测逐渐靠近实际量测.产生上述变化的原因是新定义的适应度函数中量测值的修正作用.因为量测噪声小,所以量测值的修正作用强,各粒子对应的量测值不断靠近真实的量测值,同时粒子的分布也逐渐向真实状态靠近且分布相对较集中,从而对粒子的分布起到了很好的优化作用.实验2(跟踪性能对比与分析).为对比4种算法的跟踪性能,对每一种算法进行RMC=200次独立蒙特卡洛仿真,并定义k时刻的均方根误差为式中,xk,j和分别为第j次仿真中k时刻的实际和预测状态.实验中量测噪声vk~N(0,0.00001),图3所示分别给出了粒子数N=100和N=10的2种设置下4种算法时刻均方根误差的对比.同时,定义一次蒙特卡洛仿真的均方根误差公式为取粒子数N=100,增加系统量测噪声强度后,进行200次蒙特卡洛仿真并取平均值,实验结果如表1所示.从图3中可以看出,IDE-PF的时刻均方根误差最小,说明其估计精度最高,且随着粒子数的减少估计精度仍优于另外3种算法.从表1实验结果中可以看出,采用优化算法的粒子滤波误差明显小于标准粒子滤波算法,这是由于寻优过程提高了粒子的质量.但是,优化过程也增加了算法的执行时间,IDE-PF在达到优化需求的情况下即停止优化,故运算时间少于POS-PF和DE-MCPF.每种方法优化后的粒子滤波精度存在较大差别,IDE-PF的滤波精度最高,POS-PF的滤波精度高于DE-MCPF,但算法运行时间最长,由此可见粒子的多样性与寻优速度之间的平衡对最终的优化效果具有显著影响.本文所提IDE-PF算法在粒子数较少量测噪声较大的情况下,跟踪精度均好于其他3种算法.实验3(粒子多样性的对比和分析).量测噪声的分布取为vk~N(0,0.00001),粒子数目N=100,图4~7对比了PF、POS-PF、DE-MCPF和IDE-PF4种算法重采样后得到的粒子集的分布与真实状态之间的关系,以及粒子集的集中程度的对比.从图4中可以发现,PF算法在重采样后粒子的分布非常集中,这说明在重采样之前所得到的高权值的粒子数目少,而重采样后