论利用粒子群算法求解测距定位方程

欢迎大家来到IT世界,在知识的湖畔探索吧!

摘要：针对用传统解算方法求解非线性测距定位方程时，其解算结果不稳定及可靠性低的问题，利用粒子群算法对测距定位方程进行求解。模拟和实测算例的结果表明，粒子群算法相较于传统解算方法能够准确、高效地搜索到多个全局最优候选解，对进一步结合实际或引入约束条件，最终获取唯一解具有一定的应用价值。

关键词： 多解性 测绘学 测距方程 病态方程 粒子群算法 非线性

大地测量学科中观测模型多数为非线性模型[1,2]，其中测距定位方程又是1类应用最广、最为关注的非线性观测模型。非线性平差问题，通常采用待求参数的近似值对非线性方程进行泰勒（Taylor）级数展开,并取其1阶项，使其转化为线性平差问题进行求解[3]。然而，待求参数的初值与真实值偏差较大时，会导致解算失败；当平差模型的非线性强度较大时，线性化处理甚至失效[4,5]。非线性强度的刻画，通常以模型的固有曲率和参数效应曲率作为评价指标[6,7]。

非线性观测方程的求解，通常是基于线性化处理的普通线性最小二乘法，或采用高斯-牛顿法为代表的非线性最小二乘法。大地测量平差模型病态时，线性化平差方法和高斯-牛顿法等数值解法会呈现出解的不稳定特性[8,9,10]。文献[2]指出，病态问题的主要特征是解的不稳定性质。文献[11]从经典测量平差理论出发，讨论了处理非线性问题的适用条件。文献[12]指出，非线性扰动主要来自于线性化过程中系数矩阵的扰动及附加的截断误差，文献[12]也讨论了非线性平差的收敛稳定性问题。文献[13]提出1种似解析非线性平差解法，该解法的基本思想源自高斯-雅克比组合平差方法，通过将超定非线性方程组转化为多个恰定方程组来进行参数求解。文献[14,15]在高斯-牛顿法的基础上，推导出了非线性的封闭式牛顿法，并对封闭式牛顿法退化为牛顿法的相关条件进行了探讨。

本文对测距定位方程解算产生多解性的原因进行解析，以控制点近似共线及近似共面2类定位构型为例，对测距定位方程多解原因进行了探讨。应用粒子群算法对测距定位方程进行求解，这是因为粒子群算法在求解非线性测距定位方程时，不需进行线性化处理，而且粒子群算法在解决解的多解性、稳定性及全局解搜索方面具有一定优势。最后以模拟和实测病态测距定位方程求解为例，验证了粒子群算法求解测距定位方程的优越性和可靠性。

1、测距定位方程多解性分析

大地测量学科中不适定问题是广泛存在的，其中系统的病态性更是测量平差领域中的常见问题，系统存在病态将影响参数解的稳定性，难以获取准确的参数估值和可靠的平差成果。系统病态性产生的原因涉及多方面，测距定位中系统病态性产生的原因，主要是由控制点的几何分布造成，体现在控制点与待定点组成的定位图形的设计矩阵表现出严重的复共线性。例如，当控制点近似共线或近似共面分布时，2类定位构型对待定点进行求解时，常出现多个不同解的情况产生，即由于定位图形结构而产生的病态性，使参数的求解表现为不稳定性。下面将讨论控制点近似共线和近似共面2类定位构型产生多解性的原因，图1为控制点近似共线分布示意图。

图1控制点近似共线分布

从图1中可知，控制点近似共线分布可表示为控制点分布在以圆柱体为限制的图形中，其中控制点的平面坐标（x,y）以圆柱体的底面圆为范围随机生成，坐标分量z均匀分布在以圆柱体的高为限制的范围内，控制点的共线程度以圆柱体的半径R作为评价指标，R越小表示控制点的共线程度越强，反之则共线程度越弱。

控制点近似共面的分布时，控制点与待定点之间组成的定位图形如图2所示。

图2控制点近似共面分布

从图2中可知，控制点近似共面分布可表示为控制点分布在以高度H为限制的几何体内部，控制点的平面坐标（x,y）在几何体底面内均匀分布，坐标分量z在高度H内随机生成，控制点的共面程度以几何体的高度H作为评价指标，H越小表示控制点的共面程度越强，反之则共面程度越弱。

从理论上讲,仅用2个控制点的测距信息就能应用最小二乘算法对待定点坐标进行求解，然而，当控制点近似共线和近似共面时，控制点坐标分量的取值相差很小，就空间几何图形而言，其变化是微小的，是几何结构非常差的系统，因而设计矩阵是病态的；就观测信息而言，由于近似共线和近似共面时，控制点与待定点的设计矩阵不是满秩矩阵，相当于观测信息不足的情况，因而参数的求解会出现多解现象。下面从定位构型的角度，分析测距定位方程解算产生多解性的原因，图3为定位构型多解性的解析图。

图3定位构型多解性解析示意图

为了便于几何图解，讨论仅限于2维空间，相关结果很容易推广到3维空间。2维距离方程为

式中：(xi,yi)为控制点坐标；(x,y)为待定点坐标；ρi为第i个控制点与待定点的欧式距离；εi为距离观测距离iL的随机误差；n为距离观测个数。

距离函数ρi的1阶导数为

式中：αi为方向余弦向量ei=(cosαi,sinαi)与X坐标轴的夹角，对于待定点的初值(x0,y0)，可得到距离函数的微分dρ=ρi(x,y)-ρi(x0,y0)=cosαidx+sinαidy。设dx=k(cosβi,sinβi)为坐标微分，则沿方向(cosβi,sinβi)距离函数ρi(x,y)的方向导数为

距离函数ρi(x,y)沿着方向余弦的垂直方向时，方向导数为

式（4）表明，当坐标微分与方向余弦垂直时，dx对于距离微分不产生影响。将坐标微分dx代入距离函数的微分dρ中可得

式中：为坐标微分的长度；θi为方向余弦与坐标微分的夹角，其范围为0°～90°。由式（5）可知：距离微分的大小仅与坐标的微分长度k和方向余弦与坐标微分之间形成的角度相关。由上述分析可知，当控制点近似共线与近似共面分布时，方向余弦与坐标微分之间的夹角近似处于垂直状态，因而造成距离计算结果与观测值相差较小，即距离的残差较小，从而产生多解现象。

2、测距定位方程粒子群搜索解法

非线性观测方程的求解，可通过Taylor级数展开后，进行线性方程组的求解，然而当方程的非线性强度较大时，线性化所产生的误差对解算结果将产生较大的误差影响。当采用迭代算法进行参数求解时，例如高斯-牛顿算法会涉及矩阵求逆等复杂运算，待估参数初值的准确性也决定了方程组求解的成功与否，这也成为这类算法求解非线性观测方程的不足之处；此外，包括高斯-牛顿法、牛顿法等解析方法获取的解算结果通常为局部最优解，很难获得问题的全部解和全局最优解。因此，本文将启发式算法中的粒子群算法，应用于测距定位方程的求解，该算法的核心思想为种群间个体的信息交互，从而使种群个体不断优化得到问题的最优解[16]。粒子群算法具有高精度、高稳定性和全局搜索能力，计算过程中不需要进行线性化和矩阵求逆等复杂运算。图4为应用粒子群算法对最优化问题求解的流程图。

图4粒子群算法流程图

由图4可知，应用粒子群算法的关键步骤为适应度函数的建立，对粒子的适应度进行评价，使粒子不断对自身进行优化，从而搜索到全局最优解。应用粒子群算法对待定点求解时，可将式（1）的测距定位方程转化为最优化问题的求解，即

式中：F(X)为测距定位方程求解的目标函数；为距离估值与观测距离之差即距离残差。式（6）为测距定位方程解算时的目标函数，粒子群算法在搜索最优解的过程中，需要建立适应度函数，对粒子的性能进行判定，适应度越大，表明粒子越接近问题的最优解，本文将粒子的适应度函数定义为测距定位方程求解目标函数的倒数，即

式中Fitness为粒子群算法求解测距定位方程的适应度函数。

采用粒子群算法对D维空间的测距定位方程进行求解时，设定初始生成粒子数目为N，其中第i个粒子的当前位置为Xi=(Xi1,Xi2,,XiD)，粒子的位置限定范围为Xmin≤Xij≤Xmax，粒子的当前速度为vi=(vi1,vi2,…,viD)，粒子的速度限定范围为vmin≤vij≤vmax。单个粒子的最优搜索位置记为Pbest，全部粒子的最优搜索位置记为Gbest，当粒子从第k次进行第k+1次迭代时，粒子的位置和速度更新为

式中：ω为惯性权重因子，是粒子的历史信息对速度更新产生的影响；1c为自身认知参数，是粒子自身历史最优值的权重系数；c2为社会认知参数，是粒子全局最优值的权重系数；r1、r2为[0,1]区间的随机数。由式（8）可知，粒子群算法的核心思想是群体信息的传递与共享，从而使粒子在限定范围内搜索到问题的最优解，图5为粒子群算法搜索最优解过程中，粒子的更新示意图。

图5粒子移动示意

从图5可知，粒子的运动方向与3个因素相关，分别为粒子的惯性、粒子的个体最优解以及全局最优解，3个部分共同决定粒子的移动方向。本文应用粒子群算法对测距定位方程进行求解时，为充分发挥粒子群算法搜索最优解的性能，粒子惯性ω设置为0.7，自身认知参数1c设置为1.5，群体认知参数c2设置为1.2，算法的最大迭代次数为设置100。

3、算例列举

算例1。3维测距定位中，控制点近似共线时，待定点的求解出现不稳定的态势，表现为产生多个参数解的情况。为验证这一结论，随机生成1000组近似共线的定位构型，对待定点坐标进行解算，控制点坐标范围为：坐标分量x为-2～2m；坐标分量y为-2～2m；坐标分量z为-100～100m。每组实验的控制点数目设置8个，观测距离添加0.5m的随机误差，待定点坐标模拟值为（50m,0m,50m）。采用粒子群算法对待定点进行求解，粒子在3个坐标分量的搜索范围都为-100～100m,移动速度范围为-2～2m。具体的解算结果如图6和图7所示。

图6控制点近似共线定位解分布

图7控制点近似共线定位解算结果

图6和图7为应用粒子群搜索算法，对随机生成的1000组近似共线定位构型进行待定点坐标解算的结果，可知当控制点呈现近似共线分布时，待定点的解算结果分布在围绕控制点的近似圆周之上，其原因为，当控制点为近似共线分布时，控制点与待定点之间的距离计算结果与观测距离之差较小，从解算结果的残差平方和中能证实此结论，此时进行待定点的解算时会出现多解现象。

算例2。3维测距定位中，控制点近似共面时，待定点的求解出现不稳定的态势，表现为产生多个参数解的情况。为验证这一结论，随机生成1000组近似共面的定位构型控制点，对待定点坐标进行解算，控制点坐标范围为：坐标分量x为-10000～10000m；坐标分量y为-10000～10000m，坐标分量z为-100～100m。每组实验的控制点数目设置6个，观测距离添加0.5m的随机误差，待定点坐标模拟值为（50m,0m,50m）。采用粒子群算法对定位点进行求解，粒子在3个坐标分量的搜索范围都为-100～100m,移动速度范围为-5～5m，具体的解算结果如图8和图9所示。

图8控制点近似共面定位解分布

图9控制点近似共面定位解算结果

如图8和图9可知，当控制点呈现近似共面分布时，待定点的解出现在待定点与控制点平面的垂直方向上，呈现线型分布，其原因为当控制点近似共面分布时，垂直方向上存在的偏差对距离计算的影响较小，从而与观测距离之差较小，造成距离变化的不敏感而产生多解现象。

算例3。采用文献[17]中的模拟测边网进行实验，P1、P2、…、P8为8个已知的控制点，P0为待定点，模拟值为(0,0,0），控制点坐标分布及观测距离信息见表1。采用粒子群算法对待定点进行1000次求解，粒子在3个坐标分量的搜索范围为-100～100m，移动速度范围设置为-1～1m，具体的解算结果如图10和图11所示。

表1控制点坐标和距离观测值

图10算例3的定位解分布

图11算例3定位解算结果

图11算例3定位解算结果

如图10和图11所示，当采用文献[19]中控制点近似共线的测边网算例对待定点坐标进行解算时，应用粒子群算法对待定点坐标进行1000次解算，可知当控制点近似共线时，待定点的解算结果产生多解现象呈现出近似圆形分布，与本文所得结论一致。

4、结束语

本文对控制点近似共线和控制点近似共面2类定位构性产生多解性现象的原因进行了探讨，从图形的角度进行多解现象的成因分析，发现控制点近似共线与近似共面分布时，造成多解的原因主要是由于控制点与待定点之间的距离计算结果与观测距离之差较小，从而产生多个残差平方和较小的解算结果而产生多解现象。

引入粒子群算法对测距定位方程进行解算，该算法相比于传统迭代算法不需进行线性化处理，具有高精度、高稳定性和全局搜索能力。粒子群算法为解决复杂的非线性最优化提供了全新的思路，然而算法的性能与相关参数的设置密切相关，参数的合理设置以及与其它智能算法的融合，用以提升算法的性能将会是未来研究的主要内容。