基于改進(jìn)遺傳算法的多水源大型供水管網(wǎng)優(yōu)化調(diào)度

20世紀(jì)70年代，國外專家如羅氏、蘭茲、彌勒斯和科赫伯勒先后開始研究管網(wǎng)優(yōu)化計劃。從20世紀(jì)80年代開始，王訓(xùn)堅、趙鴻斌、趙新華和呂坤在這方面進(jìn)行了深入研究和研究成果。在實際設(shè)計應(yīng)用方面，美國的紐約、倫敦、英國大陸、巴黎、巴黎、chambery和日本的一些城市也取得了深入研究和成果。近年來，一些中國城市也在這方面進(jìn)行了應(yīng)用實踐研究，優(yōu)化計劃的理論模型和解決方案也取得了一些新的研究進(jìn)展。隨著數(shù)據(jù)收集和監(jiān)測、通信等軟件和硬件設(shè)備的逐步完善，整個供水系統(tǒng)的優(yōu)化計劃應(yīng)用程序的開發(fā)將逐步完善。因此，本研究適用于我國大部分水源大城市供水管網(wǎng)的計算機(jī)優(yōu)化規(guī)劃模型和解決方案，積極開展應(yīng)用實踐，提高我國供水行業(yè)的信息水平，對供水行業(yè)的運(yùn)營成本具有重要意義。1直接優(yōu)化調(diào)度數(shù)學(xué)模型優(yōu)化調(diào)度的目標(biāo)是尋求在調(diào)度周期內(nèi)使供水能量費(fèi)用達(dá)到最小的水泵、水池(或水庫)組合供水方案.由于水泵本身分定速、變速兩種不同的類型,因而該問題是既有連續(xù)變量又有離散變量的混合非線性優(yōu)化問題.本文以管網(wǎng)微觀水力模型作為計算核心,建立以管網(wǎng)中所有水泵的開關(guān)及轉(zhuǎn)速比為決策變量的直接優(yōu)化調(diào)度數(shù)學(xué)模型.1.1總供水量及調(diào)度時間供水能量費(fèi)用主要包括制水費(fèi)用和輸水費(fèi)用兩部分.輸水費(fèi)用主要集中在水廠的二級泵站內(nèi)部,一級泵站的能量費(fèi)用以單位流量的能耗費(fèi)用計入制水成本,同時考慮城市供水系統(tǒng)以天為周期的規(guī)律性,優(yōu)化調(diào)度的時間周期選為24h.單臺水泵工作時,水泵的有效功率消耗為Pi=KQiHi/ηi其中:K為換算系數(shù);Qi為水泵的出水流量,m3·s-1;Hi為水泵的出水揚(yáng)程,m;ηi為水泵在當(dāng)前流量、揚(yáng)程下的運(yùn)行效率;Pi為水泵功率,kW.對于二級泵站,考慮相應(yīng)水廠的制水成本,泵站的總供水費(fèi)用為Cj(t)=[pj∑i=1nX(i)?Qi+∑i=1nPiX(i)Fj(t)]E(t)(1)Cj(t)=[pj∑i=1nX(i)?Qi+∑i=1nΡiX(i)Fj(t)]E(t)(1)式中:pj為泵站j對應(yīng)水廠的制水成本;Qi為泵站j的第i臺水泵出水量;X(i)為該泵站第i臺水泵開關(guān)狀態(tài),開啟時X(i)=1,關(guān)閉時X(i)=0;Fj(t)為j泵站第t時段電費(fèi);E(t)為t時段調(diào)度時間間隔,t為該調(diào)度時段起始時刻;n為泵站j內(nèi)水泵臺數(shù).對特定時段調(diào)度時,總的供水費(fèi)用目標(biāo)函數(shù)可以寫成∑j=1JCj(t)=∑j=1J[pj∑i=1nX(i)?Qi+∑i=1nWiX(i)Fi(t)]E(t)(2)∑j=1JCj(t)=∑j=1J[pj∑i=1nX(i)?Qi+∑i=1nWiX(i)Fi(t)]E(t)(2)當(dāng)以24h為周期進(jìn)行全天候調(diào)度時,總的供水費(fèi)用目標(biāo)函數(shù)為C=∑t=1T∑j=1JCj(t)=∑t=1T{E(t)∑j=1J[pj∑i=1nX(i)?Qi+∑i=1nWi?X(i)Fi(t)]}(3)C=∑t=1Τ∑j=1JCj(t)=∑t=1Τ{E(t)∑j=1J[pj∑i=1nX(i)?Qi+∑i=1nWi?X(i)Fi(t)]}(3)式中:T為調(diào)度周期時間長度;J為管網(wǎng)中泵站數(shù).1.2控制集合n(1)以管網(wǎng)連續(xù)性方程與能量守恒方程為基礎(chǔ)的隱式水力平衡約束條件F(Q,H)=0(4)F(Q,Η)=0(4)(2)最小服務(wù)水壓約束Hi,t＜Hi,t,req(5)Ηi,t＜Ηi,t,req(5)其中:Hi∈Ωn,Ωn為控制點(diǎn)集合;t為調(diào)度時刻,t=1,…,T.(3)泵站的出水量約束minQj,t≤Qj,t≤maxQj,t(6)minQj,t≤Qj,t≤maxQj,t(6)(4)水池(庫)的最高、最低水位約束minVr,t≤Vr,t≤maxVr,t(7)minVr,t≤Vr,t≤maxVr,t(7)式中:r為水池(庫),r=1,…,R.(5)水泵揚(yáng)程約束,根據(jù)水泵的運(yùn)行特性曲線可知,等效于對水泵效率的約束minHi,t≤Hi,t≤maxHi,t(8)minΗi,t≤Ηi,t≤maxΗi,t(8)(6)初始邊界條件,要求在調(diào)度周期(一般為24h)內(nèi),水池(庫)的初始時段水位與末時段水位相等Vr,init=Vr,end(9)Vr,init=Vr,end(9)2優(yōu)化規(guī)劃模型的主要功能2.1管網(wǎng)微觀水力模型的適用性和靈活性本優(yōu)化問題基于管網(wǎng)微觀水力模型,比基于宏觀模型更為靈活.宏觀模型是通過對監(jiān)測的水量、水壓等數(shù)據(jù)回歸分析,獲得管網(wǎng)中供水泵站出水量、水壓與管網(wǎng)中監(jiān)測點(diǎn)的相關(guān)關(guān)系,并以此分析供水調(diào)度方案的水力約束及供水能量費(fèi)用.由于宏觀模型對管網(wǎng)大幅簡化,僅保留供水泵站和連接泵站的概念性主干管等,雖然一定程度上降低了建模的難度,但模型的精度和不確定性也顯然隨之增大.而且,當(dāng)實際管網(wǎng)發(fā)生變化(改建或者擴(kuò)建)時,原有宏觀模型很可能不再適用,需重新收集數(shù)據(jù).因此,宏觀模型的靈活性和適應(yīng)性較差.管網(wǎng)微觀水力模型是基于完整的管網(wǎng)拓?fù)浜凸芫W(wǎng)水力計算理論建立的,供水水源的水量和水壓力通過求解水力平衡方程獲得,較宏觀模型使用的回歸分析方法更為精確.此外,當(dāng)管網(wǎng)結(jié)構(gòu)變化時,微觀模型僅需對管網(wǎng)輸入?yún)?shù)作相應(yīng)改動,無須重新收集數(shù)據(jù)和建模,具有更大的通用性和靈活性.2.2優(yōu)化問題的求解結(jié)構(gòu)從式(1)可見,作為供水系統(tǒng)運(yùn)行費(fèi)用函數(shù),以管網(wǎng)中各臺水泵的流量、揚(yáng)程、運(yùn)行效率以及制水成本系數(shù)等參數(shù)顯式表達(dá),而這些參數(shù)可通過微觀水力模型求解獲得.此外,基于微觀模型的優(yōu)化調(diào)度方法不再將優(yōu)化問題分為泵站層次的水量分配和泵站內(nèi)部的水泵組合優(yōu)化兩個子問題,而是直接以水泵的開關(guān)狀態(tài)和轉(zhuǎn)速比作為決策變量來求解,避免了兩級優(yōu)化的協(xié)調(diào)和對優(yōu)化問題的分解求解等問題.在求解結(jié)構(gòu)上,采取最優(yōu)化模型與水力計算模型分離的模式(圖1),由水力模擬模塊計算參數(shù),向最優(yōu)化模型傳遞,避開對最優(yōu)化問題及約束條件的繁瑣數(shù)學(xué)分析和簡化(如求解函數(shù)梯度等),同時保證模塊自身的高內(nèi)聚與模塊之間的低耦合.這種求解模式的優(yōu)勢在于:①使模型更加靈活,可對水力計算模塊或者最優(yōu)化計算模塊獨(dú)立地修改或完善,以提高模型的整體性能.②模型結(jié)構(gòu)更適于分布式計算,將大量的計算負(fù)荷分散到更多的計算機(jī)CPU上執(zhí)行,大大提高模型的求解效率.3并行遺傳算法在管網(wǎng)優(yōu)化調(diào)度中應(yīng)用逐步在各個領(lǐng)域采用遺傳算法作為管網(wǎng)優(yōu)化調(diào)度問題的求解方法.由于內(nèi)在的類隨機(jī)搜索機(jī)制,造成遺傳算法較傳統(tǒng)的線性、非線性最優(yōu)化方法需更大的計算量,求解效率也較傳統(tǒng)搜索方法低.此外,遺傳算法求解還存在過早收斂于局部最優(yōu)解的問題.除了從編碼方式及遺傳算子本身等改進(jìn)外,另一改進(jìn)途徑是并行化.目前,傳統(tǒng)的遺傳算法在各個領(lǐng)域的研究及應(yīng)用已十分廣泛,而并行遺傳算法由于受到需并行計算硬件環(huán)境等限制,仍以基礎(chǔ)算法研究為主.但隨著并行計算技術(shù)、網(wǎng)絡(luò)通訊技術(shù)不斷發(fā)展和普及,針對并行遺傳算法在工程調(diào)度領(lǐng)域的研究及應(yīng)用也在逐漸增加.在水電站的優(yōu)化調(diào)度、電網(wǎng)的無功優(yōu)化、車間作業(yè)調(diào)度等應(yīng)用、研究方面,近期均有關(guān)于采用并行遺傳算法的文獻(xiàn)報道.近來,隨著管網(wǎng)微觀水力建模技術(shù)的不斷成熟,遺傳算法在管網(wǎng)優(yōu)化調(diào)度問題的研究及應(yīng)用也在不斷增多.同時,并行計算技術(shù)、計算機(jī)網(wǎng)絡(luò)的不斷發(fā)展,也為采用并行遺傳算法研究此類問題并最終應(yīng)用于工程實踐提供了可能.3.1新一代種群的形成遺傳算法是一種適合求解大型組合優(yōu)化問題的算法,對決策變量編碼后會形成有限長的字符串——染色體或個體.每個個體都對應(yīng)優(yōu)化問題的一個可行解.一組個體組成一代種群.對該種群模擬進(jìn)化過程,運(yùn)用優(yōu)勝劣汰原則,通過選擇、交換、變異等遺傳操作形成新一代種群,如此“選擇—交換—變異—再選擇”,不斷重復(fù),使各代種群的優(yōu)良基因成分逐漸積累,直到種群趨于成熟,即找到問題的最優(yōu)解.3.2狀態(tài)轉(zhuǎn)換編碼針對泵站中存在定速泵和變速泵兩類情形,分別以二進(jìn)制0/1和實數(shù)編碼0～1.0表達(dá)定速泵的開/關(guān)狀態(tài)和變速泵的轉(zhuǎn)速比,并以編碼串組合來表達(dá)管網(wǎng)中所有水泵的運(yùn)行狀態(tài),形成用以表達(dá)某種調(diào)度方案的染色體個體,再由一定量染色體個體組合形成種群.這種編碼方式的優(yōu)點(diǎn)在于既能保證決策變量與編碼結(jié)構(gòu)在形式上的統(tǒng)一,也避免了用多位二進(jìn)制編碼映射實數(shù)值時的額外計算開銷,從而提高了算法的搜索效率.3.3建立最優(yōu)個體緩沖池并行遺傳算法主要分為主從式(僅實現(xiàn)適應(yīng)度評估的并行化)、粗粒度、細(xì)粒度三種架構(gòu).限于研究的硬件條件,在單臺計算機(jī)上采用多線程技術(shù)設(shè)計偽并行遺傳算法,模擬粗粒度并行計算環(huán)境.方法實現(xiàn):將種群分解為同等規(guī)模的m個子種群(m>1),分別初始化并進(jìn)化計算.同時,為m個子種群建立一個最優(yōu)個體緩沖池,當(dāng)子種群進(jìn)化至一定代數(shù)時,通過自身的遷移算子執(zhí)行個體遷移計算.不同于真正的并行算法,本方法所實現(xiàn)的偽并行算法無須維護(hù)各計算節(jié)點(diǎn)之間所形成一定規(guī)則的拓?fù)?而是所有遷移算子都通過最優(yōu)個體緩沖池來實現(xiàn)群體之間最優(yōu)個體的交換.緩沖池設(shè)計為單入口單出口的管道式結(jié)構(gòu),具體方法是,執(zhí)行至一定進(jìn)化代數(shù)后,子群體首先將內(nèi)部最優(yōu)的x個個體送入緩沖池,同時從緩沖池的出口側(cè)取走x個個體替換內(nèi)部最差的x個個體.為避免由于多線程模式引起緩沖池數(shù)據(jù)的存取沖突,設(shè)計一組變量監(jiān)視緩沖池各位置上的個體的空/滿的狀態(tài)變化,通過緩沖池群體每隔一定進(jìn)化代數(shù),可以與其他群體充分交換彼此的優(yōu)異進(jìn)化個體,增加了搜索到更為優(yōu)異個體的可能性,也一定程度地避免了單種群進(jìn)化過程中的過早收斂問題(圖2).4偽并行遺傳算法和傳統(tǒng)知識的比較,及其與其他傳統(tǒng)知識的比較,可實現(xiàn)偽并行遺傳算法優(yōu)化調(diào)度計算方法優(yōu)化調(diào)度計算方法的比較,以我國目前還確定了偽并行遺傳算法優(yōu)化調(diào)度計算方法在網(wǎng)絡(luò)上的應(yīng)用.為考察所設(shè)計偽并行遺傳算法的求解效率和問題解的質(zhì)量,以南方某市供水管網(wǎng)為例,利用偽并行遺傳算法優(yōu)化調(diào)度計算,并與傳統(tǒng)的單種群非并行遺傳算法進(jìn)行比較.4.1管網(wǎng)和水泵的按需分布和設(shè)置一個微水力模型(1)該市管網(wǎng)建立了較為完善和可靠的數(shù)據(jù)采集與監(jiān)控(SCADA)系統(tǒng),可以實時監(jiān)測管網(wǎng)中水廠的出水壓力、流量以及分布于管網(wǎng)中的30多個測壓點(diǎn)的壓力變化.(2)已經(jīng)建立供水管網(wǎng)的管徑500mm以上微觀水力模型,精度滿足實際工程的需要,可用于優(yōu)化調(diào)度計算(圖3).(3)管網(wǎng)內(nèi)無高地水池或水庫等調(diào)節(jié)設(shè)施.(4)全市不分晝夜實施統(tǒng)一電價.(5)其中一個水廠二級泵站配有調(diào)速泵,調(diào)度須同時考慮水泵轉(zhuǎn)速的優(yōu)化.4.2優(yōu)化協(xié)議模型的主要限制因素(1)控制壓力范圍設(shè)定整個管網(wǎng)中節(jié)點(diǎn)的最小服務(wù)水頭約束為20m,同時根據(jù)調(diào)度經(jīng)驗,為保證供水壓力的均勻性,控制分布在管網(wǎng)不同位置的3個測壓點(diǎn)的壓力范圍,分別為控制點(diǎn)1(32～34m),控制點(diǎn)2(34～36m),控制點(diǎn)3(34～36m).(2)制水成本目標(biāo)函數(shù)管網(wǎng)中共有5個水廠和2個加壓泵站(圖3),各水廠二泵站的出水量受水廠制水能力的限制.由于位置標(biāo)高不同和工藝差異,各水廠制水成本也有所不同.這些均以參數(shù)形式在費(fèi)用目標(biāo)函數(shù)中體現(xiàn).(3)泵送流量限制根據(jù)各水泵型號,結(jié)合特性曲線,設(shè)定對應(yīng)高效段的流量范圍.4.3偽并行算法對傳統(tǒng)遺傳算法的改進(jìn)效果對某日某一時段,采用遺傳算法,按個體數(shù)為25,50,100的單一群體S25,S50,S100,個體數(shù)分別為25和50的雙群體P25及P50等五種情形進(jìn)行求解,進(jìn)化代數(shù)均為100,每種情形均求解20次,所得到的最小目標(biāo)函數(shù)值的分布情況如表1及圖4所示.可以看出,S25的求解質(zhì)量最差.原因在于群體規(guī)模較小,在遺傳算子特別是選擇算子的作用下,群體在100代內(nèi)很快就進(jìn)入收斂階段;但由于群體進(jìn)化并不充分,群體陷入局部最優(yōu)解,而且解的質(zhì)量較差.S50的求解質(zhì)量有顯著改善,所求的目標(biāo)函數(shù)值大部分低于21000元.但S100對S50解的改善并不大.當(dāng)采用偽并行算法求解時,求解質(zhì)量均優(yōu)于個體數(shù)相同的單群體進(jìn)化的結(jié)果,其中P25顯然有效地改善了單群體進(jìn)化時陷入的局部收斂問題,解的質(zhì)量也有較大提高,甚至搜索到所有計算結(jié)果中的最小值.為進(jìn)一步說明偽并行算法對傳統(tǒng)遺傳算法的改進(jìn)效果,對S50,S100,P25及P50的20次計算結(jié)果中的最小目標(biāo)函數(shù)值逐代取平均值,繪制各自的群體最小目標(biāo)函數(shù)值隨進(jìn)化代數(shù)的變化曲線圖(圖5).從圖中可見,S25的求解效率及求解質(zhì)量最差,而P50的求解效率和解的質(zhì)量最高.P25在進(jìn)化初期的求解效率高于S50,但隨著進(jìn)化接近進(jìn)入成熟期,S25的求解質(zhì)量高于P25.這表明,個體總數(shù)過少時,偽并行遺傳算法的優(yōu)勢無法充分發(fā)揮.當(dāng)個體總數(shù)為100時(P50及S100),并行群體求解優(yōu)勢明顯體現(xiàn).以上分析表明,對于所建立的多水源大型供水管網(wǎng)的優(yōu)化調(diào)度模型,采用以多種群并行進(jìn)化為主要特征的偽并行遺傳算法求解,較單一種群進(jìn)化的傳統(tǒng)遺傳算法,無論在求解效率還是質(zhì)量上都有較大程度的改善,甚至以較小規(guī)模并行進(jìn)化的種群可以獲得比較大規(guī)模單一進(jìn)化種群更為優(yōu)良的解.根據(jù)以上的試驗分析,采用P50方案的偽并行遺傳算法,對該市管網(wǎng)2002年9月27日8:00到次日7:00進(jìn)行優(yōu)化調(diào)度計算.為便于比較,以對應(yīng)時段實際供水量作為優(yōu)化調(diào)度計算時的管網(wǎng)用水量.計算結(jié)果如圖6所示.通過計算,在優(yōu)化調(diào)度方案下,當(dāng)日總運(yùn)行費(fèi)用為563143元,而實際總運(yùn)行費(fèi)用為587947元,當(dāng)日可節(jié)省運(yùn)行費(fèi)用24804元,占總費(fèi)用的4.2%.5其他并行技術(shù)(1)對于多水源大型城市給水管網(wǎng)優(yōu)化調(diào)度問題,所建立的基于管網(wǎng)微觀水力模型的最優(yōu)化數(shù)學(xué)模型和高內(nèi)聚、低耦合的求解模式,具有準(zhǔn)確度高、適應(yīng)性強(qiáng)、靈活度大等優(yōu)點(diǎn),并且更適用于并行算法或者分布式模型求解.(2)在求解方法上,采用遺傳算法對最優(yōu)化調(diào)度模型求解,并針對問題的特點(diǎn)對算法中遺傳個體的編碼方式改進(jìn),使其與決策變量的結(jié)構(gòu)更為契合,在一定