樂亞南,張獻(xiàn)州,陳 超,2

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

改進(jìn)遺傳算法在變形監(jiān)測網(wǎng)平差中的應(yīng)用

樂亞南1,張獻(xiàn)州1,陳 超1,2

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

遺傳算法在處理非線性最小二乘問題上具有其獨(dú)到的優(yōu)勢。文中通過對(duì)遺傳算法的理論性研究，對(duì)常規(guī)遺傳算法的選擇交叉策略、變異步長及變異率都作了改進(jìn)。并將改進(jìn)的遺傳算法應(yīng)用到變形監(jiān)測網(wǎng)平差中，實(shí)現(xiàn)變形監(jiān)測網(wǎng)在不同基準(zhǔn)下的非線性平差計(jì)算，并通過實(shí)例證明其實(shí)用性及優(yōu)越性。

改進(jìn)遺傳算法；變形監(jiān)測網(wǎng)；非線性平差；最小二乘準(zhǔn)則

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

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

針對(duì)常規(guī)遺傳算法具有收斂速度慢、易陷入局部收斂等缺點(diǎn)以及變形監(jiān)測數(shù)據(jù)對(duì)非線性平差形式的渴望，本文對(duì)常規(guī)遺傳算法進(jìn)行改進(jìn)，并用實(shí)例驗(yàn)證了改進(jìn)遺傳算法在變形監(jiān)測平差中的適用性及有效性。

1 改進(jìn)遺傳算法

遺傳算法主要是以適應(yīng)度來衡量解的優(yōu)劣，在實(shí)際操作中，為了能夠直觀地反應(yīng)個(gè)體對(duì)優(yōu)化問題的解釋程度，適應(yīng)度函數(shù)一般是以目標(biāo)函數(shù)的某種變換作為設(shè)計(jì)依據(jù)的，在進(jìn)行時(shí)，種群中可能會(huì)產(chǎn)生適應(yīng)度較強(qiáng)的個(gè)體而影響全局收斂。同時(shí)常規(guī)遺傳算法變異步長是固定的，并具有隨機(jī)性，這也可能造成收斂速度慢或得到較差的數(shù)據(jù)質(zhì)量。針對(duì)常規(guī)遺傳算法的以上缺點(diǎn)，從以下幾點(diǎn)對(duì)遺傳算法做了改進(jìn)。

1.1 種群初始化

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

1.2 適應(yīng)度函數(shù)的計(jì)算

適應(yīng)度反應(yīng)的是個(gè)體的適應(yīng)情況，在計(jì)算時(shí)則需先構(gòu)造適應(yīng)度函數(shù)，合理的適應(yīng)度函數(shù)可以使搜索向最優(yōu)化方向發(fā)展。同時(shí)適應(yīng)度函數(shù)是在非線性最小二乘平差準(zhǔn)則VTPV=min的基礎(chǔ)上求得的目標(biāo)函數(shù)F(X)[3-4]。由于F(X)總是變化的，則存在區(qū)間[F(X)min,F(X)max]，并且目標(biāo)函數(shù)是運(yùn)用各個(gè)目標(biāo)函數(shù)間的距離構(gòu)造的。若個(gè)體i的目標(biāo)函數(shù)值為F(Xi)，則個(gè)體i的適應(yīng)度值為

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

1.3 選擇與交叉

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

常規(guī)遺傳算法的交叉概率是不變的，這給遺傳進(jìn)化也帶來了局限性，因此本文在交叉策略上采用的是動(dòng)態(tài)自適應(yīng)交叉率的方法和基于線性的快速尋優(yōu)操作方法的改進(jìn)方法。將二者的優(yōu)點(diǎn)相結(jié)合保證了種群的多樣性并且該算法可根據(jù)個(gè)體的適應(yīng)度自適應(yīng)調(diào)整，因此本文采用如下自適應(yīng)交叉方案[7]：

其中：k1,k2是屬于[0，1]之間的隨機(jī)數(shù);Gbig為交叉?zhèn)€體中適應(yīng)度較大者;Gmax,Gavg分別為當(dāng)代種群的最大適應(yīng)度和平均適應(yīng)度。

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

1.4 變 異

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

變異步長針對(duì)的是個(gè)體基因的變化，其取值伴隨著一定的隨機(jī)性，有時(shí)變異步長短會(huì)取得較好的優(yōu)化效果，有時(shí)變異步長長會(huì)取得好的效果。針對(duì)步長的長短難確定的特點(diǎn)，采用自適應(yīng)的隨機(jī)變異步長，其公式如下：

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

變異率對(duì)應(yīng)的是種群，主要是與種群中變異種群的數(shù)目有關(guān)。變異率的大小決定了變異操作效果的好壞。因此本文采用的是自適應(yīng)變異率方案，其公式如下：

式中:k1，k2是[0，1]間的隨機(jī)數(shù)，Gmax為當(dāng)代種群的最大種群數(shù),Gavg為平均適應(yīng)度，Gbig為交叉?zhèn)€體中適應(yīng)度較大者，G為變異個(gè)體的適應(yīng)度。

1.5 種群進(jìn)化

在種群進(jìn)行進(jìn)化時(shí)，將t代種群和該種群經(jīng)過交叉、變異產(chǎn)生的t+1代種群放在一起，將它們按適應(yīng)度從大到小的順序排列，取最優(yōu)的前m-2個(gè)個(gè)體，再將適應(yīng)度最強(qiáng)的兩個(gè)個(gè)體復(fù)制兩個(gè)一同放入下一代，并將后面的個(gè)體淘汰，這樣種群就得到了進(jìn)化。

2 改進(jìn)遺傳算法在變形監(jiān)測中的應(yīng)用

2.1 變形監(jiān)測網(wǎng)的平差模型

在實(shí)際處理數(shù)據(jù)時(shí)，大多數(shù)的平差數(shù)學(xué)模型都是非線性的[10]，表達(dá)式如下：

L=f(X)+Δ.

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

式中：Px為基準(zhǔn)權(quán)方陣(變形監(jiān)測主要應(yīng)用固定基準(zhǔn)、重心基準(zhǔn)、擬穩(wěn)定基準(zhǔn)3個(gè)基準(zhǔn))，G為基準(zhǔn)權(quán)的附加矩陣。要想將上式轉(zhuǎn)化為標(biāo)準(zhǔn)的含有等式約束條件的優(yōu)化問題，則可將變形監(jiān)測網(wǎng)平差模型表示為

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

并且滿足

GTPxx=0.

應(yīng)用以上兩式就可以對(duì)附加基準(zhǔn)方程的變形監(jiān)測網(wǎng)進(jìn)行平差優(yōu)化。從而可解決非線性平差問題。

2.2 算 例

本文以一個(gè)測角網(wǎng)為例，驗(yàn)證改進(jìn)遺傳算法在變形監(jiān)測網(wǎng)平差中應(yīng)用的可行性，網(wǎng)圖如圖1所示。

圖1 網(wǎng)圖

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

表1 方向觀測值 (°)

各點(diǎn)的近似坐標(biāo)如表2所示。

表2 各點(diǎn)的近似坐標(biāo) m

應(yīng)用線性化法進(jìn)行最小二乘平差后計(jì)算得到不同基準(zhǔn)條件下各點(diǎn)的坐標(biāo),如表3所示。

表3 線性化方法平差計(jì)算的不同基準(zhǔn)條件下各點(diǎn)的坐標(biāo) m

應(yīng)用改進(jìn)遺傳算法平差后得到不同基準(zhǔn)條件下各點(diǎn)的坐標(biāo),如表4所示。

表4 改進(jìn)遺傳算法平差計(jì)算不同基準(zhǔn)條件下各點(diǎn)的坐標(biāo) m

在3種不同基準(zhǔn)條件下，線性化方法與改進(jìn)遺傳算法各點(diǎn)坐標(biāo)之間分別作差，結(jié)果如表5所示。

表5 線性化平差與改進(jìn)遺傳算法平差各點(diǎn)坐標(biāo)之差 mm

從表5中可以看出，改進(jìn)的遺傳算法與線性化方法算得的固定基準(zhǔn)的平差結(jié)果一致；重心基準(zhǔn)平差的計(jì)算結(jié)果與線性化計(jì)算結(jié)果最大差值為0.56 mm；而擬穩(wěn)重心基準(zhǔn)的計(jì)算結(jié)果與線性化方法計(jì)算的結(jié)果最大差值為1.38 mm。在3種基準(zhǔn)條件下，應(yīng)用改進(jìn)的遺傳算法算得的最后結(jié)果與線性化平差基本一致，同時(shí)也證實(shí)了改進(jìn)遺傳算法在變形監(jiān)測網(wǎng)平差中的可行性。

3 結(jié)束語

遺傳算法是一種全局優(yōu)化算法，尤其在非線性問題上具有明顯的優(yōu)勢。本文在常規(guī)遺傳算法的基礎(chǔ)上進(jìn)行了改進(jìn)，采用了保存最優(yōu)個(gè)體的選擇策略，在交叉算法上采用了一種現(xiàn)行的快速尋優(yōu)方法使適應(yīng)度較弱的個(gè)體向適應(yīng)度較強(qiáng)的個(gè)體進(jìn)行基因的轉(zhuǎn)化，防止了常規(guī)方法過早出現(xiàn)收斂的現(xiàn)象。為了滿足實(shí)際工程上對(duì)非線性數(shù)據(jù)處理的實(shí)際需求，本文將改進(jìn)的遺傳算法與最小二乘平差準(zhǔn)則相結(jié)合應(yīng)用到了變形監(jiān)測中。通過實(shí)例證明了改進(jìn)的遺傳算法在進(jìn)行變形監(jiān)測網(wǎng)平差方面具有較好的可行性及優(yōu)越性。

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

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

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

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

[5]王越,許全文,黃麗豐.基于改進(jìn)遺傳算法的連續(xù)函數(shù)優(yōu)化[J].重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版,2011,25(2):62-67.

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

[7]朱燦.實(shí)數(shù)編碼遺傳算法機(jī)理分析及算法改進(jìn)研究[D].長沙：中南大學(xué),2009.

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

[9]陳超.實(shí)數(shù)編碼遺傳算法在變形監(jiān)測網(wǎng)平差與變形預(yù)測中的應(yīng)用[D].成都：西南交通大學(xué),2012:34-40.

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

[11]王新洲.非線性模型參數(shù)估計(jì)理論與應(yīng)用[M].武漢：武漢大學(xué)出版社,2002.

[責(zé)任編輯：劉文霞]

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

鐵道部科技研究開發(fā)計(jì)劃資助項(xiàng)目(2012G009-C);鐵道部科技發(fā)展計(jì)劃資助項(xiàng)目(2008G031-5);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(SWJTU10ZT02)

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

P207

：A

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