基于鸽群优化改进的粒子滤波算法*

韩 锟, 张 赫

(中南大学 交通运输工程学院, 湖南 长沙 410075)

0 引 言

粒子滤波(particle filtering,PF)通过非参数化蒙特卡洛方法实现递推贝叶斯滤波[1],摆脱了传统解决非线性滤波问题时,随机量必须满足高斯分布的制约条件[2],使其能够在无线定位、金融与经济学、参数估计、目标跟踪[3～5]等非线性系统下,展现出明显的优越性。然而,传统的PF在重要性采样后会出现粒子退化问题,通过重采样[6]后又会导致粒子贫化现象[7]。而且状态预测过程中往往需要大量粒子,这会使得计算效率低下[8]。为了解决上述问题,Li T等人[9]提出确定性重采样,张光等人[10]采用正则化方法,罗颖等人[11]提出智能采样,均有效缓解粒子退化问题,但无法从根本上解决粒子贫化问题。

将群体智能优化算法与PF结合是目前PF发展的一个较新的思路[12],主要是将粒子看作生物群体的个体,通过模拟生物集群的运动规律调整粒子的分布,由于其过程并未舍弃权重低的粒子,能够从根本上避免粒子贫化现象[13]。目前,已先后有将遗传算法、粒子群算法、人工鱼群算法、萤火虫算法等智能优化算法与PF结合的实例[13～16]。本文结合最新的鸽群优化(pigeon-inspired optimization,PIO)算法[17,18]以及PF[19]的特点,对鸽群优化2种算子加以改进,并引入自适应交叉操作,保障粒子多样性。通过模型仿真实验表明本文所提算法在保证粒子多样性的同时能够很好地提高状态估计精度与稳定性。

1 PIO算法

PIO算法基本流程主要由以下两种算子分别进行的迭代循环组成[18]：

1)地图和指南针算子(map and compass operator)：在搜索空间随机初始化种群数量为N的鸽群,每只鸽子的位置和速度依据式(1)进行迭代更新

(1)

式中xgbest为当前全局最有位置,R为地图与指南针因子,t为当前迭代次数。

2)地标算子(landmark operator)：每次迭代循环中,适应度较低的那一半鸽子被剔除。余下的鸽子以其中心位置作为导航继续飞行,设fitness(x)是鸽群适应度函数,位置更新公式为

(2)

(3)

2 基于PIO算法的PF

标准PF过程中,经过重要性采样得到N个粒子后,此时利用PIO算法,对粒子群体进行两种算子运算,使粒子不断向高似然区域靠近。然而PIO算法存在着极易陷入局部最优的问题,需要对鸽群优化过程进行适当修正与改进。

2.1 速度更新改进策略

由PIO算法流程可以发现PIO算法与粒子群算法有相似之处,两者都遵循以下规则：向目的地运动和向群体的中心运动[20]。但2种算法也存在着明显的不同,粒子群算法每次迭代都是用速度惯性、粒子本身最优值以及种群最优值一起决定下一位置。鸽群算法中速度的更新主要依赖于指南针因子、迭代次数以及当前全局最优值等。针对不同问题,两种算法结果会不同。因而本文联合两种更新公式,设计鸽群速度更新为

(4)

通过调节α和β的值,充分利用两者速度各自更新优势。

2.2 地标算子改进策略

PF最终状态输出依赖的是所有粒子的位置,将PIO算法与PF结合时不能舍弃低权重的粒子,这同时也保障了粒子多样性。本文改进地标算子策略如下：每次迭代循环中,首先对种群的适应度进行排序,适应度较高的那一半鸽子,以其中心位置作为当前所有鸽子的导航地标,鸽群向该位置飞去,然后再随机飞出继续搜索,如此循环直到达到最大迭代次数或是设定的精度为止。改进后地标算子为

(5)

式中 (2rand-1)为[-1,1]间的一个随机数,表示个体搜索的随机方向;h为最大搜索半径。

2.3 自适应交叉因子

(6)

式中pc1与pc2为交叉概率的变化范围,fb为两个交叉个体中较大的适应度值,fmax为种群中最大适应度值,favg为种群适应度平均值。可以使得适应度值接近最优的那部分个体也可以保持一定的交叉概率,这部分个体经过交叉运算以后,可增加新产生的子代个体中优秀个体的数量。

3 算法设计

本文将最新量测值引入采样过程,定义适应度函数为

(7)

式中ηk为测量噪声方差,zk为最新观测值,zpre(i)为观测预测值。

算法流程如下：

1)初始化参数：粒子数N,2种算子最大迭代次数T1max,T2max,最大速度vmax,地图与指南针因子R,学习因子c1,c2,α,β的值以及自适应交叉概率范围。

4)根据式(7)计算每个粒子适应度值,并找出当前全局最优值位置。

5)给予N个粒子随机的速度Vi,以xi作为个体历史最优位置,适应度值作为各自历史最优值pbest,并找出粒子中最大适应度值以及对应坐标gbest。对种群分布进行鸽群优化。

地图和指南针算子优化：

1)根据式(4)、式(1)更新每个粒子的速度和位置,重新计算适应度值。

2)由式(6)确定2个随机粒子的交叉概率,随后进行交叉操作。

3)重新计算适应度值,更新pbest和gbest。

4)判断迭代是否达到最大次数T1max,若是,则结束循环;否则,继续步骤(1)。

地标算子优化：

1)将粒子的适应度值进行排序,取适应度值较大的一半鸽子的中心作为导航地标。

“现在，我等对于但采氏有两法：一、彼若于二月底回国，则月薪送至二月止。二、若彼仍继续工作(无论在宁在平)，则按月送薪，至彼归国之月止。至于暂领生活费办法，由于我等爱国爱院的热心；彼是外国人，不便以爱中国之心责之；彼在本院，时期虽短，即将解约，亦不便以爱院之心责之。彼抱一片热心而来，不意因水土不服，夫妇均大病，几丧其生命。物质精神上之损失已不少，稍加优待，当能为诸同事所谅解。”[11]22

2)所有鸽子飞向中心位置,再按照式(5)随机飞出,重新计算适应度值。

3)根据式(6)确定2个随机粒子的交叉概率,随后进行交叉操作。

4)重新计算权值,找出适应度值较大的一半鸽子的中心位置。

5)判断迭代是否达到最大次数T2max,若是,则结束循环;否则,回到步骤(2)。

4 模型仿真实验

为了验证本文算法的有效性,对比了标准PF、遗传算法优化PF(genetic algorithm-PF,GA-PF)、粒子群优化PF(particle swarm optimization-PF,PSO-PF)以及鸽群优化粒子滤波(PIO-PF)在粒子总数为50和100时的滤波仿真实验。采用单变量非静态增长模型作为仿真对象,模型为

(8)

式中wk和vk皆为零均值高斯噪声,设系统噪声wk方差Q=1,测量噪声vk方差R=1,迭代次数T为50,GA-PF中交叉概率为0.7,变异概率为0.05。

取均方根误差(root-mean-square error,RMSE)作为算法估计精度的判定值,RMSE公式为

(9)

以RMSE的方差作为算法的稳定性判定依据,方差越低,表明算法稳定性越好。图1为4种算法粒子数N=100时,独立运行100次RMSE仿真结果,以及算法分别在不同粒子数下100次独立实验的RMSE值。

图1 仿真对比结果

与标准PF,GA-PF以及PSO-PF相比,本文所提PIO-PF算法状态预测曲线与实际状态相似程度最高。而图1(c)和图1(d)中PIO-PF无论在粒子数为50或是100时,RMSE曲线均最低,表明PIO-PF算法要优于其他3种算法。表1中数据为每种算法独立运行100次后的均方跟误差平均值以及方差,从中可以看出,PIO-PF的均方根误差以及方差最低,且在粒子数为100时两者皆小于1,当粒子数为50时,其误差值也比粒子数为100的PF以及PSO-PF算法低,与GA-PF也只有0.01左右的差距,说明PIO-PF能够用较少的粒子达到所需的精度。而均方根误差方差体现算法预测的稳定性,PIO-PF也是最低的,当粒子数越多时更为明显。

表1 实验结果

5 结 论

本文将PIO算法应用到PF中,驱动粒子不断向高似然区域移动,更加接近真实分布。在单变量非静态增长模型仿真实验中,粒子数为100时,PIO-PF实验结果均方根误差均值为0.844 1,RMSE方差为0.452 8,算法精度、稳定性均高于同类其它算法。相对于标准PF,本文所提算法精度提高了45 %,稳定性提高了72 %,且滤波过程所需粒子数也大幅减少。