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

劉佳明,王 寧,徐浩廣

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

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

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

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

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

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

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

水力模型自動校核; 遺傳算法; 改進遺傳算法; 供水管網

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

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

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

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

1 管網水力模型自動校核原理及問題建模

1.1 影響供水管網水力模型準確性的因素

(1) 管網基礎數據的準確性

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

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

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

(3) 管網節點流量的不確定性

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

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

對于供水管網管段的摩阻系數進行測量時,通常實際測量只是能夠將一些具有代表性以及易于測量的部分進行準確的測量,很多的管段都是不能夠進行有效測量的,一般對于不能測量的管段,會通過管段自身的屬性來進行進一步的摩阻值估算. 估算的結果實際上是不精確的.

1.2 供水管網水力模型自動校核問題建模

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

約束條件為:

f1,f2——分別為節點壓力和節點流量的量綱影響系數;

Ω1,Ω2——壓力監測點和管段監測點的集合;

q——管段流量轉置矩陣;

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

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

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

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

A,L——連續性方程和能量方程系統矩陣;

C——海曾-威廉系數;

K——節點流量變化系數;

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

n,P——分別為節點數和管段數.

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

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

2 改進遺傳算法設計

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

2.1 染色體編碼

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

2.2 初始化群種

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

2.3 適應度函數

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

式中:fi——第i個個體的適應度;

g——遺傳代數序號;

N——種群個體數;

T——溫度;

T0——初始溫度.

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

2.4 遺傳操作

2.4.1 選擇操作

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

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

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

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

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

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

2.4.2 交叉操作

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

2.4.3 變異操作

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

2.5 雙重收斂判斷準則

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

(1) 總的進化次數I;

(2) 連續多次進化的優化結果不變,或優化結果小于某一提前設定的固定的小數ε.

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

3 案例應用與結果分析

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

圖2 G 市某區域供水管網 GIS 圖

表1 水力模型壓力誤差統計

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

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

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

表2 標準遺傳算法校核后水力模型誤差統計

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

圖3 兩種算法的運行情況

圖4 10 次測試收斂次數比較

由對比圖可以發現,改進的算法無論在收斂次數還是在收斂時間方面都有較大的提高.

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

4 結論

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

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

3孫柏. 供水管網水力水質模型及其校核研究[碩士學位論文].長沙: 湖南大學,2012.

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

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

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

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

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

9周松儒. 遺傳算法的混合改進研究及其應用[碩士學位論文].南寧: 廣西大學,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陳長征,王楠. 遺傳算法中交叉和變異概率選擇的自適應方法及作用機理. 控制理論與應用,2002,19(1): 41–43.[doi: 10.3969/j.issn.1000-8152.2002.01.007]

14楊旭東,張彤. 遺傳算法應用于系統在線識別研究. 哈爾濱工業大學學報,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

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

遼寧省科技計劃-環境預警項目(20150303)

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