NSGA-II算法介绍
博主畢設(shè)用到了，記錄下來防忘記，比較具體，也分享給需要學(xué)習(xí)的同學(xué)。
1995年，Srinivas和Deb提出了非支配遺傳（Non-dominated Sorting Genetic Algorithms，NSGA）算法[42]。NSGA算法是以遺傳算法為基礎(chǔ)并基于Pareto最優(yōu)概念得到的。NSGA算法與基本遺傳算法的主要區(qū)別是其在進行選擇操作之前對個體進行了快速非支配排序，增大了優(yōu)秀個體被保留的概率[43]，而選擇、交叉、變異等操作與基本遺傳算法無異。經(jīng)過諸多學(xué)者的研究測試，NSGA算法比傳統(tǒng)的多目標(biāo)遺傳算法效果更好。但是在實際應(yīng)用中發(fā)現(xiàn)NSGA算法仍具有一定的缺點，主要體現(xiàn)在以下方面：
（1）算法計算量大。NSGA算法的計算復(fù)雜度與種群數(shù)量N、目標(biāo)函數(shù)個數(shù)m的關(guān)系為T = O(mN3)，當(dāng)種群規(guī)模較大、目標(biāo)函數(shù)較多時所耗時間較長。
（2）沒有應(yīng)用精英策略。未通過精英策略提高優(yōu)秀個體的保留概率，因而無法加快程序的執(zhí)行速度。
（3）需要人為地指定共享半徑σshare，對于經(jīng)驗的要求非常高。
為了改善NSGA算法的缺點，Deb等人在2002年提出了NSGA-II算法[44]。相對于NSGA算法，NSGA-II算法主要在以下三個方面做了改進：
（1）NSGA-II算法使用了快速非支配排序法，將算法的計算復(fù)雜度由O(mN3)降到了O(mN2)，使得算法的計算時間大大減少。
（2）采用了精英策略，將父代個體與子代個體合并后進行非支配排序，使得搜索空間變大，生成下一代父代種群時按順序?qū)?yōu)先級較高的個體選入，并在同級個體中采用擁擠度進行選擇，保證了優(yōu)秀個體能夠有更大的概率被保留。
（3）用擁擠度的方法代替了需指定共享半徑的適應(yīng)度共享策略，并作為在同級個體中選擇優(yōu)秀個體的標(biāo)準(zhǔn)，保證了種群中個體的多樣性，有利于個體能夠在整個區(qū)間內(nèi)進行選擇、交叉和變異。
實踐證明，NSGA-II算法無論在優(yōu)化效果還是運算時間等方面都比NSGA算法有了一定的改進，是一種優(yōu)秀的多目標(biāo)優(yōu)化算法。
1、?選擇、交叉、變異
遺傳算法中個體的編碼方式主要有實數(shù)編碼、二進制編碼、格雷編碼等，根據(jù)系統(tǒng)容量一般較大的特點，本文選擇實數(shù)編碼方式。在優(yōu)化過程中，個體的好壞依賴于個體的適應(yīng)度，適應(yīng)度高的個體有更大的可能被保留進入下一代。在實際操作當(dāng)中，適應(yīng)度一般為個體的目標(biāo)函數(shù)。
（1）選擇
選擇操作模仿自然界中的“優(yōu)勝劣汰”法則，若個體的適應(yīng)度高則其有更大概率被遺傳到下一代，反之則概率較小。進行選擇操作的方法有許多，比如輪盤賭選擇、排序選擇、最優(yōu)個體保存、隨機聯(lián)賽選擇等。
a. 輪盤賭選擇：將種群中所有個體的適應(yīng)度值加和，并把每個個體的適應(yīng)度值與和的比值作為該個體選擇的選擇概率，從而個體適應(yīng)度越高被選中概率越高。
b. 排序選擇：按照適應(yīng)度值大小對所有個體進行排序，并根據(jù)排序確定個體被選中的概率。
c. 最優(yōu)個體保存：會將父代群體中的最優(yōu)的個體直接保存入子代個體中，保證了優(yōu)秀個體能夠遺傳到下一代。
d. 隨機聯(lián)賽選擇：設(shè)置固定值k，每次隨機取k個個體，將其中適應(yīng)度最高的個體遺傳入下一代。
這些選擇方法各有優(yōu)缺點，應(yīng)根據(jù)不同場景、不同要求進行選擇，本研究采用隨機聯(lián)賽選擇方法。
?（2）交叉
交叉操作模擬自然界中染色體的交叉換位現(xiàn)象，用于生成新個體，決定了算法的全局搜索能力。標(biāo)準(zhǔn)的NSGA-II算法使用模擬二進制交叉算子，第k+1代個體的計算公式如下[44, 45]：
??? ?????????????????? ?????????????
式中，p1,k+1和p2,k+1是交叉后生成的第k+1代個體；p1,k和p2,k是被選中的第k代個體；βqi是均勻分布因子,其計算方式如下：
式中，ui是屬于[0,1)的隨機數(shù)；η是交叉分布指數(shù)，一般的定義為20~30，η的大小會影響產(chǎn)生的個體距離父代個體的遠近。
（3）變異
變異操作是模擬生物的基因變異，同交叉操作一樣，都用于產(chǎn)生新個體。標(biāo)準(zhǔn)NSGA-II算法的變異算子為多項式變異算子，第k+1代個體的計算公式如下[44,45]:
?
式中，pk是被選中的第k代個體；pk+1是pk經(jīng)變異操作得到的第k+1代個體；pmax k和pmin k分別為決策變量的上界和下界；δk計算公式如下：
?
式中，rk為[0,1]中的均勻分布隨機數(shù)；ηm為變異分布指數(shù)。
2、快速非支配排序
快速非支配排序是在Pareto支配基礎(chǔ)上提出的概念。假設(shè)有k個目標(biāo)函數(shù)記為fi (x)，其中i是1, 2, … , k中的任意整數(shù)，j同樣是1,2, …, k中的任意整數(shù)，但i≠j。若個體x1和x2對于任意的目標(biāo)函數(shù)都有fi(x1) < fi(x2)則稱個體x1支配x2；若對于任意的目標(biāo)函數(shù)都有fi(x1) ≤ fi(x2)且至少有一個目標(biāo)函數(shù)使得fj(x1) < fj(x2)成立則稱x1弱支配x2；若既存在目標(biāo)函數(shù)使得fi(x1) ≤ fi(x2)成立又存在目標(biāo)函數(shù)滿足fj(x1) > fj(x2)，則稱個體x1和x2互不支配。
種群中的每個個體都有兩個參數(shù)ni和Si，ni為種群中支配個體i 的個體數(shù)量，Si是被個體i支配的個體的集合,快速非支配排序的步驟如下：
（1）通過循環(huán)比較找到種群中所有ni = 0的個體，賦予其非支配等級為1，并將這些個體存入非支配集合rank1中。
（2）集合rank1中的每一個個體，將其所支配的個體集合中的每個個體的nj都減去1，若nj-1=0則將個體j存入集合rank2中，并賦予其中的個體非支配等級2。
（3）之后對rank2中的個體重復(fù)上述操作，直至所有個體都被賦予了非支配等級。
非支配等級也稱作Pareto等級，其中Pareto等級為1的個體由于不受其他個體的支配，叫做非支配解，也叫 Pareto最優(yōu)解，而解集所形成的曲線叫做Pareto前沿。以有兩個目標(biāo)函數(shù)f1和f2為例，假設(shè)經(jīng)過快速非支配排序之后共分成了三個Pareto等級，如圖4.1所示。圖4.1中用圓圈表示的個體即Pareto等級為1的個體組成的集合為本例的Pareto最優(yōu)解，這些個體形成的曲線即為本例的Pareto前沿。
?
?
?
3、擁擠度計算
在NSGA算法中，需要指定共享半徑σshare，這對經(jīng)驗要求較高，為了克服這一缺點，NSGA-II引用了擁擠度的概念。擁擠度表示空間中個體的密度值，直觀上可以用個體? 周圍不包括其他個體的長方形表示，如圖所示。
?
在對某個等級的個體進行擁擠度計算時，設(shè)該等級共有m個個體，每個個體用xi表示，i為1~m中的任意整數(shù)，xi-1，xi+1分別為i=2, 3, …, m-1時個體? 前后的個體；記第? 個個體的擁擠度為yi，初始值設(shè)為0；設(shè)有n個目標(biāo)函數(shù)，記為fk(x)，k=1, 2, …, n，記fmin k、fmax k分別為m個個體中目標(biāo)函數(shù)值fk(xi)的最小值和最大值，擁擠度計算的偽代碼流程如下所示：
for k<=n
{
?? ?// 根據(jù)目標(biāo)函數(shù)值fk(xi)對該等級的全部個體進行排序
??? y1=∞
??? ym=∞
?? ?i=2
for i<m
{
i=i+1
}
k=k+1
}
4、精英策略
NSGA-II算法引入了精英策略，達到保留優(yōu)秀個體淘汰劣等個體的目的。精英策略通過將父代與子代個體混合形成新的群體，擴大了產(chǎn)生下一代個體時的篩選范圍。以圖所示的例子進行分析，圖中P表示父代種群，設(shè)其中的個體數(shù)量為n，Q表示子代種群，具體步驟如下：
（1）將父代種群和子代種群合并形成新的種群。之后對新種群進行非支配排序，本例中將種群分成了6個Pareto等級。
（2）進行新的父代的生成工作，先將Pareto等級為1的非支配個體放入新的父代集合當(dāng)中，之后將Pareto等級為2的個體放入新的父代種群中，以此類推。
（3）若等級為k的個體全部放入新的父代集合中后，集合中個體的數(shù)量小于n，而等級為k+1的個體全部放入新的父代集合中后，集合中的個體數(shù)量大于n，則對第k+1等級的全部個體計算擁擠度并將所有個體按擁擠度進行降序排列,之后將等級大于k+1的個體全部淘汰。本例中可以看出k為2，所以對Pareto等級為3的個體計算擁擠度并按其進行降序排序，等級為4~6的個體全部淘汰。
（4） 將等級k+1中的個體按步驟2中排好的順序逐個放入新的父代集合中，直到父代集合中的個體數(shù)量等于n，剩余的個體被淘汰。
?
?
5、算法的實現(xiàn)步驟
NSGA-II算法的流程圖如圖4.4所示，具體實現(xiàn)過程如下：
第一步：初始種群并設(shè)置進化代數(shù)Gen=1。
第二步：判斷是否生成了第一代子種群，若已生成則令進化代數(shù)Gen=2，否則，對初始種群進行非支配排序和選擇、高斯交叉、變異從而生成第一代子種群并使進化代數(shù)Gen=2。
第三步：將父代種群與子代種群合并為新種群。
第四步：判斷是否已生成新的父代種群，若沒有則計算新種群中個體的目標(biāo)函數(shù)，并執(zhí)行快速非支配排序、計算擁擠度、精英策略等操作生成新的父代種群；否則，進入第五步。
第五步：對生成的父代種群執(zhí)行選擇、交叉、變異操作生成子代種群。
第六步：判斷Gen是否等于最大的進化代數(shù)，若沒有則進化代數(shù)Gen=Gen+1并返回第三步；否則，算法運行結(jié)束。
?
?
總結(jié)
以上是生活随笔為你收集整理的NSGA-II算法介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： psql 命令
- 下一篇： antd 日期时间选择_Excel最全时