關于NSGA—II算法的研究

高小艷

摘 要 遺傳算法通過模擬生物自適應選擇過程和自適應進化過程，通過不斷迭代逼近最優解，可以將其用于求解高度復雜的非線性最優值問題，多目標遺傳算法在優化多目標問題時具有良好的效果。本文在簡單遺傳算法的理論基礎上，主要著重的介紹了NSGA與NSGA-II算法，得出，改進后的算法時間開銷有所降低，既保證了種群的多樣性，同時引入擁擠距離排序機制使算法避免了預先設定參數的困難。

關鍵詞 多目標優化 遺傳算法 最優解 生物進化算法

中圖分類號：TP181 文獻標識碼：A

0前言

19世紀70年代初期，由于受到達爾文進化理論的啟發，Rosenberg提出了采用達爾文進化理論的思想解決多目標優化問題。1993 年，Deb和 Srinivas 首先提出基于非劣分級排序的遺傳算法（NSGA）。Hom 提出 Pareto 遺傳算法。NSGA-II是針對原NSGA算法存在的不足的改進，2002 年 Deb提出帶有精英策略的非劣分級排序的遺傳算法（NSGA-II），該算法通過采用快速分級排序以及精英策略，能夠提高算法收斂速度及保持結果多樣性。目前，NSGA-II算法已經成為解決多目標優化問題的優秀算法，被廣泛應用到科學工程領域等。

1 Pareto占優

對于多目標優化問題，通常存在一個解集，這些解之間就全體目標函數而言是無法比較優劣的，其特點是：無法在改進任何目標函數的同時不削弱至少一個其他目標函數。這種解稱作非支配解或Pareto最優解。對于組成Pareto最優解集的所有Pareto最優解，其對應目標空間中的目標矢量所構成的曲面稱作Pareto最優前沿。

NSGA與簡單的遺傳算法的主要區別在于：該算法在選擇算子執行之前根據個體之間的支配關系進行了分層。其選擇算子、交叉算子和變異算子與簡單遺傳算法沒有區別。

2 NSGA算法

NSGA-II擁擠度比較算子：經過前面的快速非支配排序和擁擠度計算之后，種群中的每個個體i都擁有倆個屬性：非支配排序決定的配置配序irank和擁擠度id。只要下面任意一個條件成立，則個體i獲勝。勝出的個體進入下一個操作。

（1）如果個體i所處的非支配層優于個體j所處的非支配層，即irank

（2）如果他們具有相同的等級，且個體i比個體j有一個更大的擁擠距離，即：。

4結語

NSGA-II與NSGA比較而言，采用了快速非劣排序，新的多樣性保持策略，使得其計算復雜度由原來的為O（MN3）降低到O（MN2）（其中M為目標數量，N為種群大小）。

采用了擁擠度和擁擠度比較算子，不但克服了NSGA中需要人為指定共享參數的缺陷，而且將其將其作為種群中個體的比較標準，使得準Pareto域中的個體能均勻地擴展到整個Pareto域，保證了種群的多樣性。

參考文獻

[1] 郭修豪. 改進遺傳算法在多目標問題上的應用研究[D].重慶師范大學，2016.

[2] 徐磊. 基于遺傳算法的多目標優化問題的研究與應用[D].中南大學，2007.

[3] 魏靜. 基于改進NSGA2算法的給水管網多目標優化設計[D].北京工業大學，2016.