能幫助通俗解釋下NSGA3演算法嗎。？

12-28

演算法。計算。

題主好，很慚愧，只有一點微小的見解，希望能相互交流，共同進步。

首先NSGA-III演算法沿用了NSGA-II的框架，要弄懂NSGA-III，先要簡略地了解NSGA-II

兩種演算法都是多目標進化演算法，大致可以分為兩步：第一步是非支配分層，第二步是從最後一個非支配層級中挑選個體進入子代。

所以NSGA-III演算法其實可以被劃分為以下五步：
1）首先假設有一個規模為N的種群A，用遺傳運算元（選擇、重組、變異）對種群A進行操作，得到一個規模為N的種群B，再將種群A和種群B混合，得到一個規模為2N的種群C。

2）對種群C進行非支配排序（詳見NSGA-II），得到非支配層級為1、2、3、4……的諸層個體。把非支配層級為1、2、3……的個體依次加入下一代子代的集合D，直到集合D的規模大於N。記下這個時候的非支配層級L

我們接下來要做的，就是從L層級里挑選出K個個體，使得K和之前所有層級個體之和等於N

3）函數標量化操作
這一步是要對多目標函數進行標量化操作，方便下一步關聯參考點。
首先需要計算M個目標函數中每一個目標維度i上的最小值（就是遍歷取到Min啦，很簡單的），得到第i個目標上對應的最小數值為Zi，此Zi的集合即為NSGA-III演算法中提到的理想點集合（ideal points）。得到該理想點集合後，便有第一步的標量化公式，如下所示：

完成這一步之後，需要尋找極值點，也即NSGA-III演算法中提到的extreme points，在此需要用到一個名為ASF(achievement scalarizing function)的函數，公式如下所示，該公式同樣作用於每個維度的目標函數。

遍歷每個函數，找到ASF數值最小的個體，這些個體就是extreme points，根據這些點的具體函數值，就能算出對應坐標軸上的截距，在這裡，這個截距的實際意義是每個坐標點在對應坐標軸上的坐標值，可以將其記錄為ai。得到ai和zi的具體數值以後，可以按如下所示的公式進行歸一化運算：

第三步就完成啦

4）個體關聯參考點
NSGA-III是一種基於參考點的多目標進化演算法，這個參考點至關重要，以四劃分三個目標函數為例，參考點分布如下圖所示（圖片來源自NSGA-III原論文）：

這裡插播一句，這樣的排列方式應該怎麼實現呢？

可以看到參考點是依次往上，逐級遞減，一種簡單的方法就是遞歸！處理這種問題，遞歸大法是墜吼的，雖然遞歸開銷巨大，但是參考點又不需要每一代都算，可以一勞永逸

得到相應劃分的參考點之後，接下來要做的即為構建參考點向量（參考點到原點的連線，即為一條參考向量）。所以我覺得，與其說NSGA-III是基於參考點的演算法，不如說是基於參考向量的演算法，這樣更加準確一點。

做完這一步以後，需要針對每一個種群個體遍歷所有向量，找到距離每個種群個體最近的參考點（這裡需要用到點到向量的距離公式），同時記錄下參考點的信息和對應的最短距離。其中，種群個體到參考點向量的距離將用垂直距離來描述，三維示例如下圖（圖片來源自NSGA-III原論文）：

因為要保存個體點、參考點、距離等等相關聯的信息，實現的時候可以用結構體封裝所有數據，或者新建一個類

5）最後一步，篩選子代與刪除參考點

一個參考點可能有一個或多個種群成員與之相關，或者不需要任何種群成員與之關聯。

經過非支配排序後，假設從第一個非支配層級到第FL層級的種群成員數目總和第一次超過種群規模N，那麼定義St+1為包含了FL中全部個體的集合，由於St+1的規模超過了預先設定的種群成員數目，因此需要進行相應的篩選。篩選的第一步是對每個參考點進行遍歷，查看它被不包含FL的St+1引用的次數，並且尋找到被引用次數最少的參考點，也即被數量最少的種群個體所關聯的參考點，將其被引用次數記錄為pj。

然後就是黑暗前的黎明，成功前的最後一步——分情況討論：

（1）假如這個參考點關聯的種群個體數量為零，也即pj等於零，但在FL中有個體被關聯到這個參考點向量，則從中尋找距離最小的點，並將其從FL中抽取，加入到被選擇的下一代種群中，設置pj=pj+1

（2）如果在FL中沒有個體被引用到該參考點，則刪除該參考點向量，倘若pj&>0，則從中選擇距離最近的參考點

直到種群規模為N為止，就大功告成了！

知乎首答，百分百原創……因為才疏學淺，可能有錯漏之處，恭請指正，感謝閱讀。

今天在看NSGA-III的論文，感覺歸一化（Adaptive Normalization of Population Members）這一部分比較難理解，特別是裡面提到的ASF函數。要理解之，我覺得可以一邊看論文，一邊看jMetal裡面對於NSGA-III的代碼實現：https://github.com/jMetal/jMetal/blob/master/jmetal-algorithm/src/main/java/org/uma/jmetal/algorithm/multiobjective/nsgaiii/NSGAIII.java
我對於NSGA-III的理解如下：

1. 歸一化方法

a) 先對目標值進行映射（映射的方法是減去理想點的值）

b) 然後找到每個維度的極端點（也就是離每個坐標軸比較近的點）

c) 找極端點的方法是：固定某一個維度，該維度的權重設為1，其他維度的權重設為一個很小的值，對於每一個解，用ASF計算它的值（以所有維度上的最大值表示這個解），選擇所有解中ASF值最小的解作為極端點。

d) 一般情況下，所有維度的極端點可以確定一個超平面。

e) 計算這個超平面和各個坐標軸的交點（截距）

f) 歸一化的時候直接除以截距

2. 對於關鍵層的解的選擇策略

a) 設定一系列參考點

b) 已經在種群中的解（也就是關鍵層前面的層裡面的所有解），每個解都會關聯到一個參考點

c) 每個解關聯到哪一個參考點取決於它到參考線的距離，到哪個參考線的距離最小就關聯到哪個參考線（而參考線就是參考點到原點的連線）

d) 關聯之後，每個參考點 $j$ 都會有一個與它關聯的解的數量 $ho _{j}$

e) 每次從關鍵層裡面選一個解加入到種群，選擇的策略是：選 $ho _{j}$ 最小的參考點 $j$ ，如果 $ho _{j}=0$
（表示當前種群裡面沒有任何解與這個參考點關聯），則從關鍵層裡面選擇一個到該參考點 $j$ 距離最小的解加入種群（如果有的話），否則把該參考點從當前代中去除。如果 $ho _{j}geq 1$ ，則從關鍵層裡面隨機選擇一個關聯到該參考點的解加入到種群（如果有的話）

NSGA2和NSGA3的兩篇文章，都是在挑選下一代做文章。主要做的是保證下一代的多樣性（即適應度），第二篇比第一篇的方法更系統。我覺得好多遺傳演算法都是針對適應度改進。

NSGA-3是在NSGA-2演算法上改進得到的，個人認為只是在選擇操作（replace）上有一些差別，不再是NGSA-2單獨的比較，而是需要在求取每個種群個體在參考平面上的距離並進行比較。暫時得到的Pareto曲面還沒那麼好，ieee30節點數據最小的才799.幾，現在還在努力改進中~