改進遺傳算法在GPS坐標轉(zhuǎn)換中的應用研究

1、吳章祥,聶明新武漢理工大學信息工程學院,湖北武漢 430070E-mail: amorel摘要:近年來全球定位系統(tǒng)(GPS技術(shù)一直是測量以及通信等領(lǐng)域關(guān)注的焦點,對于GPS觀測數(shù)據(jù)的坐標變換中傳統(tǒng)的方法是高斯最小二乘法方法,然而利用傳統(tǒng)的高斯約化方法解算“病態(tài)”矩陣時結(jié)果很不穩(wěn)定,可能會產(chǎn)生很大的誤差。因此本文對用遺傳算法處理GPS坐標轉(zhuǎn)換中的病態(tài)問題進行了探討研究。關(guān)鍵詞:GPS;坐標轉(zhuǎn)換;病態(tài)方程; 遺傳算法中圖分類號:TP2281.引言全球定位系統(tǒng)(GPS 是美國從本世紀70年代開始研制,歷時20年耗資200億美元,于1994年全面建成的衛(wèi)星導航定位系統(tǒng)。作為新一代的衛(wèi)星導航定位系統(tǒng)經(jīng)過

2、20多年的發(fā)展,已成為在航空、航天、軍事、交通運輸、資源勘探、通信氣象、工程測繪等所有的領(lǐng)域,該系統(tǒng)近些年來發(fā)展迅速并日臻完善,并創(chuàng)造了巨大的經(jīng)濟價值和社會價值。但是GPS定位觀測得到的觀測成果通常是世界大地坐標系統(tǒng)WGS-84中的坐標或坐標差,而在實際應用中需要的往往卻是地面點在國家坐標系和地方獨立坐標系中的坐標。因此,GPS的觀測成果在實際中就必須進行坐標轉(zhuǎn)換1。傳統(tǒng)方法用于解決坐標轉(zhuǎn)換的一種方法是高斯最小二乘法,它主要是通過解算法方程組得到坐標轉(zhuǎn)換結(jié)果。然而由于高斯約化過程中的誤差積累及法方程組可能病態(tài)的問題,從而導致得到的結(jié)果精度不高。我們知道,遺傳算法在處理病態(tài)問題方面具有一定的優(yōu)勢

3、,因此研究用遺傳算法求取轉(zhuǎn)換參數(shù)、尤其是在法方程組病態(tài)的情況下求解轉(zhuǎn)換參數(shù)具有重要的研究意義。所以本文將首先介紹有關(guān)GPS坐標系統(tǒng)的基礎(chǔ)知識,然后分析了病態(tài)問題產(chǎn)生的原因以及危害。進而討論標準遺傳算法的不足之處和目前遺傳算法的幾類改進方法。最后,結(jié)合一個算例來驗證改進的遺傳算法處理病態(tài)問題的可行性和有效性。2.坐標系統(tǒng)的介紹2.1 WGS-84坐標系統(tǒng)WGS-84坐標系是目前GPS所采用的坐標系統(tǒng),是由美國國防部制圖局建立,于1987年取代了當時GPS所采用的坐標系統(tǒng)(WGS-72坐標系統(tǒng)而成為GPS目前所使用的坐標系統(tǒng)。WGS-84坐標系的坐標原點位于地球的質(zhì)心Z軸指向BIHl984.0定義

4、的協(xié)議地球極方向,X軸指向BIHl984.0的起始子午面和赤道的交點,Y軸與X軸和Z軸構(gòu)成右手系。WGS-84系所采用橢球參數(shù)為a=6 378 138 m; f=1/298.257223563。2.2 1954年北京坐標系1954年北京坐標系是我國目前廣泛采用的大地測量坐標系。該坐標系源自于原蘇聯(lián)采用過的1942年普爾科夫坐標系。建國前,我國沒有統(tǒng)一的大地坐標系統(tǒng),建國初期,在蘇聯(lián)專家的建議下,我國根據(jù)當時的具體情況,建立起了全國統(tǒng)一的1954年北京坐標系。該坐標采用的參考橢球是克拉索夫斯基橢球,該橢球的參數(shù)為:a=6378245m; f=1/298.3。該橢球并未依據(jù)當時我國的天文觀測資料進

5、行重新定位。而是由前蘇聯(lián)西伯利亞地區(qū)的一等鎖,經(jīng)我國的東北地區(qū)傳算過來的,該坐標的高程異2.3 1980年西安坐標系1980年西安坐標系采用了全面描述橢球性質(zhì)的四個基本參數(shù)a、GM、J2、。四個參數(shù)的數(shù)值采用的是1975年國際大地測量與地球物理聯(lián)合會16屆大會的推薦值:a=6378140m; GM=3986005*108m3/s;J2=1 082.63×10-6;=7 292 115×10-11rad/s。1980年西安坐標系的原點位于我國的中部,陜西西安市的附近。橢球的短軸平行于由地球質(zhì)心指向我國地極原點JYD1968。0的方向,起始大地子午面平行與我國起始天文子午面。大

6、地點的高程是1956年青島驗潮站的黃海平均海水面為基準。3.不同坐標系的坐標轉(zhuǎn)換中的病態(tài)問題在應用包括GPS在內(nèi)的空間定位技術(shù)進行測量時,往往需要進行不同基準間的轉(zhuǎn)換,目前一般采用布爾莎公式(七參數(shù)法 完成WGS-84坐標系到北京54坐標系的轉(zhuǎn)換,得到北京54坐標數(shù)據(jù)。布爾沙模型在進行全球或是較大范圍的基準轉(zhuǎn)換時較為常用,但在該模型中,由于旋轉(zhuǎn)中心位于原始坐標參照系的原點,因而旋轉(zhuǎn)參數(shù)與平移參數(shù)具有較高的相關(guān)性,容易導致轉(zhuǎn)換的病態(tài)問題。3.1病態(tài)性產(chǎn)生的原因及危害我們知道病態(tài)性在數(shù)據(jù)處理中的危害性是很大的。對病態(tài)性產(chǎn)生的原因進行準確的分析和掌握,有助于對病態(tài)性進行正確的診斷,也是研究如何削弱和

7、克服病態(tài)性影響的基礎(chǔ)。病態(tài)性的產(chǎn)生主要與參數(shù)選取、觀測以及計算方法等密切相關(guān)。病態(tài)效應主要表現(xiàn)在兩個方面:一是計算方面,在計算方面,病態(tài)性引起LS估計的法矩陣條件數(shù)很大,數(shù)據(jù)微小的變化會引起解的巨大變化,在數(shù)值計算上很不穩(wěn)定;二是統(tǒng)計方面,由于病態(tài)性嚴重影響了模型LS估計的優(yōu)良性質(zhì),因此法矩陣呈現(xiàn)病態(tài)性說明法矩陣的最大特征值與最小特征值差異較大,相對來說最小特征值較小, LS估計的均方差很大,導致準確性很差。3.2常用的解決病態(tài)問題的方法在許多與參數(shù)估計相關(guān)的數(shù)據(jù)處理領(lǐng)域中,如地球物理參數(shù)反演、回歸分析、坐標變換等,病態(tài)問題非常常見,其危害性是非常嚴重的。最小二乘估計一直是被廣泛應用于測量數(shù)據(jù)

8、處理中,它是一種重要的估計方法。然而當模型病態(tài)時,雖然用最小二乘解算的結(jié)果是無偏的,但方差較大。若觀測數(shù)據(jù)含有誤差,參數(shù)估值與真值就會相差很大,并且估值的表現(xiàn)不穩(wěn)定?；谶@個原因,病態(tài)問題引起了相關(guān)領(lǐng)域科技人員的廣泛關(guān)注,許多學者對病態(tài)模型的參數(shù)估計進行了深入的、系統(tǒng)的研究,取得了重要的理論成果和豐富的實踐經(jīng)驗,在解決病態(tài)問題方面做出了巨大的貢獻。目前解決病態(tài)方程常用并且效果較好的有有偏估計中的嶺估計和截斷奇異值分解(SVD方法,其中嶺估計是處理病態(tài)問題最常用的方法2。但這兩種方法都存在著不同程度的缺陷和不足。標準遺傳算法(SGA對各種實際優(yōu)化問題的搜索空間(優(yōu)化變量空間的大小變化的適應能力也

9、較差,計算量大,容易出現(xiàn)早熟收斂,SGA控制參數(shù)的設(shè)置技術(shù)目前尚無明確準則指導3。因此,本文研究用具有搜索優(yōu)秀結(jié)果能力的改進的遺傳算法求解病態(tài)方程,并通過一個算例來說明該方法處理病態(tài)問題的可行性和有效性4.1標準遺傳算法的缺陷標準遺傳算法(SGA因其具有運算簡單和解決問題的有效能力,被廣泛應用于眾多領(lǐng)域。理論上,SGA可以依概率“1”的方式尋求問題的最優(yōu)解,然而實際中SGA會表現(xiàn)的不盡如人意,很多問題有待進一步研究和探討。SGA的不足之處主要表現(xiàn)在以下幾個方面:(l早熟現(xiàn)象,即算法在搜索過程中,由于優(yōu)良個體急劇增加,使種群失去多樣性,尚未成熟就提前收斂于局部最優(yōu)解,使得算法無法繼續(xù)下去。(2運

10、行效率低,標準遺傳算法的交叉、變異算子是在一定的概率指導下進行的,使得SGA無法避免多次重復搜索同一個解,極大的降低了SGA的運行效率。(3參數(shù)的選擇問題,也就是說目前還沒有理論上的指導依據(jù),往往要靠實驗或經(jīng)驗來確定。(4局部尋優(yōu)能力較差,即SGA對局部空間的搜索能力不具備微調(diào)能力。(5標準遺傳算法適于解決缺乏解析知識、復雜、有噪聲的動態(tài)系統(tǒng),目前更適用于求解組合優(yōu)化問題,對實變量優(yōu)化問題不太合適。(6標準遺傳算法的計算精度受編碼長度控制,往往需要耗費比較長的計算時間。4.2目前遺傳算法的幾類改進方法為了克服遺傳算法存在收斂速度慢、易陷入局部極值點等缺陷,提高遺傳算法的性能和運行效率,不少學者

11、對遺傳算法進行了研究,提出了很多改進方法。這些方法歸納起來有以下三類:(1在遺傳算法機理研究基礎(chǔ)上,提出新的操作算子和算法,或者是在遺傳算法設(shè)計中融入實際問題的知識體系,這類改進涉及面比較寬,改動也比較大,故統(tǒng)稱為新型遺傳算法。如優(yōu)劣復取舍遺傳算法、小群體并行育種遺傳算法、優(yōu)良模式自學習遺傳算法等。(2對遺傳算法的操作過程或組成要素,如編碼方法、適應度設(shè)計、交叉、變異等操作算子進行一些改進。如多維實數(shù)編碼、圖文法編碼,多元非均勻變異算子、自調(diào)整遺傳算法、多個體參與與交叉的遺傳算法等。這些改進主要是局部細節(jié)的改變,實現(xiàn)起來不是太復雜,統(tǒng)稱為改進型遺傳算法。(3針對遺傳算法和其它優(yōu)化算法的優(yōu)缺點,

12、將其互相引進或結(jié)合,以彌補各自不足而形成的這類算法,統(tǒng)稱為混合遺傳算法。如基于共扼梯度法的函數(shù)優(yōu)化混合遺傳算法、模擬退火遺傳算法、混沌遺傳算法、遺傳算法與禁忌搜遺傳算法的混合策略、基于免疫原理的遺傳算法等等。5.基于改進的遺傳算法求解病態(tài)方程標準遺傳算法的編碼方式通常采用二進制,即所使用的編碼符合集是由二進制符0和1組成,它所構(gòu)成的個體基因型是一個二進制編碼符合串。二進制編碼簡單,交叉、變異等遺傳操作易于實現(xiàn),但是它不便于反映所求問題的結(jié)構(gòu)特征,對于一些連續(xù)函數(shù)的優(yōu)化問題等,也由于遺傳運算的隨機特征而使其局部搜索能力較差。同時,對于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題,使用二進制編碼來表示個

13、體時將會有一些不利之處。當個體編碼串的長度較短時,可能達不到精度要求,而個體編碼串的長度較長時,雖然能提高編碼精度,但卻會使遺傳算法的搜索空間急劇擴大。我們可以通過采用實數(shù)編碼來改進二進制編碼方法的這些缺點,使個體編碼長度等于其決策變量的個數(shù)4。實數(shù)編碼具有以下優(yōu)點:(l適合于在遺傳算法中表示范圍較大的數(shù);(2適合于精度要求較高的遺傳算法;(4改善了遺傳算法的計算復雜性,提高了運算效率;(5便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用;(6便于設(shè)計針對問題的專門知識的知識型遺傳算子;(7便于處理復雜的決策變量約束條件。受正交設(shè)計法的啟發(fā),經(jīng)深入探討標準遺傳算法的尋優(yōu)性能和大量的數(shù)值實驗與實際應用,有學

14、著提出了用第一次、第二次進化迭代所產(chǎn)生的優(yōu)秀個體的變量變化區(qū)間作為變量新的初始化變化區(qū)間,然后算法進行實數(shù)編碼,重新運行SGA 算法,如此加速循環(huán),優(yōu)秀個體的變化區(qū)間將逐步調(diào)整和收縮,與最優(yōu)點的距離將越來越近,直到最優(yōu)個體的優(yōu)化準則函數(shù)值小于某一設(shè)定值或算法運行達到預定加速(循環(huán)次數(shù),結(jié)束整個算法的運行5。此時,就把當前群體中最佳個體或優(yōu)秀個體的平均值指定為加速遺傳算法的結(jié)果。經(jīng)大量數(shù)值實驗和實際應用,初步結(jié)果表明:加速遺傳算法對SGA 的收斂速度和全局優(yōu)化性能方面有明顯的改進。6. 結(jié) 論下面我們將以一個個模擬的病態(tài)方程為例,研究和探索用改進的遺傳算法處理病態(tài)方程的可行性、可靠性和合理性。這

15、是一個模擬病態(tài)問題的算例,2.0000 5.0000 1.0000 1.00009.50002.0000 4.0000 1.0000 1.05008.50002.0000 1.0000 1.0000 1.0000 2.40001.0000 2.50000 4.00000.50007.00001.0000 3.2000 4.00000.50008.40001.0000 1.0000 3.00000.40000.49003.0000M =7.0000 3.0000 1.500012.70005.0000 1.0000 2.00002.50003.00004.0000 2.0000 2.0000 2

16、.0100 3.00004.0000 3.0000 2.0000 2.00005.0000 其中設(shè)計矩陣法方程系數(shù)陣的條件數(shù)為 1.2892,病態(tài)性嚴重。未知參數(shù)有5個,它們的真值為M M N T =510×T X 11111=,觀測噪聲,0(2I N 1=,由隨機數(shù)發(fā)器產(chǎn)生。該算例中,用改進的遺傳算法進行參數(shù)求解計算時,用隨機數(shù)生成器生成了25組滿足算例要求的觀測噪聲。初始參數(shù)的搜索范圍統(tǒng)一設(shè)為0,2,在不同的觀測誤差影響下,RAGA 計算出了25組不同的結(jié)果。選擇10組X 值較優(yōu)的解,計算出這10組解的均值l X 分為(0.8781,1.0617,0.9653,1.0615,0.

17、9809,MSE l X 為0.0713,X 為0.1547;同時選擇10組X 值相對較差的結(jié)果,得到10組解的均值l X =(0.9290,1.0435,0.9887,1.1160,0.9770,MSE(l X =0.4809,X =0.1451。將遺傳算法的結(jié)果與LS 估計、截斷奇異值法、嶺估計、兩步解法計算得到的數(shù)值比較,比較計算的lX 的均方誤差。從表1可以看出,用改進的遺傳算法求解病態(tài)方程的結(jié)果優(yōu)于LS 估計、截斷奇異值法、嶺估計等常規(guī)方法。通過該算例我們看到該方法在處理病態(tài)問題時是可行性的和有效的,結(jié)果表明改進的遺傳算法可以較快的計算出較高精度的結(jié)果。我們也發(fā)現(xiàn)RAGA 求解的結(jié)果

18、受觀測 參考文獻1 熊志昂.GPS技術(shù)與工程應用M.北京:國防工業(yè)出版社,2005.2 王新洲.在無偏估計類改進最小二乘估計的方法J.武漢測繪科技大學學報,1995,20(1:46-50.3 葉松林.矩陣奇異值分解與廣義嶺估計及其在測量中的應用.J中國有色金屬學報,1998,8(l:160-1644 陳國良.遺傳算法及其應用M.北京:人民有點出版社,1996.5 金菊良.標準遺傳算法的改進方案.J系統(tǒng)工程理論與實踐,2001,21(4:8-13Research on the improved GA in GPS coordinate transformationWu Zhangxiang, Nie MingxinSchool of Information Engineering of Wuhan University of Technology,Wuhan 430070AbstractIn recent years, GPS always was paid much attention to in the communications and measure field. The traditional way is using the least-squares method to get the