NSGA2遺傳算法怎樣解決多目標優化

NSGA2遺傳算法怎樣解決多目標優化，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

NSGA-II

進行多目標優化時，通常面臨多個目標函數無法同時達到最優的情況，為了解決這一矛盾，引入Pareto-Optimality的概念

Pareto-Optimality

通常，多目標優化的一般形式為：

經過處理，可以化為以下形式：

其中

f1(x),f2(x),...,fn(x)

為目標函數，其全部都是求最小值的形式

以下針對兩個目標函數進行討論：

有幾個目標函數便為幾維空間，有兩個目標函數Time(f1(x)),Cost(f2(x)),

可以畫出圖像：

隨后引入幾個概念：

非支配解：假設任何二解S1 及S2 對所有目標而言，S1均優于S2，則我們稱S1 支配S2，若S1 的解沒有被其他解所支配，則S1 稱為非支配解（不受支配解），也稱Pareto解

支配解：若解S2的所有目標均劣于S1，則稱S1優于S2，也稱S1支配S2

，S2為受支配解。

因此現在的首要任務是尋找解空間里面所有的Pareto解，找到所有Pareto解之后，這些解組成的平面叫做Pareto前沿面（Non-dominated front）。在目標函數較多時，前沿面通常為超曲面。

非支配解排序（Non-dominated Sorting）

1. 設所有解的集合為S，現從中找出非支配解集合，記為F1

2. 令S=S-F1，從S中再找出非支配解集合，記為F2

3. 重復第二步，直到S為空集

將每次找出的非支配解進行排序如下：

{F1,F2,…,Fn}

在途中畫出Fi集合中對應點，并連線，則構成了n個pareto曲面，分別編號為Non-dominated Front 1，Non-dominated Front 2…

以上述表格中數據為例：F1={A,B,D,F}, F2={C,E,D}, F3={H,I}

畫出相應圖形：

在第一個前沿面上的解具有最大的適應度，序數越大則適應度越小。序號小的前沿面上的解可以支配序號大的前沿面上的解。

同一前沿面上解的排序-擁擠度（Crowding Distances）

針對第一個前沿面來說，其中包含了A,B,D,F四個解，如何評判這四個解的適應度大小呢？由此引入了擁擠度的概念。

擁擠度的計算：

1. 只考慮同一前沿面上的解，設定位于前沿面兩端邊界點的擁擠度為∞。

2. 對于不在兩端的點，其擁擠度主要與其相鄰兩個點有關

擁擠度越小則對應該解越重要

比較通俗的理解：擁擠度越小就說明該解與其他解相似程度不高，保留擁擠度較小的點相當于保存了解的多樣性

所以說，確定解的適應度大小順序應該先判斷該解在哪個前沿面上，如果在同一個前沿面上，則再計算擁擠度進行判斷

與遺傳算法結合

與普通遺傳算法步驟大概相同，初始化隨機取幾個解，進行編碼，交叉互換，突變

生成子代

但是，在生成子代后，需要與父代混合，從中挑選出適應度較高的解重新形成子代，再進行新的一輪迭代。

舉例說明：

1.針對一個兩目標優化問題，初始化隨機取出10個解記為F，經過計算得到子一代為P

此時將P,F混合，形成新的解集S

2.針對S，進行上面所介紹的非支配解排序，計算擁擠度，最終得出這12個解的適應度大小順序，從中取適應度較大的10個點生成新的子代（維持和父代個數相同），帶入算法進行新一輪迭代

子代父代混合篩選生成新的子代，好像叫做精英策略

任何啟發式算法均有兩個方面組成：加快收斂的操作和在收斂過程中保持解的多樣性的操作，兩種操作相互作用，以至于找到一個合適的收斂速度，減少計算時間，同時避免陷入局部最優

對于NSGA來說，其規則仍然符合這兩個準則：

1. 本算法并不是只取最優的前沿面，而是將所有前沿面均納入考慮范圍內，是為了體現解的多樣性，防止陷入局部最優

2. 計算擁擠度是為了保存下來相似程度較低的解，保持解空間的多樣性

3. 使用精英策略是為了加速收斂，更快的除去劣解

看完上述內容，你們掌握NSGA2遺傳算法怎樣解決多目標優化的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！