基于改進SPEA2算法的給水管網(wǎng)多目標優(yōu)化設計

孟勤超，楊翠麗，喬俊飛

（1. 北京工業(yè)大學 信息學部，北京 100124; 2. 北京工業(yè)大學 計算智能與智能系統(tǒng)北京市重點實驗室，北京 100124）

給水管網(wǎng)是城市重要基礎設施，是整個城市得以生存和發(fā)展的命脈[1]。同時，給水管網(wǎng)投資巨大，往往占到整個供水系統(tǒng)的60%～80%，而且還涉及龐大的運行動力費和運行管理費[2]。

給水管網(wǎng)的優(yōu)化設計，一般是在工程資金投入有限的情況下，尋求滿足用戶用水需求，且使整個系統(tǒng)的造價最低可靠性最高的設計方案。因此，管網(wǎng)的優(yōu)化設計直接影響到整個供水系統(tǒng)的經(jīng)濟性和可靠性[3]。由于管網(wǎng)系統(tǒng)的非線性和管徑的離散性，管網(wǎng)的多目標優(yōu)化求解十分困難，成為了國內(nèi)外眾多學者研究的熱點問題。文獻[4]第一個將結構化混合遺傳算法(structured messy genetic algor-ithm, SMGA)應用到給水管網(wǎng)多目標優(yōu)化中，并將系統(tǒng)造價最低、收益最大作為兩個目標，求得了一系列非支配解，但是SMGA算法的求解效率和所得解的多樣性較差。文獻[5]建立了以管網(wǎng)造價最小、管網(wǎng)壓降最小為目標的優(yōu)化模型，并采用多目標粒子群算法(multi-objective particle swarm optimization algorithm, MOPSO)進行優(yōu)化，但是MOPSO算法不適合離散變量的優(yōu)化問題。文獻[6]建立了以管網(wǎng)造價最小、水質(zhì)最優(yōu)為目標的優(yōu)化模型，且采用多目標遺傳算法(multi-objective optimization genetic algorithm, MOGA)進行管網(wǎng)優(yōu)化設計，其研究的重點主要為管網(wǎng)模型的設計。文獻[7]以管網(wǎng)造價最低、可靠性最高為目標，建立了3個目標的管網(wǎng)優(yōu)化模型，并采用快速非支配排序遺傳算法(nondominated sorting genetic algorithm II, NSGA-II)優(yōu)化管網(wǎng)模型，取得了較好的效果，但是NSGA-II算法容易陷入局部最優(yōu)，使獲得的解分布不均勻。

目前，智能優(yōu)化算法在解決管網(wǎng)多目標優(yōu)化問題中取得了廣泛的應用，但解的多樣性和收斂性不好是其存在的主要問題，因此提高多目標優(yōu)化算法解的多樣性和收斂性成為重要的研究方向[8-10]。文獻[11]提出了強度帕累托進化算法(strength Pareto evolutionary algorithm 2, SPEA2)，通過引入密度估計策略和歸檔集截斷算法，從一定程度上提高了算法解的多樣性和收斂性。文獻[12]提出的NSGAII算法，其快速非支配排序和擁擠距離策略提高了多樣性和收斂性。這兩種算法均能從一定程度上提高算法的性能，但是都將多目標優(yōu)化問題作為一個整體優(yōu)化。因此當目標數(shù)大于2時，這兩種算法的搜索性能急劇下降。文獻[13]提出了基于分解的多目標進化算法(multi-objective evolutionary algorithm based on decomposition, MOEA/D)，將一個多目標優(yōu)化問題分解為多個單目標優(yōu)化問題，通過同時優(yōu)化所有的單目標子問題，提高了算法解的多樣性和收斂性。但是，對于具有不同Pareto前沿的多目標優(yōu)化問題，MOEA/D卻使用了相同的權值向量。文獻[14]基于支配和分解的框架，在NSGA-II算法基礎上，結合一組提前設定的參考點，提出了NSGAIII算法。雖然NSGA-III算法進一步提高了解的多樣性和收斂性，但是其收斂速度依然較慢，而且固定的參考點使得具有不同Pareto前沿的多目標優(yōu)化問題難以達到相同的優(yōu)化效果。

本文采用SPEA2算法[11]作為基礎，結合NSGAIII中基于支配和分解的思想，提出了一種基于參考向量的強度帕累托進化算法(strength Pareto evolutionary algorithm 2 based on reference vectors, RVSPEA2)，其目的是提高算法的多樣性和收斂性，并采用文獻[7]的3個目標作為管網(wǎng)優(yōu)化模型，將其應用到雙環(huán)管網(wǎng)、紐約管網(wǎng)以及實際的管網(wǎng)優(yōu)化案例中。

1 給水管網(wǎng)優(yōu)化模型描述

給水管網(wǎng)優(yōu)化設計的目的是在滿足用戶用水需求的前提下，使管網(wǎng)經(jīng)濟性最低和可靠性最高，并求出最優(yōu)管線直徑。本文中采用管網(wǎng)造價作為經(jīng)濟性目標，節(jié)點富余水頭總和與節(jié)點富余水頭方差作為可靠性目標，建立給水管網(wǎng)優(yōu)化模型。

1.1 目標函數(shù)

為了簡化管網(wǎng)優(yōu)化計算，本文采用管網(wǎng)造價作為經(jīng)濟性目標，其目標函數(shù)如式(1)：

式中：Z為管網(wǎng)總造價；Dj、Lj分別為第j根管段的直徑、長度；Cj(Dj)為管徑為Dj的管段的單位長度造價；P為管網(wǎng)中管段總數(shù)。

管網(wǎng)的可靠性目標可用節(jié)點富余水頭總和與節(jié)點富余水頭方差表示。其相關定義如下。

每個節(jié)點的富余水頭Isi計算如式(2)：

式中：Hi為管網(wǎng)節(jié)點i的水壓標高；Hmin為管網(wǎng)節(jié)點所要求的最小自由水壓；I為管網(wǎng)中節(jié)點總數(shù)。

給水管網(wǎng)節(jié)點富余水頭總和Is為

節(jié)點富余水頭均值Is為

節(jié)點富余水頭方差S為

因此，給水管網(wǎng)多目標優(yōu)化模型可表示為

管網(wǎng)總造價Z越小，表明管網(wǎng)系統(tǒng)經(jīng)濟性越高。節(jié)點富余水頭Is是指節(jié)點自由水頭超過節(jié)點所要求的最小自由水頭的部分水頭，它與管網(wǎng)水壓呈線性關系。在滿足管網(wǎng)約束的條件下，節(jié)點富余水頭越小，管網(wǎng)水壓就越低。節(jié)點富余水頭總和越大，即管網(wǎng)水壓總和越大，一方面反映了資源浪費的情況，另一方面也代表了管網(wǎng)存在爆管的危險。另外，節(jié)點富余水頭方差S反映了管網(wǎng)中各節(jié)點富余水頭的分布情況。節(jié)點富余水頭方差越大，說明了管網(wǎng)中各節(jié)點壓力分布不均，亦存在爆管的危險。因此，節(jié)點富余水頭總和與節(jié)點富余水頭方差越小，表明管網(wǎng)系統(tǒng)可靠性越高。

1.2 約束條件

除了優(yōu)化目標之外，給水管網(wǎng)的優(yōu)化還必須滿足下列約束條件。

1) 節(jié)點流量連續(xù)性約束管網(wǎng)中每個節(jié)點應滿足：

式中：A為節(jié)點關系矩陣，g為與該節(jié)點相連的管段流量，G為節(jié)點流量。

2) 能量平衡約束

管網(wǎng)中閉合回路水頭損失代數(shù)和為零，即

式中：ΔHk為閉合回路l中管段k的水頭損失，L是管網(wǎng)中所有閉合回路。

3) 節(jié)點流量連續(xù)性約束

管網(wǎng)中每個節(jié)點應滿足

式中：Hi為節(jié)點i的水頭，Hmin和Hmax分別為節(jié)點最小水頭和最大水頭。

4) 能量平衡約束

管網(wǎng)中每個管段直徑應滿足：

式中：Dj為管段j的直徑，D1～Dm為標準管徑。

2 基于參考向量的強度帕累托進化算法RVSPEA2

本文基于SPEA2算法，與基于支配和基于分解的選擇機制相結合，提出了一種基于參考向量的強度帕累托進化算法(RVSPEA2)，旨在進一步提高算法解的多樣性和收斂性，以解決給水管網(wǎng)的多目標優(yōu)化問題。

2.1 基于參考向量的選擇機制

在SPEA2算法的環(huán)境選擇過程中，當前種群中所有的非支配解被放入外部歸檔集中。如果外部歸檔集|Qt|≥N(預設值)，則通過最小距離截斷算法刪除個體，直至|Qt|=N；如果外部歸檔集|Qt|＜N(預設值)，則隨機選擇支配解放入外部歸檔集，直至|Qt|=N。而在RVSPEA2中，當外部歸檔集|Qt|＜N時，引入?yún)⒖枷蛄浚鶕?jù)非支配解與參考向量的關系，有目標地選擇支配解放入外部歸檔集，其選擇機制將在本節(jié)中詳細介紹。

2.1.1 自適應目標歸一化

在實際的多目標優(yōu)化問題中，各目標的范圍往往差別很大，其對優(yōu)化結果影響巨大[15]。因此，為了解決目標范圍不同的優(yōu)化問題，RVSPEA2采用了一種簡單的目標歸一化方法，即對于第j代種群的第i個目標函數(shù) fi,j(x)，其歸一化如式(11)：

2.1.2 參考向量的生成

為了探索和開發(fā)整個搜索空間，RVSPEA2采用了一種簡單且有效的方法用于生成參考向量。首先，在整個歸一化目標空間生成Km個參考點，其中m為目標個數(shù)，K的計算公式如式(12)：

圖 1 當m=3，K=3時歸一化空間中的27個參考點Fig. 1 Twenty-seven reference points on the normalized objective space for a three-objective problem with K=3

2.1.3 關聯(lián)操作

生成參考向量后，將種群中每個成員都關聯(lián)一個參考向量。首先，計算種群成員與每一個參考向量的垂直距離，如式(13)所示。與每個成員垂直距離最近的參考向量將與該成員相關聯(lián)，如式(14)：

式中：q 為種群成員，w 為參考向量，d⊥(q;w)代表q 與w 的垂直距離，∥·∥代表向量的模，R 為參考向量集合，函數(shù)argmin 可計算出當目標函數(shù)d⊥(q;w)最小時的變量值w。

圖 2 當m=3，K=3時歸一化空間中的參考向量Fig. 2 Reference vectors on the normalized objective spacefor a three-objective problem with K=3

2.1.4 環(huán)境選擇操作

經(jīng)過關聯(lián)操作后，一個參考向量可能會有一個或多個種群成員與之相關聯(lián)，甚至沒有種群成員與之相關聯(lián)[16]。當外部歸檔集|Qt|＜N時，通過統(tǒng)計已有成員所關聯(lián)的參考向量，排除這部分參考向量，從剩余參考向量所關聯(lián)的種群成員中選擇成員填滿外部歸檔集。當外部歸檔集|Qt|≥N時，則依然通過最小距離截斷算法刪除個體[6]，直至|Qt|=N。通過參考向量選擇可以保證算法初期優(yōu)化解的多樣性，避免算法陷入局部最優(yōu)；而在算法后期，在保證算法收斂性的同時，通過最小距離截斷算法，進一步提高算法的多樣性。

2.2 算法流程及性能測試

設種群大小為N，最大進化代數(shù)為T，RVSPEA2算法的具體流程如下：

1) 初始化種群P0和外部歸檔集Q0，進化代數(shù)t=0；

2) 合并 Pt和 Qt為 Qt+1；

3) 計算種群Qt+1中各成員的適應度；

4) 通過選擇機制，從Qt+1中選出N個成員；

5) 進行錦標賽選擇配對、單點交叉和均勻變異操作，得到Pt+1；

6) 計算t=t+1，并判斷算法的終止條件，若滿足則進行下一步，否則轉(zhuǎn)至2)；

7) 通過選擇機制選出N個非支配解，并輸出結果。

為了驗證算法的性能，將RVSPEA2算法與SPEA2、NSGA-II和MOEA/D進行對比，用于優(yōu)化雙環(huán)管網(wǎng)和紐約管網(wǎng)，其布局圖分別如圖3和圖4所示，其節(jié)點水壓和管段長度等詳細數(shù)據(jù)參照文獻[17]。為了比較算法所得解的多樣性和收斂性，本文采用了以下3個性能指標。

圖 3 雙環(huán)管網(wǎng)Fig. 3 Two-loop network

圖 4 紐約管網(wǎng)Fig. 4 New York Tunnels network

1) IGD(inverted generational distance)[18]

IGD的定義如式(15)，其中P*為一組均勻分布在Pareto前沿上的解，P為算法所求得的非支配解，d(x, P)代表解x與P中解的最小歐式距離。如果P*中解的數(shù)量足夠多，IGD在一定程度上能同時反映解的多樣性和收斂性。IGD的值越小，算法所得解的多樣性和收斂性越好。

2) GD(generational distance)[19]

GD的定義如式(16)所示，其用于計算非支配解與Pareto前沿之間的距離。GD的值越小，算法所得解的收斂性越好。

3) SP(spacing)[20]

SP用于計算非支配解中相鄰解之間距離的方差，其公式如式(17)：

對于雙環(huán)管網(wǎng)問題，RVSPEA2算法具體參數(shù)設置如表1所示，為了公平對比，SPEA2、NSGA-II和MOEA/D的參數(shù)設置與本文所提算法相同，每種算法均獨立運行30次。表2列出了SPEA2、NSGA-II、MOEA/D與本文提出的RVSPEA2算法優(yōu)化雙環(huán)管網(wǎng)的結果。從表2中可以看出，在IGD、GD和SP 3個指標的均值上，本文提出的RVSPEA2算法都優(yōu)于其他算法，說明在雙環(huán)管網(wǎng)問題上，RVSPEA2算法所得解的多樣性和收斂性最好。

表 1 雙環(huán)管網(wǎng)和紐約管網(wǎng)參數(shù)設置Table 1 Parameters of two-loop network and New York tunnels network

對于紐約管網(wǎng)問題，RVSPEA2算法具體參數(shù)設置如表1所示，SPEA2、NSGA-II和MOEA/D的參數(shù)設置與RVSPEA2算法相同，每種算法均獨立運行30次。表3列出了SPEA2、NSGA-II、MOEA/D與本文提出的RVSPEA2算法優(yōu)化紐約管網(wǎng)的結果。從表3中可以看出，本文提出的RVSPEA2算法在IGD、GD和SP這3個指標的均值上，都優(yōu)于其他算法。因此，在紐約管網(wǎng)問題上，RVSPEA2算法所得解的多樣性和收斂性也優(yōu)于SPEA2、NSGAII和MOEA/D算法。

表 2 雙環(huán)管網(wǎng)優(yōu)化結果Table 2 Optimization results for two-loop network

表 3 紐約管網(wǎng)優(yōu)化結果Table 3 Optimization result for New York tunnels network

通過雙環(huán)管網(wǎng)和紐約管網(wǎng)的測試，驗證了本文提出的RVSPEA2算法在解決管網(wǎng)多目標優(yōu)化設計上的性能。

3 工程實例

現(xiàn)將RVSPEA2算法應用于實際管網(wǎng)中。本實例為北京市某高校給水管網(wǎng)設計工程，管網(wǎng)布局如圖5所示，管網(wǎng)中有1個水源、43個節(jié)點和60條管線。RVSPEA2算法參數(shù)設置如表4所示。圖6畫出了RVSPEA2算法所求出的非支配解。在實際工程應用中，應根據(jù)實際工程情況和決策者的經(jīng)驗，在保證供水基本可靠及居民正常用水的情況下，合理地選擇一個施工方案。針對該實際工程問題，本文給出3個施工方案以供決策者選擇，如表5所示。當資金有限時，應選擇造價較低的方案，如方案A；當資金充足、管網(wǎng)可靠性更重要時，可采用節(jié)點富余水頭總和小、節(jié)點富余水頭方差小的方案，如方案C；當資金和管網(wǎng)可靠性同等重要時，可選擇方案B。

圖 5 工程實例Fig. 5 Engineering example

表 4 工程實例參數(shù)設置Table 4 Parameters for engineering example

圖 6 工程實例的非支配解Fig. 6 Non-dominated solutions for engineering example

表 5 3種不同情況下的施工方案Table 5 Construction schemes for three different cases

4 結束語

針對管網(wǎng)多目標優(yōu)化問題，本文結合選擇機制中支配和分解的思想，提出了一種基于參考向量的強度帕累托進化算法——RVSPEA2。該算法通過在目標空間中生成均勻分布的點，生成一組參考向量，并基于SPEA2算法的選擇機制，將進化產(chǎn)生的解與各參考向量相關聯(lián)，通過參考向量配合支配強度進行解的選擇，提高了算法解的多樣性和收斂性。兩個經(jīng)典管網(wǎng)的驗證表明了RVSPEA2算法解決管網(wǎng)多目標優(yōu)化問題的有效性。最后，本文將RVSPEA2算法應用于工程實例，并給出3種施工方案以供決策者選擇。

[1]ALPEROVITS E, SHAMIR U. Design of optimal water distribution systems[J]. Water resources research, 1977, 13(6):885–900.

[2]MURPHY L J, SIMPSON A R, DANDY G C. Design of a pipe network using genetic algorithms[J]. Water-melbourne then artarmon, 1993, 20(4): 40–42.

[3]MORGAN D R, GOULTER I C. Optimal urban water distribution design[J]. Water resources research, 1985, 21(5):642–652.

[4]HALHAL D, WALTERS G A, OUAZAR D, et al. Water network rehabilitation with structured messy genetic algorithm[J]. Journal of water resources planning and management, 1997, 123(3): 137–146.

[5]MONTALVO I, IZQUIERDO J, SCHWARZE S, et al.Multi-objective particle swarm optimization applied to water distribution systems design: an approach with human interaction[J]. Mathematical and computer modelling, 2010,52(7/8): 1219–1227.

[6]LIU Haixing, YUAN Yixing, ZHAO Ming, et al. Hybrid multi-objective genetic algorithm for optimal design of water supply network[C]//Proceedings of the 12th Annual Conference on Water Distribution Systems Analysis. Tucson,United States, 2010: 899–908.

[7]劉書明, 李明明, 王歡歡, 等. 基于NSGA-II算法的給水管網(wǎng)多目標優(yōu)化設計[J]. 中國給水排水, 2015, 31(5): 50–53.LIU Shuming, LI Mingming, WANG Huanhuan, et al.Multi-objective optimization design of water distribution system based on non-dominated sorting genetic algorithm-II[J]. China water and wastewater, 2015, 31(5): 50–53.

[8]蔣懷德. 給水管網(wǎng)多目標優(yōu)化設計[D]. 上海：同濟大學,2007, 5–7.JIANG Huaide. Multi-objective optimization design of urban water distribution networks[D]. Shanghai: Tongji University, 2007, 5–7.

[9]LI Mingming, LIU Shuming, ZHANG Ling, et al. Nondominated sorting genetic algorithms-iibased on multi-objective optimization model in the water distribution system[J].Procedia engineering, 2012, 37: 309–313.

[10]TOLSON B A, MAIER H R, SIMPSON A R, et al. Genetic algorithms for reliability-based optimization of water distribution systems[J]. Journal of water resources plan-ning and management, 2004, 130(1): 63–72.

[11]ZITZLER E, LAUMANNS M, THIELE L. SPEA2: improving the strength Pareto evolutionary algorithm: TIKReport 103[R]. Swiss: Swiss Federal Institute of Technology, 2001.

[12]DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE transactions on evolutionary computation, 2002, 6(2):182–197.

[13]ZHANG Qingfu, LI Hui. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE transactions on evolutionary computation, 2007, 11(6): 712–731.

[14]DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE transactions on evolutionary computation,2014, 18(4): 577–601.

[15]PRASAD T D, PARK N S. Multiobjective genetic algorithms for design of water distribution networks[J].Journal of water resources planning and management,2004, 130(1): 73–82.

[16]JIANG Siwei, CAI Zhihua, ZHANG Jie, et al. Multiobjective optimization by decomposition with Pareto-adaptive weight vectors[C]// International Conference on Natural Computation, Icnc 2011, Shanghai, China, 26–28 July.DBLP, 2011: 1260–1264.

[17]SEDKI A, OUAZAR D. Hybrid particle swarm optimization and differential evolution for optimal design of water distribution systems[J]. Advanced engineering informatics,2012, 26(3): 582–591.

[18]MA Xiaoliang, LIU Fang, QI Yutao, et al. A multiobjective evolutionary algorithm based on decision variable analyses for multiobjective optimization problems with largescale variables[J]. IEEE transactions on evolutionary computation, 2016, 20(2): 275–298.

[19]TANG Lixin, WANG Xianpeng. A hybrid multiobjective evolutionary algorithm for multiobjective optimization problems[J]. IEEE transactions on evolutionary computation, 2013, 17(1): 20–45.

[20]JIANG Shouyong, YANG Shengxing. Evolutionary dynamic multiobjective optimization: benchmarks and algorithm comparisons[J]. IEEE transactions on cybernetics,2017, 47(1): 198–211.