基于遗传算法的地磁匹配搜索策略

陈励华 王仕成 刘志国

第二炮兵工程大学，西安 710025

地磁场是地球的固有资源，场强随空间与时间变化，地磁场导航正是利用这种地磁场在空间分布的各异性来确定载体所在的地理位置。由于地磁定位与地形定位很相似，都是航迹曲线与数字地图的配准，因此目前地磁场导航技术采用的导航算法主要是借鉴地形高程导航算法中的TERCOM(Terrain Contour Matching)和SITAN(Sandia Inertial Terrain Aided Navigation),即地磁匹配与地磁滤波2种方式[1-6]。与地磁滤波相比，地磁匹配可断续使用，不存在累积误差，易于获得更高的导航定位精度，因此逐渐成为地磁导航的主流方法[7]。

地磁匹配(Magnetic Field Contour Matching，MAGCOM)通过对测量序列与基准图之间相关性进行度量完成定位。现有的MAGCOM算法在理论上可以只依据磁测设备提供信息单独实现定位，但实际应用中往往只能作为辅助导航方式，其中基于推位运算的MAGCOM要求航迹为直线，这就最大地限制了地磁匹配的应用。本文重点研究载体行进路径形状未知条件下，如何利用相关性度量实现地磁场定位的问题。文中采用了在最优化问题中成功运用的遗传算法，并对其中交叉与变异概率的选取方法做出相应的改进。仿真实验证实结合智能优化方法的MAGCOM可以完成地磁匹配导航，相关结论亦可用于地形匹配或重力场匹配定位。

1 常规MAGCOM的应用条件

MAGCOM是在预先已知的基准地磁图中寻找与测量序列度量指标最优的一条对应序列作为对测点位置的估计结果，其实质是数据集的配准问题。该方法可具体描述如下(参见图1)。

图1 MAGCOM原理

预先测量地磁场特征量，并绘制成基准图。一般基准图都以网格形式表示，其中横轴和纵轴为地理位置。实际匹配时，根据对载体航行区域的估计，在预存的基准图中选择合适的子图，完成相关性匹配。用于匹配的子图网格数目设为ML×NL，网格宽度表征了基准图的分辨率，纵向与横向分辨率可以相同，也可以不同，图1中基准图采用均匀网格，网格大小为d×d，表示不同方向分辨率相同。

匹配时，根据对当地地磁场特征量的实际测量值Tt={Tt(i);i=1,…,N}与基准图中预存的地磁场数据Tm={Tm(i);i=1,…,N}序列计算相应的相关性度量函数。在所有可能的数据序列中寻找度量指标最优的数据列，其横、纵坐标即是对真实航迹的估计。常用的度量函数指标包括距离与相似性两类。前者如平均绝对差(MAD)算法、平均平方差(MSD)算法等；后者如积相关(prod)算法和归一化的积相关(Nprod)算法等[4-6]。度量中期望距离指标最小或相似性指标最大。

相关性度量仅对地磁测量值完成，因此理论上MAGCOM方法可单独利用磁测计定位。但是在实际度量中，仅仅已知地磁场测量序列是不够的。以MAD度量为例说明如下。地磁场MAD度量指标如式(1)所示：

(1)

其中，Tt(i)为第i点实测磁场数值，d为网格宽度，Tm(u,v)为基准图上存储的(u,v)位置上地磁数据。由于测量航迹序列Tt与基准数字地磁图Tm之间对应关系未知，会造成可行解的MAD指标计算数目极其巨大，具体分析如下：在已知的基准图中搜索指标极值时，路径起点可能是ML×NL中任意一点，假定相邻测点间距与基准图网格宽度d相同，即相邻点之间存在八邻域关系，则对于长度为N的测量序列，测量值与基准图之间所有可能的对应关系共有ML×NL×8N-1种，对所有可行解求取MAD指标，再寻找指标最优解，则会由于运算量过大而导致难以求解。因此现有的MAGCOM方法一般假定测量航迹形状已知,即各测点之间的相对距离和方向信息都是已知的。在这种假设条件下，可行解的个数为ML×NL，有效地减小了搜索空间。

MAGCOM实现一般需借助惯导系统。惯性导航系统经初始对准后，可提供测点之间距离与方向的信息，地磁匹配运算认为真实航迹和惯导航迹形状相同(如图1所示)，以减小可行解数目。这样MAGCOM方法就只能作为辅助导航方式，而无法独立定位。

采用惯性器件导致导航成本较高，因此有时也会采用里程计，利用推位计算为MAGCOM提供航迹信息[8]。由于里程计只能提供测点之间的距离信息，而无法给出方向信息，所以推位航迹一般设为直线，因此该方法只适用于载体行进路径为直线的场合，从而限制了地磁匹配的应用。

MAGCOM的实质是在可能的解空间中搜索度量指标最优，遗传算法是解决搜索问题的一种通用方法，因此本文考虑将遗传算法应用于地磁匹配定位问题。遗传算法的引入使得MAGCOM不再关注测点之间的相对方向信息，只需磁测计和里程计即可实现测量，无需惯性器件的参与，减小了匹配成本。与现有基于推位计算的地磁匹配算法相比，载体行进路径不存在直线约束，可以为任意形状，因此扩大了匹配方法的应用范围。

2 遗传算法及其在地磁场匹配导航中的应用

2.1 遗传算法

遗传算法是借鉴生物界中进化与遗传的机理实现的智能计算，它模拟孟德尔遗传变异理论和达尔文优胜劣汰思想，通过“遗传-竞争-再遗传-再竞争”的方式一步步逼近问题的最优解。遗传算法求解是从代表问题可能潜在的解集的一个种群开始的，在每一代根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。

遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。

2.2 遗传算法在地磁匹配导航中的应用

以下算法的约束条件为测量序列的各测点之间间距已知，该信息可由里程计测量得到。按照测点间距调整基准地磁图网格的大小，相应的序列比对中，某点的相邻测点位置只需在基准图中该点的八邻域中搜索。

2.2.1 初始种群

基于遗传算法的MAGCOM中，基准图上每一条长度为N的序列都对应一个可行解，即种群中的一个染色体，可表示为有序点连接而成的折线：

path=[x1,y1;x2,y2;...;xN,yN]

(2)

其中xi,yi表示路径上第i点在基准图上的坐标，设xi,yi取值为1～ML和1～NL范围的实数，且相邻点满足八邻域关系：

(xi-xi-1,yi-yi-1)∈{(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)}

根据相邻点的邻域关系，染色体亦可用相对坐标表示为

path1=[0,0;x2-x1,y2-y1;...;

(3)

相邻点的邻域关系仅有8种，因此path1的表达形式比path简单，但缺少起始点的信息。

初始解path的产生可以通过以下3个步骤完成：

1) 序列的起始点(x1,y1)产生。起始点可能在已知基准图中任何一点，因此可以随机的产生取值为1～ML的任意实数x1和1～NL的任意实数y1；

2) 相对坐标序列path1的产生。随机产生长度为N-1的相邻点八邻域关系，并按式(3)的规则产生path1；

3) 根据式(2)和(3)关系可计算得到初始解path。

按照以上步骤可以产生m个初始解，形成初始种群。

2.2.2 适应度函数

其中， bij（0-t）表示在时间段 （0-t） 内， i地区j产业的增长速度，表示在时间段（0-t）内j产业在全国的增长速度。

解的优劣可以通过该路径与测量值的相似性程度来体现。适应度函数选为相似性度量指标如MAD，NPROD等。MAD指标对应的适应度函数如下：

NPROD指标对应的适应度函数如下：

适应度函数根据某一染色体path中每一个点对应的基准图中地磁场强度大小Tm与实际测量序列中对应的磁测值Tt进行比较、计算得到。对某染色体而言，以上2个适应度指标越大，则意味着该染色体适应能力越强。

2.2.3 遗传算子

遗传算法的选择算子采用轮盘赌的方式，适应度越高的个体被选中的概率越大。在交叉与变异中为保证运算后能满足相邻点的八邻域要求，执行运算时区分起点和其余各点。起点的交叉和变异对path中的第1组坐标(x1,y1)进行，其余各点则利用path1表达式，即改变点之间的邻域关系。经过交叉与变异后，路径上点间的邻域关系发生变化，获得新个体。

遗传算法中交叉概率Pc和变异概率Pm的选择是影响算法性能的关键。交叉概率Pc过小会导致搜索过程变慢，过大会破坏优秀个体的结构；变异用于表现基因的突变，可使求解过程跳出局部搜索空间，变异概率Pm过小不易产生新的全局极值，过大则遗传算法会成为纯粹的随机搜索。因此Pc和Pm需要反复试验确定。Srinvivas等人提出根据适应度大小自适应调整Pc和Pm的方法[9]，如式(6)和(7)所示：

(6)

(7)

式中，fmax为群体中最大的适应度，favg为每代群体平均适应度，f′为交叉的两个体中较大适应度，f为变异个体的适应度。

本文研究的长度为N的有序点集配准问题，实际是个多级寻优问题。结合多级寻优具有可加性特点，提出以局部适应度函数对以上自适应调整Pc和Pm的方法作进一步改进。最优解从起点开始，以小于等于N的任何一级作为终点，得到的序列仍应是该长度下的优解。为保护优秀基因不在交叉和变异中遭到破坏，设置局部适应度函数。以MAD指标为例，第n级局部适应度函数如式(8)所示，其中n为[1,N]中的任意整数。

(8)

与式(4)相同，式(8)的分母部分表示的也是被搜索序列与测量序列相比平均每点的距离偏差，因此可以将局部适应度与整条序列的适应度比较。

交叉可单点进行，也可多点进行。本文采用单点交叉的方式，随机选择交叉点，依据式(8)计算拟交叉的2条序列在该点的局部适应度d1和d2，令f′=max(d1,d2)，由式(6)计算可得Pc，同理以局部适应度取代序列适应度计算Pm。

局部适应度的作用是针对那些包含优秀基因的劣解，能在减小优秀基因段被改变概率的同时尽量增大不良基因交叉和变异的可能。

2.2.4 迭代终止条件

遗传算法循环迭代搜索，迭代次数是影响计算量的重要因素。只要满足以下任一条件，即停止迭代：1)设定最大遗传代数Gn，当迭代次数到达Gn，即停止迭代，以当前最佳个体作为匹配结果； 2)迭代到一定程度可能已无法得到适应度更优的结果，若连续g代最优适应度未有改进，即停止迭代。

2.2.5 算法的复杂度分析

算法效率可用时间复杂度分析。以比较运算作为基本操作，在本文的约束条件下，现有MAGCOM方法时间复杂度为o(ML×NL×8N-1)，上述遗传算法中，种群大小m序列长度为N的染色体，最大迭代次数为Gn，整个计算过程的时间复杂度为o(m.N.Gn)。当序列长度较大时，遗传算法的计算量优势明显。

2.3 仿真验证

为了验证本文提出算法的有效性，在实测地磁图上进行仿真试验。该图来自我国西部某地区实地测量结果。地磁图网格数为30×30，网格间距为20m×20m，对应测点间距亦为20m。仿真中适应度函数取MAD 指标，序列长度取N=10，交叉概率Pc与变异概率Pm如前所述自适应获得，初始种群大小m=50，遗传代数Gn=100。

在不考虑噪声的条件下，对某测量序列在整个基准图中搜索，定位结果如图2所示。图中序列的10个测点中有8个完全匹配，整个序列的总误差为2.828网格，且误差随种群规模和迭代次数的增大、参数设置的改进还有望减小。这表示遗传算法能够在已知测点间距的条件下，利用相似性比较获得测量路径的形状，因此不必依赖惯性系统信息，即可完成定位。

图2 仿真结果

3 主要影响因素分析

遗传算法中解的生成具有不确定性，而且地磁匹配定位还需考虑测量噪声与基准图制备等误差因素影响，因此很难保证定位结果足够理想。本节从基准图大小、序列长度、噪声条件等方面对地磁匹配进行仿真，寻找以上因素对算法影响的规律以及改进措施。以下仿真中，如未作特殊说明，仿真条件同2.3节。

3.1 基准图大小

在不考虑噪声的条件下，选取序列长度为N=10，在不同基准图大小条件下完成匹配。基准图网格数分别为10×10，20×20，30×30，经过500次匹配，计算所得的平均误差如表1所示。表中误差亦指整个序列误差。

表1 基准图网格数的影响

由于遗传算法参数选取一致，因此表1中3种情况搜索的运算量是相同的。然而基准图越大，会导致匹配空间越大，因此遗传算法越容易落入指标的局部极小值点而无法实现序列的准确比对，造成误差随基准图增大而增大。对于本例而言，如表1所示，即使在基准图为30×30的仿真条件下，整个序列的定位误差仍可达到5个网格左右，相应的平均单点误差仅有0.5个网格，定位精度比较理想。

3.2 序列长度与噪声

综合分析序列长度与噪声的影响。在N=5，N=10两种序列长度下，匹配基准图选为20×20，分别叠加如上所述高斯噪声和均匀噪声，其它参数设置不变。对各种情况测试500次，平均结果如表2所示。

表2 序列长度与噪声的影响

将表1和表2中序列长度N=10，基准图20×20的结果对比可以发现，均匀噪声的影响非常小，有无噪声条件下误差差别不大；高斯噪声则影响明显，会引起匹配精度的显著下降。另一方面，序列长度会引起整条序列误差的增加，但平均每个点所引起的误差随序列长度增长并无明显增大的表现。

4 结论

本文提出利用遗传算法实现的地磁匹配。该方法有效解决解空间过大的难题，计算量较小。具体实现中以相似性度量作为适应度函数，采用相对路径完成交叉和变异，并对交叉变异的概率自适应调整方法实现了改进。通过仿真讨论了基准图大小、噪声、匹配序列长度对算法的影响，发现基准图增大、高斯噪声会引起匹配误差的明显增加，而序列长度影响不明显。结果表明，该方法降低了现有MAGCOM方法在使用中的约束条件，在仅提供测点地磁场信息和相对距离信息的条件下，能依靠算法获得路径形状，以较小误差实现定位。

参 考 文 献

[1] Mu Hua, Wu Mei-ping. Geomagnetic Surface Navigation Using Adaptive EKF[C].2007 IEEE Conference on Industrial Electronics and Application,Harbin,2007.

[2] E R Benson,T S Stombaugh,N Noguchi, et al. An Evaluation of a Geomagnetic Direction Sensor for Vehicle Guidance in Precision Agriculture Applications[C]. ASAE Paper 983203, ASAE.St. Joseph,MI,1998.

[3] Mohammad Nizam Filipski,Ermira Junita Abduliah. Nanosatellite Navigation with the WMM2005 Geomagnetic Field Model[J].Turkish Journal of Environmental Sciences, 2006,30(1): 43-55.

[4] 刘颖,吴美平.地磁匹配中的匹配长度估计方法[J].中国惯性技术学报,2010,18(4):439-443.(Liu Ying, Wu Mei-ping.Match Length Estimation in Geomagnetic Matching System [J]. Journal of Chinese Inertial Technology, 2010,18(4):439-443.)

[5] 刘飞,周贤高,等.相关地磁匹配定位技术[J].中国惯性技术学报,2007,15(1):59-62.(Liu Fei, Zhou Xian-gao,et al. Geomagnetic Matching Location Using Correlation Method[J]. Journal of Chinese Inertial Technology, 2007,15(1):59-62.)

[6] 任治新，杨功流，李士心.基于向量搜索的地磁导航匹配算法[J].中国惯性技术学报,2008,16(4)：424-427.(Ren Zhixin,Yang Gongliu,Li Shixin.Geomagnetic Matching Algorithm Based on Vector Search[J]. Journal of Chinese Inertial Technology, 2008,16(4)：424-427.)

[7] 周军,葛致磊,施桂国,等.地磁导航发展与关键技术[J].宇航学报,2008,29(5):1467-1742.(Zhou Jun, Ge Zhilei, Shi Guiguo, et al. Key Technique and Development for Geomagnetic Navigation[J]. Journal of Astronautics, 2008, 29(5):1467-1742.)

[8] 乔玉坤.地磁导航基准图制备与数学仿真方法研究[D].西安：第二炮兵工程学院，2011.(Qiao Yukun.Study on the Preparation and Numerical Simulation of Reference Maps for Geomagnetic Navigation[D]. Doctor Dissertation of Second Artillery Engineering Institute,Xi-an,2011.)

[9] Srinivas M,Patnaik L M.Adaptive Probabilities of Crossover and Mutations in Gas[J]. IEEE Transactions on SMC,1994,24(4):656-667.