唐立強

（湖南省水利水電勘測設計研究總院 長沙市 410007）

1 問題的提出

在經(jīng)典間接平差中，必須要有足夠的起算數(shù)據(jù)。當控制網(wǎng)中僅含必要的起算數(shù)據(jù)時，我們稱之為自由網(wǎng)；當控制網(wǎng)中除必要起算數(shù)據(jù)外，還有多余起算數(shù)據(jù)時，我們稱之為附合網(wǎng)。不管自由網(wǎng)還是附合網(wǎng)，在間接平差時，當所選的待定參數(shù)獨立時，誤差方程的系數(shù)矩陣B總是列滿秩的，相應的法方程系數(shù)陣N=BTPB為一滿秩對稱陣，故法方程有唯一解。

在實際工程應用中，我們經(jīng)常遇到一種具有特殊用途的控制網(wǎng)，它沒有起算數(shù)據(jù)并以待定點的坐標作為參數(shù)。顯然，由于缺乏確定控制網(wǎng)坐標的基準，這種網(wǎng)的誤差方程的系數(shù)矩陣B不是列滿秩的，相應的法方程系數(shù)陣N=BTPB為奇異陣。這種網(wǎng)被稱為秩虧自由網(wǎng)。秩虧自由網(wǎng)的法方程系數(shù)陣N奇異，即│N│=0，故N的凱利逆N-1不存在，法方程有無窮解[1]。因此在求解此類問題時一般采用附加d（d為法方程秩虧數(shù)）個基準條件，且附加的基準條件與法方程N線性無關?；鶞蕳l件的確定依據(jù)不同的網(wǎng)型，需要進行大量的前期計算工作，而且把基準條件方程與法方程聯(lián)立進行參數(shù)估計時，涉及復雜的矩陣運算。鑒于此，有必要研究一種計算更加簡單、有效的參數(shù)估計方法。

遺傳算法（Genetic Algorithms），簡稱 GA，是人類向其自身演化這一宏觀過程學習的結果，是一種更為宏觀意義下的仿生算法，它模仿的機制是一切生命與智能的產(chǎn)生與進化過程。它通過模擬達爾文“優(yōu)勝劣汰、適者生存”的原理激勵好的機制；通過模擬孟德爾遺傳變異的理論在迭代過程中保持已有的結構，同時尋找更好的結構[2]。與其它搜索算法相比，GA具有智能性、良好的并行性、很強的通用性、全局優(yōu)化性、穩(wěn)健性、可操作性、簡單性的優(yōu)點，體現(xiàn)出很強的尋優(yōu)能力。本文提出一種基于遺傳算法求解秩虧自由網(wǎng)平差的新算法。

2 問題的數(shù)學描述

秩虧自由網(wǎng)平差的法方程組用下式表示：

其中 法方程系數(shù)陣N=BTPB為t×t維的奇異方陣，參數(shù)向量 X=（x1，x2，…，xt）T，常數(shù)項向量 W=（w1，w2，… ，wt）T，t為未知參數(shù)的個數(shù)。

令 F（X）=NX-W，其中 F（X）=（f1（X），f2（X），…，ft（X））T，為了方便用遺傳算法來求解奇異方程組 （1），將方程組（1）的求解轉化為一個多維優(yōu)化問題來解決。方程組（1）的最小二乘解（或L2范數(shù)）等價于下面多維無約束優(yōu)化問題（2）的全局近似最優(yōu)解。

令目標函數(shù)ObjF(X)=FT(X)F(X)，則無約束多維優(yōu)化問題為:

上述問題就轉化為求解優(yōu)化問題（2）。

3 問題的遺傳算法設計

用遺傳算法求解問題（2）時涉及的主要問題有參數(shù)編碼方案、適應度函數(shù)設計、遺傳操作算子設計、遺傳算法基本參數(shù)選擇、迭代終止條件等等。

3.1 參數(shù)編碼方案

對問題（2），我們采用二進制多參數(shù)級聯(lián)編碼，即把參數(shù)向量X的每個分量先進行二進制編碼得到各個子串，再把各個子串按參數(shù)的順序排列在一起形成一個解個體。

3.2 適應度函數(shù)的設計

適應度函數(shù)是選擇操作的最根本依據(jù)，它直接影響到遺傳算法的性能。但適應度函數(shù)的設計沒有一成不變的公式，只能根據(jù)具體問題進行設計，并通過仿真進行改進。對于優(yōu)化問題（2），本文采用下式計算個體染色體的適應值：

可見，目標函數(shù)值越大，其適應值越小，與優(yōu)化問題

（2）一致，且該適應度函數(shù)變化趨勢平緩，有利于趨近全局最優(yōu)解。

3.3 遺傳算法基本參數(shù)選擇

群體規(guī)模l，交叉概率Pc,變異概率Pm的確定沒有明確的數(shù)值，只有大概的范圍。本文根據(jù)文獻[5]的研究成果并結合所研究問題的實際取群體規(guī)模L為40～100，Pc為0.4～0.8，Pm為 0.001～0.01 。

3.4 遺傳操作算子設計

選擇算子采用排序選擇，其主要著眼點是個體適應度之間的大小關系。即按適應度把個體從大到小排列，然后把序號在前的e個個體復制兩份，覆蓋序號在后面e個個體，而序號在中間的個體復制一份。這樣整個群體大小并沒有變化，它能保持一致的選擇壓力，能較好的抑制非成熟收斂。其中e的大小視群體規(guī)模而定，一般取1～5，當e=1時為杰出種子保留策略，本文采用這種策略。

交叉算子采用單點交叉，它能有效的保存較好的模式；變異算子采用基本位變異，即對個體染色體以變異概率Pm隨機指定的某一位或某幾位基因座上的基因值做變異運算。

3.5 迭代終止條件

雖然從理論上講，遺傳算法可以得到全局最優(yōu)解，但實際上我們無法判斷其確切的收斂時機，大多數(shù)情況下得出的是其近似最優(yōu)解，這對于實際應用已經(jīng)足夠了。本文采用目標函數(shù)值ObjF（X）＜1e-6作為迭代收斂條件。

3.6 遺傳算法的具體實現(xiàn)步驟

（1）設定遺傳算法的基本參數(shù)，初始化種群。

（2）根據(jù)式（3）計算每個個體的適應度。

（3）讓群體中的個體進行上述的遺傳操作，以產(chǎn)生新一代種群。

（4）判斷是否達到3.5中所述的收斂條件。

（5）若是，則結束運算；若否，則重復（2）、（3）、（4）步直到算法收斂。

（6）對適應度最高的進行解碼，從而得出方程（1）的最優(yōu)L2范數(shù)解。

4 應用實例

本例取自文獻[8]的[例7-5]。秩虧自由網(wǎng)平差的法方程為：

很顯然，方程（4）的法方程系數(shù)陣的行列式│N│=0。為了驗證本文算法的有效性，我們用上述遺傳算法思想編程實現(xiàn)了求解該方程組。遺傳算法參數(shù)設置為：群體大小L=80，交叉概率Pc=0.70，變異概率Pm=0.009.

附表給出了進化代數(shù)與目標函數(shù)值、方程解之間的情況。當?shù)?80次，算法終止，得出X=（-1.499 96,1.499 96,-0.500 04,0.500 00），這與文獻[8]用兩種方法計算的結果幾乎完全相同，但在實現(xiàn)方法上卻簡單了很多，省去了大量復雜的矩陣運算及需掌握的煩瑣專業(yè)知識。

附表 進化過程中目標函數(shù)值及解的演變過程

5 結論

本文應用遺傳算法直接求解秩虧方程組，實例結果表明，該方法能省去大量復雜的矩陣計算，且求解精度很高，完全滿足工程的實際需要。本文所設計的算法比較合理，能有效地解決測量中秩虧自由網(wǎng)平差問題，具有較高的應用價值。但在算法設計中，遺傳參數(shù)的選擇還停留在定性階段，需憑經(jīng)驗或通過大量的仿真來確定。一般情況下，我們希望能解決一類問題，而遺傳算法依具體的問題不同，其參數(shù)的選擇也不同，因此如何使參數(shù)能隨著種群的進化過程進行自適應調(diào)整，從而得出問題的滿意遺傳解，是筆者下一步要研究的課題。

1 武漢測繪科技大學測量平差教研室.測量平差基礎（第三版）[M].北京：測繪出版社,1996.

2 張文修,梁怡.遺傳算法的數(shù)學基礎[M].西安：西安交通大學出版社,2000.

3 周明,孫樹棟.遺傳算法原理及應用[M].北京：國防工業(yè)出版社，1999.

4 王小平,曹立明.遺傳算法—理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社,2002.

5 李敏強,寇紀凇,林丹,等.遺傳算法的基本理論與應用[M].北京：科學出版社，2002.

6 李世玲，張富堂，李治.基于遺傳算法的一類不確定性擾動下的系統(tǒng)參數(shù)辨識[J].系統(tǒng)仿真學報，2002,（5）.

7 郝博，胡玉蘭，盧有文，聶義勇.用遺傳算法解病態(tài)線性方程組的研究[J].計算機工程與設計，1998,（3）.

8 於宗儔，魯林成.測量平差基礎（增訂本）[M].北京,測繪出版社,1983.

9 馮旭東，陳方.遺傳算法的程序設計與實現(xiàn)[J].微機發(fā)展,1997,(6).