变异扩散蚁群算法求解战区潜艇三维路径规划问题

包贤哲 丁稳房

(湖北工业大学电气与电子工程学院 湖北 武汉 430068)

0 引 言

潜艇作为海上军事力量的重要组成部分之一，已经成为各个国家争相研究的重要武器装备。随着潜艇在海上对抗中的作用日渐显著，出现了众多针对潜艇的反潜武器，例如水雷和声呐探测系统等。此时潜艇执行任务时的路径规划显得十分重要，正确且快速找到潜艇的最优前行路径打击敌方舰船目标对海上战场局势起着决定性作用，具有非常重要的研究意义。

近年来，很多学者尝试用各种优化算法解决路径规划问题且取得了不错的效果，如陈光荣等[1]通过交替使用两种凸优化算法并结合经典A*算法求解最小路径并通过仿真实验验证了算法的有效性。改进的A*算法[2-3]在路径规划问题上有较好的效果。Sun等[4]结合无线传感器网络调度技术提出了一种基于模糊神经网络的最优航路规划模型，该方法路径规划的可靠性高、收敛性较好。Lo等[5]将油耗作为优化函数，并提出了一种油耗估算方法，通过燃油燃烧量最终搜寻出最省油的路线，该方式能够很好地节省企业成本。王培良等[6]以栅格化地图为研究背景，提出了蚁群元胞优化算法，该算法可以有效提高搜索能力并避免陷入局部最优解，但模型中并未考虑障碍物的形状以及机器人的体积大小。Zeng等[7]采用步长优先级的启发信息，并加入不同的信息更新方式来优化蚁群算法。占伟等[8]针对蚁群算法的启发因子和信息素更新策略进行优化，提出一种改进的蚁群算法解决机器人路径规划问题，但其设置的机器人移动场景较为简单，实际应用性不强。Viseras等[9]则通过在RRT/RRT*算法中引入蚁群优化概念并定义一种新颖的效用函数来权衡搜索空间。Sahu等[10]使用自适应蚁群算法修改了蚁群算法的基本参数以增强其控制能力。Yang等[11]则使用同时运行搜索的高效双层蚁群算法能够得到较为平滑的曲线，但参数设置和算法过于复杂。Wang等[12]结合禁忌表和网络权重表来加快算法收敛。改进的蚁群算法[13-16]对于路径搜索问题有着良好的适应性。Gao等[17]发现路径规划中定位精度的限制，导致了机器人运行的高风险性，为解决此问题，提出了一种新的路径评估方法，首先分析不确定性再通过融合两者的不确定性来估计可定位性，最终建立了用于路径规划的新路径评估功能，该方法可有效提升路径规划的安全性和精度。Ueno等[18]为了解决动态路径规划中路径切换中的避障问题，引入虚拟障碍物分配法抑制其带来的影响并采用鲁棒路径规划算法求解路径，有效避免切换路径后的障碍物碰撞问题。除此之外，遗传算法[19-22]、人工势场法[23-25]和鲸鱼算法[26-28]在路径规划问题上也有应用。

虽然上述算法在解决路径规划问题上有着不错的效果，但都存在着一些如参数设置复杂、收敛效果不佳、未考虑移动物体的体积、障碍物体积形状等缺点。针对这些问题，提出一种变异扩散蚁群算法(Mutation Diffusion Ant Colony Algorithm,MDACO)，该算法运用极值限制策略限制信息素浓度防止算法过早停滞，运用变异策略增加例子多样性扩大搜索范围提高算法精度，再采用信息素扩散策略加大距离较近蚂蚁之间的沟通协作，加快算法收敛。最后通过四个三维空间内的战区潜艇路径规划问题对变异扩散蚁群算法、传统蚁群算法、遗传算法和粒子群算法进行求解，结果证明该算法拥有良好的性能，且对三维路径规划问题有着良好的适应性。

1 问题分析与模型建立

设定一个海域Q∈[m×n×p]的三维空间中，有一艘潜艇P要从海域内某一点前往另外一点实施打击任务，在该海域内存在敌方布置的各式水雷阻碍潜艇行进，且在海域近海底部分存在暗礁岩石等障碍物，潜艇需要在避开这些障碍物且不被敌方发现的情况下尽可能快速地到达指定位置完成打击任务。

将处于海域不同位置和深度的水雷简化为不同大小的球形障碍物，在海域内，其函数表达为：

(x-x0)2+(y-y0)2+(z-z0)2=R

(x0,y0,z0)∈Q

(1)

式中：点(x0,y0,z0)为水雷的中心位置坐标，水雷在水域中是随机分布的。

除此之外，近海底区域还存在着暗礁以及海底岩石等障碍物，将这些障碍物简化为一个个单峰函数来表示，其表达式为：

(2)

式中：Zi(x,y)表示在(x,y)点上障碍物的高度；(xi,yi)则表示海底暗礁等障碍物的中心坐标位置；k为常参数；xsi表示障碍物在x方向上的陡度；ysi表示障碍物在y方向上的陡度。

根据题意，潜艇在前行的过程中不能与障碍物发生碰撞即：

(3)

式中：P(x,y)表示潜艇的中心位置坐标；Zo(xc,yc)表示不同深度和位置的水雷中心坐标；Dk表示海底障碍物投影在还地面的区域集合；Qk则表示水雷投影在海底面的区域集合。式(3)表示潜艇前行时中心位置的高度必须高于海底障碍物在该点的高度，而对于水雷来说，潜艇可以以低于水雷位置的高度穿过，也可从位置较深的水雷上方通过。

但在实际情况中，潜艇有固定形状和体积，若按照式(3)的约束条件潜艇与水雷或暗礁等仍然会发生碰撞，将潜艇简化为一个长为a、宽为b、高为c的长方体，其在海域航行时的断面图如图1所示。

图1 潜艇海域航行断面图

图1中矩形代表潜艇，底部起伏曲线代表海底岩石和暗礁，圆形则是处于海上不同位置和深度的水雷。依据式(3)若不考虑体积问题，潜艇中心位置大于障碍物高度或潜艇中心位置不属于水雷所在区域内时，在该点依然发生了碰撞如虚线矩形所示，所以若想要满足潜艇在任何时刻的位置都不与障碍物碰撞，要使潜艇上任意一点都不在障碍物表面或障碍物体内。考虑到暗礁岩石等物体的表面坡度并不是固定不变的，无法对每一个障碍物都进行细致建模。因此，以潜艇所在最小长方体的体对角线的一半为半径作一个外包裹球体，将其放入这个球体内，使得球体上的任意一点都不在障碍物表面或体内即可满足潜艇在任意时刻不与障碍物发生碰撞的要求，具体情况如图2所示。

图2 潜艇防撞模型示意图

图2中的长方体代表潜艇，外侧的球体半径R为潜艇体对角线的一半即OF1，其球体半径表达式为：

(4)

以潜艇的中心位置为坐标原点，将整个球体的极坐标形式引入为：

(5)

根据式(5)即可得到最终的约束条件为：

(6)

式中：C(x,y)表示以潜艇体对角线为半径的球体表面点的纵坐标。若潜艇前行满足式(6)，则在任何情况下都不会与水雷或暗礁发生碰撞。

一般评价路径优劣的评价指标包括路径长短、路径平滑度、高度等，为了能够找到最合适的行进路线，将综合考虑所有因素用以区别线路的优劣。潜艇在海域中潜行时到达的前后两点间的距离为：

(7)

根据式(7)可以得到潜艇前行的路径全长为：

(8)

潜艇航行时路径的平滑程度取决于潜艇每次前进改变的角度大小，改变角度越大越频繁则路径越曲折，反之路径越平滑，潜艇在海域三维空间前后两次转过的角度如图3所示。

图3 空间潜艇转角示意图

图3中θ表示蚂蚁经过的三点A、B、C组成的AB空间向量与BC空间向量之间的夹角。根据图3可得潜艇在海域前行的路径总的平滑程度为：

(9)

式中：Ai表示潜艇经过的第i个点与第i+1个点组成的空间向量；Bi+1表示第i+1个点与第i+2个点组成的空间向量；潜艇在一条完整路径中共经过M个点。

为了能够尽量躲避海面敌方目标的侦察和声呐探测，在保证线路安全的前提下尽可能使得潜水的深度更深，总路径的平均深度为：

(10)

式中：Zi表示潜艇在第i个点的纵坐标。

将变量进行归一化处理，并根据重要性为三个指标分配不同的权重，由式(8)-式(10)可得到最终的目标函数为：

(11)

式中：Lmax=m+n+p即潜艇沿着长方体作战区域的长、宽、高边界三条直线潜行到达目的地的最长路径；Hmax=π表示转角的最大值；Umax=p则表示最大深度；α1、α2、α3三个权重的数值则根据目标函数的重要性确定，α1+α2+α3=1。

2 算法设计

2.1 传统蚁群算法

蚁群系统(Ant System或Ant Colony System)是由意大利学者Dorigo等[29]于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。蚂蚁能根据前行道路上的信息素浓度不断向离食物最近的道路靠拢直到找到食物。

蚂蚁如何移动取决于线路上的信息素浓度水准，信息素浓度越高，蚂蚁选择该路径的概率越大，反之越小。蚂蚁k在时刻t从区域i向区域j前进的概率为：

(12)

式中：σij(t)表示时刻t线路ij上的信息素浓度；μ为信息素启发因子，代表了信息素浓度对选择概率的影响程度；γij(t)表示启发信息；λ为期望启发因子表示启发因子对概率选择的影响程度；G则表示蚂蚁k能够选择的剩余的区域地点组成的集合。启发因子的表达式为：

(13)

式中：Lij表示区域i与区域j之间的距离。在所有蚂蚁完成路径地区的遍历之后，将会更新每条道路上的信息素浓度，其信息素浓度更新公式为：

σij(t+1)=(1-δ)σij(t)+Δσij

(14)

式中：δ为信息素浓度挥发系数。线路在没有蚂蚁经过时信息素浓度会挥发逐渐下降，蚂蚁经过该路段带来的信息素浓度变化为：

(15)

2.2 变异扩散蚁群算法

2.2.1极值限制策略

蚁群算法前进的过程主要依赖于信息素浓度，但在迭代过程中很容易造成某些路段蚂蚁经过次数太多导致信息素浓度过高，而某些路段蚂蚁基本不经过信息素挥发后浓度太低，这样会导致算法在早期陷入停滞。因此，对蚂蚁信息素浓度的最大值和最小值分别做出以下限定：

(16)

式中：ω为常数；Lbest表示当前全局最优路径长度，即当前蚂蚁搜寻到的最短路径。

(17)

式中：t为迭代次数；Dbest表示最优个体占全部个体的比例即个体收敛率。通过此方式能够很好地限制信息素浓度的过分升高或降低，保证算法前期不陷入停滞。

2.2.2变异策略

蚁群算法存在着收敛速度较慢的问题，这与算法的搜索方式有关，为了克服该缺点，采取变异策略改良蚁群算法，假设第k只蚂蚁所走过的路径为：

(18)

首先确定变异区域，设定变异起止点分别为i,j∈[1，n]，将变异区域即[Li(i+1)，L(j-1)j]内的路径顺序打乱重组q次。若每次新的路径顺序满足式(19)，则用新的路径顺序代替原有的路径顺序，否则仍然采用原有的路径顺序。

L(i-1)i+Lm(m+1)+…+Lj(j-1)

Li(i+1)+…+Lj(j-1)

(19)

2.2.3交叉策略

假设存在另外一只当前全局最优蚂蚁m，其所经过的路径为：

(20)

为了能够让优质个体对其他蚂蚁起引导作用，采用交叉策略对其某部分路径进行交换。设定交叉起止点i，j∈[1,n]，当i=2、j=5时其交叉示意图如图4所示。

图4 路径交叉示意图

(21)

2.2.4扩散策略

蚁群个体是不具备任何关联性的独立个体，这样单独搜索的方式容易让某些个体偏离最优路径且迭代收敛速度较慢，为克服此问题引入信息素扩散策略。

任何挥发性的物质都会在空间中发生扩散现象，且其扩散浓度与其距扩散源的距离服从正态分布，将二维平面的扩散模型简化后扩展到三维空间如图5所示。

图5 信息素扩散三维空间模型

图5所示扩散源为O点，R表示信息素扩散最大半径，随着离扩散源距离的增大，信息素浓度不断降低。β和h为常数，其关系为：

htanβ=R

(22)

假设某蚂蚁经过路段ij，但并不经过在其扩散最大半径内的路径im，在其扩散范围内路径im接收到的由路径ij扩散的信息素浓度为：

(23)

式中：Lim表示路段im的长度；θ为一常数；Lk为第k只蚂蚁的路径全长。由此路径im上的信息素浓度变为：

(24)

任意路径上的信息浓度都是由该路径上原本的信息素浓度与周围有蚂蚁走过的路径扩散至此的信息素浓度组合而成，通过扩散策略可以加强不同蚂蚁之间的协作交流，让优质个体引导其他个体的搜索方向，加快算法收敛。改进算法流程如图6所示。

图6 改进算法流程

如图6所示，初始化参数后确定起点和终点让蚂蚁迭代寻找路径，完成路径寻优过程后得到所有蚂蚁路径信息以及全局最优蚂蚁路径信息。此时采用变异策略和交叉策略优化路径，再根据信息素限制策略和信息素扩散策略计算此次迭代后各个地点的信息素浓度，根据新的信息素浓度更新选择概率矩阵，在此基础上再进行第二次路径寻优。直到达到最大迭代次数时算法终止，输出最优路径信息。

3 实验与结果分析

假设存在四个不同的战区海域P∈[10×10×1] km3(海域深度1 km),需要派遣潜艇从某区域出发前往指定区域实施打击任务，在该海域内存在敌方部队埋下的各式水雷以及突起的暗礁和其他障碍物，潜艇需要在保证自身不被发现的前提下以最快速度安全到达指定位置完成任务。相关任务参数设置见表1。

表1 各项参数表

根据上述参数设定，设立种群最大迭代次数tmax=100，种群个体数量N=200，潜艇的长a=90 m,宽b=8 m,高c=5 m，目标函数中权重取α1=0.5、2=0.4、α3=0.1。将数据代入变异扩散蚁群算法、传统蚁群算法、遗传算法、粒子群算法四种算法中计算得到的最终路径结果如图7所示，最终数据如表2、表3所示。

(a) 海域1潜艇轨迹图

(b) 海域2潜艇轨迹图

(c) 海域3潜艇轨迹图

(d) 海域4潜艇轨迹图

表2 三种基础算法结果对比表

表3 传统蚁群算法与变异扩散蚁群算法结果对比表情形编号

表2和表3中Min代表算法搜索到的最优结果，Time表示算法迭代时间，Rate则表示收敛到最优结果的粒子个体占总个体的比例即粒子收敛率。根据图7以及表2的数据可以看出，在三种基础算法中ACO能够搜寻到更短更平滑、更安全的路径，且迭代时间更短，粒子收敛率更高，综合三个指标其整体性能更加优秀，对路径优化问题的适应性也较好，所以理论上对ACO改进能够得到更好的改进效果。由表3可知，改进后的MDACO相比于传统ACO性能更加优秀，在四个算例下得到的结果更好，迭代速度和收敛率也有明显提升，实验证明了该算法改进的有效性，改进算法对三维空间路径优化问题有着良好的适应性。四个算例中的算例1的迭代过程如图8所示。

图8 1号海域算例算法迭代图

可以看出，MDACO在30次左右就已经收敛，其迭代收敛速度相对于其他三种算法更快，在作战中能够更快速地为潜艇在复杂环境中提供最优路径，满足战时对潜艇实施打击任务快速响应的要求。

4 结 语

针对战区潜艇三维路径规划问题，提出一种变异扩散蚁群算法。该算法首先通过极值限定策略限制信息素的增长和挥发以防止算法由于路径信息素差别过大陷入停滞。而后采用变异交叉策略将蚂蚁个体的路径顺序打乱重组，对不同蚂蚁个体的路径顺序进行交叉产生新的变异个体，从而增加粒子多样性加速算法收敛。再采用信息素扩散策略加强距离较近蚂蚁之间的交流合作，增强优质蚂蚁对其他蚂蚁的引导作用以提升算法搜索速度和精度。最后采用四个不同海域的作战算例对该算法进行了检验，结果表明改进算法相对于传统算法有着更好的性能，对三维路径避障优化问题有着良好的适应性。下一步将研究将该算法与其他算法结合，进一步提升算法的性能并运用到实际作战系统和场景中。