改进的布谷鸟算法优化粒子滤波研究

王晓华，聂腾腾

西安工程大学 电子信息学院，西安710048

1 引言

粒子滤波器（Particle Filter，PF）是非线性和非高斯状态估计最有用的工具之一[1-3]。但由于重采样引起的样本贫化缺陷限制了估计的准确性[4-5]，学者们采取了很多办法来改进滤波器性能。传统方法[6-7]是通过改进重采样来优化粒子滤波。近年来，将生物智能算法[8-9]如萤火虫、蝙蝠、布谷鸟算法等被引进到粒子滤波中，解决粒子贫化退化等问题，具有良好的发展前景。文献[10]利用萤火虫算法迭代寻优的思想优化粒子分布，但萤火虫算法本身存在着对于初始解分布的依赖性；文献[11]提出了基于自控蝙蝠算法优化粒子滤波的机动目标跟踪方法，但蝙蝠个体本身缺乏变异机制，一旦受到某个局部极值约束后自身很难摆脱。CS算法参数较少：除了种群规模之外，CS算法基本上只有一个参数pα需要调整。而算法的收敛速度对参数pα不敏感，这意味着CS算法的通用性很好，鲁棒性较强，易于与粒子滤波结合。Han等[12]结合布谷鸟搜索算法与粒子滤波器（CS-PF）来估计测量信号的缺陷轮廓，并成功应用于故障检测中，所提的方法明显优于单独使用布谷鸟算法，但算法的搜索效率还有待提高。黄辰等[13]将多策略差分变异过程引入布谷鸟算法中，增加排队优选机制，并将改进的布谷鸟算法应用到粒子滤波（ICS-PF）中，解决了粒子滤波算法中的粒子贫化问题。但上述方法，并未解决算法局部寻优与全局寻优的矛盾。

为协调布谷鸟算法局部寻优与全局寻优的能力，本文对布谷鸟算法进行改进：一方面，在Lévy飞行过程中改变步长值α，以保证全局搜索时的种群多样性；另一方面，改进布谷鸟算法的宿主鸟卵的概率pα，以调整局部随机搜索获得最优解的能力，并将改进的布谷鸟算法用来优化粒子滤波，提出一种改进的布谷鸟算法优化粒子滤波方法（Particle Filter Based on Cuckoo Search，CS-PF），算法的局部寻优与全局寻优得到平衡，能够更有效地探索搜索空间，进一步提高了估计精度。

2 主要算法基本原理

2.1 布谷鸟算法

剑桥大学学者Yang和Deb通过对布谷鸟寻窝产卵行为的模拟，提出了一种全局搜索的布谷鸟搜索（Cuckoo Search，CS）算法[14-15]。布谷鸟也叫杜鹃。该算法是受一些杜鹃种群的行为和Lévy飞行的启发而发展起来的。

布谷鸟执行Lévy飞行以寻找新巢，公式（1）是寻找宿主鸟窝的位置和路径的更新公式：

其中，t是迭代次数，u和v都遵循正态分布。

对于第k个宿主鸟窝，迭代时第d维的位置更新为：

其中，bnestd是第d维度中全局最佳鸟窝的位置；r是正态分布后的随机数，均值为0，方差为1；c1是步长系数，通常设置为0.01。宿主巢中的每个布谷鸟的卵都有可能被其宿主鸟发现，被发现的概率为pα。

2.2 改进布谷鸟搜索算法

CS是一种简单，参数少，易于实现的算法，但在算法后期会出现算法搜索速度慢、精度不高等缺点，所以需要通过优化CS来提高算法的性能[16-18]。优化的目的是提高布谷鸟的全局搜索能力，通过考虑正确的产卵时间来提高布谷鸟卵的繁殖力，以及刚孵出的布谷鸟雏鸟所采取的行为。布谷鸟优化的所采取的假设是：

（1）将鸟卵放在随机选择的巢中。

（2）只有具有最佳卵的巢才能让下一代存活下来。

（3）预先确定宿主巢（通常是其他物种）的数量，并且估计宿主发现卵的概率为pα∈(0,1)。

CS中引入的参数pα、λ和α分别帮助算法找到全局和局部改进的解。参数pα和α是解向量微调的非常重要的参数，可以用于调整算法的收敛速度。传统的CS算法对pα和α都使用固定值。这些值在初始化步骤中设置，并且在新一代中不能更改，该方法的主要缺点出现在寻找最优解的迭代次数中，这可能需要更多次迭代才能找到最优解。如果pα的值很小并且α的值很大，则算法的性能将很差并且导致迭代次数的显著增加。如果pα的值很大而α的值很小，则收敛速度很快，但可能无法找到最佳解。

所以关键在于调整pα和α。为了提高CS算法的性能并消除考虑pα和α的固定值所导致的缺点，改进的算法使用变量pα和α。

通过改进的布谷鸟搜索算法中pα和α的值，根据公式（4）～（6）每次迭代进行调整。

其中，变量c是当前迭代次数，所选常量n是迭代总次数。其中寻找到最佳鸟窝位置时迭代的总次数就是改进布谷鸟算法停止寻优的标准。

2.2.1 改进CS收敛速度

改进的布谷鸟的收敛性相对于CS算法收敛速度提高了，因为迭代次数减少了。通过调整pα和α的值，避免了因pα和α的值过大或过小而导致算法的收敛性降低，如pα的值如果很小而α的值很大，则算法的性能将很差并且导致迭代次数的显著增加，收敛速度慢；如果pα的值很大而α的值很小，则收敛速度很快，但可能无法找到最佳解。所以动态调整pα和α的值，可以加快算法的收敛速度。

2.2.2 改进CS种群多样性

改进的CS算法种群多样性提高。首先鸟窝更新迭代后通过式（4）～（6）来进行算法改进；然后根据迭代次数动态地计算鸟窝放弃概率pα，通过不同的概率来动态地调整不同时期的种群多样性，使得算法可以灵活地调整种群多样性，提高了算法的收敛速度。

2.3 基本的粒子滤波

2.3.1 标准粒子滤波

粒子滤波器最初由Gordon于1993年引入，作为用于估计非线性和非高斯状态的自举滤波器[19]。下面简要介绍粒子滤波的过程[20]，粒子滤波算法过程图如图1所示。

粒子滤波器的递归过程包括两个步骤：

图1 粒子滤波算法过程图

（1）预测。

（2）更新。根据给定的在线测量序列zm={zi:i=1,2,…,m}进行更新。

在预测步骤中，在时刻m被确定为：

使用公式（7）给预测的粒子分配标准化的权重：

其中，j∈1,2,…,N,δ()⋅由xm-1和wk-1值所表示的狄拉克函数δ。在重抽样中，新样本通过重新采样N次生成估计的，以便对于任何j

2.3.2 粒子多样性度量

文献[10-11]讲述了生物智能算法会增加粒子滤波中的粒子多样性，文献[8]给出了粒子多样性度量的指标。

2.4 改进布谷鸟搜索算法与粒子滤波结合

为克服传统的粒子滤波算法中存在的粒子贫化问题，本文将改进的布谷鸟算法引入到粒子滤波算法的重采样过程中。改进CS-PF算法具体实现步骤如下：

（1）初始化。在初始时刻k=0时按照初始样本分布p(x0)进行采样，产生的N个粒子作为初始样本{ xm(0)}( m=1,2,…,N)，xm(k)服从重要性密度函数。

（2）设置每个粒子的权重为wj=1/N。

（3）采用改进的CS来优化粒子，模拟布谷鸟优化算法的全局搜索行为：

①进入优化的初始粒子

②将该粒子样本引入改进CS中，根据式（4）～（6）对每次迭代进行调整，得到进化后的新粒子集，当迭代到鸟窝的位置越来越接近最佳位置时，步长越小，当迭代到鸟窝的位置离最佳位置较远时，步长越大。这样，根据上一次迭代的结果来动态更新本次迭代的移动步长，算法的搜索速度和寻优精度都有较大的提高。在改进的布谷鸟算法中，所采用的适应度函数为：

③改进的CS的搜索策略去执行粒子滤波重采样过程。

（4）计算新粒子的重要性权值并进行归一化处理。

（5）输出粒子状态。求改进的CS-PF后输出粒子的均值。

2.4.1 改进CS-PF收敛性分析

其中，uk(B)为算法D第k次迭代的结果在集合B上的概率测度。

定理1当鸟窝位置的群体内部迭代趋于无穷次时，群体状态序列必将进入最优状态集H。

定理2改进的CS-PF算法收敛于全局最优。

证明 首先改进的CS-PF算法每次迭代都保存了群体最优位置，保证了适应值的非增性，所以随机算法的收敛满足条件1。其次由定理1知，改进CS-PF算法经过连续无穷次迭代，鸟窝位置的群体序列必将进入最优状态，所以，连续无穷次搜索不到全局最优解的可能性是0。因此，满足随即算法的收敛条件2，故改进的CS-PF算法收敛于全局最优。

2.4.2 改进CS-PF时间复杂度

标准粒子滤波的时间复杂度受初始化粒子个数N和重采样粒子数N1时的影响，粒子数越多，时间复杂度越高，所以它的时间复杂度为T(n)=O( N+N1)。

从改进CS-PF的详细过程来分析，影响算法效率的因素主要有两个：一是粒子数N2；二是宿主发现卵的概率为pα和随机步长α。计算给定个体的目标函数的执行时间是个体维数n的函数f(n)，时间复杂度为O( n+f(n))，则总体时间时间复杂度为T(n)=O( N2+n+f(n ))。其中N2＜N，大多数情况下，给定个体的目标函数的执行时间是个体维数n较小，所以改进的CS-PF具有较低的时间复杂度。

3 实验仿真

实验环境是在Inter Core i5-3230M，内存8 GB的华硕笔记本上运行的，软件环境Matlab2014b，本文仿真对象采用的非线性系统模型如下：

此模型是研究各种PF算法性能时的常用模型。其中x(t)是系统t时刻的状态，u(t)是系统状态方程中的零均值高斯噪声，y(t)是系统t时刻的测量值，v(t)是测量方程中的零均值高斯噪声。初始状态x=0.1，过程噪声和测量噪声分别是1，粒子数N=200，取不同的pα值，观察高似然区平均粒子数M1和每次平均更新的粒子次数M2。

通过实验仿真的方法，确定重要参数pα的取值范围，并验证算法的有效性。

pα的合适区域为（0.2～0.3）。如图2所示：pα的值影响着算法的运算量。当pα＜0.2时，高似然区的粒子数平均有44.37个，粒子平均更新的次数是42.38次，这样使得算法运算量增加，粒子多样性丧失，如果增加粒子数，算法的实时性也会受到影响。当pα＞0.45时，大部分粒子没有更新，在高似然区的粒子数也较少，这样会使算法精度降低。所以要保证粒子足够独多分布在高似然区，且运算量不能太高，要保证算法的实时性，即选择合适区域为（0.2～0.3）。

实验中使用的粒子数为N=200个，观测时间为T=60，滤波步数k=100,pα=0.25，将改进的CS-PF与标准的PF、EK-PF、CS-PF、ICS-PF进行100次独立实验，实验的目的是比较各算法的非线性系统状态估计及均方根误差。均方误差定义为：

实验结果由图3可以看出，改进的CS-PF算法精度高，EK-PF、CS-PF、ICS-PF算法精度较高，而PF算法精度较差。这是因为PF算法采用了先验概率转移密度作为重要性采样，忽略了当前时刻的测量值，所以精度较差；而改进的算法均结合了当前系统的测量值信息的重要性采样密度，所以精度相对较高。

图2 粒子数随着pa值变化的曲线图

表1 不同算法估计误差对比

表1是经过100次独立实验得出的不同重要性采样密度的粒子滤波算法的均方误差的均值以及运行时间的均值对比结果。对于不同的粒子数，基本PF算法的均方误差最高；EK-PF低于PF算法，但相比CS-PF、ICS-PF、改进CS-PF算法相比要高，其中改进的CS-PF的RMSE值最低。其中，对于不同的粒子数，改进的CS-PF虽然滤波精度比基本PF低，但运行时间却高。

为进一步比较标准PF算法与改进CS-PF算法的粒子多样性，选取粒子N=50、100、150、200，观察粒子在空间的状态如图3所示。

图3 状态估计结果对比图

由图4可以看出，随着粒子数的增多，改进的CS-PF粒子在状态空间的分布更加广泛，在高概率值的附近粒子数较多，低概率值旁粒子较少，所以改进的CS-PF算法能够减少粒子贫化，增加粒子的多样性。

由表2观察ρ值可以得知，改进的CS-PF比PF的粒子多样性更好，说明改进的CS-PF算法增加了粒子多样性，从而保证估计精度的提高。

表2 PF与改进CS-PF多样性指标ρ对比

4 结论

布谷鸟算法是一种全局寻优能力强，参数少，易于与其他算法结合但也存在收敛速度慢、种群多样性较差等问题，为改善算法本身的不足，通过改进pα和α值来改进布谷鸟算法，平衡布谷鸟算法局部寻优与全局寻优，然后用改进的CS的搜索策略来取代粒子滤波重采样步骤，以避免粒子样本贫化。粒子通过模拟布谷鸟个体，使粒子在全局搜素范围内寻找到最优的位置，也就是使粒子更准确地分布在真实值的附近。仿真结果表明：改进的布谷鸟优化粒子滤波，能有效解决粒子在滤波过程中出现的粒子贫化的问题，增加粒子的多样性，运算精度也较大提高。

图4 粒子空间图