一種用于給水管網多目標優化的改進差分算法

莫涵 馮燕 馬琪然

摘 要：針對標準差分算法無法有效處理給水管網多目標優化問題，提出一種新的算法——改進差分算法。首先，采用Pareto最優原理和非支配排序策略，建立多目標優化機制，保障算法對多個目標的協調與尋優；其次，采用精英策略取代差分算法原有的選擇策略，確保每次尋優均能得到基于全局的最優個體，提高尋優效率。河內管網的優化案例表明，改進的差分算法是一種可行的、適用于給水管網多目標優化的方法。

關鍵詞：差分算法；算法改進；給水管網；多目標優化

DOI：10. 11907/rjdk. 191287

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）005-0089-04

Abstract：To deal with the multiobjective optimization of the water distribution system，which can not be solved by standard difference algorithm，a new algorithm named improved difference algorithm has been proposed. Firstly， the Pareto optimal principle and non-dominated sorting strategy are adopted to establish a multiobjective optimization mechanism to ensure the coordination and optimization of the algorithm for multiple objectives.Secondly， the elite strategy is used to replace the original selection strategy of the difference algorithm to ensure that the optimal individuals based on the overall situation can be obtained for each optimization， so as to improve the efficiency of the optimization.According to the case of Hanoi pipeline network， it is proved that the improved difference algorithm proposed in this paper is a feasible method for multiobjective optimization of water distribution system.

Key Words：differential algorithm；algorithm improved；water distribution system；multiobjective optimization

0 引言

給水管網是城鎮重要的基礎設施，承擔生活和生產用水重任，給水管網優化是否合理直接影響整個供水系統的運行效益和經濟效益。長期以來，給水管網設計本身是一個難以處理的不確定性多項式問題，多數優化研究主要圍繞管網經濟性單一目標展開，對影響管網后期運行性能關注較少，導致現實生活中很多管網在運行期出現爆管[1-4]、漏損、局部供水不足、運行管理費用高等問題[5-6]。我國“十二五”和“十三五”規劃中明確指出“要加大對供水設施的投資力度”、“增強供水管網的建設力度”[7-8]，但是如果繼續延用不夠完善的單目標方法設計新的給水管網，會造成大量資源浪費，這與我國建設資源節約型社會目標相違背。因此，有必要尋找一種既能實現管網經濟性優化，又能實現管網可靠性優化的給水管網多目標優化方法。

標準差分算法（簡稱差分算法）是一種利用群體間個體差異實現啟發式并行搜索的實參優化算法[9]，具有魯棒性強、空間復雜度低、搜索能力強的特點[10-11]，常用于處理復雜、離散、非線性的優化問題。2010年，Suribabu等[12]首次將差分算法引入給水管網的優化問題研究。之后，Vasan等[13]、Zheng等[14]分別采用附加懲罰函數和參數自適應方法，對差分算法進行了改進，改進后的差分算法在處理給水管網最小經濟投入的優化方面表現優異，但仍舊無法處理多個目標的優化設計問題。本文通過深入分析差分算法原理機制，結合給水管網多目標優化特點，提出一種改進差分算法并將其成功應用于河內管網優化設計，得到一系列既考慮管網經濟性又兼顧管網可靠性的最優解決方案。

1 基本原理

1.1 差分算法

差分算法起源于遺傳退火算法，結構與其它進化算法相似，主要由差分變異、交叉和選擇環節組成。

1.1.1 差分變異

1.2 算法缺陷

以某小型環狀管網為例，分別以管網成本最低、管網彈性最高及二者同時最優為優化目標，利用差分算法尋找最適合管網的管徑組合方案。

（1）差分算法可快速完成給水管網的單目標尋優，但得到的優化方案并不完全符合設計要求的基本約束條件。以管網成本最低為例，差分算法找到的管徑組合方案對應的管網成本極低，但將該方案包含的所有管徑取出，發現部分管徑為0，而實際工程中管徑不允許為0。因此，該優化結果不具有實際參考意義。

（2）差分算法在處理多個目標優化時表現出明顯的“惰性”，在以管網成本最低和管網彈性最高為優化目標時，算法只圍繞其中一個目標展開，對另一個目標直接忽略，得到的優化結果實質上還是單目標最優，而非多目標最優。

對差分算法的運行機理進行深度剖析，發現造成上述問題的原因是差分算法缺乏判斷既矛盾又競爭的多個目標優劣機制。基于此，本文對差分算法進行改進。

2 改進差分算法

2.1 Pareto最優思想

給水管網優化中，多個優化目標間的矛盾性和競爭性造成很難找到一個滿足所有目標的最優解，只能通過對各目標進行權衡和折中的方式獲得盡量接近全局最優解，Pareto表現的正是這種優秀的權衡思想。

目標函數空間（[Λ]）中的任意向量[u]和[v]，[u={u1，][u2，？，un}]，[v={v1，v2，？，vn}]，對于[？i∈{1，2，？，k}]滿足[uivi]，并且[？j∈{1，2，？，k}]使得[ujvj]，則稱[u]優于（支配）向量[v]（記作[u？v]）。

在可行性區域[Xf]中，對于[？x]不存在[a∈Xf]，使得[F（a）=（f1（a），f2（a），？，fk（a））]優于（支配）[F（x）=（f1（x），f2（x），][？，fk（x））]，即稱x是[Xf]中的Pareto 最優解[18]。

2.2 非支配排序

得到Pareto最優解的關鍵在于判別比較對象的支配性（或非支配性）。本文采用非支配排序對種群中的所有個體對應的函數值（即適應度）進行非支配性計算，并根據計算結果進行排序，確定每個個體對應的等級情況，由此完成多個目標的判斷與優選。本文采用的非支配排序過程如下：

（1）對主種群[P]中的每一個體[p]均設置兩個參數[Sp]和[np]，其中[Sp]表示一個集合，包含了所有被[p]支配的個體；[np]是一個數，表示主種群[P]中支配個體[p]的個體數。

（2）對于個體[p]，初始化[Sp]和[np]，即[Sp=φ]，[np=0]。

（3）判斷支配與否。將個體[p]與種群[P]中的每個個體進行比較。如果[p]支配[q]，則將[q]加到集合[Sp]里面，即[Sp=Sp？{q}]；否則，[q]支配[p]的話，則[np]值加1，即[np=np+1]。

（4）對種群[P]中的每個個體均進行支配比較，最終每個個體均對應自己的[Sp]和[np]。在所有個體中，找出[np=][0]，意味著個體[p]不被種群[P]中任何個體支配，是非支配個體。將其放到第一前沿集合（First Front，簡寫為[F1]），即[F1=F1？p]；再令個體[p]的解集等級為1，即[prank=1]。

（5）將[Fi]中的每個非支配個體[p]、對應[Sp]集合里的個體[q]進行支配個體數減1操作，即令[nq=nq-1]。

（6）若步驟（5）之后得到[nq=0]，說明之后的層級中無可支配個體[q]，則將個體[q]放入第2個前沿集合（[F2]），并令[qrank=prank+1]，使[F2=F2？p]。

（7）對[F2]重復步驟（4）-步驟（6）的分級操作，直到所有個體均被分級。

2.3 精英策略

差分算法在選擇環節采用貪婪策略，核心是將兩代種群中相同位置的個體進行比較，性能更佳者保留至下一代種群的相同位置。但是，這種比較方法只做到了相同位置個體的優劣判斷，忽略了不同位置個體間的優劣判斷，對于整個問題的尋優無疑是不利的。因此，本文采取將兩代種群混合重新計算個體等級后再排序的方式，選擇并保留兩代種群中最優的個體作為后代種群，實現全面的精英策略，如圖1所示。

本文采用Pareto最優原理和非支配排序策略建立多目標優化機制，以及基于全局精英策略對差分算法進行改進，改進的差分算法結構見圖2。本文提出的改進差分算法可直接處理多個矛盾目標的優化問題，無需事先處理決策變量，算法計算速度快、尋優能力強。

3 算法應用

將改進差分算法應用于河內管網[19]（Hanoi Network， HAN）的多目標優化設計。

3.1 案例介紹

HAN管網是越南河內市給水系統的一個簡化管網，平面布置情況如圖2所示。管網采取重力供水，水源處固定水頭為100m。管網中有32個節點、34根管道和3個回路，管段長度為100-3500m，各節點需水量在60-1345m3/h之間，管網布置情況如圖3所示。

3.2 模型優化

3.2.1 目標函數

本文模型采用“管網成本”衡量管網經濟性，以“管網彈性”[20]衡量管網可靠性。

3.2.3 算法優化

從HAN管網基本信息可知，該管網的優化解空間共包含[634]個不同的管徑組合方案。改進算法中，決策變量為34，縮放因子取0.8，交叉因子取0.5。初始種群規模設為200，迭代次數取600。利用MATLAB平臺進行編程，調用EPANET軟件作為管網水力模擬器，實現對HAN管網的多目標優化，優化結果如圖4所示。

圖4中，每一個圓圈代表一個HAN管網的Pareto最優解，每個Pareto最優解代表一種權衡了“管網成本最低-管網彈性最高”的管徑組合方案。將優化結果劃分為AB、BC和CD三段，并將分段點對應的函數信息取出，見表1。

結合HAN管網Pareto最優解分布情況和表1可知，AB區段中，隨著管網彈性增大，管網成本緩慢增大；CD區段中，隨著管網彈性增大，管網成本迅速升高；BC區段的變化趨勢介于AB區段和CD區段之間，管網彈性增量和管網成本增量均處中間值。

投資效益最大化是工程項目追求的重要目標，即用相對少的投資獲得較為理想的效益。因此，基于本研究成果對HAN管網的工程設計提出以下建議：

（1）當管網成本<8.699時，推薦采用AB區段中的Pareto最優解所對應的管網組合方案。若投資緊張，可盡量取靠近A端的最優解；若管網彈性要求相對較高，則盡量取靠近B端的最優解。

（2）當8.699<管網成本<9.572時，推薦采用BC區段中的Pareto最優解所對應的管網組合方案，可選擇方案多。

（3）管網成本應盡量控制在9.572以下，以避免經濟浪費。

4 結語

本文對差分算法原理進行了深入研究和剖析，指出差分算法無法處理多目標優化問題的根本原因在于缺乏同時判斷多個矛盾目標優劣性的尋優機制。通過引入Pareto最優原理和非支配排序策略，建立多目標尋優機制，并采用精英策略對差分算法進行改進，提出了改進的差分算法。本文提出的改進算法與原算法相比，可在滿足管網設計眾多約束條件的同時找到最符合多個目標的最優管徑組合方案，對管網的工程設計具有現實意義。

參考文獻：

[1] 陳盛達，李樹平，姜曉東. 2015年國內網絡媒體報道給水爆管分析[J]. 四川環境，2016，35（4）：22-28.

[2] 周艷春，李樹平，沈繼龍，等. 2014年國內媒體報道給水爆管分析[J]. 公共安全，2015，39（2）：6-10.

[3] 趙子威，李樹平，周艷春，等. 2013年國內網絡媒體報道給水管網爆管事件分析[J]. 凈水技術，2014，33（1）：11-16，24.

[4] 鄒俊，李樹平，趙子威. 2012年國內媒體報道給水爆管分析[J]. 公共安全，2013，33（4）：9-13.

[5] 中國城鎮供水排水協會. 城市供水統計年鑒2016年[Z]. 中國城鎮供水排水協會，2016.

[6] 魏靜. 基于改進NSGA2算法的給水管網多目標優化設計[D]. 北京：北京工業大學，2016.

[7] 住房和城鄉建設部. 全國城鎮供水設施改造與建設“十二五”規劃及 2020 年遠景目標[Z]. 2012.

[8] 中共中央關于制定國民經濟和社會發展第十三個五年規劃的建議[EB/OL]. http：//www.moa.gov.cn/zwllm/zcfg/flfg/201511/t20151103_4888538.htm.

[9] STORN，KENNETH PRICE. Differential evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces by rainer[D]. California：International Computer Science Institute，1995.

[10] 楊衛東，姚峰，張明. 基于自適應交叉概率因子的差分進化算法及其應用[J]. 信息與控制，2010，39（2）：187-193.

[11] 賈東立，鄭國莘. 基于混沌和高斯局部優化的混合差分進化算法[J]. 控制與決策，2010，25（6）：899-902.

[12] SURIBABU C R. Differential evolution algorithm for optimal design of water distribution networks[J]. Journal of Hydroinformatics，2010，12（1）：66-82.

[13] VASAN A，SLOBODAN P，SIMONOVIC. Optimization of water distribution network design using differential evolution[J]. Journal of water resources planning and management，2010（2）：279-287.

[14] ZHENG F F，AARON C， ZECCHIN，et al. Self-adaptive differential evolution algorithm applied to water distribution system optimization[J]. Journal of computing in civil engineering，2013（27）：148-158.

[15] BREST J，BOSKOVIC B，GREINER S，et al. Performance comparison of self-adaptive and adaptive differential evolution algorithms[J]. Soft Computing，2007，11（7）：617-629.

[16] DAS S，ABRAHAM A，CHAKRABORTY U K，et al. Differential evolution using a neighborhood based mutation operator[J]. IEEE Transactions on Evolutionary Computation，2009，13（3）：526-553.

[17] 王叢佼，王錫淮，肖建梅. 具有參數自適應機制的改進離散差分進化算法[J]. 計算機科學，2014（1）： 279-282.

[18] 王凌，何鍥，金以慧. 智能約束處理技術綜述[J]. 化工自動化及儀表，2008（1）：1-7.

[19] FUJIWARA O，KHANG D B. A two-phase decomposition method for optimal design of looped water distribution networks[J]. Water Resour， Res，1987，23（6）：977-982.

[20] PRASAD T D. Multiobjective genetic algorithms for design of water distribution networks[J]. Water Resour Plann Manage，2004，130（73）：73-82.

（責任編輯：杜能鋼）