蚁群算法在远程鱼雷航路规划中的应用∗

邓新文 邓南明

（中国人民解放军91388部队 湛江 524022）

1 引言

远程鱼雷的设计理念是增加鱼雷的航程，利用鱼雷的机动替代发射平台的机动，从而极大地减少了发射平台被敌方发现的概率，是实现水下“不接触，零伤害”远程打击的重要作战手段［1］。相对于普通鱼雷，远程鱼雷最大的特点为航程远，通常在百公里或者百公里以上［2］。使用时，需要对远程鱼雷进行航路规划，鱼雷出管后首先按照规划的航路航渡至目标区域，然后像普通鱼雷一样按预定的搜索弹道与自导方式进行目标搜索与攻击［3］。航路规划的优劣对于远程鱼雷的战力发挥具有重要影响，而蚁群算法是一种元启发式的随机搜索方法，非常适用于解决组合优化问题，而远程鱼雷的航路规划就是典型的组合优化问题（安全、最短），易于描述但求解困难，本文对如何应用蚁群算法解决远程鱼雷航路规划问题进行研究。

2 远程鱼雷航路规划问题描述与环境建模

2.1 应用条件

文章主要研究远程鱼雷的二维航路规划。远程鱼雷发射后通常是进入一定深度自主航行，所以研究远程鱼雷的二维航路规划具有较大的现实意义［4］。

航路规划的基础是威胁区域已知。远程鱼雷水下航行面临的安全威胁主要考虑岛礁、码头以及敌方固定探测区域的威胁，而这些威胁区域的范围可以通过海图、侦察等手段事先获取［5］，这些威胁区域在鱼雷航行深度上的投影即为威胁区域分布平面，因此可以在已知威胁区域的基础上开展远程鱼雷航路规划研究。

2.2 航路规划问题描述

航路规划的目的是为了在鱼雷起点位置与目标点位置之间，寻找到最优路径［6］。最优路径包含两个方面:一方面要保证鱼雷的航行安全，即避开威胁区域；另一方面要最有利于鱼雷到达目标点后的战力发挥，即预留充足的能源，由于鱼雷航深与航速一定的情况下，路径越短则能耗越小，所以路径越短越有利。最优路径可以认为是保证鱼雷航行安全基础上从起点到目标点的最短路径。

2.3 建立栅格化海图

假设鱼雷的起点位置为S(x0,y0)，目标点为E(xe,ye)，以S(x0,y0)为坐标原点，以正东方向为X轴正向，以正北方向为Y轴正向构建坐标系XOY。假定规划的海域大小为M×N米，将该海域地图按照步长da栅格化，则可以将规划的范围分为(M/da)×(N/da)个栅格，栅格海图中鱼雷从起始点到目标点的航路规划完成了，就说明鱼雷找到了起始点到目的点的航路。假设威胁区域某点坐标为g(x,y)，则其对应的栅格格坐标g(c,r)，其中c为列号与r为行号，g(c,r)可以根据式（1）确定:

栅格的编号可以根据式（2）确定:

在进行栅格划分时，无论是威胁区域栅格还是非威胁区域栅格不满一个时，将其填满，按一个栅格计算，而且为了确保鱼雷的航行安全，威胁区域栅格应该将威胁区域边缘外扩dw（dw为确保鱼雷航行安全，距离威胁区域边缘的最小安全距离）。安全信息由黑白栅格表示。黑色栅格代表威胁区域，即不可行区域，定义黑色栅格集合为tabuk；白色栅格代表可通行区域，定义白色栅格集合为allowedk。栅格地图将不可行区域和可通行区域用一个二进制矩阵表示，矩阵中1代表不可通行栅格，0代表可通行栅格，由此在建立了一个融合威胁区域信息的栅格化海图。

3 蚁群算法航路规划

蚁群算法是通过观察蚂蚁觅食过程，提出的一种基于信息正反馈的进化算法［7］。蚁群算法的基本思想是，蚂蚁寻找食物时，会在走过的路上释放信息素，信息素会随着时间推移而逐渐挥发，一定时间内其他蚂蚁会觉察到信息素的存在，因而相同食物位置的情况下，一群蚂蚁自由觅食，某只蚂蚁走的路径越短，则该路径信息素越浓，更浓的信息素会吸引更多的蚂蚁前来按照该路径行进，某一路径上通过蚂蚁数量就会越多，则该路径信息素会越浓，最终所有的蚂蚁都会选择信息素浓度最大的路径，该路径也是最短路径［8］。另外，蚂蚁选择信息素浓度较高的路径时，可能会发生新路线的探索行为，如果探索过程中发现了更短的路径，那么更多的蚂蚁就会被吸引过去，这样就避免了局部最优解，达到寻找到蚁穴与食物之间最短路径的目的［9］。

影响蚁群算法性能的主要是启发式信息及信息素浓度［10］，t时刻当鱼雷处于某个栅格i时，此时鱼雷可行栅格的集合为allowedk(ct,rt)。鱼雷下一步到达的栅格为j，其坐标为 (cj,rj)，其中(cj,rj)∈allowedk(ct,rt)。目标点E(xe,ye)对应的栅格坐标为E(ce,re)，则所有可行栅格的全局启发式信息为ηij(t)，ηij(t)的计算公式如式（3）所示。

式中，Ik为可通行栅格集合。α为信息素强度影响因子，其值越大代表信息素强度的影响越大［11］。β为启发函数因子，其值越大代表启发式信息的影响越大。τij(t)为t时刻栅格i与j连接路径上的信息素浓度。在蚂蚁行走的过程中，蚂蚁释放信息素的同时，信息素也在挥发，为了描述信息素的挥发情况，我们定义挥发因子 ρ(0＜ρ＜1)来表示信息素挥发程度，则蚂蚁遍历所有地点后，各地点相连路径的信息素浓度可表示为

式中，Δτij为所有蚂蚁在栅格i与栅格j连接路径上释放信息素所增加的浓度。

4 远程鱼雷航路规划的流程

步骤1:建立栅格化海图。在海图上标注出威胁区域，并将威胁区域边缘外扩dw，按照2.3的方法建立栅格化海图。

步骤2:参数设置。涉及的参数主要有蚂蚁数量m，信息素强度影响因子α，启发函数因子β，信息素挥发因子ρ，以及信息素强度Q，最大迭代次数等。

步骤3:状态初始化。当前节点初始化为起始点，航行路径长度初始化为0，禁忌表初始化为M×N全1矩阵并排除起始点（即起始点对应矩阵位置设为0），邻接矩阵初始化。

步骤4:计算可以前往的节点。随机将蚂蚁放置于不同的地点，对蚂蚁计算其下一个访问地点，直至所有蚂蚁访问完所有可通行地点。

步骤5:计算各个蚂蚁行走的路径长度，记录当前迭代结果中路径的最优解（即最小值），同时对路径上信息素浓度进行更新［12］。

步骤6:是否达到最大迭代次数，若没有则重复执行步骤2。

步骤7:得到最优路径结果。

5 计算机仿真

假设鱼雷需要航渡的海域融合威胁区域信息后的栅格化海图如图1所示。其中步长为Lm。

图1 航渡区域栅格化海图

图2 一次规划最优路径

为验证蚁群算法在进行远程鱼雷航路规划问题中的性能，笔者采用Matlab，进行了模拟仿真试验。试验中根据蚁群算法路径规划的经验，设置初始化参数如下:蚂蚁数量m=80，信息素强度影响因子α=1，启发函数因子 β=7，信息素挥发因子ρ=0.3，以及信息素强度Q=10，最大迭代次数为500次。得到最优航路如图2所示，收敛曲线如图3所示，最短路径长度为43.4*Lm，收敛次数为196次。

图3 一次规划收敛曲线

图4 二次规划最优路径

图5 二次规划收敛曲线

该航路规划方法不仅能用于发射前的一次航路规划，当目标点移动时，若远程鱼雷还能接收遥控规划，还能实现动态规划。假定鱼雷航行至栅格（10，8）时，战场情况有变，需更改目标点，新的目标点栅格坐标为（30，1），则可以进行二次规划，二次规划结果最优航路为图4所示，收敛曲线如图5所示，最短路径长度为22.9*L m，收敛次数为35次。

6 结语

航路规划对于远程鱼雷非常重要，是影响鱼雷能力发挥的一个重要环节。笔者针对远程鱼雷航路规划问题，基于安全基础上最短路径长度的原则，采用蚁群算法进行了求解计算。通过仿真结果可见，蚁群算法能有效解决远程鱼雷航路规划问题。该航迹规划方法不仅可以用于远程鱼雷的航路规划，还可以应用于UUV以及无人机等装备的二维最优路径规划。在远程鱼雷的试验过程中，进行航路规划时应该考虑以该方法规划的航路作为试验航路，以贴近实际使用的方式来进行航路规划功能以及导航精度等指标的考核验证。