地下水污染修復管理模型求解方法

　　1 引言

　　地下水污染修復實(shí)際上是一個(gè)既考慮治理效果又考慮治理成本的復雜的多目標優(yōu)化問(wèn)題.當前,求解多目標問(wèn)題最有效的方法是多目標智能優(yōu)化算法,一方面,該算法可以并行地處理一組可能的解(群體),能在一次算法過(guò)程中找到Pareto最優(yōu)集中的多個(gè)解;另一方面進(jìn)化算法不局限于Pareto前端的形狀和連續性,易于處理不連續的、凹形的多目標函數,能夠有效地克服古典方法的局限性.如基于小生境的Pareto遺傳算法(niched Pareto genetic algorithm,NPGA),快速非支配遺傳算法(nondominated sorting genetic algorithm Ⅱ,NSGA Ⅱ)等.以上提出的多目標遺傳算法具有良好的全局搜索能力,然而在搜索的中后期,算法收斂于真實(shí)最優(yōu)解的效率大幅降低,而且遺傳算法是以種群為單位的群體搜索方法,對于復雜的非線(xiàn)性規劃問(wèn)題不能保證收斂到最優(yōu)解.鑒于以上不足,國內外研究者提出了多種對傳統多目標智能優(yōu)化算法的改進(jìn)算法.本文對遺傳算法初期搜索到的優(yōu)化解進(jìn)行局部搜索,形成了一種新的混合多目標優(yōu)化模式.該混合算法即是利用遺傳算法的全局搜索能力搜尋最優(yōu)解,然后將進(jìn)化的解作為初始解進(jìn)行局部搜索以搜尋到真實(shí)的Pareto最優(yōu)解.

　　本文將NSGAII與一種迭代式的局部搜索算法(Hill Climber with Step,HCS)相結合,開(kāi)發(fā)了一種新的混合多目標遺傳算法NSGAII-HCS.利用CONV1和ZDT6兩個(gè)經(jīng)典的多目標優(yōu)化函數對NSGAII-HCS的性能進(jìn)行測試.最后,將NSGAII-HCS與地下水流模擬軟件MODFLOW和溶質(zhì)運移模擬軟件MT3DMS相耦合,并應用到一個(gè)理想的二維地下水污染修復管理模型中,結果分析表明該方法可為地下水污染治理提供多樣的和收斂的Pareto管理策略,是一種穩定可靠的多目標優(yōu)化方法.

　　2 混合多目標遺傳算法

　　2.1 快速非支配遺傳算法

　　NSGAII是一種可以快速進(jìn)行Pareto排序的非支配多目標遺傳算法,如圖 1所示.該算法的優(yōu)點(diǎn)主要包括以下3個(gè)方面：① 提出快速非支配排序法,降低算法的復雜度;② 提出擁擠度與擁擠度比較算子,代替了需要指定共享半徑的適應度共享策略,并在同一級排序中將擁擠度作為個(gè)體的勝出標準,保持了種群的多樣性;③ 引入精英策略,有利于保存種群進(jìn)化過(guò)程中的優(yōu)良個(gè)體,加速了種群的收斂.以上優(yōu)點(diǎn)使NSGAII成為一種廣泛應用的多目標智能優(yōu)化算法,并作為與其它改進(jìn)算法的比較基準.

　　圖 1 NSGAII-HCS的計算流程圖

　　2.2 局部搜索算法

　　HCS是一種基于最優(yōu)搜尋方向的迭代式局部搜索方法.由于地下水污染修復管理模型是復雜的非線(xiàn)性規劃問(wèn)題,不能準確計算目標函數的梯度信息,因此本文采用無(wú)梯度計算的局部搜尋方法.

　　為了詳細闡述HCS的具體搜索過(guò)程,可以將HCS作為一種對遺傳算法進(jìn)化的Pareto解進(jìn)行局部搜索,然后輸出局部最優(yōu)解的獨立的算法,而HCS與NSGAII的耦合過(guò)程如圖 1所示.HCS的計算流程圖如圖 2所示.為了決定局部搜尋的方向,需要利用初始解的給定鄰域半徑內的鄰域解.鄰域解的定義即：

　　(1)

　　式中,X0=(x01,x02,…,x0m);Xn=(xn1,xn2,…,xnm).X0是初始解決策變量的向量形式;Xn 是鄰域解決策變量的向量形式;m是決策變量的個(gè)數;x0i是初始解第i個(gè)決策變量;H是在尋優(yōu)過(guò)程中選取鄰域解的參考解集,以進(jìn)化過(guò)程中父代與子代解集作為參考解集并從中選取符合要求的鄰域解,這樣可以減少因產(chǎn)生鄰域解而需要的目標函數評價(jià),增加算法的效率;r是鄰域半徑.若鄰域解Pareto主導初始解并以Xn

　　(2)

　　式中,fi(X)表示第i個(gè)目標函數,k表示目標個(gè)數.

　　圖 2 HCS的計算流程圖

　　在流程圖 2中,Nd是局部搜索的最大迭代次數;T是衡量決策變量變化的參數;Na是搜尋最優(yōu)T值的最大試驗次數;Xni表示第i次迭代選取的鄰域解的決策變量;εy是計算最優(yōu)變化量的參數,一般選取2~5;L0是近似表達目標函數梯度信息的變量;a是Nd次迭代搜尋過(guò)程中決策變量的平均變化量;其余符號如前所述.根據初始解與鄰域解的Pareto主導關(guān)系可以將HCS分為Hill Climber與Step兩個(gè)部分.當在Nd次迭代搜索內存在鄰域解與初始解是Pareto主導關(guān)系,則進(jìn)行最優(yōu)方向的搜索.Lara et al提出以二次多項式的形式估計函數F(T),即F(T)=aT2+bT+c.當函數值F(T0),F(T1),F(T2)存在以下關(guān)系,即：

　　(3)

　　則認為存在最優(yōu)值T=-b/(2a).如圖 2所示,當經(jīng)過(guò)Na次試驗未滿(mǎn)足式(3)的條件,則以最小變化量T0作為最優(yōu)值.如果經(jīng)過(guò)Nd次搜索,鄰域解與初始解均處于非支配的關(guān)系,則認為初始解是局部最優(yōu)Pareto解.為了保持解的多樣性,Lara et al提出利用Nd個(gè)鄰域解沿著(zhù)Pareto解的鋒面方向繼續搜索,具體搜索過(guò)程如圖 2所示.

　　HCS需要輸入的主要參數是搜尋半徑r與最大迭代搜尋次數N.N值越大,局部搜尋的解更可能達到最優(yōu)解,但同時(shí)會(huì )增加目標函數的評價(jià)次數,因此,Lara et al.建議N值一般取5～10.由于是局部搜索,搜尋半徑不宜過(guò)大,一般取值0.1～ 0.3.啟發(fā)式搜尋最優(yōu)T值的方法需要指定最大試驗次數Na,Na值過(guò)大則降低算法的效率,本文根據Lara et al建議取值為3.

　　2.3 組合優(yōu)化的方法

　　混合多目標算法的兩個(gè)重要問(wèn)題是如何選擇個(gè)體作為局部搜尋的初始解與如何平衡全局搜索與局部搜索之間的關(guān)系.遺傳算法的搜尋特點(diǎn)是在初期階段的全局搜索能力可以快速找到接近最優(yōu)解的個(gè)體,但是到后期階段收斂到最優(yōu)解的速度減慢.因此,在實(shí)施局部搜索時(shí),應選取當前代進(jìn)化得到最優(yōu)個(gè)體作為初始解.全局搜索與局部搜索的平衡關(guān)系可以由當前選擇個(gè)體作為初始解的概率來(lái)調節.如果在進(jìn)化初期階段選擇概率較大,則搜尋的解易陷入局部最優(yōu)的陷阱.

　　理想算例將局部搜尋設定在進(jìn)化的10代以后,使遺傳算法的全局搜索能力得到發(fā)揮.然后,每隔5代進(jìn)行局部搜索,每一代搜索的概率服從以下函數分布：

　　(4)

　　式中,pl是局部搜索概率,rw,ra是函數分布參數,pmax是最大的局部搜索概率,m是進(jìn)化過(guò)程中種群的局部搜索次數.在求解理想算例時(shí),將pmax設定為0.3,m設定為20,函數圖像如圖 3所示.

　　圖 3局部搜索概率分布曲線(xiàn)

　　從圖 3中可以看到遺傳算法進(jìn)化的初始階段局部搜尋概率小,有利于全局尋優(yōu),進(jìn)化的中期增加局部搜索的能力改善解的精度,到后期可以減少局部搜索避免陷入局部最優(yōu)的陷阱同時(shí)減少函數評價(jià)的次數,提高算法的效率.

　　2.4 標準測試函數的檢驗

　　為了測試NSGAII-HCS算法的性能,選用多目標問(wèn)題的經(jīng)典測試函數CONV1與ZDT6,其函數表達式分別是：

　　CONV1目標函數：

　　(5)

　　(6)

　　約束條件：

　　(7)

　　ZDT6目標函數：

　　(8)

　　(9)

　　約束條件：

　　(10)

　　(11)

　　標準測試函數的多目標遺傳算法參數如表 1所示.如圖 4a所示,對于凸形的多目標函數CONV1,NSGAII-HCS得到的解更趨近真實(shí)的Pareto解集,但是進(jìn)化的總代數較小,因此不能使所有的解完全收斂到真實(shí)的Pareto鋒面.如圖 4b所示,對于凹形的多目標函數ZDT6,NSGAII-HCS在種群進(jìn)化到第100代時(shí),解完全收斂到真實(shí)的Pareto鋒面,表明了該算法具有在保持解多樣性的同時(shí),可以使Pareto解達到局部最優(yōu)性;而NSGAII在種群進(jìn)化到第250代時(shí),得到的Pareto鋒面與真實(shí)的Pareto鋒面的平均距離為0.16,仍與真實(shí)Pareto解存在較大的差距.標準函數的測試結果表明了NSGAII-HCS與NSGAII相比能搜尋到真實(shí)的Pareto解,具有明顯的優(yōu)勢.

　　表 1 多目標遺傳算法參數

　　圖 4 NSGAII與NSGAII-HCS求解CONV1(a)與ZDT6(b)的數值計算結果

　　3 算例分析

　　3.1 算例概述

　　本理想算例來(lái)自文獻Zheng and Wang,目的是利用NSGAII-HCS來(lái)設計一個(gè)抽取-處理(pump-and-treat,PAT)系統,以同時(shí)達到治理成本最小和含水層中剩余污染物最小這兩個(gè)目標.算例場(chǎng)地信息可參見(jiàn)相關(guān)文獻.該算例的地下水污染優(yōu)化管理模型即：

　　目標函數：

　　(12)

　　(13)

　　約束條件：

　　(14)

　　(15)

　　其中,f1是治理成本,a1是安裝抽水井的總費用(設為CNY150000),N是PAT系統控制井的數量,Nw是非零流量井的數量,a2是處理單位體積污水需要的費用(設為CNY 0.76· m-3),Qi是第i口井的流量(m3 · d-1),Δti是第i口井持續抽水的時(shí)間(d),f2是治理結束后剩余污染物質(zhì)量與初始質(zhì)量的百分比,massinitial是含水層初始污染物質(zhì)量(kg),massend是剩余污染物質(zhì)量(kg),C*是污染物濃度約束區域的最大允許濃度值(設為20 g · m-3),mc是污染物濃度約束區域節點(diǎn)的數量.

　　對于研究區的所有節點(diǎn)的濃度通過(guò)調用地下水水流模型MODFLOW與溶質(zhì)運移模型MT3DMS計算,研究區的各點(diǎn)的污染物濃度取決于抽水量,抽水持續時(shí)間以及初始污染物濃度.函數表達式如下：

　　(16)

　　3.2 結果與討論

　　本文將NSGAII-HCS和NSGAII分別與常用的地下水流模型MODFLOW和溶質(zhì)運移模型MT3DMS相耦合,模擬優(yōu)化理想條件下二維的地下水污染修復系統.兩種算法在全局搜索的遺傳算法上使用的參數相同,即種群大小為100,進(jìn)化的總代數為100代,交叉概率為0.9,突變概率為0.05.對于局部搜索,最大的局部搜索概率為0.3,鄰域搜索半徑為0.2,每隔5代進(jìn)行局部搜索,最大的迭代搜索次數為5次.本文引入多樣性、收斂性和均勻性三個(gè)指標來(lái)評價(jià)NSGAII-HCS的尋優(yōu)性能.

　　3.2.1 算法性能的衡量指標

　　多樣性的衡量是通過(guò)將兩種算法計算的解合并,并重新進(jìn)行非支配解的排序得到最優(yōu)解集,將每一種算法在最優(yōu)解集中占有的Pareto解的個(gè)數作為多樣性指標.收斂性指標是參照Deb提出的計算方法,即選取若干個(gè)真實(shí)的Pareto解作為參考點(diǎn),然后計算多目標算法得到的權衡曲線(xiàn)與參考點(diǎn)構成的權衡曲線(xiàn)的距離.計算方程如下：

　　(17)

　　式中,N是種群大小,dij是第i個(gè)進(jìn)化的個(gè)體到第j個(gè)參考點(diǎn)的距離,R是選取的參考點(diǎn)個(gè)數.Z值越大表示計算的解與真實(shí)解的差距越大,解的收斂性差,反之,收斂性好.由于地下水污染優(yōu)化管理模型真實(shí)的Pareto解集未知,所以從兩種算法合并后的最優(yōu)解集中選取若干個(gè)均勻分布的Pareto解作為參考點(diǎn).

　　均勻性指標的計算方程如下：

　　(18)

　　式中,N是Pareto解的個(gè)數,di是權衡曲線(xiàn)上相鄰兩點(diǎn)的距離, 是di的平均值.若解的分布比較均勻,則相鄰點(diǎn)距離與平均距離相近,Δ較小.反之,Δ較大.

　　3.2.2 優(yōu)化結果的對比與分析

　　將NSGAII與NSGAII-HCS計算得到的結果進(jìn)行對比分析(圖 5).在剩余污染物百分比大于15%時(shí),NSGAII-HCS可以搜索到收斂性與多樣性更優(yōu)的解,同時(shí)保證所有的Pareto解在權衡曲線(xiàn)上均勻分布.因此,NSGAII-HCS能尋找到精度更高的Pareto解,并能提升解的多樣性,具有更加明顯的優(yōu)勢.

　　圖 5 NSGAII與NSGAII-HCS運行到100代時(shí)的Pareto解集

　　為了比較在種群進(jìn)化過(guò)程中兩種不同算法的收斂性,可以計算NSGAII與NSGAII-HCS的每一代種群收斂性指標的差值ΔZ.ΔZ為正值表示NSGAII-HCS計算的解與參考點(diǎn)的距離較小.如圖 6所示,在進(jìn)化的初期由于遺傳算法的全局搜索的能力,NSGAII算法發(fā)揮較大的作用,而局部搜索可能使解陷入局部最優(yōu)值.在進(jìn)化的中后期,遺傳算法尋找到接近真實(shí)Pareto解的最優(yōu)解而繼續搜索真實(shí)解的效率逐漸降低.NSGAII-HCS具有的局部搜索能力可以很大程度上改善遺傳算法在中后期搜索的Pareto解,使種群的收斂速度加快.如表 2所示,兩種算法運行到100代時(shí),NSGAII-HCS的Z值較小,表明解的精度更高.Pareto解集的多樣性與均勻性的提升有助于決策者根據自己的要求選擇最優(yōu)的管理方案.從表 2中也可以看到,NSGAII-HCS在保證Pareto解局部最優(yōu)性的同時(shí),可以提供多樣的解并且解的分布較均勻.具體參見(jiàn)污水寶商城資料或http://www.sharpedgetext.com更多相關(guān)技術(shù)文檔。

　　圖 6兩種算法收斂性指標的差值與進(jìn)化代數的關(guān)系

　　表 2 NSGAII與NSGAII-HCS運行到100代時(shí)Pareto解比較

　　4 結論與展望

　　1) 為了提高多目標遺傳算法Pareto解的局部最優(yōu)性,將NSGAII與一種迭代式的局部搜索算法HCS相結合,開(kāi)發(fā)了一種新的混合多目標遺傳算法NSGAII-HCS.HCS通過(guò)利用鄰域解確定最優(yōu)的搜尋方向,使種群朝著(zhù)真實(shí)解的方向收斂,提高了收斂速度與解的精度.同時(shí),在尋找到最優(yōu)解后,HCS利用局部搜索的解沿著(zhù)Pareto鋒面的方向繼續搜索,有助于改善解的多樣性.通過(guò)選擇兩個(gè)經(jīng)典的多目標測試函數檢驗算法的性能,結果表明NSGAII-HCS的解更加接近或完全收斂到真實(shí)的Pareto解.

　　2) 將NSGAII-HCS應用于理想的二維地下水污染修復管理模型中,從Pareto解的收斂性、多樣性和均勻性方面分析,可以得到該算法與NSGAII相比能尋找到精度更高、跨度更大、沿權衡曲線(xiàn)分布更均勻的Pareto解.NSGAII-HCS同時(shí)具有遺傳算法的全局搜索能力和HCS的局部搜索能力,而在進(jìn)化過(guò)程中,NSGAII-HCS在中后期的局部搜索使收斂速度明顯加快.在地下水污染修復優(yōu)化管理模型中,精度更高的解可以節約污染物治理成本,同時(shí)有助于選擇最高效的管理策略,使地下水污染治理的目標達到.NSGAII-HCS的優(yōu)點(diǎn)則是能加速收斂到最優(yōu)解,使決策者能選擇最理想的治理方案.

　　3) 盡管本文算例是一理想的二維均質(zhì)等厚各向同性承壓含水層系統,但由于NSGAII-HCS耦合的水流和污染物運移模型適用于任何多孔介質(zhì)的地下水系統,因此該優(yōu)化模型同樣可推廣應用到實(shí)際含水層的地下水污染修復管理.當然,其優(yōu)化效果如何,有待于后續應用實(shí)踐的檢驗.另一方面,NSGAII-HCS每隔幾代進(jìn)行局部搜索的策略可能減小了算法的效率,如何進(jìn)行自適應的局部搜索有待于一步研究.將NSGAII-HCS應用于實(shí)際場(chǎng)地條件下的地下水污染修復管理,充分發(fā)揮該算法的優(yōu)點(diǎn)是未來(lái)的發(fā)展方向.