1 引言

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

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

　　2 混合多目標遺傳算法

　　2.1 快速非支配遺傳算法

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

　　圖 1 NSGAII-HCS的計算流程圖

　　2.2 局部搜索算法

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

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

　　(1)

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

　　(2)

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

　　圖 2 HCS的計算流程圖

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

　　(3)

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

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

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

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

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

　　(4)

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

　　圖 3局部搜索概率分布曲線

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

　　2.4 標準測試函數(shù)的檢驗

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

　　CONV1目標函數(shù)：

　　(5)

　　(6)

　　約束條件：

　　(7)

　　ZDT6目標函數(shù)：

　　(8)

　　(9)

　　約束條件：

　　(10)

　　(11)

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

　　表 1 多目標遺傳算法參數(shù)

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

　　3 算例分析

　　3.1 算例概述

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

　　目標函數(shù)：

　　(12)

　　(13)

　　約束條件：

　　(14)

　　(15)

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

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

　　(16)

　　3.2 結(jié)果與討論

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

　　3.2.1 算法性能的衡量指標

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

　　(17)

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

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

　　(18)

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

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

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

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

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

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

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

　　4 結(jié)論與展望

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

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

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