劉書剛 張亞晶
(華北電力大學(xué)計(jì)算機(jī)系 保定 071003)
?
基于人工魚群算法的整周模糊度解算算法*
劉書剛 張亞晶
(華北電力大學(xué)計(jì)算機(jī)系 保定 071003)
整周模糊度解算是基于全球衛(wèi)星導(dǎo)航系統(tǒng)定位解算中的關(guān)鍵問題。在模糊度解算過程中存在搜索速度慢的問題。針對這一問題,論文利用人工魚群算法的全局尋優(yōu)的特性,將該算法引入整周模糊度的快速解算中。論文首先分析了衛(wèi)星定位系統(tǒng)的雙差載波相位測量模型并利用加權(quán)最小二乘估計(jì)解算出模糊度浮點(diǎn)解;然后利用升序排序的逆整Cholesky算法降低模糊度浮點(diǎn)解及其協(xié)方差矩陣的相關(guān)性;最后運(yùn)用人工魚群算法進(jìn)行模糊度搜索。由于模糊度的整數(shù)特性,在搜索中利用舍入算法對人工魚群算法進(jìn)行改進(jìn)。運(yùn)用實(shí)例進(jìn)行仿真實(shí)驗(yàn)得到較好結(jié)果。并與利用自適應(yīng)遺傳算法的模糊度解算結(jié)果進(jìn)行比較,結(jié)果表明人工魚群算法用于模糊度解算可以得到精確的模糊度解,并且解算時(shí)間優(yōu)于遺傳算法的解算時(shí)間。
全球定位系統(tǒng); 整周模糊度; 人工魚群算法
Class Number P228.41
在GPS載波相位精密定位中,整周模糊度的求解是其中的關(guān)鍵問題。其中LAMBDA[1~3](最小二乘模糊度降相關(guān)平差)是目前應(yīng)用最為廣泛的模糊度求解算法。LAMBDA求解整周模糊度分為兩步,首先,對由模糊度雙差模型求得的模糊度浮點(diǎn)解及其相應(yīng)的模糊度方差-協(xié)方差矩陣進(jìn)行降相關(guān)操作(主要包括整數(shù)高斯變換、逆整形Cholesky分解、LLL規(guī)約等)。隨后,在以模糊度浮點(diǎn)解為中心的橢球區(qū)域內(nèi)搜索模糊度最優(yōu)解。由于其搜索過程需遍歷搜索空間中所有的候選點(diǎn),這樣大大增加了搜索的開銷,延長了搜索時(shí)間。因此,具有全局尋優(yōu)特點(diǎn)的人工智能算法對模糊度的搜索尋優(yōu)更加有利。
在人工智能領(lǐng)域中,遺傳算法[4]與蟻群算法[5]等均具有全局尋優(yōu)的能力。鄭慶暉等[6]提出了一種基于簡單遺傳算法的改進(jìn)整周模糊的搜索方法,大大提高了搜索效率。徐定杰等[7]提出里一種基于自適應(yīng)遺傳算法的整周模糊度解算算法。人工魚群算法[8~10]是群智能領(lǐng)域中的一個(gè)重要算法,具有較好的全局優(yōu)化能力,當(dāng)個(gè)體數(shù)增加時(shí),其收斂速度提高。相比于遺傳算法存在的早熟收斂的缺陷,人工魚群算法特有隨機(jī)行為機(jī)制避免了在搜索過程中陷入局部最優(yōu)而無法跳出的問題。本文采用人工魚群算法來進(jìn)行整周模糊度的搜索。并且根據(jù)模糊度的整數(shù)特性將人工魚群算法進(jìn)行了改進(jìn)。
2.1 模糊度最小二乘估計(jì)模型
衛(wèi)星精確定位中,由于載波相位差分測量[11~12]定位在進(jìn)行雙差操作時(shí)可以減小電離層、對流層、衛(wèi)星鐘差等誤差,因此被廣泛應(yīng)用于衛(wèi)星精密定位中。假設(shè)接收機(jī)1、2在t時(shí)刻對兩個(gè)衛(wèi)星j、k進(jìn)行觀測,雙差定為模型可表示為
(1)
其中Φ表示t時(shí)刻兩接收機(jī)與兩衛(wèi)星的雙差觀測量;N表示接收機(jī)r與衛(wèi)星s之間的載波相位整周模糊度;ρ表示接收機(jī)r與衛(wèi)星s之間的距離;ddε表示雙差觀測噪聲;λ為GPS載波波長。將載波相位的雙差模型線性化,其數(shù)學(xué)模型表示為
V=Aa+Bb+ε
(2)
其中V是載波相位觀測值,a是整周模糊度向量,b是兩基站之間基線向量,A,B均為設(shè)計(jì)矩陣,ε為觀測誤差向量。式(2)中有兩個(gè)未知向量整周模糊度向量a與基線向量b。式(2)中未知參數(shù)a與b的確定可以用最小二乘的參數(shù)估計(jì)[13~14]求解,因此式(2)實(shí)質(zhì)上是最小二乘解求解問題。
(3)
式中Nr是載波相位方差協(xié)方差矩陣。
(4)
2.2 模糊度降相關(guān)
通過最小二乘估計(jì)獲得的模糊度浮點(diǎn)值及其方差-協(xié)方差矩陣具有較高的相關(guān)性,在整數(shù)模糊度搜索過程中,這會(huì)影響搜索速率,降低模糊度的搜索效率。因此,在進(jìn)行模糊度搜索前,應(yīng)進(jìn)行模糊度降相關(guān)操作。常用的降相關(guān)算法[15]有:整數(shù)高斯變換[16]、逆整數(shù)Cholesky算法[17]、LLL算法[18]等。李志平等[19]對上述三種模糊度降相關(guān)算法進(jìn)行了評價(jià),并提出對于小于20維低維方差-協(xié)方差矩陣基于升序排列的逆整Cholesky算法具有較好的降相關(guān)效果。由于GPS動(dòng)態(tài)定位中,模糊度方差陣的維數(shù)一般在5~10維左右,因此本文采用基于升序排列的逆整數(shù)Cholesky算法進(jìn)行模糊度降相關(guān)。升序排列的逆整數(shù)Cholesky算法,對模糊度協(xié)方差矩陣進(jìn)行LDLT分解后的對角矩陣按對角線升序排列后,再進(jìn)行整數(shù)Z變換。
2.3 搜索空間確定
在GPS短基線測量定位中,模糊度搜索空間的確定主要的約束條件是基線長度。假設(shè)基線長度為m,以模糊度浮點(diǎn)解為中心的整周模糊度a的取值范圍為
-m/λ≤a≤m/λ
(5)
其中λ為GPS載波波長,取值為0.19m。本文采用的基線長度為2m。因此本文中搜索空間范圍為
-10.5≤a≤10.5
(6)
模糊度搜索實(shí)質(zhì)上是在搜索空間中找的式(4)的最小值。為了減少模糊度的搜索次數(shù),提高模糊度的搜索效率,本文引入人工魚群算法進(jìn)行模糊度搜索。人工魚群算法是借鑒自然界中魚群趨向食物豐富方向而產(chǎn)生的覓食、追尾、聚群等行為進(jìn)行優(yōu)化操作的一種群智能算法。隨著迭代次數(shù)的增加,人工魚群會(huì)逐步游向食物濃度更高的區(qū)域,并聚集在這個(gè)區(qū)域。本文提出了改進(jìn)的人工魚群算法,利用取整操作保證人工魚個(gè)體中每個(gè)變量的整數(shù)特性。
3.1 初始化
人工魚群算法的目標(biāo)函數(shù)為式(4),如圖1所示,由于人工魚群算法在較為平坦的范圍,搜索效率較低,且容易陷入局部最優(yōu)。因此本文采用文獻(xiàn)[2]中的適應(yīng)度函數(shù)作為目標(biāo)函數(shù)進(jìn)行整數(shù)模糊度搜索,如圖2所示。式(7)為修改后的目標(biāo)函數(shù)
f(a)=b-log(J(a))
(7)
3.2 行為選擇
在本次魚群算法的目標(biāo)函數(shù)為式(7),即求最大值問題。因此在行為選擇中,首先對追尾行為和聚群行為進(jìn)行模擬,對其行為執(zhí)行后所在位置的食物濃度進(jìn)行比較選擇其中食物濃度較大的行為并執(zhí)行。對每個(gè)狀態(tài)的評價(jià)如下:
1) 隨機(jī)行為(AF-rand):當(dāng)人工魚個(gè)體通過其他行為判斷搜索不到較優(yōu)狀態(tài)時(shí),該個(gè)體隨機(jī)選擇一個(gè)狀態(tài)作為下一狀態(tài)移動(dòng)一步。其數(shù)學(xué)表達(dá)式為
(8)
2) 覓食行為(AF-preying):人工魚個(gè)體隨機(jī)選擇一個(gè)狀態(tài),與當(dāng)前狀態(tài)的食物濃度進(jìn)行比較。若該狀態(tài)食物濃度較大,則移動(dòng)一步;否則,重新選擇下一狀態(tài),直到試探達(dá)到最大次數(shù),則執(zhí)行隨機(jī)行為。其數(shù)學(xué)表達(dá)式為
(9)
3) 追尾行為(AF-fllow):人工魚個(gè)體對其感知范圍內(nèi)的所有伙伴進(jìn)行判斷,找出所在位置的食物濃度最高的伙伴位置,并與自己當(dāng)前位置的食物濃度比較。若該位置食物濃度大,則向著該伙伴的方向移動(dòng)一部。反之,則執(zhí)行覓食行為。
(10)
4) 聚群行為(AF-swam):人工魚個(gè)體Xi探索其感知范圍內(nèi)的伙伴數(shù)目nf及中心位置Xc,若Yc/nf>δYi(δ為擁堵因子),則向Xc方向移動(dòng)一步。否則,執(zhí)行覓食行為。
(11)
3.3 結(jié)果評價(jià)
在本文中的求最大值問題,因此采用當(dāng)人工魚群算法達(dá)到最大迭代次數(shù)時(shí),公告板中所記錄的最大食物濃度即為所求模糊度整數(shù)解。
文獻(xiàn)[2]中采用簡單遺傳算法進(jìn)行模糊度搜索,與LAMBDA算法相比具有較高的搜索效率。文獻(xiàn)[3]中采用自適應(yīng)遺傳算法進(jìn)行模糊度求解,并與簡單遺傳算法、LAMBDA的模糊度求解相比較,證明了自適應(yīng)的遺傳算法具有較高的模糊度搜索效率,并且在相同的搜索精度下,自適應(yīng)遺傳算法的搜索時(shí)間遠(yuǎn)小于LAMBDA的搜索時(shí)間。因此本文仿真試驗(yàn)中主要通過自適應(yīng)遺傳算法與人工魚群算法的搜索效率比較來驗(yàn)證本文算法的性能。
對人工魚群算法的模糊度搜索進(jìn)行仿真,本文采用文獻(xiàn)[3]中的模糊度解算例子,模糊度浮點(diǎn)解和模糊度方差為
利用升序排列的逆整數(shù)Cholesky降相關(guān)算法操作后的模糊度浮點(diǎn)解和模糊度方差為
降相關(guān)前后的目標(biāo)函數(shù)圖像如圖2和圖1所示,通過比較可以看出,通過降相關(guān)操作,避免了搜索過程中陷入局部最優(yōu)。
圖1 降相關(guān)后目標(biāo)函數(shù)圖像
為方便將人工魚群算法和自適應(yīng)遺傳算法進(jìn)行比較,本次試驗(yàn)中人工魚群算法與自適應(yīng)遺傳算法的種群個(gè)數(shù)與迭代次數(shù)分別為50、200。如圖3、圖4所示為兩種算法隨迭代次數(shù)的增加其最優(yōu)值得變化情況。從圖中可以看出,人工魚群算法在80代以內(nèi)就可獲得最優(yōu)解,而自適應(yīng)遺傳算法在120代以后達(dá)到最優(yōu)解。這是因?yàn)殡S著迭代次數(shù)增加,自適應(yīng)遺傳算法的種群多樣性降低,容易陷入早熟收斂,而人工魚群算法的覓食、追尾和聚群等行為使算法快速收斂,隨機(jī)行為又使算法可以跳出局部最優(yōu),從而達(dá)到全局最優(yōu)。
圖2 降相關(guān)前目標(biāo)函數(shù)圖像
圖3 人工魚群算法
圖4 自適應(yīng)遺傳算法
利用自適應(yīng)遺傳算法和人工魚群算法對初始整周模糊度解算結(jié)果與時(shí)間的比較見表1。從表1中可以看出人工魚群算法與自適應(yīng)遺傳算法對整周模糊度的解算都可以達(dá)到較為理想的結(jié)果,但AFSA的解算時(shí)間遠(yuǎn)優(yōu)于自適應(yīng)遺傳算法,文獻(xiàn)[3]中將LAMBDA算法與自適應(yīng)遺傳算法以相同的模糊度浮點(diǎn)解與方差陣實(shí)例進(jìn)行了初始模糊度解算,并比較解算結(jié)果與時(shí)間效率。文獻(xiàn)[5]中的結(jié)果表明,LAMBDA以自適應(yīng)遺傳算法均能解得精確的模糊度解,但自適應(yīng)遺傳算法的解算時(shí)間遠(yuǎn)小于LAMBDA算法?;谝陨辖Y(jié)論,可以得出人工魚群算法的解算效率高于自適應(yīng)遺傳算法與LAMBDA算法。
表1 AFSA與AGA模糊度解算值與時(shí)間比較
本文分析了GPS載波相位雙差定位模型,并針對整周模糊度求解問題,引入了人工魚群算法。經(jīng)過數(shù)值實(shí)驗(yàn)可以證明,人工魚群算法應(yīng)用于解算整周模糊度,在數(shù)值精度上與自適應(yīng)遺傳算法一致,但其搜索時(shí)間優(yōu)于自適應(yīng)遺傳算法。因此,人工魚群算法應(yīng)用于整周模糊度的解算具有較高的魯棒性和解算效率,具有很高的使用價(jià)值。
[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ā),等.整周模糊度估計(jì)的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].國防科技大學(xué)學(xué)報(bào),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] 徐定杰,劉明凱,沈鋒,等.基于自適應(yīng)遺傳算法的DGPS整周模糊度快速解算[J].航空學(xué)報(bào),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].杭州:浙江大學(xué),2003. LI Xiaolei. A New Intelligent Optimization Method-Artificial Fish School Algorithm[M]. Hangzhou: Zhejiang University,2003.
[9] 黃華娟,周永權(quán).求解全局優(yōu)化問題的混合人工魚群算法[J].計(jì)算機(jī)應(yīng)用,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] 洪興福,胡祥濤.一種求解復(fù)雜優(yōu)化問題的新型人工魚群算法[J].計(jì)算機(jī)工程與應(yīng)用,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] 王廣運(yùn).載波相位差分GPS定位技術(shù)[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差分定位技術(shù)及實(shí)現(xiàn)方法的研究[D].鄭州:解放軍信息工程大學(xué),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ìn)算法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,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模糊度降相關(guān)算法的比較[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] 謝愷,柴洪洲,范龍,等.一種改進(jìn)的LLL模糊度降相關(guān)算法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,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模糊度降相關(guān)算法及其評價(jià)指標(biāo)研究[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,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日
劉書剛,男,副教授,碩士生導(dǎo)師,研究方向:嵌入式系統(tǒng)。張亞晶,女,碩士研究生,研究方向:嵌入式系統(tǒng)。
P228.41
10.3969/j.issn.1672-9722.2016.11.006