0371-60972711
來(lái)源： 點(diǎn)擊：1663 喜歡：0
2016-10-25 09:05:20 來(lái)源： 點(diǎn)擊：
1 引言地下水污染修復(fù)實(shí)際上是一個(gè)既考慮治理效果又考慮治理成本的復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題.當(dāng)前,求解多目標(biāo)問(wèn)題最有效的方法是多目標(biāo)智能優(yōu)化算法,一方面,該算法可以并行地處理一組可能的解(群體),能在一次算法過(guò)程中找到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ī)劃問(wèn)題不能保證收斂到最優(yōu)解.鑒于以上不足,國(guó)內(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é)合,開(kāi)發(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)化過(guò)程中的優(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ī)劃問(wèn)題,不能準(zhǔn)確計(jì)算目標(biāo)函數(shù)的梯度信息,因此本文采用無(wú)梯度計(jì)算的局部搜尋方法.
為了詳細(xì)闡述HCS的具體搜索過(guò)程,可以將HCS作為一種對(duì)遺傳算法進(jìn)化的Pareto解進(jìn)行局部搜索,然后輸出局部最優(yōu)解的獨(dú)立的算法,而HCS與NSGAII的耦合過(guò)程如圖 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)過(guò)程中選取鄰域解的參考解集,以進(jìn)化過(guò)程中父代與子代解集作為參考解集并從中選取符合要求的鄰域解,這樣可以減少因產(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次迭代搜尋過(guò)程中決策變量的平均變化量;其余符號(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)過(guò)Na次試驗(yàn)未滿足式(3)的條件,則以最小變化量T0作為最優(yōu)值.如果經(jīng)過(guò)Nd次搜索,鄰域解與初始解均處于非支配的關(guān)系,則認(rèn)為初始解是局部最優(yōu)Pareto解.為了保持解的多樣性,Lara et al提出利用Nd個(gè)鄰域解沿著Pareto解的鋒面方向繼續(xù)搜索,具體搜索過(guò)程如圖 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.由于是局部搜索,搜尋半徑不宜過(guò)大,一般取值0.1～ 0.3.啟發(fā)式搜尋最優(yōu)T值的方法需要指定最大試驗(yàn)次數(shù)Na,Na值過(guò)大則降低算法的效率,本文根據(jù)Lara et al建議取值為3.
2.3 組合優(yōu)化的方法
混合多目標(biāo)算法的兩個(gè)重要問(wèn)題是如何選擇個(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è)體作為初始解的概率來(lái)調(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)化過(guò)程中種群的局部搜索次數(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)問(wèn)題的經(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 算例概述
本理想算例來(lái)自文獻(xiàn)Zheng and Wang,目的是利用NSGAII-HCS來(lái)設(shè)計(jì)一個(gè)抽取-處理(pump-and-treat,PAT)系統(tǒng),以同時(shí)達(dá)到治理成本最小和含水層中剩余污染物最小這兩個(gè)目標(biāo).算例場(chǎng)地信息可參見(jiàn)相關(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)的濃度通過(guò)調(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)來(lái)評(píng)價(jià)NSGAII-HCS的尋優(yōu)性能.
3.2.1 算法性能的衡量指標(biāo)
多樣性的衡量是通過(guò)將兩種算法計(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)化過(guò)程中兩種不同算法的收斂性,可以計(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é)合,開(kāi)發(fā)了一種新的混合多目標(biāo)遺傳算法NSGAII-HCS.HCS通過(guò)利用鄰域解確定最優(yōu)的搜尋方向,使種群朝著真實(shí)解的方向收斂,提高了收斂速度與解的精度.同時(shí),在尋找到最優(yōu)解后,HCS利用局部搜索的解沿著Pareto鋒面的方向繼續(xù)搜索,有助于改善解的多樣性.通過(guò)選擇兩個(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)化過(guò)程中,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)是未來(lái)的發(fā)展方向.
上一篇：沒(méi)有了
下一篇：如何南方污水處理廠中試脫氮工藝的效率
