3 NSGA-II

3.1 算法流程

確定種群大小 n，交叉概率 t，迭代次數(shù) g 隨機產(chǎn)生 n 個個體，它們整體視為種群 P for i = 1 to gP = ? for j = 1 to n產(chǎn)生一個 [0,1] 的隨機數(shù) aif (a<t)從 P 中隨機選出兩個個體作為父母，交叉產(chǎn)生一個新的個體并放入 P’ 中else從 P 中隨機選出一個個體，變異產(chǎn)生一個新的個體并放入 P’ 中endend利用非支配排序和擁擠距離，從 P∪P’ 中選出 n 個個體， 代替 P # NSGA-II改進(jìn)的部分 end 輸出最終種群 P 中的非支配個體

---

3.2 NSGA-II 提出的 NSGA的缺點

• $O(M{N}^3)$計算復(fù)雜度(其中M代表目標(biāo)個數(shù)，N代表種群個數(shù))

  NSGA算法每一代進(jìn)化都要構(gòu)造非支配集, 在種群規(guī)模大的時候會造成巨大的時間開銷

• 非精英機制方法

  NSGA算法沒有采取保留優(yōu)秀解的措施, 導(dǎo)致算法性能受損。

• 需要指定共享參數(shù)

  指定共享參數(shù)是因為NSGA需要依靠共享參數(shù)來維持解群體的分布性, 也即實現(xiàn)解盡可能地均勻分布, 但共享參數(shù)的定義往往需要一定的經(jīng)驗, 這也導(dǎo)致共享參數(shù)的確定成為了老大難的問題。

---

3.3 NSGA-II 較于 NSGA的優(yōu)點

3.3.1 快速非支配排序

?在NSGA-中，將進(jìn)化群體按支配時關(guān)系分為若干層，第一層為進(jìn)化群體的非支配個體集合，第二層為在進(jìn)化群體中去掉第一層個體后所求得的非支配個體集合，第三層為在進(jìn)化群體中去掉第一層和第二層個體后所求得的非支配個體集合，依此類推。選擇操作首先考慮第一層非支配集，按照某種策略從第一層中選取個體;然后再考慮在第二層非支配個體集合中選擇個體，依此類推,直至滿足新進(jìn)化群體的大小要求。

1) 論文算法

---

2) 支配關(guān)系

對于二目標(biāo)優(yōu)化問題來講, 支配的含義在于 解A的值在兩個目標(biāo)函數(shù)上都優(yōu)與解B , 這樣我們就稱 解A支配解B (不理解可以參照 Pareto理論)
假如橫縱坐標(biāo)為兩個不同的約束函數(shù), 函數(shù)值越小越優(yōu)秀的情況下。 那么 B 顯然能夠支配 C和D , 因為 B的兩個函數(shù)值都小于 C與 D, 因此 $S_p=C,D$ 。 而 C 顯然受到 A 和 B 的支配, 因此 $np=2$ 。

---

3) 論文解釋

• 原文

  ? First, for each solution we calculate two entities: 1) domination count $n_p$, the number of solutions which dominate the solution p, and 2) $S_p$, a set of solutions that the solution dominates. This requires $O(M{N}^2)$comparisons.
  ? All solutions in the first nondominated front will have their domination count as zero. Now, for each solution p with $n_p=0$, we visit each member (q ) of its sets $S_q$ and reduce its domination count by one. In doing so, if for any member q the domination count becomes zero, we put it in a separate list Q. These members belong to the second nondominated front. Now, the above procedure is continued with each member of Q and the third front is identified. This process continues until all fronts are identified.

  ---

• 譯文

  ? 首先，對每一個解我門計算兩個實體:1）支配計數(shù)$n_p$ ,即支配著解 p 的解的數(shù)量，還有 2）$S_p$，解所支配的解的集合，這需要$O(M{N}^2)$次比較。
  ? 所有第一非支配前沿面解的支配計數(shù)都為零。現(xiàn)在，對每一個解 p 都有$n_p=0$，我們訪問每一成員(q）和他的集合$S_q$并且減少逐一減少支配計數(shù)。通過這樣，如果任何成員q的支配計數(shù)達(dá)到0，我們就把它放進(jìn)一個單獨集合 Q。這些成員屬于第二非支配前沿面。現(xiàn)在，以上程序應(yīng)用 Q中的每一成員繼續(xù)執(zhí)行直到第三前沿面被確定。這一過程持續(xù)到所有前沿面被確定。

  ---

• 個人理解

  快速非支配排序算法的目的在于將 種群根據(jù)相應(yīng)的支配關(guān)系劃分為不同級別的Pareto解 , 根據(jù)約束函數(shù)劃分為 $Paret{o}_1、Paret{o}_2......Paret{o}_N$ 等若干個等級。算法首先完成對所有種群最優(yōu)解的劃分, 也即 $Paret{o}_1$ 級解(也即種群的最優(yōu)解, 其余解按照$1?N$ 優(yōu)先級依次遞減)。其次完成刨去 $Paret{o}_1$ 級解之后解的劃分, 根據(jù)支配次數(shù)的結(jié)果 $n_q$ 的大小, 每執(zhí)行依次遞減, 當(dāng)執(zhí)行同一批次 $n_q$ 為零時的解劃分為同一等級 (Pareto front) , 直到集合為空, 完成種群 N 的劃分。

  ---

4) 偽代碼

# 以下是 NSGA-II 的偽代碼 # 參數(shù)說明 # np表示被多少解支配，是一個數(shù)目 # Sp表示該解所支配的解的集合,是一個集合 # P表示整個種群 # 對于參數(shù)而言, 這里的參數(shù)都是一些假參數(shù), 實際設(shè)計時, 解應(yīng)該是一個具有屬性地對象def fast_nondominated_sort(P):F = [] # 初始化 F用來存放支配關(guān)系的排序結(jié)果(分層劃分)for p in P: # 遍歷整個種群Sp = [] # 支配解集合初始化np = 0 # 支配解個數(shù)初始化for q in P: # 遍歷整個種群if p > q: # 如果p支配q,將q添加到 Sp 列表(p被p支配)Sp.append(q)elif q > p: # 如果q支配p,則 np + 1np += 1if np == 0: # 如果p沒有被其它解支配, 將它設(shè)為Pareto 1級, 也即非支配解p_rank = 1 #p_rank 是解的一個屬性, 代表了當(dāng)前解的 Pareto等級F1.append(p) # 將非支配解加入p 集合中F.append(F1) # 將Pareto 1級解加入F群體中i = 1# 下述算法復(fù)雜度為 O(MN^2)while F[i]: # 當(dāng)F 非空Q = [] # Q 存放后續(xù)的非支配解for p in F[i]: # 遍歷Pareto 1級解集合for q in Sp: # 遍歷Pareto 1級解的支配解 該集合 = 全集 - Pareto1級解nq -= 1 # 消除了 Pareto上層解 對它的支配if nq == 0: # 如果該個體支配計數(shù)為0, 代表是非支配解q_rank = i+1 # 設(shè)置該解為與 i + 1前沿面 i 初始為 1Q.append(q) # 將解存放到Q集合中F.append(Q) # 把Q得到的劃分好的非支配解排序結(jié)果拼接到 F 結(jié)果集內(nèi)部i += 1 # 重復(fù)循環(huán) 知道F[i]為空, 也即遍歷完所有的Pareto 1級解

---

3.3.2 擁擠度與擁擠度比較算子

1) 擁擠度計算公式

$I[i+1].m和I[i?1].m分別是解i后一個與前一個解在m函數(shù)上的的函數(shù)值$

$f_m^{max}和f_m^{min}分別是第m個函數(shù)的最大和最小值$
$$I_{distance}=(I[i+1].m?I[i?1].m)/(f_m^{max}?f_m^{min})$$

---

2) 擁擠比較算子

經(jīng)過前面的快速非支配排序和擁擠度計算之后，種群中的每個個體 $i$ 都擁有兩個屬性：非支配排序決定的非支配序 $i_{rank}$（級數(shù)，即第幾級）和擁擠度 $i_d$。依據(jù)這兩個屬性，可以定義擁擠度比較算子：個體i與另一個個體 j 進(jìn)行比較，只要下面任意一個條件成立，則個體 $i$ 獲勝。

① 如果個體 $i$ 所處非支配層優(yōu)于個體 $j$ 所處的非支配層，即 $i_{rank}<j_{rank}$

?② 如果它們有相同的等級且個體 $i$ 比個體 $j$ 有一個更大的擁擠距離，即 $i_{rank}=j_{rank}$ 且 $i_d>j_d$

第一個條件確保被選擇的個體屬于較優(yōu)的非劣等級。第二個條件根據(jù)它們的擁擠距離選擇由于在同一非劣等級而不分勝負(fù)的兩個個體中位于較不擁擠區(qū)域的個體(有較大的擁擠度 $i_d$ )。勝出的個體進(jìn)入下一個操作。

---

3.3.3 精英策略

1) 概述

首先將第 t 代產(chǎn)生的新種群 $Q_t$ 與父代 $P_t$ 合并組成 $R_t$ , 種群大小為 $2N$ 。然后 $R_t$ 進(jìn)行非支配排序產(chǎn)生一系列非支配集 $Z_i$ 并計算擁擠度。由于子代和父代個體都包含在 $R_t$ 中, 則經(jīng)過非支配排序后的非支配集合 $Z_1$ 是最優(yōu)的, 所以首先將 $Z_1$ 加入 $P_{t+1}$ 新父代種群中。 如果大小小于 N, 則繼續(xù)向 $P_{t+1}$ 種群中添加 $Z_2$ 。直到添加 $Z_3$ 時, 種群大小超過了 N , 這時就根據(jù)擁擠度比較算子進(jìn)行選擇添加, 使得 $P_{t+1}$ 個體數(shù)量達(dá)到 $N$。然后通過遺傳算子(選擇、交叉、變異)產(chǎn)生新的子代種群 $Q_{t+1}$

---

2)主體循環(huán)

以上代碼的邏輯跟精英策略的邏輯一致。

---

3.4 選擇算法

3.4.1 錦標(biāo)賽選擇算法

?遺傳算法中的錦標(biāo)賽選擇策略每次從種群中取出一定數(shù)量個體（放回抽樣），然后選擇其中最好的一個進(jìn)入子代種群。重復(fù)該操作，直到新的種群規(guī)模達(dá)到原來的種群規(guī)模。幾元錦標(biāo)賽就是一次性在總體中取出幾個個體，然后在這些個體中取出最優(yōu)的個體放入保留到下一代種群的集合中。具體的操作步驟如下：

?① 確定每次選擇的個體數(shù)量N。（二元錦標(biāo)賽選擇即選擇2個個體）
?② 從種群中隨機選擇N個個體(每個個體被選擇的概率相同) ，根據(jù)每個個體的適應(yīng)度值，選擇其中適應(yīng)度值最好的個體進(jìn)入下一代種群。
?③ 重復(fù)步驟②多次（重復(fù)次數(shù)為種群的大小），直到新的種群規(guī)模達(dá)到原來的種群規(guī)模。

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。