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

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

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

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

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

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

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

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

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

10、個(gè)解加入集合P，其后P種群中的其它解都和P集合中的解比較，如果P集合中的任何個(gè)體支配P中的任何個(gè)體q，此時(shí)將P集合中的個(gè)體q移除。通過這種方法，所有的非支配個(gè)體都被保留。否則，如果個(gè)體p被P中的所有個(gè)體支配，則不將p包含進(jìn)P中。fast-nondominant-sort(Rt)P = 1 /將第一個(gè)成員加入到P中for each pP p/ P /每次選擇一個(gè)不在P中的pP = P U p /將p臨時(shí)性的包含值P中for each qP q/ P /將p與P中的其它成員比較if pq, then P = P q /如果支配 P 中的任何一個(gè)成員 則刪除P 中的該成員qelse if qp, t

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

12、Ifor each i, set Iidistance = 0 /初始化所有的擁擠度值為0for each objective m I = sort(I, m) /基于每個(gè)目標(biāo)函數(shù)對(duì)種群進(jìn)行排序Ildistance = Iidistance = /令兩個(gè)邊界個(gè)體的擁擠度為無窮for i = 2 to (l 1) /對(duì)于其他的個(gè)體Iidistance = iidistance + (Ii+1.m Ii-1.m) /計(jì)算每個(gè)個(gè)體的擁擠度3.3 擁擠度比較算子定義擁擠度算子 用符號(hào)（）來表示，該種群中的每個(gè)個(gè)體都擁有如下兩個(gè)屬性：1. 非支配排序?qū)蛹?jí) ()2. 擁擠度 ()可以定義擁擠度算子如下：i

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

14、, .F2,.) /將合并后的種群進(jìn)行非支配排序Pt+i = 空集 /初始化 Pt+1 父代種群until |Pt+i | N /直到Pt+1父代種群填滿，進(jìn)行下列的循環(huán)crowding-distance-assignment（Fi) /計(jì)算第i層級(jí)上的所有個(gè)體的擁擠度Pt+1 = Pt+1 Fi /將第i層級(jí)中的個(gè)體并入Pt+1父代種群中i= i+1Sort(Pt+1, n) /當(dāng)父代種群填滿之后 對(duì)父代種群Pt+1 按照擁擠度算子排序Pt+1 = Pt+1 0 : N /選出Pt+1中前N個(gè)個(gè)體Qt+i = make-new-pop (Pt+i) /對(duì)Pt+1中的個(gè)體進(jìn)行交叉，選擇，變異的

15、遺傳算法產(chǎn)生新的子代子群Qt+1t = t + 1 /繼續(xù)重復(fù)如上操作4、結(jié)果我們將NSGA-II算法與PAEs算法在相同的測(cè)試函數(shù)下進(jìn)行了比較，測(cè)試函數(shù)如下：MOP2： （1） MOP3：其中MOP4：TC4： 其中TC6： 其中由于解集的多樣性是多目標(biāo)優(yōu)化的重要指標(biāo)，我們?cè)O(shè)計(jì)了兩種方法：一種是基于連續(xù)距離另外一種是基于平均距離。獲得的階級(jí)的第一個(gè)非支配層級(jí)和一個(gè)一致分布相比較，得到它的偏差如下：為了保證這個(gè)計(jì)算把解在整個(gè)分布的擴(kuò)散性，我們包含了非支配層級(jí)的邊界，F(xiàn)1-對(duì)于離散的Pareto最優(yōu)邊界，我們計(jì)算每一個(gè)離散區(qū)域的加權(quán)平均數(shù)。Di是歐幾里德距離。參數(shù)d是這些距離的平均值。1、表一比較了通過NSGA-II，PAES和SPEA三種算法得出的平均值和方差的區(qū)別2、表二比較了通過NSGA-II，PAES和SPEA三種算法得出到真實(shí)的Pareto最優(yōu)邊界的距離和它的標(biāo)準(zhǔn)偏差3、通過比較MOP4測(cè)試函數(shù)得到的Pareto最優(yōu)邊界圖形可以