一种基于蚁群算法的山区GPS高程异常拟合方法

蒲 伦，唐诗华，张紫萍，李宗婉，张 炎

(1. 桂林理工大学测绘地理信息学院，广西 桂林 541006； 2. 广西空间信息与测绘重点实验室，广西 桂林 541006； 3. 青海省生态环境遥感监测中心，青海 西宁 810007)

随着现代测绘技术飞跃发展，GPS在实际工程中的应用越来越广泛[1]。为满足各行业的建设需求，建立精确可靠的高程基准是测绘行业必不可少的工作。采用GPS技术能够精确测定地物点的坐标，但GPS获取的大地高不能直接用于实际工程，转换为实际所需的正常高是数据处理的关键技术，即高程异常拟合的精度直接影响坐标转换精度[2]。

GPS高程异常拟合的方法较多，目前常用的拟合方法有多项式曲线拟合法、三次样条曲线拟合法、平面拟合法及多面函数拟合法等[3]。常规拟合方法在地势平缓地区拟合效果较好，能够满足实际精度需求[4]。在地形条件复杂、地势起伏较大的山区获取拟合数据，常规方法很难满足实际所需精度要求，往往需要对传统方法进行一定的改进[5]。多面函数法可以解决山区GPS高程异常拟合困难问题，但在采用多面函数法拟合时，要提供足够的特征点才能达到理想的拟合效果[6]。寻找特征点的过程较为烦琐，为解决特征点选择困难的问题，本文基于蚁群算法来寻找最佳分布的特征点。利用蚁群算法对多面函数必要参数及其数量进行有效选择，为模型构建提供可靠依据。

1 蚁群算法基本原理

蚁群算法是由Marco Dorigo在20世纪90年代提出的寻优方法，主要是根据蚂蚁在寻找食物时通过正反馈寻找最佳路径的方法[7]。如图1所示，蚂蚁寻找食物过程中能够在通过的路径上释放信息素，蚂蚁之间就是以信息素实现信息传递，后续到来的蚂蚁倾向于选择信息素浓度高的路径，个体之间不断进行信息交流和传递，表现出一种信息正反馈现象[8]。路径上经过的蚂蚁数越多，路径上留下的信息素就越浓，越能吸引更多的蚂蚁选择此路径；若路径长期没有蚂蚁经过，或经过的蚂蚁数量太少，会因为信息素逐渐挥发后浓度降低，蚂蚁群体能够通过这种协调机制找到通往食物源的最短路径。

图1 蚁群选择路径示意图

蚂蚁寻找最优路径的过程可以分为3个步骤：①寻找初始路径，将蚂蚁随机分配到研究区域中，每只蚂蚁从空路径开始搜索，根据属性节点重复选取满足条件项加入到路径中，构成完整路径；②对选择的路径剪枝优化，去掉与实际不符或不相关节点，避免影响最优路径筛选；③更新已选路径的信息素浓度，最佳路径的信息浓度增加，反之则降低浓度。

1.1 寻找初始路径

蚂蚁根据重复选择属性节点来完成路径的选择工作，选取属性节点理论上可以任意随机，但考虑搜索速度及效率问题，以启发函数的形式来指引蚂蚁选择路径显得很有必要[9]。将启发式函数ηij表示为

(1)

式中，启发值大小表征选择路径能力；K为路径数量；a为属性的数量；bi为属性i的个数；infoTij为选择属性节点时符合条件的可设比例关系式。

给定蚂蚁的随机位置，设置信息素初始浓度值，计算公式表示为

(2)

式中，τij为条件项的信息素浓度。根据启发函数和信息素浓度来确定是否选择某一路径，可计算对应的概率确定是否选择。路径概率公式为

(3)

通过属性节点被选中的概率值来判定是否选取为当前路径，若满足相应条件即可设为备选路径，形成一条完整的路径。

1.2 初始路径优化

构造初始路径时添加每个属性节点，形成完整路径，条件项过多将对蚁群择优路径造成一定的干扰，降低了寻优路径的选取质量，此时需要去掉不相关的属性节点，由优化后的有效性来判断是否保留有效的属性节点。有效性的计算公式定义为

(4)

式中，TP为满足条件，实测与预测值相同数目；FP为满足条件，但实测与预测值不同数目；TN为不满足条件，实测与预测值不同数目；FN为不满足条件，实测与预测值相同数目。

通过上述有效性决定是否去除某个属性节点并保留最佳属性。设A={条件i，类名，i=1，2，…，n}表示生成的路径A，可得路径的剪枝实现步骤为

(1) 计算A的有效性AG。

(2) 移去A中的条件i，形成B路径，同理计算B的有效性BG。

(3) 比较AG和BG有效性，若AG

(4)i=i+1反复循环前3个步骤，当执行完所有的条件后循环结束并选择最优路径。

1.3 信息素更新

构造初始路径并经过优化后得到的路径，其属性节点的信息素浓度都会发生变化，信息素浓度更新的过程中会考虑最优路径选择的效率问题，调整信息素浓度的规则是提高包含在最优路径中的属性节点浓度，降低不包含最优路径中的浓度。更新公式为

τi j(t+1)=(1-ρ)·τij(t)+G·τi j(t)

(5)

式中，ρ为信息素的挥发系数，根据实际需要设置挥发系数。每次构造路径都将更新浓度，所有蚂蚁不断重复进行更新。通过循环迭代，设置停止准则，选出最优的路径后若满足停止条件则停止循环，从而获取最优的路径。

2 多面函数法拟合山区GPS高程异常

多面函数法是美国Hardy教授在19世纪70年代提出的由若干简单曲面叠加成复杂连续曲面的建模方法，任意规则或不规则圆滑曲面都可由单值数学面叠加逼近，达到逼近真实模型的效果[10]。适合地形条件复杂、地势起伏明显的山区拟合建模，研究表明任何一个圆滑的曲面都可以通过该方法达到逼近的效果。

2.1 多面函数基本原理

根据多面函数拟合的思想，设f(x,y)为已知曲面函数，若函数φ(x,y)满足

∑(f(xi,yi)-φ(xi,yi))2=min

(6)

称φ(x,y)为逼近函数，逼近函数φ(x,y)表示如下

(7)

式中，u为核函数的个数；β为模型系数；Q表示核函数；(xj,yj)为中心节点。

可选任意函数作为核函数，通常选取对称型或距离型核函数使计算更方便[11]。常见核函数可以分为两大类，大体走势如图2所示。

图2 两种常见类型核函数示意图

根据图2可知，空间数据拟合主要分为“钟”型核函数和“钵”型核函数两类。多面函数拟合中常用的正双曲函数、倒双曲函数及三次曲面函数，其表达式分别为

Q=((x-xj)2+(y-yj)2+δ)1/2

(8)

Q=((x-xj)2+(y-yj)2+δ)-1/2

(9)

Q=((x-xj)2+(y-yj)2)3/2+δ

(10)

式中，δ为核函数光滑因子，用于调节核函数的形状。

选取上述核函数建立误差方程，设有n组观测值(xi,yi,ζi)，i=1，2，…，n， 则得

(11)

式中，(x0j,y0j)表示中心节点位置。ζ为对应的观测值，用A表示核函数矩阵，则改正数V的矩阵形式为

(12)

根据最小二乘原理求得拟合模型的系数项为

(13)

求解拟合模型系数矩阵后代入式(7)即可完成多面函数的拟合模型构建。

2.2 多面函数相关参数设置

2.2.1 选择核函数

多面函数法的模型求解过程中，核函数的选择直接关系到拟合的效果，通常根据观测数据自身较强的相关性来选择核函数，研究人员对此作了大量研究并得出一般性结论[12-13]。判断核函数的优劣遵循一定原则，拟合值与实际观测值之间不存在偏差，待测点的估算值平稳，避免出现急剧变化的现象等。Hardy教授的研究结果表明对扰动位型调和函数拟合采用倒双曲面函数，对地形模型非调和型拟合则采用正双曲面函数实现拟合，管真等对正倒核函数进行了研究[14]。目前对于高程拟合模型构建具有较好拟合效果的核函数主要是正双曲面函数、倒双曲面函数和三次曲面核函数。

2.2.2 确定平滑因子

平滑因子δ是改变核函数形状的重要因素，从图2可以看出，平滑因子δ取不同的值，核函数的大致走势可能保持不变，但会影响核函数的细节变化。齐娜等通过大量试验发现随着平滑因子的递增，检核点残差中误差先变小后逐渐增大，当结果到达理想状态时，平滑因子的值会落在某个区间范围[15]。根据计算和经验确定平滑因子应取0或者较小的正数[16]。

2.2.3 蚁群算法获取特征点

地形特征点的位置及数量的确定是多面函数中关键步骤，其点位选取质量直接影响模型构建的精度高低。对于地势起伏较大，地形条件复杂区域，特征点最好选择合理分布在研究区域内的代表点[17]。数据分布均匀时可选择非严格数据格网化的点位数据加以补充，进而全面表述地形地物特征。均匀特征点的选取决定了多面函数拟合效果，因此，需要有一种高效合理的方法来找出这些特征点，本文基于蚁群算法寻找复杂地形中的特征点方法。

蚁群算法寻找特征点的总体思路：将若干蚂蚁任意分布在研究区内，设置相同的信息素浓度和挥发系数；让每只蚂蚁根据启发函数或最终目标分别寻找具有代表性的特征点，通过迭代循环快速确定蚂蚁群体的行进路线，对于高程拟合的特征点由明显特征是山脊线或山谷线附近的点位；更新移动路径，确定寻找特征点的完整路线；汇集所有特征点并对其密度进行处理，形成最优特征点的集合，提供必要的拟合模型参数。

3 算例分析

以西南某山区GPS观测数据为例，总面积约100 km2，经计算求得该区域内GPS高程异常数据的最大值为27.946 m，最小值为19.953 m。收集了500个 GPS水准重合点，从其中的400个数据中寻找最优特征点，并完成拟合模型构建，然后用剩余数据检核验证拟合模型的精度，综合分析并合理评定高程异常拟合模型的精度及其稳定性。

3.1 获取多面函数拟合的特征点

多面函数的特征点表征研究区域的地形地貌特点，用特征点构建拟合模型能够最大可能接近实际情况。蚁群算法寻找地形复杂地区的特征点具有明显优势，通过寻优路径的正反馈原理能够实现快速搜索的功能，根据实际收集数据及经验，在研究区域分配400只蚂蚁，完成群体规模大小设置，每只蚂蚁的位置分布完全随机，通过大量尝试后给定迭代次数50次，分别寻找范围内海拔差异较大的点。通过蚁群寻优路径的正反馈机制最终向山脊线或山谷线靠拢，完成路径的搜索过程，从而快速找出适用于构建拟合模型的最佳特征点。

根据设定规则可知，初始随机分配蚂蚁的位置没有任何规律可循，蚁群找到特征点位的分布后，所有蚂蚁向山脊线或山谷线汇集，缩小了整个区域的特征点分布范围。蚁群算法找出山脊线和山谷线附近的分布点后，再采用均匀格网法补充少量地势平缓地区的特征点，使选取点更能充分合理说明状况。最后对整体特征点的密度作过滤处理，对于点位密集程度大的地方根据实际情况设置阈值进行筛选，留下最优的选择方案构成特征集合点。

3.2 构建GPS高程异常拟合模型

图3 蚁群算法建模前后检测点三维对比

由图3中拟合前后的三维效果对比图可知，加入蚁群算法的多面函数拟合模型求解结果同实际检测点位GPS高程异常值接近，绘图效果直观说明建模良好。

3.3 拟合结果精度对比分析

完成拟合模型构建后，分别从拟合模型的内外符合精度进行评价与分析。蚁群算法快速搜索特征点集合，求得多面函数的系数矩阵实现模型构建。对同一组检核点分别采用蚁群和格网法获取特征点，然后与蚁群结合均匀格网一同比较分析。从100个检测点的拟合结果中随机抽取了15组，残差对比情况见表1。

表1 不同拟合方法的残差对比 mm

由表1可知，首先采用蚁群算法寻找的特征主要分布在地形起伏较大的山脊和山谷地区，未涉及地势较平缓的区域，只用这些特征点拟合所得结果不稳定，出现明显的误差属于正常现象，故需要利用均匀格网补充平缓研究区域均匀分布的特征点。从表1第3列数据的拟合结果来看，拟合结果的残差更加趋于稳定，同时残差波动范围明显小于仅使用均匀格网法的拟合残差。为了避免偶然情况及精度分析的特殊性，对3种不同拟合方式分别求解其内符合精度和外符合精度，选取计算统计的10次拟合结果(见表2)。

表2说明无论是从内符合精度还是外符合精度来看，蚁群算法结合均匀格网获取多面函数所需的特征点，拟合精度均高于单独使用其中的一种方法的拟合精度，由大量试验统计分析求得检核点的精度σw=±4.4 mm。

表2 不同方法选取多面函数法特征点拟合精度统计 m

除了根据检核点外符合精度来比对分析，为清晰直观地说明蚁群算法在山区GPS高程异常拟合中具有的明显优势，绘制了检核点残差对比图(如图4所示)。另外分别用二次曲面和三次曲面拟合相同检测点的GPS高程异常数据，对比残差曲线如图5所示。

图4清晰展示了蚁群算法寻找特征点的优势，在多面函数建模过程中参数得到了优化，模型的稳定性比仅用均匀格网结果要好。

根据图5中残差曲线走势可知，常规方法适用于平缓区域，而复杂区域难以满足实际需求。多面函数拟合法在山区GPS高程异常拟合中比曲面拟合更加有效可行，同时证明采用蚁群算法优化特征点后的拟合方法对于提高模型的精度具有明显优势。

4 结 语

本文研究了基于蚁群算法的山区GPS高程异常拟合方法，同曲面拟合模型相比，在地势起伏较大的山区选择多面函数拟合法更为合理。将蚁群算法结合均匀格网共同选取最优特征点，然后求解拟合参数并构建多面函数拟合模型。通过算例分析结果表明，基于蚁群算法优化多面函数参数的方法有效可行，构建的拟合模型优于使用单一方法拟合结果，在一定程度上提高了多面函数拟合模型的精度，具有一定的研究价值。

图4 均匀格网与加入蚁群算法拟合结果残差对比

图5 二次曲面与三次曲面法拟合结果残差对比