戴雄奇
（深圳市自來水集團(tuán)有限公司供水調(diào)度中心）

　　摘　要 本文首先簡要介紹了遺傳算法的基本思想和步驟：繼而探討了如何將遺傳算法應(yīng)用于求解供水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)問題，并提出了對(duì)連續(xù)／離散混合變量的編碼方法；最后將遺傳算法應(yīng)用于一個(gè)供水管網(wǎng)改擴(kuò)建實(shí)例，效果比較明顯。該算例表明該算法具有很強(qiáng)的適應(yīng)性，可實(shí)際應(yīng)用于管網(wǎng)改擴(kuò)建優(yōu)化設(shè)。
　　關(guān)鍵詞 遺傳算法 供水管網(wǎng) 改擴(kuò)建優(yōu)化

1 引言

　　城市供水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)是基于對(duì)現(xiàn)有管網(wǎng)的工況正確分析、評(píng)價(jià)的基礎(chǔ)上進(jìn)行的，由于供水管網(wǎng)改擴(kuò)建設(shè)計(jì)是一個(gè)復(fù)雜的多元系統(tǒng)，不僅目標(biāo)函數(shù)比較復(fù)雜，受許多因素的影響和制約，而且優(yōu)化設(shè)計(jì)模型中加壓泵站的水泵臺(tái)數(shù)為整型變量，管道管徑為離散型變量，是一類混合離散變量優(yōu)化問題。
　　對(duì)于供水管網(wǎng)改擴(kuò)建的優(yōu)化設(shè)計(jì)的求解，到目前為止，國內(nèi)外學(xué)者已經(jīng)提出了不少方法，這些方法均使用數(shù)學(xué)規(guī)劃技術(shù)尋找最優(yōu)解。不少方法假定，設(shè)計(jì)變量是連續(xù)的，且目標(biāo)函數(shù)具有可導(dǎo)性，但實(shí)際上，混合離散優(yōu)化問題的特殊性使這些求解方法往往難以獲得原目標(biāo)函數(shù)真正的最優(yōu)解。為外，該問題也是一個(gè)非線性規(guī)劃問題，非線性規(guī)劃至今沒有一個(gè)成熟算法，即使有些方法，當(dāng)被用于供水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)問題時(shí)，往往收斂到局部最優(yōu)解，很難收斂到全局最優(yōu)解。為了克服數(shù)學(xué)規(guī)劃方法用于管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)所帶來的缺陷，本文提出了一種人工智能性算法，即含有交叉和變異等算子的遺傳算法。

2 遺傳算法的基本思想

　　遺傳算法（Genetic Algorithm, GA）是基于人類補(bǔ)會(huì)的進(jìn)化過程，它首先利用隨機(jī)力式在個(gè)空間內(nèi)產(chǎn)生一初始群體（祖先），即多個(gè)初始點(diǎn)，群體中每個(gè)個(gè)體稱為染色體，它對(duì)應(yīng)有優(yōu)化問題的一個(gè)可能解，染色體的最小組成元素就稱為基因它對(duì)應(yīng)可能解
某一特征，即設(shè)計(jì)變量。染色體的評(píng)價(jià)函數(shù)值反映可能解的優(yōu)劣，按照優(yōu)勝劣汰原則對(duì)染色體進(jìn)行選擇，相對(duì)“好”的個(gè)體得以繁殖，相對(duì)“差”的個(gè)體將死亡，因此群體整體的性能，通過選擇、雜交、突變等過程將趨于改善，經(jīng)過若干代繁衍進(jìn)化就可使群體性能趨于最佳^[1]。
2．1 遺傳算法的基本步驟
　?。?）編碼：二進(jìn)制編碼方法是遺計(jì)算法中最常用的一種編碼方法，它使用的編碼符號(hào)是由二進(jìn)制符號(hào)O和1所組成的二值符號(hào)集{0，1}，它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)串。二進(jìn)制編碼符號(hào)串的長度與問題所要求的求解精度有關(guān)，假設(shè)某一參數(shù)的取值范圍是[Umin，Umax]，用長度為λ的二進(jìn)制編碼符號(hào)串來表示該參數(shù)，它總共能夠產(chǎn)生2種不同的編碼。
　　二進(jìn)制編碼的編碼精度為：δ=[Umax-Umin]/2^λ-1
　　假設(shè)某一個(gè)體的編碼是：X：bλbλ-1bλ-2∧b2b1
　　則對(duì)應(yīng)的解碼公式為：x=Umin+[bi.2i-1).[lUmax-Umin]/[2^λ-1]
　　(2) 產(chǎn)生初始群體：由計(jì)算機(jī)按隨機(jī)方法從可能解中產(chǎn)生給定數(shù)量的二進(jìn)制代碼串，構(gòu)成一個(gè)原始的祖先群體，其中的每個(gè)二進(jìn)制代碼串代表了這一群體的一位祖先，對(duì)每位祖先（可行解）計(jì)算其相應(yīng)的函數(shù)值F1。按F1的大小來評(píng)價(jià)這位祖先的染色體的素質(zhì)。
　?。?）計(jì)算適應(yīng)度函數(shù)：最優(yōu)化問題可分為兩大類，類為求目標(biāo)標(biāo)明函數(shù)的個(gè)局的最大值，另一類為求目標(biāo)函數(shù)的全局最小值。對(duì)于這兩類優(yōu)化問題，由解空間中某一點(diǎn)的目標(biāo)函數(shù)值f（X）到搜索空間中對(duì)應(yīng)個(gè)體的適應(yīng)度函數(shù)值F（X）要通過適當(dāng)?shù)姆椒右赞D(zhuǎn)換。在遺傳算法中，群體的進(jìn)化過程就是以群體中各個(gè)個(gè)體的適應(yīng)度為依據(jù)，通過個(gè)反復(fù)迭代過程，不斷地尋求出適應(yīng)度較大的個(gè)體，最終就可得到問題的最優(yōu)解或近似最優(yōu)解。
　　（4）選擇：這一步模擬生物進(jìn)化的自然選擇功能。從原始群體中隨機(jī)取一對(duì)個(gè)體作為繁殖后代的雙親，選種的規(guī)則是適應(yīng)度值Fi越大的個(gè)體，賦予的選擇概率Pc越大，一般P1∝Fi即適應(yīng)度值高的個(gè)體有更多的繁殖后代的機(jī)會(huì)，以使優(yōu)良特性得以遺傳和保留。
　　（5）交叉：遺傳算法中所謂交義，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換某部分基因，從而形成兩個(gè)新的個(gè)體，它以一定的概率Pc在個(gè)體編碼串中隨機(jī)設(shè)置一個(gè)交義點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)個(gè)體的染色體。
　?。?）變異：突變是用來模擬生物在自然的遺傳環(huán)境中，由于各種偶然因素引起的基因突變，即將個(gè)體染色體編碼串中的某些基因值用其他等位基因來替換，從而形成個(gè)新的個(gè)體。
　　綜上幾步：通過選擇、交叉、變異得到的新一代群體，將替代上一代群體，一般說來新的群體的平均素質(zhì)可望比上一代群體素質(zhì)要好。不斷重復(fù)迭代上述過程，各代群體的優(yōu)良基因成份逐漸積累，群體的平均適應(yīng)度值和最優(yōu)個(gè)體的適應(yīng)度值不斷上升，直到迭代過程收斂（適度值趨于穩(wěn)定）即找到了最優(yōu)解。

3 遺傳算法在供水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)中的應(yīng)用

3．1 城市供水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)數(shù)學(xué)模型
　　改擴(kuò)建管網(wǎng)，由于新舊設(shè)施共存，各部分相互牽連、互相影響，構(gòu)成一個(gè)復(fù)雜的大系統(tǒng)，憑經(jīng)驗(yàn)的定性分析無法保證管網(wǎng)系統(tǒng)設(shè)計(jì)的質(zhì)量，只有建立切合實(shí)際情況的數(shù)學(xué)模型，通過科學(xué)計(jì)算才能取得較合理的管網(wǎng)設(shè)計(jì)方案。供水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)的目標(biāo)，就是在供水管網(wǎng)系統(tǒng)改擴(kuò)建優(yōu)化設(shè)計(jì)基本思想指導(dǎo)下，以有限的建設(shè)資金最大限度地提高改擴(kuò)建管網(wǎng)供水的綜合效益，即在滿足水量水壓要求的前提下，推求改擴(kuò)建管道建設(shè)費(fèi)用及改擴(kuò)建后整個(gè)管網(wǎng)系統(tǒng)運(yùn)行動(dòng)力費(fèi)用最低的纖濟(jì)管徑^[2]。
　　其數(shù)學(xué)模型為：

　　式中：p——管網(wǎng)造價(jià)動(dòng)態(tài)折算系數(shù)；m——大修基金提存率（％）；
　　　　　N——新鋪設(shè)管段集合；Ci——第i條管段的單位長度造價(jià)（元／米〕；
　　　　　Li——第i條管段的長度（米）；γi——用電i期供水能量變化系數(shù)；
　　　　　Ei——用電i期電費(fèi)價(jià)格（元／千瓦時(shí)）；Ti——用電i期供水時(shí)間（小時(shí)）；
　　　　　n_s——泵站個(gè)數(shù)集合；Hi,j——第j個(gè)泵站機(jī)組i供電期的揚(yáng)程（米）；
　　　　　Qi.j——第j個(gè)泵站機(jī)組i供電期的輸水量（升／秒）；
　　　　　η——第j泵站機(jī)組i供電期的泵站效率（％）。
3．2 用遺傳算法求解供水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)問題
　　某城市現(xiàn)狀供水管網(wǎng)經(jīng)簡化后，共有67條管段（管徑均大于等于DN300），有55個(gè)節(jié)點(diǎn)（其中有2個(gè)水源點(diǎn)）。由于城市生產(chǎn)、生活用水的增長，需將原管網(wǎng)進(jìn)行改擴(kuò)建，經(jīng)有關(guān)部門規(guī)劃，需增設(shè)23個(gè)節(jié)點(diǎn)，31條管段。
　　用編制的遺傳算法程序?qū)芫W(wǎng)進(jìn)行優(yōu)化計(jì)算。按程序要求，需準(zhǔn)備如下數(shù)據(jù)：
　　　　p=0.18；m=3%；γ=0.5； E=0.8；η=0.8；N=31；ns=2；Dmax=1000mm；
　　　　vmin=0.6m/s；vmax=1.5m/s;Hmin=18.00m;Hmax=50.00m。
　　然后用遺傳算法進(jìn)行求解，求解時(shí)注意以卜兩個(gè)問題：
　?。?）編碼問題。采用二進(jìn)制編碼方式，對(duì)于管徑編碼時(shí)，取范圍在[300，1000]內(nèi)的標(biāo)準(zhǔn)規(guī)格的管徑，δ取100，則由δ=Umax-Umin/2λ-1得λ=3，即染色體上每三位表示一個(gè)標(biāo)準(zhǔn)規(guī)格管徑；對(duì)于節(jié)點(diǎn)水壓編碼，其范用是[18.00，50.00]，若精度δ取0.1，則由δ=[Umax-Umin]/[2λ-1]得λ=8.4≈9，此時(shí)精度為0.06。山于共有31條新建管段，78個(gè)節(jié)點(diǎn)，所以整條染色體長度為：3×31+9×78=795。
　?。?） 適應(yīng)度函數(shù)問題。將要求解的數(shù)學(xué)函數(shù)和約束進(jìn)行變形和轉(zhuǎn)換，通過引入懲罰函數(shù)的方法化成遺傳算法的標(biāo)準(zhǔn)適應(yīng)度函數(shù)。原數(shù)學(xué)模型可變?yōu)椋?/p>

　　　　　　

　　將目標(biāo)函數(shù)化為無約束極大值形式為：Max
式中，Cmax為一個(gè)適當(dāng)?shù)叵鄬?duì)較大的數(shù)。本例中，M取5.0e+5，Cmax取5.0e+7。優(yōu)化結(jié)果與規(guī)劃結(jié)果的比較見表一：

表一 管徑優(yōu)化結(jié)果和規(guī)劃結(jié)果的比較

序號(hào) 規(guī)劃(mm) 優(yōu)化（mm） 序號(hào) 規(guī)劃(mm) 優(yōu)化（mm） 1 800 500 17 500 1000 2 800 600 18 600 400 3 700 900 19 600 300 4 600 700 20 800 600 5 800 300 21 800 900 6 400 700 22 800 400 7 500 400 23 800 800 8 800 800 24 800 800 9 800 300 25 600 400 10 400 1000 26 400 500 11 600 400 27 500 400 12 400 400 28 600 300 13 400 900 29 600 400 14 600 500 30 600 700 15 600 900 31 600 500 16 600 300

表二 規(guī)劃管網(wǎng)與優(yōu)化管網(wǎng)的比較

管網(wǎng)狀況 新建管段造價(jià)年折算值（萬元/年） 管網(wǎng)年運(yùn)行費(fèi)用（萬元/年） 管網(wǎng)年費(fèi)用值（萬元/年） 規(guī)劃管網(wǎng) 2595.36 487.33 3082.69 優(yōu)化管網(wǎng) 2119.01 496.81 2615.82

　　從表二可看出，優(yōu)化計(jì)算后的每年費(fèi)用比預(yù)計(jì)規(guī)劃計(jì)算的節(jié)省了400多萬元，大大地減少了管網(wǎng)的投資費(fèi)用，故能產(chǎn)生較大的經(jīng)濟(jì)效益和社會(huì)效益。

4 結(jié)束語

　　綜上所述，用遺傳算法求解供水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)問題得到的結(jié)果是令人滿意的，這說明遺傳算法是一種比較好的搜索算法，它不僅快速、準(zhǔn)確、搜索遍及全空間，具有較大的把握得到全局最優(yōu)點(diǎn)，而且不用對(duì)原問題作過多的分析處理，具有很高的適應(yīng)性。當(dāng)然遺傳算法也存在一些缺點(diǎn)，如遺傳算法的操作參數(shù)和優(yōu)化結(jié)果相互之間比較獨(dú)立，故對(duì)于操作參數(shù)的選取比較困難；此外由于遺傳算法還處于發(fā)展的初級(jí)階 段，尚有許多問題需要研究和探討，比如對(duì)于大型復(fù)雜的問題收斂速度還比較慢等等[3]。
　　總之，本文采用遺傳算法求解直接優(yōu)化調(diào)度數(shù)學(xué)模型獲得了較理想的結(jié)果，故認(rèn)為遺傳算法在管網(wǎng)優(yōu)化方面的應(yīng)用值得推廣。

參考文獻(xiàn)：

　　1．周明、樹棟，《遺傳算法原理及應(yīng)用》，國防工業(yè)出版社，NO．1，1999
　　2．趙運(yùn)德，用廣義簡約梯度法求管網(wǎng)經(jīng)濟(jì)管徑，水利學(xué)報(bào)，No.6，1999
　　3．王平洋，加快遺傳模糊算法的搜索過程，電網(wǎng)技術(shù)，Vol．23，NO.5，1999