測距定位方程的多解性及粒子群搜索算法

楊文龍，薛樹強，曲國慶，王薪普，王冠宇

測距定位方程的多解性及粒子群搜索算法

楊文龍1,2，薛樹強2，曲國慶1，王薪普1,2，王冠宇1

（1. 山東理工大學，山東 淄博 255000；2. 中國測繪科學研究院，北京 100036）

針對用傳統解算方法求解非線性測距定位方程時，其解算結果不穩定及可靠性低的問題，利用粒子群算法對測距定位方程進行求解。模擬和實測算例的結果表明，粒子群算法相較于傳統解算方法能夠準確、高效地搜索到多個全局最優候選解，對進一步結合實際或引入約束條件，最終獲取唯一解具有一定的應用價值。

測距方程；非線性；病態方程；多解性；粒子群算法

0 引言

大地測量學科中觀測模型多數為非線性模型[1-2]，其中測距定位方程又是1類應用最廣、最為關注的非線性觀測模型。非線性平差問題，通常采用待求參數的近似值對非線性方程進行泰勒（Taylor）級數展開,并取其1階項，使其轉化為線性平差問題進行求解[3]。然而，待求參數的初值與真實值偏差較大時，會導致解算失敗；當平差模型的非線性強度較大時，線性化處理甚至失效[4-5]。非線性強度的刻畫，通常以模型的固有曲率和參數效應曲率作為評價指標[6-7]。

非線性觀測方程的求解，通常是基于線性化處理的普通線性最小二乘法，或采用高斯-牛頓法為代表的非線性最小二乘法。大地測量平差模型病態時，線性化平差方法和高斯-牛頓法等數值解法會呈現出解的不穩定特性[8-10]。文獻[2]指出，病態問題的主要特征是解的不穩定性質。文獻[11]從經典測量平差理論出發，討論了處理非線性問題的適用條件。文獻[12]指出，非線性擾動主要來自于線性化過程中系數矩陣的擾動及附加的截斷誤差，文獻[12]也討論了非線性平差的收斂穩定性問題。文獻[13]提出1種似解析非線性平差解法，該解法的基本思想源自高斯-雅克比組合平差方法，通過將超定非線性方程組轉化為多個恰定方程組來進行參數求解。文獻[14-15]在高斯-牛頓法的基礎上，推導出了非線性的封閉式牛頓法，并對封閉式牛頓法退化為牛頓法的相關條件進行了探討。

本文對測距定位方程解算產生多解性的原因進行解析，以控制點近似共線及近似共面2類定位構型為例，對測距定位方程多解原因進行了探討。應用粒子群算法（particle swarm optimization, PSO）對測距定位方程進行求解，這是因為粒子群算法在求解非線性測距定位方程時，不需進行線性化處理，而且粒子群算法在解決解的多解性、穩定性及全局解搜索方面具有一定優勢。最后以模擬和實測病態測距定位方程求解為例，驗證了粒子群算法求解測距定位方程的優越性和可靠性。

1 測距定位方程多解性分析

大地測量學科中不適定問題是廣泛存在的，其中系統的病態性更是測量平差領域中的常見問題，系統存在病態將影響參數解的穩定性，難以獲取準確的參數估值和可靠的平差成果。系統病態性產生的原因涉及多方面，測距定位中系統病態性產生的原因，主要是由控制點的幾何分布造成，體現在控制點與待定點組成的定位圖形的設計矩陣表現出嚴重的復共線性。例如，當控制點近似共線或近似共面分布時，2類定位構型對待定點進行求解時，常出現多個不同解的情況產生，即由于定位圖形結構而產生的病態性，使參數的求解表現為不穩定性。下面將討論控制點近似共線和近似共面2類定位構型產生多解性的原因，圖1為控制點近似共線分布示意圖。

從圖1中可知，控制點近似共線分布可表示為控制點分布在以圓柱體為限制的圖形中，其中控制點的平面坐標（，）以圓柱體的底面圓為范圍隨機生成，坐標分量均勻分布在以圓柱體的高為限制的范圍內，控制點的共線程度以圓柱體的半徑作為評價指標，越小表示控制點的共線程度越強，反之則共線程度越弱。

控制點近似共面的分布時，控制點與待定點之間組成的定位圖形如圖2所示。

圖2 控制點近似共面分布

從圖2中可知，控制點近似共面分布可表示為控制點分布在以高度為限制的幾何體內部，控制點的平面坐標（，）在幾何體底面內均勻分布，坐標分量在高度內隨機生成，控制點的共面程度以幾何體的高度作為評價指標，越小表示控制點的共面程度越強，反之則共面程度越弱。

從理論上講,僅用2個控制點的測距信息就能應用最小二乘算法對待定點坐標進行求解，然而，當控制點近似共線和近似共面時，控制點坐標分量的取值相差很小，就空間幾何圖形而言，其變化是微小的，是幾何結構非常差的系統，因而設計矩陣是病態的；就觀測信息而言，由于近似共線和近似共面時，控制點與待定點的設計矩陣不是滿秩矩陣，相當于觀測信息不足的情況，因而參數的求解會出現多解現象。下面從定位構型的角度，分析測距定位方程解算產生多解性的原因，圖3為定位構型多解性的解析圖。

圖3 定位構型多解性解析示意圖

為了便于幾何圖解，討論僅限于2維空間，相關結果很容易推廣到3維空間。2維距離方程為

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

非線性觀測方程的求解，可通過Taylor級數展開后，進行線性方程組的求解，然而當方程的非線性強度較大時，線性化所產生的誤差對解算結果將產生較大的誤差影響。當采用迭代算法進行參數求解時，例如高斯-牛頓算法會涉及矩陣求逆等復雜運算，待估參數初值的準確性也決定了方程組求解的成功與否，這也成為這類算法求解非線性觀測方程的不足之處；此外，包括高斯-牛頓法、牛頓法等解析方法獲取的解算結果通常為局部最優解，很難獲得問題的全部解和全局最優解。因此，本文將啟發式算法中的粒子群算法，應用于測距定位方程的求解，該算法的核心思想為種群間個體的信息交互，從而使種群個體不斷優化得到問題的最優解[16]。粒子群算法具有高精度、高穩定性和全局搜索能力，計算過程中不需要進行線性化和矩陣求逆等復雜運算。圖4為應用粒子群算法對最優化問題求解的流程圖。

圖4 粒子群算法流程圖

由圖4可知，應用粒子群算法的關鍵步驟為適應度函數的建立，對粒子的適應度進行評價，使粒子不斷對自身進行優化，從而搜索到全局最優解。應用粒子群算法對待定點求解時，可將式（1）的測距定位方程轉化為最優化問題的求解，即

式中Fitness為粒子群算法求解測距定位方程的適應度函數。

式中：為慣性權重因子，是粒子的歷史信息對速度更新產生的影響；為自身認知參數，是粒子自身歷史最優值的權重系數；為社會認知參數，是粒子全局最優值的權重系數；為[0,1]區間的隨機數。由式（8）可知，粒子群算法的核心思想是群體信息的傳遞與共享，從而使粒子在限定范圍內搜索到問題的最優解，圖5為粒子群算法搜索最優解過程中，粒子的更新示意圖。

3 算例列舉

算例1。3維測距定位中，控制點近似共線時，待定點的求解出現不穩定的態勢，表現為產生多個參數解的情況。為驗證這一結論，隨機生成1000組近似共線的定位構型，對待定點坐標進行解算，控制點坐標范圍為：坐標分量為-2~2 m；坐標分量為-2~2 m；坐標分量為-100~100 m。每組實驗的控制點數目設置8個，觀測距離添加0.5 m的隨機誤差，待定點坐標模擬值為（50 m,0 m, 50 m）。采用粒子群算法對待定點進行求解，粒子在3個坐標分量的搜索范圍都為-100~100 m,移動速度范圍為-2~2 m。具體的解算結果如圖6和圖7所示。

圖6 控制點近似共線定位解分布

圖7 控制點近似共線定位解算結果

圖6和圖7為應用粒子群搜索算法，對隨機生成的1000組近似共線定位構型進行待定點坐標解算的結果，可知當控制點呈現近似共線分布時，待定點的解算結果分布在圍繞控制點的近似圓周之上，其原因為，當控制點為近似共線分布時，控制點與待定點之間的距離計算結果與觀測距離之差較小，從解算結果的殘差平方和中能證實此結論，此時進行待定點的解算時會出現多解現象。

算例2。3維測距定位中，控制點近似共面時，待定點的求解出現不穩定的態勢，表現為產生多個參數解的情況。為驗證這一結論，隨機生成1000組近似共面的定位構型控制點，對待定點坐標進行解算，控制點坐標范圍為：坐標分量為-10000~ 10000 m；坐標分量為-10000~10000 m，坐標分量為-100~100 m。每組實驗的控制點數目設置6個，觀測距離添加0.5 m的隨機誤差，待定點坐標模擬值為（50 m, 0 m, 50 m）。采用粒子群算法對定位點進行求解，粒子在3個坐標分量的搜索范圍都為-100~100 m,移動速度范圍為-5~5 m，具體的解算結果如圖8和圖9所示。

圖8 控制點近似共面定位解分布

圖9 控制點近似共面定位解算結果

如圖8和圖9可知，當控制點呈現近似共面分布時，待定點的解出現在待定點與控制點平面的垂直方向上，呈現線型分布，其原因為當控制點近似共面分布時，垂直方向上存在的偏差對距離計算的影響較小，從而與觀測距離之差較小，造成距離變化的不敏感而產生多解現象。

表1 控制點坐標和距離觀測值 單位：m

圖10 算例3的定位解分布

如圖10和圖11所示，當采用文獻[19]中控制點近似共線的測邊網算例對待定點坐標進行解算時，應用粒子群算法對待定點坐標進行1000次解算，可知當控制點近似共線時，待定點的解算結果產生多解現象呈現出近似圓形分布，與本文所得結論一致。

4 結束語

本文對控制點近似共線和控制點近似共面2類定位構性產生多解性現象的原因進行了探討，從圖形的角度進行多解現象的成因分析，發現控制點近似共線與近似共面分布時，造成多解的原因主要是由于控制點與待定點之間的距離計算結果與觀測距離之差較小，從而產生多個殘差平方和較小的解算結果而產生多解現象。

引入粒子群算法對測距定位方程進行解算，該算法相比于傳統迭代算法不需進行線性化處理，具有高精度、高穩定性和全局搜索能力。粒子群算法為解決復雜的非線性最優化提供了全新的思路，然而算法的性能與相關參數的設置密切相關，參數的合理設置以及與其它智能算法的融合，用以提升算法的性能將會是未來研究的主要內容。

[1] 楊元喜, 張麗萍. 中國大地測量數據處理60年重要進展第一部分:函數模型和隨機模型進展[J]. 地理空間信息, 2009, 7(6): 7-11.

[2] 楊元喜, 張麗萍. 中國大地測量數據處理60年重要進展第二部分:大地測量參數估計理論與方法的主要進展[J]. 地理空間信息, 2010, 8(1): 1-6.

[3] 孫振, 曲國慶, 蘇曉慶, 等.測距定位模型參數估計的Landweber迭代法[J]. 測繪科學, 2019, 44(4): 15-19.

[4] STEFANIA B, SERGE G, ELISA R. A Levenberg–Marquardt method for large nonlinear least-squares problems with dynamic accuracy in functions and gradients[J]. Numerische Mathematik, 2018, 49(140): 791–825.

[5] 曲國慶, 孫振, 蘇曉慶, 等. 非線性參數估計的自適應松弛正則化算法[J]. 武漢大學學報（信息科學版）, 2019, 44(10): 1491-1497.

[6] 劉國林, 姜巖, 陶華學, 等. 非線性最小二乘參數平差[J]. 測繪學報, 1998, 37(3): 224-230.

[7] 王新洲. 非線性模型線性近似的容許曲率[J]. 武漢測繪科技大學學報, 1999, 24(2): 29-31.

[8] BAO Jifeng, LI Chong, SHEN Weiping, et al. Approximate Gauss–Newton methods for solving underdetermined nonlinear least squares problems[J]. Applied Numerical Mathematics, 2017, 111: 92–110.

[9] WANG Chuanyang, YU Hang, WANG Jian, et al. Bias analysis of parameter estimator based on Gauss-Newton method applied to ultra-wideband positioning[J]. Applied Sciences, 2019, 10(1): 273.

[10] 齊珂, 曲國慶, 薛樹強, 等. 測距定位方程的多解性及其非線性最小二乘迭代算法[J]. 測繪通報, 2018(8): 37-40,46.

[11] TEUNISSEN P J G, KNICKMEYER E H. Nonlinearity and least-squares[J]. CISM Journal ACSGC, 1988, 42(4): 321-330．

[12] 李斐, 郝衛峰, 王文睿, 等. 非線性病態問題解算的擾動分析[J]. 測繪學報, 2011, 40(1): 9-13.

[13] AWANGE J L, GRAFAREND E W. Explicit solution of the overdetermined three-dimensional resection problem[J]. Journal of Geodesy, 2003, 76(11/12): 605-616.

[14] XUE S Q, YANG Y X, DANG Y M. A closed-form of Newton method for solving over-determined pseudo-distance equations[J]. Journal of Geodesy, 2014, 88(5): 441-448.

[15] 薛樹強, 楊元喜, 黨亞民. 測距定位方程非線性平差的封閉牛頓迭代公式[J]. 測繪學報, 2014, 43(8): 771-777.

[16] XIA Xuewen, XING Ying, WEI Bo, et al. A fitness-based multi-role particle swarm optimization[J]. Swarm and Evolutionary Computation, 2019, 44: 349-364.

[17] 歸慶明, 張建軍. 壓縮型抗差估計[J]. 測繪學報, 2000, 29(3): 224-228.

Multiple solutions of distance equations and particle swarm optimization algorithm

YANG Wenlong1,2, XUE Shuqiang2, QU Guoqing1,2, WANG Xinpu1,2, WANG Guanyu1

（1. Shandong University of Technology, Zibo, Shandong 255000, China;2. Chinese Academy of Surveying and Mapping, Beijing 100036）

In view of the instability and low reliability of the traditional method to solve the nonlinear distance equation, the particle swarm optimization(PSO) algorithm is used to solve the distcace equation. The performance of particle swarm optimization is verified by simulation and practical examples. The results show that PSO can search multiple candidate solutions accurately and efficiently compared with the traditional method. It has a certain practical value for further combining the actual situation or introducing constraints to obtain the final solution of the problem.

distance observation; non-linear models; ill-conditioned equation; multiple solutions；particle swarm optimization

P228

A

2095-4999(2020)03-0121-06

楊文龍，薛樹強，曲國慶，等. 測距定位方程的多解性及粒子群搜索算法[J]. 導航定位學報, 2020, 8(3): 121-126.（YANG Wenlong, XUE Shuqiang, QU Guoqing, et al. Multiple solutions of distance equations and particle swarm optimization algorithm[J]. Journal of Navigation and Positioning, 2020, 8(3): 121-126.）

10.16547/j.cnki.10-1096.20200320.

2020-03-02

國家自然科學基金資助項目（41674014，41931076）；國家重點研發計劃項目（2016YFB0501700）。

楊文龍（1995—），男，天津人，碩士研究生，研究方向為GNSS數據處理與應用。

曲國慶（1962—），男，山東萊陽人，博士，教授，研究方向為測量數據處理理論與方法。