曹建秋，张广言，徐 鹏

重庆交通大学 信息科学与工程学院，重庆400074

无人飞行技术是当前很多领域的重要研究内容之一[1]，其中包括地形勘测[2]、无人运输、民用无人机[3]等。路径规划是无人机任务规划中最重要的一部分，它需要在一定的约束条件下，获取自起始点到目标点的安全、快速和最小消耗的路径[4-5]。通过建立模型，可将路径规划问题看作一个复杂的优化问题，需要高效的算法来进行求解。

近年来，各种智能算法相继提出并应用在路径规划问题上，其中包括粒子群算法（particle swarm optimization，PSO）[6]、遗传算法（genetic algorithm，GA）[7]等，随着问题复杂度的增加，传统群智能算法往往产生过快陷入局部最优解、迭代过慢等问题[8]。在此基础上，一些针对群智能算法进行改进的算法相继被提出，较为有效地解决了上述问题。

灰狼优化（gray wolf optimazer，GWO）算法是一种新兴的群智能元启发式算法，其在2014年被Mirjalili提出。此算法借鉴了灰狼的社会组织与狩猎时的行为模式，具有很强的探索能力[9-10]。与其他元启发式算法相比，灰狼优化具有不需要计算梯度、算法灵活简单、便于实现等优点。作为一种高效的优化算法，灰狼优化被大量应用在许多工程应用问题[11-12]。但与之前的群智能算法相同，灰狼算法同样具有与前文算法类似的问题，为解决这一问题，现有的对于灰狼优化算法的改进主要体现在三方面：第一，引入非线性惯性权重以及自适应交叉编译策略，如李靖等人[13]通过引入余弦收敛因子加快狼群在找到猎物后的攻击速度，即迭代后期的收敛速度，袁光辉[14]通过使用具有正弦曲线特性的惯性权重提升搜索能力与寻优精度，并引入了自适应交叉编译策略，使得适应度较低的个体通过变异避免算法后期陷入局部最优；第二，引入路径微调算子，如刘二辉等人[15]在其改进的灰狼优化算法中引入了按照情景设定的路径微调算子和邻域变异算子，提高了算法的局部开发能力，避免算法迭代到后期的进化停滞；第三，引入新的初始解生成算法，文献[15]同样使用了一种自定义的启发式规则生成初始解，提升了初始种群的数量，进而提高了算法稳定性。

为了提高路径规划问题的收敛速度，结合不同元启发式算法的全局或局部搜索能力，提出一种基于A*初始化的变异灰狼优化算法（A* initialized mutable gray wolf optimazer，AMGWO）。该算法可快速计算无人机的最优路径，然后通过三次B样条曲线进行路径平滑。

1 基础原理和方法

1.1 无人机路径规划的数学模型

建立分阶段求取最优节点的地图模型，其二维表示如图1 所示。其中，Pstart与Pend分别代表无人机路径的初始点和目标点，通过两点连线构建搜索空间的x、y、z坐标轴。将搜索空间按列分为N个阶段，图中Li为阶段所在的直线，通过在每个阶段上选取点{P1,P2,…,Pn}来生成最终的路径。threati代表第i个威胁源，其半径表示为ri。当路径落入威胁区时，无人机将受到来自地面攻击设施、障碍物或其他飞行器的阻挡。故引入代价函数，如下节所述。

图1 威胁模型Fig.1 Threaten model

1.2 代价函数

代价分为燃料代价和威胁代价，假设无人机保持匀速航行，则到达阶段Lk时的燃料代价退化为路径长度[16]：

式中：li代表了阶段Li-1与阶段Li之间的所选路径线段（简称线段）长度。

为简化问题复杂度，提出一种威胁代价函数，其通过路径线段与威胁源和威胁边界两者的距离来确定，当路径某段线段落入威胁区时，线段距离威胁源越近，威胁代价越大，反之越小，但不会低于0，函数表达如下式：

式中：ri代表第i个威胁源的半径，di,k代表第k段线段与威胁源的最短距离。ReLU函数的图像如图2所示。

图2 ReLU函数的图像Fig.2 Graph of ReLU

综上，阶段Lk上的总代价为：

1.3 A*算法

A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。其能够在具有任意形状的威胁和各种约束下进行路径规划[17]。作为一种搜索算法，A*可以提供一种较优的可行解，使得在其基础上迭代的算法拥有一个较优的起点。

A*算法的代价公式表示为：

式中：f(n)是经由状态n的整体代价估计；g(n)是从初始状态到状态n的实际代价；h(n)是从状态n到目标状态的估计代价。

1.4 灰狼优化

灰狼优化算法是一种新的元启发式算法，现已被用在路径规划问题上，成为一种有效的路径规划算法[18]。

1.4.1 灰狼优化更新过程

灰狼优化算法的优化模式具有较强的开发能力，并且由于其不需要计算梯度的特性，使得该算法运行速度快，迭代之间的种群变化较大，可以成为较为有效的进化框架为后续局部开发算法提供配合。

灰狼优化通过以下公式更新狼群：

式中：t指当前迭代，Xi代表第i个个体在搜索空间中的位置，Xp是目标的位置，系数向量A和C表示为：

式中：r0,1代表在（0，1）之间随机取一个值，不同式中的r0,1不相等。a是一个随着迭代从2到0线性减小的值。

标准灰狼算法中，狼群适应度前三的个体被称作头狼，分别定义为α、β和γ，其余的个体为ω。实际搜索过程使用以下公式进行更新：

每次更新完毕后，从群体中重新选举头狼。

1.4.2 灰狼优化的收敛性

收敛性是评价一个算法是否可以收敛到全局最优解的指标，其通过数学方法对算法进行收敛性分析，进而证明算法的有效性[19]。马骏等人通过马尔可夫过程相关理论给出了标准灰狼优化的收敛性分析，证实了灰狼优化的概率矩阵存在全局最优解，且收敛概率为1[20]。

1.5 B样条路径平滑

在无人机实际飞行作业中，机器硬件本身具有各种性能限制，例如最小转弯半径、最大加速度等约束。为避免飞行器出现瞬间转弯或路径曲率变化超过性能限制的问题，AMGWO 算法采用B 样条曲线进行路径平滑，其曲线如图3所示。

图3 B样条曲线Fig.3 B-spline curve

2 A*初始化的变异灰狼优化算法

AMGWO算法的前半部分结合了A*算法和灰狼优化的优点来解决全局有效搜索的问题，通过对A*算法在离散化的低精确度地图上求取结果，以向灰狼算法提供一个适应度较高的初始头狼。通过灰狼优化的全局搜索能力保证对搜索空间的探索能力。

AMGWO 算法的后半部分使用了修正变异算子对狼群个体进行变异，以增强狼群的局部搜索能力。此变异算子是针对路径规划问题而提出的修正变异算子。

2.1 AMGWO算法

2.1.1 初始化

AMGWO算法种群初始化过程包含头狼的A*初始化与狼群的随机初始化两个步骤，头狼与随机生成的狼群数量总和为设定的种群个体数。

对于通过迭代方式进行优化的群智能优化算法，一个较优的起点可以指引群体在迭代前期的移动方向，减少算法在迭代前期由于头狼适应度过低导致收敛不明显，并加快其整体的收敛速度，减少达到理想最优值的时间。

本文使用A*算法进行头狼的初始化，由于算法具有离散性，不能对连续化open区间求启发式函数，通过在每一阶段上均匀选取n个点加入open区间进行前向搜索，保证了搜索范围，同时又简化了open区间。此时算法只能得到可行解，不能得到最优解，故需要结合后续算法进行优化。为了加快迭代速度，且降低过快陷入局部最优的概率，将头狼简化为一只[6]。

此时，A*的代价函数f(k)可由下式表示：

狼群的初始化采用随机选取每阶段节点的方式进行，此时只能找到无威胁约束域下的可行解。

2.1.2 通过灰狼优化更新狼群

头狼仅一只时的狼群更新公式如下：

将参数a设为1，使狼群全局搜索能力不随迭代下降。

2.1.3 修正变异

为提高种群质量，提出一种路径微调算子，其针对路径规划问题中产生的解使用了随机变异的方式进行微调，称其为修正变异算子。此方法通过随机修正个别路径点使其落在前后点所在直线上，从而优化路径。对于路径规划问题，一个n维的个体中，第k个维度上的值与其前后两个维度上的值紧密相关（两点之间直线最短）：

式中：ik,amend是个体Xi上第k维的值被前后值修正后的值。而使用这一新值的个体被称作Xi,amend，将其与原值进行对比。新的个体生成按照下式：

同随机变异一样采取择优保留策略的修正变异算子增强了算法的收敛性，经过修正变异后的个体代价将不会升高。此步可设定执行概率来加快整体优化速度。

2.2 搜索步骤

如图4所示，AMGWO主要分为两步：

步骤1初始化。首先用A*算法初始化头狼，并且随机生成最大种群数量减一的狼群，随后将头狼置入狼群。

步骤2更新迭代。开始种群迭代后，每一次迭代过程中，首先使用式（14）对狼群进行位置更新，随后随机选取一部分狼，通过式（16）、（17）对它们进行修正变异。当迭代次数达到设定值后结束迭代并返回结果。

2.3 算法性能分析

2.3.1 计算复杂度

如图4 所述，AMGWO 算法共可分为三大部分：步骤1初始化在算法开始执行时仅执行一次，其中包含A*算法和种群初始化。步骤2为灰狼优化算法更新群体，步骤3为修正变异，此两步在迭代中反复执行。对于一个包含N个个体，每个个体表示为一个D维向量的种群来说：

图4 AMGWO的算法流程Fig.4 Algorithm flow of AMGWO

步骤1初始化。A*算法使用离散的模型，通常将连续化模型离散为包含D×Dy个点的网格地图，由于其带有有向性，并且open表总是下一阶段的全体节点，故复杂度为O(D×Dy)，通常情况下Dy为较小的有限值（一般取6到10），故其复杂度应为O(D)。种群初始化涉及到N个D维向量的随机初始化。此阶段的计算复杂度为O(N×D)。

步骤2GWO 的更新。通过种群最优个体的影响，GWO 将每个个体更新为一个新的个体，其中不涉及其他运算，故此阶段的复杂度应为O(N×D)。

步骤3修正变异。随机选取个体向量上的某个维度，通过相邻维度的值的影响重新分配其值来更新个体，此阶段的复杂度为O(N×D)。

额外步：代价的计算。计算路径上每个线段与全部威胁间的威胁代价，即点到线段的距离，若威胁区数量为T，则此步的复杂度为O(D×T)。

综上所述，算法的时间复杂度为O(N×D×T)，已知N、D、T皆为有限常数，则证明该算法具有最快级别的速度。

2.3.2 收敛性分析

由前文所述可知，AMGWO在简化的灰狼优化过程中使用了精英保留策略，故增强了算法较原GWO 算法的收敛性[21-22]。同样的，在修正变异算子中，使用了择优保留的策略，同样可使算法概率矩阵存在一个全局最优，并且收敛概率为1。

3 仿真实验

为说明AMGWO 相比于其他算法的优越性，设计了3 个仿真案例（分为二维环境和三维环境，二维环境指表中去除第3个维度的环境）来对AMGWO算法的性能进行评估，具体案例参数如表1所示。

表1 3个案例的各项参数Table 1 Parameters of 3 cases

起点与终点分别设定为搜索空间的左边界和右边界中点。最大迭代次数为100，种群个数设定为50，μ为0.5。对3个仿真案例分别使用AMGWO、PSO、GWO、SOS[23]进行10次独立搜索，记录各算法收敛速度以及统计结果。

本实验使用一台CPU 为AMD R5 3500H 的笔记本电脑，程序使用Python 3.7于PyCharm中编写。

3.1 修正变异概率的参数分析

为确定修正变异概率Pamend的最优取值，取二维环境的第一个案例，在步长为0.01的情况下，将Pamend自0取至1，分别执行路径规划。

在图5（a）中，当本文提出的算法（AMGWO）不使用修正变异算子(Pamend=0)时，其规划代价较于使用修正变异算子(0

图5 参数随变异概率Pamend 的变化Fig.5 Variation of parameters with Pamend

3.2 二维环境规划

对于第一个案例，图6（a）展示了5 个算法（包含用于初始化的A*算法）的实验结果以及差异对比。图中可见，4 个算法均获得了可行解，其中本文提出的算法（AMGWO）表现虽好，其规划出的曲线减少了绝大部分不必要的弯曲，并且满足B 样条曲线的定义，意味着曲线满足无人机的转弯性能要求。其余3 个算法得到了可行解，但不是最优，并且在曲线中可以看到不必要的弯曲。

图6（b）展示了4 个算法的代价收敛曲线。可以看出，在A*算法的初始化下，AMGWO的代价收敛起点大大低于其他算法，随着迭代，收敛效果较好。GWO算法虽然收敛速度较快，但在约40 次迭代时进入了局部最优，后续未能跳出。PSO效果略好于GWO，但同样收敛到了局部最优。SOS随着迭代进行整体呈下降趋势，但收敛速度较慢，并且在局部最优停留时间略长。

图6（c）展示了4 个算法分别在10 次独立执行结果中的最优值、平均值和最差值。首先可以看出，AMGWO算法在10 次执行中均得到了收敛较好的解，这意味着该算法具有良好的稳定性。而对于其他算法，在平均值和最差值上均有不同程度的升高，其中SOS变化幅度最大，这表明了其他算法具有较差的稳定性，不可用于实际飞行。

图6 二维案例1的运行结果与统计Fig.6 Optimization results and statistics of 2D Case1

在第二个案例中，增加了威胁源摆放的复杂度，从图7（a）可看出，AMGWO仍然搜索到了最优路径。PSO的结果最接近AMGWO，但相比之下其曲线包含了多余的弯曲。GWO 和SOS 得到的路径是失败的，它们均穿过了威胁区，从图7（b）中的收敛曲线可看出，GWO收敛速度较快，其在最快的时间里得到了除AMGWO 的结果之外的最优解，但结合路径曲线可知，其结果是失败的。而AMGWO有着最好的代价收敛曲线和结果。图7（c）同样展示了算法的稳定性差异，其中AMGWO 算法最为稳定。而另外三者有着较差的稳定性，其中PSO 较好，另外两者较差。在第三个案例中，将威胁区简化为两个，如图8 所示，在100 次迭代后，AMGWO 找到了最优解，PSO 与GWO 的规划结果较AMGWO 相差不大，但出现了不必要的弯曲路径。收敛曲线与统计结果与前两个案例相似，依然表现出了前文所述的代价收敛特征和稳定性差异。四种算法的统计结果见表3。

图7 二维案例2的运行结果与统计Fig.7 Optimization results and statistics of 2D Case2

图8 二维案例3的运行结果与统计Fig.8 Optimization results and statistics of 2D Case3

3.3 三维环境规划

三维环境通过增加阶段上节点维度来增加问题复杂度，但算法本质相同。图9（a）展示了三维环境中各个算法的最终规划路径，在增加了问题复杂度的情况下，AMGWO 算法的结果仍然保持了最优，没有多余的弯曲，而其余算法均有了更大程度的弯曲。这得益于其所使用的修正变异算子，其对路径规划问题做了针对性优化。图9（b）展示了四种算法的收敛曲线，在三维环境中，GWO 的表现较二维有较大幅度的恶化，而SOS 和PSO保持了正常的收敛速度，这说明了对于高复杂度的问题，AMGWO算法仍然保持了高性能。在图9（c）中，四种算法的表现与前文相似，均表现了前文描述中各自的稳定性。

图9 三维案例1的运行结果与统计Fig.9 Optimization results and statistics of 3D Case1

在图10中，与二维环境相同，图（a）中威胁区的半径增大，摆放复杂度也有了提升，在这种环境下，AMGWO在所得结果、收敛曲线和统计结果所表现的稳定性方面均有较高程度的领先。

图10 三维案例2的运行结果与统计Fig.10 Optimization results and statistics of 3D Case2

图11展示了大威胁半径与减少威胁区个数的环境下四种算法的表现，除AMGWO 算法的结果仍保持较好的领先外，其余算法的效果较差。具体表现为没有减少不必要的弯曲，收敛速度过慢且最终结果较差，统计结果也表现了它们的稳定性过低的特点。

图11 三维案例3的运行结果与统计Fig.11 Optimization results and statistics of 3D Case3

四种算法的统计结果见表2。

表2 四种算法路径代价统计结果Table 2 Path cost statistics of four algorithms

3.4 规划时间对比

将各算法迭代100次所消耗的时间如图12所示，综合前文所述，GWO 的速度最快，PSO 次之，但搜索效果较差，往往不能得出最优解，甚至可能出现规划失败情形。SOS的效果一般，执行慢，迭代也慢，无法满足无人机实用要求。

图12 规划时间对比Fig.12 Comparison of planning time

AMGWO 的规划时间略高于PSO 和GWO，但搜索效果最好，结合前文代价收敛曲线可看出，AMGWO 的收敛速度较快，通常在10 至40 次迭代中即可寻出一个较好的全局最优解，故该算法具有良好的性能。规划时间统计结果见表3。

表3 规划时间统计Table 3 Planning time statistics s

4 结束语

针对带有威胁源的复杂区域无人机路径规划问题，本文提出了一种A*初始化的变异灰狼优化算法，称为AMGWO算法。该算法使用了A*算法作为初始化种群首领，极大提升了种群的收敛效果，明确了种群搜索的大致方向，避免了盲目搜索。同时提出了一种新型的修正变异方法，通过个体上相邻维度之间的特定关系，修改个体的值，达到优化路径与提升搜索质量的效果。随后阐述了路径平滑的常用算法优缺点。使用三次B 样条曲线平滑使最终生成的航迹适合无人机实际飞行。

在实验部分，参数分析表明，修正变异算子有其必要性。实验结果分析表明，AMGWO算法能够获得一条高效、安全的路径。并且与其他算法的对比，也证明了AMGWO 算法在解决无人机路径规划问题上具有较高的应用价值。