莫涵 馮燕 馬琪然

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

關鍵詞：差分算法；算法改進；給水管網(wǎng)；多目標優(yōu)化

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 引言

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

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

1 基本原理

1.1 差分算法

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

1.1.1 差分變異

1.2 算法缺陷

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

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

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

對差分算法的運行機理進行深度剖析，發(fā)現(xiàn)造成上述問題的原因是差分算法缺乏判斷既矛盾又競爭的多個目標優(yōu)劣機制?；诖耍疚膶Σ罘炙惴ㄟM行改進。

2 改進差分算法

2.1 Pareto最優(yōu)思想

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

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

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

2.2 非支配排序

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

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

（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]進行支配個體數(shù)減1操作，即令[nq=nq-1]。

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

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

2.3 精英策略

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

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

3 算法應用

將改進差分算法應用于河內(nèi)管網(wǎng)[19]（Hanoi Network， HAN）的多目標優(yōu)化設計。

3.1 案例介紹

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

3.2 模型優(yōu)化

3.2.1 目標函數(shù)

本文模型采用“管網(wǎng)成本”衡量管網(wǎng)經(jīng)濟性，以“管網(wǎng)彈性”[20]衡量管網(wǎng)可靠性。

3.2.3 算法優(yōu)化

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

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

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

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

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

（2）當8.699<管網(wǎng)成本<9.572時，推薦采用BC區(qū)段中的Pareto最優(yōu)解所對應的管網(wǎng)組合方案，可選擇方案多。

（3）管網(wǎng)成本應盡量控制在9.572以下，以避免經(jīng)濟浪費。

4 結語

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

參考文獻：

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

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

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

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

[5] 中國城鎮(zhèn)供水排水協(xié)會. 城市供水統(tǒng)計年鑒2016年[Z]. 中國城鎮(zhèn)供水排水協(xié)會，2016.

[6] 魏靜. 基于改進NSGA2算法的給水管網(wǎng)多目標優(yōu)化設計[D]. 北京：北京工業(yè)大學，2016.

[7] 住房和城鄉(xiāng)建設部. 全國城鎮(zhèn)供水設施改造與建設“十二五”規(guī)劃及 2020 年遠景目標[Z]. 2012.

[8] 中共中央關于制定國民經(jīng)濟和社會發(fā)展第十三個五年規(guī)劃的建議[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] 楊衛(wèi)東，姚峰，張明. 基于自適應交叉概率因子的差分進化算法及其應用[J]. 信息與控制，2010，39（2）：187-193.

[11] 賈東立，鄭國莘. 基于混沌和高斯局部優(yōu)化的混合差分進化算法[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] 王叢佼，王錫淮，肖建梅. 具有參數(shù)自適應機制的改進離散差分進化算法[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.

（責任編輯：杜能鋼）