## 1 引言

在文獻(xiàn)[1]中，作者提出了一種基于非支配排序的多目標(biāo)進(jìn)化算法(MOEA)，稱為非支配排序遺傳算法 II (NSGA-II)，它緩解了進(jìn)化算法以下三個困難：

• 1. 時間復(fù)雜度為$O(MN^3)$，其中$M$為求解目標(biāo)數(shù)，$N$為種群數(shù)目
  

• 2. 非精英主義方法

• 3. 需要指定共享參數(shù)

具體來說，提出了一種計算復(fù)雜度為$O(MN^2)$的快速非支配排序方法。此外，還提出了一個選擇算子，它通過結(jié)合父母和后代種群并選擇最佳（關(guān)于適應(yīng)度和傳播）解決方案來創(chuàng)建交配池。對困難測試問題的仿真結(jié)果表明，與 Pareto 歸檔進(jìn)化策略和強(qiáng)度 Pareto EA 相比，在大多數(shù)問題中，所提出的 NSGA-II 能夠在真正的 Pareto 最優(yōu)前沿附近找到更好的解分布和更好的收斂性——另外兩個精英 MOEAs 特別關(guān)注創(chuàng)造一個多樣化的帕累托最優(yōu)前沿。

原則上，一個問題中存在多個目標(biāo)會產(chǎn)生一組最優(yōu)解（主要是稱為帕累托最優(yōu)解），而不是單個最優(yōu)解。 在沒有任何進(jìn)一步信息的情況下，不能說這些帕累托最優(yōu)解中的一個比另一個更好。 這要求用戶找到盡可能多的帕累托最優(yōu)解。 經(jīng)典優(yōu)化方法（包括多準(zhǔn)則決策方法）建議通過一次強(qiáng)調(diào)一個特定的帕累托最優(yōu)解將多目標(biāo)優(yōu)化問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題。 當(dāng)這種方法用于尋找多個解決方案時，必須多次應(yīng)用，希望在每次模擬運行時找到不同的解決方案。

在過去幾十年中，已經(jīng)提出了許多多目標(biāo)進(jìn)化算法 (MOEA)。由于進(jìn)化算法 (EA) 與大量解決方案一起工作，因此可以擴(kuò)展一個簡單的 EA 以維護(hù)一組不同的解決方案。 強(qiáng)調(diào)向真正的帕累托最優(yōu)區(qū)域移動，EA 可用于在一次模擬運行中找到多個帕累托最優(yōu)解。

?N. Srinivas，Kalyanmoy Deb提出的非支配排序遺傳算法 (NSGA) 是最早的此類 EA 之一。 多年來，對 NSGA 方法的主要批評如下：

1. 非支配排序計算復(fù)雜度高：NSGA非支配排序算法的計算復(fù)雜度為$O(MN^3)$（其中$M$為目標(biāo)數(shù)，$N$為種群規(guī)模）。 這使得NSGA 對于大種群規(guī)模的計算成本很高。 之所以會出現(xiàn)這種大的復(fù)雜性，是因為每一代的非支配排序過程都涉及到復(fù)雜性。

2. 缺乏精英主義：最近的研究結(jié)果表明，精英主義可以顯著加快 GA 的性能，這也有助于防止一旦找到好的解決方案就丟失。

3. 需要指定共享參數(shù)$\delta_{share}$：確保種群多樣性以得到多種等效解決方案的傳統(tǒng)機(jī)制主要依賴于共享的概念。 共享的主要問題是它需要指定共享參數(shù)($\delta_{share}$)。

本文的NSGA-Ⅱ解決了所有這些問題。 從對許多困難測試問題的模擬結(jié)果來看，我們發(fā)現(xiàn) NSGA-II 在尋找多樣化集合方面優(yōu)于其他兩個當(dāng)代 MOEA：帕累托存檔進(jìn)化策略 (PAES)和強(qiáng)度帕累托 EA (SPEA)的解決方案，并在真正的帕累托最優(yōu)集附近收斂。

## 2 算法實現(xiàn)

## 3 參考文獻(xiàn)

[1] Deb K ,?Pratap A ,?Agarwal S , et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.

## 4 代碼免費獲取

https://mbd.pub/o/bread/mbd-Y52bl59v