基于改进麻雀搜索算法的粒子滤波研究

石 硬,韩玉兰,薛 丽

(宁夏大学物理与电子电气工程学院,宁夏银川 750021)

0 引言

粒子滤波[1](particle filter,PF)技术在非线性、非高斯系统问题上表现出来的卓越性与优异性使其被广泛应用于各个领域,如雷达跟踪[2]、工业领域的机器寿命预测[3]与电池寿命预测[4]、交通管制领域的人车追踪[5-6]、室内机器人定位[7-8]等。但是粒子滤波存在退化现象[9],引入重采样过程在减轻退化的同时又带来了粒子贫化现象[10]。使用大量样本虽可得到较好的预测结果但需较大的计算量,影响算法运行效率从而降低了算法性能。相关研究学者针对粒子贫化现象进行了大量的研究与改进[11-13],虽然相关改进算法都针对原有粒子滤波有所改进,但是改进后的算法仍无法完全避免重采样过程。

群智能优化算法的提出为改进粒子滤波的状态估计过程提供了新的思路,目前已经有多种群智能优化算法成功应用于粒子滤波[14-18],但群智能优化算法本身也存在相应的缺点,如易局部收敛、全局搜索能力弱等,如何针对粒子滤波的状态估计过程改进相关寻优策略,快速准确地得到全局最优解成为当前急需解决的问题。麻雀搜索算法[19](sparrow search algorithm,SSA)是一种提出于2020年的新型群智能优化算法,仿真结果证明[19]麻雀搜索算法在精度、收敛速度、稳定性和鲁棒性方面均优于灰狼优化算法( GWO)、引力搜索算法( GSA)和粒子群优化算法( PSO)等。目前还没有麻雀搜索算法与粒子滤波结合的相关研究,将麻雀搜索算法应用于粒子滤波的状态估计过程有助于群智能优化理论算法与粒子滤波的进一步应用。

为了解决粒子滤波重采样导致的粒子贫化问题,本文将麻雀搜索算法引入粒子滤波中,提出了一种基于改进麻雀搜索算法的粒子滤波算法(a particle filtering algorithm based on an improved sparrow search algorithm,SSA-PF)。SSA-PF将粒子状态值看作麻雀个体位置,通过发现者、跟随者、警戒者的迭代寻优更新粒子位置,引导粒子群体逐渐向状态估计的高似然域移动,整个过程保留了所有粒子信息,不需要重采样过程,从根本上解决了粒子贫化问题。并且,为了进一步提高滤波性能,SSA-PF针对麻雀搜索算法直接应用于粒子滤波状态估计时出现的全局搜索能力不足、样本分布不合理等问题综合粒子滤波求解思想进行了相应的改进:使用Logistic-tent map初始化分布以提高种群多样性,帮助算法增强后续解的质量;加入比例系数以及使用新的发现者更新策略增强SSA-PF的全局搜索能力,同时引入动态权重协调前期全局大范围搜索与后期局部精确搜索;改进麻雀搜索算法的追随者更新策略,使粒子分布更趋于合理的同时提高样本多样性;引入蚂蚁随机游走策略增大搜索空间,进一步帮助算法跳出局部最优。

1 传统粒子滤波算法

贝叶斯滤波非线性动态过程表示为:

xk=f(xk-1,uk-1)

(1)

yk=h(xk,vk)

(2)

式中:xk与yk分别为k时刻对应的状态值与观测值;f(·)与h(·)分别为状态函数与观测函数;uk与vk分别为过程噪声与测量噪声。

为了方便表示,用Xk=x0∶k={x0,x1,…,xk}、Yk=y0∶k={y0,y1,…,yk}分别表示一段时间内的累计状态与观测。贝叶斯滤波的预测阶段由k-1时刻的后验概率密度p(xk-1|||Yk-1)得到当前时刻状态量的预测概率密度p(xk|||Yk-1),预测方程为

(3)

贝叶斯滤波的更新阶段由k时刻的观测量p(yk|||xk)修正p(xk|||Yk-1)得到k时刻的后验概率密度p(xk|||Yk):

(4)

贝叶斯滤波在在遇到复杂的概率分布形式时很难求出积分的解,常用基于蒙特卡洛原理的粒子滤波,将积分运算转变为样本加权和运算,使用易于采样的重要性分布函数q(xk|||Yk)的样本加权和来逼近后验概率密度p(xk|||Yk):

(5)

最终输出当前时刻状态值:

(6)

然后进行重采样过程后开始下一时刻的滤波过程。

2 麻雀搜索算法分析

为了更好地将麻雀搜索算法应用于粒子滤波的状态估计过程,SSA-PF将每个粒子的状态值看作麻雀种群的个体位置,位置越好的麻雀个体相当于权值越高的粒子,其中,位置越好的麻雀个体与真实值越接近,为了评价每个麻雀个体位置的好坏程度,本文结合最新观测信息为SSA-PF设计了新的适应度函数:

f=|||znew-zpred|||

(7)

式中:znew为最新的测量值;zpred为预测值。

f值越小代表该麻雀的适应度越高,其表示的粒子与实际位置的观测值越接近。

从式(6)可以看出粒子滤波的核心思路之一是利用粒子集合的均值作为滤波器的估计值,因此合理的分布需要粒子很好的“覆盖”真实值,为了得到较好的滤波效果,麻雀群体需要找到最优点的同时合理分布在最优点附近,本节结合该思路对麻雀搜索算法进行分析,指出麻雀搜索算法直接指导粒子更新时存在的问题,以便后续进行相应的改进。

麻雀搜索算法中[19],假设种群有n只麻雀,则种群位置X可以表示为

(8)

式中:xij为第i只麻雀所处第j维中的位置;n为麻雀种群的数量;d为向量空间的维度。

个体各自对应的适应度函数F为

F=[f(x1),f(x2),f(x3),…,f(xn)]T

麻雀搜索算法中的发现者作为位置最好的一部分群体,主要为种群提供寻找食物的方向和大体位置。发现者的位置更新式(6)为

(9)

(a)Niter_max=1 000时y值的分布

除去位置最好的发现者,其他麻雀群体称作跟随者,他们主要跟随发现者来获取食物,发现者与跟随者的身份是有可能发生转换的,位置更新后适应度较高的跟随者会变成发现者,但二者的比例是确定的。跟随者的位置更新公式为

(10)

警戒者占种群比例的10%～20%,它们是随机选择的,既可以是发现者也可以是跟随者,主要负责对种群的预警。三者通过位置及关系的不断更替完成觅食过程。警戒者位置更新方式为

(11)

当fi≠fg时,表示该麻雀处于种群的外围,易遭到攻击,它将飞向最优位置附近;当fi=fg时,意味着该麻雀处于种群中心,它将向其他麻雀靠拢来躲避捕食者。

3 麻雀搜索算法改进的粒子滤波

根据2小节的分析,本节对麻雀搜索算法进行相应的改进,保证快速准确找到全局最优点的同时大部分群体也合理分布在最优点附近,从而进一步提高麻雀搜索算法与粒子滤波的适配性,增强SSA-PF的综合滤波性能。

3.1 Logistic-tent map初始化种群

混沌映射被用于生成混沌序列,在优化领域,可根据混沌序列的遍历性与随机性代替伪随机数生成器初始化种群以提高种群多样性。文献[22]提出的Logistic-tent复合混沌系统融合了Logistic复杂的混沌动力学特性和Tent混沌系统较快的迭代速度等特点,将该混沌系统引入SSA-PF初始化种群有助于为算法全局搜索过程的种群多样性奠定基础,提高后续迭代寻优所得解的质量。Logistic-tent数学表达式为

(12)

图2分别为二维空间下随机初始化种群分布与Logistic-tent map映射后的种群分布,从图2可以看出经过Logistic-tent map映射后的初始化种群分布更分散,重合个体更少。

(a)随机初始化分布

3.2 发现者位置更新公式改进

发现者在群体中起引领作用,其位置更新结果直接影响算法的寻优性能,而发现者搜索范围的广度直接决定算法能否找到更好的位置。本文针对上述分析对SSA-PF发现者更新公式做了2方面的改进:一方面,针对麻雀搜索算法直接用于优化粒子滤波状态估计时,因Niter_max较少导致发现者收敛速度过快,缺少大范围搜索进而影响状态估计精度的问题,引入比例系数保证R2

(13)

式中:Y为比例系数;Niter_max为SSA-PF的最大迭代次数;M为1行d列矩阵,M的每个元素值服从期望为1、方差为ω2的正态分布,记为M～N(1,ω2);ω的值依赖当前迭代次数与最大迭代次数满足ω=ωmax-[Niter(ωmax-ωmin)/Niter_max];Niter为当前迭代次数;ωmax、ωmin为权重的最大值、最小值。

通过调节Y可以控制SSA-PF的发现者收敛速度,避免当Niter_max较小时发现者收敛速度过快。使用ωmax、ωmin保证发现者进行适度的空间探索。采用自适应权重来动态调整高斯模型的标准差,迭代前期降低发现者个体对于自身位置的依赖性,使发现者前期进行更广泛的搜索,减少发现者搜索时的盲点区域,后期随着麻雀种群逐渐向目标值靠近,减小权重增强发现者的局部搜索能力,同时,相比于原来发现者更新时每个维度移动相同的距离,改进后的发现者更新公式使麻雀群分布更合理,种群多样性更强。

3.3 跟随者位置更新公式改进

(14)

3.4 蚂蚁随机游走策略

发现者、跟随者、警戒者公式中都存在向零点或最优位置收敛的行为,虽然存在相应的跳出局部最优的措施,但是算法依然存在陷入局部最优的风险,因此本文引入蚁狮优化算法[23]中的蚂蚁随机游走策略对每次更新后的麻雀种群进行随机游走,进一步扩大全局搜索范围,降低算法陷入局部最优的概率。随机游走的过程在数学上可以表示为

X(t)={0,cussum[2r(t1)-1],…,cussum(2r(tn)-1}

(15)

式中:X(t)为蚂蚁随机游走的步数集;cussum为累加公式;t为随机游走的步数;r(t)为取1或0的随机函数。

由于可行域存在边界,不能直接用式(15)更新蚂蚁的位置。为确保蚂蚁在可行域范围内随机游走,需根据式(16)对其进行归一化:

(16)

3.5 算法实现步骤

(1)初始化麻雀搜索算法相关参数。

(2)使用式(12)Logistic-tent map初始化种群分布。

(5)开始循环迭代,利用式(11)、式(13)、式(14)引导麻雀群不断进行位置更新,对更新后的麻雀群引入随机游走策略,若游走后的适应度更高,则代替原有的麻雀位置。

(6)判断是否满足迭代次数阈值,不满足则返回步骤(4)。

(8)权值归一化处理并进行状态输出:

(17)

4 仿真实验与分析

仿真硬件环境为Intel(R) Core(TM) i7-11700、8 GB内存台式计算机,软件环境为MATLAB R2019a。假设k=1时刻小车处于100 m×100 m场地中的(60 m,15 m)位置,通过预测小车在二维空间中的弧线运动验证所提算法的滤波性能。使用的测量模型的状态方程以及观测方程为:

x(k)=x(k-1)+l[-cos(k-1)θ,sin(k-1)θ]

(18)

z(k)=x(k)+v(k)

(19)

式中:x(k)为k时刻小车在二维空间中的真实坐标位置;k∈[1,T],时间步长(小车移动总步数)T=20;l为小车每次移动的距离(步长);旋转的角度θ=π/T(rad);z(k)为k时刻的观测值;v(k)为一个噪声强度为10lgR(dBw)的高斯白噪声矩阵。

为有效验证所提算法的综合性能,实验使用标准粒子滤波(PF)、灰狼算法优化粒子滤波(GWO-PF)、粒子群优化粒子滤波(PSO-PF)与所提算法做仿真对比。

4.1 算法滤波精度测试

使用均方根误差评价实验算法的滤波精度,均方根误差公式为

(20)

(a)滤波状态估计

(a)滤波状态估计

(a)滤波状态估计

从图3～图5可以看出,同等粒子数下SSA-PF的预测轨迹与实际轨迹的重合度最高且均方根误差最小,这是因为除了麻雀搜索算法本身较强的寻优机制,本文结合粒子滤波的求解过程对麻雀搜索算法更新策略进行了改进,在提高全局搜索能力的同时使用自适应权重平衡了前期全局搜索与后期局部搜索,保证粒子更新后更接近真实值,且合理分布在真实值周围,最后引入蚂蚁随机游走策略控制粒子游走进一步提高滤波精度。另一方面,不同粒子数下SSA-PF都有着较低的均方根误差,且随着时间步长变化没有较大起伏,虽然某些时候误差稍高于其他对比算法,但总体误差最低,体现出所提算法较好的稳定性。

将每个算法的T个RMSE值求平均值得到表1所示的平均均方根误差对比(T-RMSE),更为直观精确地显示不同算法滤波精度。

表1 平均均方根误差对比

从表1可以看出,随着粒子数的增加,各算法的滤波精度都有所提高,同等粒子数量下SSA-PF平均均方根误差的平均值小于其他对比算法,且不需要较大的样本数量时就能拥有较好的预测效果,综合上述实验证明了所提算法拥有较高的滤波精度和滤波稳定性。

4.2 粒子多样性测试

为了测试相关算法的粒子多样性,令n=100,增加时间步长,T=50,降低步长l=1.5 m,观察k=9,k=25,k=46时不同算法的粒子分布情况,结果如图6所示。

(a)k=9时算法粒子状态分布

从图6可以看出3种时刻下,PF与GWO-PF粒子分布比较集中,本文提出的SSA-PF与PSO-PF的粒子大部分靠近在真实值附近,在其他区域也有一定的分布。这是由于PF的重采样过程会逐渐去除低权值粒子,让高权值粒子不断复制使粒子逐渐集中在少数几个状态值上,因此与图3～图5的(a)图对应,粒子滤波预测轨迹需要随着小车的移动才会逐渐趋于稳定,但这也导致粒子过度集中缺乏多样性。本文提出的SSA-PF没有使用传统的重采样过程,未涉及粒子的直接舍弃,有效避免了粒子贫化现象,同时使用改进后的发现者与跟随者更新公式和麻雀搜索算法本身的警戒者机制使粒子始终有一个较好的分布,符合所述粒子滤波核心思想,即使在运行后期也能够保持较好的样本多样性。

5 结束语

为了解决粒子贫化现象本文首次将麻雀搜索算法与粒子滤波结合提出了一种基于改进麻雀搜索算法的新型粒子滤波算法(SSA-PF),采用改进后的麻雀搜索算法优化粒子滤波。麻雀搜索算法收敛速度快、稳定性高、结构简单但直接应用于粒子滤波求解时存在全局搜索范围不足导致的局部最优和中后期种群分布不符合粒子滤波求解思想等缺点。本文首先使用Logistic-tent混沌映射提高种群多样性;为SSA-PF发现者更新公式加入比例系数稳定收敛速度,同时提出了新的发现者策略更新粒子,提高全局搜索能力的同时保证了前期全局搜索与后期局部搜索;优化跟随者更新策略来进一步提高种群分布的合理性;最后使用蚂蚁随机游走策略进一步帮助算法跳出局部最优。群智能优化理论算法优化粒子滤波能有效解决粒子贫化现象,本文所提算法不需要大量粒子即可达到较好的预测精度。仿真实验结果证明:本文所提的SSA-PF相对其他对比算法滤波精度最高,粒子分布合理,状态估计所需样本数量较少,总体来说滤波性能较强。