赵冬梅 周 波 宋 阳 周国军

（海军大连舰艇学院基础部 大连 116018）

1 引言

无人机（UAV）结构简单，价格低廉，安全性好，适用于执行侦察、攻击和评估等军事任务。2020年1 月3 日，美国出动无人机在巴格达机场附近暗杀前伊斯兰革命卫队圣城军指挥官苏莱曼尼［1］。随着无人机技术的发展，在未来战场上，无人机将大显身手，成为陆、海、空战的主力。航迹规划是无人机完成任务的前提，是无人机技术研究的关键环节。航迹规划的目的是在复杂的战场环境中，在满足一定的约束条件下，寻找一条从出发点到目标点的最优路径［2］。目前，国内外学者围绕无人机的航迹规划算法开展了大量研究［3］，主要分为Dijkstra算法［4］、模拟退火算法［5］和人工势场法［6～7］等传统经典算法和遗传算法［8］、粒子群优化算法［9］和蚁群优化算法［10～11］等现代智能算法。

相比于经典算法，智能优化算法以其概念简明、实现方便、参数设置少、鲁棒性强［12］等优点越来越受到研究学者的青睐。文献［13］采用基于时间和空间的信息素挥发因子自适应更新策略改进蚁群算法，保证搜索范围的同时加快了收敛速度；文献［14］提出改进变步长蚁群算法，兼顾较大的搜索区域和较少的迭代次数，提高算法的全局寻优能力；文献［15］将起始点和目的点的直线连线作为对角线划定矩形区域，区别初始化区域内和区域外的信息素浓度，利于减小搜索初期的盲目性，但没有进一步细化信息素差异；文献［16］提出一种新的信息素更新机制，在迭代后期将每代最优路径长度引入信息素增量公式中，区分不同搜索时期的信息素更新，但以固定的迭代次数作为划分依据，降低算法的灵活性；文献［17］根据最优解增加最优路径上的信息素，根据最差解减弱最差路径上的信息素，提高了蚁群算法的收敛速度，但没有解决易陷入局部最优问题。

综合上述文献对蚁群算法改进的优缺点，提出一种新的改进思路：初始化信息素时增大出发点和目标点连线附近的浓度，同时根据距离远近设置浓度差异，使蚂蚁在搜索初期就能沿着目标点方向选择路径，提高搜索的指向性；为提高搜索效率，改进启发函数，增加待选点和目标点的距离信息以及相邻航迹的转角信息；随着算法的进程，优质路径的优势逐渐显现，故在搜索后期进行状态转移时，采用概率选择和确定性选择相融合的策略，进一步提高算法的收敛速度；完善信息素更新机制，根据迭代次数动态调整信息素总量，自适应地进行信息素更新，以平衡算法收敛速度和陷入局部最优之间的矛盾。最后通过仿真实验验证算法的优越性。

2 航迹规划问题建模

2.1 问题描述

无人机在100km×100km×8km的空间区域内从基地出发，到达目标点执行攻击任务，这就需要规划出一条避开障碍物、路径较短、高度起伏和转弯较小的最优航迹。

2.2 三维环境地形建模

采取随机地形和典型地形相结合的方式建立环境地形模型。通过式（1）设置随机地形的高度，模拟较平坦的地形。

式（2）用于模拟典型地形山峰或山谷，n 为山峰或山谷的个数，（xi0，yi0）为山峰或山谷的中心坐标，hi为高度值，通过xis和yis设置峰谷的陡峭程度。

取随机地形和典型地形的较大值为坐标点（x，y）对应的实际高度值z，如式（3）所示。

2.3 三维空间抽象建模

参考文献［18］，在三维坐标系下，沿x 轴取经度方向，沿y 轴取纬度方向，沿z 轴取海拔高度方向。当无人机执行任务的搜索空间确定后，其在三维坐标系下的路径空间也随之建立。以xGrid、yGrid、zGrid为步长分别对x、y、z 三个方向进行等分，从而确定航迹规划空间内离散化的三维点集合。无人机航迹规划可以抽象为在这些三维点中进行航迹点选择，确定从出发点S（xs，ys，zs）到目标点T（xt，yt，zt）的最优航迹。

2.4 搜索区域规则

为降低航迹规划的复杂度，规定经度方向为蚂蚁移动的主方向，即无人机沿x 轴方向以xGrid的固定步长移动，同时设置蚂蚁沿纬度和高度方向均有最大允许移动距离，分别为Dymax和Dzmax，这就为蚂蚁选择下一航迹点提供了一个较小的可搜索空间，进一步提高算法的运行效率。

3 改进蚁群算法

3.1 蚁群算法原理

蚂蚁从出发点开始，根据信息素τij(t)和启发函数ηij(t)按照式（4）的概率选择下一个节点，直至到达目标点并计算航迹距离。

式（4）中，allowm为蚂蚁m 待访问节点的集合，α和β分别为信息素和启发函数重要程度参数，体现蚁群先验知识和未探知航迹的权重大小。

随着时间的推移，信息素浓度会逐渐挥发，ρ为挥发因子，当所有蚂蚁寻找到一条从出发点到目标点的航迹后，信息素按式（5）进行更新。

重复上述计算转移概率、确定下一节点、计算各个蚂蚁路径长度、更新信息素浓度的步骤，直至迭代结束，得到最优航迹BestPath。

3.2 非均匀初始化信息素

信息素是吸引蚂蚁移动的主要因素之一，合理设置信息素的初始值和更新方法是蚁群算法有效实现的重要保证。传统蚁群算法设置浓度相同的信息素初始值，信息素的均匀分布增加了蚂蚁搜索初期的难度，使算法不易收敛。为引导蚂蚁从出发点朝着目标点方向移动，设置非均匀分布的信息素初始值。

以无人机出发点和目标点的连线ST 为中心，向四周空间辐射的信息素浓度逐渐减小。设计方法为计算空间中任一航迹点到直线ST 的垂直距离d，该航迹点信息素的初始值τ与距离d 服从指数分布，二者关系为

其中，τ0为ST上航迹点的信息素初始值，也是信息素初始值的最大值。

根据上述设计，信息素初始值呈现以出发点和目标点连线为中心的指数递减分布，突出了搜索初期从出发点到目标点的引导性，极大提高了算法的效率和准确性。

3.3 基于距离和转角的启发信息

启发信息是吸引蚂蚁移动的另一重要因素，文献［20］将目标节点信息加入启发因子中，利于算法收敛，但忽略了局部最短路径，易出现折线路径。为此，本文将待选航迹点与目标点距离和相邻航迹间的转角两项因素融入启发函数中，降低蚂蚁转弯的概率，进一步缩短航迹，减小无人机能耗。

其中，γ1、γ2、γ3为上述三个因素的权重因素，代表它们各自的重要程度。

1）相邻航迹点距离

Dij的计算公式如下：

式中，（xi，yi，zi）为当前航迹点的坐标值，（xj，yj，zj）为待选航迹点的坐标值，该启发信息的设置有利于蚂蚁选取距离较短的航迹点。

2）待选航迹点与目标点距离

Qij的计算公式如下：

式中，（xj，yj，zj）为待选航迹点的坐标值，（xt，yt，zt）为目标点的坐标值，该启发信息的设置有利于蚂蚁选取距离目标较近的航迹点。

3）相邻航迹线的转角信息

式中，ε是值大于0 的转角调整系数，目的是防止Φij的分母为0，该启发信息的设置有助于蚂蚁选取转角较小的航迹点。

3.4 融入确定性选择的状态转移策略

选择下一节点j的方法为

其中，q 为0～1 之间的随机数，q0为0～1 之间的可调参数，表示使用确定性节点转移策略的概率。

3.5 动态调整的信息素更新机制

改变传统蚁群算法信息素总量Q 固定不变的机制，以算法迭代次数为变量控制Q的取值。在搜索初期，由于蚂蚁主要根据非均匀初始化的信息素浓度寻找航迹，可设置较大的Q 值，有助于提高搜索效率；随着算法的推进，经过一定次数的迭代，各航迹上的信息素数值较大，为避免阻塞和停滞，应适当降低Q 值，利于蚂蚁进行全局搜索；在算法后期，蚂蚁已基本找到最优航迹，为加快算法收敛，可再适当增加Q 值。因此，设计信息素总量Q 随迭代次数服从倒置的高斯分布，表达式为

其中，l为迭代次数，c取值为最大迭代次数的1/2，σ取值为最大迭代次数的1/4，设置信息素总量Q 的取值范围在［Qmin，Qmax］区间内。

对于信息素更新公式（5），为平衡算法的全局搜索能力和收敛速度，采取参考文献［21］提出的自适应信息素更新策略，公式为

其中，φm=a·l，和迭代次数l成正比，a为常数。

3.6 航迹评价函数

航迹评价函数体现无人机航迹规划的优劣程度。本文设计基于航程距离代价、海拔高度代价和相邻航线转角代价的航迹评价函数，表达式如下：

其中，ωD、ωH和ωθ分别为航程、海拔和转角代价的权重因子。

上述评价指标兼顾了飞行距离、高度和转角，能够引导蚂蚁选择出长度较短、高度起伏较缓和转动角度较小的最优航迹。

4 算法流程

应用改进蚁群算法进行无人机三维航迹规划的流程如图1所示。

图1 改进蚁群算法流程图

5 仿真实验与结果分析

为检验本文提出的改进蚁群算法的有效性，进行如下仿真实验。设置蚂蚁数量为20，出发点和目标点坐标分别为（1，20，4）和（100，80，5），最大迭代次数NC=400。环境建模参数如表1所示。

表1 三维环境建模参数

传统蚁群算法和改进蚁群算法规划的航迹如图2所示。

图2 传统蚁群算法和改进蚁群算法规划航迹对比图

由图2 可见，传统蚁群算法规划的航迹转弯点较多，增加了无人机的飞行距离；而改进算法规划的转弯点较少，航迹较平滑，提高了无人机的飞行性能。

传统算法和改进算法的航迹评价函数值随迭代次数变化的曲线如图3所示。

图3 传统蚁群算法和改进蚁群算法航迹评价函数值对比图

随机选取3 次实验，记录两种算法在航迹长度、转角和、迭代次数和运行时间等方面的结果如表2所示。

表2 传统蚁群算法和改进蚁群算法的性能对比

综上所述，与传统蚁群算法相比，改进后的算法在搜索初期具有较强的收敛性，整体迭代次数更少，规划的航迹长度更短，航迹转角和更小，这充分说明改进蚁群算法的优越性。

6 结语

本文采用改进的蚁群算法进行无人机航迹规划。为克服初始阶段蚂蚁搜索的盲目性，加强起点和终点连线附近的信息素浓度，并由近及远形成遵循指数衰减分布的浓度梯度，极大提高了第一代蚁群的搜索效率。设计基于相邻航迹点长度、待选航迹点与目标点长度和相邻航线转动角度三个要素的启发函数，进一步平滑航迹，缩短航程，减小无人机油耗。在搜索后期进行航迹点选择时，采用概率选择和确定性选择相融合的策略，进一步提高算法的收敛速度。改进信息素更新机制，根据迭代次数自适应调整信息素总量和更新信息素，以兼顾算法收敛速度快和全局搜索能力。仿真实验表明：改进后的算法具有较强的全局搜索能力，有效减小了迭代次数，较大程度提高了航迹规划的质量。