綜合性遺傳算法用于水質模型參數估值
摘要：將一種具有更高收斂速度、更少迭代次數的綜合性遺傳算法 應用 于水環境模型參數估值之中，通過與簡單遺傳算法 計算 結果的對比驗證了新 方法 的有效性。
關鍵詞：遺傳算法 優化 水質模型 參數估值
遺傳算法(SGA)應用于環境 科學 領域的 研究 主要集中在對各種非線性水質模型的參數估計[1]、水質及水污染非線性規劃的求解[2]等，但簡單的遺傳算法在求解中存在不少 問題 [3]，尤其對類似水質非線性規劃等復雜的多變量優化問題則效率并不高，有時并不收斂或者出現“早熟現象”[4]，故提出一種綜合性遺傳算法(MAGA)。
1 遺傳算法和綜合遺傳算法
在利用遺傳算法求解問題時，問題的每個可能的解都被編碼成一個“染色體”，即若干個體構成了群體(所有可能解)。算法開始時總是隨機地產生一些個體(即初始解)，根據預定的 目標函數對每個個體進行評價后得出一個適應度值;基于此適應度值選擇個體用來復制下一代，選擇操作體現了“適者”生存的原理，“好”的個體被復制，“壞”的則被淘汰;然后選擇出來的個體經交叉和變異進行再組合生成新一代，這一群新個體由于繼承了上一代的一些優良性狀，因而在性能上要優于上一代，這樣逐步朝著更優解方向進化5]。基本流程見圖1。
盡管傳統遺傳算法可以找到全局最優，但在求解許多實際問題時其收斂速度還不盡人意，且操作參數的選取對結果 影響 巨大，故許多學者對簡單的遺傳算法進行了改進[6、7]，在此提出一種效率較高的綜合遺傳算法。
① 選擇操作的改進
利用基于馬爾科夫鏈的定量的數學證明認為，簡單的遺傳算法不是全局收斂的，而帶有最優個體保留的遺傳算法則是全局收斂的[6]，故在選擇操作中采用杰出個體保護策略。
根據目標函數值決定將被復制的數字串，設種群中有N個個體，將這N個個體解碼得N個適應性函數值fi(i=1,2,3,…,N),按下述步驟復制：
a.令P=隨機數×∑fi
則復制第k個數字串。
將N個個體f值先按從大到小的順序排列，復制出N/2個個體到匹配池中等待交叉操作，將選出的N/2個個體進行交叉操作后放回到匹配池中，頂替排在后面的N/2個個體(即將排在后面的N/2個個體清除掉)。對匹配池中的N個個體重新按大到小的順序排列，采用杰出個體保護策略，即將父代中最優個體放回到匹配池中頂替重新排列后的最后一個個體以保持種群中優秀個體的存在。
② 適應值函數調整
在遺傳進化初期，通常會出現一些超常的個體，為避免“早熟現象”，應將適應函數值進行適當調整以降低選擇強度，在此采用Paul L.Stoffa提出的模擬退火法對適應值函數進行拉伸[7]：
式中 fi——第i個個體適合度
N——種群個體總數
g——遺傳代數序號
T——溫度
T0——初始溫度
從式(1)、(2)可以看出，在溫度高時(即進化前期)，適合度相近的個體產生后代的概率相近，而當溫度不斷下降后，拉伸作用加強使得適合度相近的個體適合度差異放大，從而使優秀的個體優勢更明顯。
③ 交叉操作的改進
以單點交叉、兩點交叉和交叉位置的非等概率選取相結合作為交叉操作。當染色體位串長度較短時，可采用整串的兩點交叉操作;而當染色體位串長度較長時，特別是子串位數較多時可采用各個子串分別進行單點交叉操作，并引進交叉位置的非等概率選取。 ④ 自適應調整Pc和Pm
在簡單遺傳算法中，交換概率Pc和變異概率Pm一般取為恒定值，在進行復雜多變量優化問題時，效率并不高，主要是因為Pc越大個體被破壞的可能性就會增加，使得具有高適應值的個體結構很快被破壞，Pc過小會使搜索緩慢而停滯不前;Pm過大遺傳算法就變成了純粹的隨機搜索算法，Pm過小又不易產生新的個體，因此如何選擇Pc和Pm是保證算法成功的關鍵。
有學者提出Pc和Pm隨適應度值自動改變的方法。對于高于平均適應值 的解，令Pc和Pm取值小一些，使解受破壞的可能性小，而對低于平均適應值的解，令Pc和Pm取值大一些以防止遺傳算法陷入局部解。因此按 參考 文獻 [8]提出的方法進行調整：
式中 Pc1=0.9,Pc2=0.7,Pm1=0.01,Pm2=0.001。
⑤ 變量區間優化(動態變量編碼)
一般來說，自變量參數(即所求未知參數)的范圍越小搜索的速度就越快，也就更加容易確定最優解。設新求出的優化變量值為x′，將-|x′|以及|x′|值作為下一次x求解的取值區間的上下限，重新進行計算。
⑥ 終止條件的選擇
經典的方法是固定遺傳代數，到達后即終止，本文采用改進的方法，即根據連續幾代個體平均適合度不變(其差小于某個極小的閾值)作為終止的條件。
2 實例驗證
利用 文獻 [9]中水質模型的參數估值一實例來比較綜合遺傳算法與簡單遺傳算法優化性能的不同。
某河流各斷面溶解氧實測值如表1所示。
| 項目 | 斷面(j) | |||
| 1 | 2 | 3 | 4 | |
| x(km) | 8 | 28 | 36 | 56 |
| t(h) | 2.0 | 7.0 | 9.0 | 14 |
| Cj(mg/L) | 8.5 | 7.0 | 6.1 | 7.2 |
水質參數為：飽和溶解氧濃度Cs=10mg/L，初始段面濃度C0=Cs，初始斷面BOD濃度L0=20mg/L，流速u=4km/h要求估計BOD衰減系數K1、大氣復氧系數K2，使得下式的優化準則函數取得極小值：
為運用綜合遺傳算法，參數設定如下[7]：
串長L=20;
種群個數N=50;
初始溫度T0=50 ℃;
簡單遺傳算法Pc=0.6,Pm=0.003;
綜合遺傳算法Pc1=0.8，Pc2=0.5，Pm1=0.005,Pm2=0.001。
文獻[9] 計算 結果為Fmin=0.49,K1=0.056h-1,K2=0.209 5h-1，本題將適應值函數的平均值不再變化作為算法的收斂判據。兩種算法的計算 結果見表2，收斂率與遺傳代數的關系曲線見圖2。
| 計算次數 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | |
| 遺傳代數 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | |
| 收斂次數 | SGA | 3 | 6 | 6 | 9 | 12 | 10 | 15 | 18 |
| SGA-1 | 6 | 13 | 15 | 18 | 22 | 24 | 18 | 21 | |
| MAGA | 3 | 18 | 24 | 27 | 30 | 30 | 30 | 30 | |
| 注：SGA-1為帶最優個體保護的SGA。 | |||||||||
由圖2可見，經過25次迭代MAGA的收斂率達到100%，而SGA僅為40%，可見綜合遺傳算法既發揮了最優個體保護的優勢，又克服了異常個體充斥群體的弊端，同時還進行了交換變異概率的自適應調整，收斂效率要高得多。另外為驗證綜合遺傳算法的準確性，還與文獻[6]中梯度法的計算結果進行了對比(見表3)。
| 項 目 | 梯度法 | SGA算法 | MAGA算法 |
| K1(h-1) | 0.0560 | 0.0530 | 0.0560 |
| K2(h-1) | 0.2095 | 0.2085 | 0.2096 |
從表3看出MAGA算法的精度非常高。
3 結論
綜合性遺傳算法在交叉、變異、適應值函數等方面都對簡單遺傳算法的相關操作進行了改進，具有精度更高、收斂更快的特點。在水環境模型參數估值的 應用 實例中，其優勢得到了驗證。
參考 文獻：
[1]席裕賡.遺傳算法綜述[J].控制 理論 與應用,1996,13(6):697-708.
[2]金菊良，楊曉華.非線性環境模型優化的一種數值 方法 [J].環境 科學 進展,1997,12(增刊): 108-112.
[3]Dewdney K A.Exploring the field of genetic algorithms in primordial computer sea full of flibs[J].Scientific American,1985,253(5):21-32.
[4]樊會元，王尚錦.遺傳算法引入進化方向算子的一個改進及應用[J].西安 交通 大學學報,19 99,33(5):45-48.
[5]王慧，劉寶坤.一種改進的遺傳算法及應用[J].天津理工學院學報,1998,14(4):62-66.
[6]段玉倩，賀家李.遺傳算法及其改進[J].電力系統及其自動化學報,1998,10(1):39-51.
[7]丁承民， 張傳生，等.遺傳算法縱橫談[J].信息與控制，1997,26(1):40-48.
[8]Srinivas M,Patnaik L M.Adaptive probability of crossover and mutation in genetic algorithms[J].IEEE Trans on SMC,1994,24(4):656-667.
[9]程聲通，陳毓齡.環境系統 分析 [M].北京：高等 教育 出版社，1996.
使用微信“掃一掃”功能添加“谷騰環保網”
