改进蚁群算法在飞机突防航线规划问题中的应用

陶 杨，周 益

（解放军92728 部队，上海 200436）

0 引言

在航空兵突击作战中，航线规划是任务规划的重要组成部分，也是实施作战任务的重要保障，其要求为在战场迷雾的众多约束和限定条件下，根据任务区域特定战场环境（主要包括地形地貌等自然环境和敌方布势兵力等威胁环境）及我方兵力突击能力，设置一条符合战场敌我双方态势和作战飞机飞行能力的最优飞行航线。航线规划的本质是路径规划，近年来，国内外学者提出了很多针对该问题的求解方法，既有解析法［1］、人工势场法［2］、A* 算法［3］、Floyd［4］等传统算法，也有蚁群算法［5］、遗传算法［6］、萤火虫算法［7］、粒子群算法［8］、智能体［9］等智能算法。相比传统算法，智能算法独有的自我学习、自我更新、自我进化和记忆保存等能力［10］，能够处理更为复杂的路径规划问题，而受到极高的关注度。其中，由于蚁群算法的蚂蚁觅食行为与路径规划有着高度的相似性［5］，采用蚁群算法求解路径规划问题也成为了相对最为合理的，同时也是适应度最高的解决方案。因此，本文也在蚁群算法的基础上开展了相关的研究工作。

1 算法实现

1.1 威胁区域设置

飞机突防航线规划，可类比理解为路径寻优问题，即在存在若干不可跨越区域的有限大小的地图上，寻找一条从起点到终点的距离短、平滑度高的最佳路径。在忽略自然环境影响的前提下，不可跨越区域即为作战前期由相关作战部门针对威胁对象等确定的战场威胁区域。本文根据威胁对象的可移动属性，将威胁区域分为两类：一类是以预警雷达、防空导弹和电子干扰等固定式或慢速移动式装备，该类装备的威胁区域是以装备位置为圆心，以探测距离、导弹射程和干扰距离为半径的圆形区域；另一类是以飞机、车辆等移动式防空装备，该类装备的威胁区域是以巡逻线+探测/攻击距离构成的跑道型区域。

1.2 解空间建模

建立解空间，常用方法有基于图形规划法、基于栅格规划法等，本文采用基于图形规划法，建立自由空间（makline 图论）［11］，通过各威胁区边界点之间的连线以及与威胁区与地图边界的连线，生成makline 线段，以makline 线段中点作为途经点，构成用于寻找初始航线规划的无向网络图。通过人工筛选，生成n 条从起点O 到终点O*的可行路径集合。

1.3 初始路径选择

1.4 蚁群算法寻优

在得到次优路径后，需对次优路径扩容形成次优路径带，再通过蚁群算法进行深度优化，求得更优的最佳路径。

1.4.1 次优路径扩容

假设Dijkstra 算法得到次优路径dmin需经过O、P1、P2，…，Pn、O*点，其中，Pn点对应的makline 线段端点为、，离散化后，线段中任意节点Pi可表示为

其中，L 为线段等分数。这样就形成了以次优路径为中心的沿线条带区域——次优路径带。

1.4.2 节点选择

通过识别次优路径带上各条路径上的信息素浓度，蚂蚁确定爬行过程中的移动方向。移动过程中，在Li条线段上的蚂蚁，通过式（2）选择Li+1条线段的j 节点

当q＜q0时，先依次计算当前位置的蚂蚁到Li+1条线段的j 节点的状态转移概率pi，j，再通过轮盘赌的方式选择出j 节点。

其中，allowedk表示第k 只蚂蚁下一步可选的节点集合，α 为信息启发因子。根据文献［12］的研究结论，考虑算法收敛速度和全局搜索效率，一般取α=1、β∈［3，5］。在算法初期，应尽量选择较小的β值，以避免算法过早收敛、陷入局部最优；而在算法后期，应尽量选择较大的β 值，以降低算法随机搜索概率、提高收敛速度。因此，本文考虑采取自适应的期望启发因子。通过判断一定迭代运算下最优路径的偏离程度，动态调整β 值。具体为：设置β 值初始值为3，在计算过程中，若出现5 次迭代结果的标准差变化范围都在5%以内，则令β 值在其定义域内增加1.1 倍。

1.4.3 信息素更新

蚁群的信息素更新包括两部分，1）实时更新，指每只蚂蚁在选择某个节点后对该节点信息素更新；2）路径更新，全部蚂蚁遍历完所有路径后，选择最优蚂蚁的爬行路径，更新该条路径上每个途径节点的信息素。在路径信息素更新中，相比传统蚁群算法，本文引入了两种改进方案：

1）精英筛选策略，通过增加最优蚂蚁的信息素浓度、减少最差蚂蚁的信息素浓度，保障种群的总体优秀程度，提升算法寻优能力。信息素实时更新和路径更新的表示式如式（4）和式（5）所示：

2）自适应信息素挥发因子调整策略。信息素挥发因子ρ 对蚁群的影响主要是以下两个方面：①ρ过大时，再次选择被搜索过的节点概率增大，算法随机性减弱，易陷入局部最优；②ρ 过小时，节点残留信息素浓度较高，算法随机性增强，收敛速度减慢。因此，最佳方案为根据每次迭代结果对ρ 值动态调整。为方便起见，在ρ∈［0.3，1）的定义域内，参考期望启发因子β 的调整策略执行。

2 算法步骤

算法主要通过以下步骤实现，流程如图1 所示。

图1 算法流程Fig.1 Algorithm flowchart

Step 1 根据不可跨越区域范围，离散地图形成解空间；

Step 2 根据解空间途经点，生成所有从起点到终点的可行路径；

Step 3 通过Dijkstra 算法，遍历所有可行路径并得到次优路径；

Step 4 扩展次优路径为次优路径带，通过改进蚁群算法，在该路径带中进一步寻优并得到最优路径；

Step 5 判断连续5 次迭代计算得到的最优路径标准差变化是否大于5%，若是，则调整参数，并返回Step 4；若不是，则进入下一步；

Step 6 判断算法是否满足结束条件，计算结束。

3 算例验证

假设无量纲化后的地图面积为18×18，起点和终点坐标分别O（1，17）和O*（15，3），地图上黑色区域为参考“1.1 威胁区域设置”相关描述设定的不可跨越区。算法中makline 线段等分数为12，蚂蚁种群数为20，采用以上方法和思路计算，经300 步得出的结果如图2 和图3 所示。从航线距离上看，对比Dijkstra 算法得到距离为27.885 0 的次优航线，标准蚁群算法得到的航线距离为23.241 6，而本文算法得出的航线距离更短，为22.727 4。从效果上看，本文算法得到了航线平滑度高，途径航迹点转弯过渡平顺，对飞机而言意味着可以用更少的机动动作、更低的油耗和更短的时间完成突防任务。从质量上看，相比标准蚁群算法，1）寻优能力更强，在算法前期可很快收敛到全局最优解附近；2）收敛速度更快，经过118 步迭代，即得到全局最优解；3）在前期陷入局部最优解后，具有跳出能力，并可进一步寻优；4）计算过程稳定，数值波动范围小、结果未见发散。

图2 最优突防路径Fig.2 Optimal penetration route

图3 标准蚁群算法与本文算法计算过程对比Fig.3 Calculation process comparison of standard ant colony algorithm and the proposed algorithm

4 结论

本文在对航空兵突击作战深入研究的基础上，将飞机突防航线规划问题抽象为在特定解空间中的最佳路径寻优。针对该问题特点，通过对标准蚁群算法的适应性改进和优化，提高了算法效率，形成面向飞机突防问题的通用化解决方案，并可向类似专业领域推广应用。经验证，该方法得到的突防航线对飞机而言，一是突防航程短，同等条件下用时少，减少了暴露风险；二是航线平滑度高，途径航迹点转弯角度平缓，降低了大角度机动转弯带来高油耗，间接增加了飞机任务时间。