NSGAII基于非支配排序的多目標(biāo)優(yōu)化算法(中文翻譯)

1、-word資料-基于非支配排序的帶有精英策略的多目標(biāo)優(yōu)化算法：NSGA-II摘要：使用非支配排序和共享變量方法的多目標(biāo)進(jìn)化算法近年來因為它的一些缺陷指責(zé)，主要是由于這種算法的計算復(fù)雜度較高，達(dá)到了0（mn3）（其中m表示多目標(biāo)優(yōu)化中目標(biāo)的數(shù)量，n表示種群的大小），（ii）缺少精英策略，（iii）需要人為指定共享變量。在本文中，提出了一種基于多目標(biāo)進(jìn)化算法的非支配排序方法（我們將它稱為非支配排序GA-II算法或者NSGA-II算法）。選擇操作通過把父代和子代混合在一個交配庫中，從中選擇最優(yōu)的N個個體（根據(jù)適應(yīng)度層級和擁擠度進(jìn)行優(yōu)劣排序）。通過5個復(fù)雜的測試函數(shù)進(jìn)行測試得出的模擬結(jié)果表明，本文所提

2、及的NSGA-II算法，在解決大部分問題是，比PAES和SPEA算法（另外兩種具有精英策略的多目標(biāo)遺傳算法，這兩種算法在的優(yōu)勢在于創(chuàng)造多樣的Pareto最優(yōu)層級）具有更好的分布，并且它的收斂性更接近實際中的Pareto最優(yōu)層級。因為NSGA-II算法具有較低的計算復(fù)雜度，帶有精英策略和較少的共享參數(shù)參數(shù)5NSGA-II算法在最近幾年內(nèi)將應(yīng)用在更多的領(lǐng)域。1、介紹在過去的十多年中，人們提出了大量的多目標(biāo)進(jìn)化算法（MOEAs）。主要原因是它們在一次運(yùn)行中找尋多值Pareto最優(yōu)解的能力。一個問題有多個最優(yōu)解的主要原因是不可能同時優(yōu)化多個對象時找到一個單獨(dú)的最優(yōu)解，所以一個能給出大量可供選擇的最優(yōu)解

3、集的算法才是具有實際價值的。由Srinivas和Deb教授提出的非支配排序遺傳算法（NSGA）曾經(jīng)是其中第一個這樣的進(jìn)化算法。多年以來，對NSGA算法主要的批評如下：（1）.進(jìn)行非支配排序時的計算復(fù)雜度高：NSGA進(jìn)行非支配排序時的計算復(fù)雜度是O（mN3）（m為優(yōu)化對象的個數(shù)，N為種群大?。?，一旦當(dāng)種群較大時，計算十分復(fù)雜，尤其是種群需要在每一代都進(jìn)行非支配排序。（2）缺少精英策略：最近一些實驗的結(jié)果表明，精英策略在相當(dāng)程度上能夠加速遺傳算法的執(zhí)行。而且一旦滿意解被找到，它也能防止這些滿意解的丟失。（3）.需要指定共享參數(shù):傳統(tǒng)的為了保證一個種群中的多樣性，從而得到具有share廣泛多樣性的等

4、價解的方法主要依賴于共享的概念。而這種方法的主要問題是它需要指定共享參數(shù)，盡管已經(jīng)有一些方法能夠動態(tài)的指定共享參數(shù)，但一個不需要共享參數(shù)的保share持多樣性的方法才是最需要的。在本文中，我們解決了所有的這些問題，提出了一個更加優(yōu)秀的NSGA版本，我們將它稱為NSGA-II算法。從對很多測試函數(shù)測試得出的仿真結(jié)果來看，NSGA-II算法總的來說是優(yōu)于PAEs算法和SPEA算法另外兩種帶有精英策略的多目標(biāo)進(jìn)化算法（依據(jù)聚合在Pareto最優(yōu)邊界和在獲得的解集中保持多樣性），這些測試結(jié)果激勵我們把NSGA-II應(yīng)用在一些更復(fù)雜的應(yīng)用和解決一些現(xiàn)實世界中的多目標(biāo)優(yōu)化問題。2、帶有精英策略的多目標(biāo)進(jìn)化

5、算法Zitzler，Deb和Theile教授通過研究發(fā)現(xiàn)，在多目標(biāo)進(jìn)化算法中精英策略能夠幫助獲得更好的收斂邊界。在所有提出的帶有精英策略多目標(biāo)進(jìn)化算法中，Zitzler和Thiele教授提出的SPEA算法，Knowles和Gome教授提出的PAEs算法以及Rudolph教授提出的精英遺傳算法(elitistGA)是最廣為人知的Zitzler和Thiele教授在它們的非支配排序中提出了多重標(biāo)準(zhǔn)精英策略的概念。他們表示如果在每一代的排序過程中，保持外部種群，那么從初始種群開始所有的非支配解都能被發(fā)現(xiàn)。這些外部種群參加遺傳操作。每一代，都有一個具有外圍的合并的種群，這個種群是第一個被構(gòu)造的。在合并種

6、群中的所有的非支配解都被根據(jù)它們支配解的數(shù)量分配了一個適應(yīng)度，所有的支配解則被分配了一個比所有非支配解都差的適應(yīng)度。這種適應(yīng)度的安排保證了直接在非支配解中尋找最優(yōu)解集。一種決定性的聚集技術(shù)被用來保證非支配解的多樣性。盡管實施表明計算復(fù)雜度是0(MN)，但通過簿記，SPEAs的計算復(fù)雜度可以降低到0(MN2)。Knowles和Corne教授提出了另外一種簡單的使用進(jìn)化策略的多目標(biāo)進(jìn)化算法，這種算法，種群具有一個父代和一個子代，父代和子代進(jìn)行比較，如果子代支配父代，那么子代就作為下一個父代，如果父代支配子代，那么子代就被拋棄，一個突變的解(新的子代)加入。然而，如果子代和父代相互之間沒有支配關(guān)系，

7、則通過比較它們和所有已經(jīng)發(fā)現(xiàn)的最優(yōu)解，如果子代被發(fā)現(xiàn)支配最優(yōu)解中的任何一個解，則子代被接受為新的父代，而被支配的最優(yōu)解則從最優(yōu)解集中刪除。如果子代不支配任何最優(yōu)解，那么檢查父代和子代與最優(yōu)解集的接近程度，如果子代存在于一個共享參數(shù)不密集的區(qū)域，則它被接受為新的父代加入到最優(yōu)解集中。這種算法的最差計算復(fù)雜度為0(aMN)，a表示最優(yōu)解集的大小，由于最優(yōu)解集通常是和種群大小N成比例的，所以這種算法總的計算復(fù)雜度是0(MN2)Rudolph教授提出的一個簡單的通過系統(tǒng)的比較父代個體和后代的種群多目標(biāo)優(yōu)化算法。后代種群中的非支配解和父代種群中的非支配解組成一個總的非支配解集，在下一次循環(huán)中，這個非支配

8、解集成為新的父代，如果這個集合沒有需要得到的種群大小大，其他獨(dú)立的后代繼續(xù)被加入。通過這種策略，能夠證明Pareto最優(yōu)邊界。雖然這種算法比較優(yōu)秀，但它缺少解決第二個問題，保持解集多樣性的辦法。3、帶有精英策略的非支配排序遺傳算法(NSGA-II)非支配排序遺傳算法由Srinivas和Deb教授在1994提出，由于它的一些前面提及的問題遭到了批評。在這一節(jié)中，我們提出了NSGA-II算法，減輕了這些困難。接下來我們將分幾個板塊介紹NSGA-II算法。3.1.快速非支配排序方法為了對大小為N的種群根據(jù)非支配層級進(jìn)行排序，每一個解必須和種群中的其他解都進(jìn)行比較，從而得出它是否被支配，這需要O(MN

9、)的計算復(fù)雜度，M是優(yōu)化對象的數(shù)量。當(dāng)這一步驟進(jìn)行完畢后，繼續(xù)找出所有第一個非支配層級的個體，總的計算復(fù)雜度是0(MN2)在這一步中，所有在第一個非支配層級的個體都被找到。為了找出下一個支配層級的個體，屬于第一個非支配層級的個體暫時不被計入，繼續(xù)進(jìn)行前面的操作，重復(fù)如上操作一直到找到后來的所有非支配層級上的個體?？梢钥吹阶畈畹那闆r下(每一個層級上只有一個個體)，在沒有任何簿記的情況下，計算復(fù)雜度是0(MN3)。而下面將介紹的快速非支配排序則在最差情況下，計算復(fù)雜度是0(MN2)。這個方法與上面介紹的方法大部分是相類似的，但它有更好的簿記策略。所有種群中的解與一個部分填滿的種群比較支配關(guān)系。開始

10、時，先將第一個解加入集合P，其后P種群中的其它解都和P集合中的解比較，如果P集合中的任何個體支配P中的任何個體q，此時將P集合中的個體q移除。通過這種方法，所有的非支配個體都被保留。否則，如果個體p被P中的所有個體支配，則不將P包含進(jìn)P中。fast-nondominant-sort(Rt)P=1/將第一個成員加入到P中foreachpeP人pe/P/每次選擇一個不在P中的pP=PUp/將p臨時性的包含值P中foreachqeP人qe/P/將p與P中的其它成員比較ifpq,thenP=Pq/如果支配P中的任何一個成員則刪除P中的該成員qelseifqp,then=Pp/如果p被P中的所有成員支配

11、則不將p包含在P中為了找到其他非支配層級，P中的成員將不被再次計入，再重復(fù)上面的循環(huán)操作。我們發(fā)現(xiàn)，第二個個體只需要和P中的一個個體進(jìn)行比較，第三個個體則需要與兩個個體進(jìn)行比較，在最壞的情況下，即當(dāng)P中的所有個體均為非支配個體時，比較的總次數(shù)為：N2/2。所以算法的時間復(fù)雜度均為0(N2)。3.2擁擠度計算為了計算每個解周圍的其它解的分布情況，我們得出該個體周圍只包含個體本身的區(qū)域的最大長方形的長的平均長度(我們稱之為擁擠度)。如圖1所示。crowding-distance-assignment(Fi)l=|1|/個體的個數(shù)為Iforeachi,setIidistance=0/初始化所有的擁擠

12、度值為0foreachobjectivemI=sort(I,m)/基于每個目標(biāo)函數(shù)對種群進(jìn)行排序lldistanee=lidistanee=g/令兩個邊界個體的擁擠度為無窮fori=2to(l1)/對于其他的個體lidistanee=iidistanee+(li+1.m-li-1.m)/計算每個個體的擁擠度3.3擁擠度比較算子定義擁擠度算子用符號(n)來表示，該種群中的每個個體都擁有如下兩個屬性：1.非支配排序?qū)蛹?i)rank2.擁擠度(i)distance可以定義擁擠度算子如下：ij表示(ijnrankrankrankrankdistancedistance此算子的含義是，當(dāng)兩個解，屬于不

13、同的非支配排序的層級時，選擇非支配層級較低的解，當(dāng)兩個解屬于同一個非支配層級的時候，選擇擁擠度較大的解，即此解周圍的個體較少，所在區(qū)域解的分布較為稀疏。3.4主流程開始時，創(chuàng)建一個隨機(jī)的父代種群P0，種群進(jìn)行快速非支配排序，每一個解都被分配一個和非支配層級(1是最優(yōu)層級)相應(yīng)的適應(yīng)度值。因此，最小的適應(yīng)度值是假定的。然后進(jìn)行二進(jìn)制錦標(biāo)賽選擇，重新組合，變異算子用來創(chuàng)造新的大小為N的子代種群Q0。從第一代開始，進(jìn)行的步驟是不同的：Rt=PtUQt/將父代種群和子代種群合并F=fast-nondominant-sort(Rt)F=(F1,.F2,.)/將合并后的種群進(jìn)行非支配排序Pt+i=空集/初

14、始化Pt+1父代種群until|Pt+i|N/直到Pt+1父代種群填滿，進(jìn)行下列的循環(huán)crowding-distance-assignment(Fi)/計算第i層級上的所有個體的擁擠度Pt+1=Pt+1UFi/將第i層級中的個體并入Pt+1父代種群中i=i+1Sort(Pt+1,n)/當(dāng)父代種群填滿之后對父代種群Pt+1按照擁擠度算子排序Pt+1=Pt+10:N/選出Pt+1中前N個個體Qt+i=make-new-pop(Pt+i)/對Pt+1中的個體進(jìn)行交叉，選擇，變異的遺傳算法產(chǎn)生新的子代子群Qt+1t=t+1/繼續(xù)重復(fù)如上操作4、結(jié)果我們將NSGA-II算法與PAEs算法在相同的測試函數(shù)

15、下進(jìn)行了比較，測試函數(shù)如下：MOP2：f(x)二1-exp1)f(x)=1-exp-4x,x,x4123MOP3：f(x)=1+(A-B+(A-B11122f(x)=l+3+(y+12其中A】=0.5sin1一2cos1+sin2一1.5cos2A=1.5sin1一cosl+2sin2一0.5cos22B=0.5sinx一2cos1x+siny一1.5cosyB=1.5sinx一cosx+2siny一0.5cosyMOP4：(x)=1-10exp02px2+x2f(x)=冰|0-8+5sin(x)2ii=1i=1、0 x11TC4：?(x)=x11(x)=g1-2一5x,.,x5210其中g(shù)(

16、x)=91+蘭(x2-i10cos(4兀x)ii=2TC6：0 x1i=1,.,10iG)=1-exp(-4x)sin6(6兀x)111f2(x)=gI1-其中g(shù)(x)=1+9丈。x/9IiJ、0.25丿由于解集的多樣性是多目標(biāo)優(yōu)化的重要指標(biāo)，我們設(shè)計了兩種方法：一種是基于連續(xù)距離另外一種是基于平均距離。獲得的階級的第一個非支配層級和一個一致分布相比較，得到它的偏差如下：為了保證這個計算把解在整個分布的擴(kuò)散性，我們包含了非支配層級的邊界，F(xiàn)1-對于離散的Pareto最優(yōu)邊界，我們計算每一個離散區(qū)域的加權(quán)平均數(shù)。Di是歐幾里德距離。參數(shù)d是這些距離的平均值。1、表一比較了通過NSGA-II，PA

17、ES和SPEA三種算法得出A的平均值和方差的區(qū)別AIgonthtnMOP2MOP3MOP4TC4W6NSGAJIPALSSFEA1.6090.74000(賈用圳a.006710/00748044sL3410.8000.00()430.00495Q.005080.W1W0.733.001640.00&87O.3.S3IMft1-67Q.O0W99(1.05723hCKKXX)b.365|0JJ6l31.1950.051510,04C.Q1422、表二比較了通過NSGA-II，PAES和SPEA三種算法得出到真實的Pareto最優(yōu)邊界的距離和它的標(biāo)準(zhǔn)偏差A(yù)hTomhinM0P2MOF3TC4IC$NSGA-I0.0019o,anom0.0151o.txwo0.42500.00004451284.553860+06110,00056PAESOJ7040.0000211.331512.13053c.to恥0.CJ0540,58460,53590.JW0.00122SPEA0J2570.00004O.OOOOS).000057.34036.572520.2211O.OOQ4-53、通過比較M0P4測試函數(shù)得到的Pareto最優(yōu)邊界圖形可以看出，NSGA-II得出更好，更清晰的分布。如圖2和圖3所示。Fig.3.AJan-donunitedgolutionsbiaifitdm-i叱P