文章目錄
- 前言
- 一、什麼是NSGA-II？
- 二、學習NSGA-II
-
- 1.快速非支配排序算法
- 2.密度估計
- 3.擁擠比較算子
- 4.主循環
- 5.代碼
- 6.總結
前言
NSGA-II适用于複雜的多目标優化問題，是K-Deb教授在2000年在一篇paper《MOEAs — A fast and elitist multi-objective genetic algorithm: nsga2》提出。
Keywords： optimization; multi-objective evolutionary algorithm; non-dominated sorting genetic algorithm II (NSGA-II); genetic algorithm(GA)；crowding-distance
原文連結: http://repository.ias.ac.in/83498/1/2-a.pdf.
一、什麼是NSGA-II？
在過去的十年裡，許多多目标進化算法被提出。主要原因是他們能夠在一次運作中找到多個帕累托最優解。由于問題具有多目标公式的主要原因是不可能有一個同時優化所有目标的單一解，是以給出大量位于帕累托最優前沿或其附近的備選解的算法具有很大的實用價值。
The Non-dominated Sorting Genetic Algorithm (NSGA) 是此多目标進化算法之一。
但是NSGA有一些問題：
- 非支配排序高的計算複雜度: 複雜度為 O ( m N 3 ) O\left(m N^{3}\right) O(mN3)
- 缺乏elitism: 精英主義可以顯著加快遺傳算法的性能。
- 需要制定共享參數: 嚴重依賴于共享的概念。
NSGA-II的出現解決了這些問題。
二、學習NSGA-II
1.快速非支配排序算法
為了根據非支配水準大小為N的種群進行排序，必須将每個解與種群中的每個其他的解進行比較，以發現它是否被支配。
什麼是支配？
比如一個女生和另外一個女生比較身高和體重，如果1号女生既比2号女生高又比2号女生瘦，此時1号女生支配2号女生。如果1号女生隻比2号女生高，但是比2号女生瘦，這說明兩個女生身材不分伯仲，此時誰都不支配誰。
首先，我們對于每個解，計算兩個實體：
- n i n_{i} ni支配解的數量。
-
S i S_{i} Si支配解 i i i的一組解
這兩個實體的計算複雜度為 O ( m N 2 ) O\left(m N^{2}\right) O(mN2)。
我們要找到所有 n i = 0 n_{i}=0 ni=0的點，并把它放入一個 F 1 F_{1} F1清單中。現在，對于 F 1 F_{1} F1證監會中每一個解決方案，我們通路其 S i S_{i} Si集合中的每一個成員j，并将n計數減少1。如果對于任何一個成員j的計數變為0，就将它放入單獨的清單h中。當 F 1 F_{1} F1中所有成員被檢查過，将 F 1 F_{1} F1作為一級非支配層。然後，繼續循環，使用h作為下一次循環的 F 1 F_{1} F1。以此類推，直到整個種群被分層。
2.密度估計
為了估計人口中特定點周圍解的密度，我們沿着每個目标取該點兩側兩點的平均距離。這個數值作為以最近鄰居作為頂點的長方體周長的估計。
3.擁擠比較算子
經過快速非支配排序以及計算擁擠度之後，種群中每個人口有兩個屬性：
- 非支配等級
-
局部擁擠距離
也就是說，在具有不同非支配等級的兩個解之間，我們具有較低等級的點更好。如果兩個點都屬于一個等級，那麼位于點數較少的區域的點（包含它的長方體的大小較大）更好。
4.主循環
最初，建立随機的父群體 P 0 P_{0} P0，對種群進行非支配排序。每個解被配置設定一個與其非支配等級級别相等的适應度。Binary tournament、重組、變異操作符用于建立大小為n的子種群 Q 0 Q_{0} Q0。精英政策僞代碼如下所示：
首先，将t代産生的新種群 Q t Q_{t} Qt與父代種群 P t P_{t} Pt合并。群體大小為2N。然後，進行非支配排序。新的父群體 P t + 1 P_{t+1} Pt+1是累加的，直到填滿N。這個n個大小的種群現在用于選擇、交叉和變異，以建立新種群 Q t + 1 Q_{t+1} Qt+1。
精英政策：
5.代碼
使用geatpy遺傳算法工具庫可以實作NSGA-II算法。後期會介紹，敬請期待！
6.總結
以上就是今天要講的内容，本文僅僅簡單介紹了NSGA-II以及代碼，NSGA-II是一個非常強大的多目标優化算法。