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

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

1 引言

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

2 遺傳算法的基本思想

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

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

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

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

　　　　　　

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

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

序號 規(guī)劃(mm) 優(yōu)化（mm） 序號 規(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)狀況 新建管段造價年折算值（萬元/年） 管網(wǎng)年運行費用（萬元/年） 管網(wǎng)年費用值（萬元/年） 規(guī)劃管網(wǎng) 2595.36 487.33 3082.69 優(yōu)化管網(wǎng) 2119.01 496.81 2615.82

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

4 結束語

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

參考文獻：

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