1 引言
地下水污染修復實際上是一個既考慮治理效果又考慮治理成本的復雜的多目標優化問題.當前,求解多目標問題最有效的方法是多目標智能優化算法,一方面,該算法可以并行地處理一組可能的解(群體),能在一次算法過程中找到Pareto最優集中的多個解;另一方面進化算法不局限于Pareto前端的形狀和連續性,易于處理不連續的、凹形的多目標函數,能夠有效地克服古典方法的局限性.如基于小生境的Pareto遺傳算法(niched Pareto genetic algorithm,NPGA),快速非支配遺傳算法(nondominated sorting genetic algorithm Ⅱ,NSGA Ⅱ)等.以上提出的多目標遺傳算法具有良好的全局搜索能力,然而在搜索的中后期,算法收斂于真實最優解的效率大幅降低,而且遺傳算法是以種群為單位的群體搜索方法,對于復雜的非線性規劃問題不能保證收斂到最優解.鑒于以上不足,國內外研究者提出了多種對傳統多目標智能優化算法的改進算法.本文對遺傳算法初期搜索到的優化解進行局部搜索,形成了一種新的混合多目標優化模式.該混合算法即是利用遺傳算法的全局搜索能力搜尋最優解,然后將進化的解作為初始解進行局部搜索以搜尋到真實的Pareto最優解.
本文將NSGAII與一種迭代式的局部搜索算法(Hill Climber with Step,HCS)相結合,開發了一種新的混合多目標遺傳算法NSGAII-HCS.利用CONV1和ZDT6兩個經典的多目標優化函數對NSGAII-HCS的性能進行測試.最后,將NSGAII-HCS與地下水流模擬軟件MODFLOW和溶質運移模擬軟件MT3DMS相耦合,并應用到一個理想的二維地下水污染修復管理模型中,結果分析表明該方法可為地下水污染治理提供多樣的和收斂的Pareto管理策略,是一種穩定可靠的多目標優化方法.
2 混合多目標遺傳算法
2.1 快速非支配遺傳算法
NSGAII是一種可以快速進行Pareto排序的非支配多目標遺傳算法,如圖 1所示.該算法的優點主要包括以下3個方面：① 提出快速非支配排序法,降低算法的復雜度;② 提出擁擠度與擁擠度比較算子,代替了需要指定共享半徑的適應度共享策略,并在同一級排序中將擁擠度作為個體的勝出標準,保持了種群的多樣性;③ 引入精英策略,有利于保存種群進化過程中的優良個體,加速了種群的收斂.以上優點使NSGAII成為一種廣泛應用的多目標智能優化算法,并作為與其它改進算法的比較基準.
圖 1 NSGAII-HCS的計算流程圖
2.2 局部搜索算法
HCS是一種基于最優搜尋方向的迭代式局部搜索方法.由于地下水污染修復管理模型是復雜的非線性規劃問題,不能準確計算目標函數的梯度信息,因此本文采用無梯度計算的局部搜尋方法.
為了詳細闡述HCS的具體搜索過程,可以將HCS作為一種對遺傳算法進化的Pareto解進行局部搜索,然后輸出局部最優解的獨立的算法,而HCS與NSGAII的耦合過程如圖 1所示.HCS的計算流程圖如圖 2所示.為了決定局部搜尋的方向,需要利用初始解的給定鄰域半徑內的鄰域解.鄰域解的定義即：
(1)
式中,X0=(x01,x02,…,x0m);Xn=(xn1,xn2,…,xnm).X0是初始解決策變量的向量形式;Xn 是鄰域解決策變量的向量形式;m是決策變量的個數;x0i是初始解第i個決策變量;H是在尋優過程中選取鄰域解的參考解集,以進化過程中父代與子代解集作為參考解集并從中選取符合要求的鄰域解,這樣可以減少因產生鄰域解而需要的目標函數評價,增加算法的效率;r是鄰域半徑.若鄰域解Pareto主導初始解并以Xn
(2)
式中,fi(X)表示第i個目標函數,k表示目標個數.
圖 2 HCS的計算流程圖
在流程圖 2中,Nd是局部搜索的最大迭代次數;T是衡量決策變量變化的參數;Na是搜尋最優T值的最大試驗次數;Xni表示第i次迭代選取的鄰域解的決策變量;εy是計算最優變化量的參數,一般選取2~5;L0是近似表達目標函數梯度信息的變量;a是Nd次迭代搜尋過程中決策變量的平均變化量;其余符號如前所述.根據初始解與鄰域解的Pareto主導關系可以將HCS分為Hill Climber與Step兩個部分.當在Nd次迭代搜索內存在鄰域解與初始解是Pareto主導關系,則進行最優方向的搜索.Lara et al提出以二次多項式的形式估計函數F(T),即F(T)=aT2+bT+c.當函數值F(T0),F(T1),F(T2)存在以下關系,即：
(3)
則認為存在最優值T=-b/(2a).如圖 2所示,當經過Na次試驗未滿足式(3)的條件,則以最小變化量T0作為最優值.如果經過Nd次搜索,鄰域解與初始解均處于非支配的關系,則認為初始解是局部最優Pareto解.為了保持解的多樣性,Lara et al提出利用Nd個鄰域解沿著Pareto解的鋒面方向繼續搜索,具體搜索過程如圖 2所示.
HCS需要輸入的主要參數是搜尋半徑r與最大迭代搜尋次數N.N值越大,局部搜尋的解更可能達到最優解,但同時會增加目標函數的評價次數,因此,Lara et al.建議N值一般取5～10.由于是局部搜索,搜尋半徑不宜過大,一般取值0.1～ 0.3.啟發式搜尋最優T值的方法需要指定最大試驗次數Na,Na值過大則降低算法的效率,本文根據Lara et al建議取值為3.
2.3 組合優化的方法
混合多目標算法的兩個重要問題是如何選擇個體作為局部搜尋的初始解與如何平衡全局搜索與局部搜索之間的關系.遺傳算法的搜尋特點是在初期階段的全局搜索能力可以快速找到接近最優解的個體,但是到后期階段收斂到最優解的速度減慢.因此,在實施局部搜索時,應選取當前代進化得到最優個體作為初始解.全局搜索與局部搜索的平衡關系可以由當前選擇個體作為初始解的概率來調節.如果在進化初期階段選擇概率較大,則搜尋的解易陷入局部最優的陷阱.
理想算例將局部搜尋設定在進化的10代以后,使遺傳算法的全局搜索能力得到發揮.然后,每隔5代進行局部搜索,每一代搜索的概率服從以下函數分布：
(4)
式中,pl是局部搜索概率,rw,ra是函數分布參數,pmax是最大的局部搜索概率,m是進化過程中種群的局部搜索次數.在求解理想算例時,將pmax設定為0.3,m設定為20,函數圖像如圖 3所示.
圖 3局部搜索概率分布曲線
從圖 3中可以看到遺傳算法進化的初始階段局部搜尋概率小,有利于全局尋優,進化的中期增加局部搜索的能力改善解的精度,到后期可以減少局部搜索避免陷入局部最優的陷阱同時減少函數評價的次數,提高算法的效率.
2.4 標準測試函數的檢驗
為了測試NSGAII-HCS算法的性能,選用多目標問題的經典測試函數CONV1與ZDT6,其函數表達式分別是：
CONV1目標函數：
(5)
(6)
約束條件：
(7)
ZDT6目標函數：
(8)
(9)
約束條件：
(10)
(11)
標準測試函數的多目標遺傳算法參數如表 1所示.如圖 4a所示,對于凸形的多目標函數CONV1,NSGAII-HCS得到的解更趨近真實的Pareto解集,但是進化的總代數較小,因此不能使所有的解完全收斂到真實的Pareto鋒面.如圖 4b所示,對于凹形的多目標函數ZDT6,NSGAII-HCS在種群進化到第100代時,解完全收斂到真實的Pareto鋒面,表明了該算法具有在保持解多樣性的同時,可以使Pareto解達到局部最優性;而NSGAII在種群進化到第250代時,得到的Pareto鋒面與真實的Pareto鋒面的平均距離為0.16,仍與真實Pareto解存在較大的差距.標準函數的測試結果表明了NSGAII-HCS與NSGAII相比能搜尋到真實的Pareto解,具有明顯的優勢.
表 1 多目標遺傳算法參數
圖 4 NSGAII與NSGAII-HCS求解CONV1(a)與ZDT6(b)的數值計算結果
3 算例分析
3.1 算例概述
本理想算例來自文獻Zheng and Wang,目的是利用NSGAII-HCS來設計一個抽取-處理(pump-and-treat,PAT)系統,以同時達到治理成本最小和含水層中剩余污染物最小這兩個目標.算例場地信息可參見相關文獻.該算例的地下水污染優化管理模型即：
目標函數：
(12)
(13)
約束條件：
(14)
(15)
其中,f1是治理成本,a1是安裝抽水井的總費用(設為CNY150000),N是PAT系統控制井的數量,Nw是非零流量井的數量,a2是處理單位體積污水需要的費用(設為CNY 0.76· m-3),Qi是第i口井的流量(m3 · d-1),Δti是第i口井持續抽水的時間(d),f2是治理結束后剩余污染物質量與初始質量的百分比,massinitial是含水層初始污染物質量(kg),massend是剩余污染物質量(kg),C*是污染物濃度約束區域的最大允許濃度值(設為20 g · m-3),mc是污染物濃度約束區域節點的數量.
對于研究區的所有節點的濃度通過調用地下水水流模型MODFLOW與溶質運移模型MT3DMS計算,研究區的各點的污染物濃度取決于抽水量,抽水持續時間以及初始污染物濃度.函數表達式如下：
(16)
3.2 結果與討論
本文將NSGAII-HCS和NSGAII分別與常用的地下水流模型MODFLOW和溶質運移模型MT3DMS相耦合,模擬優化理想條件下二維的地下水污染修復系統.兩種算法在全局搜索的遺傳算法上使用的參數相同,即種群大小為100,進化的總代數為100代,交叉概率為0.9,突變概率為0.05.對于局部搜索,最大的局部搜索概率為0.3,鄰域搜索半徑為0.2,每隔5代進行局部搜索,最大的迭代搜索次數為5次.本文引入多樣性、收斂性和均勻性三個指標來評價NSGAII-HCS的尋優性能.
3.2.1 算法性能的衡量指標
多樣性的衡量是通過將兩種算法計算的解合并,并重新進行非支配解的排序得到最優解集,將每一種算法在最優解集中占有的Pareto解的個數作為多樣性指標.收斂性指標是參照Deb提出的計算方法,即選取若干個真實的Pareto解作為參考點,然后計算多目標算法得到的權衡曲線與參考點構成的權衡曲線的距離.計算方程如下：
(17)
式中,N是種群大小,dij是第i個進化的個體到第j個參考點的距離,R是選取的參考點個數.Z值越大表示計算的解與真實解的差距越大,解的收斂性差,反之,收斂性好.由于地下水污染優化管理模型真實的Pareto解集未知,所以從兩種算法合并后的最優解集中選取若干個均勻分布的Pareto解作為參考點.
均勻性指標的計算方程如下：
(18)
式中,N是Pareto解的個數,di是權衡曲線上相鄰兩點的距離, 是di的平均值.若解的分布比較均勻,則相鄰點距離與平均距離相近,Δ較小.反之,Δ較大.
3.2.2 優化結果的對比與分析
將NSGAII與NSGAII-HCS計算得到的結果進行對比分析(圖 5).在剩余污染物百分比大于15%時,NSGAII-HCS可以搜索到收斂性與多樣性更優的解,同時保證所有的Pareto解在權衡曲線上均勻分布.因此,NSGAII-HCS能尋找到精度更高的Pareto解,并能提升解的多樣性,具有更加明顯的優勢.
圖 5 NSGAII與NSGAII-HCS運行到100代時的Pareto解集
為了比較在種群進化過程中兩種不同算法的收斂性,可以計算NSGAII與NSGAII-HCS的每一代種群收斂性指標的差值ΔZ.ΔZ為正值表示NSGAII-HCS計算的解與參考點的距離較小.如圖 6所示,在進化的初期由于遺傳算法的全局搜索的能力,NSGAII算法發揮較大的作用,而局部搜索可能使解陷入局部最優值.在進化的中后期,遺傳算法尋找到接近真實Pareto解的最優解而繼續搜索真實解的效率逐漸降低.NSGAII-HCS具有的局部搜索能力可以很大程度上改善遺傳算法在中后期搜索的Pareto解,使種群的收斂速度加快.如表 2所示,兩種算法運行到100代時,NSGAII-HCS的Z值較小,表明解的精度更高.Pareto解集的多樣性與均勻性的提升有助于決策者根據自己的要求選擇最優的管理方案.從表 2中也可以看到,NSGAII-HCS在保證Pareto解局部最優性的同時,可以提供多樣的解并且解的分布較均勻.具體參見污水寶商城資料或http://www.dongaorq.cn更多相關技術文檔。
圖 6兩種算法收斂性指標的差值與進化代數的關系
表 2 NSGAII與NSGAII-HCS運行到100代時Pareto解比較
4 結論與展望
1) 為了提高多目標遺傳算法Pareto解的局部最優性,將NSGAII與一種迭代式的局部搜索算法HCS相結合,開發了一種新的混合多目標遺傳算法NSGAII-HCS.HCS通過利用鄰域解確定最優的搜尋方向,使種群朝著真實解的方向收斂,提高了收斂速度與解的精度.同時,在尋找到最優解后,HCS利用局部搜索的解沿著Pareto鋒面的方向繼續搜索,有助于改善解的多樣性.通過選擇兩個經典的多目標測試函數檢驗算法的性能,結果表明NSGAII-HCS的解更加接近或完全收斂到真實的Pareto解.
2) 將NSGAII-HCS應用于理想的二維地下水污染修復管理模型中,從Pareto解的收斂性、多樣性和均勻性方面分析,可以得到該算法與NSGAII相比能尋找到精度更高、跨度更大、沿權衡曲線分布更均勻的Pareto解.NSGAII-HCS同時具有遺傳算法的全局搜索能力和HCS的局部搜索能力,而在進化過程中,NSGAII-HCS在中后期的局部搜索使收斂速度明顯加快.在地下水污染修復優化管理模型中,精度更高的解可以節約污染物治理成本,同時有助于選擇最高效的管理策略,使地下水污染治理的目標達到.NSGAII-HCS的優點則是能加速收斂到最優解,使決策者能選擇最理想的治理方案.
3) 盡管本文算例是一理想的二維均質等厚各向同性承壓含水層系統,但由于NSGAII-HCS耦合的水流和污染物運移模型適用于任何多孔介質的地下水系統,因此該優化模型同樣可推廣應用到實際含水層的地下水污染修復管理.當然,其優化效果如何,有待于后續應用實踐的檢驗.另一方面,NSGAII-HCS每隔幾代進行局部搜索的策略可能減小了算法的效率,如何進行自適應的局部搜索有待于一步研究.將NSGAII-HCS應用于實際場地條件下的地下水污染修復管理,充分發揮該算法的優點是未來的發展方向.
