王躍鋼，王 樂(lè)，騰紅磊，張兆龍

（火箭軍工程大學(xué) 304教研室，西安 710025）

基于改進(jìn)人工魚(yú)群算法的DGPS整周模糊度快速固定

王躍鋼，王 樂(lè)，騰紅磊，張兆龍

（火箭軍工程大學(xué) 304教研室，西安 710025）

為提高DGPS整周模糊度的搜索效率，將改進(jìn)人工魚(yú)群算法引入模糊度固定解搜索環(huán)節(jié)。在解算中首先根據(jù)GPS雙差載波相位觀測(cè)方程，利用卡爾曼濾波估計(jì)模糊度浮點(diǎn)解，針對(duì)短基線解算問(wèn)題，以基線長(zhǎng)度為約束確定模糊度搜索范圍，進(jìn)而采用LLL降相關(guān)算法對(duì)模糊度浮點(diǎn)解作降相關(guān)處理，最后利用附加整數(shù)約束的改進(jìn)人工魚(yú)群算法搜索整周模糊度固定解。算例分析結(jié)果表明，在與遺傳算法的100次對(duì)比實(shí)驗(yàn)中，改進(jìn)人工魚(yú)群算法搜索平均用時(shí)1.6617 s，比遺傳算法縮短2.4987 s，算法搜索速度更快，搜索效率明顯提高。算法的模糊度搜索成功率為 92%，高出遺傳算法 9%，搜索成功率得到有效提升。因此，與遺傳算法相比，改進(jìn)人工魚(yú)群算法能夠更為快速地得到整周模糊度固定解，且具有更高的搜索效率和成功率。

DGPS；整周模糊度；LLL降相關(guān)算法；改進(jìn)人工魚(yú)群算法

航空重力測(cè)量的一項(xiàng)重要內(nèi)容是利用DGPS技術(shù)高精度解算載體加速度，在采用雙差載波相位觀測(cè)量時(shí)，整周模糊度的快速固定是關(guān)鍵[1]。通常模糊度的解算按如下步驟進(jìn)行：首先得到忽略整數(shù)約束的模糊度浮點(diǎn)解及其協(xié)方差矩陣，構(gòu)造搜索空間；進(jìn)而針對(duì)浮點(diǎn)解間的相關(guān)性問(wèn)題，對(duì)浮點(diǎn)解作降相關(guān)處理；最后運(yùn)用搜索算法搜尋得到整周模糊度固定解[2-4]。近年來(lái)，國(guó)內(nèi)外學(xué)者積極探索模糊度解算方法，在改善病態(tài)性、改進(jìn)降相關(guān)效果、提高搜索效率等方面展開(kāi)研究[5-8]，特別是在搜索算法方面采用了現(xiàn)代啟發(fā)式算法，如遺傳算法、蟻群算法和粒子群算法等[9-11]。為進(jìn)一步提高搜索效率，本文將采用改進(jìn)人工魚(yú)群算法搜索模糊度固定解。

人工魚(yú)群算法（Artificial Fish Swarm Algorithm,AFSA）是李曉磊提出的一種現(xiàn)代啟發(fā)式尋優(yōu)算法，用于解決組合優(yōu)化問(wèn)題。該算法的基本原理是通過(guò)構(gòu)造人工魚(yú)模擬魚(yú)的覓食、聚群和追尾行為，從單條魚(yú)的基本行為開(kāi)始，通過(guò)魚(yú)群中各個(gè)體的局部尋優(yōu)，達(dá)到全局最優(yōu)值在群體中凸顯的目的，具有并行、高效和較強(qiáng)的取得全局最優(yōu)解的能力[12-13]。

本文針對(duì)DGPS整周模糊度的快速固定問(wèn)題，將人工魚(yú)群算法引入整周模糊度的搜索環(huán)節(jié)，并針對(duì)問(wèn)題特性對(duì)人工魚(yú)群算法作整數(shù)約束改進(jìn)，在提高搜索效率的同時(shí)保證了算法的收斂性和有效性。

1 卡爾曼濾波濾波估計(jì)模糊度浮點(diǎn)解

在DGPS定位技術(shù)中，參考站i、j(GPS雙頻接收機(jī))相對(duì)于衛(wèi)星k、l的GPS雙差載波相位L1和L2波段觀測(cè)方程為[14]

式中：1Φ、2Φ分別表示L1和L2波段載波相位偽距觀測(cè)量；ρ表示接收機(jī)與衛(wèi)星間的歐氏距離；、分別表示L1和L2波段的電離層延遲；T表示對(duì)流層延遲；λ為載波波長(zhǎng)；N為整周模糊度；ε為觀測(cè)噪聲。

參考站的坐標(biāo)精確已知，通過(guò)卡爾曼濾波可實(shí)時(shí)估計(jì)基線向量、對(duì)流層延遲、電離層延遲和載波相位模糊度實(shí)數(shù)解。卡爾曼濾波模型表示為

式中：Xk為狀態(tài)向量；kΦ為一步轉(zhuǎn)移矩陣；Lk為觀測(cè)向量；Hk為量測(cè)矩陣；Wk、Vk分別為狀態(tài)噪聲和量測(cè)噪聲；Qk、Rk分別是其相應(yīng)的協(xié)方差陣。

整周模糊度的固定解N并不能簡(jiǎn)單地通過(guò)在浮點(diǎn)解?N附近取整數(shù)值得到，需要由上述浮點(diǎn)解根據(jù)一定準(zhǔn)則通過(guò)整數(shù)約束搜索得到，因此，可通過(guò)使下面二次型目標(biāo)函數(shù)最小來(lái)求解整周模糊度的固定解：

為解算式(4)，需首先確定一個(gè)整數(shù)向量集合，然后從中根據(jù)目標(biāo)函數(shù)最小原則搜索出整周模糊度的固定解。該整數(shù)向量集合即為整周模糊度的搜索空間。在DGPS短基線定位應(yīng)用中，采用基線長(zhǎng)度作為約束條件，構(gòu)造搜索空間如下：

2 LLL模糊度降相關(guān)算法

首先對(duì)協(xié)方差陣Q?N進(jìn)行Cholesky分解，即Q?N=，其中的行向量記為。對(duì)進(jìn)行整數(shù)Gram-Schmidt正交變換：

式中：

3 改進(jìn)人工魚(yú)群算法求解整周模糊度

為了更快速準(zhǔn)確地求解目標(biāo)函數(shù)(4)的最小值，進(jìn)而正確固定整周模糊度，引入人工魚(yú)群算法解決該問(wèn)題。算法基本定義如下：

人工魚(yú)i和j的間距表示為

算法執(zhí)行過(guò)程中，人工魚(yú)在水中隨機(jī)游動(dòng)，通過(guò)感知能力確定水中的食物濃度，并實(shí)施覓食、聚群和追尾行為，用公告板記錄最優(yōu)魚(yú)的狀態(tài)，通過(guò)算法迭代中狀態(tài)的不斷更新實(shí)現(xiàn)尋優(yōu)。對(duì)于模糊度固定解搜索問(wèn)題，由于模糊度搜索空間屬于整數(shù)域，需要對(duì)人工魚(yú)群算法作整數(shù)約束改進(jìn)，改進(jìn)后人工魚(yú)執(zhí)行覓食行為的一步狀態(tài)轉(zhuǎn)移方程表示為

式中：Xi表示人工魚(yú)當(dāng)前狀態(tài)；Xj表示感知范圍內(nèi)的另一狀態(tài)；［·］表示取整算子；rand表示［0,1 ］內(nèi)隨機(jī)數(shù)。聚群和追尾行為的一步狀態(tài)轉(zhuǎn)移方程與式(11)類似，不作贅述。

圖1 改進(jìn)人工魚(yú)群算法流程圖Fig.1 Flowchart of the improved artificial fish swarm algorithm

鑒于以上算法定義與行為描述，將搜索整周模糊度的改進(jìn)人工魚(yú)群算法流程描述如圖1所示。

4 仿真實(shí)驗(yàn)與分析

采用本文提出的方法對(duì)DGPS整周模糊度進(jìn)行快速固定的處理流程如圖2所示。

圖2 基于IFASA快速固定DGPS整周模糊度流程圖Fig.2 Flowchart of fast fixing the DGPS integer ambiguity based on the improved artificial fish swarm algorithm

為驗(yàn)證該方法的有效性，采用文獻(xiàn)[2]中的經(jīng)典算例進(jìn)行仿真驗(yàn)證，選取模糊度浮點(diǎn)解及其協(xié)方差矩陣為

從上述協(xié)方差矩陣可以看出，各個(gè)維度上的模糊度間具有較強(qiáng)的相關(guān)性，將嚴(yán)重影響搜索效率，并可能導(dǎo)致搜索失敗。因此本文采用LLL降相關(guān)算法對(duì)協(xié)方差陣進(jìn)行處理，降相關(guān)后的浮點(diǎn)解及其協(xié)方差陣為：

可見(jiàn)，與原始協(xié)方差陣相比，降相關(guān)后的協(xié)方差陣更接近對(duì)角陣，說(shuō)明降相關(guān)的過(guò)程使各維模糊度間的相關(guān)性明顯降低，從而使對(duì)應(yīng)的食物濃度函數(shù)的函數(shù)特性也發(fā)生了變化。

圖3反映了降相關(guān)前后食物濃度函數(shù)值在三維整周模糊度空間中的變化。圖3中顏色的變化代表食物濃度函數(shù)值的變化，由于算例中的食物濃度函數(shù)是超維函數(shù)，難以在三維空間中直觀觀察其變化程度，為方便研究，分別取三維模糊度中任意兩維模糊度對(duì)降相關(guān)前后食物濃度函數(shù)的分布情況進(jìn)行研究，如圖4所示。

圖3 降相關(guān)前后食物濃度函數(shù)Fig.3 FC functions before and after decorrelation

圖4 降相關(guān)前后兩兩模糊度間的食物濃度函數(shù)Fig.4 Food concentration functions of two ambiguities before and after decorrelation

由圖3、圖4可以看出，相對(duì)于原食物濃度函數(shù)存在多個(gè)局部極值點(diǎn)的情況，降相關(guān)后的食物濃度函數(shù)僅有一個(gè)最優(yōu)解對(duì)應(yīng)著整周模糊度固定解，能夠避免人工魚(yú)群算法陷入局部最優(yōu)解，有助于提高算法的效率和搜索正確率，使搜索過(guò)程快速收斂到全局最優(yōu)解。

采用本文提出的改進(jìn)人工魚(yú)群算法在降相關(guān)后搜索空間中搜索整周模糊度固定解，算法的參數(shù)設(shè)置為：魚(yú)群規(guī)模，迭代次數(shù)，人工魚(yú)每次移動(dòng)的最大試探次數(shù)，人工魚(yú)的感知距離，擁擠度因子 δ= 0.618，人工魚(yú)移動(dòng)的最大步長(zhǎng)step=2。為檢驗(yàn)算法性能，分別采用本文算法和遺傳算法在相同條件下分別進(jìn)行了100次仿真實(shí)驗(yàn)，遺傳算法的種群大小設(shè)為50，最大進(jìn)化代數(shù)設(shè)為 100。實(shí)驗(yàn)結(jié)果表明，利用改進(jìn)人工魚(yú)群算法，有 92次得到全局最優(yōu)解，搜索正確率為92%，高于遺傳算法83%的搜索正確率。算法具有更高的搜索可靠性，這也反映出改進(jìn)人工魚(yú)群算法更好地解決了全局搜索和局部搜索的問(wèn)題，在搜索中更易跳出局部極值。進(jìn)一步對(duì)比改進(jìn)人工魚(yú)群算法和遺傳算法在100次實(shí)驗(yàn)中收斂到最優(yōu)解的收斂代數(shù)，如圖5所示。

圖5 兩種算法收斂代數(shù)對(duì)比Fig.5 Comparison on two algorithms for convergence algebra

由圖5可知，人工魚(yú)群算法可以比遺傳算法更快地收斂到全局最優(yōu)解，采用人工魚(yú)群算法，平均收斂代數(shù)為18.45，按四舍五入取整，算法平均在搜索18代后收斂，則搜索的空間為900（18× 50），占問(wèn)題空間（ 213）的9.72%，算法搜索平均用時(shí)1.6617 s；遺傳算法的平均收斂代數(shù)為 33.7，搜索的空間為 1700（34× 50），占問(wèn)題空間（ 213）的 18.36%，算法搜索平均用時(shí)4.1604 s。實(shí)驗(yàn)結(jié)果表明，與遺傳算法相比，人工魚(yú)群算法具有更高的搜索效率。

圖6和表1給出了整周模糊度一次解算中食物濃度函數(shù)Y的變化過(guò)程。

綜合圖6、圖7和表1可以看出，在人工魚(yú)群算法的一次解算中，魚(yú)群在迭代11次后收斂到了全局最優(yōu)解，收斂速度較快，且收斂后食物濃度函數(shù)值未再發(fā)生波動(dòng)，穩(wěn)定性較高，隨著迭代次數(shù)的增加，魚(yú)群逐漸靠攏到全局最優(yōu)解附近。這也說(shuō)明算法達(dá)到了全局尋優(yōu)的目的，并且更加高效、可靠。

圖7給出了迭代前后魚(yú)群的空間分布情況。

圖6 迭代過(guò)程中食物濃度值的變化Fig.6 Changes of food concentration in iterative process

表1 迭代過(guò)程中最優(yōu)解的演變Tab.1 Changes of optimal solution in iterative process

圖7 魚(yú)群空間分布變化Fig.7 Spatial distribution of fish swarm

5 結(jié) 論

本文將改進(jìn)人工魚(yú)群算法引入DGPS整周模糊度的解算問(wèn)題。在降相關(guān)的基礎(chǔ)上，通過(guò)人工魚(yú)群算法改善搜索性能，提高搜索效率和成功率，達(dá)到更快速、準(zhǔn)確地解算整周模糊度的目的。通過(guò)算例分析可知，與遺傳算法相比，本文算法的搜索成功率優(yōu)于遺傳算法，且搜索效率高，耗時(shí)短。

然而，關(guān)于這種方法還有許多問(wèn)題值得進(jìn)一步探討與研究，如研究通過(guò)自適應(yīng)調(diào)整算法參數(shù)提高搜索效率，通過(guò)約束方程進(jìn)一步縮小算法初始搜索范圍，進(jìn)一步提高算法搜索全局最優(yōu)解能力提高成功率等等，這些都是可以再深入研究的課題。

（References）：

[1]Xu Ying, Ji Shengyue, Chen Wu. A new ionosphere-free ambiguity resolution method forlong-range baseline with GNSS triple-frequency signals[J]. Advances in Space Research, 2015, 56: 1600-1612.

[2]de Jorge P, Tiberius C. The LAMBDA method for integer ambiguity estimation: implementation aspects[R]. Delft:Delft University of Technology, 1996.

[3]Li Bo-feng, Verhagen S, Teunissen P J G. GNSS integer ambiguity estimation and evaluation: LAMBDA and Ps-LAMBDA[C]//2013 Proceedings of China Satellite Navigation Conference. Wuhan, China, 2013: 291-301.

[4] 李豹, 許江寧, 曹可勁, 等. 改進(jìn) LAMBDA 算法實(shí)現(xiàn)單頻 GPS 整周模糊度快速解算[J]. 中國(guó)慣性技術(shù)學(xué)報(bào), 2013, 21(3): 365-368.Li Bao, Xu Jiang-ning, Cao Ke-jin, et al. Fast resolution of single frequency GPS integer ambiguity realized by improved LAMBDA algorithm[J]. Journal of Chinese Inertial Technology, 2013, 21(3): 365-368.

[5]段榮, 趙修斌, 龐春雷, 等. GPS快速定位中相位模糊度動(dòng)態(tài)解算的一種正則化方法[J]. 中國(guó)慣性技術(shù)學(xué)報(bào).2015, 23(5): 624-630.Duan Rong, Zhao Xiu-bin, Pang Chun-lei, et al. Regularization approach for dynamic resolution of phase integer ambiguity in GPS rapid positioning[J]. Journal of Chinese Inertial Technology, 2015, 23(5): 624-630.

[6]鄧健, 王勝利, 陳潤(rùn)靜. GNSS網(wǎng)絡(luò)實(shí)時(shí)動(dòng)態(tài)模糊度解算病態(tài)性解決策略[J]. 中國(guó)慣性技術(shù)學(xué)報(bào), 2016, 24(1):14-19.Deng Jian, Wang Sheng-li, Chen Run-jing. Resolving strategies for ill-posed equation in ambiguity resolution of GNSS network real-time kinematics[J]. Journal of Chinese Inertial Technology, 2016, 24(1): 14-19.

[7]范龍, 翟國(guó)君, 柴洪洲. 模糊度降相關(guān)的整數(shù)分塊正交化算法[J]. 測(cè)繪學(xué)報(bào), 2014, 43(8): 818-826.Fan Long, Zhai Guo-jun, Chai Hong-zhou. Ambiguity decorrelation with integer block orthogonalization algorithm[J]. Acta Geodaetica et Catographica Sinca, 2014,43(8): 818-826.

[8]王勝利, 王慶, 潘樹(shù)國(guó), 等. 基于抗差估計(jì)的網(wǎng)絡(luò)RTK基站雙差模糊度檢驗(yàn)與修正方法[J]. 中國(guó)慣性技術(shù)學(xué)報(bào), 2012, 20(6): 705-714.Wang Sheng-li, Wang Qing, Pan Shu-guo, et al. Double integer ambiguities test and repair method for network RTK base stations based on robust estimation[J]. Journal of Chinese Inertial Technology, 2012, 20(6): 705-714.

[9]徐定杰, 劉明凱, 沈鋒, 等. 基于自適應(yīng)遺傳算法的DGPS整周模糊度快速解算[J]. 航空學(xué)報(bào), 2013, 34(2):371-377.Xu Ding-jie, Liu Ming-kai, Shen Feng, et al. Fast DGPS integer ambiguity resolution using adaptive genetic algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2013,34(2): 371-377.

[10]S Jazaeria, A R Amiri-Simkooeib, M A Sharifia. Fast GNSS ambiguity resolution by ant colony optimisation[J].Survey Review, 2013, 330(45): 190-196.

[11]Skvortsov A N. Estimation of rotation ambiguity in multivariate curve resolution with charged particle swarm optimization[J]. Journal of Chemometrics, 2014, 28(10): 727-739.

[12]王庭軍, 高延濱, 李光春. 利用人工魚(yú)群算法對(duì)光纖陀螺隨機(jī)漂移建模[J]. 中國(guó)慣性技術(shù)學(xué)報(bào), 2012, 20(3):358-362.Wang Ting-jun, Gao Yan-bin, Li Guang-chun. FOG random drift modeling by artificial fish swarm algorithm[J]. Journal of Chinese Inertial Technology, 2012, 20(3): 358-362.

[13]Peng Yong. An improved artificial fish swarm algorithm for optimal operation of cascade reservoirs[J]. Journal of Computer, 2011, 6(4): 740-746.

[14]Chang-Ki Hong, Chi Ho Park, Joong-hee Han, et al.Medium to long range kinematic GPS positioning with position-velocity-acceleration model using multiple reference stations[J]. Sensors, 2015, 15: 16895-16909.

DGPS integer ambiguity fast fixation based on improved artificial fish swarm algorithm

WANG Yue-gang, WANG Le, TENG Hong-lei, ZHANG Zhao-long
(Unit 304, Rocket Force University of Engineering, Xi’an 710025, China)

In order to improve the search efficiency of DGPS integer ambiguity, an improved artificial fish swarm algorithm (IAFSA) is introduced into the search of the integer ambiguity. Firstly, according to the DD GPS carrier phase observation equation, a Kalman filter is used to estimate the ambiguity floating-point solution. For the solution problem of short baseline, the range of ambiguity is determined with the constraint of baseline length. Then the LLL algorithm is used into the ambiguity decorrelation problem. Finally, the IAFSA with integer constraints is used to search the fixed solutions of integer ambiguity. The results of an example show that the average searching time of IAFSA is 1.6617 s, which is 2.4987 s shorter than that of the genetic algorithm(GA) in 100 experiments. The success rate of ambiguity search is 92%, which is 9% higher than that of the GA, showing that the IAFSA can get the fixed ambiguity solution more quickly, and has higher search efficiency and reliability.

DGPS; integer ambiguity; LLL decorrelation algorithm; improved artificial fish swarm algorithm

P228.4

A

1005-6734(2016)05-0619-05

10.13695/j.cnki.12-1222/o3.2016.05.011

2016-07-28；

2016-09-20

國(guó)防預(yù)研（403050202）

王躍鋼（1958—），男，教授，博士生導(dǎo)師。E-mail: wangyueg@163.com