遺傳算法在秩虧自由網平差中的應用研究

唐立強

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

1 問題的提出

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

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

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

2 問題的數學描述

秩虧自由網平差的法方程組用下式表示：

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

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

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

上述問題就轉化為求解優化問題（2）。

3 問題的遺傳算法設計

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

3.1 參數編碼方案

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

3.2 適應度函數的設計

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

可見，目標函數值越大，其適應值越小，與優化問題

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

3.3 遺傳算法基本參數選擇

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

3.4 遺傳操作算子設計

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

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

3.5 迭代終止條件

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

3.6 遺傳算法的具體實現步驟

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

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

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

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

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

（6）對適應度最高的進行解碼，從而得出方程（1）的最優L2范數解。

4 應用實例

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

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

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

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

5 結論

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

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

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

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

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

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

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

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

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

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