果蝇优化算法在区域高程拟合中的应用

张 炎，周 飞，唐诗华，肖 燕，张 跃

(1.广西空间信息与测绘重点实验室，广西 桂林 541006；2.桂林理工大学测绘地理信息学院，广西 桂林 541006；3.广西基础地理信息中心，广西 南宁 530023)

0 引 言

随着现代测量技术的快速发展，全球定位系统(GPS)凭借其全能性、全天候、连续性和实时性得到了广泛应用[1]。GPS测量可以同时测定目标位置的平面坐标和大地高程，并且平面定位精度可达到1～2 cm。但是大地高并不是实际工程中所用到的高程，需要将大地高转化为正常高才能满足工程需求[2]，两者之间存在一个高程异常值。因此，如何获取高精度的高程异常值始终是测绘工作者面临的问题。目前，采用少量GPS水准重合点来实现高程拟合越来越受到业界认可。常规的GPS高程拟合方法有二次曲面拟合、三次样条拟合、多项式曲线拟合、多面函数法等，但前3种方法拟合精度往往难于满足实际工程需求，多面函数法中心点的选取过于繁琐[3- 4]。最小二乘支持向量机(least squares support vector machine，LSSVM)是一种新型机器学习方法，可以利用少量样本数据快速精确地建立拟合模型，但参数的选择较为复杂。

本文提出将果蝇优化算法(fruit fly optimization algorithm，FOA)引入最小二乘支持向量机(LSSVM)，建立区域GPS拟合模型。利用FOA全局寻优能力强、过程简练的特性，快速精准的为LSSVM选择最佳参数，近一步提高利用少量GPS水准重合点建立区域高程拟合模型的精度。

1 最小二乘支持向量机

最小二乘支持向量机(LSSVM)是由Suykens在原有支持向量机的基础上提出的。支持向量机具有结构简单、全局优化、泛化能力较好等优点，而LSSVM除具备这些优点之外还提高了收敛速度，化简了计算过程[5- 6]。两者区别主要在于用等式约束代替标准支持向量机中的不等式约束，并收集数据的误差平方和损失函数作为训练集的经验损失[7]。其具体步骤如下：

针对给定的训练集Α={(x1，y1)，…，(xl，yl)}∈(Rn×Y)l，xi∈Rn，yi∈Y=R，i=1，2，…，l。其中，A为训练样本集；(xl，yl)为训练样本；R、Y为实数集。利用非线性映射将样本输入映射到高维特征空间，构造出高维特征空间的线性回归函数，即

g(x，w)=wTφ(x)+b

(1)

式中，g为线性回归函数；w为权值向量；φ(x)为非线性映射函数；b为阈值。根据结构风险最小化原理，将其转化为以下优化问题，公式为

(2)

约束条件为

s.t.yi=wTφ(xi)+b+ξi

(3)

式中，c为正则化参数；ξ为误差项。利用Lagrange函数和KKT(Karush-Kuhn-Tucker)优化条件可以求得LSSVM的函数模型，即

Z(x)=ai[φ(xk)φ(xi)]+b

(4)

式中，Z(x)为LSSVM的函数；ai为Lagrange乘子。

根据Hilbert-Schmidt原理，引入核函数K(xk，xj)=[φ(xk)φ(xi)]，近而将高维空间的内积计算转换为原空间中的函数的计算，解决了高维特征空间的计算问题，即

(5)

目前，核函数主要有多项式核函数、径向基核函数和线性核函数。考虑到GPS高程拟合预测模型较为复杂，本文选用径向基核函数作为LSSVM的核函数，可以达到比较好的预测效果，即

(6)

式中，σ为核函数参数。

从上面整个过程可以看出，利用最小二乘支持向量机(LSSVM)构建拟合模型只需要确定核函数参数σ和正则化参数c。相比原有支持向量机，计算过程简洁许多。

2 标准果蝇算法

果蝇优化算法(FOA)是由台湾学者潘文超提出的一种基于果蝇觅食行为的群智能优化算法。相比于其他智能优化算法，FOA具备全局寻优能力强、运行时间少、参数少等优点，在各个领域得到广泛应用。其基本原理是果蝇在嗅觉与视觉上的感知能力要优于其他生物，凭借灵敏的嗅觉器官，果蝇可以快速地搜索并分辨出空气中存在的各种气味，达到食物的周围后，借助于优越的视觉定位出同伴与食物的所在地。果蝇优化算法流程见图1。详细操作步骤[8-9]：

(1)初始确定果蝇种群的规模、迭代次数，随机给出每个果蝇个体根据嗅觉寻找食物的初始方向和距离。

(2)在刚开始仍然无法得知食物所在的准确位置，只能先获取果蝇与原点的距离L，进一步计算味道浓度判定值S，利用味道浓度判定值S确定味道浓度判定函数值，最终获取目前所在位置的食物味道浓度。

(3)确定味道浓度最大的位置，记录保存下来，之后所有果蝇均朝此方向飞去。

(4)重复以上步骤，迭代多次，每次的迭代结果均与上一次迭代结果比较，保留食物味道浓度的最佳位置及方向，最终获取食物的最佳位置。

图1 果蝇优化算法流程

3 基于FOA优化LSSVM

在实际的工程应用中，要想获取最佳的GPS高程拟合模型去解决工程中的问题，现有的一些方法难以达到理想的要求。吴吉贤，杜海燕等[10]曾提出过利用LSSVM拟合方法进行区域GPS拟合模型的建立，但需要合理的方法来提取最佳参数。因此，本文提出利用FOA-LSSVM的组合方法来解决这个问题。利用FOA的广泛快速的搜索能力，为LSSVM选取建模过程中的正则化参数c和核参数σ最优值，进一步提高LSSVM方法构建模型的拟合精度。FOA-LSSVM拟合方法的基本步骤是：

(1)输入训练样本数据，并对其进行归一化处理。

(2)设置初始果蝇的种群参数，主要有种群大小D、迭代最大限值Bmax、初始位置(x，y)、方向、搜寻距离L。

(3)计算味道浓度判定值S，并将其映射为LSSVM的参数，建立高程拟合模型及预测。

(4)以均方根误差RSME为味道浓度函数，获取种群内最优个体的位置及最佳味道浓度值记录并保存。

(5)将种群位置、方向、搜寻距离、味道浓度值进行迭代寻优。

(6)输出结果。

迭代次数存在最大限值，若迭代次数达到了最大限值或找到了符合要求的果蝇味道浓度函数值，则结束迭代，将最终结果输出；否则，重复步骤(3)～(6)，直到达到最大限度或获取符合要求的最佳味道浓度函数值为止。

表2 3种模型拟合结果的残差值

4 算例分析

研究区域选择在广西东南小范围区域，覆盖面积约200 km2，以此来分析FAO-LSSVM拟合方法在区域GPS高程拟合中应用的精度。本文选取了30个GPS水准重合点数据进行拟合模型的建立，剩余的10个作为检测样本。步骤如下：

(1)将果蝇种群规模设置为20个，最大迭代次数为80次。

(2)随机选取种群个体的初始位置、方向、搜寻距离。

(3)将径向基函数(RBF)选定为FOA-LSSVM拟合方法的核函数。

为证明FOA-LSSVM拟合方法的有效性，将其结果与BP神经网络、LSSVM拟合方法的拟合结果进行对比。表1为不同拟合方法的符合精度。从表1可知，BP神经网络的内符合精度为0.013 7 m，标准LSSVM拟合方法的内符合精度为0.010 7 m，FOA-LSSVM拟合方法的内符合精度为0.007 9 m，比标准LSSVM拟合方法的内符合精度提高了26%，同时也可以看出其外符合精度也均优于其他2种方法。因此，利用FOA-LSSVM拟合方法构建区域GPS拟合模型具有一定的可行性，且模型的拟合精度较高。

表1 不同拟合方法的符合精度对比

为近一步检验FOA-LSSVM拟合方法的稳定性，选用10个检测数据在该模型中获取GPS高程异常值，从检测数据的拟合结果中得到残差值，并进行对比分析。3种模型拟合结果的残差值见表2。3种拟合方法的残差对比见图2。

由表2和图2可知，相比于BP神经网络、LSSVM拟合方法拟合结果，FOA-LSSVM拟合方法拟合结果波动较小，尤其是相对于常规的LSSVM拟合方法而言，拟合精度更加稳定，总体的波动范围也有所减小，充分证明了该组合方法的现实性及有效性，并且确保了在区域范围内进行拟合模型建立的稳定性。

图2 3种拟合方法的残差对比

5 结 语

本文基于果蝇优化算法对最小二乘支持向量机拟合方法进行了参数优化，进一步解决了其在构建区域GPS高程拟合模型过程中难以获取最佳参数的问题，并与BP神经网络拟合方法、常规的LSSVM拟合方法进行了对比分析，得出以下结论：

(1)利用果蝇优化算法为最小二乘支持向量机拟合方法选择参数时，由于果蝇优化算法本身具有全局寻优能力强、参数少、过程简单、易实现的优点，使得经过其优化的最小二乘支持向量机拟合方法的拟合结果更佳，避免了常见的易陷入局部最优的缺陷，模型的整体拟合精度有了一定的提高。

(2)相比于BP神经网络，在选择了合适的函数、最佳参数的情况下，最小二乘支持向量机拟合方法针对非线性的少量样本数据有更高精度的拟合效果，且FOA-LSSVM组合方法解决了BP神经网络易陷入局部最优化的问题，也避免了其需要大量的样本数据的麻烦，具有一定的现实性及有效性。

本文提出的果蝇优化算法结合最小二乘支持向量机拟合法构建的区域高程拟合模型的精度相比于常规LSSVM拟合法、BP神经网络拟合法有一定的提高，为以后的拟合模型构建提供了思路，但试验对比仅针对了小范围区域，今后需要采集大范围的研究区域数据进行进一步对比分析。