maplele的博客：NSGA-2學(xué)習(xí)筆記

https://blog.csdn.net/lf8289/article/details/2291466

u014276869的博客：NSGA-II算法的學(xué)習(xí)筆記

https://blog.csdn.net/u014276869/article/details/74450669

冷夏的專欄：多目標(biāo)優(yōu)化系列（一）NSGA-Ⅱ

https://blog.csdn.net/u014119694/article/details/77248913?locationNum=6&fps=1

------------------------------------------------------------------------------------------------------------------------------------------------------------------

本文全篇來源于“自助者天助！”的博客園《從NSGA到 NSGA II》，引用僅僅因?yàn)椴榭捶奖?#xff0c;僅用于學(xué)習(xí)，絕無其他商業(yè)用途，對此致謝，如有侵犯，請聯(lián)系1933464516@qq.com刪帖。

https://www.cnblogs.com/bnuvincent/p/5268786.html

GA（非支配排序遺傳算法）、NSGAII（帶精英策略的非支配排序的遺傳算法），都是基于遺傳算法的多目標(biāo)優(yōu)化算法，都是基于pareto最優(yōu)解討論的多目標(biāo)優(yōu)化，遺傳算法已經(jīng)做過筆記，下面介紹pareto（帕累托）最優(yōu)解的相關(guān)概念。本文是基于參考文獻(xiàn)做的讀書筆記。

1 NSGA算法

1.1?Paerot支配關(guān)系

1.2 ?Pareto最優(yōu)解定義

多目標(biāo)優(yōu)化問題與單目標(biāo)優(yōu)化問題有很大差異。當(dāng)只有一個(gè)目標(biāo)函數(shù)時(shí),人們尋找最好的解,這個(gè)解優(yōu)于其他所有解,通常是全局最大或最小,即全局最優(yōu)解。而當(dāng)存在多個(gè)目標(biāo)時(shí),由于目標(biāo)之間存在沖突無法比較,所以很難找到一個(gè)解使得所有的目標(biāo)函數(shù)同時(shí)最優(yōu),也就是說,一個(gè)解可能對于某個(gè)目標(biāo)函數(shù)是最好的,但對于其他的目標(biāo)函數(shù)卻不是最好的,甚至是最差的。因此,對于多目標(biāo)優(yōu)化問題,通常存在一個(gè)解集,這些解之間就全體目標(biāo)函數(shù)而言是無法比較優(yōu)劣的,其特點(diǎn)是:無法在改進(jìn)任何目標(biāo)函數(shù)的同時(shí)不削弱至少一個(gè)其他目標(biāo)函數(shù)。這種解稱作非支配解(nondominated soluitons)或Pareto最優(yōu)解(Pareto optimal?Soluitons),定義如下：

也即沒有其他值可以支配Xu。

2、NSGA一般流程

NSGA采用的非支配分層方法,可以使好的個(gè)體有更大的機(jī)會遺傳到下一代;適應(yīng)度共享策略則使得準(zhǔn)Pareto面上的個(gè)體均勻分布,保持了群體多樣性,克服了超級個(gè)體的過度繁殖,防止了早熟收斂。流程圖如下：

NSGA與簡單的遺傳算法的主要區(qū)別在于:該算法在選擇算子執(zhí)行之前根據(jù)個(gè)體之間的支配關(guān)系進(jìn)行了分層。其選擇算子、交叉算子和變異算子與簡單遺傳算法沒有區(qū)別。

從圖中可以看到，算法首先判斷種群是否全部分級，如果已經(jīng)全部分級，則在分級的基礎(chǔ)上，使用基于擁擠策略的小生境(NIChe)技術(shù)對虛擬適應(yīng)度值進(jìn)行調(diào)整，并確定每個(gè)種群的虛擬適應(yīng)度值，然后根據(jù)虛擬適應(yīng)度值的大小，確定優(yōu)先選擇進(jìn)行處理的種群（遺傳算法）。

2.1?非支配排序

考慮一個(gè)目標(biāo)函數(shù)個(gè)數(shù)為K(K>1)、規(guī)模大小為N的種群,通過非支配排序算法可以對該種群進(jìn)行分層,具體的步驟如下:

通過上述步驟得到的非支配個(gè)體集是種群的第一級非支配層;然后,忽略這些標(biāo)記的非支配個(gè)體,再遵循步驟(1)一(4),就會得到第二級非支配;依此類推,直到整個(gè)種群被分類。

2.2?虛擬適應(yīng)度值的確定

在對種群進(jìn)行非支配排序的過程中,需要給每一個(gè)非支配層指定一個(gè)虛擬適應(yīng)度值。級數(shù)越大,虛擬適應(yīng)度值越小;反之,虛擬適應(yīng)度值越大。這樣可以保證在選擇操作中等級較低的非支配個(gè)體有更多的機(jī)會被選擇進(jìn)入下一代,使得算法以最快的速度收斂于最優(yōu)區(qū)域。另一方面,為了得到分布均勻的Pareto最優(yōu)解集,就要保證當(dāng)前非支配層上的個(gè)體具有多樣性。NSGA中引入了基于擁擠策略的小生境(NIChe)技術(shù),即通過適應(yīng)度共享函數(shù)的方法對原先指定的虛擬適應(yīng)度值進(jìn)行重新指定。

3、NSGAII算法

NSGA一II算法的基本思想為:首先,隨機(jī)產(chǎn)生規(guī)模為N的初始種群,非支配排序后通過遺傳算法的選擇、交叉、變異三個(gè)基本操作得到第一代子代種群;其次,從第二代開始,將父代種群與子代種群合并,進(jìn)行快速非支配排序,同時(shí)對每個(gè)非支配層中的個(gè)體進(jìn)行擁擠度計(jì)算,根據(jù)非支配關(guān)系以及個(gè)體的擁擠度選取合適的個(gè)體組成新的父代種群;最后,通過遺傳算法的基本操作產(chǎn)生新的子代種群:依此類推,直到滿足程序結(jié)束的條件。相應(yīng)的程序流程圖如下圖所示。

3.1 快速非支配排序算法

3.2 擁擠度和擁擠度比較算子

擠度是指種群中給定個(gè)體的周圍個(gè)體的密度,直觀上可表示為個(gè)體。周圍僅僅包含個(gè)體。本身的最大長方形的長,用nd表示,

擁擠度的算法如下：

3.3擁擠度比較算子

3.3 兩種算法對比及II代的改進(jìn)：

非支配排序遺傳算法(NSGA)在許多問題上得到了應(yīng)用,但NSGA仍存在一些問題:
)a計(jì)算復(fù)雜度較高,為O(mN3)(m為目標(biāo)函數(shù)個(gè)數(shù),N為種群大小),所以當(dāng)種群較大時(shí),計(jì)算相當(dāng)耗時(shí)。
b)沒有精英策略;精英策略可以加速算法的執(zhí)行速度,而且也能在一定程度上確保己經(jīng)找到的滿意解不被丟失。
)c需要指定共享半徑。

而NSGA一II針對以上的缺陷通過以下三個(gè)方面進(jìn)行了改進(jìn):

)a提出了快速非支配排序法,降低了算法的計(jì)算復(fù)雜度。由原來的O(mN3)降到O(mN2),其中,m為目標(biāo)函數(shù)個(gè)數(shù),N為種群大小。
b)提出了擁擠度和擁擠度比較算子,代替了需要指定共享半徑的適應(yīng)度共享策略,并在快速排序后的同級比較中作為勝出標(biāo)準(zhǔn),使準(zhǔn)Paroet域中的個(gè)體能擴(kuò)展到整個(gè)Pareto域,并均勻分布,保持了種群的多樣性。
)c引入精英策略,擴(kuò)大采樣空間。將父代種群與其產(chǎn)生的子代種群組合,共同競爭產(chǎn)生下一代種群,有利于保持父代中的優(yōu)良個(gè)體進(jìn)入下一代,并通過對種群中所有個(gè)體的分層存放,使得最佳個(gè)體不會丟失,迅速提高種群水平。

參考文獻(xiàn)：

1、帶精英策略的非支配排序遺傳算法的研究與應(yīng)用_鄭強(qiáng)

2、非支配排序遺傳算法_NSGA_的研究與應(yīng)用_高媛

?

總結(jié)

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

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