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

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

1 引言

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

2 遺傳算法的基本思想

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

3 遺傳算法在供水管網改擴建優化設計中的應用

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

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

　　　　　　

　　將目標函數化為無約束極大值形式為：Max
式中，Cmax為一個適當地相對較大的數。本例中，M取5.0e+5，Cmax取5.0e+7。優化結果與規劃結果的比較見表一：

表一 管徑優化結果和規劃結果的比較

序號 規劃(mm) 優化（mm） 序號 規劃(mm) 優化（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

表二 規劃管網與優化管網的比較

管網狀況 新建管段造價年折算值（萬元/年） 管網年運行費用（萬元/年） 管網年費用值（萬元/年） 規劃管網 2595.36 487.33 3082.69 優化管網 2119.01 496.81 2615.82

　　從表二可看出，優化計算后的每年費用比預計規劃計算的節省了400多萬元，大大地減少了管網的投資費用，故能產生較大的經濟效益和社會效益。

4 結束語

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

參考文獻：

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