鲸群优化的粒子滤波算法研究

武风波，刘 瑶，朱代先，王明博

（西安科技大学 通信与信息工程学院，陕西 西安 710600）

引言

基于卡尔曼滤波理论的滤波算法运用环境有限，在非线性、非高斯系统中其性能会大大降低。基于蒙特卡罗和贝叶斯滤波方法的粒子滤波（particle filter，PF）算法不受线性化误差和高斯噪声假定的限制[1]，适用于由状态空间模型表示的任何非线性或非高斯系统。它已广泛应用于目标跟踪、机器人定位建图、数据分析、图像处理、卫星导航动态定位等研究领域。

在标准的粒子滤波算法迭代后期，除了少数粒子，大多数粒子的权重值都小到可以忽略不计，这些小权重粒子滤波性能差，这就是粒子权值退化现象。如果继续迭代，不仅会造成计算资源的浪费，还会使滤波精度降低，因此引入重采样技术，可以改善粒子退化现象。然而有效粒子数目减少，会带来粒子贫化问题，虽然通过大量的粒子可以取得较好的滤波效果，但是算法的复杂度和计算量也会随之增加。为此，国内外学者进行了大量研究，文献[2]使用广义回归神经网络调整粒子样本，使其更接近后验概率密度，提高滤波精度。文献[3]将无迹卡尔曼滤波和权值优化方法相结合，以无迹卡尔曼滤波作为重要性密度函数对粒子状态进行优化，指导粒子采样，并引入影响因子优化粒子权值。文献[4]提出了基于误差椭圆重采样的粒子滤波算法，通过建立具有不同置信水平的误差椭圆，根据粒子的几何位置将粒子分层，实现基于粒子位置的误差重采样。这些算法都在一定程度上提高了滤波性能，但运行过程中仍然可能会舍弃掉部分有效粒子，均未从本质上完全消除粒子贫化的问题。

群智能优化理论为粒子滤波算法提供了一个新的改进思路，经典的群智能算法具有稳健性、强搜索性、强寻优性等特点，目前国内外已有许多学者将群智能优化理论成功应用到粒子滤波研究中。如基于引力场的粒子滤波[5]在粒子重采样中引入引力场优化思想，将采样后的粒子作为宇宙中的灰尘，将全局最优值作为中心灰尘，通过中心灰尘的吸引与排斥作用来优化采样粒子的分布情况。除此之外，还有基于果蝇算法的粒子滤波方法[6]、基于蝙蝠算法的粒子滤波方法[7]和基于萤火虫算法的粒子滤波方法[8]等。截至目前，基于群智能优化理论改进粒子滤波的算法仍存在不足，在算法计算后期粒子的寻优能力下降，寻优结果出现偏差，算法迭代过程中容易陷入早熟或欠收敛状态，导致滤波性能降低。因此，如何快速准确地寻找全局最优解是目前研究中面临的难点问题[9]。

鲸群算法[10]（whale swarm algorithm，WSA）是由Mirjalili等人在2016年提出的一种新型、基于种群的仿生智能优化算法。该算法思想源于对海洋中座头鲸生物搜寻、包围、狩猎等行为的效仿，算法实现过程简单，收敛速度快，具有较强的鲁棒性。文献[11]已证明，鲸群算法的寻优搜索能力优于蝙蝠算法、蜻蜓算法。鲸群算法自提出后多被用于系统调度、图像检索、特征选择等领域[12-14]，目前还没有将鲸群算法与粒子滤波结合的相关研究。

本文将鲸群算法引入粒子滤波中，提出一种改进的鲸群算法优化粒子滤波（improved whale swarm algorithm optimized particle filter，IWS-PF）。该算法中，考虑到粒子滤波的运行机制和鲸群算法的特点，利用鲸鱼群的螺旋运动寻优方式更新粒子位置，并引入最优邻域扰动策略和自适应权重因子策略，动态调整鲸群的全局最优位置，平衡算法的局部与全局搜索能力。改进的鲸群优化粒子滤波算法实现了对重要性采样过程的优化，使粒子的分布更加接近真实的后验概率密度，改善了粒子权值退化现象，从根本上解决了粒子贫化问题，提高了粒子滤波的精度。

1 粒子滤波算法

粒子滤波算法的基本思想来源于蒙特卡罗方法（Monte Carlo methods），它适用于所有可被状态空间模型描述的系统。粒子滤波采用状态空间的随机样本近似概率密度函数，使用样本均值避免复杂的积分计算[15]。给定非线性动态方程为

式中：xt代 表系统在t时 刻的状态变量；f(·)代表状态转移方程；wt代表系统的过程噪声。zt代表系统在t时刻的观测值；h(·)代 表观测方程；vt代表系统观测噪声；ut代 表系统在t时刻的输入量。

粒子滤波的核心是求解边缘后验概率p(xtjz1:t)，其实现可分为2个过程：预测过程和更新过程。

1）预测过程 给定t−1时刻的数据观测值，预测t时刻状态变量xt出现的概率。预测方程为

2）更新过程 从t−1时 刻到达t时刻，得到一个新的观测变量zt，修正上式的预测值。更新方程为

归一化常数为

粒子权值更新公式表示为

对权值进行归一化，即：

则输出状态为

2 鲸群算法

鲸群算法是一种模拟海洋中座头鲸捕食行为的群智能优化算法。座头鲸的捕食行为如图1所示。通过气泡网进行攻击，不断螺旋向上靠近目标，逐渐收缩包围圈，最终到达目标鱼群的位置。该算法主要包含3个阶段：包围猎物、螺旋搜寻、随机搜寻。

图1 座头鲸捕食行为Fig.1 Feedation behavior of humpback whale

2.1 包围猎物

在搜寻猎物过程中，WSA令当前最优解或接近最优候选解为猎物目标，然后其他鲸鱼向当前最接近猎物的鲸鱼方向移动，并逐渐缩小整个鲸鱼群的包围圈，实现对猎物的包围。在此过程中，鲸鱼位置更新公式为

式中：t为当前迭代次数；D为最优鲸鱼与其他鲸鱼个体的距离向量；X∗(t)为当前最优的鲸鱼位置；X(t)为当前鲸鱼个体位置的坐标向量；系数向量A和C的计算公式为

式中：r1和r2是 0～1之间的随机数；a是收敛因子，从2～0线性递减；tmax是最大迭代次数。

2.2 螺旋搜寻

座头鲸狩猎时以螺旋式游向猎物，构建鲸鱼群狩猎行为的数学分析模型为

式中：D′为 鲸鱼与猎物之间的距离；b是决定螺旋形状的系数；l是−1～1的随机数。

WSA选择概率p作为阈值，决定鲸鱼位置更新的方式，其中包含包围猎物和狩猎行为两种机制[16]。其数学模型描述为

若p<0.5，则：

若p≥0.5，则：

2.3 随机搜寻

鲸鱼捕食时，1）假定A<1时，采用螺旋包围狩猎行为；2）假定A≥1时，采用随机搜寻方式。随机搜寻过程的数学模型为

式中：Xrand是鲸群中随机选择一个鲸鱼的位置向量。

3 鲸群算法优化的粒子滤波

从上述2种算法的运行机制上看，可以考虑采用鲸群算法来优化粒子重要性采样过程，通过鲸群算法的强寻优能力，使粒子集合集中分布在高似然区域，缓解粒子退化问题，并且每个鲸鱼受最优鲸鱼位置的吸引力大小不同，这将使粒子多样性得到提升。基于此，本文提出的IWS-PF算法设计如下。

3.1 将粒子权值作为鲸鱼个体位置的评判标准

在粒子滤波算法中，越接近真实值的粒子权值越大。在鲸群算法中，越接近目标猎物的鲸鱼适应度越大，所处位置越优。因此，将粒子权值作为鲸鱼个体位置的评判标准，这样就建立了鲸群算法与粒子滤波算法两者之间的联系，即每个粒子的权重值大小表征鲸鱼个体所处位置的状态，最佳位置所处的的鲸鱼相当于集合中权重值最高粒子的状态，鲸鱼个体通过迭代不断向最优位置鲸鱼靠近，此过程可以类比为粒子不断逼近真实系统状态的后验概率分布。因此，可以考虑通过鲸群算法优化重要性采样后粒子分布。

3.2 全局最优值调整策略设计

当更新鲸鱼位置时，通常会针对当前的最佳鲸鱼进行迭代。在整个迭代过程中，只有出现优于当前时刻的最佳位置时，才会对原来的最佳位置进行更新。这样的搜索策略会使总的更新次数较少，导致群体的多样性降低，从而影响算法的搜索效率。为此，考虑引入最优邻域随机扰动策略，增加对附近空间的随机搜索，寻找一个更优的全局值，以提升整个算法的收敛速度和全局搜索能力。最优邻域随机扰动公式[17]为

若rand2<0.5，则：

若rand2≥0.5，则：

式中： rand1、 rand2 是 [0,1]之 间的随机数；是新生成的邻域位置。随机数 rand2与鲸群算法中概率p的作用类似，它以相同的概率50%作为阈值来更新新生成的位置。当 rand2<0.5时，新生成的邻域位置为（20）式所示；当 r and2≥0.5时，新生成的邻域位置仍为当前最优鲸鱼的位置。若新生成的位置比原位置的适应度好，则更新原位置，否则，原位置保持不变。数学模型如下：

3.3 位置更新公式修正

为实现鲸群算法与粒子滤波的有效结合，本文采用螺旋搜寻方式优化采样粒子，实现对重要性采样后的粒子分布优化。权重因子能够有效平衡算法的局部寻优能力和全局搜索能力，本文考虑对鲸鱼位置的更新过程引入自适应权重因子wt，动态地平衡算法的局部与全局搜索能力。构造的自适应因子表达式为

加入自适应权重后，鲸鱼位置更新公式（16）和（17）修正为

结合 sin 函 数在 ( 0,π/2)区间的变化特性可知，在算法前期wt会得到较大值，此时，鲸鱼受当前种群中最优解的吸引力较弱，这样可提升算法在前期的全局搜索能力。随着迭代次数t的 增加，wt的值会越来越小，使当前种群的最优解的影响力逐渐提升，对其他鲸鱼的吸引力越来越强，其他鲸鱼逐渐向当前最优位置移动。这样加强了算法的局部开发能力，提升了算法求解精度和收敛速度。

3.4 算法实现步骤

综上所述，IWS-PF算法实现流程图如图2所示。

图2 算法流程图Fig.2 Flow chart of algorithm

1）t=0 时 刻，在状态空间采样N个初始粒子i=1，2···Ng。

2）根据（1）式计算t+1时 刻粒子状态值xt和观测值zt， 将每个粒子的状态值作为每个鲸鱼的位置X(i)(t)。

3）使用（6）式计算每个粒子权重值，更新当前时刻的全局最优值X∗(t)。

4）对X∗(t)进行最优邻域随机扰动更新，生成均匀分布的随机数r and1、 r and2 ，若 r and2<0.5，则执行（20）式。否则，执行（21）式。

6）生成一个独立的随机数 rand(p)， 通过p的取值大小执行（24）式，更新粒子位置。

7）判断是否达到最大迭代次数，若是达到，则停止迭代；否则，转到步骤3。

8）更新粒子权值，并使用（7）式归一化权值。

9）根据（8）式输出每个粒子的状态值。

3.5 算法计算复杂度分析

在IWS-PF算法中，设粒子数量为N，最大迭代次数为M。从图2算法流程图可以看出，加入自适应权重的位置更新修正公式并未增加循环次数，理论上算法时间复杂度为O(N∗M)，加入最优邻域随机扰动将要生成一个新位置，意味着算法增加了一次遍历种群的循环，算法复杂度为O(2∗N∗M)，也就是说与PF相比，IWS-PF整体上增加了O(N∗M)的计算复杂度。因此，IWS-PF的运行时间也会略高于PF，这也与下文的仿真测试结果相符。

4 仿真实验及结果分析

实验的硬件环境为台式电脑（IntelCorei5处理器，4GB内存），实验环境为MATLAB 2018b。粒子滤波仿真中采用的状态方程和观测方程为

此模型是一个典型的非线性、非高斯系统模型，w(t)、v(t)为零均值高斯噪声。采用均方根误差公式作为算法性能评价的依据，其定义为

实验中，设R=1，Q=10，初始状态0.1，采样步长50。因为WSA与引力场算法具有很多共通之处，两者都是根据群体中某个个体得到的信息求解最优解。引力场算法是通过中心灰尘的吸引力与排斥力作用于其他灰尘使其靠近或远离。WSA是通过当前种群中的最优鲸鱼对其他鲸鱼的吸引力大小来决定靠近或远离。本文提出的IWSPF算法与引力场优化的粒子滤波算法[5]（gravitation field algorithm particle filter，GFA-PF）都是基于标准PF做出的改进算法，所以在滤波精度、运算时间等方面对这3种算法进行了对比分析，比较了算法的性能。

4.1 算法收敛性分析

为验证IWS-PF算法与PF算法的收敛性，其他参数设置相同，在粒子数目不同的条件下对2种算法进行RMSE对比，算法收敛性如图3所示。

图3 PF，IWS-PF算法收敛性Fig.3 Convergence of PF and IWS-PF algorithms

由图3可知，本文提出的IWS-PF算法随着粒子数目的增多，算法的滤波精度逐渐提升，并且当粒子数目达到80后，算法的RMSE值慢慢趋于稳定状态。这表明当粒子数目达到一定条件后IWSPF与传统PF算法都具有误差趋于平稳的特征，也就是说，本文提出的IWS-PF算法也具有相似的收敛性。

4.2 粒子分布测试

为测试IWS-PF粒子多样性，设置粒子总数为100，标准PF与IWS-PF算法进行50次迭代后的粒子分布如图4所示。

由图4可知，标准PF只用大权值粒子进行状态估计，导致粒子分布状态单一且聚集性强，不利于整体状态估计。IWS-PF大部分粒子整体分布在高似然区域，少部分粒子散落分布在低似然区域，粒子多样性丰富。通过包围以及螺旋搜寻两种不同的方式优化，使得粒子分布更加合理。测试结果表明，IWS-PF有效改善了粒子退化问题，增加了粒子多样性。

图4 粒子分布Fig.4 Particle distribution

4.3 滤波精度测试

图5～图7分别是PF、GFA-PF和IWS-PF在粒子数为20、50、100时的状态估计及对应的误差统计对比结果图。

图5 状态估计及误差统计对比（N=20，Q=10，R=1）Fig.5 Statistical comparison of state estimation and error（N = 20，Q = 10，R = 1）

图6 状态估计及误差统计对比（N=50，Q=10，R=1）Fig.6 Statistical comparison of state estimation and error（N = 50，Q = 10，R = 1）

由图5～图7可知，在粒子数目相同的条件下，相较于标准PF、GFA-PF，IWS-PF的预测曲线与真实状态曲线重合度最高，说明IWS-PF的估计绝对值误差最小，这是由于运用了鲸群算法的寻优机制，使粒子分布更加接近真实值；引入的最优邻域随机扰动策略和自适应权重，实现了算法前期全局寻优，后期局部精准寻优，从而提高了粒子滤波的精度。

图7 状态估计及误差统计对比（N=100，Q=10，R=1）Fig.7 Statistical comparison of state estimation and error（N =100，Q = 10，R = 1）

实验中取不同粒子数目N=20、50、100，对3种算法分别进行20次独立仿真实验，取其均方根误差的平均值进行对比，结果如表1所示，3种算法运行时间如表2所示。

表2 3种算法运行时间对比Table 2 Comparison of operation time of three algorithms

由表1实验结果可以看出，随着粒子数目的不断增加，3种算法的的误差在逐渐减小，即粒子数目越多，滤波效果也越好。在粒子数目相同的条件下，IWS-PF的均方误差值始终低于PF、GFAPF，并且IWS-PF在粒子数为N=20的时候，就能够达到标准PF算法N=100时的滤波精度，所以IWSPF算法的状态估计效果更好，并且IWS-PF的运算时间略高于PF，但与GFA-PF算法的运行时间几乎一致，说明算法在保证滤波精度的同时，也能够保持较好的实时性。

表1 3种算法均方根误差对比Table 1 Comparison of root mean square error of three algorithms

5 结论

本文提出了一种鲸群优化的粒子滤波算法，利用鲸群算法的螺旋寻优机制优化了粒子滤波的重要性采样过程，使粒子分布更加合理，并引入了最优邻域随机扰动策略，增强了算法的强寻优能力，并在鲸鱼位置更新过程中加入自适应权重因子，动态地平衡算法的局部与全局搜索能力，提高了粒子滤波求解精度。实验结果表明，提出的IWSPF相较于标准PF、GFA-PF具有更高的粒子滤波估计精度和更小的均方误差，并且在运行后期依然能够保持良好的粒子多样性，避免了粒子贫化现象。