关于非对称含错学习问题的困难性研究

张江; 范淑琴

doi:10.11999/JEIT190685

关于非对称含错学习问题的困难性研究

doi: 10.11999/JEIT190685

张江^,,
范淑琴

密码科学技术国家重点实验室北京 100878

基金项目: 国家重点研发计划(2017YFB0802005, 2018YFB0804105)，国家自然科学基金(61602046, 61932019)，中国科协“青年人才托举工程”(2016QNRC001)

详细信息

作者简介:
张江：男，1986年生，副研究员，主要研究方向为基于格的密码协议及其可证明安全

范淑琴：女，1978年生，教授，主要研究方向为基于格的密码分析

通讯作者:
张江　jiangzhang09@gmail.com

中图分类号: TN918, TP309.7
计量
- 文章访问数: 2473
- HTML全文浏览量: 952
- PDF下载量: 103
- 被引次数: 16
出版历程
- 收稿日期: 2019-09-14
- 修回日期: 2019-11-20
- 网络出版日期: 2019-11-29
- 刊出日期: 2020-02-19

On the Hardness of the Asymmetric Learning With Errors Problem

Jiang ZHANG^,,
Shuqin FAN

State Key Laboratory of Cryptology, Beijing 100878, China

Funds: The National Key Research and Development Program of China (2017YFB0802005, 2018YFB0804105), The National Natural Science Foundation of China (61602046, 61932019), The Young Elite Scientists Sponsorship Program by China Association for Science and Technology (2016QNRC001)

摘要

摘要: 由于基于最坏情况困难假设等优点，基于格的密码被认为是最具前景的抗量子密码研究方向。作为格密码的常用的两个主要困难问题之一，含错学习(LWE)问题被广泛用于密码算法的设计。为了提高格密码算法的性能，Zhang等人(2019)提出了非对称含错学习问题，该文将从理论上详细研究非对称含错学习问题和标准含错学习问题关系，并证明在特定错误分布下非对称含错学习问题和含错学习问题是多项式时间等价的，从而为基于非对称含错学习问题设计安全的格密码算法奠定了理论基础。
- 抗量子密码 /
- 格密码 /
- 含错学习问题
Abstract: Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem.
- Post-qauntum cryptography /
- Lattice-based cryptography /
- Learning With Errors (LWE)

HTML全文

1. 引言

粒子滤波是基于蒙特卡罗思想和序贯贝叶斯推断方法，能够有效处理非线性、非高斯动态模型估计问题，已广泛用于目标跟踪^[1-3]、故障检测^[4]、寿命预测^[5]以及定位导航^[6]等领域。由于基本粒子滤波存在权值退化现象导致状态预测精度下降，Gordon等人^[7]提出自举粒子滤波算法基于序贯重要性采样进行重采样，从而克服了样本的权值退化。但重采样过程会导致粒子多样性缺失造成粒子贫化，限制了滤波精度的进一步提升^[8,9]。为此，国内外学者针对粒子贫化问题开展了一系列研究工作，将群智能算法融入粒子滤波改善粒子分布，已成为解决粒子滤波粒子贫化问题的新路径。刘海涛等人^[10]提出一种利用遗传算法自适应优化低权值粒子的粒子滤波方法，有效减缓了权值退化问题，并保证了粒子多样性。刘润邦等人^[11]将万有引力算法作为粒子引导方式优化粒子分布，借助感知模型防止粒子拥挤或重叠，在粒子数较少条件下保证了滤波精度和速度。王尔申等人^[12]提出一种基于混沌改进的粒子群优化粒子滤波算法，利用混沌的遍历性将变量从混沌空间映射到解空间，从而实现对粒子的混沌扰动，提高滤波样本的质量。田梦楚等人^[13]提出利用改进的萤火虫位置迭代公式和荧光亮度更新公式提升了滤波精度。2019年Heidari根据哈里斯鹰捕食行为提出哈里斯鹰优化算法^[14,15](Harris Hawks Optimization, HHO)，相比上述群智能算法哈里斯鹰优化算法具有多个活跃的时变位置更新阶段，能够较好地平衡种群的探索行为和开发行为，十分适于复杂优化问题的求解。

针对粒子滤波重采样过程导致的粒子贫化问题，本文综合粒子滤波方法和哈里斯鹰优化算法特点，提出一种基于围猎改进哈里斯鹰优化的粒子滤波方法(Particle Filter based on Harris Hawks Optimization improved by Encircling strategy, EHHOPF)。该方法探索阶段融入围猎策略并且简化开发阶段策略选择结构，有效提升全局搜索能力和局部开发能力，利用Sigmoid函数构建非线性猎物逃逸能量平衡算法全局搜索能力和局部开发能力，提高粒子滤波的状态估计精度和滤波实时性能。

2. 粒子滤波原理

粒子滤波通过离散随机采样粒子近似系统状态的后验概率密度，根据蒙特卡罗方法和大数定律以样本均值代替积分运算，从而获得系统状态的最小方差估计。设非线性动态过程为

$\qquad\qquad\quad {x_k} = f({x_{k - 1}},{w_k})$

(1)

$\qquad\qquad\quad {z_k} = h({x_k},{v_k})$

(2)

其中， ${x_k}$ 为系统 $k$ 时刻状态， $f( \cdot )$ 为系统状态转移函数， ${w_k}$ 为系统过程噪声， ${z_k}$ 为系统 $k$ 时刻观测值， $h( \cdot )$ 为系统观测函数， ${v_k}$ 为量测噪声。

令状态初始后验概率密度 $p({x_0}|{z_0}) = p({x_0})$ ，则状态预测方程为

$p({x_k}|{z_{1:k - 1}}) = \int {p({x_k}|{x_{k - 1}})p({x_{k - 1}}|{z_{1:k - 1}}){\text{d}}{x_{k - 1}}}$

(3)

状态更新方程为

$p({x_k}|{z_{1:k}}) = \frac{{p({z_k}|{x_k})p({x_k}|{z_{1:k - 1}})}}{{p({z_k}|{z_{1:k - 1}})}}$

(4)

其中，

$p({z_k}|{z_{1:k - 1}}) = \int {p({z_k}|{x_k})p({x_k}|{z_{1:k - 1}}){\text{d}}{x_k}}$

(5)

设重要性概率密度函数 $q({x_{0:k}}|{z_{1:k}})$ 具备性质

$q({x_{0:k}}|{z_{1:k}}) = q({x_0})\prod\limits_{j = 1}^k {q({x_j}|{x_{0:j - 1}},{z_{1:j}})}$

(6)

则权值公式

${w_k} = \frac{{p({z_{1:k - 1}}|{x_{0:k}})p({x_{0:k}})}}{{q({x_k}|{x_{0:k - 1}},{z_{1:k}})q({x_{0:k - 1}},{z_{1:k}})}}$

(7)

从 $p({x_{k - 1}}|{z_{1:k}})$ 中采集 $N$ 个样本点 $\{ x_{k - 1}^i\} _{i = 1}^N$ ，获得后验概率密度函数估计为

$p({x_k}|{z_{1:k}}) = \sum\limits_{i = 1}^N {w_k^i\delta ({x_k} - x_k^i)}$

(8)

其中， $\delta ( \cdot )$ 为狄拉克函数，重要性权值更新公式

$w_k^i = w_{k - 1}^i\frac{{p({z_k}|x_k^i)p(x_k^i|x_{k - 1}^i)}}{{q(x_k^i|x_{k - 1}^i,{z_k})}}$

(9)

最后归一化权值并输出最终滤波状态

$\tilde w_k^i = \frac{{w_k^i}}{{\displaystyle\sum\limits_{i = 1}^N {w_k^i} }}\;\;$

(10)

${\hat x_k} = \sum\limits_{i = 1}^N {\tilde w_k^ix_k^i}$

(11)

3. 哈里斯鹰优化算法

哈里斯鹰优化算法根据哈里斯鹰捕猎习性将其捕猎过程划分为探索行为和开发行为，采用猎物逃逸能量动态选取探索行为或开发行为进行捕猎，猎物逃逸能量定义为

$E = 2{E_0}\left(1 - \frac{t}{M}\right)$

(12)

其中， ${E_0} \sim {\text{U}}( - 1,1)$ 为初始逃逸能量，t为当前进化代数，M为种群最大进化代数。当|E|≥1时进入探索阶段，|E|<1时进入开发阶段。

(1)探索阶段。当|E|≥1时哈里斯鹰执行探索模式捕猎，哈里斯鹰种群个体随机栖息在可行域内，通过以下策略对猎物进行等概率全局搜索

$\begin{split} & X(t + 1) =\\ & \left\{ \begin{gathered} {X_{{\text{rd}}}}(t) - {r_1}|{X_{{\text{rd}}}}(t) - 2{r_2}X(t)|,{\text{ }}q \ge 0.5 \\ ({X_{{\text{rt}}}}(t) - {X_m}(t)) - {r_3}({\text{LB}} + {r_4}({\text{UB}} - {\text{LB}})),{\text{ }}q < 0.5 \\ \end{gathered} \right. \end{split}$

(13)

其中， ${X_{{\text{rd}}}}(t)$ 为第 $t$ 代种群中随机选择的哈里斯鹰个体； ${X_{{\text{rt}}}}$ 表示猎物位置； ${X_m}(t)$ 表示当前哈里斯鹰种群的平均位置；UB, LB分别为搜索范围上限和下限； ${r_1},{r_2},{r_3},{r_4},q$ 均为 $(0,1)$ 区间内的随机数。

(2)开发阶段。当|E|<1时哈里斯鹰执行开发模式捕猎，令 $r \sim {\text{U}}(0,1)$ ，结合猎物逃逸能量和随机策略选取4种捕猎策略。

(a)当 $0.5 \le |E| < 1$ 且 $r \ge 0.5$ 时，采取软包围策略完成个体位置更新

$X(t + 1) = \Delta X(t) - E|J{X_{{\text{rt}}}}(t) - X(t)|$

(14)

$\Delta X(t) = {X_{{\text{rt}}}}(t) - X(t)$

(15)

其中， $\Delta X(t)$ 猎物位置与当前个体位置差值； $J \sim {\text{U}}(0,2)$ 。

(b)当 $|E| < 0.5$ 且 $r \ge 0.5$ 时，采取硬包围策略完成个体位置更新

$X(t + 1) = {X_{{\rm{rt}}}}(t) - E|\Delta X(t)|$

(16)

(c)当 $0.5 \le |E| < 1$ 且 $r < 0.5$ 时，采用渐进式快速俯冲软包围策略更新个体位置

$X(t + 1) = \left\{ \begin{gathered} Y,{\text{ }}f(Y) < f(X(t)) \\ Z,{\text{ }}f(Z) < f(X(t)) \\ \end{gathered} \right.$

(17)

$Y = {X_{{\text{rt}}}}(t) - E|J{X_{{\text{rt}}}}(t) - X(t)|$

(18)

$Z = Y + {\boldsymbol{S}} \cdot {\text{LF}}(d)$

(19)

其中， $f( \cdot )$ 是适应度函数； ${\boldsymbol{S}}$ 是元素为 $(0,1)$ 之间 $d$ 维随机向量； ${\text{LF}}( \cdot )$ 为莱维飞行策略； $\Gamma ( \cdot )$ 为Gamma函数。

(d)当 $|E| < 0.5$ 且 $r < 0.5$ 时，采取渐进式快速俯冲硬包围策略更新个体位置

$X(t + 1) = \left\{ \begin{gathered} Y,{\text{ }}f(Y) < f(X(t)) \\ Z,{\text{ }}f(Z) < f(X(t)) \\ \end{gathered} \right.$

(20)

$Y = {X_{{\text{rt}}}}(t) - E|J{X_{{\text{rt}}}}(t) - {X_m}(t)|$

(21)

$Z = Y + {\boldsymbol{S}} \cdot {\text{LF}}(d)$

(22)

4. 基于围猎改进哈里斯鹰优化粒子滤波方法

将粒子滤波中粒子的先验状态作为哈里斯鹰初始种群个体位置，利用迭代寻优过程改善粒子的分布情况。针对粒子滤波的特点，对哈里斯鹰优化算法进行改进，提高算法对粒子滤波的作用性能。

4.1 围猎策略

哈里斯鹰优化算法探索阶段中的全局搜索策略包含种群搜索范围和边界，无法满足粒子滤波随机预测条件。灰狼算法^[16,17]中围猎策略采用包围搜索方式，能够对猎物实现包围搜索，符合粒子滤波中粒子分布“聚而不合，散而不离”的特性。故将围猎策略引入哈里斯鹰优化算法探索阶段，保证算法适配于粒子滤波过程，围猎策略为

$\qquad {\boldsymbol{A}} = 2a \cdot {{\boldsymbol{r}}_5} - a$

(23)

$\qquad {\boldsymbol{C}} = 2{{\boldsymbol{r}}_6}$

(24)

$\qquad {\boldsymbol{D}} = \left| {{\boldsymbol{C}} \cdot {X_{{\rm{rt}}}}(t) - X(t)} \right|$

(25)

$\qquad X(t + 1) = {X_{{\text{rt}}}}(t) - {\boldsymbol{A}} \cdot {\boldsymbol{D}}$

(26)

$\qquad a = 2 \left(1 - \frac{t}{{{M}}}\right)$

(27)

其中， $a$ 为收敛因子； ${{\boldsymbol{r}}_5}$ , ${{\boldsymbol{r}}_6}$ 表示 $(0,1)$ 的d维随机向量； ${\boldsymbol{A}}$ , ${\boldsymbol{C}}$ 为系数向量， ${\boldsymbol{D}}$ 为距离向量。

4.2 非线性猎物逃逸能量

猎物逃逸能量作为控制哈里斯鹰个体位置更新方式的关键参数，负责平衡算法的全局搜索和局部开发行为。由图1可知，相比猎物逃逸能量的线性变化方式，Sigmoid函数的S型特征使得算法前期持续进行全局搜索发现最优区域，后期局部开发快速锁定全局最优位置，能够保证算法寻优收敛精度并提高收敛速度。因此，利用Sigmoid非线性函数构建猎物逃逸能量为

图 1 猎物逃逸能量变化对比

下载: 全尺寸图片幻灯片

$E = {E_0}({E_{\min }} + ({E_{\max }} - {E_{\min }}){f_{\text{s}}}(x))$

(28)

${f_{\text{s}}}(x) = \frac{1}{{1 + {{\text{e}}^{ - x}}}},{\text{ }}x = \lambda \left(2\frac{t}{M} - 1 \right)$

(29)

其中， ${E_{\max }}$ = 2为猎物最大逃逸能量； ${E_{\min }}$ = ${E_{\max }}$ /10为猎物最小逃逸能量； ${f_{\text{s}}}( \cdot )$ 为Sigmoid非线性函数； $x$ 为非线性段取值范围； $\lambda$ = 6为取值范围调节系数。

4.3 开发阶段捕猎策略融合

哈里斯鹰优化算法迭代后期应具备快速稳步收敛能力，引入选择比例因子融合硬包围策略、软包围策略以及与二者对应的渐进式俯冲包围策略，进一步优化开发阶段的分层捕猎策略选择机制。此外，设计非线性猎物跳跃强度更新方式动态调整粒子的收敛步长，提高算法迭代后期收敛效率，开发阶段捕猎策略融合过程为：当 $0.5 \le |E| < 1$ 时，融合软包围策略和渐进式快速俯冲软包围策略

$X_1 = \left\{ \begin{gathered} Y_1,{\text{ }}0{\text{ }} < {\text{rd }} < {\text{ }}{C_{{\text{rd}}}} \\ Z_1,{\text{ }}{C_{\text{r}}}_{\text{d}}{\text{ }} < {\text{rd }} < {\text{ }}2{C_{\text{r}}}_{\text{d}} \\ R_1,{\text{ }}2{C_{\text{r}}}_{\text{d}}{\text{ }} < {\text{rd }} < {\text{ }}1 \\ \end{gathered} \right.$

(30)

$Y_1 = {X_{{\text{rt}}}}(t) - E|{J_1}{X_{{\text{rt}}}}(t) - X(t)|$

(31)

$Z_1 = Y_1 + {\boldsymbol{S}} \cdot {\text{LF}}(d)$

(32)

$R_1 = \Delta X(t) - E|{J_1}{X_{{\text{rt}}}}(t) - X(t)|$

(33)

$X(t+1)=\left\{\begin{aligned} & X_1,\text{ }f(X_1) < f(X(t))\\ & X(t),\text{ }其他 \end{aligned}\right.$

(34)

${J_1} = {E_0}\left(1 - {\left(\frac{t}{M}\right)^{\frac{1}{3}}}\right) + 1$

(35)

其中， ${\rm{rd}} \sim {\text{U}}(0,1)$ ； ${J_1}$ 为非线性猎物跳跃强度； ${C_{{\text{rd}}}}$ 为选择比例因子，取为0.25。

当 $|E| < 0.5$ 时，融合硬包围策略和渐进式快速俯冲硬包围策略为

$X_2 = \left\{ \begin{aligned} & Y_2,{\text{ }}0{\text{ }} < {\text{rd }} < {\text{ }}{C_{\text{r}}}_{\text{d}} \\ & Z_2,{\text{ }}{C_{\text{r}}}_{\text{d}}{\text{ }} < {\text{rd }} < {\text{ }}2{C_{\text{r}}}_{\text{d}} \\ & R_2,{\text{ }}2{C_{\text{r}}}_{\text{d}}{\text{ }} < {\text{rd }} < {\text{ }}1 \end{aligned} \right.$

(36)

$Y_2 = {X_{{\text{rt}}}}(t) - E|{J_1}{X_{{\text{rt}}}}(t) - {X_m}(t)|$

(37)

$Z_2 = Y_2 + {\boldsymbol{S}} \cdot {\text{LF}}(d)$

(38)

$R_2 = {X_{{\text{rt}}}}(t) - E|\Delta X(t)|$

(39)

$X(t+1)=\left\{\begin{aligned} & X_2,\text{ }f(X_2) < f(X(t))\\ & X(t),\text{ }其他 \end{aligned}\right.$

(40)

4.4 算法实现步骤

为优化粒子滤波采样过程，将融入围猎策略的哈里斯鹰优化算法与粒子滤波结合，定义适应度函数为

$f{\text{ }} = {\text{ }}|{z_{{\text{real}}}} - {z_{{\text{pre}}}}|$

(41)

其中， ${z_{{\text{real}}}}$ 为实际量测值； ${z_{{\text{pre}}}}$ 为预测量测值。

EHHOPF算法实现步骤如下。

步骤1　初始化粒子状态。在 $k = 0$ 时按照初始样本分布 $p\left( {{x_0}} \right)$ 进行采样，生成N个粒子作为初始样本 $\{ x_0^i,i = 1,2, \cdot \cdot \cdot ,N\}$ 。重要性密度函数为

$x_k^i \sim q(x_k^i|x_{k - 1}^i,{z_k}) = p(x_k^i|x_{k - 1}^i)$

(42)

步骤2　预测粒子状态。利用式(1)和式(2)计算下一时刻的粒子状态值 $x_k^i$ 和观测值 $z_k^i$ ，将粒子的状态值 $x_k^i$ 作为哈里斯鹰个体初始位置 ${X_i}$ 。

步骤3　更新粒子状态。执行融入围猎策略的哈里斯鹰优化算法，根据式(24)—式(41)对粒子位置进行迭代更新。

步骤4　权值计算。根据式(9)计算粒子重要性权值。

步骤5　归一化权值。根据式(10)对粒子的重要性权值进行归一化。

步骤6　系统状态估计。根据式(11)计算粒子加权和，输出系统状态滤波预测结果。

5. 仿真实验与结果分析

为验证所提出算法的滤波性能，采用一种高度非线性非高斯系统模型进行仿真试验，该系统状态方程和观测方程如下

$x(k) = 1 + \sin (0.04\pi k) + 0.5x(k - 1) + w(k)$

(43)

$z(k) = \left\{ \begin{aligned} & 0.2{x^2}(k) + v(k),{\text{ }}k \le 30 \\ & - 2 + 0.5x + v(k),{\text{ }}k > 30 \end{aligned} \right.$

(44)

其中， $w(k) \sim \Gamma (3,2)$ 为系统第k步过程噪声， $v(k) \sim N(0,{10^{ - 5}})$ 为系统第k步量测噪声。实验平台为Intel i7, 2.9 GHz和8 GB RAM，仿真环境为MATLAB 2019b。

5.1 状态预测精度测试

为验证所提方法的状态预测性能，选取粒子滤波(Particle Filter, PF)、改进的磷虾算法优化粒子滤波(Improved Particle Filter algorithm optimized by Krill Herd, IKHPF)^[18]、蝙蝠算法优化粒子滤波(Bat Algorithm optimized Particle Filter, BAPF)^[19]、基于改进布谷鸟算法的粒子滤波方法(Particle Filter based on Improved Cuckoo Search, ICSPF)^[20]、基于灰狼优化算法的粒子滤波方法(Particle Filter based on Grey Wolf Optimizer, GWOPF)与EHHOPF进行状态跟踪性能对比。单次独立仿真系统整体均方根误差为

${\rm{RMSE}} = \sqrt {\frac{1}{T}\sum\limits_{k = 1}^T {{{({x_k} - {{\hat x}_k})}^2}} }$

(45)

其中， $T$ 为总仿真时间步数； ${x_k}$ 为 $k$ 时刻状态真实值； ${\hat x_k}$ 为 $k$ 时刻状态估计值。

仿真实验相关设置如下：初始粒子 $\sim N(0,0.75)$ ，滤波步数T=60。IKHPF算法关键参数包括权重 ${w_1}$ 和 ${w_2}$ 、最大诱导速度 ${N^{\max }}$ 、个体觅食速度 ${V_f}$ 和最大随机扩散速度 ${D^{\max }}$ ；BAPF算法关键参数包括衰减系数 $\alpha$ 、增强系数 $\gamma$ 、最小脉冲频率 ${f_{\min }}$ 和最大脉冲频率 ${f_{\max }}$ ；ICSPF算法关键参数为发现概率 ${p_a}$ 。各算法参数具体设置如表1所示，各优化粒子滤波算法最大进化代数M= 10，所有算法均独立仿真30次。

表 1 群智能优化滤波方法参数设置

滤波方法	${w_1}$	${w_2}$	${N^{\max }}$	${V_f}$	${D^{\max }}$	$\alpha$	$\gamma$	${f_{\min }}$	${f_{\max }}$	${p_a}$
IKHPF	0.2	0.6	0.08	1.2	0.01	–	–	–	–	–
BAPF	–	–	–	–	–	0.5	0.5	0	2	–
ICSPF	–	–	–	–	–	–	–	–	–	0.75

下载: 导出CSV

| 显示表格

图2、图3分别为6种优化滤波方法在粒子群总数N=20条件下系统的状态估计结果和状态估计绝对误差，各算法对真实状态的变化均有较好的跟随效果，ICSPF和EHHOPF的状态预测误差相较于IKHPF, BAPF和GWOPF显著减小，且EHHOPF方法的滤波稳定性和预测精度总体优于ICSPF。将粒子群总数调整为N=100，如图4、图5所示，各优化滤波方法精度伴随粒子数提升而显著改善，EHHOPF方法的滤波稳定性和总体估计精度均优于其他4种方法。

图 2 滤波状态估计 (N=20)

下载: 全尺寸图片幻灯片

图 3 估计误差绝对值 (N=20)

下载: 全尺寸图片幻灯片

图 4 滤波状态估计 (N=100)

下载: 全尺寸图片幻灯片

图 5 估计误差绝对值 (N=100)

下载: 全尺寸图片幻灯片

由表2仿真试验结果可知，群智能算法优化粒子滤波方法估计结果的30次均方误差均值RMSE_mean相比PF存在显著改善，证明群智能优化算法改善粒子分布的有效性。伴随参与状态估计的粒子数量增加，包括经典粒子滤波在内的6种滤波方法的状态估计精度提高。相比IKHPF, BAPF和GWOPF, ICSPF和EHHOPF均能够在扩增粒子数量的前提下进一步挖掘状态估计能力，且EHHOPF在粒子数较少时亦能实现较为准确的系统状态估计。EHHOPF方法在不同粒子数量条件下均较好地保证了粒子分布向最优似然区靠近，进而获得了优于其他方法的状态估计稳定性。粒子数量较少时，EHHOPF与PF的单步估计平均时间T_mean处于同一时间量级，几乎不影响滤波实时性。当粒子数量由20增大至50时，EHHOPF和ICSPF相比IKHPF与BAPF所需的单步估计平均时间未有显著延长。当粒子规模进一步扩增为100时，EHHOPF单步估计平均时间仍低于其余群智能优化滤波算法，满足滤波快速性要求。

表 2 不同粒子滤波算法仿真结果比较

滤波方法	RMSE_mean			RMSE_var			T_mean(s)
滤波方法	20	50	100	20	50	100	20	50	100
PF	0.7863	0.6188	0.5231	0.0373	0.0419	0.0261	2.71E-03	6.23E-03	0.0113
IKHPF	0.0691	0.0371	0.0357	2.36E-03	1.17E-03	9.54E-04	0.0214	0.0582	0.1319
BAPF	0.0430	0.0313	0.0286	1.24E-04	3.19E-05	8.38E-06	0.0134	0.0329	0.0633
ICSPF	0.0225	0.0138	0.0112	1.82E-04	3.04E-05	9.86E-06	9.79E-03	0.0181	0.0310
GWOPF	0.0508	0.0295	0.0264	5.57E-03	1.22E-05	7.05E-06	3.06E-03	7.33E-03	0.0141
EHHOPF	0.0193	0.0116	9.02E-03	7.11E-05	6.91E-06	3.45E-06	6.04E-03	0.0148	0.0271

下载: 导出CSV

| 显示表格

5.2 粒子分布多样性测试

为验证EHHOPF滤波估计时的粒子多样性，比较PF和EHHOPF的粒子分布情况，粒子总数为N=100。观察k=8，k=25和k=45时刻粒子分布情况，如图6所示。在不同采样时刻，粒子滤波算法由于重采样操作多次采样权重较大的粒子，造成粒子多样性缺失的粒子贫化现象，不可避免地导致最终状态估计仅由有限的大权重采样粒子表示，因此难以保证滤波精度。相比之下，EHHOPF方法中采样粒子大都集中分布在真实状态附近，也存在少部分粒子离真实值较远，保持了粒子的多样性，有利于整体状态估计。

图 6 不同时刻粒子分布

下载: 全尺寸图片幻灯片

5.3 滤波实时性测试

为比较不同滤波方法的滤波实时性能，观察在N=20和N=100条件下各滤波方法不同采样时刻的滤波时长，如图7所示，各方法滤波耗时均为伴随时刻变化的动态过程。GWOPF在不同粒子数量条件下的滤波实时性表现与PF处于同一量级且波动不大，表明GWO寻优机制能够较快完成目标函数的寻优搜索，为EHHOPF的寻优快速性提供了基础。EHHOPF的全采样过程各时刻耗时短于IKHPF, BAPF, ICSPF，且各时刻状态估计耗时波动较小。另一方面，伴随参与滤波的粒子数量增加，EHHOPF采样时刻的状态估计耗时更为稳定。

图 7 不同方法的滤波实时性

下载: 全尺寸图片幻灯片

5.4 算法收敛性测试

为验证算法收敛性，以均方根误差量化分析在不同粒子数条件下群智能算法优化粒子滤波方法的收敛情况，如图8所示。随着粒子数的增加，各方法均方根误差都存在整体下降趋势，其中BAPF, ICSPF以及EHHOPF具有持续收敛态势，IKHPF和GWOPF存在局部收敛精度波动。此外，EHHOPF相较其他方法可在粒子数较少时获得较好的滤波效果。

图 8 不同粒子数下各滤波方法均方根误差

下载: 全尺寸图片幻灯片

6. 基于距离的机动目标跟踪实例

为进一步测试EHHOPF在工程应用中的性能表现，引入一种基于距离的机动目标跟踪模型，该模型假设目标做匀速直线运动，目标状态为 ${\boldsymbol{X}}{\text{(}}k{\text{)}} = {\left[ {{x_{\rm{p}}}(k),{\text{ }}{x_{\rm{v}}}(k),{\text{ }}{y_{\rm{p}}}(k),{\text{ }}{y_{\rm{v}}}(k)} \right]^{\text{T}}}$ ，其中 $({x_{\rm{p}}}(k),{\text{ }}{y_{\rm{p}}}(k))$ 为目标在时刻k所处的位置， $({x_{\rm{v}}}(k),{\text{ }}{y_{\rm{v}}}(k))$ 为目标在k时刻具备的速度，系统噪声为 ${\boldsymbol{w}}{\text{(}}k{\text{)}} = \left[ {w_{x{\rm{p}}}}(k), {\text{ }}{w_{x{\rm{v}}}}(k),{\text{ }}{w_{y{\rm{p}}}}(k),{\text{ }}{w_{y{\rm{v}}}}(k) \right]^{\text{T}}$ ，各维噪声均服从高斯分布。上述系统具体可表述为

$\begin{split} \left[ {\begin{array}{*{20}{c}} {{x_{\rm{p}}}(k + 1)} \\ {{x_{\rm{v}}}(k + 1)} \\ {{y_{\rm{p}}}(k + 1)} \\ {{y_{\rm{v}}}(k + 1)} \end{array}} \right] =& \left[ {\begin{array}{*{20}{c}} 1&T&0&0 \\ 0&1&0&0 \\ 0&0&1&T \\ 0&0&0&1 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{x_{\rm{p}}}(k)} \\ {{x_{\rm{v}}}(k)} \\ {{y_{\rm{p}}}(k)} \\ {{y_{\rm{v}}}(k)} \end{array}} \right] \\ & + \left[ {\begin{array}{*{20}{c}} {0.5{T^2}}&0&0&0 \\ 0&T&0&0 \\ 0&0&{0.5{T^2}}&0 \\ 0&0&0&T \end{array}} \right]\\ & \cdot\left[ {\begin{array}{*{20}{c}} {{w_{x{\rm{p}}}}(k)} \\ {{w_{x{\rm{v}}}}(k)} \\ {{w_{y{\rm{p}}}}(k)} \\ {{w_{y{\rm{v}}}}(k)} \end{array}} \right] \end{split}$

(46)

$Z(k) = \sqrt {{{({x_{\rm{p}}}(k) - {x_{\rm{s}}})}^2} + {{({y_{\rm{p}}}(k) - {y_{\rm{s}}})}^2}} + v(k)$

(47)

其中，T=1 s为单步采样时间， $v(k)$ 为高斯随机观测噪声。在原点 $({x_{\rm{s}}},{y_{\rm{s}}})$ = $(0,0)$ 的位置进行观测并记录预测目标与观测点的距离，目标跟踪步数M=30，采样粒子数N=100，目标运动场地长L=100 m，宽W=100 m，初始目标状态设为 ${\boldsymbol{X}}{\text{(1)}} = \left[ 1,{\text{ }}L/M, {\text{ }}20,{\text{ }}60/M \right]^{\text{T}}$ 。为测试EHHOPF方法求解工程问题的性能，对上述机动目标跟踪模型进行30次目标跟踪。

6种粒子滤波方法在粒子群数量N=100条件下的目标跟踪轨迹和目标跟踪偏差变化情况如图9和图10所示，ICSPF对于目标跟踪的精确性存在一定波动，IKHPF的跟踪偏差随时间逐步递增，PF, BAPF, GWOPF和EHHOPF在真实运动状态变化前期均呈现出较好的跟踪效果。伴随运动不断进行，PF的跟踪误差逐渐增大，BAPF的跟踪性能则出现了波动情况，GWOPF和EHHOPF的跟踪偏差优于其他粒子滤波方法，且EHHOPF方法的总体滤波稳定性和预测精度优于GWOPF。

图 9 目标跟踪轨迹

下载: 全尺寸图片幻灯片

图 10 目标距离偏差变化

下载: 全尺寸图片幻灯片

上述跟踪过程为平面目标跟踪，包括位置和速度两种跟踪状态，其中每种状态可以分解成X和Y方向的4种状态：(1) X方向的位置P_x；(2) X方向的速度V_x；(3) Y方向的位置P_y；(4) Y方向的速度V_y。计算30次实验每一维度状态的均方根误差RMSE、总体绝对偏差和SGAD以及单步平均绝对偏差MAD，结果如表3所示。IKHPF, GWOPF和EHHOPF的位置跟踪性能总体优于PF, BAPF和ICSPF, ICSPF速度状态的均方根误差均值RMSE_mean与均方根误差方差RMSE_var优于其他算法，EHHOPF相比IKHPF和GWOPF的各项性能表现不仅更为均衡且波动性更小。考虑滤波方法的总体误差性能SGAD和单步跟踪性能MAD的平均误差和误差方差，EHHOPF相比其他滤波方法受滤波过程随机性的影响最小。

表 3 不同滤波算法目标跟踪结果(m)

滤波方法	RMSE_mean				RMSE_var				SGAD		MAD
滤波方法	P_x	V_x	P_y	V_y	P_x	V_x	P_y	V_y	均值	方差	均值	方差
PF	10.0260	0.6644	11.8082	0.8561	17.0158	0.0621	24.5250	0.1248	58.4830	1036.36	1.9494	1.1515
IKHPF	4.9863	0.6188	5.2403	0.5968	11.4143	0.1528	12.4253	0.0804	35.6843	600.255	1.1895	0.6669
BAPF	14.8241	1.2136	17.3307	1.4562	39.7658	0.1654	51.4222	0.3707	72.6756	1718.71	2.4225	1.9097
ICSPF	40.4398	0.1106	63.5023	0.2041	277.389	4.36E-04	1301.48	5.41E-04	261.777	13191.3	8.7259	14.657
GWOPF	4.5594	0.1912	5.0885	0.2513	4.4170	0.0119	6.0523	0.0238	28.4354	196.586	0.9478	0.2184
EHHOPF	4.4762	0.2249	4.9962	0.2871	3.0997	8.00E-03	4.2422	0.0148	27.9863	144.975	0.9329	0.1611

下载: 导出CSV

| 显示表格

7. 结论

本文提出了一种基于围猎改进哈里斯鹰优化的粒子滤波方法，通过围猎策略令哈里斯鹰优化算法适配粒子滤波环境，提出非线性猎物逃逸能量平衡算法全局探索行为和局部开发行为，构建选择比例因子优化算法开发阶段策略选择模式，有效地提高了算法的寻优效率。为满足粒子滤波预测条件，将哈里斯鹰算法中探索阶段全局搜索策略替换成围猎策略，更利于实现高似然区搜索。非线性非高斯系统和目标跟踪问题的仿真试验结果表明：

(1)群智能优化粒子滤波方法能够有效解决粒子贫化问题，提出的EHHOPF方法的滤波精度与滤波稳定性随粒子数量增加而提升，且优于PF, IKHPF, BAPF和ICSPF等方法；

(2)提出的EHHOPF在序贯采样后期通过引导粒子向高似然区运动改善合理化粒子分布，有利于保证滤波精度；

(3)EHHOPF方法的系统状态单步预测时间优于IKHPF, BAPF和ICSPF方法，且粒子数量增大时单步预测时间趋于稳定，能够满足实时滤波要求。对于系统含非线性非高斯噪声与高斯噪声两种情况，EHHOPF方法均保障了较好的滤波性能，具备一定的鲁棒性。

图 1 高斯分布和二项分布

下载: 全尺寸图片幻灯片

参考文献(10)

SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484–1509. doi: 10.1137/S0097539795293172

NSA. National Security Agency. Cryptography today[EB/OL]. https://www.nsa.gov/ia/programs/suiteb_cryptography/, 2015.

NIST. Post-quantum cryptography standardization[EB/OL]. http://csrc.nist.gov/groups/ST/post-quantum-crypto/submission-requirements/index.html, 2016.

中国科学技术学会. 科普时报: 中国科协发布12个领域60大科技难题[EB/OL]. http://www.cast.org.cn/art/2018/6/22/art_90_77662.html, 2018.

REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. The 37th Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93.

AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA,1996: 99–108.

ZHANG Jiang, YU Yu, FAN Shuqin, et al. Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes[R]. Cryptology ePrint Archive 2019/510, 2019.

APPLEBAUM B, CASH D, PEIKERT C, et al. Fast cryptographic primitives and circular-secure encryption based on hard learning problems[C]. The 29th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2009: 595–618.

MICCIANCIO D and REGEV O. Worst-case to average-case reductions based on Gaussian measures[C]. The 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004: 372–381.

PEIKERT C. An efficient and parallel Gaussian sampler for lattices[C]. The 30th Annual Conference on Advances in Cryptology, Santa Barbara, USA, 2010: 80–97.

施引文献

期刊类型引用(7)

1.	姚正，鲁兵. SDN网络中STP避环的设计与实现. 通化师范学院学报. 2024(04): 44-49 . 百度学术
2.	孙毅，彭杰，武光华，史轮，李飞，汪洋. 电动汽车充电网络的软件定义理论、架构及关键技术. 供用电. 2024(12): 33-46 . 百度学术
3.	史久根，杨旭，刘雅丽，孙立. 软件定义网络中快速和一致的流更新策略. 电子与信息学报. 2021(09): 2617-2623 . 本站查看
4.	黄梅根，汪涛，刘亮，庞瑞琴，杜欢. 基于软件定义网络资源优化的虚拟网络功能部署策略. 计算机科学. 2020(S1): 404-408 . 百度学术
5.	史久根，王继，张径，徐皓. 软件定义网络中基于流量管理的分布式防火墙策略. 电子与信息学报. 2019(01): 91-98 . 本站查看
6.	史久根，张径，徐皓，王继，孙立. 一种面向运营成本优化的虚拟网络功能部署和路由分配策略. 电子与信息学报. 2019(04): 973-979 . 本站查看
7.	史久根，贾坤荥，邾伟，张径. 基于软件定义的数据中心网络虚拟机迁移规划. 电子测量与仪器学报. 2018(02): 119-127 . 百度学术