一類基于-支配關系的多目標進化算法

1種新的基于-支配關系的多目標進化算法解優化問題（又稱數學方案問題）是指從所有可能的方案中選擇最合理的方式來實現目標優化的過程。通常，如果優化問題的目標數超過一個，則稱為多目標優化。在正常情況下，同一問題中的多個目標函數是矛盾的，因此最終結果是多個妥協的結果。多目標進化算法是指利用進化搜索的技術去解決多目標優化問題.Schaffer提出了第一個多目標進化算法即向量進化遺傳算法,而后該領域專家又提出了多種多目標進化算法并應用于求解實際問題.Coello總結了目前的多目標進化算法,并將它們分為兩代:第一代強調簡潔,第二代強調效率,它們之間的主要區別在于精英個體是否被引入種群的進化過程之中.Laumanns歸納了采用精英策略的多目標進化統一模型(UnifiedmodelforMOEAs,UMMEA),通過將存儲當前所有非被支配個體的種群同一般的進化種群相結合,實現精英參與種群的進化.大部分第二代的多目標進化算法,如強度Pareto進化算法(SPEA)、強度Pareto進化算法2(SPEA2)、Pareto包絡選擇算法(PAES)都符合這樣的模型結構.另一個常用的非劣排序遺傳算法2(NSGAII)沒有直接利用外部種群.它將子代種群和父代種群相結合,優先選擇其中的精英個體去構成下一代的進化種群.這種策略也實現了精英個體加入種群進化,并取得了很好的計算結果.另一個分類標準即是否采用了Pareto支配排序.Goldberg率先將Pareto優化的概念引入多目標進化算法.當前的多目標進化算法大多通過Pareto支配關系的排序來計算種群中個體的適應值,從而引導種群朝向Pareto前沿面進化.雖然這種方法可以較好地改善算法的收斂性,但是排序過程要耗費大量的計算.為了提高進化算法效率,一些研究者采用了穩態的進化策略.所謂穩態是當新個體產生后立即加入到種群的下一代進化過程之中,如簡單進化算法(SEAMO)、Pareto收斂遺傳算法(PCGA)、ε-多目標進化算法(ε-MOEA).在選擇個體進入交配池的操作中,它們均采用配對比較的方法,而沒有進行個體適應值的計算.實驗結果表明這些基于穩態的進化算法在處理某些問題上要優于基于Pareto排序的算法.另外,由于非支配解的數量巨大,而外部種群存儲容量有限,很多修剪策略,如PAES中的自適應網格、NSGAII中的Crowding-Distance、SPEA中的聚類和SPEA2中的最近距離方法等都在各自算法中發揮了很好的作用.然而,正如文獻所述,這些修剪策略很可能造成Pareto前沿的退化,進而影響到最終種群的收斂.Laummans根據ε-支配關系,提出一種基于網格向量的種群修剪策略,可以很好地防止進化過程中種群的退化.這種策略在計算網格向量時,除了ε參數,還需要獲得各個目標上的最小值,并且相同網格中的個體比較需要計算各自的歐式距離,相對來說計算量比較大.本文提出了一種新的基于ε-支配關系的多目標進化算法,即ε-支配多目標進化算法(ε-DominanceMOEA,EDMOEA).該算法采用一種新的基于ε-支配關系的修剪策略,不僅可以防止退化現象,還可以有效地保存極端值個體以保證Pareto前沿面的廣度.該算法基于穩態替換策略,利用μ+2的選擇方法,可以更加快速有效地到達Pareto前沿面.同時,在新算法中采用了新的自適應ε調整策略,實驗結果驗證了這種新策略的優越性.本文第2節介紹Pareto優化和ε-Pareto優化的概念;第3節簡要引入協同UMMEA模型,并對其進行修正;第4節詳細討論新的EDMOEA算法和自適應ε調整策略;第5節針對在一系列測試函數上的計算實驗,將包含自適應調整策略的自適應多目標進化算法(AEDMOEA)同固定ε策略的EDMOEA及NSGAII,SPEA2,ε-MOEA等其它算法進行對比,分析新算法的性能優勢;第6節總結本文研究結論.2基本總結2.1pareto最優解在多目標優化問題中,Pareto優化解是最常用的優化概念.它最早由FrancisYsidroEdgeworth在1881年提出而后經VilfredoPareto推廣(為方便討論起見,本文的優化問題皆為最小化問題),其定義如下.定義1(Pareto支配).設f:Rm→Rk,x1,x2∈Ω?Rm,稱解x1支配解x2當且僅當f(x1)部分地優于f(x2),即?i∈{1,2,…,k},fi(x1)≤fi(x2)∧?i∈{1,2,…,k},fi(x1)<fi(x2),記作x1?x2.定義2(Pareto最優解).解x*∈Ω稱之為解集合Ω的Pareto優化解當且僅當集合{x|x?x*,x∈Ω}=?.定義3(Pareto最優解集).對于給定的多目標優化問題,設其定義域為Ω,則其Pareto最優集X*,定義為:X?={x∈Ω|??x′∈Ω,f(x′)?f(x)}.X*={x∈Ω|??x′∈Ω,f(x′)?f(x)}.將Pareto最優解集在函數空間上對應的集合稱之為Pareto前沿,記為PF*.2.2x為集合x的-pareto解集及-pareto解集的可能性ε-支配關系是傳統的Pareto支配關系的弱化,其具有多種概念形式.這里我們采用加ε的形式,且對于給定的ε∈Rk,εi>0,?i∈k.其定義如下:定義4(ε-支配).設f:Rm→Rk,x1,x2∈Ω?Rm,對ε∈Rk,εi>0,稱x1ε-支配x2當且僅當?i∈{1,2,…,k},fi(x1)-εi≤fi(x2),且?i,fi(x1)-εi<fi(x2).記為x1?εx2.定義5(ε-Pareto最優解集近似).集合Xa稱為X的ε-Pareto最優解集近似,當且僅當對任意x∈X都存在?x′∈Xa,使得x′?εx.定義6(ε-Pareto解集).集合Xε稱為集合X的ε-Pareto解集,當且僅當Xε為集合X的ε-Pareto最優解集近似,且Xε?X*.根據以上定義,可以得到如下兩個定理.定理1.x1,x2∈X,x1?x2?x1?εx2.證明.因為x1?x2,故對?i有fi(x1)≤fi(x2),且?i使得fi(x1)<fi(x2)fi(x1)<fi(x2).又由εi>0,則對?i,fi(x1)?εi<fi(x2)?i,fi(x1)-εi<fi(x2).因此可知x1?εx2.定理得證.證畢.定理2.設x1,x2,x3∈X,則有x1?x2,x2?εx3?x1?εx3.證明.由題設可知x1?x2,則有?i,fi(x1)≤fi(x2)?i,fi(x1)≤fi(x2),且?i使得fi(x1)<fi(x2)fi(x1)<fi(x2).又由εi>0,故可知?i,fi(x1)?εi<fi(x2)?εi?i,fi(x1)-εi<fi(x2)-εi.另一方面,由x2?εx3,據定義可知?i,fi(x2)?εi≤fi(x3),?i,fi(x2)?εi<fi(x3)?i,fi(x2)-εi≤fi(x3),?i,fi(x2)-εi<fi(x3).顯然可知,對?i,有fi(x1)?εi<fi(x3)fi(x1)-εi<fi(x3),即x1?εx3.定理得證.證畢.值得注意的是,Xε和Xa分別作為集合X的ε-Pareto解集和ε-Pareto最優解集近似,都不是唯一的.一些個體靠近Pareto前沿,但不是Pareto最優解,若滿足ε-支配關系,都有可能包含在Xa中.定義6可以保證Xε中的個體皆為Pareto最優解.3精英強度修正Laumanns給出了采用精英策略的多目標進化算法的一般模型結構UMMEA,協同進化個體種群和精英種群.精英策略是指優良的個體不會因為劣個體的影響而被排除出種群的基因池.其算法流程如下:首先,采用初始化算子生成進化種群和精英種群,并選擇參數精英強度pe.然后,由當前的進化種群和精英種群生成子代種群.其中,精英強度pe控制精英個體的參與程度,即從精英種群中選擇個體作為交配個體的概率.取樣過程由取樣算子(sample)控制,變化算子(vary)則通過交叉和變異操作而產生子代個體.雖然PAES,SPEA,SPEA2皆可抽象為這樣的構架,然而對于NSGAII和ε-MOEA來說,卻需要做一些必要的修正,如算法1所示.算法1.修正的具有精英策略的多目標進化算法.At表示精英種群,Bt表示進化種群,pteet表示精英強度,St表示子代種群.算法1在進化過程中強調了子代種群同父代種群之間的競爭作用.這種競爭不僅在評估過程中而且也分別在兩個種群的更新算子(update1和update2)中.顯然,ε-MOEA可以看作算法1的一個實例,NSGAII即是精英種群設置為零的特殊情形.當直接把子代種群看作下一代進化種群時,算法1同Laumanns所提的UMMEA是等價的.由于進化種群的更新過程同精英種群是相對獨立的,在進化過程中或許有部分的精英個體進入進化種群.因此,精英強度重新定義為從兩個協同種群中選擇的交配個體都為精英的概率.4標進化算法在本節中,我們提出了一類新的基于ε-支配關系的多目標進化算法.同ε-MOEA一樣,它也可以分解為算法1的實例.這兩個算法的主要區別即在于精英種群的更新策略上.新算法的更新策略結構簡單,且具有較少的參數設置.4.1-pareto解集的更新算法首先,我們給出對于給定的集合X逼近其Pareto最優解集的迭代搜索算法的基本框架,如算法2所示.算法2.迭代的搜索算法.其中,t表示迭代次數,x(t)表示在第t次循環時所產生的新的個體,而集合X(t)表示t時的精英種群.算子generate()是指在第t次迭代時產生新的子代個體;update()表示結合新的子代個體對原有的精英種群X(t-1)做更新操作,其流程如算法3所示.算法3.生成Pareto最優解集的更新算法.顯然,如果我們采用算法3的更新策略,通過算法2所得到的最終種群將是Pareto最優解集的子集合.然而若僅僅將算法3第2行的Pareto支配關系改為ε-Pareto支配關系,最后所輸出的解集僅僅是ε-Pareto最優解集近似.故一類新的用以生成ε-Pareto解集的算法構成如下.算法4.ε-Pareto解集的更新算法.定理3.設x(j)是第j代生成的個體,X(t)=∪tj=1j=1tx(j)為到第i代為止所生成的個體的集合.而X(t)指根據算法4的更新策略在第i代時所輸出的最終種群,則X(t)是X(t)的一個ε-Pareto解集.證明.首先,可證X(t)?X(t)*.令任意x∈X(t),x=x(τ),τ≤t.假設存在x′=x(τ′),x′?x,τ′≠τ.如果τ′<τ,則x在t=τ時不會被接收(算法4,第3行);如果存在x″=x(τ″),τ′<τ″<τ,使得x″?x′,則根據Pareto支配關系的傳遞性可知x″?x,故x依然被排除在最終種群之外.如果τ′>τ,則x將會從X(τ′)中被移除(算法4,第7行).這皆與x∈X(t)矛盾.故假設不成立,即X(t)中的任一個體均為非被支配解.其次,可證X(t)是集合X(t)的ε-Pareto最優解集近似.假設其不正確,則當且僅當存在x=x(τ),τ≤t,其不被X(t)的任何成員ε-Pareto支配,但卻不屬于集合X(t).倘若x不屬于集合X(t),則其或者在t=τ時不被集合X(τ-1)接收,或者在t=τ時被接收但在以后的更新過程中被移除.對于后者,只有當可以支配x的個體進入X(t)中,移除才能進行.根據定理1,若兩個個體滿足支配關系則意味著它們也滿足ε-支配關系.而又因為支配關系具有傳遞性,故在輸出種群X(t)中必有一個體可以ε-支配x,這與假設矛盾.另一方面,拒絕操作發生在算法4的第2或第9行.同理可知,如果個體x被拒絕,則表明種群中存在某一個體對它具有ε-支配關系.而根據定理2,即使這樣的個體在以后的更新過程中被移出,其替代個體仍然可以ε-支配x,亦與假設矛盾.故綜合可知,X(t)是X(t)的一個ε-Pareto解集.定理得證.證畢.可見利用算法4的更新策略,可以保證最終的輸出種群為Pareto最優解集的子集,且其中的個體成員的ε-鄰域內都無其它個體,保證了均勻的分布性.值得注意的是,在輸出種群中可能存在一些個體,這里我們稱之為“臨近點”.它們位于Pareto前沿的邊緣,可以ε-支配一些雖然處在前沿面上但和它們不具有Pareto支配關系的個體.而當進化結束時,如果能夠支配這些“臨近點”的個體沒有生成,則它們將會保留到最終的輸出種群中.不過根據定理2可知,這些點的存在不會影響算法4的收斂性.實際上,它們仍可以看作當前種群中的Pareto最優解,因為一旦能夠支配它們的個體生成,它們將會從最終種群中移除.4.2at的終止條件結合算法4中的更新策略,EDMOEA的算法流程如下:1.隨機生成初始種群P(t),將其中的不可支配個體復制到第二種群A(t),并求出其在目標i上的極值點pi,i=1,2,…,m,并設置進化代數t=0.2.從A(t)中隨機選擇一個個體,設其為a.3.以pi和a作為父代,如果pi=a則更換其它的目標的極值個體pj,j≠i.對所選父代遺傳操作(交叉和變異),生成的子代個體設為q1,q2.4.比較q1,q2的支配關系,選擇非被支配的個體;如果兩者互為不可支配,則比較ε-支配關系.如果均不可行,則隨機選擇一個作為優勝者,然后利用算法4的更新策略,將其加入種群A(t)之中.5.如果不滿足終止條件,令t=t+1,從步2開始重新進化;否則,A(t)即為最終的輸出種群.顯然,EDMOEA算法可以分解為統一模型的特例.因為其選擇進行交配的個體都是當前種群中的非被支配個體即精英個體,故EDMOEA在進化過程中的精英強度將一直為1.0,為高精英強度進化算法.如文獻所述,在多目標進化算法中高精英參與比例有利于種群的收斂.由于父代個體之一pi(i=1,2,…,m)為所對應目標的當前極值,故若pi=a,則pj必不等于a,j≠i,除非精英種群中只有唯一的個體.所以這種策略可以避免對相同的個體進行遺傳操作.EDMOEA與ε-MOEA在算法結構尤其是精英種群的更新策略上有顯著的區別:首先,ε-MOEA根據ε的支配關系將目標函數空間中的點轉化為網格向量,這樣通常會導致一些在某一目標上的函數值是極端值的個體被支配,從而缺失于最終的輸出種群.如文獻所述,如果這些代表Pareto前沿邊界的個體被排除,精英種群所逼近的前沿面將會收縮,從而算法將收斂到部分的Pareto前沿面.但是采用算法4的更新策略,當前種群的極端個體將會保留到下一代,除非有可以支配它們的個體產生,而若其能夠支配具有極端值的個體,則必在對應目標上具有更好的邊界取值.其次,在網格向量的計算過程中,尤其在對實際問題的處理時,需要各個目標函數上可能取得的最小值的信息.雖然它們可以在算法進行過程中獲得,但當新的最小值產生后,需要對當前的精英種群中個體的網格向量值進行更新.這些都將增加計算量.采用EDMOEA的更新策略,只需要各個目標上的ε參數值,而且更新操作中僅需比較新個體與精英種群的支配關系,計算復雜度同種群大小呈線性關系.最后,如圖1所示,在ε-MOEA中,對于同一網格中個體的處理,無法保證相鄰網格的個體保持一致的分布.而根據算法4的更新策略,一旦個體在精英種群中確定,其的ε-鄰域內將不再有個體被包括在最終的種群中(如圖2所示).因此相比ε-MOEA,其將更有效地保持種群的多樣性.4.3自適應的調整根據上述討論可見,ε取值在基于ε-支配的進化算法中起關鍵作用.Laumanns曾給出ε的估值公式,并提出一種動態調整ε值以獲取給定規模的解集的方法.首先從一個最小的ε值開始,當精英種群中的個體數量超過事先給定的最大規模時,則按照某種規則增大ε取值.然而當新的ε值設定后,精英種群中個體的網格向量值需要更新,這需要額外的計算量.另一方面,當新的網格向量值取定后,精英種群內的個體需按照其新的網格向量坐標重新確定網格的支配關系,同樣將耗費額外的計算量.事實上,我們發現在EDMOEA算法中大的ε取值反而更有利于算法的收斂(見5.1節),故據此,我們提出一種自適應的ε調整方法如下.1.開始于一個最大的ε取值;2.如果滿足終止條件則終止調整策略,否則按照預先設定的下降幅度Δi,i=1,2,…,m,減少當前的ε取值,即如下式所示:εi←εi?Δi.εi←εi-Δi.顯然當從一個大的ε取值開始時,精英種群中現存個體的ε-支配關系不會因為ε值的降低而發生變化.因此沒有必要再對它們進行重新的比較.結合如文獻的終止法則,我們給出了如下的終止條件:(1)當適應值函數計算次數超過給定的最大上限(這里設為25000);(2)當在給定的一段連續的進化代數后,精英種群沒有新的個體出現.因為精英種群中新產生的個體將豐富當前Pareto前沿的多樣性或者將其朝向真實的Pareto前沿逼近.(3)當在給定的一段連續的進化代數后,精英種群中的極端個體的目標函數值沒有變化.精英種群中的極端值的變化在一定程度上也反應了種群的收斂性.于是同上一個終止法則相結合,如果它們都在給定的計算次數后保持不變,則表明深度搜索已經充分進行,需要降低ε的取值開始進行當前Pareto前沿的廣度搜索.這樣可以增加依靠當前Pareto前沿的多樣性,引導搜索朝向真正的Pareto前沿面推進.(4)當ε的值達到其的底線.可見這種自適應的調整策略類似于模擬退火的思路,當按照既定的判斷標準,種群進化沒有進展時,則按照如上的調整公式,降低ε在各個目標函數上的限制范圍,從而促使種群的進化.注意到第2和第3個終止法則中有一個重要的參數即給定的一段連續進化代數,本文中我們將其設置為200.同時設定最大的ε取值為0.06,最小的為0.0006.5edoa的多目標進化在本節中,計算實驗采用了多目標進化算法測試中被廣泛應用的5個多目標函數,這些函數包括雙目標函數,具有凸性、多模態等不同特性.首先討論了在不同ε取值下的EDMOEA的性能,然后通過其它通用多目標進化算法,如NSGAII、SPEA2、ε-MOEA等,進行比較分析,表明了EDMOEA和AEDMOEA的優越性.5.1近似種群的值及最小值首先,分別采用5個不同的ε值0.0006,0.006,0.06,0.6,0.9(這里我們認為在各個目標上的ε取值一致且算法進化種群大小為100,進行25000次適應值評價),結果表明當ε為較大的取值,EDMOEA可以更好地收斂到Pareto前沿曲面.采用當代距離指標(GeneralDistance,GD)包括的GD-Max和GD-Min兩種性能指標,評測最終種群同Pareto前沿面的接近程度.它們各自表示最終近似種群中的個體到Pareto前沿面的距離的最大值和最小值.實驗結果如表1和表2所示.如表1和表2所示,隨著參數ε值的增大,EDMOEA在各個問題上的GD-Max和GD-Min的取值呈先減小后增大趨勢,表中加粗部分即是各自變化的轉折點.對于ZDT1,ZDT2,ZDT3問題,當ε增至0.06時GD-Min顯著減小,表明種群中已有個體充分接近真實Pareto前沿.對于ZDT4問題,盡管當ε取得0.0006時,GD-Min最小,但當ε增至0.06時,GD-Max值最小,即整體收斂性在ε=0.06時最好.當ε=0.06時,ZDT6問題的GD-Max顯著減小,在ε=0.6時達到最小,而后其GD-Min隨ε增大呈小幅下降,當ε=0.6時最小.需要注意的是,當ε取值過大時,最終收斂種群的規模有限(表3可見),例如當ε=0.6,0.9時,最終種群中只有兩個個體在Pareto前沿兩端,即各個目標函數的極值點.所以盡管這樣得到的GD-Max和GD-Min值很小,但這十分不利于決策者做出最好的選擇.事實上,在進化算法的搜索過程中,深度搜索和廣度搜索是相互交叉進行的.當選擇大的ε取值的時候,EDMOEA偏重于深度搜索即引導搜索朝向真實的Pareto前沿面,而當采用小的ε取值時,EDMOEA則在當前的Pareto前沿面進行搜索而取得更好的分布性.故我們推薦從較大的ε取值開始,如ε=0.06,直至減少到最小的ε值.5.2函數和函數在本節中,EDMOEA、采用自適應ε調整策略的AEDMOEA、NSGAII、ε-MOEA、SPEA2等,均用于求解5個測試函數,并針對收斂性、分布性及計算效率對各個算法進行比較分析.具體的設置如下:所有初始種群中個體的基因都是隨機產生且采用實數編碼.交叉操作采用仿二進制交叉算子(SimulatedBinaryCrossover),變異操作采用多項式變異算子(PolynomialMutation),其中的交叉算子參數ηc=15,變異算子參數ηm=20.對于EDMOEA算法,在5個測試函數上都設置相同的ε參數,εi=0.006(i=1,2).SPEA2算法的k-近鄰參數k計算方法如下:k=N+Nˉˉˉ???????√(Nk=Ν+Νˉ(Ν表示種群,NˉˉˉΝˉ表示精英種群大小).AEDMOEA,EDMOEA和ε-MOEA都采用穩態的進化策略,且適應值評價的最大次數為25000.所有算法的其它共有參數設置如表4所示.為了比較5個算法的性能,采用一元評價指標函數.所謂一元評價指標函數是從向量集合到實數集的映射:I:Ω→R.利用實數集合上的全序關系,可以比較在Ω空間中的不同向量集合之間的質量.不同的一元指標函數采用了不同的偏好信息.對于給定的集合A,定義I(A)=I(A,R),計算A與參考集合R的指標函數值,其值越小,表明所用集合的質量越高.我們采用比較常用的兩個指標函數:Hypervolume指標函數(記為IH)和Epsilon指標函數(采用加的形式)(記作Iε).因為兩個指標函數采用了不同的偏好信息,若對于相同的比較集合A和B,它們指標值的序關系分別為IH(A)<IH(B)和Iε(A)>Iε(B),則可以推斷這兩個集合是等價的.其中,參照集合R構造如下:聯合5個算法在運行中所產生的最終近似種群,然后去除其中被支配的和重復的個體.這樣,參照集合R中的個體即不被任何聯合種群中個體所支配.實驗結果如表5～表9所示.ZDT1問題是檢測算法尋找具有凸性的Pareto最優解集的能力,如表5所示.AEDMOEA在Hypervolume和Epsilon指標上各自取得最小值而EDMOEA取得次小值,NSGAII所得到的近似集合質量最低.ZDT2問題是檢測算法對于非凸性Pareto最優解集的處理能力,AEDMOEA最優,ε-MOEA次之,而NSGAII表現最差.ZDT3