李海英1，秦肖生2
(1.中南大學(xué)資源環(huán)境建筑工程學(xué)院，湖南長沙　410083；2.湖南大學(xué)環(huán)境工程系,湖南長沙　410082)

　　摘　要：將一種具有更高收斂速度、更少迭代次數(shù)的綜合性遺傳算法應(yīng)用于水環(huán)境模型參數(shù)估值之中，通過與簡單遺傳算法計算結(jié)果的對比驗證了新方法的有效性。
　　關(guān)鍵詞： 遺傳算法；優(yōu)化；水質(zhì)模型；參數(shù)估值
　　中圖分類號：TU991.21
　　文獻標識碼：B
　　文章編號：1000-4602(2002)05-0028-03

　　遺傳算法(SGA)應(yīng)用于環(huán)境科學(xué)領(lǐng)域的研究主要集中在對各種非線性水質(zhì)模型的參數(shù)估計［1］、水質(zhì)及水污染非線性規(guī)劃的求解［2］等，但簡單的遺傳算法在求解中存在不少問題［3］，尤其對類似水質(zhì)非線性規(guī)劃等復(fù)雜的多變量優(yōu)化問題則效率并不高，有時并不收斂或者出現(xiàn)“早熟現(xiàn)象”［4］，故提出一種綜合性遺傳算法(MAGA)。

1　遺傳算法和綜合遺傳算法

　　在利用遺傳算法求解問題時，問題的每個可能的解都被編碼成一個“染色體”，即若干個體構(gòu)成了群體(所有可能解)。算法開始時總是隨機地產(chǎn)生一些個體(即初始解)，根據(jù)預(yù)定的 目標函數(shù)對每個個體進行評價后得出一個適應(yīng)度值；基于此適應(yīng)度值選擇個體用來復(fù)制下一代，選擇操作體現(xiàn)了“適者”生存的原理，“好”的個體被復(fù)制，“壞”的則被淘汰；然后選擇出來的個體經(jīng)交叉和變異進行再組合生成新一代，這一群新個體由于繼承了上一代的一些優(yōu)良性狀，因而在性能上要優(yōu)于上一代，這樣逐步朝著更優(yōu)解方向進化5］。基本流程見圖1。
　　盡管傳統(tǒng)遺傳算法可以找到全局最優(yōu)，但在求解許多實際問題時其收斂速度還不盡人意，且操作參數(shù)的選取對結(jié)果影響巨大，故許多學(xué)者對簡單的遺傳算法進行了改進^［6、7］，在此提出一種效率較高的綜合遺傳算法。

　　① 選擇操作的改進
　　利用基于馬爾科夫鏈的定量的數(shù)學(xué)證明認為，簡單的遺傳算法不是全局收斂的，而帶有最優(yōu)個體保留的遺傳算法則是全局收斂的^［6］，故在選擇操作中采用杰出個體保護策略。?
　　根據(jù)目標函數(shù)值決定將被復(fù)制的數(shù)字串，設(shè)種群中有N個個體，將這N個個體解碼得N個適應(yīng)性函數(shù)值fi(i=1,2,3,…,N),按下述步驟復(fù)制：
　　a.令P=隨機數(shù)×∑fi?
　　
　　則復(fù)制第k個數(shù)字串。
　　將N個個體f值先按從大到小的順序排列，復(fù)制出N/2個個體到匹配池中等待交叉操作，將選出的N/2個個體進行交叉操作后放回到匹配池中，頂替排在后面的N/2個個體(即將排在后面的N/2個個體清除掉)。對匹配池中的N個個體重新按大到小的順序排列，采用杰出個體保護策略，即將父代中最優(yōu)個體放回到匹配池中頂替重新排列后的最后一個個體以保持種群中優(yōu)秀個體的存在。
　?、?適應(yīng)值函數(shù)調(diào)整?
　　在遺傳進化初期，通常會出現(xiàn)一些超常的個體，為避免“早熟現(xiàn)象”，應(yīng)將適應(yīng)函數(shù)值進行適當(dāng)調(diào)整以降低選擇強度，在此采用Paul L.Stoffa提出的模擬退火法對適應(yīng)值函數(shù)進行拉伸［7］：

　　

　　式中 ?fi——第i個個體適合度?
　　　　　?N——種群個體總數(shù)?
　　　　　?g——遺傳代數(shù)序號?
　　　　　?T——溫度?
　　　　　?T₀——初始溫度
　　從式(1)、(2)可以看出，在溫度高時(即進化前期)，適合度相近的個體產(chǎn)生后代的概率相近，而當(dāng)溫度不斷下降后，拉伸作用加強使得適合度相近的個體適合度差異放大，從而使優(yōu)秀的個體優(yōu)勢更明顯。
　?、?交叉操作的改進?
　　以單點交叉、兩點交叉和交叉位置的非等概率選取相結(jié)合作為交叉操作。當(dāng)染色體位串長度較短時，可采用整串的兩點交叉操作；而當(dāng)染色體位串長度較長時，特別是子串位數(shù)較多時可采用各個子串分別進行單點交叉操作，并引進交叉位置的非等概率選取?！　、?自適應(yīng)調(diào)整Pc和Pm
　　在簡單遺傳算法中，交換概率Pc和變異概率Pm一般取為恒定值，在進行復(fù)雜多變量優(yōu)化問題時，效率并不高，主要是因為Pc越大個體被破壞的可能性就會增加，使得具有高適應(yīng)值的個體結(jié)構(gòu)很快被破壞，Pc過小會使搜索緩慢而停滯不前；Pm過大遺傳算法就變成了純粹的隨機搜索算法，Pm過小又不易產(chǎn)生新的個體，因此如何選擇Pc和Pm是保證算法成功的關(guān)鍵。
　　有學(xué)者提出Pc和Pm隨適應(yīng)度值自動改變的方法。對于高于平均適應(yīng)值 的解，令Pc和Pm取值小一些，使解受破壞的可能性小，而對低于平均適應(yīng)值的解，令Pc和Pm取值大一些以防止遺傳算法陷入局部解。因此按參考文獻^［8］提出的方法進行調(diào)整：

　　　　

　　式中 ?Pc1=0.9,Pc2=0.7,Pm1=0.01,Pm2=0.001。?
　　⑤ 變量區(qū)間優(yōu)化(動態(tài)變量編碼)?
　　一般來說，自變量參數(shù)(即所求未知參數(shù))的范圍越小搜索的速度就越快，也就更加容易確定最優(yōu)解。設(shè)新求出的優(yōu)化變量值為?x′，將-｜x′｜以及｜x′｜值作為下一次x求解的取值區(qū)間的上下限，重新進行計算。?
　　⑥ 終止條件的選擇
　　經(jīng)典的方法是固定遺傳代數(shù)，到達后即終止，本文采用改進的方法，即根據(jù)連續(xù)幾代個體平均適合度不變(其差小于某個極小的閾值)作為終止的條件。

2　實例驗證

　　利用文獻^［9］中水質(zhì)模型的參數(shù)估值一實例來比較綜合遺傳算法與簡單遺傳算法優(yōu)化性能的不同。
　　某河流各斷面溶解氧實測值如表1所示。

表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

　　水質(zhì)參數(shù)為：飽和溶解氧濃度Cs=10mg/L，初始段面濃度C0=Cs，初始斷面BOD濃度L0=20mg/L，流速u=4km/h要求估計BOD衰減系數(shù)K1、大氣復(fù)氧系數(shù)K2，使得下式的優(yōu)化準則函數(shù)取得極小值：?

　　

　　為運用綜合遺傳算法，參數(shù)設(shè)定如下［7］：
　　串長L=20；?
　　種群個數(shù)N=50；?
　　初始溫度T0=50 ℃；
　　簡單遺傳算法Pc=0.6,Pm=0.003；
　　綜合遺傳算法Pc1=0.8，Pc2=0.5，Pm1=0.005,Pm²=0.001。
　　文獻^［9］計算結(jié)果為Fmin=0.49,K1=0.056h^-1,K2=0.209 5h-1，本題將適應(yīng)值函數(shù)的平均值不再變化作為算法的收斂判據(jù)。兩種算法的計算 結(jié)果見表2，收斂率與遺傳代數(shù)的關(guān)系曲線見圖2。

表2 SGA、SGA-1、M AGA法計算結(jié)果 計算次數(shù) 30 30 30 30 30 30 30 30 遺傳代數(shù) 5 10 15 20 25 30 35 40 收斂次數(shù) 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為帶最優(yōu)個體保護的SGA。

　　由圖2可見，經(jīng)過25次迭代MAGA的收斂率達到100%，而SGA僅為40%，可見綜合遺傳算法既發(fā)揮了最優(yōu)個體保護的優(yōu)勢，又克服了異常個體充斥群體的弊端，同時還進行了交換變異概率的自適應(yīng)調(diào)整，收斂效率要高得多。另外為驗證綜合遺傳算法的準確性，還與文獻［6］中梯度法的計算結(jié)果進行了對比(見表3)。

表3 計算結(jié)果對比 項 目 梯度法 SGA算法 MAGA算法 K₁(h^-1) 0.0560 0.0530 0.0560 K₂(h^-1) 0.2095 0.2085 0.2096

　　從表3看出MAGA算法的精度非常高。

3 結(jié)論

　　 綜合性遺傳算法在交叉、變異、適應(yīng)值函數(shù)等方面都對簡單遺傳算法的相關(guān)操作進行了改進，具有精度更高、收斂更快的特點。在水環(huán)境模型參數(shù)估值的應(yīng)用實例中，其優(yōu)勢得到了驗證。

參考文獻：

　?。?］席裕賡.遺傳算法綜述［J］.控制理論與應(yīng)用,1996,13(6):697-708.
　　［2］金菊良，楊曉華.非線性環(huán)境模型優(yōu)化的一種數(shù)值方法［J］.環(huán)境科學(xué)進展,1997,12(增刊): 108-112.
　?。?］Dewdney K A.Exploring the field of genetic algorithms in primordial computer sea full of flibs［J］.Scientific American,1985,253(5):21-32.
　?。?］樊會元，王尚錦.遺傳算法引入進化方向算子的一個改進及應(yīng)用［J］.西安交通大學(xué)學(xué)報,19 99,33(5):45-48.
　?。?］王慧，劉寶坤.一種改進的遺傳算法及應(yīng)用［J］.天津理工學(xué)院學(xué)報,1998,14(4):62-66.
　?。?］段玉倩，賀家李.遺傳算法及其改進［J］.電力系統(tǒng)及其自動化學(xué)報,1998,10(1):39-51.
　?。?］丁承民， 張傳生，等.遺傳算法縱橫談［J］.信息與控制，1997,26(1):40-48.
　?。?］Srinivas M,Patnaik L M.Adaptive probability of crossover and mutation in genetic algorithms［J］.IEEE Trans on SMC,1994,24(4):656-667.
　?。?］程聲通，陳毓齡.環(huán)境系統(tǒng)分析［M］.北京：高等教育出版社，1996.

---

　　電　　話：(0731)8830832(H)?
　　收稿日期：2001-09-28