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

韓蕊

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

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

一、NSGA-II概況

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

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

二、NSGA-II操作步驟

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

2.初始種群是根據非支配排序?？焖倥判蛩惴ㄈ缦拢?/p>

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

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

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

該算法優于原NSGA算法，由于它利用了關于個人支配的集合（Sp）和受個體支配的個體數目（np）。

3.擁擠距離

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

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

（1）初始化所有個體的距離為零，即Fi（dj）=0，其中j對應于前線Fi中的Jth個體。（2）對于每個目標函數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個目標函數的值。

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

4.選擇

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

5.遺傳算子

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

（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是從具有密度的隨機數生成的樣本。

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

?>1

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

（2）多項式突變。

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

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

6.重組和選擇。

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

三、結語

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

參考文獻：

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