基于自適應MOEA/D 的供水管網多目標優化

董 娜

（內蒙古電子信息職業技術學院電子與自動化學院，內蒙古 呼和浩特 010070）

0 引 言

城市供水系統是整座城市的生命線，完善的供水管網能夠保障人民群眾日常生活的正常運轉。在城市供水系統中，管網優化設計一直是研究熱點問題之一［1］。在管網設計時，要求在滿足供水需求量和水壓等約束條件下，期望能盡量減少節點富余水頭總和，以降低管網設計的故障率，增強其可靠性。同時，又期望盡可能降低管網建造總成本，以提高管網建造的經濟性。顯然，總造價和故障率是一對具有沖突特性的目標函數。隨著總造價的提高，故障率呈下降趨勢；反之，隨著總造價的降低，故障率呈上升趨勢。因此，供水管網設計顯然是一個多目標優化問題［2］。傳統的單目標優化方法需要利用權重系數將多目標優化問題轉化為單目標優化問題。但是權重系數極難確定，而且對算法結果影響巨大。由于多目標進化算法一次運行能夠獲取多個Pareto最優解，適合于解決管網多目標優化問題。研究者將其應用在城市管網優化設計當中，為市政工程的施工建設提供有益參考［3，4］。

基于分解的多目標進化算法（MOEA/D）采用分解方法將一個多目標優化問題轉化為一組單目標優化子問題，并以協作的方式處理它們。MOEA/D公認為是多目標進化領域的主流算法之一［5］。MOEA/D 在實際工程領域具有廣泛的應用，如無人機航跡規劃［6］、能源計劃優化［7］、網絡接入控制［8］、樓宇負荷優化［9］、天線優化［10］、飛行器氣動外形優化［11］等。MOEA/D在解決一些復雜多目標優化問題時，其難以發現目標空間中Pareto 前沿上的邊界解，而與這些邊界解對應的決策空間中的輸入矢量有可能是期望的Pareto最優解［12］。

為了取得收斂性和多樣性的最佳平衡，研究者提出多種改進方法。例如：LI 等人將差分進化算子（DE）引入到MOEA/D中，形成MOEA/D-DE 算法［13］。ZHANG 等人設計一種基于精英群體的自適應權重向量調整策略，并集成到MOEA/D 中形成MOEA/D-AWA 算法。MOEA/D-AWA 通過引入精英群體，以在目標空間稀疏區域添加新的子問題，從而能夠有效解決復雜MOP問題［14］。LI等人設計一種自適應交配選擇策略，提出一種簡單有效的穩定匹配模型來協調選擇過程［15］。此外，如自適應交配選擇機制、鄰域大小集合、可變鄰域策略等均已成功集成到MOEA/D中來解決實際工程問題。

然而，實際工程中大多數多目標優化問題具有復雜的Pareto 最優前沿，比如長尾巴、尖峰或不連續。以供水管網優化問題來說，總造價和故障率不一定呈現出標準的Pareto 前沿。我們總是期望，當總造價緩慢增加時，故障率將會緩慢降低；當總造價緩慢降低時，故障率將會緩慢增加。然而，現實情況卻是，在某個臨界點后，總造價的些許降低可能導致故障率的極大增加，總造價的極大增加也可能無法使故障率有些許降低。這就出現了所謂的長尾巴、尖峰等復雜Pareto 前沿的情況。針對這些復雜優化問題，其中一個目標的細微變換會導致另一個目標較大的變換，從而導致Pareto 最優解集中在Pareto 前沿的中部區域，邊界區域很難獲取到Pareto 最優解。顯然，傳統MOEA/D難以有效完成這類問題的尋優。

主要針對供水管網多目標優化呈現的Pareto解集前沿面存在尖峰、長尾和不連續等問題，提出一種帶有兩階段策略和小生境引導策略的MOEA/D 算法（MOEA/D-TPN），旨在解決Pareto 解的多樣性和分布性的不平衡問題。然后利用MOEA/DTPN 算法求解城市供水管網多目標優化問題，獲取雙環管網的最優解集，為城市供水管網的工程設計提供可行參考方案。

1 城市供水管網多目標優化問題

管網形式主要分環狀和樹狀，樹狀主要用于邊緣地區，其他地區一般布置環狀管網以保證用水安全。Alperovits 與Shamir 提出的雙環管網是公認的管網優化模型，如圖1 所示。它包含了1個水源、7個節點和8個段長1 000 m 的管段，海曾威廉系數設定為130［16］。表1 給出了各節點的節點高程、最低自由水頭和需水量等參數。

圖1 雙環管網結構圖Fig.1 Structure diagram of double ring pipe network

根據雙環管網和單元管段的結構，可得到如下的供水管網經濟性目標函數，即管網的總造價［16］：

式中：P為管網每年大修與折舊的費用在整個管網造價中的比例；E=［j（1+j）n］/［（1+j）n-1］為基建投資效果系數；j為銀行利率；n為資金回收期；np為管網的管段數；Di、li分別為第i段管道的直徑和長度；a+bDiλ為管網建造費用，a、b和λ分別為管道造價公式的系數及指數；H0為水泵靜揚程；hi為管段i的水頭損失；Qp為進入管網的總流量，K=（24×356×10 000γσ）/（102η）=8 600γ σ/η；σ為泵站電價；γ為管網使用年限內管網供水不均勻所占比；η為泵站效率。

由于節點富余水頭越大，管網中水壓越高，事故發生的概率就越大，因此可靠性目標函數定義為節點富余水頭總和，即管網的故障率［16］：

式中：Hi為節點i處的自由水頭：Himin為節點i處要求的最小水壓；I為管網節點總數；Hi-Himin為節點i的富余水頭。

2 MOEA/D原理

MOEA/D利用分解方法將多目標優化問題轉換為一系列單目標優化子問題，并構造問題導向的鄰域關系，然后以協同方式同時處理所有子問題，最終得到完整的Pareto 前沿［5］。常用的分解方法有權重聚合法、切比雪夫法和基于懲罰的邊界交叉法［5］。由于權重聚合法不能很好地處理真實Pareto 前沿為凹狀的問題，基于懲罰的邊界交叉法的性能受懲罰因子的影響較大，因此以切比雪夫法為例進行研究。在該方法中，第i個子問題定義為如下形式：

其中，z*=min｛fi（x）|x∈Ω｝，i=1，2，…，m，λ=（λ1，λ2，…，λm）T為權重向量，滿足λi＞=0，且有

3 MOEA/D-TPN算法

考慮到公式（3）是z*作為參考點，當其處理復雜凸優化問題時，算法尋找到的Pareto 最優解會向Pareto 前沿中部區域聚集。對于該問題，如果采用znad作為參考點，算法將能夠尋找到邊界區域的Pareto解。上述思想如圖2所示。

圖2 Pareto解集分布情況Fig.2 The distribution of Pareto solution set.

基于此，提出一種自適應MOEA/D 算法，其將進化過程分成兩個階段。在第一階段利用z*作為參考點，在第二階段利用znad作為參考點。同時為了增加算法的多樣性，設計了一套小生境引導策略，以選擇不同的交配個體。

3.1 兩階段策略

第一階段采用公式（3）將多目標優化問題分解成子問題進行協同優化。第二階段采用公式（4）將凸多目標優化問題分解成子問題進行協調優化。

其中，znad=max｛fi（x）|x∈Ω｝，i=1，2，…，m。

然而，在處理多目標優化問題時，一般無法事先知道問題的凸凹性。因此何時選取公式（3）和公式（4）對問題進行求解存在困難。本文所提兩階段策略，在最大迭代步數的Mr%，使用公式（3）處理多目標優化問題。在第一階段結束時，使用基于擁擠的方法來評估MOEA/D 是否得到了一組均勻解［12］。該方法能夠估算出Pareto 前沿中間區域和極端區域的解的密度。如果中間區域的解比極端區域的解更密集，則說明多目標優化問題可能是凸的。基于此，在第二階段，采用公式（4）處理多目標優化問題。

下面闡述基于擁擠的評估方法的原理［12］。由于在MOEA/D 權重向量λ滿足λ1+λ2+ … +λm= 1，根據幾何平均不等式定理，始終成立，因此λ位于超平面λ1+λ2+ … +λm= 1 的中心。換句話說，越大，權重向量就越接近中心權重向量。因此，將MOEA/D 的n個權重向量集分為兩個子集，即中間子集Wm和極端子集We：

其中，Ωλ是MOEA/D 運用單純形格子法生成的n個權重向量集。公式（5）中設置系數為0.5，能夠取得Wm和We的最佳分類。

然后，根據權重向量子集Wm和We，將種群分為兩個子種群，分別稱為中間區域子種群Pm和極端區域子種群Pe。兩個子種群的擁擠程度采用公式（7）和（8）進行估計：

式中：Dmid和Dext分別是中間子種群和極端子種群的擁擠度值；γ(i)表示子種群中第i個解的擁擠度，定義如下：

式中：d（i，j）為解i與j之間的距離；B（i）和T分別為解i鄰域內的個體和鄰域大小。

3.2 小生境引導策略

傳統MOEA/D 在鄰域交配和更新時會產生許多類似的解。盡管在MOEA/D-DE 中使用DE 算子取代了模擬二進制交叉算子，以克服該問題。但是當Pareto前沿具有不連續區域時，這種缺陷會導致種群多樣性急劇降低。

參考文獻［12］提出一種具有自適應選擇能力的小生境引導策略。在該策略中，首先計算出每個個體在其相鄰個體上的生態位計數。每個個體i的生態位計數是通過對相鄰個體求和獲得的一個共享函數，用nc（i）來表示：

式中：dij是個體i和j之間的距離；sh（dij）是測量個體i和j之間相似程度的共享函數，定義為：

式中：σshare是一個預先定義的生態位半徑；α是一個常數，稱為共享水平。

如果個體的生態位計數超過了給定的閾值，這意味著個體與它的鄰接個體相似，所以最好選擇鄰域之外的個體作為交配的父代種群。因此，自適應更新定義如下：

其中，β是與生態位半徑σshare密切相關的閾值，即β主要由σshare決定。由于nc（i）的最大值為T，將β設為T/2。P和P′產生方法如下：

其中，當rand1和rand2在范圍［0，1］內獨立生成隨機數時，P與MOEA/D-DE 中的P保持相同。P′的定義意味著如果個體i的生態位計數達到閾值β，它有50%的機會選擇其周圍的個體作為交配父代種群。

3.3 MOEA/D-TPN算法框架

其中，是的第k個分量，xrk1、xrk2和xrk3是從種群中隨機選擇的3 個不同個體。CR和F是兩個控制參數。采用多項式突變策略從產生一個解y=（y1，…，yn）：

其中，rand是［0，1］區間隨機數，η和Pm分別是分布指數和突變率，bk和ak分別是決策變量的上下界。

4 實驗分析

4.1 參數設置

MOEA/D-TPN 的參數設置如下：種群規模N=100，鄰域規模T=20，nr=2，最大迭代次數maxIteration=100；從鄰域內選取解的概率δ=0.9；差分進化的雜交率CR=0.5，尺度因子F=0.5；多項式變異的變異率pm=1/n，分布性指數η=20。

4.2 基準測試

為了評價MOEA/D-TPN 的有效性，采用6 個具有長尾巴、尖峰等復雜POF 的MOP （F1-F6）作為測試案例［12］，決策變量個數均設置為20，取值范圍在［0，1］n，具體信息見表2。

表2 具有復雜POF的MOPTab.2 MOP with complex POF

4.4 實驗結果

圖3 給出了MOEA/D-TPN 的逼近結果，并與MOEA/D-DE和MOEA/D-STM 進行了對比分析。可以看出，對于F1 測試問題，MOEA/D-DE 和MOEA/D-STM 獲取的解會收斂到POF 的中間區域，難以發現邊界解，MOEA/D-TPN 容易找到邊界解。對于F2 測試問題，MOEA/D-DE、MOEA/D-STM 和MOEA/D-TPN三個算法獲取到解的精度基本相同，但是MOEA/D-TPN 的收斂速度最快。F3、F4 和F5 三個測試函數極其復雜，具有長尾和尖峰區域，MOEA/D-DE 僅在POF 中部區域上找到一部分解，MOEA/D-TPN 在邊界區域也能尋找到一部分解。對于更復雜的三目標優化問題F6，MOEA/D-TPN 也表現出了更優越的尋優性能。

圖3 3種算法的逼近結果Fig.3 Approximation results of three algorithms

圖4給出了3種對比算法30次獨立運行取得最小IGD 值時的演化曲線。可以看出，對于F1-F6 測試函數，與MOEA/D-DE和MOEA/D-STM 相比，MOEA/D-TPN 的進化曲線均表現出較快的收斂速度和較好的逼近精度。

圖4 3種算法的IGD進化曲線Fig.4 IGD evolution curve of three algorithms

圖5 給出了3 種對比算法30 次獨立運行繪制的IGD 盒形圖。可以看出，對于F1、F3、F4 和F5 四個測試函數，MOEA/DTPN的IGD總體處于較低范圍，分布性好，尋優性能突出。對于F2 和F6，MOEA/D-TPN 與MOEA/D-DE、MOEA/D-STM 的性能相當，略占優勢。

圖5 3種算法的IGD盒形圖Fig.5 IGD box diagram of three algorithms

4.4 供水管網優化

下面利用所設計的MOEA/D-TPN 算法對雙環管網的造價（經濟性）和節點富余水頭總和（可靠性）兩個目標進行優化。MOEA/D-TPN 的參數設置同上。圖6 給出了MOEA/D-TPN 算法獲取到的Pareto 前沿。每一個Pareto 解對應的決策空間變量是［x1，x2，x3，x4，x5，x6，x7，x8］，分別表示雙環管網的8個管徑。

圖6 管網的Pareto前沿Fig.6 Pareto front of pipe network

本文設計一種基于模糊隸屬函數的智能決策方法，利用該方法能夠在Pareto 前沿上決策出一個折衷解，從而獲得8 個管徑的一個最佳組合。首先利用模糊隸屬函數定義第i個目標函數fi的Pareto解xk的滿意度，如下：

其中，fmaxi和fmini分別代表第i個目標函數fi的最大值和最小值。然后， 可以計算出xk的規范化隸屬度函數μk，如下：

其中，m為目標函數個數，|S|是算法獲得的Pareto 解集的元素個數。本文選取μk為最小值時的解，即可圖6中的折衷解。

從圖6中可以看出，MOEA/D-TPN能夠獲取更多的邊界解。此時，從邊界中進行取值能夠取得經濟性和可靠性的最佳平衡。

從圖6 的Pareto 前沿中選取25 個解，列出決策變量和目標函數的取值，如表3所示。可以看出，管網造價和節點富余水頭總和之間存在沖突特性。隨著管網造價的逐步升高，節點富余水頭總和越來越低，表明總造價增大的同時，故障率逐步降低，可靠性逐步增大；反之總造價減少的話，故障率逐步抬高，可靠性逐步降低。這在管網施工時就會產生沖突，施工方一方面期望能盡量降低總造價，另一方面也期望故障率盡可能地低，可靠性盡可能地高。利用MOEA/D-TPN 決策出的最優解將能夠在保證足夠可靠性的前提下盡量降低成本，為城市供水管網優化設計提供有益參考。

表3 算法獲取的Pareto解Tab.3 Pareto solutions obtained by algorithm

5 結 語

本文提出一種自適應MOEA/D 算法，命名為MOEA/DTPN，利用其解決城市供水管網多目標優化設計問題。為了平衡MOEA/D 解的多樣性和分布性，設計了兩階段策略和小生境引導策略。利用6 個具有復雜Pareto 前沿的測試函數進行了算法性能驗證，并與MOEA/D-DE、MOEA/D-STM 等多個先進算法進行了比較，在4 個測試函數中MOEA/D-TPN 的尋優結果最好，在其余兩個測試函數中性能表現相當。根據我國供水系統的運行情況，利用城市供水雙環官網模型進行了仿真測試，確定了總造價和故障率兩個沖突的目標函數，運用MOEA/D-TPN算法對管網進行多目標優化設計，求解出雙環管網的最優解集。下一步工作是利用本文設計的MOEA/D-TPN 解決大型復雜管網的多目標優化問題。