一種快速精英化多目標遺傳算法：NSGA—Ⅱ

韓蕊

【摘要】NSGA是一種流行的基于非支配的遺傳算法，用于多目標優(yōu)化。是一種非常有效的算法，但由于其計算復雜度低、缺乏精英性以及需要預先確定共享參數(shù)σshare而被詬病。NSGA-II提出了一種更好的排序算法，該算法采用了精英主義，不需要選擇共享參數(shù)。

【中圖分類號】TP18 【文獻標識碼】A 【文章編號】2095-3089（2018）03-0025-02

一、NSGA-II概況

種群按照通常的方式被初始化。初始化了的種群基于非支配進入種群進行排序，并被分配適應度值，同時還定義了一個新的參數(shù)：擁擠距離。擁擠距離是衡量一個個體到另一個個體之間距離，值越大種群的多樣性越好。

通過基于等級和擁擠距離的二元競爭選擇，從群體中選擇父輩。所選種群從交叉和變異算子中生成子代。對具有當前種群和當前種群子代的種群進行再排序，根據(jù)非支配原則，只選擇最佳的N個個體，其中N是種群的大小。選擇的依據(jù)是等級和最后一條線上的擁擠距離。

二、NSGA-II操作步驟

1.初始化種群。根據(jù)問題范圍和約束初始化種群。

2.初始種群是根據(jù)非支配排序。快速排序算法如下：

對于主種群P中的每個個體p，執(zhí)行以下操作：1.初始化Sp=?；此集合將包含所有被p支配的個體。2.初始化np=0。這將是支配p的個體數(shù)量。3.對于種群P中的每個個體q。If p支配q，則：增加q到Sp集合中，即Sp=Sp∪{q}；Or if q支配p，則增加p的控制計數(shù)器，即np=np+1。4.如果np=0，即沒有個體支配p，則p屬于第一前沿，則單個p的集合非劣等級為1，即prank=1。更新第一前沿的集合通過添加p到前沿，即F1=F1∪{P}。

這是針對主種群中每一個個體運行的。將前面的計數(shù)器初始化為1。即i=1。在第i前沿為非空的情況下進行如下操作，即Fi≠ ?；

1.Q= ?；用于存儲第（i+1）線的個體的集合。2.對于Fi前沿的每一個個體p，對于Sp中的每個個體q?！猲q=nq-1，減少個體的支配數(shù)?！鬾q=0，那么在隨后的前沿將支配q，因此設(shè)置qrank=i+1。更新Q用具有個體q的集q，即Q=Q∪q。3.把前面的前沿增大一個。集合Q是下一個前線，因此Fi=Q。

該算法優(yōu)于原NSGA算法，由于它利用了關(guān)于個人支配的集合（Sp）和受個體支配的個體數(shù)目（np）。

3.擁擠距離

一旦非支配排序完成，擁擠距離就會被分配。由于個體是根據(jù)等級和擁擠距離來選擇的，種群中的所有個體都被分配了一個擁擠距離值。計算如下：

對于每一個前線Fi，n是個體的數(shù)量。

（1）初始化所有個體的距離為零，即Fi（dj）=0，其中j對應于前線Fi中的Jth個體。（2）對于每個目標函數(shù)m?；谀繕薽，對前沿個體進行排序，即I=sort（Fi；m）；給Fi中每一個個體分配無限大的邊界值。即I（d1）= ∞，I（dn）= ∞；for k = 2 to （n +1）

I（dk）= I（dk）+（ I（k + 1）·m -I（k -1）· m）/（fmmax-fmmin）

其中，I（k ）· m是I中第k個個體在第m個目標函數(shù)的值。

擁擠距離的基本思想是基于m維的m個目標在前線中的每個個體之間的相互關(guān)系。邊界中的個體總是被選中的，因為他們影響距離分配。

4.選擇

一旦這些個體根據(jù)非支配和在指定擁擠距離的情況下，選擇使用一個擁擠比較運算符（fi（Dq），即擁擠距離應該更遠。個體是通過使用二元競賽選擇和比較運算符來選擇的。

5.遺傳算子

實數(shù)編碼遺傳算法使用模擬二進制交叉、交叉算子和多項式變異算子。

（1）模擬二元交叉。模擬二元交叉是模擬自然界中的交叉，如下所示。

c1，k =1/2[（1 +?k）p1，k + （1 + ?k）p，k]

c2，k =1/2[（1 + ?k）p1，k + （1+?k）p2，k]

其中ci，k是kth分量的第一個子代；Pi，k是選擇的父代；?k是從具有密度的隨機數(shù)生成的樣本。

p（?）=1/2（ηc+ 1）?ηc 0< ?≤1

?>1

該分布可以從（0，1）之間的均勻采樣的隨機數(shù)獲得。ηc是交叉的分布指標。

（2）多項式突變。

其中，ck是子代，Pk是父代，pku是父代種群的上邊界，pkl是父代種群的下界。δk是由多項式分布計算的小變差。

rk是（0，1）之間的一個均勻抽樣隨機數(shù)。ηm是變異分布指數(shù)。

6.重組和選擇。

重組是當前遺傳種群和子代進行重組；選擇是形成下一代種群個體的集合。因為以前和現(xiàn)在最好的個體組成新種群，精英主義得到了保證。種群現(xiàn)在是根據(jù)非支配排序。如果通過添加所有的個體在Fj前面，種群超過N，然后選擇前面Fj中的個體。它們的擁擠距離是遞減的，直到種群規(guī)模達到N。因此，這個過程會重復產(chǎn)生后代。

三、結(jié)語

NSGA-II由于其新的基于分級的快速非支配解排序方法將計算復雜度降低；該算法提出了擁擠距離的概念，采用擁擠距離比較算子代替NSGA中的適值度共享方法，時間復雜度降低；同時引入了精英保留機制，經(jīng)選擇后參加繁殖的個體所產(chǎn)生的后代與其父代個體共同競爭來產(chǎn)生下一代種群，有利于提高種群的整體進化水平。因此NSGA-II得到了廣泛應用。

參考文獻：

[1]Kalyanmoy Deb and R.B.Agarwal.Simulated Binary Crossover for Continuous Search Space.Complex Systems，9：115- 148，April 1995.