NSGA-II多目标優化算法講解（附MATLAB代碼）

小編今天為大家講解NSGA-II多目标優化算法，提到多目标優化，大家可能第一個就想到NSGA-II算法，今天小編就帶領大家解開NSGA-II的神秘面紗。

NSGA-II全稱是快速非支配排序遺傳算法，這個算法的精髓展現在“快速非支配排序”這7個字上，那麼究竟什麼是“快速非支配排序”，NSGA-II是如何實作“快速非支配排序”的呢？各位先别急，且聽小編慢慢道來，在​​基于粒子群算法的多目标搜尋算法講解（附MATLAB代碼）​​中，已經講到，多目标優化問題沒有一個所謂的最優解，而是存在一個最優解集。

為了讓大家更深入了解NSGA-II算法，小編查閱網上各種大神講解的資料，終于在知乎上發現一位大神講解地特别到位，這位大神在知乎上回答的連結如下：

​​https://www.zhihu.com/question/26990498/answer/35644566​​

小編覺得這位大神在講解NSGA-II時，真的講得太nice了,是以小編決定做一次大自然的搬運工，把這位大神的回答搬運過來。小編建議各位邊看代碼邊體會下面的步驟，效果會更好。

NSGA-II在正常遺傳算法上的改進，關鍵步驟就3步。

1）快速非支配排序算子的設計

多目标優化問題的設計關鍵在于求取Pareto最優解集。NSGA-II算法中的快速非支配排序是根據個體的非劣解水準對種群分層，其作用是指引搜尋向Pareto最優解集方向進行。它是一個循環的适應值分級過程：首先找出群體中非支配解集，記為第一非支配層F，将其所有個體賦予非支配序值irank=1(其中irank是個體i的非支配排序值)，并從整個種群中除去；然後繼續找出餘下群體中非支配解集，記為第二非支配排序層F2，個體被賦予非支配序值irank=2；照此進行下去，直到整個種群被分層，同一分層内的個體具有相同的非支配序值irank。

2）個體擁擠距離算子設計

為了能夠在具有相同irank的個體内進行選擇性排序，NSGA-II提出了個體擁擠距離的概念。個體i的擁擠距離是目标空間上與i相鄰的2個個體i+1和i-1之間的距離，其計算步驟為：

a)對同層的個體初始化距離。令L[i]d=0（其中L[i]d表示任意個體i的擁擠距離）；

b)對同層的個體按第m個目标函數值升序排列；

c)使得排序邊緣上的個體具有選擇優勢。給定一個大數M，令L[1]d=L[end]d=M；

d)對排序中間的個體，求擁擠距離：

（其中：L[i+1]m為第i+1個個體的第m目标函數值，

和

分别為集合中第m目标函數值的最大值和最小值）

e)對不同的目标函數，重複步驟a)~步驟d)操作，得到個體i的擁擠距離L[i]d，通過優先選擇擁擠距離較大的個體，可使計算結果在目标空間比較均勻分布，以維持種群的多樣性。

3）精英政策選擇算子

精英政策即保留父代中的優良個體直接進入子代，以防止獲得的Pareto最優解丢失。精英政策選擇算子按3個名額對由父代Ci和子代Di合成的種群Ri進行優選，以組成新的父代種群Ci+1。首先淘汰父代中方案校驗标志為不可行的方案；其次按照非支配序值irank從低到高排序，将整層種群依次放入Ci+1，直到放入某一層Fj時出現Ci+1大小超過種群規模限制N的情況；最後，依據Fj中的個體擁擠距離由大到小的順序繼續填充Ci+1直到種群數量達到N時終止。

下面這個圖檔能很好的說明NSGA-II的實作過程

最後附上用NSGA-II求解ZDT1函數的MATLAB代碼，ZDT1函數如下：

代碼來源：​​http://www.omegaxyz.com/2017/05/04/nsga2matlabzdt1/​​

代碼連結（背景回複“NSGA”提取代碼）：https://pan.baidu.com/s/1EBUxjF8J262jTScKzIbD2w 

提取碼：fk4j