NSGA-II

A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II中文翻譯

目錄

1. NSGA-II 簡介

2. NSGA-II 詳細介紹

3. NSGA-II 模拟結果

4. 參數設定問題

5. 限制處理方法

1. NSGA 簡介

NSGA-II适合應用于複雜的、多目标優化問題。是K-Deb教授于2002在論文：A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II，中提出。在論文中提出的NSGA-II解決了NSGA的主要缺陷，實作快速、準确的搜尋性能。NSGA的非支配排序的時間複雜度為 O(MN3) O ( M N 3 ) ，在種群規模N較大時排序的速度會很慢。NSGA-II使用帶精英政策的快速非支配排序，時間複雜度為 O(M(2N)2) O ( M ( 2 N ) 2 ) ，排序速度有大幅的提升。而且使用了精英政策，保證了找到的最優解不會被抛棄，提高了搜尋性能。另一方面NSGA使用共享函數來使解分布均勻，該函數依賴于共享參數 σshare σ s h a r e 的選擇，而且共享函數的複雜度高達 O(N2) O ( N 2 ) 。NSGA-II從新定義了擁擠距離來代替共享參數。

2. NSGA-II詳細介紹

一. 快速非支配排序

基于支配比較對種群快速非支配排序,排序分兩部分

• 将群體的的個體能支配的個體組成一個集合 Sp S p ，記錄個體被支配的個體數 np n p
• 将 np==0 n p == 0 的個體組成第一個前列集 F1 F 1 ，并給個體的等級rank指派為1。從 Fi F i 中取出每個個體，對該個體的 Sp S p 集合中的個體進行如下操作： 将 np n p 都減一，并判斷如果 np==0 n p == 0 則加入集合 Fi+1 F i + 1 中。

二.多樣性保護

• 1.擁擠距離（crowding distance）

  NSGA在使種群收斂到pareto-optimal-solutions的同時，使用共享參數來保持解能相對均勻分布，也就是盡量要保持解得多樣性。但是共享函數複雜度（O(n^2)）太高，這裡使用擁擠距離來代替共享參數。對兩個目标函數的擁擠距離如下圖

  

  擁擠距離等于解在各個目标函數的方向上的前後兩個解得距離和。在二維時就等于圖示矩形周長的一半。

  擁擠距離的僞代碼如下：

  

note : 如果某個方向上的距離很大，就會很大程度上影響總的距離的大小。為了使每個方向上的目标函數對擁擠距離有等效的影響力，需要每個目标函數上的距離要規則化normalized。

• 2.擁擠比較操作（crowded-comparison-operator)

  在選擇算子是基于非支配比較操作區選擇個體

  

• 3.NSAG-II的實作過程

  

  首先：對種群 Pt P t 執行選擇、交叉、變異操作，形成新種群 Qt Q t 。

  然後：合并這兩個種群并對合并後的種群執行非支配排序

  最後：根據個體rank形成的前列面 Fi F i ，從低到高依次加入下一代種群 Pt+1 P t + 1 ,當 Fi F i 加入使種群大小越界時，依據擁擠距離從大到小，将個體加入種群。

  we use a binary tournament selection operator on crowded_comparison operator

  

• 複雜度分析：worst case

  fast_nondominated_sort complexity: O(M(2N)2) O ( M ( 2 N ) 2 )

  crowding_distance_assign complexity: O(M(2N)log(2N)) O ( M ( 2 N ) l o g ( 2 N ) )

  sorting on nondominated_operator complexity: O((2N)log(2N)) O ( ( 2 N ) l o g ( 2 N ) ) (such as quick sort)

3.模拟結果

選擇合适參數設定進行測試，雖然不是最佳的參數設定，但是為了展現NSGA-II相比其他算法的優越性，應該是對各種問題表現都相對均衡的參數。參數設定如下

population size：250

probability for crossover：0.9

probability for mutation： 1nvariesor1nbits 1 n v a r i e s o r 1 n b i t s

distribution index for crossover and mutation: nc=20　nm=20 n c = 20 　 n m = 20

binary code ： single point crossover， bitwise mutation

real code : SBX , polynomial mutation

測試結果：

可見除了ZDT3 和ZDT6，NSGA-II性能都是最好的。

大多數情況下，浮點數編碼的NSGA-II比其他任何算法都有更好的解分布，包括二進制編碼的NSGA-II.

4.參數設定

隻是以進化次數和變異分布指數為例，簡單說明參數的影響，并不對最優參數設定做深入的研究。

增加進化次數到500 ：可以得到離最優解更近的收斂，和更均勻的解分布

減少變異分布指數： 可以使多項式變異産生變化更大的解

例如：ZDT4有很多局部最優解，為了跳出zdt4的局部最優解，自變量要有大變化才可能。這裡使用了更小的distribution index for mutation： nm=10 n m = 10 ，結果convergence metric 減小到0.02，diversity metric 減小到0.498

5.限制處理