一种改进混沌蚁群的地磁匹配算法

王崇兵，范荣双，李大伟，任 伟

（1.辽宁工程技术大学, 测绘与地理科学学院，辽宁 阜新 123000；2.中国测绘科学研究院, 北京 100039；3.山东科技大学，测绘与空间信息学院，山东 青岛 266590；4.北京博维航空设施管理有限公司，北京 101317）

0 引言

现代导航技术在当今社会发展中扮演者重要角色，无论是在民用还是在军事领域，都离不开导航定位技术。目前已有多种较为成熟的导航系统和组合导航系统，包括全球定位系统（global positioning system, GPS）、惯性导航系统（inertial navigation system, INS）、GPS/INS组合导航系统等，但它们都存在不足之处并且通过自身系统难以克服，例如，GPS信号易受干扰、惯性导航系统具有累积误差、地形导航在平缓地区地形起伏不明显的情况下，导航会受到限制。随着科技的进步及人们对导航的需求不断加大，以上这些系统难以满足长航时高精度导航的需求，地磁导航系统具有全天候可观测、无源、误差不随时间累积等特点，可以较好地弥补现有的某些导航系统所存在的不足，因此，将地磁导航系统作为辅助纠正手段，是一种较好的选择。早在 20世纪 60年代中期，美国的一家公司就提出了基于地磁轮廓匹配（magnetic contour matching, MAGCOM）算法，受当时条件限制，研究人员无法获取地磁场数据，MAGCOM算法无法进行实验验证，但为后续地磁匹配研究奠定了基础，具有深远意义。

近年来，对MAGCOM算法的研究取得了许多成果：文献[3]提出一种改进的基于等值线约束（contour constraint matching, CCM）相关匹配算法，采用粗匹配和精匹配结合的方式，有效消除了载体的初始位置误差；文献[4]提出一种改进型地形轮廓匹配（terrain contour matching, TERCOM）算法，用于水下地磁匹配导航，将基于平均豪斯多夫（Hausdorff）距离（modified Hausdorff distance,MHD）的匹配准则引入该算法中，有效提高了水下地磁匹配导航的精度和可靠性；基于相关性度量的地磁匹配算法存在匹配精度低，抗干扰能力弱等问题，但因其原理简单、计算量小等优势在地磁匹配导航领域仍受学者青睐；文献[5]提出一种基于平均绝对距离（mean absolute difference, MAD）的地磁匹配导航算法，将维纳滤波（Wiener filter,WF)、卡尔曼滤波（Kalman filter, KF）算法与MAD相融合后，来进行相关计算并最后确定载体位置，动态定位效果较好；将仿射变换模型引入地磁匹配算法中的应用也较为广泛，随着不断地研究与探索，该类算法在匹配导航中效果较为明显。文献[6]针对匹配精度和算法效率相互制约问题，建立关于初始误差、初始航向误差、初始速度误差的仿射变换模型，在提高算法精度的同时缩短了算法时间；文献[7]将匹配轨迹与实测数据进行相关性约束，对约束函数进行离散化后引入仿射变换模型中，有效解决了惯导系统长时间定位过程中误差累积问题；文献[8]提出一种基于蚁群优化（ant colony optimization, ACO）的地磁场匹配改进算法，将地磁匹配看作为多级优化问题，采用多级蚁群优化算法进行匹配定位，在算法寻优过程中，利用双重适应度函数进行计算，有效解决了无法利用任意形状路径的匹配导航问题；文献[9]提出一种自适应模拟退火-蚁群地磁匹配导航算法，将模拟退火（simulated annealing, SA）算法与ACO算法融合并改变信息素更新策略，有效解决了算法输出次优解问题；文献[10]针对参考轨迹存在速度误差的问题，提出一种基于仿射遗传的地磁匹配导航算法，实现了参考轨迹存在速度误差下的地磁匹配；文献[11]提出一种基于粒子约束的粒子群地磁匹配算法，利用地磁基准图和地磁测量冗余信息，计算待匹配点为实际位置的置信概率，有效提高算法的匹配速度及匹配概率。

关于地磁匹配算法还有很多新颖的算法，如基于神经网络的地磁匹配算法、三角匹配算法等，在不同的应用背景下有着不同的创新方法，本文只叙述了地磁匹配算法在不断演进过程中，比较具有代表性的一些算法。在前人研究的基础上，针对MAGCOM算法过于依赖惯导系统导致算法具有的局限性，且抗噪效果差、匹配精度较低问题，提出一种改进混沌蚁群的地磁匹配算法，该算法改进了蚁群算法的概率转移公式及信息素的表示方式，将混沌优化算法嵌到蚁群算法寻优过程中，有效提高了匹配精度及匹配效率。最后通过实验证明该算法在地磁匹配导航中的可行性和有效性。

1 MAGCOM地磁导航匹配算法研究

地磁轮廓线匹配算法匹配思路简单，匹配原理易于理解，实现相对容易。在对导航精度要求不高的情况下，是一种较好的选择。

1.1 MAGCOM算法搜索原理

MAGCOM算法的原理与 TERCOM有很多相同之处，它们都是利用相关度量算法进行相关性判别，相关性度量算法介绍可参考文献[11]，采用批量遍历搜索的方式进行匹配。即在一定时间内累积一定长度的轨迹，获取该轨迹上若干个轨迹点并获取相应的特征值进行相关匹配。不同的是，基于MAGCOM的地磁匹配算法是以地磁值作为特征量进行判别，而地形轮廓匹配算法的特征量为地形数据，具体搜索过程也可参考文献[11]。

1.2 基于Hausdorff距离的地磁匹配

Hausdorff距离已在图像识别领域得到了广泛应用，该算法最常用作比较两组点集的相似度，用极大极小值最为评判准则，抗干扰能力较强，计算速度快，具有较好的稳定性和鲁棒性。并且，该算法非常适用于任意曲线形状的匹配。因此，选取该函数作为改进的地磁匹配算法匹配序列与实测序列之间的度量函数。文献[4]给出了平均Hausdorff距离函数基本概念。

当利用平均Hausdorff距离作为匹配轨迹与实测轨迹之间的度量函数时，根据地磁匹配原理和特点，该函数可具体定义为

式中：为待匹配区；为由Hausdorff距离函数求出每条序列适应值；H为地磁实时测量序列值。(,)为地磁实时测量序列值到待匹配序列的单向Hausdorff距离；(,)为待匹配序列到地磁实时测量序列值的单向Hausdorff距离；当MHD计算结果整体为极小值时，判定对应的点即为最佳匹配点位。

2 基于改进蚁群优化的地磁匹配算法

针对MAGCOM算法的优缺点，结合地磁匹配特点，本节提出一种改进蚁群优化算法。该算法能够进行智能全局优化搜索，精度高并且具有强的抗干扰能力。

2.1 改进蚁群优化算法

蚁群优化算法是受自然界蚂蚁寻找食物过程的启发，提出的一种寻找最优路径的智能随机搜索算法。将该算法运用到地磁匹配导航中，可以解决当载体运行轨迹不明确且为任意形状的情况下，自主匹配定位的问题，但该算法存在计算量大，受噪声影响大，前期因初始浓度相同，未发挥出正反馈效果导致收敛效率低下，以及在搜索过程中次优解占据优势，使算法陷入局部最优等问题。针对以上问题，本文对该算法进行一定的改进。改进蚁群优化算法的实现主要分为以下几部分：

1）初始化各个参数，即在计算之前对相关参数初始化。

2）随机放置蚂蚁到各个城市并利用概率转移公式为蚂蚁随机选择下一次去往的城市，利用该算法进行地磁匹配时，载体上的传感器在匹配区域测得的数据是存在一定噪声的，导致启发式因子对算法造成干扰，所以，将转移概率公式中的启发式因子部分去除，计算蚂蚁从当前点到点的转移概率为

式中：为蚂蚁在点时可以一步到达的位置；为经过此路径蚂蚁的个数；为信息素启发因子；()为时刻在点上的信息素浓度。

3）利用度量函数求出每次迭代的最优解并记录下来。

4）根据当前最优解进行混沌局部再搜索，此步骤将混沌优化算法与蚁群优化算法融合，利用混沌优化算法具有遍历性和随机性等特点，解决传统蚁群优化算法易陷入局部最优问题。

5）更新信息素浓度，本文在信息素更新上主要做了三点改进：①信息素更新方式，传统蚁群算法是将信息素更新到两个节点的路径上，将两点连线作为信息素存储载体，该存储方式大大增加了算法的空间复杂度。根据地磁匹配以及地磁基准图的特点，本文将信息素更新到各个节点上，每个点上信息素浓度的高低决定对蚂蚁的吸引程度，该方式可有效降低算法的空间复杂性；②将混沌优化算法的混动扰动因子加到信息素更新公式中，进行全局信息素更新；③利用自适应挥发因子()替换，传统蚁群算法中挥发因子为(0,1)范围内的常量，算法在进行匹配时，很容易存在未被搜索到的点的情况，当迭代一定次数后，由于蚁群算法的正反馈作用，很容易陷入局部最优解。因此，本文设置挥发因子的最大最小值，利用()替换进行自适应调节，再利用混沌因子和() 改变信息素更新方法，并将混沌优化算法中的变尺度混沌局部再搜索策略，引到蚁群算法寻优过程中，使算法跳出局部最优并加快算法收敛速度。其计算公式为

式中：为最小挥发系数；为最大挥发系数；为随机数；()为自适应挥发系数；为挥发因子调整系数，且∈(0,1)。

6）输出最优解。

2.2 改进蚁群地磁匹配算法设计

通过对基于改进蚁群优化算法的相关介绍，本节将给出详细的地磁匹配算法设计，具体流程如图2所示。

图1 基于改进ACO的地磁匹配算法流程

1）初始化改进蚁群优化算法相关参数，具体包括（最大迭代次数）、（信息素挥发因子）、（信息素因子）、（信息素常数）、（蚁群数量）等

2）设置初始信息素浓度，各节点初始信息素浓度采用非等值划分，确保算法前期信息素作用明显，同时设置最大最小初始信息素区间[,]，防止各节点初始信息素差异较大导致算法停滞。

3）将只蚂蚁随机放置到各个起点，根据改进的概率转移公式为每只蚂蚁选择下一节点，直至达到搜索节点个数为止。

4）利用度量函数求出本次迭代的最佳匹配序列，将该序列与上一次迭代求出的最优解进行对比更新并记录下来，然后，以当前最优解为基础进行变尺度混沌局部再搜索，搜索点集的计算公式为

式中：为当前最优解；α为调节系数；为伪随机数；γ为混沌变量，由乌拉姆-冯·诺伊曼（Ulam-von Neumann）映射产生，该映射的引入可以弥补逻辑斯蒂（Logistic）映射的不足，使搜索点在最优解两侧的邻域内搜索。将可变调节系数α引入函数式中，可以更灵活地改变搜索范围，同时引入伪随机数的三次方缩小搜索范围，加快算法收敛，其计算公式为

式中：为衰减系数；为混沌迭代系数；为当前迭代次数。

5）利用改写的信息素更新公式，全局信息素更新的计算方法为

式中：Δ()为时刻蚂蚁从当前点到点信息素变化量；τ为信息素变化总量；N表示蚁群数目；(+1)为Ulam_von Neumann映射产生的混沌因子。

6）将当前迭代次数下的最优解进行保存，迭代次数=+1，将蚂蚁随机放置到各个节点并重新设置初始信息素浓度，进行下一次迭代。当达到最大迭代次数时，结束算法输出最优匹配序列。

3 实验分析

为验证上述算法的有效性，本文选取北京市某区域开展仿真实验。首先，利用CB-3铯光泵磁力仪和GPS导航设备在实验区域内获取200个采样点的地磁属性信息和经纬度信息。然后，对其进行空间结构分析，确定地磁图网格间距（本文地磁图网格间距为50 m，网格大小为50 m×50 m），最后通过克里金插值法构建该区域地磁，如图2所示。

图2 地磁等值线基准

利用载有CB-3铯光泵磁力仪和GPS导航设备的汽车作为真实轨迹；根据真实轨迹加入初始位置误差（100 m,300 m）、陀螺仪零偏误差0.01(°)/h、加速度计零偏误差 5 0× 1 0×（=9.806 65 m/s）等惯导系统常见误差计算生成惯导轨迹；实测序列中加入 20nT白噪声，增强随机测量噪声干扰；轨迹形状在地磁图中随机生成；匹配后的轨迹分别由传统蚁群算法、基于蚁群算法改进的地磁匹配算法以及MAD算法匹配得到。MAD算法是由文献[6]中提出的一种地磁匹配算法，MAD算法是MAGCOM匹配算法中较为经典且具有代表性，因此，利用该算法的匹配结果作参考可使实验分析结果更具有说服力。

3.1 实验参数设置

对上述算法进行实验时，所涉及的参数设置如表1、表2所示。

表1 传统ACO参数设置

表2 改进ACO参数设置

3.2 实验结果分析

通过对基于MAD的地磁匹配算法、传统蚁群优化算法及改进蚁群算法的地磁匹配算法进行实验，得到匹配结果如图2、图3所示（注：图2、图3为地磁图局部放大部分）。

图3 传统ACO匹配结果图

由图3和图4匹配结果图可知，在加入20nT磁场测量白噪声的条件下，传统蚁群优化算法和MAD匹配算法匹配航迹均明显偏离真实航迹，定位精度较差，MAD匹配算法偏离最为明显，而改进蚁群优化算法匹配航迹仍在真实航迹附近，依然具有较高的匹配精度。

图4 改进ACO匹配结果图

通过导航系统得到的20个采样点的匹配误差值进行统计，并将各采样点东向和北向误差取绝对值求平均，得到统计结果如图5所示。

图5 采样点匹配误差数值曲线

通过图5可知：利用平均绝对差（MAD）进行匹配，各采样点匹配误差较大，虚线变化幅度较为明显，匹配效果差；传统蚁群算法匹配精度优于MAD地磁匹配算法，但受测量噪声影响较大，曲线震荡也较为明显，说明该算法抗噪能力弱，稳定性差。改进蚁群优化算法与MAD和传统蚁群优化算法相比较而言，整体匹配误差小，而且匹配误差曲线变化较为平缓，说明该算法抗噪能力强，稳定性较好，可以进行地磁匹配导航。

通过每一次实验计算匹配航迹的东向和北向误差取绝对值求平均后进行统计，得到匹配结果如表3所示。

表3 不同算法匹配结果

由表3可知：在测量噪声较为明显的条件下，基于蚁群改进的地磁匹配算法较 MAD地磁匹配算法精度提高了约171 m；较传统的蚁群优化算法精度提高了约74 m。由此可知，该算法抗干扰能力较强，具有一定的鲁棒性，具有更高的定位精度和更好的匹配效果。

4 结束语

随着社会的快速发展，人们对地磁匹配导航算法也提出了更高的要求，匹配速度快、精度高、稳定性好是判断地磁匹配算法优劣的先决条件。因此，为了让地磁匹配导航技术在导航定位领域发挥更大的作用，提出该算法以Hausdorff距离作为度量函数并利用该函数配合进行信息素更新，改进概率转移公式及信息素表示方式，将混沌优化算法与基本蚁群算法融合进行地磁匹配，有效弥补了 MAGCOM 算法存在的缺陷，减少测量噪声对地磁匹配结果的影响，实现了地磁匹配算法精度的提高。文中选取北京某区域地磁基准图进行实验，实验结果表明：该算法不仅可以在任意轨迹下进行匹配定位，而且在抗噪能力和匹配精度方面都优于传统蚁群优化算法和 MAD的地磁匹配算法，可以利用该算法进行匹配导航。