《测绘学报》

构建与学术的桥梁 拉近与权威的距离

复制链接，关注《测绘学报》抖音！

【测绘学报的个人主页】长按复制此条消息，长按复制打开抖音查看TA的更多作品##7NsBSynuc88##[抖音口令]

蚁群-势场算法在水下重力辅助导航航迹规划中的应用

张驰1, 李姗姗1, 史颜俊2,邢志斌1,范雕1

1.信息工程大学, 河南 郑州 450001;2.92337部队, 辽宁 大连 116023

摘要：水下潜器航迹处于重力特征变化明显的适配区域才能保证重力辅助导航的有效实施，因此在重力匹配导航阶段，潜器的航迹规划至关重要。本文首先依据重力统计特征参数对水下潜器航行区域进行适配性划分，并给出适配、非适配区标签，然后在蚁群算法进行航迹规划的基础上引入人工势场算法，重新构建启发函数，避免了蚁群算法的局部最优问题；同时利用最大-最小蚁群系统改进算法信息素更新规则，防止了“早熟”现象发生。仿真试验结果表明，本文提出的蚁群-势场算法可以有效解决水下潜器在重力辅助导航中的航迹优化问题，提高了问题解的可行性。

关键词：航迹规划 蚁群算法 人工势场法 重力辅助导航

引文格式：张驰, 李姗姗, 史颜俊, 等. 蚁群-势场算法在水下重力辅助导航航迹规划中的应用. 测绘学报，2020，49(7)：865-873. DOI: 10.11947/j.AGCS.2020.20190194.

基金项目：国家自然科学基金（41777021；41574020）；信息工程大学校立课题（2017503902）

阅读全文：

全文概述

现阶段水下潜器(underwater vehicle，UV)的主要导航方式为惯性导航[1]，它具有能够连续工作、提供比较完备的导航参数以及短时噪声低等优点。惯性导航误差具有随时间积累，解算精度随时间下降的缺点[2]，因此长期航行时UV必须通过其他导航方式进行辅助校正[3]。然而依靠卫星、天文等外部有源信息来校正惯性导航误差，会损失UV的隐蔽性[4]，而重力匹配辅助惯性导航系统是利用重力场这一地球固有场信息，可以对惯性导航系统长航时条件下的误差漂移进行抑制和修正[5]，以满足UV“自主性、高精度、隐蔽性”的要求[6]。

在重力辅助导航过程中，UV会经过重力变化明显的适配区域，也会经过变化平缓的非适配区域。因此，让UV航迹一直处于重力适配区而避开非适配区是保证重力辅助导航有效实施的关键之一。水下重力辅助导航最优航迹规划问题可以转换为将重力盲区作为障碍的全局路径规划问题。目前，国内外学者在路径规划方面己经作了大量的研究工作，其中包括Dijkstra算法[7]、A*算法和人工势场法[8]等传统算法，以及遗传算法[9]、人工神经网络[10]、粒子群算法[11]等智能优化算法[12]，每种算法在不同的性能指标下都有自身的优点。

为进一步优选重力匹配航迹，本文综合利用主成分分析法[13]、蚁群算法和人工势场法进行重力辅助导航航迹规划。

1 蚁群算法

蚁群算法(ant colony optimization, ACO)是一种在图中寻找优化路径的几率型算法[14]。该算法受蚂蚁觅食过程中的路径行为启发，蚂蚁在路径中会分泌一定浓度且具有挥发性的信息素。同时，蚂蚁在觅食过程中会倾向于选择信息素浓度大的路径。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复。

首先依据主成分分析法(principal component analysis，PCA)对重力场特征参数进行统计并给出重力适配区评价结果[15]，利用栅格法将待匹配区域重力异常图离散化为二维栅格图，每个栅格的状态定义为“free”或“occupied”，其中适配区标定为“free”，非适配区标定为“occupied”，即为障碍物，如图 1所示。

图 1 重力异常图离散化二维栅格图

Fig. 1 Discrete two-dimensional raster map of gravity anomaly

图选项

UV会占据重力图中的一个栅格，其相邻的8个栅格为UV下一时刻可选的位置。利用蚁群算法的避让规则、移动规则和信息更新规则[16]搜索出最优航迹。具体搜索过程如图 2所示。

图 2 栅格搜索过程

Fig. 2 Raster search process

图选项

若蚂蚁数量为M，蚂蚁k(k=1, 2, …,M)在t时刻从位置i移动到j的概率表示为

(1)

式中，α为信息素浓度启发因子；β为期望启发因子；ηij为启发函数，是位置i与位置j之间距离dij的倒数

(2)

蚂蚁会在经过的航迹上留下信息素，信息素随时间的改变具有挥发性，信息素的更新规则如下

(3)

(4)

式中，ρ为信息素挥发系数，ρ∈(0, 1)；Δτijk为蚂蚁在t到t+n位置栅格之间的信息素。

依据ant-cycle模型

(5)

式中，Q为信息素强度；Lk为蚂蚁k在本次循环中的航迹长度；Pk(begin, end)为蚂蚁k在本次循环中从起点栅格到终点栅格所走的航迹[17]。

蚁群算法在初始阶段各航迹信息素是相同的，差异主要表现在启发信息上。由于启发函数特性，蚁群首条航迹规划会偏向于距目标点近的航迹，此时蚁群算法相似于贪婪算法，在特殊环境中未必反映最优航迹，由于蚁群算法的正反馈性，导致蚁群向错误的方向规划。为解决这一问题，本文在蚁群算法进行航迹规划的基础上引入人工势场法，将人工势场法求得的航迹和UV与下一个节点之间的距离信息综合改进启发信息，利用新的转移概率确定下一个栅格的选择。同时利用最优-最差蚂蚁系统，找出最优航迹解和最差航迹解，分别进行全局信息素更新，对最优航迹进行增强，对最差航迹进行削弱。

2 改进的蚁群-势场算法

2.1 人工势场法

人工势场法[18]通过模拟构建一个抽象的人造势场来进行航迹规划。人工势场由引力场和斥力场构成[19]，引力场是由目标点位置产生并作用于UV，势场矢量方向由UV指向目标点，势能与到目标点的距离成反比；斥力场由障碍物产生，势场矢量方向由障碍物指向UV，势能与到障碍物的距离成反比[20]。引力场和斥力场对UV共同作用，搜索出一条不接触障碍的最优航迹。

作用于UV的势场函数和合力函数为

(6)

(7)

式中，U为总势场；Ur为斥力场；Ua为引力场；F为合力；Fr为斥力；Fa为引力。

定义引力为引力场的负梯度，则引力势场函数及引力为

(8)

(9)

式中，k为大于0的引力常量；Xg为目标点位置。

定义斥力为斥力场的负梯度，定义斥力势场函数和斥力为

(10)

(11)

式中，m为大于0的斥力常量；ρ0为障碍物的影响范围；XO为障碍物位置。

2.2 蚁群-势场算法

2.2.1 改进的启发信息函数

与ACO相比，改进的蚁群-势场算法中的启发信息加入了由人工势场法影响的势场启发信息，ACO的启发信息和人工势场法的启发信息分别表示如下[21]

(12)

(13)

当前栅格位置为P，目标栅格位置为Q，d(P,G)为当前栅格与目标栅格之间的距离，a为大于0常数，F为人工势场的合力，θ为势场合力方向与下一栅格位置方向的夹角[22]。

在航迹规划前期，蚁群信息素浓度较低，启发信息较小，需加大人工势场法所控制的启发信息；航迹规划后期，信息素浓度的提升，需降低人工势场法所控制的启发信息[23]。因此，引入一个信息递减因子χ来控制人工势场法启发信息[24]

(14)

式中，Nmax为最大的迭代次数；NC为当前时刻的迭代次数。

因此蚁群-势场算法的启发函数为

(15)

从而得到改进的转移概率公式为

(16)

由于人工势场法模型简单，实时性强，将其求得的航迹引入蚁群算法的启发函数中，可有效避免蚁群算法由于启发信息所导致的局部最优问题，同时提高蚁群算法的搜索效率。

2.2.2 改进的信息素浓度更新规则

在ACO中，当所有蚂蚁完成一次迭代后，会根据式(3)进行全局信息素更新。由于任何一次迭代中蚂蚁所产生的航迹都会对蚁群以后航迹规划产生影响，非最优航迹蚂蚁会对以后的蚂蚁造成误导。因此，本文引入最优-最差蚂蚁系统[25]，在完成一次迭代后，找出最优航迹和最差航迹，分别进行全局信息素更新。对最优航迹进行增强，对最差航迹进行削弱[26]。最优-最差蚂蚁系统使得蚂蚁搜索更集中与当前最优航迹的范围内，并向着全局最优的方向不断发展[27]。

在一次迭代结束后，选出最优蚂蚁航迹和最差蚂蚁航迹，对最优蚂蚁按式(3)进行信息素更新，对于最差蚂蚁按式(17)进行信息素更新

(17)

式中，ε为最优-最差蚂蚁系统参数；Lw为最差蚂蚁航迹；Lb为最优蚂蚁航迹。

2.2.3 蚁群-势场算法具体步骤

改进的蚁群-势场算法具体流程如图 3所示。

图 3 蚁群-势场算法流程

Fig. 3 Ant colony-potential field algorithm

图选项

步骤1：初始化参数。选择起点栅格、目标栅格、迭代计数器NC=0，设置最大迭代次数Nmax，对蚂蚁数量M、信息素启发因子α、期望启发式因子β、引力常量k、斥力常量m等参数初始化。

步骤2：蚂蚁航迹选择。将M只蚂蚁放到起点栅格，并将起点栅格加入禁忌表中。采用人工势场法计算启发信息，得到新的概率信息，从而确定下一个可行栅格，并将下一个可行栅格加入禁忌表中，如此循环直到蚂蚁到达目标栅格。

步骤3：信息素全局更新。所有蚂蚁完成一次迭代后，找出本次迭代中的最优蚂蚁和最差蚂蚁，对最优蚂蚁搜索的航迹按照式(12)进行信息素更新；对最差蚂蚁搜索的航迹按照式(26)进行更新。

步骤4：结束搜索。判断迭代是否到达最大迭代次数，若达到最大迭代次数，则输出最优航迹长度；否则，清空禁忌表，令NC=NC+1，从步骤2开始重新循环搜索，直到满足循环次数NC=Nmax，输出最优航迹长度，算法结束。

3 仿真试验及结果分析

3.1 主要参数设置

本文将蚁群-势场算法应用于重力辅助导航航迹规划问题中，通过多次仿真试验对比蚁群-势场算法和传统ACO，验证本文蚁群-势场算法的优越性。算法运行环境为：Windows 10 64 bit；Matlab R2014a。

由于到目前为止还没有确切的研究给出蚁群算法模型的最优参数设置，一般通过试验来选择参数。本文在参数变化范围内设置不同的参数组合，通过统计试验结果的优劣，选取最优参数组合。各个参数给出的范围如下：α∈0, 0.5, 1, 5，β∈0, 1, 3, 5, 8, 10，ε∈0, 0.5, 0.8, 1。

经过控制变量解算得出算法的主要参数为：α的最优值在1左右，β的最优值在5~10，ε的最优值在0.5左右。

3.2 人工设定10×10栅格航迹规划

为对比蚁群-势场算法和传统ACO在航迹规划中的优劣程度，本文人工设定一个10×10的栅格，如图 4所示。蚁群-势场算法和传统ACO分别在此人工设定10×10栅格图上进行航迹规划。经过大量试验对算法参数进行调试，本次试验参数设定为最大迭代次数Nmax=100，蚂蚁个数M=50，α=1，β=8，ρ=0.1，ρ0=2，ε=0.5，引力常量k=2，斥力场量m=1，航迹规划结果如图 5所示。

图 4 人工设定10×10的栅格

Fig. 4 Manually setting 10×10 grid

图选项

图 5 人工设定10×10栅格航迹规划结果

Fig. 5 Manually set 10×10 grid track planning results

图选项

如图 4、图 5所示，在栅格图内，白色栅格为自由栅格，黑色栅格为障碍栅格，左下方红色栅格为起点栅格，右下方绿色栅格点为目标栅格，带线圈的黑色折线为算法规划的航迹。

由图 5(a)、5(b)对比可以看出，传统ACO所得航迹并非最优航迹，而是收敛到一条较长航迹上；蚁群-势场算法则收敛到了最短航迹上。这是因为受传统ACO启发信息的影响，在第1次航迹规划迭代时蚂蚁会更趋向于选择离目标栅格较近的栅格，结合正反馈作用，之后迭代的蚂蚁也更趋向于选择这条航迹，并最终收敛于此航迹上；而蚁群-势场算法考虑人工势场法规划的航迹，并且将下一个栅格的位置信息考虑进来，对启发函数进行了重构，新的启发函数避免了传统ACO中这种情况的发生。因此，蚁群-势场算法则是收敛到了最短航迹上。

3.3 重力实测区域航迹规划

为验证蚁群-势场算法在重力实测区域航迹规划的可行性，本文分别选取来自南海的两个试验区域。区域卫星测高重力异常数据来源于DTU10模型，格网分辨率为1′×1′，两个试验区域的重力异常分布如图 6所示。

图 6 试验区域重力异常分布图

Fig. 6 Distribution of gravity anomaly in the experimental area

图选项

首先，利用PCA对试验区域重力异常数据进行基于多特征值的重力辅助导航适配性分析。选取重力场标准差、粗糙度、相关系数、信息熵和坡度作为航迹规划衡量适配区的重力特征统计参数。求解重力统计参数贡献率和累计贡献率，当累计贡献率大于等于0.85后确定主成分个数，见表 1。根据表中的累计贡献率可以确定主成分个数k=3。通过计算区域可导航能力，导航能力大于0的区域被标记为适配区，小于0的区域被标记为非适配区，获得区域适配/非适配区标签。得到如图 7所示的二维栅格图，每个栅格包含20′×20′的重力异常数据。适配区在栅格图中标为白色，表示为自由区域；非适配区在栅格图中标为黑色，表示为障碍区域。

图 7 试验区域二维栅格图

Fig. 7 2D raster image of the experimental area

图选项

表 1 重力统计参数贡献率和累计贡献率

Tab. 1 Gravity statistical parameter contribution rate and cumulative contribution rate

序号区域1

区域2贡献率累计贡献率

贡献率累计贡献率10.408 80.408 8

0.461 80.461 820.333 30.742 1

0.284 90.746 730.179 50.921 6

0.172 20.918 940.078 00.999 6

0.080 70.999 650.000 41.000 0

0.000 41.000 0

表选项

从图 7可以看出，区域1的非适配区栅格分布比较集中，最终形成的障碍个数较少，形状比较规整，分布比较简单；区域2的非适配区栅格分布比较零散，且最终形成的障碍多为L形和正方形，分布较为复杂，航迹规划难度较大。所以本试验依据这两片海域的重力常数据设置了两种不同栅格环境，对蚁群-势场算法和传统ACO进行对比。

本次试验参数设定为最大迭代次数Nmax=100，蚂蚁个数M=50，α=1，β=8，ρ=0.1，ρ0=2，ε=0.5，引力常量k=2，斥力场量m=1，左上角红色栅格为起点栅格，右下角绿色栅格为目标栅格，带线圈的黑色折线为算法规划的航迹。简单环境下的航迹规划结果如图 8、图 9所示，复杂环境下的航迹规划结果如图 10、图 11所示。

图 8 试验区域1(简单环境)传统ACO航迹规划结果

Fig. 8 Experimental area 1 (simple environment) traditional ACO track planning results

图选项

图 9 试验区域1(简单环境)蚁群-势场算法航迹规划结果

Fig. 9 Experimental area 1 (simple environment) ant colony-potential field algorithm track planning results

图选项

图 10 试验区域1(复杂环境)传统ACO航迹规划结果

Fig. 10 Experimental area 1 (complex environment) traditional ACO track planning results

图选项

图 11 试验区域1(复杂环境)蚁群-势场算法航迹规划结果

Fig. 11 Experimental area 1 (complex environment) ant colony-potential field algorithm track planning results

图选项

由图 8与图 9对比可得，在简单环境中，通过10次试验后，蚁群-势场算法平均迭代次数为9.8次，最优航迹平均长度为16.485 3，平均用时为4.26 s；传统ACO平均迭代次数为46.7次，最优航迹平均长度为21.313 7，平均用时为9.87 s。

由图 10与图 11对比可得，在复杂环境中，通过10次试验后，蚁群-势场算法平均迭代次数为4.5次，最优航迹平均长度为14.485 3，平均用时为5.90 s；传统ACO平均迭代次数为28.6次，最优航迹平均长度为18.879 5，平均用时为10.33 s。

由以上对比分析可知，在简单环境和复杂环境两种栅格环境中，蚁群-势场算法的航迹均比传统ACO的航迹更为平滑，而且长度更短；利用蚁群-势场算法在UV重力辅助导航中进行航迹规划，航迹更优，收敛速度更快。

4 结 论

本文在全局静态环境下，利用栅格法对UV所经过海域的重力异常数据进行建模，针对ACO在水下重力辅助导航航迹规划中的不足，提出了一种改进的蚁群-势场算法。

蚁群-势场算法对信息素浓度更新规则进行了改进，引入了最优-最差蚂蚁系统，在有效缩小搜索最优航迹范围的同时，防止“早熟”现象的发生；利用人工势场法，依据初始路径，考虑UV当前栅格节点与下一个栅格节点之间的距离信息，对启发函数进行改进。新的启发信息能够有效避免算法在特殊环境中陷入局部最优，且利用人工势场法的先验航迹作为启发信息的参数，使得算法的收敛速度得以提高。

通过对算法的复杂度和实用性分析，并结合在特殊环境和复杂环境下的仿真结果来看，本文提出的蚁群-势场算法能够在UV重力辅助导航航迹规划中较好地躲避非适配区，顺利到达目标，且航迹平滑，航迹长度较短，能够更有效地进行航迹规划。

作者简介

第一作者简介：张驰(1993-), 男, 硕士生, 研究方向为重力辅助导航和物理大地测量。E-mail:18631492420@163.com

通信作者：李姗姗，博士生导师， E-mail：zzy_lily@sina.com

行业 | 就测绘资质管理制度改革，自然资源部正在征求意见

人物 | 杨元喜院士——运筹北斗 丈量天地！

贺浩 王舒洋 王仕成 | 《测绘学报（英文版）》（JGGS）精选论文

年薪40~120万！中国地震局地球物理研究所发布优秀人才引进通知！

院士论坛｜龚健雅：人工智能对摄影测量与遥感的影响与挑战

重磅 | 扬帆远航 习近平这样为海洋经济指明方向

重磅 | 测绘学报编委刘经南院士获湖北省科学技术突出贡献奖

Seabed 2030 Project : 2030年前绘制完整的世界海床地图

测绘名人堂（八）丨高俊院士

权威 | 专业 | 学术 | 前沿微信、抖音小视频投稿邮箱 | song_qi_fan@163.com

欢迎加入《测绘学报》作者QQ群： 751717395

进群请备注：姓名+单位+稿件编号