Gravity Matching Method Based on Artificial Bee Colony Algorithm with Restriction and MHD*

GAOWei，ZHAO Bo，ZHOU Guangtao

(College of Automation，Harbin Engineering University，Harbin 150001，China)

Gravity Matching Method Based on Artificial Bee Colony Algorithm with Restriction and MHD*

GAOWei，ZHAO Bo，ZHOU Guangtao*

(College of Automation，Harbin Engineering University，Harbin 150001，China)

Gravity matching algorithm is one of the key technologies for gravity aided inertial navigation system. However，there are lots of defects such as high complexity and small range of applications for the traditionalmatchingmethods，so it is difficult to obtain a accurate and fastmatching result.This article will introduce artificial bee colony algorithm with restriction into the searching process of gravitymatching and take the velocity information provided by DVL as a restriction condition to restrict the searching process of artificial bee colony.On this basis，modified Hausdorff distance(MHD)is introduced in order to select thematching results.As a result，the mismatch rate will decrease with the accuracy of the gravity anomaly in gravity database under certain conditions.The simulation results show that the algorithm has a highmatch rate and can obtain accurate and fast positioning in the gravity zone with significant feature in order to realize gravity aided inertial navigation.

gravitymatching;modified hausdorff distance;artificial bee colony;external restriction

20世纪80年代～90年代美国和前苏联便相继开始了研制战略水下潜器的无源导航辅助系统。最初的辅助方法是基于图形匹配，包括与海底地形图、磁场图的匹配，但由于需要用声纳测量海底轮廓，导致海底地形匹配的隐蔽性较弱;同时由于磁场变化复杂目前还难以真正运用到水下潜器导航中，因此重力异常和重力梯度数据成为水下潜器导航的主要无源信息资源。重力辅助导航具有精度高、隐蔽性强、自主性强等优点，是潜艇等水下航行器理想的水下辅助导航定位手段［1－2］。经典的重力匹配方法有递推最优估计滤波和相关值匹配方法两大类。近几年，在相关值匹配方向有较多研究成果，包括神经网络、支持向量机、数据关联滤波等［3－5］。但是在匹配精度上没有太大提高。

2005年，Karaboga模仿蜜蜂行为提出了人工蜂群算法，该算法是集群智能思想的一个具体应用［6］。它只需要对问题进行优劣的比较，最终在群体中使全局最优值突现出来，在很大程度上避免了局部最优的缺陷，适用于区域目标搜索过程。为此，本文将人工蜂群算法引入到重力匹配搜索过程中，并将外部速度信息作为约束条件，对匹配点进行限制，在一定程度上减少了误配。同时，考虑到匹配结果的多值性，本文采用平均Hausdorff距离对匹配结果进行筛选。平均Hausdorff距离一般用于图像匹配过程中测量两个点集的匹配程度，利用这一准则以获取最优的匹配结果。

1 人工蜂群算法

在人工蜂群算法中，蜂群产生群体智慧的最小搜索模型包含基本的3个组成要素:蜜源、被雇佣的蜜蜂和未被雇佣的蜜蜂。被雇用的蜜蜂也称为引领蜂，其与所采集的蜜源一一对应，引领蜂储存有某一个蜜源的相关信息并以一定的概率与其他蜜蜂分享。未被雇用的蜜蜂的主要任务是寻找和开采蜜源。有两种未被雇用的蜜蜂:侦察蜂和跟随蜂。侦察蜂搜索蜂巢附近的新蜜源;跟随蜂在蜂巢里面并通过与引领蜂分享相关信息找到蜜源。

初始时刻，每个引领蜂对应一个确定的蜜源，蜜源的花蜜量是由相应解的适应度值来决定的。初始化之后，引领蜂根据记忆中的局部信息产生一个新的位置并检查新位置的花蜜量。若新位置的花蜜量比原来的多，则该蜜蜂更新记忆并记住新的位置。待所有的引领蜂搜索结束，将花蜜源信息传递给跟随蜂。跟随蜂根据引领蜂所找的蜜源的花蜜量，按概率选择一只引领蜂并跟随它，在这只引领蜂所在的蜜源附近再搜索到新的位置，并检查新候选位置的花蜜量。若新位置优于原来的位置，则更新并记住新的位置。不断重复寻找到花蜜量最多的位置［8］。

人工蜂群算法的流程图如图1所示。

图1 人工蜂群算法流程图

其中，xij为引领蜂对应的位置变量，cij为随机数rand(－1，1)，随机数i，k∈(1，N)，N为蜜蜂种群数量，j为随机选取的某一位置变量下标。

跟随蜂确定跟踪引领蜂的概率按下式计算:

其中，fiti是第i个解的适应度值，对应蜜源的丰富程度。

如果经过一定次数迭代后，得到的最优解没有改进，为了避免局部最优解，要舍去该位置对应的解，同时由侦察蜂代替引领蜂产生一个新的位置。这样改进是为了增加种群的多样性和随机性。此时，按下式更新位置［9］。

2 平均Hausdorff距离

经典Hausdorff距离是一种极大极小距离，用来描述两组点集之间的相似程度。它的引入使重力匹配基于一种新的测度，能更为有效地表征点集之间相似性，从而对匹配点进行筛选［10］。

有限点集A={a1，a2，…，ap}和B={b1，b2，…，bq}之间的Hausdorff距离定义为:

其中:

式中‖·‖为在点集A和B上的某种距离范数; dh(A，B)称为A和B之间的Hausdorff距离，表示点集A中所有的点到点集B的距离的最大值;dH(A，B)取dh(A，B)和dh(B，A)中较大值，从而可以得到点集A和B之间的匹配程度。

考虑到经典Hausdorff距离容易受到外部干扰，必将导致计算结果存在较大误差，从而影响匹配的效果，故引入平均Hausdorff距离的定义:

其中，

式中，NA表示点集A中的点个数;NB表示点集B中的点个数。

3 重力匹配算法

本文采用双人工蜂群搜索方式，依据相同的搜索策略分别在相邻惯导指示位置周围寻找匹配点。但是两个匹配点之间的距离受到外部速度信息的约束，尽管这样，得到匹配结果仍具有多值性，针对这一问题，本文利用平均Hausdorff距离对匹配点对进行筛选，从而实现重力匹配定位［11－12］。

如图2所示，Pk－1、Pk和Pk+1分别表示INS在k－1、k和k+1时刻指示载体的位置，同时，重力仪可以输出每个时刻的重力异常值Δgk－1、Δgk和Δgk+1。以k－1和k时刻为例，最终确定的最佳匹配点对(~Pk－1和~Pk)需同时满足下面的条件:

式中，Δgobs(k)表示k时刻重力仪输出的重力异常值;Δg(~Pk)表示k时刻搜索点~Pk－1在重力数据库(EGM2008)中插值得到的重力异常值;σd和σg分别表示距离和重力异常差的阈值。

图2 引入外部速度信息的重力匹配原理图

在蜂群搜索过程中，适应度函数值按下式计算:

根据平均Hausdorff距离准则对多组匹配结果(~Pk－1(i)和~Pk(i))进行筛选，确定一个最优的位置作为最终匹配结果，满足下式:

其中，N为待筛选的匹配点个数;~Pk－1、k(i)为第i个匹配点对;Pk－1、k为INS输出的位置点对;^Pk－1、k为筛选后输出的匹配点对。

根据前面的匹配过程可知，每个时刻都要经过两次匹配，并取两次匹配平均值作为最终结果，类似于估计理论中的“估计”和“平滑”两个过程。在有些情况下，可以提供载体准确的位置信息或者匹配过程中初始位置误差较小，可以考虑简化匹配模型，即用Pk－1来代替~Pk－1。这样减少了一个约束条件，有效缩短了匹配时间。在实际过程中，可以间隔一定步长按简化前模型匹配，在获取较准确位置后，再进行简化模型匹配，这样既保证了匹配精度，又缩短了匹配时间［13］。匹配算法的工作原理如图3所示。

图3 匹配流程图

4 仿真分析

4.1 仿真条件及过程

模拟生成惯导系统的运动轨迹包括INS指示轨迹和载体真实轨迹，其中载体真实轨迹为一段直线;建立重力异常数据库，利用模拟的载体真实位置信息通过插值可以得到载体所在位置的真实重力异常值，在此基础上加上一定量测噪声(0.1 mgal)来模拟重力敏感器输出;人工峰群算法的参数设置为如表1。

表1 人工峰群算法参数

根据EGM2008重力异常数据库，获取INS指示轨迹和载体真实轨迹附近的重力异常分布如图4。

图4 匹配区域的重力异常变化

4.2 仿真结果

按以上条件进行仿真，如图5所示，对重力匹配前后的运动轨迹进行对比，其中匹配过程分为未引入和引入Hausdorff距离两种情况，重力辅助导航系统的定位误差小于一个重力基准网格。

图5 不同条件下匹配轨迹效果对比

引入Hausdorff距离前后的匹配精度见表2所示。从表中的试验数据可以看出，与引入Hausdorff距离前相比，引入Hausdorff距离进行筛选后，经度误差和纬度误差都明显减小，说明引入Hausdorff距离对该匹配算法的精度有了较大的提高。

表2 匹配精度对比

5 结论

重力匹配导航问题是一个多解的复杂优化问题，不仅要求匹配精度足够高，而且要求匹配时间短，在考虑现有匹配算法不足基础上，本文提出的一种带约束人工蜂群算法和平均Hausdorff距离的重力匹配方法，并建立仿真环境对该重力匹配算法进行测试。仿真表明，该重力匹配方法可以有效地快速地进行匹配定位，有效地避免了误配情况。尽管传统的人工蜂群算法已经很好地应用到重力匹配中，但是其搜索速度和收敛精度仍有较大提升空间，

同时，还可以将外部航向信息作为约束条件，希望获取更好的匹配效果。

［1］李姗姗.水下重力辅助惯性导航的理论与方法研究［D］.武汉:解放军信息工程大学，2010.

［2］童余德，边少锋，蒋东方，等.基于局部连续场的重力匹配辅助导航［J］.中国惯性技术学报2011，19(6):682－685.

［3］程力，蔡体菁.基于模式识别神经网络的重力匹配算法［J］.东南大学学报(自然科学版)，2007，37(5):839－843.

［4］程力，蔡体菁.基于支持向量机的重力匹配算法［J］.系统仿真学报，2008，20(21):5953－5962.

［5］李姗姗，吴晓平，马彪.水下重力异常相关极值匹配算法［J］.中国惯性技术学报，2011，40(4):464－469.

［6］Karabogad.An Idea Based on Honey Bee Swarm for Numerical Optimization［R］.Turkey:Erciyes University，2005.

［7］KamalamBal.A Comprehensive Review of Artificial Bee Colony Algorithm［J］.International Journal of Computers Technology，2013，5(1):15－28.

［8］黎竹娟.人工蜂群算法在移动机器人路径规划中的应用［J］.计算机仿真，2012，29(12):247－251.

［9］Faiza Abdulsalam M，Azuraliza Abu Bakar.A Cluster－Based Deviation Detection Task Using the Artificial Bee Colony Algorithm［J］.International Journal of Soft Computing，2012，7(2):71－78.

［10］孔亚男，鲁浩，徐剑芸.基于Hausdorff距离的地磁匹配导航算法［J］.航空兵器，2011，26(4):26－29.

［11］马玉良，马云鹏，张启忠，等.GA－BP神经网络在下肢运动步态识别中的应用研究［J］.传感技术学报，2013，26(9):1183－1187.

［12］李牧东，熊伟，梁青.基于人工蜂群改进算法的无线传感器网络定位算法［J］.传感技术学报，2013，26(2):241－245.

［13］Wang Hubiao，Wang Yong，Fang Jian，et al.Simulation Research on a Minimum Root－Mean－Square Error Rotation－Fitting Algorithm for Gravity Matching Navigation［J］.Science China Earth Sciences，2012，55(1):90－97.

高伟(1977－)，男，博士，教授，研究方向为载体姿态及运动参数测量技术，现代船舶综合导航技术，惯性仪表测试及建模技术，水下导航技术，gaowei407 @yahoo.com.cn;

赵博(1988－)，男，硕士，研究方向为捷联惯性导航技术，重力辅助导航技术，重力仪误差补偿技术，zhaobo880928 @126.com;

周广涛(1981－)，男，博士，讲师，研究方向为捷联惯性导航技术，组合导航技术，信息融合技术，计算机仿真技术，zhougt@hrbeu.edu.cn。

基于带约束人工蜂群算法和平均Hausdorff距离的重力匹配方法*

高伟，赵博，周广涛*

(哈尔滨工程大学自动化学院，哈尔滨150001)

重力匹配算法是实现重力辅助惯性导航系统的关键技术之一。但是，传统重力匹配方法存在复杂度高、应用范围小等缺陷，一般很难实现精确、快速匹配的效果。将人工蜂群算法用于重力匹配的搜索过程，并将多普勒测速仪提供的速度信息作为限制条件对蜂群搜索过程进行约束。在此基础上，利用平均Hausdorff距离对匹配结果进行筛选，在重力数据库中重力异常精度一定的条件下，可降低误配率。仿真结果表明，该匹配算法在重力特征显著的区域具有较高的匹配率，可以达到精确、快速的匹配定位，从而实现重力辅助导航。

重力匹配;平均Hausdorff距离;人工蜂群算法;外界约束

U666.12

A

1004－1699(2014)01－0074－05

2013－10－30修改日期:2013－12－16

C:7230J

10.3969/j.issn.1004－1699.2014.01.014

项目来源:国家自然科学基金项目(51179039)