注釋：是學習之余整理的資料，如有不足的地方還請指教，十分感謝！

目錄

1、多目標進化算法

1.1 MOEA概述

1.2 MOEA的分類

2、NSGA-Ⅱ算法介紹

2.1 NSGA算法

2.2 NSGA-Ⅱ算法

3、NSGA-Ⅱ算法的步驟

3.1 NSGA-Ⅱ算法流程圖

?3.2 NSGA-Ⅱ關鍵子程序算法

4、NSGA-Ⅱ算法的優、缺點

5、NSGA-Ⅱ算法的應用

5.1公交調度優化問題

5.2軌道電路維修策略問題

1、多目標進化算法

進化算法是一類模擬生物自然選擇與自然進化的隨機搜索算法，因其適用于求解高度復雜的非線性問題而得到了廣泛的應用，同時他又具有較好的通用性。在解決只有單個目標的復雜系統優化問題時，進化算法的優勢得到了充分展現。然而，現實世界中的優化問題通常是多屬性的，一般是對多個目標的同時優化。由此，針對多個目標的優化問題，出現了多目標進化算法MOEA。

1.1 MOEA概述

1967年，Rosenberg建議采用基于進化的搜索來處理多目標優化問題，但他沒有具體實現。1985年，David Schaffer首次在機器學習中實現了向量評估遺傳算法。1989年，David Goldberg提出來用進化算法實現多目標的優化技術，在對多目標進化算法的研究具有重要的方向性指導意義。

1994-2001年的8年，國際上所出版的論文是過去10年的3倍多。最近15年的發展速度比過去8年又有很大提高，一方面，在IEEE Transacrions on Evolutionary Computation、Evolutionary Computation和Genetic Programming and Evolvable Machines等國際重要學術期刊，以及各類國際進化計算學術會議上發表的有關多目標進化的論文比過去八年增長的幅度大很多，另一方面有關進化算法的期刊或會議的影響力越來越大，如IEEE Transacrions on Evolutionary Computation、Evolutionary Computation按JCR期刊影響因子均已進入SCI一區。第三方面，應用成果越來越多，涉及的應用范圍越來越廣。

1.2 MOEA的分類

MOEA種類較多，在此我們只討論按不同的進化機制和不同的決策方式對MOEA進行分類:

①基于分解的MOEA

②基于支配關系的MOEA

③基于指標的MOEA

而本次要講解的NSGA-Ⅱ屬于②基于支配關系的MOEA

2、NSGA-Ⅱ算法介紹

2.1 NSGA算法

? ? ? ?NSGA通過基于非支配排序的方法保留了種群中的優良個體,并且利用適應度共享函數保持了群體的多樣性，取得了非常良好的效果。但實際工程領域中發現NSGA算法存在明顯不足，這主要體現在如下3個方面：

(1)非支配排序的高計算復雜性。非支配排序算法一般要進行mN^3次搜索，搜索的次數隨著目標函數數量和種群大小的增加而增多。（m為目標數，N為群體大小）?

(2)缺少精英策略。研究結果表明，引用精英策略可以加快遺傳算法的執行，并且還助于防止優秀的個體丟失。
(3)需要指定共享參數share，在NSGA算法中保持種群和解的多樣性方法都是依賴于共享的概念，共享的主要問題之一就是需要人為指定一個共享參數share。

2.2 NSGA-Ⅱ算法

為了克服非支配排序遺傳算法(NSGA)的上述不足，印度科學家Deb于2002年在NSGA算法的基礎上進行了改進，提出了帶精英策略的非支配排序遺傳算法(Elitist Non-Dominated Sorting Genetic Algorithm，NSGA-II)，NSGA-II 算法針對NSGA的缺陷通過以下三個方面進行了改進：

①提出了快速非支配的排序算法，降低了計算非支配序的復雜度。

②引入了精英策略，擴大了采樣空間，提高優化結果的準確度。

③引入擁擠度和擁擠度比較算子，這不但克服了NSGA算法中需要人為指定共享參數的缺陷，而且將擁擠度作為種群中個體之間的比較準則，使得準Pareto域中的種群個體能均勻擴展到整個Pareto域，從而保證了種群的多樣性。

①支配：假設小明9歲，50斤，小紅8歲，45斤，小明無論是歲數還是體重都比小紅大，所以小明支配小紅。

②互不支配：假設小明7歲，50斤，小紅8歲，45斤，小明歲數比小紅小，但體重比小紅大，所以小明和小紅互不支配。

③非支配排序：將一組解分成n個集合：rank1,rank2…rankn,每個集合中所有的解都互不支配，但ranki中的任意解支配rankj中的任意解（i<j）。

④精英策略即保留父代（上代），然后讓父代和經過選擇、交叉、變異后產生的子代共同組成一個群體，其目的就是為了防止父代中可能存在的最優解被遺落，最后經過再次選擇操作，獲得與初始種群同樣規模的群落。

3、NSGA-Ⅱ算法的步驟

3.1 NSGA-Ⅱ算法流程圖

首先,隨機產生規模為N的初始種群,非支配排序后通過遺傳算法的選擇、交叉、變異三個基本操作得到第一代子代種群;
其次,從第二代開始,將父代種群與子代種群合并,進行快速非支配排序,同時對每個非支配層中的個體進行擁擠度計算,根據非支配關系以及個體的擁擠度選取合適的個體組成新的父代種群;
最后,通過遺傳算法的基本操作產生新的子代種群:依此類推,直到滿足程序結束的條件。

?二進制錦標賽法（二元錦標賽法）

錦標賽方法選擇策略每次從種群中取出一定數量個體，然后選擇其中最好的一個進入子代種群。重復該操作，直到新的種群規模達到原來的種群規模。具體的操作步驟如下：

(1) 確定每次選擇的個體數量。一般選擇2個。

(2) 從種群中隨機選擇個個體(每個個體入選概率相同) 構成組，根據每個個體的適應度值，選擇其中適應度值最好的個體進入子代種群。

(3) 重復步驟(2) ，得到的個體構成新一代種群。

下面舉一個簡單的例子演示NSGA-Ⅱ算法的流程。設種群大小為5，目標函數2個。

①初始化：初始化5個個體為初代

②選擇、交叉、變異

?原先的5個個體變異，再任選兩個進行交叉，交叉又產生5個個體，現在總共有10個個體了。

?

?

④選擇

我們自然是選擇rank高的個體，rank=1和rank=2的個體，總共3個被保留。我們要再次湊成5個個體的種群。我們就在rank=3的個體中選，但是也不能全要，因為會超過5個，這就用到擁擠度了，選擇擁擠度大的，那么就是最左邊和最右邊的兩個，因為我們定義了這兩個的擁擠度是無限大。

⑤迭代

?選擇完了又回到第②步，直到進化到了一定的次數，結束算法。

?3.2 NSGA-Ⅱ關鍵子程序算法

?

?

?

?3.2.2 保持解群體分布性和多樣性的方法

為了保持解群體分布性和多樣性，首先通過計算進化群體中每個個體的聚集距離，然后依據個體所處的層次及其聚集距離，定義一個偏序集，構造新群體時依次在偏序集中選擇個體。

在產生新群體時，通常將優秀且聚集密度比較小的個體保留并參與下一代進化。聚集密度小的個體其聚集距離反而大。

（1）聚集距離：通過計算與其相鄰的兩個個體在每個子目標上的距離差之和來求取。

?

?

?

4、NSGA-Ⅱ算法的優、缺點

NSGA-II的提出，為多目標進化算法的一大進步，特別是其基于Pareto支配關系的框架被后來許多算法采用，如NSGA-III，VaEA等。同時，NSGA-II對于低維多目標優化問題效果是不錯的，但是對于高維多目標優化問題，其首先面對的便是由于其基于Pareto支配關系所導致的選擇壓力過小的問題，其次，便是擁擠距離在高維空間不適用，計算復雜度也比較高。

5、NSGA-Ⅱ算法的應用

NSGA-Ⅱ算法是 Deb 等學者于2000年在NSGA算法的基礎之上提出來的，該算法能夠得到一系列分布均勻、多樣性較好的最優解集，適用于多個目標的優化問題，且相對成熟，廣泛應用于橋 梁、核電等領域的維修策略優化中。

5.1公交調度優化問題

公交運營成本與乘客出行時間成本是一對矛盾的組合體，單方面最優無法滿足公交體系建設的需要。不科學的發車頻率不僅會延長乘客的候車時間，降低乘客乘車舒適度，也會造成運營成本的增加。所以在優化調度體系時，應同時考慮車輛運營成本與乘客的出行時間成本進行多目標優化，找到使雙方相對最優的策略。利用 NSGA-Ⅱ算法求解最優發車間隔。

5.2軌道電路維修策略問題

針對軌道電路傳統維修的低可靠性和高維修費用問題，提出軌道電路維修策略多目標優化模型，通過NSGA-Ⅱ算法對其維修策略進行優化。

總結

以上是生活随笔為你收集整理的NSGA-Ⅱ算法原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。