自动驾驶汽车将成为未来车辆领域的发展方向, 其核心是自动驾驶技术. 路径规划^[1–7]作为自动驾驶技术的关键环节之一, 已成为自动驾驶领域的研究热点. Hou等^[8]提出一种具有通信机制的增强蚁群算法进行路径规划, 通过个体之间的直接通信, 加速历史路径的整合, 同时对路径选择规则和启发式函数进行改进, 提高算法收敛速度和搜索效率; Liu等^[9]提出一种基于改进灰狼算法的路径规划方法, 引入基于狮子优化算法的干扰因子和动态权值, 避免多样性的丧失, 但是跳出局部最优的能力有待加强; Kumar等^[10]提出一种人工蜂群和进化规划算法结合的路径规划方法, 采用人工蜂群算法根据改进策略进行初步搜索, 之后采用进化算法对得到的可行路径进行细化, 降低搜索成本; 徐兴等^[11]将灾变策略和内嵌A*算法的动态变异算子引入遗传算法中, 降低早熟现象并且提高算法后期的局部搜索能力, 同时具有多约束条件的适应度函数提高了所规划路径的平滑度, 但是每次灾变初始化种群, 降低了计算效率.

遗传算法 (genetic algorithm, GA) 虽然全局搜索能力强, 具有易于扩展其他算法的特性; 但是后期染色体相似度高, 存在早熟收敛问题^[12–14]. 量子遗传算法 (quantum genetic algorithm, QGA)^[15]是遗传算法结合量子计算产生的一种新兴智能优化算法. 根据量子态的叠加、纠缠等特性, 引入量子编码和量子旋转门更新操作, 相较于遗传算法, 量子遗传算法具有更好的种群多样性和收敛速度. 然而, 基本量子遗传算法主要依靠量子旋转门进行种群更新, 在组合优化问题^[16–19]求解时, 仍存在稳定性低、收敛性差, 陷入局部最优不易跳出的问题.

本文提出一种基于梯度统计变异量子遗传算法的车辆路径规划方法, 采用动态调整量子旋转门策略, 在根据染色体适应度值动态调整旋转角步长的基础上, 引入梯度下降思想, 提高算法的收敛能力和全局搜索的稳定性; 根据染色体变化趋势的统计特性, 设计变异算子代替量子非门实现变异操作, 提出基于量子位概率密度的自适应变异策略, 以提高算法跳出局部最优的能力. 通过路径规划仿真实验分析, 验证算法有效性.

1 基本量子遗传算法

量子位 (quantum bit, Qubit) 是量子计算机的最小信息单元, 在一个双态量子系统中, 一个量子位状态可描述为^[20]:

$ \left| \varphi \right\rangle = \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle $

(1)

其中, 量子态 $\left| \varphi \right\rangle $ 处于 $\left| 0 \right\rangle $ 态和 $\left| 1 \right\rangle $ 态之间的叠加态, $\alpha $ , $\;\beta $ 分别表示量子态 $\left| 0 \right\rangle $ 和 $\left| 1 \right\rangle $ 的概率幅, 并且满足归一化条件^[20]:

$ {\left| \alpha \right|^2} + {\left| \beta \right|^2} = 1 $

(2)

采用量子位编码初始化种群, 能够以小规模的种群包含复杂的种群信息. 一个初始化量子种群为 $ Q(0) = \left\{ {{q_i}(0)} \right\}, {\text{ }}\left( {i = 1, 2, \cdots , m} \right) $ , $m$ 为种群规模, 每个个体用一条染色体 ${q_i}(0)$ 表示, 一条染色体代表一个可行解, 其编码形式如式(3)所示:

$ \begin{split} &{q_i}(0) = \\ &\left| \begin{gathered} \alpha _{i1}^1(0){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \alpha _{i1}^2(0){\kern 1pt} {\kern 1pt} \cdot \cdot \cdot {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \alpha _{i1}^k{\kern 1pt} (0){\kern 1pt} {\kern 1pt} \cdot \cdot \cdot \alpha _{in}^1(0){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \alpha _{in}^2(0){\kern 1pt} \cdot \cdot \cdot {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \alpha _{in}^k{\kern 1pt} (0){\kern 1pt} {\kern 1pt} {\kern 1pt} \\ \beta _{i1}^1{\kern 1pt} {\kern 1pt} (0){\kern 1pt} {\kern 1pt} {\kern 1pt} \beta _{i1}^2{\kern 1pt} (0){\kern 1pt} \cdot \cdot \cdot {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \beta _{i1}^k{\kern 1pt} (0) \cdot \cdot \cdot {\kern 1pt} {\kern 1pt} \beta _{in}^1{\kern 1pt} {\kern 1pt} (0){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \beta _{in}^2{\kern 1pt} (0){\kern 1pt} {\kern 1pt} \cdot \cdot \cdot \beta _{in}^k{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (0) \\ \end{gathered} \right| \end{split} $

(3)

其中, ${q_i}(0)$ 表示初始化种群中第 $i$ 个染色体; $n$ 为一个可行解中包含的基因位个数, $k$ 为每个基因位编码中包含的量子位个数. 种群初始化时, 为了确保种群分布的均衡性, 染色体中每个量子位的概率幅: $\alpha _{ir}^j(0) = \beta _{ir}^j(0) = {1 / {\sqrt 2 }}$ , 其中, $i = 1, 2, \cdots, m$ ; $ r = 1, $ $2, \cdots, n$ ; $ {\kern 1pt} {\kern 1pt} j = 1, 2, \cdots , k $ .

量子遗传算法利用量子旋转门更新量子位的概率幅实现对问题的搜索寻优. 通常采用的量子旋转门如式(4)所示^[21]:

$ U(\theta ) = \left[ \begin{gathered} \cos \theta {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} - \sin \theta \\ \sin \theta {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \cos \theta \\ \end{gathered} \right] $

(4)

其中, $\theta $ 为旋转角度.

更新后的量子态 $\left| {{\varphi {'}}} \right\rangle$ 为:

$ \left| {{\varphi {'}}} \right\rangle = \left[ \begin{gathered} {\alpha {'}} \\ {\beta {'}} \\ \end{gathered} \right] = U(\theta ) \times \left| \varphi \right\rangle = \left[ \begin{gathered} \cos \theta {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} - \sin \theta \\ \sin \theta {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \cos \theta \\ \end{gathered} \right]\left[ \begin{gathered} \alpha \\ \beta \\ \end{gathered} \right] $

(5)

其中, ${\alpha {'}}$ , $\;{\beta {'}}$ 分别表示更新后量子态 $\left| 0 \right\rangle $ 和 $\left| 1 \right\rangle $ 的概率幅.

在双态量子系统中, 量子位概率幅的更新如图1所示. 量子位概率幅的取值具有连续性, 因此量子遗传算法具备连续空间搜索能力.

2 梯度统计变异量子遗传算法 2.1 自适应量子旋转门

染色体更新过程中, 量子旋转门的旋转角度 $\theta $ 起到关键作用, 其大小和符号决定染色体进化的速度和方向. 在基本量子遗传算法中, 量子旋转门的旋转角度 $\theta $ 通过查表获得, 实现方式繁琐, 并没有根据所需解决的具体问题给出旋转角度选择的依据. 另外, 通过查表获得的旋转角度 $\theta $ 不仅没有考虑种群中染色体的差异性, 而且也未充分利用搜索点的变化趋势.

量子门的旋转角度 $\theta $ 的大小和符号会直接影响算法的收敛速度, 因此, 通过最优染色体与当前染色体对应量子位的概率幅计算量子门旋转方向^[22]. 可以保证当前染色体朝最优染色体方向进化. 令 ${({\alpha _0}, {\beta _0})^{\rm{T}}}$ 为当前最优染色体中某量子位的概率幅, ${({\alpha _1}, {\beta _1})^{\rm{T}}}$ 是当前染色体中相应量子位的概率幅, 记:

$ A = \left| \begin{gathered} {\alpha _0}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\alpha _1} \\ {\beta _0}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\beta _1} \\ \end{gathered} \right| $

(6)

旋转角 $\theta $ 的方向选取原则为: 当 $A \ne 0$ 时, 方向为 $- {{\rm{sgn}}} (A)$ ; 当 $A = 0$ 时, 方向随机选择.

考虑到同一代种群中不同染色体之间的差异, 以及不同代种群之间染色体基因位的变化趋势对群体进化的影响, 将旋转角度的大小和染色体适用度值联系起来, 同时引入梯度下降思想研究染色体基因位的变化趋势, 提出一种旋转角步长自适应调整的方法:

$ \begin{split} &{\theta }_{ir}^{j}=-\mathrm{sgn}(A)\cdot{\theta }_{0}\cdot\\ &\mathrm{exp}\left(a\cdot\dfrac{\left|fi{t}_{{\rm{best}}}-fi{t}_{i}\right|}{fi{t}_{{\rm{best}}}}+(a-1)\cdot\dfrac{\left|\nabla f({X}_{ir})-\nabla {f}_{r\mathrm{min}}\right|}{\nabla {f}_{r\mathrm{max}}-\nabla {f}_{r\mathrm{min}}}\right)\end{split} $

(7)

$ \nabla {f_{r\max }} = \max \left\{ {\left| {\frac{{\partial f({X_i})}}{{\partial {X_{ir}}}}} \right|} \right\}{\text{ }}(i = 1, 2, \cdots , m) $

(8)

$ \nabla {f_{r\min }} = \min \left\{ {\left| {\frac{{\partial f({X_i})}}{{\partial {X_{ir}}}}} \right|} \right\}{\text{ }}(i = 1, 2, \cdots , m) $

(9)

其中, $ \theta _{ir}^j $ 表示第 $i$ 个染色体第r个基因位中第 $j$ 个量子位的旋转角度; $ {\theta _0} $ 表示初始旋转角步长; 权值 $a \in (0, 1)$ 用以体现适应度函数值和基因位梯度对染色体进化程度的影响; $fi{t_i}$ 为第 $i$ 个染色体的适应度值; $fi{t_{{\rm{best}}}}$ 为当前最优染色体的适应度值; $ \nabla f({X_{ir}}) $ 为第 $i$ 个染色体第r个基因位的梯度; $ \nabla {f_{r\min }} $ 和 $ \nabla {f_{r\max }} $ 分别为当前种群中第r个基因位的梯度最小值和最大值.

动态调整量子旋转门策略既考虑染色体适应度值又兼顾染色体基因位变化趋势, 当染色体适应度值距离最优染色体较远且量子位梯度变化较小时, 增大旋转角度, 加快收敛, 反之则需要减小旋转角度, 避免错过最优染色体, 以此提高算法的收敛速度和全局搜索的稳定性.

2.2 量子变异

量子遗传算法虽然具有较强的全局搜索能力, 但仅通过量子旋转门进行种群更新, 易陷入局部最优. 因此, 需要对种群进行一定的扰动操作, 减少“早熟”现象的发生. 传统方法通常采用量子非门对种群中个体量子位的概率幅进行变异操作, 虽然一定程度上能够避免陷入局部最优, 但是当执行变异操作的染色体非常接近最优染色体时, 量子非门变异会造成量子位更新方向的反转, 可能造成种群动荡, 优秀染色体信息丢失. 另外, 该变异算子没有考虑种群中所包含的生物体信息及外部环境等干扰因素对染色体基因变异的影响, 缺乏群体观念.

从全局上, 根据过往染色体信息对当前染色体基因位的影响考虑量子位变异问题, 使量子变异操作能够在种群进化过程中施加合理的扰动, 避免种群过早收敛. 由于基因遗传信息随遗传代数的增加而递减, 当前染色体基因位受父代染色体的影响最大, 因此, 仅考虑父代染色体对当前染色体基因位的影响, 统计过往染色体基因位适应度值的梯度 $\nabla {Z_{ir}}$ :

$ \nabla {Z_{ir}} = \nabla f({X_{ir}}) + o(\nabla f({X_{ir}})) $

(10)

其中, $o(\nabla f({X_{ir}}))$ 表示子代和父代梯度 $\nabla f({X_{ir}})$ 的高阶无穷小量.

根据染色体基因位的变化趋势设计概率密度函数:

$ f(\nabla {Z}_{ir})={\displaystyle \sum _{l}^{5}{b}_{l1}\cdot\mathrm{exp}(-{((\nabla {Z}_{ir}-{b}_{l2})/{b}_{l3})}^{2})} $

(11)

其中, ${b_{l1}}$ , ${b_{l2}}$ 和 ${b_{l3}}$ $(l = 1, 2, \cdots , 5)$ 为高斯混合分布参数.

将式(11)转化为概率分布函数:

$ F(\nabla {Z}_{ir})={\displaystyle \sum _{l}^{5}{b}_{l1}\cdot{\displaystyle {\int }_{-\infty }^{{Z}_{ir}}\mathrm{exp}(-{((\nabla {Z}_{ir}-{b}_{l2})/{b}_{l3})}^{2})}} $

(12)

采用量子位梯度的概率分布作为变异算子对量子位概率幅进行变异操作, 如式(13)所示:

$ \left\{ \begin{gathered} \alpha _{ir}^j(t) = \sqrt {1 - F(\nabla {Z_{ir}})} \\ \beta _{ir}^j(t) = \sqrt {1 - \alpha _{ir}^j{{(t)}^2}} \\ \end{gathered} \right. $

(13)

其中, $\alpha _{ir}^j(t)$ 表示第 $t$ 代第 $i$ 个染色体第 $r$ 个基因位的第 $j$ 个量子位 $\left| 0 \right\rangle $ 态的概率幅; $\;\beta _{ir}^j(t)$ 表示第 $t$ 代第 $i$ 个染色体中第 $r$ 个基因位的第 $j$ 个量子位 $\left| 1 \right\rangle $ 态的概率幅.

另外, 在种群进化过程中, 合理的变异概率有利于提高种群进化的多样性和稳定性. 根据种群中染色体的进化趋势, 提出基于量子位概率密度的自适应变异机制: 依据染色体基因位适应度值的梯度确定当前量子位的变异概率, 在染色体进化过程比较“平坦”时, 给予一个大的扰动概率, 使染色体跳出局部最优, 增加种群多样性; 在染色体进化过程比较“陡峭”时, 给予一个小的扰动概率, 避免破坏拥有优良基因的个体, 提高种群的稳定性. 依据自适应变异概率随机选择个体中的量子位, 施加变异操作, 自适应变异概率如式(14)所示:

$ \begin{split} {p}_{m}&={P}(\nabla Z\geqslant \nabla {Z}_{ir})=1-F(\nabla {Z}_{ir})\\ &= 1-{\displaystyle \sum _{l}^{5}{b}_{l1}\cdot{\displaystyle {\int }_{-\infty }^{{Z}_{ir}}\mathrm{exp}\left(-{((\nabla {Z}_{lr}-{b}_{l2})/{b}_{l3})}^{2}\right)}}\end{split} $

(14)

梯度统计变异量子遗传算法的流程如图2所示.

3 基于梯度统计变异量子遗传算法的车辆路径规划

针对车辆路径规划问题, 本文的主要目标: 在规避静态障碍物的基础上, 得到一条长度最短的可行路径. 做出如下假设: 1) 车辆在有限平面空间中由起始点到目标点匀速移动, 2) 在车辆行驶过程中, 障碍物的形状大小、地理位置均不发生改变; 3) 车辆相对地图中的静态障碍物可看作一个质点.

3.1 构建环境地图

以某工业园区建筑布局为例, 采用栅格地图^[23]进行车辆路径规划研究, 如图3所示, 其中白色栅格表示可行驶区域, 黑色栅格表示障碍物. 车辆的起始点和目标点在图中用五角星符号标记.

3.2 车辆路径规划实现

利用梯度统计变异量子遗传算法规划车辆行驶路径, 首先需要进行路径编码, 通常采用空间位置点 (规划空间中的路径点作为染色体的基因位) 序列表示车辆行驶路径. 这种表示形式只需要考虑每个空间位置点的可行性问题, 有利于路径规划的计算. 假设规划空间为图3所示的栅格地图, 在规划空间内有 $20 \times 20$ 个路径点, ${20^{20}}$ 条路径点组合, 在栅格地图中, 对同一条平行线上的路径点进行量子位编码, 然后将量子编码的路径点排列, 构成一条可行路径, 即构成一条染色体. 染色体编码形式如图4所示.

路径规划主要考虑安全性及路径代价, 本文以路径最短作为车辆路径规划的路径代价. 采用路径点评价函数 $point\_fit$ 确定路径点量子态更新, 根据路径评价函数 $way\_fit$ 确定对路径的选择.

采用欧氏距离构造路径点评价函数, 如式(15)所示, 计算路径点到起始点和目标点的距离之和, 距离越小, 所需代价越小.

$ \begin{split} \min point\_fit =& \sqrt {{{({x_{ir}} - {x_s})}^2} + {{({y_{ir}} - {y_s})}^2}} \\ & +\sqrt {{{({x_{ir}} - {x_g})}^2} + {{({y_{ir}} - {y_g})}^2}} \end{split} $

(15)

其中, $({x_{ir}}, {y_{ir}})$ 表示第 $i$ 条染色体中第 $r$ 个路径点坐标; $(x_s, y_s)$ 表示起始点坐标; $(x_g, y_g)$ 表示目标点坐标.

路径评价函数计算所有路径点依次连接的路径总长度, 如式(16)所示:

$ \min way\_fit = \sum\limits_{r = 1}^{M - 1} {\sqrt {{{({x_{ir}} - {x_{ir + 1}})}^2} + {{({y_r} - {y_{ir + 1}})}^2}} } $

(16)

其中, $M$ 为一条路径中所有路径点的个数.

在车辆路径规划中, 根据式(6)–式(9)对染色体中路径点的每个量子位编码进行量子旋转门自适应更新. 由于路径点的适应度值是离散的, 染色体中路径点的梯度利用相邻两代的一阶差分表示:

$ \nabla {f_{r\max }} = \max \left\{ {\left| {f\left[ {{X_{ir}}(t - 1)} \right] - f\left[ {{X_{ir}}(t)} \right]} \right|} \right\} $

(17)

$ \nabla {f_{r\min }} = \min \left\{ {\left| {f\left[ {{X_{ir}}(t - 1)} \right] - f\left[ {{X_{ir}}(t)} \right]} \right|} \right\} $

(18)

其中, $ i = 1, 2, \cdots , m $ .

通过统计过往染色体中路径点的梯度信息, 得到式(11)中参数的具体数值:

$ {({{\boldsymbol{b}}_1}{\kern 1pt} {\kern 1pt} {{\boldsymbol{b}}_2}{\kern 1pt} {\kern 1pt} {{\boldsymbol{b}}_3})^{\rm{T}}} = \left[ \begin{gathered} 0.7521{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0.1421{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0.1519{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} - 0.6852{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0.04352 \\ 0.5204{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 2.072{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0.1908 {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0.4204{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 5.743 \\ 0.9951{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 2.126{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0.6099{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 1.01 {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 2.565 \\ \end{gathered} \right] $

基于梯度统计变异量子遗传算法的车辆路径规划的总体流程如下.

1) 构建环境地图. 根据已知的规划空间构建栅格地图.

2) 初始参数设置及种群初始化. 设置种群规模popsize为 $m$ , 进化代数 $t$ 以及旋转角初始值 ${\theta _0}$ , 确定车辆行驶的起始点和目标点位置, 对路径点进行量子编码, 初始化种群 $Q(0)$ , 初代染色体中每个路径点量子位的概率幅 $\alpha _{ir}^j(0) = \beta _{ir}^j(0) = {1 / {\sqrt 2 }}$ .

3) 初始量子位坍缩. 对初始种群 $Q(0)$ 中的所有染色体执行测量, 使染色体中的量子位坍缩到一个确定状态 $p(0)$ , 即路径点集合.

4) 初始路径适应度评价. 计算路径点的适应度值 $point\_fi{t_r}(0)$ 及路径适应度值 $ way\_fi{t_i}(0) $ ; 对种群中所有路径的适应度值进行比较, 记录表示当前最短路径的染色体 ${q_{{\rm{best}}}}$ 及其适应度值 $way\_fi{t_{{\rm{best}}}}$ .

5) 量子位坍缩. 对种群 $Q(t)$ 中的所有染色体执行测量, 使染色体中的量子位坍缩到一个确定状态 $p(t)$ .

6) 个体适应度评价. 计算路径适应度值 $way\_fi{t_i}(t)$ 及路径点的适应度值 $point\_fi{t_r}(t)$ , 计算路径点的梯度 $ \nabla f({X_{ir}}) $ ; 对种群中所有路径的适应度值进行比较, 记录表示当前最短路径的染色体 ${q_{{\rm{best}}}}$ 及其适应度值 $way\_ fi{t_{{\rm{best}}}}$ .

7) 量子旋转门自适应更新. 根据式 (6)–式(9) 得到每个量子位的旋转角度 $\theta _{ir}^j$ , 然后使用量子旋转门自适应更新染色体.

8) 量子变异操作. 通过自适应变异机制确定量子位的变异概率 ${p_m}$ , 按照变异概率 ${p_m}$ 随机选择染色体中的量子位, 采用自适应变异算子对这些量子位施加变异操作.

9) 判断是否满足最大迭代次数或收敛条件, 若满足, 则结束算法流程, 输出最短路径; 否则, 迭代次数 $t = t + 1$ , 返回步骤4).

4 仿真实验

为了验证改进量子遗传算法在路径规划中的有效性, 采用栅格法构建车辆路径规划的环境地图, 将规模约为 $4 \times {10^4}\;{{{\rm{m}}} ^2}$ 的某工业园区环境地图划分成 $20 \times 20$ 的栅格地图, 每个栅格的长宽均为0.01 km, 车辆的起始点坐标 $(x_s, y_s)$ 为 $(1, 1)$ , 目标点坐标 $(x_g, y_g)$ 为 $(20, 20)$ . 同时, 设置最大遗传代数 $t = 50$ ; 传统遗传算法(GA)的种群规模 $popsi{\textit{z}}e = 20$ 和popsize = 100, 交叉概率 ${p_c} = 0.8$ , 变异概率 ${p_m} = 0.1$ ; 基本量子遗传算法 (QGA) 的种群规模popsize = 20; 非门变异的量子遗传算法 (N-QGA) 的种群规模popsize = 20, 变异概率 ${p_m} = 0.1$ ; 本文梯度统计变异量子遗传算法 (GSM-QGA) 的种群规模popsize = 20, 初始旋转角度 ${\theta _0} = 0.1{\text π}$ .

对比4种算法的求解精度和收敛速度验证本文算法在路径规划中的性能.

在 $20 \times 20$ 规模的栅格地图中, 4种算法运行5次的路径规划仿真结果如图5–图9所示, 路径收敛曲线如图10–图14所示.

如图5–图14所示, 在相同种群规模的情况下, 当种群数量较少, GA所规划的路径明显过长且收敛速度较慢, 易陷入局部最优; 当扩大GA种群规模到100时, 其路径长度和收敛速度有所改善, 但路径距离仍然存在明显冗余; QGA和N-QGA虽然在路径距离上能够进一步优化, 但搜索到的路径变化较大, 算法稳定性不好, 收敛到最优解所需迭代次数较多, 总体收敛速度仍然有待提高; 本文提出的GSM-QGA能够有效地跳出局部最优值, 并且5次运行结果显示算法稳定性较好.

图15、图16能够更直观对比4种算法在路径规划中的求解精度和收敛速度. 由于算法有一定的搜索随机性, 本文将4种算法的5次运行结果进行统计, 如表1所示. 容易看出, GA在运行过程中收敛速度比较慢, 容易发生“早熟”现象, 且所规划的路径比较冗余. 相较于GA, QGA虽然所需迭代次数较少, 收敛很快, 但也难以跳出局部最优值, N-QGA由于量子非门变异算子的局部扰动, 使算法具有跳出局部最优的动力, 但其变异的幅度较大, 容易造成种群动荡, 收敛速度较慢; GSM-QGA通过自适应量子旋转门更新量子编码的路径点, 所需迭代次数少, 路径收敛速度更快, 另外, 根据过往路径信息设计的变异算子和变异策略, 更合理地对路径规划过程进行扰动, 有效控制算法陷入“早熟”, 得到的规划路径距离更短. 改进的量子遗传算法与其他3种算法相比, 平均路径长度分别缩短 $10.26{\text{%}} $ 、 $7.06{\text{%}} $ 、 $5.52{\text{%}} $ 、 $2.99{\text{%}} $ ; 平均迭代次数分别提高 $ 50.63{\text{%}} $ 、 $ 46.98{\text{%}} $ 、 $ 32.48{\text{%}} $ 、 $ 26.85{\text{%}} $ ; 算法稳定性最优.

为了进一步验证改进量子遗传算法在路径规划中的有效性, 在不同场景下进行对比实验. 选择两个不同的场景, 并将其划分为 $20 \times 20$ 的栅格地图, 为了验证算法的有效性并且控制无关变量, 本文将路径规划的起始点和目标点设置在相同位置, 车辆的起始点坐标 $(x_s, y_s)$ 为 $(1, 1)$ , 目标点坐标 $(x_g, y_g)$ 为 $(20, 20)$ . 通过比较4种算法在不同场景中的仿真结果, 如图17–图20所示. 在较为简单规整的场景中, 除GA外, 其他算法均可搜寻到最优解, 其中本文算法寻得最优解所需的迭代次数最少, 因此收敛速度最快. 当场景较为复杂且多为凹型建筑物时, 4种算法在运算过程中更易陷入局部最优, 从而造成额外的负担, 但从整体实验结果来看, 本文算法在寻优过程中, 仍然能以较少的迭代次数寻得最优解.

5 结论与展望

针对遗传算法在进行车辆路径规划时存在的易早熟、收敛速度慢等问题, 本文提出了一种基于梯度统计变异量子遗传算法的路径规划方法, 算法在根据染色体适应度值动态调整旋转角步长的基础上, 引入梯度下降思想, 改善动态调整量子旋转门策略, 提高算法的收敛速度和搜索寻优的稳定性; 在量子变异部分, 依据染色体变化趋势的统计特性, 设计变异算子, 并提出基于量子位概率密度的自适应变异策略, 有效控制算法陷入局部最优. 结果表明, 改进的量子遗传算法不仅能够规划出一条规避障碍物的车辆可行路径, 并且在路径长度、收敛速度、算法稳定性等方面相比遗传算法、量子遗传算法、非门变异的量子遗传算法均具有优势. 在车辆行驶过程中, 往往存在动态障碍物, 接下来的工作将改进的量子遗传算法与其他算法结合, 进行车辆避撞研究.