【學習筆記】基于參考點的非支配排序--NSGA-III

• 簡介
• 問題詳述
• 關于多目标問題的兩個想法
• NSGA-III算法

簡介

Q：進化多目标優化(EMO)方法在尋找不同的兩目标和三目标優化問題的一組良好收斂和良好多樣化的非支配解方面充分顯示了它們的優勢。然而，在涉及多個涉衆和功能的現實問題中，經常存在許多涉及四個或四個以上目标的優化問題。

A:提出的NSGA-III,在原有NSGA-II的非支配架構的基礎上，引入了參考點機制，解決目标空間維數過多遇到的一些問題。

問題詳述

在目标空間維數過多的時候，會遇到：

• 目标空間維數大，種群中大部分的個體是非支配的，選擇壓力不足
• 多樣性測度的評估在計算上變得昂貴

• 重組操作很優惠、可能是低效的

  高維空間，有限數量的解相距較遠，産生低效率的後代（因為繁殖産生的子代遠離父母過遠）

• 對于表面的權衡較為困難

  我們可以很直覺地認識到，要表示一個高維的曲面，就需要指數級的更多點。是以，需要一個較大的種群規模來表示得到的帕累托最優前沿。

• 可視化問題
• 計算名額，複雜度指數增長

關于多目标問題的兩個想法

• 使用特殊的控制原則，例如加性支配原則，這樣也會在一定程度上緩解多樣性問題，另外還有交配限制以及重組方案，如本算法建議使用SBX算子。

• 使用預定義的多目标搜尋，預設搜尋方向。由于找到對應每個目标的搜尋人物的最佳點，是以支配壓力問題也略有緩解。

  （預設搜尋方向or預設搜尋點）

NSGA-III算法

A.人口分布為非支配水準

從非主導前沿等級1到等級l的所有種群成員首先包含在St中，如果|St| = N;對于|St| > N，成員從1到(l−1)等級已經被選擇，即Pt+1 =∪ Fi，i=1~l−1剩餘的(K = N−|Pt+1|)種群成員是從最後的等級Fl中選擇的。我們在下面的子部分描述了剩餘的選擇過程。

B.超平面上參考點的确定

有兩種參考點的确定方式，一種是使用者預設參考點，另外一種是Das and Dennis方法，即在機關單純形上均勻分布。如圖為在三維目标空間上均勻産生15個參考點。

C.種群成員的自适應歸一化操作

分為兩步：

首先利用種群的理想點，進行如下操作

在利用種群的極端點，進行如下操作

ai為種群極端點構成的多元平面和坐标軸相交的截距，種群中極端點，為使ASF函數值最小的個體的值。如圖：

經過此變換操作之後，種群中的個體被歸一化到了參考點所在平面。

D.關聯操作

參考線最接近歸一化目标空間中種群個體的參考點被認為與種群個體相關聯。即找種群中個體所離的最近的由參考點确定的參考線，那麼這個個體與此參考點關聯。

E.生态保護行動（選擇操作）

1.計算pj，即前l-1個等級中與每個參考點關聯的個體數

2.選擇pj最小的參考點，即關聯數量最少的參考點。若有多個參考點關聯數量都是最小，則随機選擇其中一個。

3.如果最小的pj=0，那麼有兩種情況

• 若在l等級中，有多個個體（至少一個）與該參考點關聯，則選擇距離值（個體到參考線的垂直距離）最小的個體加入下一代。
• 若在l等級中無與該參考點關聯的個體，則排除此參考點，重新選擇一個pj最小的參考點重新計算。

如果pj>=1，則在Fl中随機選擇一個關聯個體加入（如果有關聯個體的話）。

F.創造後代種群的遺傳操作

建議使用SBX算子，以便産生逼近父代的個體。

G.源代碼