吳惕華 張貴軍 蔡滿(mǎn)軍

1  引言

    水資源規劃調度是一個(gè)古老的問(wèn)題，可追溯到人類(lèi)文明早期的防洪、供水活動(dòng)中。人類(lèi)社會(huì )早期文明（如中國、印度、歐洲以及中美洲）在一定程度上體現在他們對水資源管理及利用的能力上（Jay R. Lund, 2001）。隨著(zhù)人口集聚及城市的出現，使水資源供需之間的矛盾日見(jiàn)端倪，從而出現了早期的優(yōu)化調度思想。早在古羅馬時(shí)代人類(lèi)就將定量分析和優(yōu)化的思想應用在了水資源的規劃上（Frontinus 97 AD，Leveau1993）。隨著(zhù)現代社會(huì )工業(yè)生產(chǎn)能力的提高，城市人口的不斷增加及人們生活水平的不斷改善，對城市供水系統的要求也越來(lái)越高，使城市供水管網(wǎng)規模及復雜性不斷提高，傳統經(jīng)驗調度方法不僅耗費了大量的能源（水、電能），而且使管網(wǎng)的壓力分布極其不合理，已遠不能滿(mǎn)足人們對水資源的需求。我國（尤其是北方地區）是一個(gè)嚴重缺水的國家，數以百計的城市供水系統所采用的傳統的恒壓供水方式不僅浪費了大量的水資源，而且還消耗了大量的電能，即使如此，也不能滿(mǎn)足人們的供水需求。因此，建立城市優(yōu)化供水系統是我國為實(shí)施可持續戰略急待解決的重大課題之一。

    現代城市優(yōu)化供水系統的設計目標是整個(gè)供水系統在全面蓄調的基礎上實(shí)現經(jīng)濟調度和優(yōu)化運行的目的，建立功能齊全、完整配套的集水源、制水、配水監控于一身的城市供水調度廣域網(wǎng)絡(luò )系統。建立合理有效的城市供配水優(yōu)化調度數學(xué)模型是實(shí)現城市優(yōu)化供水系統的關(guān)鍵，其建模內容一般包括原水的計劃調度和實(shí)時(shí)調度、正常工作狀態(tài)和非正常工作狀態(tài)下的制水調度、配水計劃調度和實(shí)時(shí)調度等三類(lèi)。城市供水企業(yè)SCADA系統的推廣及城市供配水管網(wǎng)GIS系統的相繼建立、完善，為優(yōu)化調度數學(xué)模型的數據準備提供了實(shí)現的可能；現代優(yōu)化理論和方法的發(fā)展提供了優(yōu)化調度建模的理論基礎；計算機技術(shù)的發(fā)展為優(yōu)化調度模型解算提供了實(shí)現上的保障?；趦?yōu)化調度模型的城市供水系統結合企業(yè)生產(chǎn)過(guò)程的SCADA系統、企業(yè)現代化管理MIS/GIS系統和網(wǎng)絡(luò )自動(dòng)抄表收費AMR系統，組成了城市自來(lái)水綜合自動(dòng)化解決方案，從根本上解決城市優(yōu)化供配水的問(wèn)題。該方案是保證我國建成節水型城市，實(shí)現供水企業(yè)和國際接軌的重要措施。本文就有關(guān)建立城市供配水優(yōu)化調度數學(xué)模型及算法仿真問(wèn)題作一全面綜述。

2  供配水系統優(yōu)化運行的建模問(wèn)題

    城市供配水系統優(yōu)化調度在不同的文獻中有不同的定義[1~2]，本文將所研究的優(yōu)化調度定義為：根據供配水系統的歷史記錄和實(shí)時(shí)運行的信息，確定系統今后一個(gè)調度周期中各時(shí)間段內各種調節裝置（如水泵的開(kāi)停、閘閥的啟閉，貯水池水位的升降等）的運行情況，在保證系統的服務(wù)質(zhì)量（水量、水壓和水質(zhì)）下，最大限度的提高供水系統的經(jīng)濟效益和社會(huì )效益。

    供配水系統優(yōu)化運行的建模問(wèn)題包括：供配水量預測模型、供配水網(wǎng)絡(luò )分析模型及優(yōu)化調度模型。用水量預測與需求分析屬于優(yōu)化運行實(shí)施的前期工作，也是進(jìn)行供配水系統優(yōu)化運行的基礎和前提，它的準確程度直接影響到調度運行的可靠性及實(shí)用性[3]；供配水網(wǎng)絡(luò )分析模型與管網(wǎng)運行分析可以作為優(yōu)化調度模型必要的約束條件；而最終的目的則是建立優(yōu)化調度模型以實(shí)現供配水系統的優(yōu)化運行。

2.1  供配水系統用水量預測模型
    實(shí)際的供水調度中，主要是對日用水量和時(shí)用水量的預測。預測方法一般分為兩類(lèi)：解釋性預測方法和時(shí)間序列預測方法。前者認為輸入變量的變化會(huì )引起系統輸出變量的變化，也就是說(shuō)系統的輸入和輸出之間存在著(zhù)某種因果關(guān)系。對于用水量的輸入量一般要考慮氣象、人口增長(cháng)、工商業(yè)分布、居民活動(dòng)及節假日作用等影響因素。這種模型對輸入變量的精度要求較高，特別是當離線(xiàn)控制時(shí)，需要對次日整天的用水量進(jìn)行預測，這就要求次日的天氣、居民活動(dòng)等預報資料精度較高，否則誤差可能較大。后者是把系統當成一個(gè)黑箱，可以不管其影響因素，只關(guān)心觀(guān)測和預測的結果，其預測過(guò)程只依賴(lài)于歷史觀(guān)測數據和它的數據模式。用水量預測中常用的模型有指數平滑模型、自回歸（AR）模型[12]、滑動(dòng)平均（ARMA）模型[3]、灰色預測模型[2]、動(dòng)態(tài)組合預測模型[4]、自適應組合預測模型[5]、基于RBF神經(jīng)網(wǎng)絡(luò )模型[58]、模糊邏輯系統（FLS）和人工神經(jīng)網(wǎng)絡(luò )（ANN）[74]。此外，國外最新還研制出了基于環(huán)境和氣候影響的用水量預測的決策支持系統（DSS）和分析模型[6]。

    另外，用水量預測在空間上可分為總水量預測和節點(diǎn)用水量預測。前者是指預測系統內每日或每時(shí)的用戶(hù)用水量，這類(lèi)預測采用的算法很多，它主要是為宏觀(guān)模型的優(yōu)化運行服務(wù)的；后者是預測分配到各系統節點(diǎn)的用水量，它的建模比較復雜，主要是為微觀(guān)的模型服務(wù)的，國外一些發(fā)達國家在這方面進(jìn)行了許多有益的探討并進(jìn)行了實(shí)際的應用[7~9]。

2.2  供配水系統網(wǎng)絡(luò )分析模型
    要對城市供水系統的運行進(jìn)行優(yōu)化調度決策，必須建立與供水系統的外部特征相吻合的數學(xué)模型，科學(xué)、準確、定量地描述系統中各個(gè)變量之間的關(guān)系。該模型可體現在供配水系統優(yōu)化調度模型中的約束條件中。由優(yōu)化調度的步驟可以看出，建立實(shí)際供水系統的網(wǎng)絡(luò )分析模型是實(shí)現優(yōu)化運行的先決條件。其中，供水系統中管網(wǎng)的分析和計算是兩個(gè)重要模塊。一方面通過(guò)對用戶(hù)用水的要求，管網(wǎng)的管道的阻耗系數、配水泵的流量―揚程特性、管網(wǎng)的等水壓線(xiàn)的分析、確定管網(wǎng)的合理布置、管徑大小、管網(wǎng)測壓線(xiàn)的分析；另一方面，針對已有管網(wǎng)分布及其特性建立管網(wǎng)的特性分析模型，用來(lái)分析管網(wǎng)對供水的影響。國內外學(xué)者在這方面進(jìn)行了大量的研究，歸納起來(lái)大致可分為微觀(guān)模型、宏觀(guān)模型和管網(wǎng)集結模型。

    (1)  微觀(guān)模型
    微觀(guān)模型是在盡可能考慮管網(wǎng)的拓撲結構及管網(wǎng)各元素（如管道管徑、管長(cháng)、管材等）、節點(diǎn)用水量等主要參數的水力學(xué)關(guān)系的基礎上，構造出供水管網(wǎng)拓撲結構模型。這種模型的基本數學(xué)方程包括質(zhì)量平衡和能量平衡兩大部分，可用如下三個(gè)方程表示[2]：
    節點(diǎn)方程：   (1)

    回路方程：   (2)

    壓降方程：   (3)

    目前，求解上述方程的方法已相當成熟，有節點(diǎn)水頭法、環(huán)流量法和管段流量法等。以節點(diǎn)水壓為求解變量的牛頓迭代法[67]為最有效的方法之一。

    微觀(guān)模型對系統的變化及節點(diǎn)用水量分布的變化適應性強，即便水池或主干管中斷也只需將管網(wǎng)拓撲關(guān)系校正后仍可應用上述方程進(jìn)行系統工況模擬仿真。但是，其缺點(diǎn)也很明顯，需要大量的建模數據。應用上述微觀(guān)模型的前提是已知管網(wǎng)各節點(diǎn)的節點(diǎn)流量及管道的摩阻系數；然而，節點(diǎn)流量是依賴(lài)用戶(hù)用水量而隨機變化的量，是最難以確定的值；管道摩阻系數受管道敷設年限、管道腐蝕及結垢等因素而發(fā)生變化，其變化值也難以解析；其次，模型的校核工作量大，計算時(shí)間長(cháng)，耗費大。這些因素在一定程度上影響了微觀(guān)模型的實(shí)際應用。

    (2)  宏觀(guān)模型
    由美國學(xué)者Robert Demoyer Jr.[10]在1975年提出的，之后國內外許多的學(xué)者都致力于這項研究。這類(lèi)模型的主要思想是利用獲取的幾種重要的管網(wǎng)參數（如測壓點(diǎn)壓力、泵站出口壓力、泵站出水量、水池水位及系統的用水量等）以統計分析理論為基礎，建立系統網(wǎng)絡(luò )的（結構性）分析模型，其數學(xué)描述可表示為[3]：

       (4)

    (4)式右端一般為多項式，通過(guò)回歸分析可確定具體的函數形式，論文[89]中給出了其中的一種函數形式。

    管網(wǎng)宏觀(guān)模型的特點(diǎn)是建模所需數據量少，建?？?，計算效率高。但是適用范圍有一定的限制，當系統用水量及其它已知參數變化幅度較大的時(shí)候，可能產(chǎn)生明顯的誤差。如當某水池或主干管中斷時(shí)，宏觀(guān)模型需要重新獲取原始數據，進(jìn)行回歸分析、校正，建立新的模型形式。

    (3)  管網(wǎng)集結模型
    為了克服水系統管網(wǎng)微觀(guān)模型的缺點(diǎn)并能充分利用宏觀(guān)模型的優(yōu)點(diǎn)，近年來(lái)提出了供水系統管網(wǎng)集結模型[11]，該模型是建立在微觀(guān)模型的基礎上的。所謂管網(wǎng)集結其實(shí)就是一種簡(jiǎn)化網(wǎng)絡(luò )結構的方法，它把整個(gè)配水管網(wǎng)劃分為p個(gè)區域，使管網(wǎng)中每個(gè)節點(diǎn)必須且僅屬于一個(gè)區域。通常區域的劃分原則是：同區域內的各節點(diǎn)壓力大致相等，用水規律相仿。將每個(gè)區域中的所有節點(diǎn)集結在一起，形成一個(gè)虛擬的節點(diǎn)，區域（即用虛擬節點(diǎn)組成的）之間的關(guān)聯(lián)用一條虛擬的管道表示，這樣原來(lái)的管網(wǎng)模型（微觀(guān)模型）就簡(jiǎn)化為一個(gè)新的管網(wǎng)模型，稱(chēng)之為集結模型。集結模型不僅在計算上節約了計算時(shí)間，而且在建模上更科學(xué)合理且符合實(shí)際，對于多水庫聯(lián)合調度的問(wèn)題其效果更加明顯。該模型在宏觀(guān)模型和微觀(guān)模型之間提供了一種很好的折衷的方法。

2.3  供配水系統優(yōu)化調度模型
    在供水系統的需水量和管網(wǎng)模型確定之后，就可以對系統供水進(jìn)行優(yōu)化調度。優(yōu)化調度就是為已有的供水系統進(jìn)行區域水量的分配及確定水泵的優(yōu)化運行策略。具體就是在對調度日的城市用水量預測以后，利用建立的網(wǎng)絡(luò )分析模型進(jìn)行優(yōu)化計算，得到調度日內各時(shí)段、各泵站的水泵開(kāi)關(guān)策略及各種變速泵的轉速。其目的就是在保證系統約束條件及給定的邊界條件下，使給定的目標函數最小或者最大。對優(yōu)化調度模型的目標函數的確定，國內大多數的學(xué)者是以費用最小[13~14]或者城市供水量最大[15~16]為目標的，而Jay R. Lund至少提出了6種在調度模型中可選的目標函數。根據所選擇決策變量的不同還可將調度控制模型分為顯式模型和隱式模型[2~3]。顯式模型是直接以實(shí)際水泵的運行時(shí)間作為決策變量，而隱式模型則是首先采用中間變量，如泵站出口流量、水池變化軌跡等，并依此進(jìn)行目標函數的尋優(yōu)。

3  供配水系統優(yōu)化調度數學(xué)模型及算法

    供配水優(yōu)化調度是進(jìn)行水量預測和管網(wǎng)分析的目的所在，也是本文重點(diǎn)。供配水系統優(yōu)化調度首先是在城市用水量預測和管網(wǎng)分析的基礎上，建立調度模型的目標函數以及相應的系統的約束條件，其中用水量預測和管網(wǎng)分析模型體現在其約束條件中，在滿(mǎn)足約束的前提下，確定最優(yōu)的目標函數。通過(guò)相應的約束條件，供配水系統的優(yōu)化調度模型可以與水量預測模型和管網(wǎng)分析模型有機的集成在一起。

    優(yōu)化調度模型的目標函數是根據供水企業(yè)自身的費用、水源條件、環(huán)境、效益及國家的法規等多方面來(lái)確定的，Jay R. Lund在其論文中提出了6種調度模型中可選的目標函數類(lèi)型[81]。不同的供水企業(yè)其制定的目標函數可能是不同的，根據實(shí)際的情況，還有可能進(jìn)行多目標優(yōu)化調度模型。通過(guò)權重標量化或者將目標函數轉化為約束條件，可以將多目標優(yōu)化模型轉化為單目標模型，此外Jeffrey還采用了小生境排列遺傳算法NPGA來(lái)解決多目標優(yōu)化的問(wèn)題[62]并成功應用在水力系統上。NPGA在選擇算子中集成了顯性排列（Pareto Domination）的概念并采用小生境技術(shù)，從而將群體分布在最優(yōu)權衡排列面上。

    優(yōu)化調度模型的約束條件可以是供配水系統的水量預測模型、管網(wǎng)水力分析模型、目標函數或者是人為規定的一些政策法規、行業(yè)標準。約束條件的合理程度直接關(guān)系到系統優(yōu)化調度的成敗。

    總的來(lái)說(shuō)，優(yōu)化調度模型的建立和其采用的算法是密不可分的。由上可知，優(yōu)化調度模型的目標函數和約束條件在不同的場(chǎng)合是不同的，模型求解算法卻是相對確定的，也就是說(shuō)建立什么樣的模型，可以有相應的算法來(lái)求解?；谶@個(gè)原因，本文從優(yōu)化調度的數學(xué)優(yōu)化算法方面來(lái)闡述優(yōu)化調度建模及實(shí)現方法，從中可得到有益的啟迪。

    供配水優(yōu)化調度模型涉及到地上水、地下水、多水源多泵站的聯(lián)合調度問(wèn)題，是一個(gè)復雜的非線(xiàn)性系統。優(yōu)化調度模型在求解的步驟上可分為直接優(yōu)化調度模型[13]和多級優(yōu)化調度供水調度模型[76,78]，其中直接優(yōu)化調度模型一般用來(lái)解決計算量比較小的管網(wǎng)系統，而對于變量比較多，計算量比較大的城市管網(wǎng)系統，則采用多級優(yōu)化調度模型。

    下面從傳統的數學(xué)優(yōu)化方法和現代優(yōu)化算法兩方面來(lái)介紹應用在供配水優(yōu)化調度中優(yōu)化算法以及相應的模型。

3.1  應用在供配水系統中的傳統數學(xué)優(yōu)化方法
    在這里，傳統的數學(xué)優(yōu)化方法是指線(xiàn)性規劃（LP）、整數規劃（IP）、非線(xiàn)性規劃（NLP）、動(dòng)態(tài)規劃（DP）以及最優(yōu)控制理論（OCT）等優(yōu)化方法。

    供配水優(yōu)化調度模型是一個(gè)復雜的非線(xiàn)性系統。非線(xiàn)性的特征主要來(lái)源于泵站電耗、地下水水位的變化、管網(wǎng)水力方程、蒸發(fā)等因素。此外，基于決策的階段特性（以日、時(shí)為調度時(shí)間），自然而然，非線(xiàn)性規劃和動(dòng)態(tài)規劃的方法廣泛的應用在供水優(yōu)化調度的建模和模型的求解上。

    (1)  線(xiàn)性規劃（LP）、整數規劃（IP）及最優(yōu)控制原理（OCT）
    LP方法主要是應用在模型的求解上，即將調度模型的非線(xiàn)性目標函數和約束條件轉化為線(xiàn)性的約束條件，從而可以將非線(xiàn)性問(wèn)題轉化為線(xiàn)性問(wèn)題來(lái)處理。常用線(xiàn)性化方法是Talor級數展開(kāi)[57]、δ型逼近[25,75]、外部OA逼近[52]等。目前最新發(fā)展的LP是懲罰連續線(xiàn)性規劃PSLP，通過(guò)連續的使用LP來(lái)求解NLP問(wèn)題；同時(shí)Barker和Lasdon還提出了一種簡(jiǎn)化的PSLP方法[17]，與傳統連續線(xiàn)性規劃SLP相比，這種方法能夠更好的解決具有非線(xiàn)性約束條件的問(wèn)題；Zhang 等人進(jìn)一步改善了PSLP算法并論證了算法的收斂性[18]。在此基礎上Hirad Mousavi應用PSLP算法解決了多水源聯(lián)合供水系統的最優(yōu)規劃問(wèn)題[57]。

    IP在供配水系統優(yōu)化調度中的應用主要是針對一類(lèi)具有固定費用約束的優(yōu)化模型，該模型采用混合整數非線(xiàn)性規劃（MINLP）[52]來(lái)描述供水系統優(yōu)化調度問(wèn)題。常用的解法是將MINLP轉化為NLP[19~22]或者M(jìn)ILP[23~24]來(lái)求解優(yōu)化模型。

    OCT在供水系統調度模型中的應用并不多見(jiàn)，Mousavi已經(jīng)證明其得到的解是一個(gè)次最優(yōu)解[52]；然而由于該算法對搜索起點(diǎn)的不敏感性，還是有一些學(xué)者成功地將OCT應用到水庫的優(yōu)化調度上[26~30]。

    (2)  動(dòng)態(tài)規劃（DP）
    基于優(yōu)化調度是以日、小時(shí)為階段來(lái)進(jìn)行決策的，動(dòng)態(tài)規劃的方法廣泛地應用在供水系統優(yōu)化調度模型中[31~35]。其基本思想是在多階段決策的過(guò)程中，把當前階段和未來(lái)階段分開(kāi)，同時(shí)又將當前效益和未來(lái)效益結合起來(lái)考慮的一種最優(yōu)化方法。對中小型的供水優(yōu)化調度問(wèn)題應用DP能夠提出準確的最優(yōu)解，但是隨著(zhù)模型階數及變量數的增加，DP計算復雜性隨維數的增加呈指數的增長(cháng)。DP固有的兩個(gè)問(wèn)題限制了在供水優(yōu)化調度中應用[58]：
    ?  維數災：隨模型維數的增加計算復雜性呈指數的增長(cháng)；
    ?  模型災：很難確定系統的模型、狀態(tài)轉移概率。

    (3)  非線(xiàn)性規劃（NLP）
    基于梯度的NLP優(yōu)化算法廣泛地應用在供水系統調度模型中。NLP能夠求解一類(lèi)光滑的非線(xiàn)性目標函數和約束條件的函數。建立相應的目標函數和約束條件后，在能保證模型精度的情況下，應用NLP方法建模，具有求解質(zhì)量好的特點(diǎn)?，F在能夠求解上千個(gè)約束條件和變量的NLP軟件包已經(jīng)成功地應用在供水系統優(yōu)化模型中，如MINOS[36]、CONOPT2[37]等。但是NLP本質(zhì)上是一個(gè)局部尋優(yōu)算法而不是一個(gè)全局尋優(yōu)的算法，在應用上存在以下的限制[61]：
    ?  NLP算法通常收斂到離搜索起點(diǎn)最近的局部最優(yōu)點(diǎn)；
    ?  在原理上對非連續的問(wèn)題并不能保證收斂性；
    ?  隨系統的規模和復雜度的增加，計算速度和解的可靠性將降低。

    總之，傳統的數學(xué)優(yōu)化方法，從本質(zhì)上都是一種局部、串行的計算方法。在簡(jiǎn)單的供配水優(yōu)化調度系統中可能會(huì )取得很好的效果，但是隨著(zhù)系統復雜度的提高，模型的復雜度以及在求解速度、質(zhì)量上都會(huì )受到一定的影響。由此限制了傳統優(yōu)化方法在許多供水系統中的成功應用。

3.2  應用在供配水系統中的現代優(yōu)化算法
    現代優(yōu)化算法是80年代初興起的啟發(fā)式算法（Heuristic Algorithm）。這些算法包括禁忌算法（Tabu Search）、模擬退火（Simulated Annealing）、遺傳算法（Genetic Algorithm）以及人工神經(jīng)網(wǎng)絡(luò )（Neural Network）。所謂的啟發(fā)式算法是指一個(gè)基于直觀(guān)或經(jīng)驗構造的算法，在可接受的花費（指計算時(shí)間、占用空間等）下給出待解決優(yōu)化問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解偏離程度不一定事先可以預計[38]。在某些情況下，特別是實(shí)際問(wèn)題中，傳統最優(yōu)算法的計算時(shí)間使人無(wú)法忍受或因問(wèn)題的難度使其計算時(shí)間隨問(wèn)題的規模的增加以指數速度增加，尤其是傳統的最優(yōu)算法本質(zhì)上是一種串行、局部尋優(yōu)算法?；趩l(fā)算法的并行性和全局尋優(yōu)特性，為了解決上述傳統的數學(xué)規劃方法的局限性，這些算法在近幾年開(kāi)始應用于供水系統的優(yōu)化調度問(wèn)題中。

    在供水優(yōu)化調度中應用最多的是遺傳算法和模擬退火算法。也有將人工神經(jīng)網(wǎng)絡(luò )成功地應用在供水優(yōu)化調度模型中[58][73]，在該模型中M.Damas應用基于RBF網(wǎng)絡(luò )的時(shí)序預測方法確定了供水調度系統不確定的輸入變量。

    (1)  遺傳算法（GA）
    GA是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應全局優(yōu)化的概率算法。它最早是由美國密執安大學(xué)的Holland教授提出的，起源于60年代對自然和人工自適應系統的研究。70年代De Jong基于遺傳算法的思想在計算機上進(jìn)行了大量的純數值函數優(yōu)化計算實(shí)驗。在一系列研究工作的基礎上，80年代由Gold Berg進(jìn)行歸納總結，形成了遺傳算法的基本框架。

    GA已廣泛地應用到供水系統的水量分配[39~42]、泵調度[43~45,83~85]、水池水位[39~45]以及管網(wǎng)恢復系統[46~47]等方面。GA是一種并行的全局尋優(yōu)算法，應用該算法主要解決的問(wèn)題是染色體的編碼問(wèn)題以及確定編碼值是否滿(mǎn)足模型的約束條件，即可行解。S.F.Beckwith 對此進(jìn)行了討論[45]。

    由于GA算法本質(zhì)上是一種仿生算法，由此對于一些復雜高階系統的求解特別有效。在優(yōu)化調度目標函數已經(jīng)確定的前提下，其關(guān)鍵是選擇適當的交叉算子（Crossover Operator）和變異算子（Mutation Operator）以及相應的編碼和解碼方法。其算法具有一定通用性。

    此外，隨著(zhù)GA的發(fā)展，遺傳編程（GP）也取得了很快的發(fā)展，從而在實(shí)現上提供了對GA的支持。如麻省理工學(xué)院Matthew Wall開(kāi)發(fā)的GAlib，Andy Hunter開(kāi)發(fā)的SUGAL等開(kāi)發(fā)工具。應用這些中間算法庫作為平臺，可以很方便地開(kāi)發(fā)出特定環(huán)境的遺傳算法。

    但是GA算法本身也存在一些局限性，如早熟現象、最優(yōu)解附近收斂速度變慢等。對此，國內外一些學(xué)者已在進(jìn)行研究[48]。研究結果表明，結合一些傳統的優(yōu)化方法，遺傳算法可以取得更好的效果。

    (2)  模擬退火算法（SA）
    SA是Metropolis在1953年提出的，該算法是局部搜索算法的擴展，它不同于局部搜索之處是以一定的概率選擇領(lǐng)域中費用值最大的狀態(tài)。從理論上來(lái)說(shuō)是一種全局最優(yōu)化算法。在供水優(yōu)化調度中應用參見(jiàn)文獻[49~50,80]。

3.3  應用在供配水系統中的混合優(yōu)化方法
    無(wú)論是傳統的數學(xué)優(yōu)化方法還是現代優(yōu)化算法，單獨應用在供配水優(yōu)化調度問(wèn)題上都有其自身的一些局限性。比如：傳統的優(yōu)化方法大都是一些局部尋優(yōu)的算法，在實(shí)際應用中需要多次選擇起點(diǎn)來(lái)進(jìn)行測試，增加了算法的計算時(shí)間；而現代優(yōu)化方法理論上是一種全局最優(yōu)化算法，但是在最優(yōu)點(diǎn)附近的收斂速度可能很慢等。國內外學(xué)者對這方面進(jìn)行了許多的研究，提出了一些有效的供水系統優(yōu)化調度模型及混合的優(yōu)化算法。這類(lèi)算法具有自適應性的特點(diǎn)，有效地克服了單一算法的局限性，提高了系統的計算效率及精度。

    1996年，Jean-Michel[51]提出了一種基于GA和爬山法的混合優(yōu)化算法來(lái)進(jìn)行全局的尋優(yōu)，算法有效的結合了GA全局尋優(yōu)特性及爬山法在最優(yōu)點(diǎn)附近的收斂特性，在解的精確性、可靠性以及計算時(shí)間上取得了很好的折衷。2000年M.Damas[58]將此算法成功地應用到供水系統調度模型來(lái)確定一系列的可行解。

    1997年，David W. Watkins Jr.[52]對供水系統中一類(lèi)帶固定費用問(wèn)題的混合整數非線(xiàn)性規劃（MINLP）調度模型應用兩個(gè)分解算法GBD[53~54]和OA[55~56]對進(jìn)行優(yōu)化，得出了GBD適合大規模的調度模型的解算，而OA具有更快的收斂速度的結論。

    1999年，Hirad Mousavi等[57]提出了一種PSLP-OCT供水優(yōu)化運行模型。該模型應用最優(yōu)控制原理OCT和懲罰連續線(xiàn)性規劃PSLP的技術(shù)來(lái)對大規模復雜的供水系統進(jìn)行優(yōu)化。此外，為了實(shí)現費用最小以及盡可能滿(mǎn)足供水需求，在模型中還應用了Epsilon約束的方法。

    2000年，M.Damas等[58]提出了一種集混合遺傳算法[51]和NDP[59]神經(jīng)動(dòng)態(tài)規劃方法的供水網(wǎng)絡(luò )優(yōu)化調度模型。該模型主要是針對解決分階段決策優(yōu)化控制而提出的，其中每個(gè)階段的狀態(tài)變量和控制變量都是連續的。遺傳算法采用混合遺傳算法來(lái)確定每個(gè)決策階段可行的狀態(tài)變量；基于RBF神經(jīng)網(wǎng)絡(luò )[60]和經(jīng)典的正交轉換（SVD和QR）方法的時(shí)間序列預測來(lái)預測供水系統的階段需水量；為了避免動(dòng)態(tài)規劃過(guò)程的災數問(wèn)題，利用Monte Carlo仿真的方法來(lái)逼近模型的最優(yōu)值函數，以及采用并行計算的機群技術(shù)都大大提高了模型的計算時(shí)間和改善了計算效果。最后基于該模型成功地解決了西班牙Granada市供水網(wǎng)絡(luò )優(yōu)化調度的問(wèn)題。

    2001年，Ximing Cai[61]等提出了一種應用GA＆LP來(lái)求解非線(xiàn)性水管理模型混合算法，其中GA用來(lái)確定模型的復雜變量，當其固定后，保持其余變量線(xiàn)性化，即可用LP的方法來(lái)求解，依此循環(huán)。在原理上GA算法可用其它的一些啟發(fā)算法來(lái)求解，如禁忌算法TS和模擬退火SA來(lái)代替。

    在供配水系統的優(yōu)化調度模型中，還涉及到一類(lèi)多目標優(yōu)化的問(wèn)題[87]，對于這類(lèi)的問(wèn)題可以從兩方面來(lái)解決：將一些目標函數轉換為模型的約束條件；或應用多目標決策的方法來(lái)實(shí)現，如NPGA[62]的方法等。較為典型的是1999年Kato提出了一種交互式多目標的分層混合供水網(wǎng)絡(luò )調度模型[63]。模型包括兩層：抽象匯總調度層（ASP）和進(jìn)一步的連續細節調度層（CDP）。ASP層確定每日供水總調度量，CDP層在此基礎上進(jìn)一步確定出一天中每小時(shí)水的調度量。在模型的求解中應用提出的混合多目標多階段規劃的方法HMMP，并與傳統的多層網(wǎng)絡(luò )模型的求解方法多階段整數規劃（MIP）[64]和完全的多目標規劃（CMOP）在計算時(shí)間、水庫的恢復率（RLR）以及流的平穩率（FSR）等方面成功地作了比較。測試結果表明，HMMP方法為已有的MIP和COMP提供了一種很好的中間規劃方法。該模型還成功地應用到日本的某些城市供水調度中，驗證了方法的可行性。文獻[14,65~66,70]分別用不同算法實(shí)現了供水系統優(yōu)化調度多目標優(yōu)化的問(wèn)題。

4  小結

    綜上所述，供配水系統優(yōu)化調度模型是與用水量預測模型以及管網(wǎng)分析模型有機集合在一起的。在優(yōu)化調度建模中可以將水量預測模型和管網(wǎng)分析模型轉化為其約束條件，然后采用適當優(yōu)化算法對模型進(jìn)行求解。

    采用傳統的數學(xué)優(yōu)化方法建立供配水系統優(yōu)化調度模型，在系統比較簡(jiǎn)單的情況下，可以以較快的收斂速度得到較精確結果，但是現在供配水系統優(yōu)化調度的模型已不局限于傳統的單一泵站、水廠(chǎng)之間的供水調度，更多實(shí)現是多水源和多目標的聯(lián)合調度模型，隨著(zhù)模型復雜性的提高，傳統的數學(xué)優(yōu)化方法無(wú)論在求解的有效性和精確性上還是在計算時(shí)間和計算資源的要求上，已遠遠不能滿(mǎn)足要求。

    采用一些現代優(yōu)化算法可以在一定的程度上解決這個(gè)問(wèn)題。比如遺傳算法GA，單個(gè)個(gè)體的收斂速度雖然很慢，但是算法是基于整個(gè)群體，其并行性可以使收斂速度大大地提高，可獲得全局優(yōu)化；此外，算法對模型的要求也比較低，所有這些都大大促進(jìn)了遺傳算法在供配水系統中的廣泛的應用。但是其也存在著(zhù)一些問(wèn)題，比如：求解初期的收斂速度很快，但是在后期的收斂速度卻很慢，有時(shí)還必須采用適當的編碼和選擇算子以避免出現早熟現象。

    為此，采用傳統優(yōu)化方法和現代優(yōu)化算法相結合的方法建立和求解供配水系統優(yōu)化調度模型有著(zhù)廣闊的前景。其中，管網(wǎng)分析模型可轉化為模型的約束條件；采用并行的遺傳算法可以很快地收斂到最優(yōu)點(diǎn)的附近，然后應用線(xiàn)性規劃等傳統方法可很快收斂到調度模型的最優(yōu)點(diǎn)，從而可以使群體不但并行地遺傳進(jìn)化，而且使群體中的個(gè)體有學(xué)習的過(guò)程，大大提高解的收斂速度和質(zhì)量。

    筆者在這方面的研究成果將另有專(zhuān)題論述，為城市供水系統優(yōu)化調度提供一個(gè)有效的解決方案。