改進遺傳算法在變形監測網平差中的應用

樂亞南,張獻州,陳 超,2

(1.西南交通大學 地球科學與環境工程學院，四川 成都 610031; 2.中水成勘院測繪工程公司，四川 成都 610031)

改進遺傳算法在變形監測網平差中的應用

樂亞南1,張獻州1,陳 超1,2

(1.西南交通大學 地球科學與環境工程學院，四川 成都 610031; 2.中水成勘院測繪工程公司，四川 成都 610031)

遺傳算法在處理非線性最小二乘問題上具有其獨到的優勢。文中通過對遺傳算法的理論性研究，對常規遺傳算法的選擇交叉策略、變異步長及變異率都作了改進。并將改進的遺傳算法應用到變形監測網平差中，實現變形監測網在不同基準下的非線性平差計算，并通過實例證明其實用性及優越性。

改進遺傳算法；變形監測網；非線性平差；最小二乘準則

在處理變形監測數據的過程中大多數的數學模型都是非線性的，應用處理非線性問題的經典方法是將其線性化，近似值附近展開為泰勒級數，通常情況只取第一項，略去高級項[1-2]。而用這種近似的方法處理變形監測中精度要求非常高的數據，必然會使最后的成果質量下降，從而影響了變形監測數據的精度及可靠性。

隨著測量技術的不斷發展，用非線性方法處理變形監測數據已成為人們研究的熱點。遺傳算法是在1975年由美國Michigan大學J.Holland教授根據達爾文的進化論和G.Mendel的遺傳變異理論提出的一種模仿生物進化規律的隨機化搜索方法。這種算法在處理非線性數學模型上具有很好的效果。

針對常規遺傳算法具有收斂速度慢、易陷入局部收斂等缺點以及變形監測數據對非線性平差形式的渴望，本文對常規遺傳算法進行改進，并用實例驗證了改進遺傳算法在變形監測平差中的適用性及有效性。

1 改進遺傳算法

遺傳算法主要是以適應度來衡量解的優劣，在實際操作中，為了能夠直觀地反應個體對優化問題的解釋程度，適應度函數一般是以目標函數的某種變換作為設計依據的，在進行時，種群中可能會產生適應度較強的個體而影響全局收斂。同時常規遺傳算法變異步長是固定的，并具有隨機性，這也可能造成收斂速度慢或得到較差的數據質量。針對常規遺傳算法的以上缺點，從以下幾點對遺傳算法做了改進。

1.1 種群初始化

將種群規模設為m，基因(待估參數)個數設為n，問題解空間的下界和上界分別為Li和Ui，則初始種群的第i個個體編碼如下：

1.2 適應度函數的計算

適應度反應的是個體的適應情況，在計算時則需先構造適應度函數，合理的適應度函數可以使搜索向最優化方向發展。同時適應度函數是在非線性最小二乘平差準則VTPV=min的基礎上求得的目標函數F(X)[3-4]。由于F(X)總是變化的，則存在區間[F(X)min,F(X)max]，并且目標函數是運用各個目標函數間的距離構造的。若個體i的目標函數值為F(Xi)，則個體i的適應度值為

式中：G(Xi)為個體i的適應度，ε為極小值。

1.3 選擇與交叉

選擇操作通常的做法都是采用輪盤賭的策略，這種方法雖然簡單易行，但會產生“早熟”、“收斂速度慢”或是陷入局部收斂等問題[5]。本文采用一種最優化個體保護的策略[6]，通過某種方法判斷種群中適應度最高的個體，不再經過遺傳步驟直接復制兩個該個體加到下一代種群，從而達到保護最優個體的目的。

常規遺傳算法的交叉概率是不變的，這給遺傳進化也帶來了局限性，因此本文在交叉策略上采用的是動態自適應交叉率的方法和基于線性的快速尋優操作方法的改進方法。將二者的優點相結合保證了種群的多樣性并且該算法可根據個體的適應度自適應調整，因此本文采用如下自適應交叉方案[7]：

其中：k1,k2是屬于[0，1]之間的隨機數;Gbig為交叉個體中適應度較大者;Gmax,Gavg分別為當代種群的最大適應度和平均適應度。

在交叉操作上，本文采用了一種基于線性的快速尋優操作方法[8]。

1.4 變 異

變異操作最主要的是可以維持種群進化過程中的多樣性，并具有局部搜索能力，有效地防止陷入局部最優解的情況。變異操作的關鍵是變異步長和變異率[9]。

變異步長針對的是個體基因的變化，其取值伴隨著一定的隨機性，有時變異步長短會取得較好的優化效果，有時變異步長長會取得好的效果。針對步長的長短難確定的特點，采用自適應的隨機變異步長，其公式如下：

式中:α的取值范圍為[0，1]，Gen為遺傳代數。

變異率對應的是種群，主要是與種群中變異種群的數目有關。變異率的大小決定了變異操作效果的好壞。因此本文采用的是自適應變異率方案，其公式如下：

式中:k1，k2是[0，1]間的隨機數，Gmax為當代種群的最大種群數,Gavg為平均適應度，Gbig為交叉個體中適應度較大者，G為變異個體的適應度。

1.5 種群進化

在種群進行進化時，將t代種群和該種群經過交叉、變異產生的t+1代種群放在一起，將它們按適應度從大到小的順序排列，取最優的前m-2個個體，再將適應度最強的兩個個體復制兩個一同放入下一代，并將后面的個體淘汰，這樣種群就得到了進化。

2 改進遺傳算法在變形監測中的應用

2.1 變形監測網的平差模型

在實際處理數據時，大多數的平差數學模型都是非線性的[10]，表達式如下：

L=f(X)+Δ.

其中:L表示m維觀測向量，X表示n維待估參數向量，f(x)為X的非線性函數式，Δ為隨機誤差。在平差中，一般采用最小二乘原理來消除隨機誤差Δ的干擾，進而計算L的最佳估值[10]。變形監測網的非線性平差模型為

式中：Px為基準權方陣(變形監測主要應用固定基準、重心基準、擬穩定基準3個基準)，G為基準權的附加矩陣。要想將上式轉化為標準的含有等式約束條件的優化問題，則可將變形監測網平差模型表示為

F(X)=VTPV=[f(X)-L]TP[f(X)-L].

并且滿足

GTPxx=0.

應用以上兩式就可以對附加基準方程的變形監測網進行平差優化。從而可解決非線性平差問題。

2.2 算 例

本文以一個測角網為例，驗證改進遺傳算法在變形監測網平差中應用的可行性，網圖如圖1所示。

圖1 網圖

圖中A,B兩點為已知點。坐標分別為A(4 628.4318，3 037.4051)，B(3 691.4417, 2 448.424 1)。方向觀測值如表1所示。

表1 方向觀測值 (°)

各點的近似坐標如表2所示。

表2 各點的近似坐標 m

應用線性化法進行最小二乘平差后計算得到不同基準條件下各點的坐標,如表3所示。

表3 線性化方法平差計算的不同基準條件下各點的坐標 m

應用改進遺傳算法平差后得到不同基準條件下各點的坐標,如表4所示。

表4 改進遺傳算法平差計算不同基準條件下各點的坐標 m

在3種不同基準條件下，線性化方法與改進遺傳算法各點坐標之間分別作差，結果如表5所示。

表5 線性化平差與改進遺傳算法平差各點坐標之差 mm

從表5中可以看出，改進的遺傳算法與線性化方法算得的固定基準的平差結果一致；重心基準平差的計算結果與線性化計算結果最大差值為0.56 mm；而擬穩重心基準的計算結果與線性化方法計算的結果最大差值為1.38 mm。在3種基準條件下，應用改進的遺傳算法算得的最后結果與線性化平差基本一致，同時也證實了改進遺傳算法在變形監測網平差中的可行性。

3 結束語

遺傳算法是一種全局優化算法，尤其在非線性問題上具有明顯的優勢。本文在常規遺傳算法的基礎上進行了改進，采用了保存最優個體的選擇策略，在交叉算法上采用了一種現行的快速尋優方法使適應度較弱的個體向適應度較強的個體進行基因的轉化，防止了常規方法過早出現收斂的現象。為了滿足實際工程上對非線性數據處理的實際需求，本文將改進的遺傳算法與最小二乘平差準則相結合應用到了變形監測中。通過實例證明了改進的遺傳算法在進行變形監測網平差方面具有較好的可行性及優越性。

[1]谷川，張岳. 遺傳算法改進及其在非線性最小二乘平差中的應用[J].鐵道勘察,2008(2):7-10.

[2]王穗輝.遺傳算法在非線性最小二乘平差中的應用[J].大地測量與地球動力學,2006,26(2): 95-98.

[3]袁豹,岳東杰. 關于總體最小二乘方法適應性實驗研究[J].測繪工程,2012,21(6):22-26.

[4]劉國林.非線性最小二乘與測量平差[M].北京：測繪出版社，2002.

[5]王越,許全文,黃麗豐.基于改進遺傳算法的連續函數優化[J].重慶理工大學學報:自然科學版,2011,25(2):62-67.

[6]陳小平,于盛林.遺傳算法交叉策略的改進[J].電子學報,2003,31(1)：1-4.

[7]朱燦.實數編碼遺傳算法機理分析及算法改進研究[D].長沙：中南大學,2009.

[8]陳小平,石玉,于盛林.快速尋優的遺傳交叉策略[J].控制理論與應用,2002,19(6):981-984.

[9]陳超.實數編碼遺傳算法在變形監測網平差與變形預測中的應用[D].成都：西南交通大學,2012:34-40.

[10]田玉剛,王新洲,花向紅.非線性最小二乘估計的遺傳算法[J].測繪工程,2004,13(4):6-8.

[11]王新洲.非線性模型參數估計理論與應用[M].武漢：武漢大學出版社,2002.

[責任編輯：劉文霞]

Improved genetic algorithm applied to deformation monitoring network adjustment

LE Ya-nan1，ZHANG Xian-zhou1，CHEN Chao1,2

(1.School of Geosciences and Environmental Engineering Southwest Jiaotong University,Chengdu 610031, China; 2. Surveying and Mapping Engineering Co.,China Water Conservancy Survey and Design Institute, Chengdu 610031, China)

The genetic algorithm has its unique advantage in dealing with nonlinear least squares problems. Through the theoretical research of genetic algorithm, the selection and crossover strategy, mutation step size and mutation rates of conventional genetic algorithm are made with improvements. The improved genetic algorithm is applied to the deformation monitoring network adjustment in order to realize the nonlinear deformation covculation. The concrete example is demonstrated to prove its practicality and superiority.

improved genetic algorithm；deformation monitoring network；nonlinear adjustment；least squares criterion

2013-10-12

鐵道部科技研究開發計劃資助項目(2012G009-C);鐵道部科技發展計劃資助項目(2008G031-5);中央高校基本科研業務費專項資金資助項目(SWJTU10ZT02)

樂亞南(1987-)，女，碩士研究生.

P207

：A

：1006-7949(2014)10-0054-04