面向供水管網(wǎng)水力模型自動校核問題的改進遺傳算法①

劉佳明,王 寧,徐浩廣

1(中國科學(xué)院 沈陽計算技術(shù)研究所,沈陽 110168)

2(中國科學(xué)院大學(xué),北京 100049)

面向供水管網(wǎng)水力模型自動校核問題的改進遺傳算法①

劉佳明1,2,王 寧1,徐浩廣1,2

1(中國科學(xué)院 沈陽計算技術(shù)研究所,沈陽 110168)

2(中國科學(xué)院大學(xué),北京 100049)

水力模型自動校核旨在提高供水管網(wǎng)智能化管理中模型的準確性,目前廣泛使用遺傳算法進行自動校核.針對標準遺傳算法收斂速度慢,并且容易陷入局部最優(yōu)解的問題,本文對標準遺傳算法進了改進,利用模擬退火法對適應(yīng)度函數(shù)進行了拉伸,采用輪盤賭和最優(yōu)保留策略相合的方法代替?zhèn)鹘y(tǒng)的選擇方法,在交叉操作中加入了相似度函數(shù)避免了近親雜交,并且使用雙重收斂判斷準則減少不必要的計算時間. 引入G市某區(qū)域供水管網(wǎng)水力模型為案例,使用改進后的遺傳算法進行自動校核. 結(jié)果表明,改進的遺傳算法求解效率和求解精度都有較大的提高.

水力模型自動校核; 遺傳算法; 改進遺傳算法; 供水管網(wǎng)

隨著供水管網(wǎng)智能化管理的普及,各城市開始投入大量人力和財力構(gòu)建或完善管網(wǎng)水力模型. 供水管網(wǎng)水力不僅可以用于水廠優(yōu)化運營管理、供水調(diào)度,還可以成為其它相關(guān)研究的基礎(chǔ),如管網(wǎng)水質(zhì)模擬、突發(fā)性水質(zhì)污染事件預(yù)警與定位等. 水力模型自動校核是指通過程序自動調(diào)整模型中預(yù)先設(shè)置的水力參數(shù),使模型計算值與監(jiān)測值匹配的過程,其目的在于使構(gòu)建的水力模型能更準確的模擬管網(wǎng)的真實運行狀態(tài),達到預(yù)期使用的目的. Preis等[1]提出使用遺傳算法進行水力模型自動校核,并得到普遍應(yīng)用.

遺傳算法是借鑒生物進化理論和群體遺傳學(xué)思想,演變發(fā)展起來的一種具有應(yīng)用性廣泛、快捷方便的隨機搜索技術(shù)的優(yōu)化算法. 其編碼技術(shù)和遺傳操作比較簡單,對優(yōu)化問題的限制性條件要求低,具有很強的魯棒性和內(nèi)在的并行計算機制. 但它容易出現(xiàn)早熟現(xiàn)象和收斂速度慢的問題,導(dǎo)致不能獲得全局最優(yōu)解[2].

近年來國內(nèi)外學(xué)者對遺傳算法的改進做了很多研究工作. Kuo[10]提出了具有破壞性選擇的遺傳算法,通過使用最優(yōu)策略選擇出優(yōu)秀的個體和淘汰低劣的個體,能加快了種群的進化速度. De Jong[11]則使用自適應(yīng)交叉和變異算子使算法能朝全局最優(yōu)解的方向進行搜索.Goldberg等人[12]則將在簡單的遺傳算法中加入局部搜索機制——貪心算法,用來解決模糊尋優(yōu)問題. 國內(nèi)也很多學(xué)者對遺傳算法進行了改進研究,陳長征、王楠[13]對變異和交叉概率進行改進,能夠克服算法的早熟問題. 楊旭東[14]設(shè)計了自適應(yīng)選取適應(yīng)度函數(shù)的方法,避免了算法的局部收斂. 這些研究工作對遺傳算法的發(fā)展有著重要意義,為本文的研究奠定了良好的基礎(chǔ).

本文結(jié)合供水管網(wǎng)水力模型自動校核問題,針對標準遺傳算法收斂速度慢,并且容易陷入局部最優(yōu)解的問題,對標準遺傳算法進行了改進,利用模擬退火法對適應(yīng)度函數(shù)進行了拉伸,采用輪盤賭和最優(yōu)保留策略相合的方法代替?zhèn)鹘y(tǒng)的選擇方法,在交叉操作中加入了相似度函數(shù)避免了近親雜交,并且使用雙重收斂判斷準則減少不必要的計算時間. 最終引入G市某區(qū)域供水管網(wǎng)水力模型為案例,使用改進后的遺傳算法進行自動校核. 結(jié)果表明,改進的遺傳算法求解效率和求解精度都有較大的提高.

1 管網(wǎng)水力模型自動校核原理及問題建模

1.1 影響供水管網(wǎng)水力模型準確性的因素

(1) 管網(wǎng)基礎(chǔ)數(shù)據(jù)的準確性

在供水管系統(tǒng)模型中,要進行水力計算,那么就必須要以大量的數(shù)據(jù)作為基礎(chǔ),比如管網(wǎng)布置圖; 管道的長度、直徑、材料; 節(jié)點的方位、高低; 閥門的類別、大小、開啟程度、位置; 水庫或者水塔的大小、水位等都包括在內(nèi). 除此之外,水泵的運行曲線、停啟情況都包括在內(nèi). 管網(wǎng)水力模型的好壞與龐大而精準的數(shù)據(jù)有直接的關(guān)系,并在此基礎(chǔ)上創(chuàng)建水力模型. 其中所涉及到的數(shù)據(jù)是大而全面的,供水企業(yè)要將如此大量的數(shù)據(jù)進行管理是非常困難的,一般情況下,在進行數(shù)據(jù)的存儲時,使用數(shù)據(jù)庫或是GIS系統(tǒng),這樣就能夠讓數(shù)據(jù)的管理變得簡便.

(2) 管網(wǎng)拓撲圖形的完善性

管網(wǎng)拓撲圖實際上并沒有將所有的管段都包含在內(nèi),一些直徑教小的,不會過多的影響到水力條件的小管段都會在管網(wǎng)拓撲圖中進行相應(yīng)的減少或者是合并.但是,考慮到部分關(guān)鍵性小管段進行減少或者是合并后,在一定程度上影響到下游壓力,那么這樣做就是不合適的. 并且,有些管段的改變還會對水流的方向產(chǎn)生一定的影響,這些也是不能夠簡化的.

(3) 管網(wǎng)節(jié)點流量的不確定性

在計算管網(wǎng)的水力時,會進行虛擬節(jié)點流量的設(shè)計,這也是為了簡便出發(fā)的. 通常節(jié)點的流量就是管段流量的隨機集中,這樣就使得計算分配具有一種隨機性. 在進行計算時,采用這一方法可以說大大的簡化了程序,但是從實際的情況看來,還是有很大差距的,也會對管網(wǎng)的計算產(chǎn)生很大的影響,這樣所設(shè)計的模型是與實際的管網(wǎng)不相符合的. 假如出現(xiàn)流量用戶與節(jié)點分配錯誤的情況,那么將會非常嚴重的影響到局部的壓力分布以及管段流量分布.

(4) 管段摩阻系數(shù)的不確定性

對于供水管網(wǎng)管段的摩阻系數(shù)進行測量時,通常實際測量只是能夠?qū)⒁恍┚哂写硇砸约耙子跍y量的部分進行準確的測量,很多的管段都是不能夠進行有效測量的,一般對于不能測量的管段,會通過管段自身的屬性來進行進一步的摩阻值估算. 估算的結(jié)果實際上是不精確的.

1.2 供水管網(wǎng)水力模型自動校核問題建模

利用建模軟件EPANET2.0建立供水管網(wǎng)水力模型[3],并手工核實基礎(chǔ)數(shù)據(jù)后,利用管網(wǎng)上的壓力監(jiān)測點的實測值與模型的計算進行比較,對水力模型中的不確定參數(shù)(節(jié)點流量和管段摩阻系數(shù))進行調(diào)整,使得誤差滿足要求為止. 建立數(shù)學(xué)模型如下:

約束條件為:

f1,f2——分別為節(jié)點壓力和節(jié)點流量的量綱影響系數(shù);

Ω1,Ω2——壓力監(jiān)測點和管段監(jiān)測點的集合;

q——管段流量轉(zhuǎn)置矩陣;

q=(q1,q2,...,qn)T,單位為 m3/s;

Q——節(jié)點流量轉(zhuǎn)置矩陣,Q =(Q1,Q2,...,Qn)T,單位為m3/s;

h——管段水頭損失轉(zhuǎn)置矩陣,h= (h1,h2,...,hn)T,單位為m;

Qr——管段總供水量,單位為m3/s;

A,L——連續(xù)性方程和能量方程系統(tǒng)矩陣;

C——海曾-威廉系數(shù);

K——節(jié)點流量變化系數(shù);

Hmin——各節(jié)點的最低水壓要求,單位為m;

n,P——分別為節(jié)點數(shù)和管段數(shù).

F表示的水力模型的誤差,用遺傳算法求解時,作為目標函數(shù). 遺傳算法流程圖如圖1所示.

隨著經(jīng)濟科技的發(fā)展,供水管網(wǎng)上安裝了大量的傳感器并引入SCADA系統(tǒng),水力模型的更新周期也就大大縮短,用傳統(tǒng)的遺傳算法進行校核已滿足不了實時性. 所以提高算法效率是非常必要的.

2 改進遺傳算法設(shè)計

文獻[3]中采用標準遺傳算法對該模型進行求解,標準遺傳算法對參數(shù)要求高,收斂速度慢且容易陷入局部最優(yōu)解中,下面則結(jié)合該模型的特點對標準遺傳算法進行了改進.

2.1 染色體編碼

在水力模型校核中,每個節(jié)點流量和管段C值為一個基因,全體基因(所有節(jié)點流量和管段C值)構(gòu)成一個染色體,若干個染色體組成一個種群,遺傳操作以種群為單位進行,最終選出種群中最優(yōu)的染色體就作為問題的最優(yōu)解. 原有的二進制編碼用雙精度實數(shù)編碼進行取代,這樣就能夠改善由于海明距離的影響而造成二進制編碼表達困難的問題,從而整體上將編碼解碼的效率提升,無論是在精度上,還是在速度上,交叉與變異都得到了提升,實數(shù)編碼通過如下的方式實現(xiàn).

2.2 初始化群種

在解空間內(nèi)隨機生成N個染色體作為初始種群,每個染色體表示供水管網(wǎng)中所有不確定的管段摩阻系數(shù)C值和用戶節(jié)點的流量的編碼組合,N為種群的規(guī)模. 理論上種群規(guī)模越大包含的信息越豐富,更容易生成最終的優(yōu)良個體,但是種群規(guī)模越大,算法計算的代價也越大,因此一般取變量個數(shù)的線性級別,如有10個變量則N的取值范圍為10～100.

2.3 適應(yīng)度函數(shù)

遺傳算法中,適應(yīng)度是體現(xiàn)個體在生存環(huán)境中的適應(yīng)程度,表征個體的優(yōu)劣性,適應(yīng)度高的個體將會獲得更多的機會去產(chǎn)生后代,反之會在進化中逐漸滅絕.在本文模型中,適應(yīng)度f可以由目標函數(shù)值F轉(zhuǎn)化而來,目標函數(shù)值表示水力模型的誤差,值越小說明水力模型越精確. 而遺傳算法是努力將基因的適應(yīng)度函數(shù)最大化,因此將適應(yīng)度函數(shù)設(shè)定為目標函數(shù)的倒數(shù)即:f=1/F. 然后在遺傳算法后期,當(dāng)算法趨于收斂時,由于種群中個體適應(yīng)度差異較小,繼續(xù)優(yōu)化的潛能降低,常有可能獲得局部最優(yōu)解. 為此,本文利用模擬退火法(SA)對適應(yīng)度函數(shù)進行拉伸[4],避免個體的早熟現(xiàn)象.

式中:fi——第i個個體的適應(yīng)度;

g——遺傳代數(shù)序號;

N——種群個體數(shù);

T——溫度;

T0——初始溫度.

T值隨著進化次數(shù)g的增加而減少,當(dāng)g<30時,T=1.5×0.9g,否則T=0.01.

2.4 遺傳操作

2.4.1 選擇操作

選擇操作是種群進行過程中優(yōu)勝劣的手段,個體適應(yīng)度大的個體,其被選擇的概率越高,反之更可能被淘汰[5]. 標準的遺傳算法一般使用輪盤賭方式進行行選擇操作,但是在算法執(zhí)行過程中,若初始群體中存在一些適應(yīng)度比較好的個體,用輪盤賭方式這部分個體會繁殖更多的后代,占據(jù)了后代種群的主要部,而對于一些適度度較差的個體則會陷入滅絕的境地,如此就會破壞了種群的多樣性,導(dǎo)致算法陷入早熟收斂. 本文采用輪盤賭方式和最優(yōu)保留策略相結(jié)合的方法,步驟如下:

1) 首先求種群的平均適應(yīng)度以及每個個體的適應(yīng)度.

2) 如果個體的適應(yīng)度大于種群的平均適應(yīng)度,則保留下來,否則使用輪盤方法進行選擇.

3) 比較保留下來的適應(yīng)度最好的個體與截止目前找到的最好個體的適應(yīng)度值,比較大的那個個體作為新的截至目前最好的個體.

4) 將上一步找到的最好的個體不參與交叉和變異操作直接放到子代種群的第一位,其余的保留的個體進行交叉和變異操作.

這樣,不僅沒破壞種群的多樣性,而且還會向著最優(yōu)解的方向搜索,提高了運算效率.

2.4.2 交叉操作

如果其值小于閥值0.001p,說明雙親為近親. 這樣就避免了由于近親雜交而產(chǎn)生不良個體,保證遺傳操作的正常進行.

2.4.3 變異操作

變異操作是模擬生物進化過程的基因突變現(xiàn)象,用來保證種群的多樣性,防止早熟[7]. 在遺傳算法中,變異一般被看作為輔助算子,它作用在染色體上以較小概率Pm隨機改變?nèi)旧w上的某個基因. 本文在算法初期加大變異概率,使搜索空間更廣闊,在算法后期降低變異概率,防止算法變成隨機搜索不會收斂.

2.5 雙重收斂判斷準則

在設(shè)計遺傳算法的收斂準則時,一般采用設(shè)定總的進化次數(shù)I為收斂依據(jù),一旦進化次數(shù)達到I,就可以終止程序的運行. 但是,如果在算法執(zhí)行的過程中,初始群體以及其它參數(shù)選取非常理想的情況下,那么遺傳算法可以很快的搜尋到最優(yōu)解. 這種情況下,如果再采用總的進化次數(shù)I為收斂準則,就增加了不必要的計算時間[8]. 因此在算法執(zhí)行過程中,本文采用雙重收斂判斷準則:

(1) 總的進化次數(shù)I;

(2) 連續(xù)多次進化的優(yōu)化結(jié)果不變,或優(yōu)化結(jié)果小于某一提前設(shè)定的固定的小數(shù)ε.

在遺傳算法進化過程中,滿足上述兩個條件中的任何一個,都視為滿足收斂條件. 這樣的收斂準則就可以適當(dāng)減少不必要的計算時間.

3 案例應(yīng)用與結(jié)果分析

以G市某區(qū)域供水管網(wǎng)為例,建立相應(yīng)的水力模模型,引入SCADA數(shù)據(jù)庫中監(jiān)測值. 供水管網(wǎng)GIS圖見圖2,供水管網(wǎng)中有13壓力監(jiān)測點和6個流量計,在校核之前水力模型在24個時間段的平均壓力和流量誤差情況為表1所示.

圖2 G 市某區(qū)域供水管網(wǎng) GIS 圖

表1 水力模型壓力誤差統(tǒng)計

用標準遺傳算法和本文設(shè)計的改進遺傳算法分別對水力模型進行自動校核,調(diào)整供水管網(wǎng)水力模型中不確定的管段摩阻系數(shù)C值和用戶節(jié)點流量. 算法的各個參數(shù)設(shè)置如下: 初始種群大小N為300,迭代次數(shù)I為 100,ε為 0.1,交叉概率Pc為 0.8,變異概率Pm為0.05. 校核后,水力模型精度分別如表2 和表3 所示,算法的運行情況如圖3.

改進的遺傳算法相比于標準遺傳算法對水力模型自動校核結(jié)果更精確,另外標準遺傳算法難收斂到某一解,運行的時間也較長,而改進后的算法能跳出局部最優(yōu),找到更好的解,并且運行的時間也有較大的提高.

為證明改進算法的通用性,本文還選取了10個管網(wǎng)水力模型分別用和標準遺傳算法和改進的遺傳算法進行自動校核. 方法過程與G市相同,結(jié)果統(tǒng)計如圖4和圖5所示.

表2 標準遺傳算法校核后水力模型誤差統(tǒng)計

表3 本文改進遺傳算法校核后水力模型誤差統(tǒng)計

圖3 兩種算法的運行情況

圖4 10 次測試收斂次數(shù)比較

由對比圖可以發(fā)現(xiàn),改進的算法無論在收斂次數(shù)還是在收斂時間方面都有較大的提高.

圖5 10 次測試收斂耗時比較 (單位: s)

4 結(jié)論

本文對供水管網(wǎng)水力模型自動校核問題進行了描述,并建立了問題模型,針對標準遺傳算法求解效率低并且容易陷入局部最優(yōu)解的情況,采用改進的適應(yīng)度函數(shù)、選擇操作、交叉操作、變異操作以及使用雙重判斷收斂準則重新設(shè)計了算法,最后引入實際案例分別用標準遺傳算法和改進算法進行求解,并對結(jié)果進行了比較分析,驗證了改進的效果. 但用本文改進的遺傳算法對大型供水管網(wǎng)水力模型自動校核需要數(shù)小時,對要求實時進行校核的供水管網(wǎng)水力模型仍難以滿足,因此如何大幅度提高遺傳算法的運行時間有待下一步研究.

1Preis A,Allen M,Whittle AJ. On-line hydraulic modeling of a water distribution system in Singapore. Proc. of the 12th Annual Conference on Water Distribution Systems Analysis(WDSA). Singapore. 2012. 1336–1348.

2曳永芳,杜永清,行小帥. 一種抑制早熟收斂的改進遺傳算法. 山西師范大學(xué)學(xué)報 (自然科學(xué)版),2010,24(2): 24–28.

3孫柏. 供水管網(wǎng)水力水質(zhì)模型及其校核研究[碩士學(xué)位論文].長沙: 湖南大學(xué),2012.

4姚明海,王娜,趙連朋. 改進的模擬退火和遺傳算法求解TSP 問題. 計算機工程與應(yīng)用,2013,49(14): 60–65. [doi:10.3778/j.issn.1002-8331.1211-0133]

5史明霞,陶林波,沈建京. 自適應(yīng)遺傳算法的改進與應(yīng)用.微計算機應(yīng)用,2006,27(4): 405–408.

6吉根林. 遺傳算法研究綜述. 計算機應(yīng)用與軟件,2004,21(2): 69–73.

7琚潔慧. 改進適應(yīng)度函數(shù)的遺傳算法. 電腦知識與技術(shù),2005,(15): 80–83.

8李書全,孫雪,孫德輝,等. 遺傳算法中的交叉算子的述評.計算機工程與應(yīng)用,2012,48(1): 36–39.

9周松儒. 遺傳算法的混合改進研究及其應(yīng)用[碩士學(xué)位論文].南寧: 廣西大學(xué),2014.

10Glodberg DE,Kuo CH. Genetic algorithms in pipeline optimization. Computing in Civil Engineering,1987,1(2):128–141.

11Jong KAD. An analysis of the behavior of a class of genetic adaptive systems. University of Michigan,1975.

12Goldberg DE. Genetic Algorithms in Search,Optimization,and Machine Learning. Massachusetts: Addison-Wisley,Reading,1989.

13陳長征,王楠. 遺傳算法中交叉和變異概率選擇的自適應(yīng)方法及作用機理. 控制理論與應(yīng)用,2002,19(1): 41–43.[doi: 10.3969/j.issn.1000-8152.2002.01.007]

14楊旭東,張彤. 遺傳算法應(yīng)用于系統(tǒng)在線識別研究. 哈爾濱工業(yè)大學(xué)學(xué)報,2000,32(1): 102–105. [doi: 10.3321/j.issn:0367-6234.2000.01.027]

Improved Genetic Algorithm for Automatic Calibration of Water Supply Hydraulic Model

LIU Jia-Ming1,2,Wang Ning1,XU Hao-Guang1,2

1(Shenyang Institute of Computing Technology,Chinese Academy of Sciences,Shenyang 110168,China)
2(University of Chinese Academy of Sciences,Beijing 100049,China)

The automatic calibration of hydraulic model aims to improve the accuracy of the model of water supply network intelligent management. Currently,the genetic algorithm is widely used for automatic of hydraulic model. In view of problems that the standard genetic algorithm has slow convergence and can be easily trapped in local optimal,the paper makes some improvements of this algorithm. Simulated annealing algorithm is used to stretch the fitness function and the roulette wheel selection method combining elitism strategy is replacing the traditional selection method. Besides,the similarity function is added to avoid the breeding with closest relatives in cross operator and the double convergence criteria is used to reduce unnecessary computation time. The improved genetic algorithm is used to calibrate the water supply hydraulic model of G. The results show that the improved genetic algorithm has better efficiency and accuracy.

automatic calibration of hydraulic model; genetic algorithm; improved genetic algorithm; water supply network

劉佳明,王寧,徐浩廣.面向供水管網(wǎng)水力模型自動校核問題的改進遺傳算法.計算機系統(tǒng)應(yīng)用,2017,26(12):104–109. http://www.c-sa.org.cn/1003-3254/6069.html

遼寧省科技計劃-環(huán)境預(yù)警項目(20150303)

2017-03-03; 修改時間: 2017-03-20; 采用時間: 2017-03-27