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