怎么進行NSGA-II多目標優化算法的分析

這篇文章給大家介紹怎么進行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函數如下：

關于怎么進行NSGA-II多目標優化算法的分析就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。