綜合性遺傳算法用于水質(zhì)模型參數(shù)估值

1、綜合性遺傳算法用于水質(zhì)模型參數(shù)估值             摘要將一種具有更高收斂速度、更少迭代次數(shù)的綜合性遺傳算法應(yīng)用于水環(huán)境模型參數(shù)估值之中，通過(guò)與簡(jiǎn)單遺傳算法計(jì)算結(jié)果的對(duì)比驗(yàn)證了新方法的有效性。 關(guān)鍵詞遺傳算法 優(yōu)化 水質(zhì)模型 參數(shù)估值 遺傳算法(SGA)應(yīng)用于環(huán)境科學(xué)領(lǐng)域的研究主要集中在對(duì)各種非線性水質(zhì)模型的參數(shù)估計(jì)1、水質(zhì)及水污染非線性規(guī)劃的求解2等，但簡(jiǎn)單的遺傳算法在求解中存在不少問(wèn)題3，尤其對(duì)類似水質(zhì)非線性規(guī)劃等復(fù)雜的多變量?jī)?yōu)化問(wèn)題則效率并不高，有時(shí)并不收斂或者

2、出現(xiàn)“早熟現(xiàn)象”4，故提出一種綜合性遺傳算法(MAGA)。1遺傳算法和綜合遺傳算法在利用遺傳算法求解問(wèn)題時(shí)，問(wèn)題的每個(gè)可能的解都被編碼成一個(gè)“染色體”，即若干個(gè)體構(gòu)成了群體(所有可能解)。算法開始時(shí)總是隨機(jī)地產(chǎn)生一些個(gè)體(即初始解)，根據(jù)預(yù)定的 目標(biāo)函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)后得出一個(gè)適應(yīng)度值；基于此適應(yīng)度值選擇個(gè)體用來(lái)復(fù)制下一代，選擇操作體現(xiàn)了“適者”生存的原理，“好”的個(gè)體被復(fù)制，“壞”的則被淘汰；然后選擇出來(lái)的個(gè)體經(jīng)交叉和變異進(jìn)行再組合生成新一代，這一群新個(gè)體由于繼承了上一代的一些優(yōu)良性狀，因而在性能上要優(yōu)于上一代，這樣逐步朝著更優(yōu)解方向進(jìn)化5?；玖鞒桃妶D1。盡管傳統(tǒng)遺傳算法可以找到全局最

3、優(yōu)，但在求解許多實(shí)際問(wèn)題時(shí)其收斂速度還不盡人意，且操作參數(shù)的選取對(duì)結(jié)果影響巨大，故許多學(xué)者對(duì)簡(jiǎn)單的遺傳算法進(jìn)行了改進(jìn)6、7，在此提出一種效率較高的綜合遺傳算法。 選擇操作的改進(jìn)利用基于馬爾科夫鏈的定量的數(shù)學(xué)證明認(rèn)為，簡(jiǎn)單的遺傳算法不是全局收斂的，而帶有最優(yōu)個(gè)體保留的遺傳算法則是全局收斂的6，故在選擇操作中采用杰出個(gè)體保護(hù)策略。根據(jù)目標(biāo)函數(shù)值決定將被復(fù)制的數(shù)字串，設(shè)種群中有N個(gè)個(gè)體，將這N個(gè)個(gè)體解碼得N個(gè)適應(yīng)性函數(shù)值fi(i=1,2,3,N),按下述步驟復(fù)制：a.令P=隨機(jī)數(shù)×fi則復(fù)制第k個(gè)數(shù)字串。將N個(gè)個(gè)體f值先按從大到小的順序排列，復(fù)制出N/2個(gè)個(gè)體到匹配池中等待交叉操作，將選出

4、的N/2個(gè)個(gè)體進(jìn)行交叉操作后放回到匹配池中，頂替排在后面的N/2個(gè)個(gè)體(即將排在后面的N/2個(gè)個(gè)體清除掉)。對(duì)匹配池中的N個(gè)個(gè)體重新按大到小的順序排列，采用杰出個(gè)體保護(hù)策略，即將父代中最優(yōu)個(gè)體放回到匹配池中頂替重新排列后的最后一個(gè)個(gè)體以保持種群中優(yōu)秀個(gè)體的存在。 適應(yīng)值函數(shù)調(diào)整在遺傳進(jìn)化初期，通常會(huì)出現(xiàn)一些超常的個(gè)體，為避免“早熟現(xiàn)象”，應(yīng)將適應(yīng)函數(shù)值進(jìn)行適當(dāng)調(diào)整以降低選擇強(qiáng)度，在此采用Paul L.Stoffa提出的模擬退火法對(duì)適應(yīng)值函數(shù)進(jìn)行拉伸7： 式中 fi第i個(gè)個(gè)體適合度N種群個(gè)體總數(shù)g遺傳代數(shù)序號(hào)T溫度T0初始溫度從式(1)、(2)可以看出，在溫度高時(shí)(即進(jìn)化前期)，適合度相近的個(gè)體

5、產(chǎn)生后代的概率相近，而當(dāng)溫度不斷下降后，拉伸作用加強(qiáng)使得適合度相近的個(gè)體適合度差異放大，從而使優(yōu)秀的個(gè)體優(yōu)勢(shì)更明顯。 交叉操作的改進(jìn)以單點(diǎn)交叉、兩點(diǎn)交叉和交叉位置的非等概率選取相結(jié)合作為交叉操作。當(dāng)染色體位串長(zhǎng)度較短時(shí)，可采用整串的兩點(diǎn)交叉操作；而當(dāng)染色體位串長(zhǎng)度較長(zhǎng)時(shí)，特別是子串位數(shù)較多時(shí)可采用各個(gè)子串分別進(jìn)行單點(diǎn)交叉操作，并引進(jìn)交叉位置的非等概率選取。 自適應(yīng)調(diào)整Pc和Pm在簡(jiǎn)單遺傳算法中，交換概率Pc和變異概率Pm一般取為恒定值，在進(jìn)行復(fù)雜多變量?jī)?yōu)化問(wèn)題時(shí)，效率并不高，主要是因?yàn)镻c越大個(gè)體被破壞的可能性就會(huì)增加，使得具有高適應(yīng)值的個(gè)體結(jié)構(gòu)很快被破壞，Pc過(guò)小會(huì)使搜索緩慢而停滯不前；Pm

6、過(guò)大遺傳算法就變成了純粹的隨機(jī)搜索算法，Pm過(guò)小又不易產(chǎn)生新的個(gè)體，因此如何選擇Pc和Pm是保證算法成功的關(guān)鍵。有學(xué)者提出Pc和Pm隨適應(yīng)度值自動(dòng)改變的方法。對(duì)于高于平均適應(yīng)值 的解，令Pc和Pm取值小一些，使解受破壞的可能性小，而對(duì)低于平均適應(yīng)值的解，令Pc和Pm取值大一些以防止遺傳算法陷入局部解。因此按參考文獻(xiàn)8提出的方法進(jìn)行調(diào)整： 式中 Pc1=0.9,Pc2=0.7,Pm1=0.01,Pm2=0.001。 變量區(qū)間優(yōu)化(動(dòng)態(tài)變量編碼)一般來(lái)說(shuō)，自變量參數(shù)(即所求未知參數(shù))的范圍越小搜索的速度就越快，也就更加容易確定最優(yōu)解。設(shè)新求出的優(yōu)化變量值為x，將-x以及x值作為下一次x求解的取值區(qū)

7、間的上下限，重新進(jìn)行計(jì)算。 終止條件的選擇經(jīng)典的方法是固定遺傳代數(shù)，到達(dá)后即終止，本文采用改進(jìn)的方法，即根據(jù)連續(xù)幾代個(gè)體平均適合度不變(其差小于某個(gè)極小的閾值)作為終止的條件。         2實(shí)例驗(yàn)證利用文獻(xiàn)9中水質(zhì)模型的參數(shù)估值一實(shí)例來(lái)比較綜合遺傳算法與簡(jiǎn)單遺傳算法優(yōu)化性能的不同。某河流各斷面溶解氧實(shí)測(cè)值如表1所示。表1 某河流各斷面溶解氧實(shí)測(cè)值水質(zhì)參數(shù)為：飽和溶解氧濃度Cs=10mg/L，初始段面濃度C0=Cs，初始斷面BOD濃度L0=20mg/L，流速u=4km/h要求估計(jì)BOD衰減系數(shù)K1、大氣復(fù)氧系數(shù)

8、K2，使得下式的優(yōu)化準(zhǔn)則函數(shù)取得極小值：為運(yùn)用綜合遺傳算法，參數(shù)設(shè)定如下7：串長(zhǎng)L=20；種群個(gè)數(shù)N=50；初始溫度T0=50 ；簡(jiǎn)單遺傳算法Pc=0.6,Pm=0.003；綜合遺傳算法Pc1=0.8，Pc2=0.5，Pm1=0.005,Pm2=0.001。文獻(xiàn)9計(jì)算結(jié)果為Fmin=0.49,K1=0.056h-1,K2=0.209 5h-1，本題將適應(yīng)值函數(shù)的平均值不再變化作為算法的收斂判據(jù)。兩種算法的計(jì)算 結(jié)果見表2，收斂率與遺傳代數(shù)的關(guān)系曲線見圖2。表2 SGA、SGA-1、M AGA法計(jì)算結(jié)果由圖2可見，經(jīng)過(guò)25次迭代MAGA的收斂率達(dá)到100%，而SGA僅為40%，可見綜合遺傳算法既

9、發(fā)揮了最優(yōu)個(gè)體保護(hù)的優(yōu)勢(shì)，又克服了異常個(gè)體充斥群體的弊端，同時(shí)還進(jìn)行了交換變異概率的自適應(yīng)調(diào)整，收斂效率要高得多。另外為驗(yàn)證綜合遺傳算法的準(zhǔn)確性，還與文獻(xiàn)6中梯度法的計(jì)算結(jié)果進(jìn)行了對(duì)比(見表3)。表3  計(jì)算結(jié)果對(duì)比從表3看出MAGA算法的精度非常高。3  結(jié)論 綜合性遺傳算法在交叉、變異、適應(yīng)值函數(shù)等方面都對(duì)簡(jiǎn)單遺傳算法的相關(guān)操作進(jìn)行了改進(jìn)，具有精度更高、收斂更快的特點(diǎn)。在水環(huán)境模型參數(shù)估值的應(yīng)用實(shí)例中，其優(yōu)勢(shì)得到了驗(yàn)證。參考文獻(xiàn)：1席裕賡.遺傳算法綜述J.控制理論與應(yīng)用,1996,13(6):697-708.2金菊良，楊曉華.非線性環(huán)境模型優(yōu)化的一種數(shù)值方法J.環(huán)境科學(xué)

10、進(jìn)展,1997,12(增刊): 108-112.3Dewdney K A.Exploring the field of genetic algorithms in primordial computer sea full of flibsJ.Scientific American,1985,253(5):21-32.4樊會(huì)元，王尚錦.遺傳算法引入進(jìn)化方向算子的一個(gè)改進(jìn)及應(yīng)用J.西安交通大學(xué)學(xué)報(bào),19 99,33(5):45-48.5王慧，劉寶坤.一種改進(jìn)的遺傳算法及應(yīng)用J.天津理工學(xué)院學(xué)報(bào),1998,14(4):62-66.6段玉倩，賀家李.遺傳算法及其改進(jìn)J.電力系統(tǒng)及其自動(dòng)化學(xué)報(bào),1998,10(1):39-51.7丁承民， 張傳生，等.遺傳算法縱橫談J.信息與控制，1997,26(1):40-48.8Sr