改進(jìn)遺傳算法在GPS坐標(biāo)轉(zhuǎn)換中的應(yīng)用研究

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

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

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

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

5、行重新定位。而是由前蘇聯(lián)西伯利亞地區(qū)的一等鎖,經(jīng)我國的東北地區(qū)傳算過來的,該坐標(biāo)的高程異2.3 1980年西安坐標(biāo)系1980年西安坐標(biāo)系采用了全面描述橢球性質(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年西安坐標(biāo)系的原點(diǎn)位于我國的中部,陜西西安市的附近。橢球的短軸平行于由地球質(zhì)心指向我國地極原點(diǎn)JYD1968。0的方向,起始大地子午面平行與我國起始天文子午面。大

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

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

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

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

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

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

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

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

14、著提出了用第一次、第二次進(jìn)化迭代所產(chǎn)生的優(yōu)秀個體的變量變化區(qū)間作為變量新的初始化變化區(qū)間,然后算法進(jìn)行實(shí)數(shù)編碼,重新運(yùn)行SGA 算法,如此加速循環(huán),優(yōu)秀個體的變化區(qū)間將逐步調(diào)整和收縮,與最優(yōu)點(diǎn)的距離將越來越近,直到最優(yōu)個體的優(yōu)化準(zhǔn)則函數(shù)值小于某一設(shè)定值或算法運(yùn)行達(dá)到預(yù)定加速(循環(huán)次數(shù),結(jié)束整個算法的運(yùn)行5。此時,就把當(dāng)前群體中最佳個體或優(yōu)秀個體的平均值指定為加速遺傳算法的結(jié)果。經(jīng)大量數(shù)值實(shí)驗(yàn)和實(shí)際應(yīng)用,初步結(jié)果表明:加速遺傳算法對SGA 的收斂速度和全局優(yōu)化性能方面有明顯的改進(jìn)。6. 結(jié) 論下面我們將以一個個模擬的病態(tài)方程為例,研究和探索用改進(jìn)的遺傳算法處理病態(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è)計(jì)矩陣法方程系數(shù)陣的條件數(shù)為 1.2892,病態(tài)性嚴(yán)重。未知參數(shù)有5個,它們的真值為M M N T =510×T X 11111=,觀測噪聲,0(2I N 1=,由隨機(jī)數(shù)發(fā)器產(chǎn)生。該算例中,用改進(jìn)的遺傳算法進(jìn)行參數(shù)求解計(jì)算時,用隨機(jī)數(shù)生成器生成了25組滿足算例要求的觀測噪聲。初始參數(shù)的搜索范圍統(tǒng)一設(shè)為0,2,在不同的觀測誤差影響下,RAGA 計(jì)算出了25組不同的結(jié)果。選擇10組X 值較優(yōu)的解,計(jì)算出這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 估計(jì)、截?cái)嗥娈愔捣?、嶺估計(jì)、兩步解法計(jì)算得到的數(shù)值比較,比較計(jì)算的lX 的均方誤差。從表1可以看出,用改進(jìn)的遺傳算法求解病態(tài)方程的結(jié)果優(yōu)于LS 估計(jì)、截?cái)嗥娈愔捣?、嶺估計(jì)等常規(guī)方法。通過該算例我們看到該方法在處理病態(tài)問題時是可行性的和有效的,結(jié)果表明改進(jìn)的遺傳算法可以較快的計(jì)算出較高精度的結(jié)果。我們也發(fā)現(xiàn)RAGA 求解的結(jié)果

18、受觀測 參考文獻(xiàn)1 熊志昂.GPS技術(shù)與工程應(yīng)用M.北京:國防工業(yè)出版社,2005.2 王新洲.在無偏估計(jì)類改進(jìn)最小二乘估計(jì)的方法J.武漢測繪科技大學(xué)學(xué)報(bào),1995,20(1:46-50.3 葉松林.矩陣奇異值分解與廣義嶺估計(jì)及其在測量中的應(yīng)用.J中國有色金屬學(xué)報(bào),1998,8(l:160-1644 陳國良.遺傳算法及其應(yīng)用M.北京:人民有點(diǎn)出版社,1996.5 金菊良.標(biāo)準(zhǔn)遺傳算法的改進(jìn)方案.J系統(tǒng)工程理論與實(shí)踐,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