尋夢新聞LINE@每日推播熱門推薦文章，趣聞不漏接❤️
題目：Comparative study of multi-objective evolutionary algorithms for hydraulic rehabilitation of urban drainage networks
作者：J. Yazdi, D. G. Yoo & J. H. Kim
第一作者單位：Faculty of Civil, Water and Environmental Engineering, Shahid Beheshti University, Tehran, Iran
期刊：Urban Water Journal
時間：2017
關鍵詞：MOEA; SPEA2; NSGA2; HS; DE; urban drainage system
多目標進化算法是現代智能優化算法的一種，其特徵是一組解（種群）共同改進，而不只是用一個點在解空間中進行搜尋。由於可以解決非線性多目標優化問題，各類進化算法在工程研究中得到了廣泛運用，但是在水系統領域中還未出現能夠妥善解決各類問題的通用算法。實際上，算法對特定問題的可靠性取決於問題的數學關係和算法搜尋行為的契合度。
本文比較了4種多目標進化算法在計算雨水管網修繕問題上的表現。考察的4個算法是NSGA2 – 第2代非支配排序遺傳算法、NSHS – 非支配排序和聲搜尋、NSDE – 非支配排序差分進化、SPEA2 – 第2代強度帕累托進化算法，它們的區別只是從一代至下一代的種群演變規則不同。
NSHS：模擬演奏音樂的過程，每個決策變量都被視作樂隊的一個成員，通過反復調整樂隊中各樂器的音調，最終達到和諧的和聲狀態。
NSDE：算法的最大特點在於其突變過程是基於父代個體間的差分向量。
SPEA2：存儲非支配解，利用帕累托支配的概念來分配適應度，並用聚類來減少非支配解的數目。
「管網修繕」問題指的是保持系統拓撲結構不變，將若干管段的管徑進行替換，自變量是各管段將被替換成何種管徑（或不替換）。修繕的主要目標是應對降雨洪峰流量，減少內澇的發生，因而文章確定了兩個優化目標：經濟成本最小和典型降雨下的內澇總量最小，前者等於所有替換管段的建設成本，後者是將新的管網系統放入SWMM軟件模擬而得。
以四個規模不同的管網（含32~175根管不等）為計算實例，對各算法固定評估目標函數的總次數（由於評估目標函數是最耗時的步驟，因而相當於固定計算時間），比較所得的前沿面。
種群規模是進化算法中的重要參數，取值過小有可能降低種群多樣性、陷入局部最優，過大則將每一代的計算時間。對每種算法都設置種群規模為100、200和400，研究發現，NSHS的前沿面幾乎不隨種群大小而變（圖1），這是其他算法做不到的。
圖1各算法在種群規模不同時的前沿面
由於算法帶有隨機參數，對同一個算例多次運算的結果可能不同。NSHS的前沿面在這方面的穩定性也是最強的，其次是NSDE（圖2）。
圖2各算法多次計算所得的前沿面
比較前沿面的目標函數值，在問題規模較小時（圖3a）各算法所得結果一致；當問題規模稍增大時（圖3b）NSGA2、NSHS、NSDE的結果一致，而SPEA2的前沿面明顯差於前三者；當問題規模增大至接近實際規模（100根管以上）時，各算法的表現有明顯不同，其中NSHS表現最好。同時還發現，NSDE更能找到「極端」的非支配解（即一個目標值很大而另一個目標值很小），對本文實例而言，NSDE的解中有約20%是不被NSHS的前沿面所支配的。
圖3各算法前沿面目標函數值的比較
智能優化算法的本質是在局部增強和全局擴展之間的平衡，前者確保達到最優解的概率較大，後者確保陷入局部最優的概率較小。算法的效果和目標函數在解空間上的形狀密切相關，對特定的問題，特定的算法表現會比較好。因此針對大規模、非線性的優化問題有必要首先根據問題的特點確定合適的算法，同時可根據不同算法的特點進行整合以平衡優化效率和前沿面的質量。
挑選合適的算法也並非增進效率的唯一途徑。「對問題本身進行研究」也是增進效率的重要手段。比如說，如果不對問題進行合適的編碼，或者不仔細設計進化規則（即搜尋規則），很可能生成大量的不可行解，從而浪費時間。這一點應當引起注意。
https://www.tandfonline.com/doi/abs/10.1080/1573062X.2016.1223319
