基于人工魚群算法的整周模糊度解算算法*

劉書剛 張亞晶

(華北電力大學計算機系 保定 071003)

?

基于人工魚群算法的整周模糊度解算算法*

劉書剛 張亞晶

(華北電力大學計算機系 保定 071003)

整周模糊度解算是基于全球衛(wèi)星導航系統(tǒng)定位解算中的關鍵問題。在模糊度解算過程中存在搜索速度慢的問題。針對這一問題，論文利用人工魚群算法的全局尋優(yōu)的特性，將該算法引入整周模糊度的快速解算中。論文首先分析了衛(wèi)星定位系統(tǒng)的雙差載波相位測量模型并利用加權最小二乘估計解算出模糊度浮點解；然后利用升序排序的逆整Cholesky算法降低模糊度浮點解及其協(xié)方差矩陣的相關性；最后運用人工魚群算法進行模糊度搜索。由于模糊度的整數(shù)特性，在搜索中利用舍入算法對人工魚群算法進行改進。運用實例進行仿真實驗得到較好結(jié)果。并與利用自適應遺傳算法的模糊度解算結(jié)果進行比較，結(jié)果表明人工魚群算法用于模糊度解算可以得到精確的模糊度解，并且解算時間優(yōu)于遺傳算法的解算時間。

全球定位系統(tǒng); 整周模糊度; 人工魚群算法

Class Number P228.41

1 引言

在GPS載波相位精密定位中，整周模糊度的求解是其中的關鍵問題。其中LAMBDA[1～3](最小二乘模糊度降相關平差)是目前應用最為廣泛的模糊度求解算法。LAMBDA求解整周模糊度分為兩步，首先，對由模糊度雙差模型求得的模糊度浮點解及其相應的模糊度方差-協(xié)方差矩陣進行降相關操作(主要包括整數(shù)高斯變換、逆整形Cholesky分解、LLL規(guī)約等)。隨后，在以模糊度浮點解為中心的橢球區(qū)域內(nèi)搜索模糊度最優(yōu)解。由于其搜索過程需遍歷搜索空間中所有的候選點，這樣大大增加了搜索的開銷，延長了搜索時間。因此，具有全局尋優(yōu)特點的人工智能算法對模糊度的搜索尋優(yōu)更加有利。

在人工智能領域中，遺傳算法[4]與蟻群算法[5]等均具有全局尋優(yōu)的能力。鄭慶暉等[6]提出了一種基于簡單遺傳算法的改進整周模糊的搜索方法，大大提高了搜索效率。徐定杰等[7]提出里一種基于自適應遺傳算法的整周模糊度解算算法。人工魚群算法[8～10]是群智能領域中的一個重要算法，具有較好的全局優(yōu)化能力，當個體數(shù)增加時，其收斂速度提高。相比于遺傳算法存在的早熟收斂的缺陷，人工魚群算法特有隨機行為機制避免了在搜索過程中陷入局部最優(yōu)而無法跳出的問題。本文采用人工魚群算法來進行整周模糊度的搜索。并且根據(jù)模糊度的整數(shù)特性將人工魚群算法進行了改進。

2 載波相位模型分析

2.1 模糊度最小二乘估計模型

衛(wèi)星精確定位中，由于載波相位差分測量[11～12]定位在進行雙差操作時可以減小電離層、對流層、衛(wèi)星鐘差等誤差，因此被廣泛應用于衛(wèi)星精密定位中。假設接收機1、2在t時刻對兩個衛(wèi)星j、k進行觀測，雙差定為模型可表示為

(1)

其中Φ表示t時刻兩接收機與兩衛(wèi)星的雙差觀測量；N表示接收機r與衛(wèi)星s之間的載波相位整周模糊度；ρ表示接收機r與衛(wèi)星s之間的距離；ddε表示雙差觀測噪聲；λ為GPS載波波長。將載波相位的雙差模型線性化，其數(shù)學模型表示為

V=Aa+Bb+ε

(2)

其中V是載波相位觀測值，a是整周模糊度向量，b是兩基站之間基線向量，A，B均為設計矩陣，ε為觀測誤差向量。式(2)中有兩個未知向量整周模糊度向量a與基線向量b。式(2)中未知參數(shù)a與b的確定可以用最小二乘的參數(shù)估計[13～14]求解，因此式(2)實質(zhì)上是最小二乘解求解問題。

(3)

式中Nr是載波相位方差協(xié)方差矩陣。

(4)

2.2 模糊度降相關

通過最小二乘估計獲得的模糊度浮點值及其方差-協(xié)方差矩陣具有較高的相關性，在整數(shù)模糊度搜索過程中，這會影響搜索速率，降低模糊度的搜索效率。因此，在進行模糊度搜索前，應進行模糊度降相關操作。常用的降相關算法[15]有：整數(shù)高斯變換[16]、逆整數(shù)Cholesky算法[17]、LLL算法[18]等。李志平等[19]對上述三種模糊度降相關算法進行了評價，并提出對于小于20維低維方差-協(xié)方差矩陣基于升序排列的逆整Cholesky算法具有較好的降相關效果。由于GPS動態(tài)定位中，模糊度方差陣的維數(shù)一般在5～10維左右，因此本文采用基于升序排列的逆整數(shù)Cholesky算法進行模糊度降相關。升序排列的逆整數(shù)Cholesky算法，對模糊度協(xié)方差矩陣進行LDLT分解后的對角矩陣按對角線升序排列后，再進行整數(shù)Z變換。

2.3 搜索空間確定

在GPS短基線測量定位中，模糊度搜索空間的確定主要的約束條件是基線長度。假設基線長度為m，以模糊度浮點解為中心的整周模糊度a的取值范圍為

-m/λ≤a≤m/λ

(5)

其中λ為GPS載波波長，取值為0.19m。本文采用的基線長度為2m。因此本文中搜索空間范圍為

-10.5≤a≤10.5

(6)

3 人工魚群算法模糊度搜索

模糊度搜索實質(zhì)上是在搜索空間中找的式(4)的最小值。為了減少模糊度的搜索次數(shù)，提高模糊度的搜索效率，本文引入人工魚群算法進行模糊度搜索。人工魚群算法是借鑒自然界中魚群趨向食物豐富方向而產(chǎn)生的覓食、追尾、聚群等行為進行優(yōu)化操作的一種群智能算法。隨著迭代次數(shù)的增加，人工魚群會逐步游向食物濃度更高的區(qū)域，并聚集在這個區(qū)域。本文提出了改進的人工魚群算法，利用取整操作保證人工魚個體中每個變量的整數(shù)特性。

3.1 初始化

人工魚群算法的目標函數(shù)為式(4)，如圖1所示，由于人工魚群算法在較為平坦的范圍，搜索效率較低，且容易陷入局部最優(yōu)。因此本文采用文獻[2]中的適應度函數(shù)作為目標函數(shù)進行整數(shù)模糊度搜索，如圖2所示。式(7)為修改后的目標函數(shù)

f(a)=b-log(J(a))

(7)

3.2 行為選擇

在本次魚群算法的目標函數(shù)為式(7)，即求最大值問題。因此在行為選擇中，首先對追尾行為和聚群行為進行模擬，對其行為執(zhí)行后所在位置的食物濃度進行比較選擇其中食物濃度較大的行為并執(zhí)行。對每個狀態(tài)的評價如下：

1) 隨機行為(AF-rand)：當人工魚個體通過其他行為判斷搜索不到較優(yōu)狀態(tài)時，該個體隨機選擇一個狀態(tài)作為下一狀態(tài)移動一步。其數(shù)學表達式為

(8)

2) 覓食行為(AF-preying)：人工魚個體隨機選擇一個狀態(tài)，與當前狀態(tài)的食物濃度進行比較。若該狀態(tài)食物濃度較大，則移動一步；否則，重新選擇下一狀態(tài)，直到試探達到最大次數(shù)，則執(zhí)行隨機行為。其數(shù)學表達式為

(9)

3) 追尾行為(AF-fllow)：人工魚個體對其感知范圍內(nèi)的所有伙伴進行判斷，找出所在位置的食物濃度最高的伙伴位置，并與自己當前位置的食物濃度比較。若該位置食物濃度大，則向著該伙伴的方向移動一部。反之，則執(zhí)行覓食行為。

(10)

4) 聚群行為(AF-swam)：人工魚個體Xi探索其感知范圍內(nèi)的伙伴數(shù)目nf及中心位置Xc，若Yc/nf>δYi(δ為擁堵因子)，則向Xc方向移動一步。否則，執(zhí)行覓食行為。

(11)

3.3 結(jié)果評價

在本文中的求最大值問題，因此采用當人工魚群算法達到最大迭代次數(shù)時，公告板中所記錄的最大食物濃度即為所求模糊度整數(shù)解。

4 數(shù)值實驗分析

文獻[2]中采用簡單遺傳算法進行模糊度搜索，與LAMBDA算法相比具有較高的搜索效率。文獻[3]中采用自適應遺傳算法進行模糊度求解，并與簡單遺傳算法、LAMBDA的模糊度求解相比較，證明了自適應的遺傳算法具有較高的模糊度搜索效率，并且在相同的搜索精度下，自適應遺傳算法的搜索時間遠小于LAMBDA的搜索時間。因此本文仿真試驗中主要通過自適應遺傳算法與人工魚群算法的搜索效率比較來驗證本文算法的性能。

對人工魚群算法的模糊度搜索進行仿真，本文采用文獻[3]中的模糊度解算例子，模糊度浮點解和模糊度方差為

利用升序排列的逆整數(shù)Cholesky降相關算法操作后的模糊度浮點解和模糊度方差為

降相關前后的目標函數(shù)圖像如圖2和圖1所示，通過比較可以看出，通過降相關操作，避免了搜索過程中陷入局部最優(yōu)。

圖1 降相關后目標函數(shù)圖像

為方便將人工魚群算法和自適應遺傳算法進行比較，本次試驗中人工魚群算法與自適應遺傳算法的種群個數(shù)與迭代次數(shù)分別為50、200。如圖3、圖4所示為兩種算法隨迭代次數(shù)的增加其最優(yōu)值得變化情況。從圖中可以看出，人工魚群算法在80代以內(nèi)就可獲得最優(yōu)解，而自適應遺傳算法在120代以后達到最優(yōu)解。這是因為隨著迭代次數(shù)增加，自適應遺傳算法的種群多樣性降低，容易陷入早熟收斂，而人工魚群算法的覓食、追尾和聚群等行為使算法快速收斂，隨機行為又使算法可以跳出局部最優(yōu)，從而達到全局最優(yōu)。

圖2 降相關前目標函數(shù)圖像

圖3 人工魚群算法

圖4 自適應遺傳算法

利用自適應遺傳算法和人工魚群算法對初始整周模糊度解算結(jié)果與時間的比較見表1。從表1中可以看出人工魚群算法與自適應遺傳算法對整周模糊度的解算都可以達到較為理想的結(jié)果，但AFSA的解算時間遠優(yōu)于自適應遺傳算法，文獻[3]中將LAMBDA算法與自適應遺傳算法以相同的模糊度浮點解與方差陣實例進行了初始模糊度解算，并比較解算結(jié)果與時間效率。文獻[5]中的結(jié)果表明，LAMBDA以自適應遺傳算法均能解得精確的模糊度解，但自適應遺傳算法的解算時間遠小于LAMBDA算法?；谝陨辖Y(jié)論，可以得出人工魚群算法的解算效率高于自適應遺傳算法與LAMBDA算法。

表1 AFSA與AGA模糊度解算值與時間比較

5 結(jié)語

本文分析了GPS載波相位雙差定位模型，并針對整周模糊度求解問題，引入了人工魚群算法。經(jīng)過數(shù)值實驗可以證明，人工魚群算法應用于解算整周模糊度，在數(shù)值精度上與自適應遺傳算法一致，但其搜索時間優(yōu)于自適應遺傳算法。因此，人工魚群算法應用于整周模糊度的解算具有較高的魯棒性和解算效率，具有很高的使用價值。

[1] P.J.G. Teunissen. The least-square ambiguity decorrelation adjustment: a method for fast GPS integer ambiguity estimation[J]. Journal of Geodesy,1995,70:65-82.

[2] Wang B, Miao L, Wang S, et al. A constrained LAMBDA method for GPS attitude determination[J]. GPS solutions,2009,13(2):97-107.

[3] 趙毅,王慶,高成發(fā),等.整周模糊度估計的LAMBDA算法中搜索空間研究[J].艦船電子工程,2007,27(6):79-81. ZHAO Yi, WANG Qing, GAO Chengfa, et al. Research on the Ellipsoidal Region of LAMBDA Method For Integer Ambiguity Estimation[J].Ship Electronic Engineering,2007,27(6):79-81.

[4] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi objective genetic algorithm: NSGA-II[J]. Evolutionary Computation, IEEE Transactions on,2002,6(2):182-197.

[5] Dorigo M, Gambardella L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. Evolutionary Computation, IEEE Transactions on,1997,1(1):53-66.[6] 鄭慶暉,張育林.基于遺傳算法的整周模糊度OTF解算[J].國防科技大學學報,2001,23(3):12-19. ZHENG Qinghui, ZHANG Yulin. OTF Ambiguity Resolution Based on Genetic Algorithm[J]. Journal of National Univesity of Defense Technology,2001,23(3):12-19.

[7] 徐定杰,劉明凱,沈鋒,等.基于自適應遺傳算法的DGPS整周模糊度快速解算[J].航空學報,2013,34(2):371-378. XU Dingjie, LIU Mingkai, SHEN Feng, et al. Fast DGPS Integer Ambiguity Resolution Using Adaptive Genetic Algorithm[J],Acta Aeronautica et Astronatica Sinica,2013,34(2):371-378.

[8] 李曉磊.一種新型的智能優(yōu)化方法——人工魚群算法[D].杭州:浙江大學,2003. LI Xiaolei. A New Intelligent Optimization Method-Artificial Fish School Algorithm[M]. Hangzhou: Zhejiang University,2003.

[9] 黃華娟,周永權.求解全局優(yōu)化問題的混合人工魚群算法[J].計算機應用,2008,28(12):3062-3066. HUANG Huajuan, ZHOU Yongquan. Hybrid artificial fish swarm algorithm for global optimization problems[J]. Computer Applications,2008,28(12):3062-3066.

[10] 洪興福,胡祥濤.一種求解復雜優(yōu)化問題的新型人工魚群算法[J].計算機工程與應用,2015,51(14):40-46. HONG Xingfu, HU Xiangtao. Novel artificial fish-swarm algorithm for solving complex optimization problem[J]. Computer Engineering and Applications,2015,51(14):40-46.

[11] 王廣運.載波相位差分GPS定位技術[J].測繪工程,1999,8(1):12-17. WANG Guangyun. DGPS Positioning Using Carrier Phase Measurement[J]. Engineering of Surveying and Mapping,1999,8(1):12-17.

[12] 徐周.GPS差分定位技術及實現(xiàn)方法的研究[D].鄭州:解放軍信息工程大學,2006. XU Zhou. A Study of GPS Differential Positioning Technology and Realization Method[D]. Zhengzhou: A Dissertation Submitted to the Information Engineering University,2006.

[13] 邱衛(wèi)寧,齊公玉,田豐瑞,等.整體最小二乘求解線性模型的改進算法[J].武漢大學學報:信息科學版,2010,35(6):708-710. QIU Weining, QI Gongyu, TIAN Fengrui, et al. An Improved Algorithm of Total Least Squares for Linear Models[J].Geomatics and Information Science of Wuhan University,2010,35(6):708-710.

[14] 冷順綠,楊根新,楊新云,等.總體最小二乘求解線性模型的一種新算法[J].地礦測繪,2014(1):26-27. LENG Shunlv, YANG Genxin, YANG Xinyun, et al. A New Algorithm of Total Least Squares for Linear Models[J]. Surveying and Mapping of Geology and Mineral Resources,2014(1):26-27.

[15] 王思成,楊劍.三種GPS模糊度降相關算法的比較[J].礦山測量,2009(1):42-43. YANG Sicheng, YANG Jian. The comparison of three kinds of decorrelation algorithm of GPS ambiguity[J].MINE SURVEYING,2009(1):42-43.

[16] de Jonge P, Tiberius C. The LAMBDA method for integer ambiguity estimation: implementation aspects[J]. Delft Geodetic Computing Center LGR Series,1996,12:1-49.

[17] Xu P. Random simulation and GPS decorrelation[M]. Geodesy-The Challenge of the 3rd Millennium. Springer Berlin Heidelberg,2003:405-422.

[18] 謝愷，柴洪洲，范龍,等.一種改進的LLL模糊度降相關算法[J].武漢大學學報:信息科學版,2014,39(11):1363-1369. XIE Kai, CHAI Hongzhou, FAN Long, et al. An Improved LLL Ambiguity Decorrelation Algorithm[J]. Geomatics and Information Science of Wuhan University,2014,39(11):1363-1369.

[19] 劉志平，何秀鳳，郭廣禮,等.GNSS模糊度降相關算法及其評價指標研究[J].武漢大學學報:信息科學版,2011,36(3):257-262. LIU Zhiping, HE Xiufeng, CUO Guangli, et al. Decorrelation Algorithms and Its Evaliation Indexes for GNSS Ambiguity Solution[J]. Geomatics and Information Science of Wuhan University,2011,36(3):257-262.

Integer Ambiguity Solution Based on Artificial Fish Swarm Algorithm

LIU Shugang ZHANG Yajing

(Computer Science Department, North China Electric Power Univwecity, Baoding 071003)

The integer ambiguity solution is the key of solving the problem in the global satellite navigation system positioning solution. In the process of ambiguity resolution, there is a problem of low search speed. In this paper, to solve this problem, the artificial fish swarm algorithm is introduced into the fast solution of integer ambiguity according to the features of global optimization of this algorithm. Firstly, the double difference carrier phase measurement model of the satellite positioning system is analyzed, the float solution of ambiguity is calculated by the weighted least square estimation. Then, the inverse integer Cholesky algorithm based on ascending sort is used to decorrelate the float solution of the corresponding covariance matrix. Finally, the artificial fish swarm algorithm is used to search the ambiguity. And due to the integer features of ambiguity, the artificial fish swarm algorithm is improved using rounding algorrithm. The instance is used for simulation experiment. And the result of the experiment is great. Compared with genetic algorithm to solve this problem, exact solution of the problem is obtained by using artificial fish swarm algorithm, and the search time is short using this algorithm.

global positioning system, integer ambiguity, artificial fish swarm algorithm

2016年5月11日,

2016年6月27日

劉書剛，男，副教授，碩士生導師，研究方向：嵌入式系統(tǒng)。張亞晶，女，碩士研究生，研究方向：嵌入式系統(tǒng)。

P228.41

10.3969/j.issn.1672-9722.2016.11.006