一種用于給水管網(wǎng)多目標(biāo)優(yōu)化的改進(jìn)差分算法

莫涵 馮燕 馬琪然

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

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

DOI：10. 11907/rjdk. 191287

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

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

1 基本原理

1.1 差分算法

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

1.1.1 差分變異

1.2 算法缺陷

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

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

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

對差分算法的運(yùn)行機(jī)理進(jìn)行深度剖析，發(fā)現(xiàn)造成上述問題的原因是差分算法缺乏判斷既矛盾又競爭的多個(gè)目標(biāo)優(yōu)劣機(jī)制?；诖?，本文對差分算法進(jìn)行改進(jìn)。

2 改進(jìn)差分算法

2.1 Pareto最優(yōu)思想

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

目標(biāo)函數(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)解的關(guān)鍵在于判別比較對象的支配性（或非支配性）。本文采用非支配排序?qū)ΨN群中的所有個(gè)體對應(yīng)的函數(shù)值（即適應(yīng)度）進(jìn)行非支配性計(jì)算，并根據(jù)計(jì)算結(jié)果進(jìn)行排序，確定每個(gè)個(gè)體對應(yīng)的等級情況，由此完成多個(gè)目標(biāo)的判斷與優(yōu)選。本文采用的非支配排序過程如下：

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

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

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

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

（5）將[Fi]中的每個(gè)非支配個(gè)體[p]、對應(yīng)[Sp]集合里的個(gè)體[q]進(jìn)行支配個(gè)體數(shù)減1操作，即令[nq=nq-1]。

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

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

2.3 精英策略

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

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

3 算法應(yīng)用

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

3.1 案例介紹

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

3.2 模型優(yōu)化

3.2.1 目標(biāo)函數(shù)

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

3.2.3 算法優(yōu)化

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

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

結(jié)合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)成本增量均處中間值。

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[11] 賈東立，鄭國莘. 基于混沌和高斯局部優(yōu)化的混合差分進(jìn)化算法[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ù)自適應(yīng)機(jī)制的改進(jìn)離散差分進(jìn)化算法[J]. 計(jì)算機(jī)科學(xué)，2014（1）： 279-282.

[18] 王凌，何鍥，金以慧. 智能約束處理技術(shù)綜述[J]. 化工自動(dòng)化及儀表，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.

（責(zé)任編輯：杜能鋼）