改进蚁群算法在地形跟随航线规划问题中的应用 *

陶杨，周益，蒋黄滔

（1. 中国人民解放军92728 部队，上海 200436；2. 江西洪都航空工业集团有限责任公司，江西 南昌 330024）

0 引言

航线规划是飞机任务规划系统的重要组成部分，其要求是在给定环境和特定约束条件下，规避地图障碍物，找寻起止点之间的最优飞行轨迹［1］。地形跟随航线规划作为航线规划的一个重要分支，更被广泛应用于飞机/直升机的低空突防作战和无人机自主飞行任务系统中，为顺利完成作战任务提供了有效的手段。航线规划实质是路径规划，近年来，对该问题的求解方法有很多种，既有解析法［2］、人工势场法［3］、A*算法［4］等传统方法，也有蚁群算法［5］、遗传算法［6］、萤火虫算法［7］等新兴智能算法。大量研究发现，在解空间复杂程度较低的环境中，上述方法均可取得较好效果，适用度较高，但处理大规模的问题时却表现一般，主要原因为传统算法因需遍历解空间内的所有节点，算法搜索开销大、效率较低；而标准智能算法普遍易陷入局部最优的优化停滞状态，因此，直接使用的效果均不尽理想。在算法选择方面，相比而言，蚁群算法的蚂蚁觅食行为与航线规划有高度的相似性［5］，因此，采用蚁群算法求解航线规划问题是相对最为合理的也是适应度最高的方法。同样，标准蚁群算法也有一些缺点，例如性能优劣与关键参数强相关、关键参数设置经验性和随机性突出，收敛速度慢等，直接用于航线规划效果不佳。鉴于此，本文提出了一种基于改进蚁群算法的快速生成地形跟随航线的通用解决方案。

1 地形跟随航线规划的数学模型

1.1 建立解空间

在进行航线规划前，首先要重构三维地图建立解空间。这里以地图数据的某一顶点为坐标原点，以经度、纬度和高度的增加方向为3 条坐标轴，以地图数据的极值为各坐标轴终点，建立三维坐标系，所包围的立方体区域即构成了航线规划空间。采用空间等分的方法，离散规划空间，抽取航线规划所需的网格点，并由这些点的集合构造解空间。

1.2 约束条件

1.2.1 高度约束

为最大程度实现地形跟随，对航路点高度应有严格要求：

（1） 保证航路点可达，即航路点高度应大于地图地形海拔高度。

（2） 保证航线越障，即前后相邻航路点连线应高于两点间途径地形的海拔高度，即

式中：Hn为前后航路点周围的地形海拔高度；hi，j，k为前航路点海拔；hi+1，j+1，k+1为后航路点海拔；N为前后航路点周围地形点个数。

（3） 保证航路点贴合地形，在同一铅垂面上，应尽量选择海拔高度最低的航路点为中转节点，即

1.2.2 角度约束

在飞机实际航行中，航路点设置受其转弯半径的影响较大，转弯半径越小，对应的转弯角度越小，则机动所需能量越高，耗油量越大，对航程航时影响越明显，因此，在条件允许范围内，航线规划应尽可能搜寻相对平滑的飞行航线。受最小转弯半径约束，航路点转弯角度θi，j，k≥θlim，θlim为最小转弯半径对应的最小转弯角。

1.2.3 距离约束

受导航系统、飞机控制系统以及机动能力的多方面限制，需约束航线规划中每两个航路点之间的航迹距离，即

其中：dmin，dmax分别为最小和最大可用航迹长度；di，j，k为前航路航迹长度；di+1，j+1，k+1为后航路航迹长度。

1.3 目标函数

综合上述约束条件，最优航线可设置为航路点距离与海拔高度之和最小，即可建立目标函数

2 地形跟随航线规划方法

2.1 算法要点分析

2.1.1 信息素更新

蚁群的信息素更新包括两部分为

（1） 实时更新，表示当前蚂蚁信息素对种群的影响，即当前蚂蚁在选择某个节点后对该节点信息素更新，以引导后续蚂蚁的爬行路线

式中：ρ为信息素挥发因子。

（2） 路径更新，表示最优个体信息素对种群的影响，全部蚂蚁遍历完所有路径后，选择最优蚂蚁的爬行路径，更新该条路径上每个途经节点的信息素，保证次轮循环开始后该条路径对蚂蚁种群的引导为

式中：，Q为信息素强度因子；Δτi，j，k为本次循环途经节点。

在路径信息素更新中，相比传统蚁群算法，这里引入了2 种改进方案。

（1）再励学习策略，根据优劣蚂蚁爬行路径情况调整信息素浓度，以达到保障种群的总体优秀程度、提升算法寻优能力的效果。主要操作为增加最优蚂蚁途径节点的信息素浓度，强化最优蚂蚁对蚁群的引导作用；减少最劣蚂蚁途径节点的信息素浓度，降低最劣蚂蚁爬行路线对蚁群的偏离影响。基于该思想，信息素的增量可表示为

式中：q1，q2分别为最优、最劣蚂蚁的信息素强度因子；Lmax为最劣路径；Lmin为最优路径；Mmax为选择最劣路径的蚂蚁数量；M为种群中全体蚂蚁数量；Mmin为选择最优路径的蚂蚁数量。

（2） 自适应信息素挥发因子调整策略。信息素挥发因子ρ反映了蚁群个体之间的相互影响程度，ρ过大时，再次选择被搜索过的路径概率增大，算法随机性减弱，易陷入局部最优；ρ过小时，路径残留信息素浓度较高，算法随机性增强，收敛速度减慢。因此，最佳方案为根据循环迭代结果对ρ值动态调整。根据文献［8］的研究结论表明，ρ的取值范围一般在[0.3，1)。这里，考虑采取自适应的信息素挥发因子，通过判断一定迭代运算下最优路径的偏离程度，动态调整ρ值。具体为首先设置β值初始值为0.3，在计算过程中，若出现累积10 次计算结果的标准差变化范围都在至当前迭代循环次数计算结果的中位数10%以内，表示则令ρ值在其定义域内增加5%，蚂蚁树状移动图如图1 所示。

图1 蚂蚁树状移动示意图Fig. 1 Diagram of tree-like movement

2.1.2 节点选择

综合考虑信息素浓度和启发值，构建适应度函数：

式中：κ为角度补偿系数，表示转弯角对选择航路点的影响，当小于θlim时，飞机在该航路点的转弯半径超出其固有最小转弯半径要求，该航路点被舍弃，反之，角度越大则为算法带来的正反馈越强；α为信息启发因子，反映了蚂蚁在移动过程中累积信息量对蚁群搜索的指导程度，其值越大，表示在蚂蚁移动中起到的作用越大，蚂蚁越可能选择之前的路径，α值越小，表示蚂蚁对之前爬行路径的记忆力越淡，α= 0 时，为传统的随机贪心算法，路径最短点被选中的概率最大；β为期望启发因子，反映了先验知识对蚁群搜索的指导程度，其值越大，蚂蚁越倾向选择局部最短路径，β值越小，表示蚂蚁对先验知识的关心程度越低，β= 0 时，蚂蚁会完全按照信息素浓度确定移动路径。

启发值由行进距离和节点高度共同表征为

式中：S为判断算子，用于判断下一点是否可达；di，j，k为蚂蚁当前所在点与下一点之间的距离和蚂蚁后续待移动节点与终点距离；为蚂蚁当前所在点高度；σ1，σ2分别为距离和高度的权重系数，且σ2≥σ1，目的在于行动距离相等的情况下尽量选择飞行高度更低的点，以优先满足地形跟随的要求。

假设蚂蚁只能沿纵轴增加方向移动，且移动范围有限，移动步长为εi，j，k，采用文献［9］的树状移动法，在铅垂投影面形成下一航路点搜索空间，即点集。

每一点对应的蚂蚁移动概率为

通过轮盘赌的方法，根据移动概率，确定下一点，并进一步判断该航路点的可达性，即检查是否满足航路避障要求。

2.1.3 参数优化

从上述分析可知，α和β与算法收敛速度与成正比、与搜索随机性成反比，为了保证算法质量，需要选取合适的α和β值。根据文献［10-11］的研究结论，考虑算法收敛速度和全局搜索效率，取α∈[1，3]，β∈[1，5]。由于目前尚无完整的理论体系支撑确定两者最优组合方案，所以，常规做法是根据特定研究问题，以穷举法通过大量重复性试验，不断试凑得到满意的组合［11-12］。由于该方法强依赖于主观经验，且耗时较长，效率较低，严重制约了算法最优性能的发挥。为了解决该问题，本文利用粒子群算法对(α，β) 进行优化求解。

粒子群算法源自对鸟类觅食行为的研究，按照“个体认知”和“群体协作”的规则，搜寻离食物最近个体的周围区域，并以此更新自体移动速度和所在位置，并最终聚集到食物周围［13-14］。本文充分利用粒子群算法在参数寻优方面的优越性和算法实现的便利性，寻求(α，β)的最佳组合。

首先，以(α，β)定义域形成二维搜索空间Dim，规模为n的种群中每个粒子在搜索空间中的位置为、速度为。将蚁群算法中的适应度函数作为解函数，在第r步迭代过程中，通过计算解函数在每个粒子上的映射，更新粒子位置和速度，即

式中：c1，c2为加速度因子；RND1，RND2为[0，1]区间随机数；ωr为惯性权重，表示粒子对前序速度的继承能力，根据文献［15-16］的研究结论为

式中：ωstart为初始惯性权重；ωend为迭代结束时的惯性权重；R为总迭代次数。

记录每次循环迭代寻优得到的解函数f(gen)，建立误差函数若在有限次内误差不变，则认为算法已收敛，对应的(α，β)即为所求。

2.2 算法流程

算法主要通过以下步骤实现，流程见图2。

图2 算法流程图Fig. 2 Algorithm flow

图3 粒子群优化(α，β)参数组合误差变化Fig. 3 Parameter combination error variation of particle swarm optimization

step 1： 设置包含山谷区域的规划空间，通过空间等分法，离散规划空间构建解空间。

step 2： 建立小规模种群个体，执行改进蚁群算法进行路径寻优。

step 3： 以step 2 的蚁群移动路径为评价目标，利用粒子群算法，优化求解蚁群算法中(α，β)最优参数组合。

step 4： 以最优路径的标准差变化为粒子群算法结束判断依据，若30 次结果的标准差无变化，则认为粒子群算法已收敛，此时的(α，β)即为所求。

step 5： 建立较大规模的种群个体，代入step 3的优化参数，执行改进蚁群算法进行路径寻优。

step 6： 判断累积10 次计算结果的标准差变化范围是否至当前迭代循环次数计算结果的中位数10%以内，若是，则令ρ值在其定义域内增加5%；若不是，则进入下一步。

step 7： 判断算法是否达到最大迭代运算次数，计算结束。

3 算例分析

本文以某一三维地形为例，验证以上提出的地形跟随航线规划方法。假设该地形经无量纲化处理后的体积为21×21×10，起点和终点坐标分别为（1，18，5）和（21，8，6），飞机需要在与起伏地形无接触的情况下寻找一条与其尽量贴合的最短飞行航线。

3.1 求解最优参数组合

初始化一群只有5 个个体的小型蚁群，设定迭代次数为10 步，以蚁群移动最优路径为目标函数，通过粒子群算法对蚁群算法中的(α，β)参数组合进行优化计算，其中，粒子群算法的种群规模为15，加速度因子均为1.5。结果见图 3。在经过41 步迭代计算，结果已收敛，此时，(α，β)组合对应为（1.966 7，3.927 2）。

3.2 求解最优航线

重新生成个体数为20 的大型蚁群，按照上文方法和思路，将第1 步求得的(α，β)组合参数代入后，对地形跟随航线进行优化求解，结果见图4。从航线质量来看，本文算法在诸多约束条件下，仍能很好地搜寻到可行航线。与传统蚁群算法得到的个体适应度变化见图5，本文算法通过105 步迭代，可得到最优航线路径为117.3，而标准蚁群算法则多次陷入局部最优解，至300 步最大迭代次数结束，仍未完全收敛，此时对应的局部最优航线路径为126.2。时效性上，本文算法完成最大迭代次数耗时1.36 s，而标准蚁群算法为2.52 s，运算速度提高近一倍。

图4 地形跟随航线示意图Fig. 4 Map of dimensionless grain terrain following course

图5 本文算法与标准蚁群算法计算过程比较Fig. 5 Calculation process of this algorithm compared with standard ant colony algorithm

4 结束语

本文针对地形跟随航线规划的特点，将该问题抽象为在特定三维解空间中的最佳路径寻优。进一步，通过对标准蚁群算法的适应性改进和优化，提高了算法适应性，形成了面向地形跟随航线规划问题的通用化解决方案。经算例验证表明，该方法用时短，生成的航线与地貌贴合度高、与地形匹配度好，进一步说明了该方法的有效性，并可在相似领域推广应用。