基于加速遺傳算法的GPS變形監(jiān)測(cè)單歷元求解算法

王 建，張獻(xiàn)州

(西南交通大學(xué)地球科學(xué)與環(huán)境工程學(xué)院，四川成都610031)

一、引 言

整周模糊度的精確求解是GPS變形監(jiān)測(cè)［1-2］單歷元解算中的關(guān)鍵問題，對(duì)獲取高精度的變形量有著重要意義。國(guó)內(nèi)外許多學(xué)者對(duì)遺傳算法(genetic algorithm，GA)搜索整周模糊度進(jìn)行了研究，如劉智敏詳細(xì)闡述了遺傳算法的編碼方法和模糊度搜索過程［3］;陽(yáng)仁貴運(yùn)用遺傳算法搜索了單頻單歷元模糊度［4］;吳萬(wàn)清對(duì)遺傳算法聯(lián)合模糊函數(shù)法進(jìn)行了詳細(xì)的研究［5］等。以上研究都是針對(duì)模糊度域進(jìn)行操作，而模糊度具有整數(shù)特性，利用遺傳算法搜索模糊度，取整時(shí)難免會(huì)存在精度損失。本文采用改進(jìn)的二進(jìn)制編碼加速遺傳算法(AGA)，對(duì)監(jiān)測(cè)點(diǎn)坐標(biāo)進(jìn)行全局最優(yōu)搜索，當(dāng)監(jiān)測(cè)點(diǎn)坐標(biāo)滿足一定精度時(shí)，可利用直接計(jì)算法［6］快速準(zhǔn)確地固定單歷元雙差模糊度。

二、加速遺傳算法

GA是模擬生物進(jìn)化過程中優(yōu)勝劣汰規(guī)則與群體內(nèi)部染色體信息交換機(jī)制的一類全局優(yōu)化搜索算法［7］。傳統(tǒng)遺傳算法常出現(xiàn)早熟現(xiàn)象，且計(jì)算量較大，全局優(yōu)化速度較慢，針對(duì)這些問題，文獻(xiàn)［8］利用標(biāo)準(zhǔn)遺傳算法搜索到的優(yōu)秀個(gè)體來(lái)縮小變量的初始區(qū)間，構(gòu)成一種變區(qū)間的AGA。此方法采用二進(jìn)制編碼形式，而該編碼具有很強(qiáng)的雜交搜索能力，適用于較少變量和坐標(biāo)域的優(yōu)化搜索問題。

1.算法具體步驟

1)編碼長(zhǎng)度e的確定。編碼長(zhǎng)度決定了坐標(biāo)的解算精度，加速遺傳算法的變量區(qū)間不斷縮小，可由區(qū)間大?。踑i，bi］計(jì)算 e

式中，p為未知變量的個(gè)數(shù)，取p=3;坐標(biāo)搜索的精度精確到毫米。

2)初始種群的隨機(jī)生成。種群規(guī)模n取200～400，生成 n組［0，1］區(qū)間上的均勻隨機(jī)數(shù)，每組 p個(gè)，這些隨機(jī)數(shù)將對(duì)應(yīng)［ai，bi］的實(shí)數(shù)即為坐標(biāo)候選值，相應(yīng)的二進(jìn)制編碼則構(gòu)成初始種群的染色體。

3)個(gè)體的適應(yīng)度評(píng)價(jià)。由染色體對(duì)應(yīng)的坐標(biāo)候選值計(jì)算每個(gè)個(gè)體的適應(yīng)度，并以此評(píng)價(jià)個(gè)體的優(yōu)劣，調(diào)整進(jìn)化的方向。此處適應(yīng)度可依據(jù)模糊函數(shù)值計(jì)算

式中，ne為觀測(cè)歷元數(shù);nf為觀測(cè)頻率數(shù);ns為每歷元雙差觀測(cè)值數(shù);φmnobs為雙差相位觀測(cè)值;φmncal(xj，yj，zj)為坐標(biāo)候選值計(jì)算的雙差相位值。由式(2)知，模糊函數(shù)值越大，f(j)越大，個(gè)體適應(yīng)度值越高。選擇適應(yīng)度最高的s個(gè)個(gè)體構(gòu)成優(yōu)秀個(gè)體，以自適應(yīng)調(diào)整變量初始區(qū)間。

4)個(gè)體的選擇操作。采用比例選擇的方式，個(gè)體被選擇的概率與其適應(yīng)度值和群體適應(yīng)度總和有關(guān)，適應(yīng)度值越高的個(gè)體被選擇的概率應(yīng)越大。

5)個(gè)體的交叉和變異。交叉算子是體現(xiàn)遺傳算法的全局搜索能力，而變異算子則反映遺傳算法的局部尋優(yōu)能力，兩種算子是遺傳算法的核心。此處采用兩點(diǎn)變異的方式，以增強(qiáng)群體的多樣性，避免陷入局部最優(yōu);概率通過動(dòng)態(tài)自適應(yīng)方式確定，對(duì)于適應(yīng)度值較高的個(gè)體，對(duì)應(yīng)較低的交叉概率pc和變異概率pm，以保護(hù)進(jìn)入下一代;相反，適應(yīng)度較低的個(gè)體，給予較高的pc和pm，加強(qiáng)其進(jìn)化的能力。自適應(yīng)計(jì)算式［7］如下

式中，fmax為群體中最大的適應(yīng)度值;favg為每代個(gè)體的平均適應(yīng)度值;f'為兩個(gè)交叉?zhèn)€體中較大的適應(yīng)度值;f為變異個(gè)體的適應(yīng)度值。經(jīng)多次試驗(yàn)，當(dāng)pc1取 0.9、pc2取 0.6、pm1取 0.2、pm2取 0.05 時(shí)效果較好。

6)加速循環(huán)。經(jīng)選擇、交叉、變異可得到n個(gè)子代個(gè)體，取代父代個(gè)體，循環(huán)操作，構(gòu)成標(biāo)準(zhǔn)遺傳算法。在此基礎(chǔ)上，通過步驟3)選擇適應(yīng)度最高的s個(gè)個(gè)體，提取變量的變化區(qū)間，取代原始變化區(qū)間。隨著進(jìn)化的進(jìn)行，變化區(qū)間會(huì)朝著全局最優(yōu)的方向不斷縮小，加速搜索的過程。實(shí)際操作中，可以進(jìn)行兩次標(biāo)準(zhǔn)遺傳算法，把2s個(gè)優(yōu)秀個(gè)體的變量區(qū)間作為新的變量區(qū)間，進(jìn)行加速遺傳算法的進(jìn)化。當(dāng)變量區(qū)間小于某閥值時(shí)，取進(jìn)化個(gè)體中的最佳個(gè)體作為AGA的搜索結(jié)果。

2.算法穩(wěn)健性分析

加速遺傳算法不斷朝著全局最優(yōu)的方向進(jìn)化，變量的區(qū)間隨著進(jìn)化的進(jìn)行不斷縮小，對(duì)變化區(qū)間是否保留最優(yōu)個(gè)體必須進(jìn)行穩(wěn)健性分析。根據(jù)遺傳算法的收斂性定理［8］：保留最佳個(gè)體策略的遺傳算法能收斂于最優(yōu)解的概率為1，保證遺傳算法全局收斂的基本策略是生成的群體的有效基因不缺失概率盡可能大，并通過合適的選擇、雜交、變異操作把已發(fā)現(xiàn)的最優(yōu)個(gè)體保存下來(lái)。加速遺傳算法提取的2s個(gè)優(yōu)秀個(gè)體的有效基因缺失的概率為

則2s個(gè)優(yōu)秀個(gè)體包圍最優(yōu)點(diǎn)的概率為

變量個(gè)數(shù)為p，循環(huán)次數(shù)為q時(shí)，包圍概率為

當(dāng)p=3、s取20、q取20時(shí)，包圍概率 P(n)趨近于1，可知加速遺傳算法具有較強(qiáng)的全局收斂性，其保證了進(jìn)化過程朝著全局最優(yōu)的方向進(jìn)行。

三、雙差模糊度求解

GPS變形監(jiān)測(cè)中，由于基線較短(一般小于15 km)，采用雙差觀測(cè)值可大大消除衛(wèi)星鐘差、接收機(jī)鐘差、對(duì)流層延遲和電離層延遲等誤差。因此，雙差模糊度有關(guān)系式

衛(wèi)星到地面點(diǎn)的距離可表示為

式中，(xs，ys，zs)為衛(wèi)星坐標(biāo);(xp，yp，zp)為地面點(diǎn)坐標(biāo)。將式(9)展開則有

式中，p0為衛(wèi)地近似距離。

四、實(shí)例驗(yàn)證

采用某超高層建筑物GPS變形監(jiān)測(cè)數(shù)據(jù)對(duì)上述方法進(jìn)行驗(yàn)證。外業(yè)觀測(cè)采用Trimble R6雙頻接收機(jī)，采樣率為15 s，衛(wèi)星截止高度角15°，有效觀測(cè)衛(wèi)星6顆，取觀測(cè)時(shí)間1 h的基線數(shù)據(jù)進(jìn)行單歷元解算。采用上期監(jiān)測(cè)點(diǎn)坐標(biāo)作為本次計(jì)算的初始坐標(biāo)，利用 AGA 和 GA 對(duì)搜索區(qū)間［－0.2，0.2］、［－0.5，0.5］和［－1.0，1.0］的搜索效率進(jìn)行了對(duì)比，表1列出了詳細(xì)結(jié)果。

表1 不同變量區(qū)間的AGA與GA單歷元解算結(jié)果比較(n=200，s=20)

由表1知，相同搜索區(qū)間的情況下，AGA的解算成功率和平均搜索時(shí)間都優(yōu)于GA，這是因?yàn)锳GA依據(jù)優(yōu)秀個(gè)體的變化區(qū)間自適應(yīng)地縮小變量的初始區(qū)間，降低了陷入局部最優(yōu)解的可能性，從而提高了算法的搜索效率和解算成功率。兩種算法在區(qū)間［－1.0，1.0］的成功率都不是很高，尤其是GA算法，成功率僅51.3%，究其原因是搜索區(qū)間不斷增大，而種群規(guī)模n依然保持不變，群體多樣性受到限制，算法的全局收斂性亦受到影響。此時(shí)，可以考慮增加種群規(guī)模來(lái)解決這個(gè)問題，相應(yīng)的計(jì)算量和搜索時(shí)間也會(huì)增加。

為驗(yàn)證單歷元解算方法的準(zhǔn)確性，利用全部L1載波相位觀測(cè)值進(jìn)行靜態(tài)解算，采用LAMBDA方法固定雙差模糊度，作為該基線的基準(zhǔn)值，圖1顯示了在區(qū)間［－0.2，0.2］情況下，AGA 單歷元解算結(jié)果與基準(zhǔn)值的偏差情況。

由圖1知，大多數(shù)單歷元解算結(jié)果和基準(zhǔn)值的外符合精度都小于1 cm，少數(shù)歷元Y方向偏差大于1 cm。由此可見，AGA單歷元解算方法是正確的，解算結(jié)果是可靠的。從Y偏差和Z偏差還可以看出，歷元間時(shí)相關(guān)性很強(qiáng)，存在系統(tǒng)誤差的影響，如何有效地剔除單歷元解算結(jié)果的系統(tǒng)誤差，以便提取出監(jiān)測(cè)點(diǎn)的真實(shí)變形，將是筆者下一步的研究方向。

五、結(jié)束語(yǔ)

AGA相比GA，其s個(gè)優(yōu)秀個(gè)體可以反映模糊函數(shù)值在全局最優(yōu)點(diǎn)附近各方向上的變化趨勢(shì)，優(yōu)秀個(gè)體的變化區(qū)間也就是全局最優(yōu)點(diǎn)存在概率最大的區(qū)間，由此重新定義變量初始區(qū)間，能夠快速、穩(wěn)健地搜索到全局最優(yōu)解，為雙差模糊度的直接固定奠定了基礎(chǔ)。

實(shí)際應(yīng)用中，應(yīng)盡量提供較高精度的監(jiān)測(cè)點(diǎn)初始坐標(biāo)，依據(jù)變形量的大小制定合理的變量搜索區(qū)間，并依據(jù)區(qū)間大小給定合理的遺傳參數(shù)，以充分發(fā)揮加速遺傳算法的搜索能力，保證GPS單歷元的快速解算。受多路徑效應(yīng)等系統(tǒng)誤差的影響，單歷元解算結(jié)果存在強(qiáng)相關(guān)性，不能真實(shí)反映監(jiān)測(cè)點(diǎn)的實(shí)際變形，如何剔除系統(tǒng)誤差的影響，將是筆者下一步的研究方向。

圖1 單歷元解算與靜態(tài)解算比較

［1］張獻(xiàn)州，熊永良，牟朝云.電視塔中心線垂直度及塔身扭轉(zhuǎn) GPS監(jiān)測(cè)方法［J］.測(cè)繪學(xué)院學(xué)報(bào)，2003，20(2)：86-88.

［2］熊永良，黃丁發(fā)，張獻(xiàn)州.一種可靠的含約束條件的GPS變形監(jiān)測(cè)單歷元求解算法［J］.武漢大學(xué)學(xué)報(bào)，2001，26(1)：51-57.

［3］劉智敏，劉經(jīng)南，姜衛(wèi)平，等.遺傳算法解算GPS短基線整周模糊度的編碼方法研究［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2006，31(7)：607-609.

［4］陽(yáng)仁貴，歐吉坤，王振杰，等.用遺傳算法搜索GPS單頻單歷元整周模糊度［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，30(3)：251-254.

［5］吳萬(wàn)清，寧龍梅，朱才連.一種單頻單歷元GPS整周模糊度的解算方法［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，30(6)：497-501.

［6］王新洲，花向紅，邱蕾.GPS變形監(jiān)測(cè)中整周模糊度解算的新方法［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2007，32(1)：24-26.

［7］王小平.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2001：73-77.

［8］金菊良，楊曉華，丁晶.標(biāo)準(zhǔn)遺傳算法的改進(jìn)方案——加速遺傳算法［J］.系統(tǒng)工程理論與實(shí)踐，2001(4)：8-13.