田一梅，李江濤，戴雄奇，李鴻
(天津大學(xué)環(huán)境工程系，天津300072)

　　摘　要：對(duì)遺傳算法應(yīng)用于求解供水系統(tǒng)的優(yōu)化調(diào)度問(wèn)題進(jìn)行了探討，并提出了對(duì)連續(xù)/離散混合變量的編碼方法。給出了一個(gè)遺傳算法應(yīng)用在優(yōu)化調(diào)度方面的實(shí)例，結(jié)果表明該算法具有很強(qiáng)的適應(yīng)性，可實(shí)際應(yīng)用于在線優(yōu)化調(diào)度。
　　關(guān)鍵詞：遺傳算法；供水管網(wǎng)；優(yōu)化調(diào)度
　　中圖分類號(hào)：TU991.56
　　文獻(xiàn)標(biāo)識(shí)碼：C
　　文章編號(hào)：1000-4602(2001)12-0063-03

　　城市供水管網(wǎng)系統(tǒng)的優(yōu)化調(diào)度是根據(jù)管網(wǎng)實(shí)時(shí)運(yùn)行狀態(tài)確定今后一個(gè)調(diào)度期中水泵的運(yùn)行狀況，在保證供水服務(wù)質(zhì)量的前提下，使供水系統(tǒng)獲得最佳效益。通?？梢圆捎脙煞N方法求解，即直接優(yōu)化和兩級(jí)優(yōu)化，前者以泵站內(nèi)各種泵的開(kāi)機(jī)臺(tái)數(shù)和流量為變量直接確定優(yōu)化調(diào)度方案；后者則分為兩級(jí)求解，在確定各水廠最佳供水量、供水壓力的基礎(chǔ)上，給出各泵站水泵的最佳開(kāi)機(jī)方案。因此，供水系統(tǒng)優(yōu)化調(diào)度的核心就是求解一個(gè)多目標(biāo)優(yōu)化問(wèn)題，而選擇一種適當(dāng)?shù)慕夥ň统蔀閱?wèn)題的關(guān)鍵。由于供水系統(tǒng)優(yōu)化調(diào)度的目標(biāo)函數(shù)及約束條件都是非線性的，雖然可將目標(biāo)函數(shù)分段線性化并用線性優(yōu)化方法對(duì)其求解，但求得的結(jié)果難以令人滿意。而直接采用非線性優(yōu)化方法一般又很難保證求得全局最優(yōu)解，特別是在直接優(yōu)化調(diào)度中由于存在連續(xù)/離散混合變量，且當(dāng)變量多、約束條件復(fù)雜苛刻時(shí)往往只能求出局部最優(yōu)解，要想取得全局最優(yōu)解則需不斷改變初始點(diǎn)，在多個(gè)局部最優(yōu)解中擇其最優(yōu)，顯然這難于滿足在線優(yōu)化調(diào)度的要求。而兩級(jí)優(yōu)化調(diào)度由于將問(wèn)題分解，變量少且單一，約束條件寬松，故求解容易。但有些供水系統(tǒng)因泵站內(nèi)恒速泵種類較少，又沒(méi)有設(shè)置調(diào)速泵，因此很難確定出滿足第一級(jí)優(yōu)化要求的泵站開(kāi)機(jī)方案，故不適于采用兩級(jí)優(yōu)化調(diào)度。由此可見(jiàn)，尋求更好的優(yōu)化算法是供水系統(tǒng)優(yōu)化調(diào)度中的一個(gè)關(guān)鍵問(wèn)題。

1　直接優(yōu)化調(diào)度數(shù)學(xué)模型

　　直接優(yōu)化調(diào)度是以各泵站投入運(yùn)行的水泵單機(jī)流量和開(kāi)機(jī)臺(tái)數(shù)為變量，將水源、水泵及管網(wǎng)作為一個(gè)有機(jī)整體來(lái)建立模型。由于供水系統(tǒng)中各水源的供水能力、供水成本不同以及投入運(yùn)行的水泵組合方式不同，必然存在著多種不同的供水方案可滿足要求，因此就存在著如何經(jīng)濟(jì)、合理地調(diào)整各水廠、水泵之間的相對(duì)關(guān)系，既使節(jié)點(diǎn)能量浪費(fèi)最小、壓力分布均勻，又使經(jīng)濟(jì)效益最佳以達(dá)到系統(tǒng)整體最優(yōu)的問(wèn)題。
　　直接優(yōu)化調(diào)度問(wèn)題的數(shù)學(xué)模型表達(dá)如下：
　　目標(biāo)函數(shù)

　　　　　

　　　　　

　　式中f1——管網(wǎng)各壓力監(jiān)測(cè)點(diǎn)供水壓力與該點(diǎn)所需壓力之差的平方和
　　　　f2——供水系統(tǒng)的凈收益，即供水收益與制水成本、送水電費(fèi)之差
　　　　 r——換算系數(shù)
　 Hk、Hkf——分別為管網(wǎng)宏觀模型所確定的監(jiān)測(cè)點(diǎn)k的壓力和該點(diǎn)所需的最小壓力
　S1i、S2i——分別為水廠i的供水水價(jià)和單位制水成本
　S3i、σi——分別為水廠i的基本電價(jià)和耗電電價(jià)
　Nij、Nijmax——分別為水廠i中水泵j投入運(yùn)行的臺(tái)數(shù)和可開(kāi)機(jī)臺(tái)數(shù)
　Qi、Qimin、Qimax——水廠i的供水量及供水量范圍
　Qij、Qijmin、Qijmax——分別為水廠i中水泵j的供水量和該泵高效段流量
　H(Qij)、η(Qij)——分別為水廠i、水泵j在流量為Qij時(shí)的供水揚(yáng)程和供水效率
　　　　　δij——水廠i、水泵j的機(jī)電傳動(dòng)效率
　　　　　Zij——水廠i、水泵j的吸水揚(yáng)程與壓力表前水頭損失之和

2　用遺傳算法求解

　　某城市供水系統(tǒng)有2個(gè)水廠、7個(gè)管網(wǎng)壓力監(jiān)測(cè)點(diǎn)，管網(wǎng)中最不利點(diǎn)的壓力按200 kPa計(jì)算。該市用水量約35×10⁴m³/d，各水廠供水量和水泵參數(shù)見(jiàn)表1。

表1　各水廠供水量和水泵參數(shù) 項(xiàng)目 水廠一 水廠二 水泵型號(hào) 14SA—10B 12SH—9 12SH—9A 16SA—9C 14SA—10B 水泵可開(kāi)機(jī)臺(tái)數(shù) 5 2 2 4 3 水泵高效段流量(L/s) 350～250 270～160 248～147 350～250 350～250 水廠供水量范圍(L/s) 1 750～0 3 486～0

　　遺傳算法求解直接優(yōu)化調(diào)度問(wèn)題過(guò)程如下：
2.1　編碼
　　遺傳算法的工作對(duì)象是染色體字符串，首先對(duì)染色體進(jìn)行編碼。由于水泵臺(tái)數(shù)是離散變量，可直接采用二進(jìn)制編碼；而單泵流量屬連續(xù)變量，需經(jīng)離散化處理后再采用二進(jìn)制編碼。為使水泵臺(tái)數(shù)在給定的范圍內(nèi)，作者定義了一套編碼規(guī)則列于表2。

表2　編碼規(guī)則 十進(jìn)制數(shù) 1 2 3 4 5 6 7 拆分 1 1+1 3 3+1 3+1+1 3+1+1+1 7 二進(jìn)制數(shù) 1 1,1 11 11,1 11,1,1 11,1,1, 111 二進(jìn)制位數(shù) 1 1+1 2 2+1 2+1+1 2+1+1+1 3

　　表1中5種型號(hào)水泵可開(kāi)機(jī)臺(tái)數(shù)分別為：5、2、2、4、3，故由表2可知，染色體上代表水泵臺(tái)數(shù)的基因位數(shù)為：4+2+2+3+2=13位。
　　對(duì)于連續(xù)變量，根據(jù)單泵流量(Qij)的范圍［0，350］和水泵的特性并兼顧問(wèn)題求解的難易程度，取單泵流量離散化后的精度為0.68，故由二進(jìn)制編碼精度公式可計(jì)算出用9位二進(jìn)制表示每一個(gè)單泵流量，所以染色體上代表單泵流量的基因位數(shù)為45位。
　　水泵臺(tái)數(shù)的基因位數(shù)與單泵流量的基因位數(shù)之和即為染色體總長(zhǎng)度：13+45=58位。
2.2　構(gòu)造適應(yīng)度函數(shù)
　　對(duì)于所求的有約束最小化問(wèn)題，可采用序列無(wú)約束優(yōu)化法的外罰函數(shù)將其轉(zhuǎn)為無(wú)約束優(yōu)化問(wèn)題，同時(shí)按照遺傳算法的要求將極小值問(wèn)題轉(zhuǎn)化為極大值問(wèn)題求解，并保證適應(yīng)度函數(shù)始終為正值。故先將上述有約束非線性優(yōu)化調(diào)度問(wèn)題式(1)、(2)整理為標(biāo)準(zhǔn)的非線性規(guī)劃形式：

　　　

　　　

　　再將一個(gè)大數(shù)(常數(shù)C)與目標(biāo)函數(shù)之差作為適應(yīng)度函數(shù)，即：

　　　　max［C-P(X,M)］　　　　(5)
2.3　求解及結(jié)果分析
　　根據(jù)上述分析編制和調(diào)試了遺傳算法求解優(yōu)化調(diào)度問(wèn)題的有關(guān)程序，并對(duì)上述實(shí)例進(jìn)行計(jì)算，主要計(jì)算步驟如下：
　?、匐S機(jī)建立由字符串(即二進(jìn)制代碼串表示的水泵開(kāi)機(jī)臺(tái)數(shù)和單泵流量)組成的初始群體；
　?、谟?jì)算各個(gè)體的適應(yīng)度max［C-P(X，M)］；
　?、鄹鶕?jù)遺傳概率，利用復(fù)制、交換、突變產(chǎn)生新群體；
　?、芊磸?fù)執(zhí)行②、③后，一旦達(dá)到終止條件，直接輸出最優(yōu)解(見(jiàn)表3)。

表3　優(yōu)化調(diào)度最優(yōu)解 　 一廠 二廠 監(jiān)測(cè)點(diǎn) 所需壓力(kPa) 優(yōu)化計(jì)算壓力(kPa) 水泵型號(hào) 14SA—10B 12SH—9 12SH—9A 16SA—9C 14SA—10B 1 314.5 306.2 開(kāi)機(jī)臺(tái)數(shù) 4(11，0，1) 1(0，1) 2(1，1) 0(0，0) 1(01) 2 297.4 293.2 單泵流量(L/s) 350(111111111) 172(11111011) 133(11000010) 0(000000000) 285(110100000) 3 218.8 215.1 水廠供水量(L/s) 1400 723 4 208.4 205.2 所需供水壓力(kPa) 403.4 473.8 5 319.8 317.8 優(yōu)化計(jì)算壓(kPa) 415.8 452.9 6 401.3 396.7 管網(wǎng)需水量(L/s) 2 149 管網(wǎng)供水量 2 123 供需水量差 -26 7 356.5 353.1 注：括號(hào)內(nèi)為解變量的二進(jìn)制代碼。

結(jié)果分析：
　　①將最優(yōu)解代入優(yōu)化調(diào)度原問(wèn)題式(1)、(2)，滿足原問(wèn)題的要求，證明用遺傳算法求解連續(xù)/離散混合變量問(wèn)題是行之有效的。
　　②遺傳算法適用面寬，對(duì)問(wèn)題要求很少，如對(duì)目標(biāo)函數(shù)只要求有定義，不要求其連續(xù)、可微，對(duì)約束條件也無(wú)任何限制；而采用傳統(tǒng)的數(shù)學(xué)規(guī)劃方法，當(dāng)約束條件比較苛刻時(shí)進(jìn)入可行域比較困難。故該算法能夠克服傳統(tǒng)優(yōu)化方法的一些弱點(diǎn)，可以解決許多傳統(tǒng)方法不能解決的問(wèn)題。
　?、圻z傳算法在整個(gè)解的空間內(nèi)搜索，具有較大的把握求得全局最優(yōu)解。
　　④遺傳算法計(jì)算時(shí)間較短(僅需2～3 min)，滿足在線調(diào)度要求。

3 結(jié)語(yǔ)

　　綜上所述，用遺傳算法求解輸配水系統(tǒng)優(yōu)化調(diào)度問(wèn)題得到的結(jié)果是令人滿意的，這說(shuō)明遺傳算法是一種比較好的搜索算法，它不僅快速、準(zhǔn)確、搜索遍及全空間，具有較大的把握得到全局最優(yōu)點(diǎn)，而且不用對(duì)原問(wèn)題作過(guò)多的分析處理，具有很高的適應(yīng)性和很強(qiáng)的魯棒性。當(dāng)然遺傳算法也存在一些缺點(diǎn)，如遺傳算法的操作參數(shù)和優(yōu)化結(jié)果相互之間比較獨(dú)立，故對(duì)于操作參數(shù)的選取比較困難；此外由于遺傳算法還處于發(fā)展的初級(jí)階段，尚有許多問(wèn)題需要研究和探討，比如對(duì)于大型復(fù)雜問(wèn)題的收斂速度還比較慢等。對(duì)于上述問(wèn)題，前者可通過(guò)使用者編程以自動(dòng)尋求不同問(wèn)題的最佳操作參數(shù)；后者則有待于該算法的不斷改進(jìn)和進(jìn)一步
完善。

參考文獻(xiàn)：

　?。?］趙新華.城市配水系統(tǒng)優(yōu)化運(yùn)行的研究［J］.中國(guó)給水排水，1992，8(3)：18-22.
　?。?］王平洋.加快遺傳模糊算法的搜索過(guò)程［J］.電網(wǎng)技術(shù)，1999，23(5)：3-10.
　?。?］周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，1999.

---

　　電 話：(022)27400830
　　收稿日期：2001-06-15