NSGA-II入門

覺得有用的話,歡迎一起討論相互學(xué)習(xí)~

參考文獻(xiàn)1
參考文獻(xiàn)2

白話多目標(biāo)

多目標(biāo)中的目標(biāo)是個(gè)瓦特？

• 多目標(biāo)即是優(yōu)化問題中的優(yōu)化目標(biāo)在2個(gè)及以上，一般這些優(yōu)化的目標(biāo)都存在著矛盾，例如：我要買一個(gè)又便宜又漂亮又性能好的車的時(shí)候，價(jià)格，外觀， 性能 這就是一個(gè)典型的多目標(biāo)問題，我們必須在商品的價(jià)格，外觀和性能上做出取舍，畢竟外觀漂亮性能強(qiáng)勁的車型往往意味著高的價(jià)格。

多目標(biāo)中的支配是個(gè)瓦特？

• 我們經(jīng)常聽說 支配與非支配解集 ，那么什么叫做支配，什么叫做非支配呢？還是上面汽車的例子，如果汽車A價(jià)格30萬(wàn)，外觀A等，性能A等；汽車B價(jià)格40萬(wàn)，外觀A-等，性能A-等，就說汽車A支配了汽車B。如果有一輛汽車C價(jià)格20萬(wàn)，外觀B等，性能B等，相較于汽車A，雖然C的外觀和性能都比汽車A要差，但是其價(jià)格上比汽車A要低，從價(jià)格這個(gè)評(píng)價(jià)標(biāo)準(zhǔn)上來(lái)看，汽車C是要優(yōu)于汽車A的，所以說汽車C和汽車A是屬于一個(gè)非支配的關(guān)系。即 當(dāng)A所有目標(biāo)都優(yōu)于B時(shí)，就說A支配了B，否則A和B就是一個(gè)非支配的關(guān)系 ，而在NSGA-II中，種群中所有不被任何其他解支配的解構(gòu)成了非支配前沿(Pareto最優(yōu)解)
  

多目標(biāo)遺傳算法與遺傳算法的區(qū)別-選擇的方法不同

多目標(biāo)遺傳算法與遺傳算法的聯(lián)系-交叉變異的方法相同

• 遺傳算法中和多目標(biāo)遺傳算法中最大的不同在于 選擇 的過程，遺傳算法中通過適應(yīng)度函數(shù)進(jìn)行種群中個(gè)體的選擇，而多目標(biāo)遺傳算法中根據(jù) 非支配的Rank值和擁擠度進(jìn)行排序 選擇保留的個(gè)體。
  • 對(duì)于Rank值，首先我們將解集中的 所有不能被任何其他的解支配的解集 (即最厲害最牛的解)挑出來(lái)設(shè)為Rank0，然后將這些解從解集中排除，考慮剩下所有解中 所有不能被任何其他的解支配的解集 挑出來(lái)設(shè)為Rank1，…通過支配關(guān)系將解集中所有的解進(jìn)行排序，得到所有解的等級(jí)。我們認(rèn)為 Rank值越小的解越好。
  • 在選擇的過程中我們?cè)O(shè)定 每次迭代種群中個(gè)體的數(shù)量N是定值 ，而每次挑選時(shí)，先挑選表現(xiàn)最好的解–即Rank0的解，接著是Rank1,Rank2,Rank3…,但是我們總會(huì)出現(xiàn) ∑ i = 0 n ? 1 R a n k i < N \sum^{n-1}_{i=0}Rank_i<N i=0∑n?1?Ranki?<N 而 ∑ i = 0 n R a n k i > N \sum^{n}_{i=0}Rank_i>N i=0∑n?Ranki?>N 的情況，為了判定同一個(gè)Rank層的解的好壞，設(shè)置 擁擠度 作為同Rank非支配解集中解的評(píng)價(jià)標(biāo)準(zhǔn)。
  • 遺傳算法有自動(dòng)收斂的性質(zhì)，所以為了保證解的多樣性，我們往往希望同一Rank層中的解能夠相互分開，所以設(shè)置了 擁擠度 這個(gè)概念，認(rèn)為 解之間距離開的解比解之間距離小的解更好 擁擠距離排序用于保持解的多樣性。 每個(gè)個(gè)體的擁擠距離是通過計(jì)算與其相鄰的兩個(gè)個(gè)體在每個(gè)子目標(biāo)函數(shù)上的距離差之和來(lái)求取，即下圖中虛線四邊形的長(zhǎng)和寬之和
    
• 每個(gè)父代 P t P_t Pt?都會(huì)通過 交叉和變異 (其中多目標(biāo)遺傳算法中的交叉和變異與傳統(tǒng)遺傳算法中的交叉和變異沒有區(qū)別) 生成子代 Q t Q_t Qt? ,父代和子代的所有個(gè)體集合稱為 R t R_t Rt? ,先通過 非支配排序 選出 R t R_t Rt?中的合適個(gè)體，再通過 擁擠度排序 選出同一Rank層中的個(gè)體，使新的種群集合 P t + 1 P_{t+1} Pt+1? 的個(gè)體數(shù)目為N。 這一過程常常會(huì)使用以下兩種圖進(jìn)行表示：
  
  

---

學(xué)術(shù)多目標(biāo)

NSGA-II算法的今生前世

在遺傳算法在解決多目標(biāo)優(yōu)化遇到瓶頸時(shí)，許多學(xué)者花費(fèi)了不少時(shí)間和精力在多目標(biāo)優(yōu)化的遺傳算法上，Goldberg首先將Pareto最優(yōu)解的概念與適應(yīng)度值概念相關(guān)聯(lián)，即將Pareto非支配排序分層的概念與適應(yīng)度聯(lián)系，排序的層次低，則其分層中個(gè)體的適應(yīng)度值較高，使算法能夠朝著Pareto最優(yōu)前沿進(jìn)化，最終輸出Pareto最優(yōu)解集。在提出此概念后，學(xué)者們陸續(xù)提出了一系列多目標(biāo)遺傳算法，如SPGA、NPGA、FFGA、NSGA等等。但是最能代表Goldberg思想的算法是基于非支配排序的遺傳算法，即NSGA(Non—dominated Sorting Genetic Algorithm)。

科學(xué)家Srinivas和Deb在前人研究基礎(chǔ)上，于1994年首先提出了非支配排序遺傳算法的概念。其算法最主要的思想是 將所有的個(gè)體進(jìn)行分層，并且對(duì)每個(gè)個(gè)體都設(shè)置個(gè)體虛擬適應(yīng)度值同一層中的每個(gè)個(gè)體虛擬適應(yīng)度值相同，層級(jí)數(shù)越低，其適應(yīng)度值越高，遺傳到下一代的概率也就越大。為了使得到的結(jié)果沿Pareto前沿均勻分布，就需要保證非支配層中個(gè)體保持多樣性，為了保持非支配層中個(gè)體多樣性，Srinivas等人采用了共享函數(shù)法。

采用非支配排序的遺傳算法在多目標(biāo)優(yōu)化中得到了廣泛應(yīng)用，但是，隨著其使用越廣泛，其算法也暴露出了一些缺陷。 首先，NSGA算法的時(shí)間復(fù)雜度高，為 O ( m N 3 ) O(mN^3) O(mN3)，m代表目標(biāo)數(shù)，N表示種群規(guī)模大小，當(dāng)種群數(shù)目過多時(shí)，其排序過程必將耗費(fèi)更多時(shí)間，降低了搜索效率。再者，NSGA算法沒有考慮精英策略，精英策略能提高算法的計(jì)算速度，也能將優(yōu)秀個(gè)體保存下來(lái)。更為重要的一點(diǎn)是，其共享半徑參數(shù)是人為設(shè)定的，而共享半徑設(shè)置不合理，將對(duì)計(jì)算結(jié)果產(chǎn)生非常大的影響。

為了克服非支配排序遺傳算法的以上弊端，Deb等學(xué)者于2000年對(duì)NSGA算法進(jìn)行了改進(jìn)，提出了 基于快速非支配排序的遺傳算法NSGA-II，相比NSGA來(lái)說，NSGA-II有如下不同點(diǎn) :

1. 計(jì)算復(fù)雜度 在NSGA計(jì)算中，其排序的復(fù)雜程度為 O ( m N 3 ) O(mN^3) O(mN3)(m代表目標(biāo)函數(shù)個(gè)數(shù)，N表示種群規(guī)模)，而采用NSGA—II算法，其計(jì)算復(fù)雜程度將為 O ( m N 2 ) O(mN^2) O(mN2)，計(jì)算效率得到了提升。
2. 算法中加入了精英策略 其實(shí)現(xiàn)思想是：父代個(gè)體通過遺傳操作產(chǎn)生予代個(gè)體后，選擇操作選擇的個(gè)體數(shù)N需要從父代和子代個(gè)體競(jìng)爭(zhēng)，從中選出最好的，這樣做的目的就是能將最優(yōu)秀的個(gè)體保存下來(lái)。
3. 相比NSGA算法提出的共享半徑，NSGA—II采用了擁擠度的概念 在同一非支配層中，通過判斷個(gè)體周圍的擁擠程度，改善同一支配層面的種群多樣性，不需要設(shè)定比較“敏感”的共享半徑參數(shù)，對(duì)提高算法效率和保持種群多樣性上優(yōu)于NSGA算法。

NSGA-II 該算法求得的 Pareto 最優(yōu)解分布均勻，收斂性和魯棒性好，具有良好的優(yōu)化效果，是求解多目標(biāo)優(yōu)化問題的一種新思路

非支配排序

• 時(shí)間復(fù)雜度 m 個(gè)個(gè)體和種群中的其他個(gè)體進(jìn)行支配關(guān)系比較，是否支配其他全部個(gè)體，復(fù)雜度為O(mN);循環(huán)進(jìn)行直到等級(jí)1 中的非支配個(gè)體全部被搜索到，復(fù)雜度為 O ( m N 2 ) O(mN^2) O(mN2);最壞的情況下,有N個(gè)等 級(jí)，每個(gè)等級(jí)只存在一個(gè)解,復(fù)雜度為 O ( m N 3 ) O(mN^3) O(mN3)
• 算法流程 NSGA—II排序時(shí)需要設(shè)定兩個(gè)參數(shù)用 n i n_i ni?表示種群中所有個(gè)體中支配個(gè)體i的數(shù)目， S i S_i Si?表示種群中個(gè)體被個(gè)體i支配的個(gè)體集合。NSGA-II對(duì)種群個(gè)體進(jìn)行非支配排序的步驟如下：
  1. 找出種群中非支配解的個(gè)體，即 n i = 0 n_i=0 ni?=0的個(gè)體，將非支配個(gè)體放入集合F1中。
  2. 對(duì)于F1中的每個(gè)個(gè)體，找出集合中每個(gè)個(gè)體所支配個(gè)體集合 S i S_i Si?，對(duì) S i S_i Si?中的個(gè)體l，對(duì) n l n_l nl?進(jìn)行減1操作，令 n l = n l ? 1 n_l = n_l-1 nl?=nl??1 ，若 n l n_l nl?大小為0，則將此個(gè)體存放在集合H中。這個(gè)步驟的目的是去掉已經(jīng)挑選出的前沿中個(gè)體的影響，方便對(duì)剩下的個(gè)體進(jìn)行排序。
  3. 定義集合F1為第一層非支配集合，并為F1中每個(gè)個(gè)體標(biāo)記相同的非支配序列 i r a n k i_{rank} irank?。
  4. 對(duì)集合H中的個(gè)體，按照以上步驟1、步驟2和步驟3操作，直至將所有個(gè)體分層。

擁擠度排序

• 目的 同一層非支配個(gè)體集合中，為了保證解的個(gè)體能均勻分配在Pareto前沿，就需要使同一層中的非支配個(gè)體具有多樣性，否則，個(gè)體都在某一處“扎堆”，將無(wú)法得到Pareto最優(yōu)解集。NSGA—II采用了擁擠度策略，即計(jì)算同一非支配層級(jí)中某給定個(gè)體周圍其他個(gè)體的密度。
• 每個(gè)個(gè)體的擁擠距離是通過計(jì)算與其相鄰的兩個(gè)個(gè)體在每個(gè)子目標(biāo)函數(shù)上的距離差之和來(lái)求取。 D i = ( f i + 1 , 1 ? f i ? 1 , 1 ) + ( f i ? 1 , 2 ? f i + 1 , 2 ) D_i=(f_{i+1,1}-f_{i-1},1)+(f_{i-1,2}-f_{i+1,2}) Di?=(fi+1,1??fi?1?,1)+(fi?1,2??fi+1,2?) ,即下圖中虛線四邊形的長(zhǎng)和寬之和。
  

NSGA-II排序算法

• 當(dāng)每個(gè)個(gè)體擁有這兩個(gè)屬性，就可以通過這兩個(gè)屬性判定任意兩個(gè)個(gè)體的支配關(guān)系。當(dāng)兩個(gè)體沒有處在同一非支配層級(jí)時(shí)，通過判斷 i r a n k i_{rank} irank?大小，確定個(gè)體優(yōu)劣， i r a n k i_{rank} irank?值小的個(gè)體比 i r a n k i_{rank} irank?大的個(gè)體更優(yōu)；當(dāng)兩隨機(jī)個(gè)體處于同一非支配層級(jí)時(shí)，依據(jù)個(gè)體擁擠度判定個(gè)體孰優(yōu)孰劣，個(gè)體擁擠度大的比個(gè)體擁擠度小的個(gè)體更優(yōu)

NSGA-II算法流程

NSGA-II算法流程-達(dá)到一定進(jìn)化代數(shù)停止

首先種群初始化，通過快速非支配排序、選擇、交叉以及變異操作后得到初始種群，種群中個(gè)體數(shù)為N；將父代種群和子代種群合并，再通過排序、擁擠度計(jì)算得出下一代種群個(gè)體；得出新一代種群后根據(jù)遺傳操作繼續(xù)產(chǎn)生下一代，如此反復(fù)，直到達(dá)到進(jìn)化最大代數(shù)停止。

NSGA-II算法流程-算法收斂停止

1. 創(chuàng)造一個(gè)初始父代種群 P 0 P_0 P0? 使用交叉和變異操作產(chǎn)生子代種群 Q 0 Q_0 Q0?
2. 對(duì) P 0 P_0 P0? h和 Q 0 Q_0 Q0? 組成的整體 R 0 R_0 R0? 進(jìn)行非支配排序，構(gòu)造所有不同等級(jí)的非支配解集 Z 1 , Z 2 , Z 3 . . . Z_1,Z_2,Z_3 … Z1?,Z2?,Z3?...
3. 對(duì)分好等級(jí)的非支配解集進(jìn)行擁擠距離排序，根據(jù)適應(yīng)度高低得到前 N 個(gè)解，構(gòu)成下一次迭代的父代種群 P 1 P_1 P1?
4. 重復(fù)上述 3 個(gè)步驟，直到結(jié)果收斂

總結(jié)

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

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