NSGA-NSGA-I算法詳解課件

Pareto占優(yōu)對(duì)于多目標(biāo)優(yōu)化問題，通常存在一個(gè)解集，這些解之間就全體目標(biāo)函數(shù)而言是無法比較優(yōu)劣的，其特點(diǎn)是:無法在改進(jìn)任何目標(biāo)函數(shù)的同時(shí)不削弱至少一個(gè)其他目標(biāo)函數(shù)。這種解稱作非支配解或Pareto最優(yōu)解.Pareto最優(yōu)解Pareto最優(yōu)前沿對(duì)于組成Pareto最優(yōu)解集的所有Pareto最優(yōu)解，其對(duì)應(yīng)目標(biāo)空間中的目標(biāo)矢量所構(gòu)成的曲面稱作Pareto最優(yōu)前沿.NSGA非支配排序遺傳算法NSGA與簡(jiǎn)單的遺傳算法的主要區(qū)別在于:該算法在選擇算子執(zhí)行之前根據(jù)個(gè)體之間的支配關(guān)系進(jìn)行了分層。其選擇算子、交叉算子和變異算子與簡(jiǎn)單遺傳算法沒有區(qū)別.NSGA采用的非支配分層方法，可以使好的個(gè)體有更大的機(jī)會(huì)遺傳到下一代;適應(yīng)度共享策略則使得準(zhǔn)Pareto面上的個(gè)體均勻分布，保持了群體多樣性，克服了超級(jí)個(gè)體的過度繁殖，防止了早熟收斂.開始終止進(jìn)化代數(shù)Gen=0,初始化種群Front=1進(jìn)化代數(shù)Gen小于最大代數(shù)根據(jù)虛擬適應(yīng)度進(jìn)行復(fù)制交叉變異種群全部分級(jí)Gen=Gen+1識(shí)別非支配個(gè)體指定虛擬適應(yīng)度值應(yīng)用于適用度共享小生境Front=Front+1YNYN

非支配排序原理種群分層結(jié)束后，需要給每級(jí)指定一個(gè)虛擬適應(yīng)度值，級(jí)別越小，說明其中的個(gè)體越優(yōu)，賦予越高的虛擬適應(yīng)值，反之級(jí)別越大，賦予越低的虛擬適應(yīng)值。這樣可以保證在復(fù)制操作中級(jí)別越小的非支配個(gè)體有更多的機(jī)會(huì)被選擇進(jìn)入下一代，使得算法以最快的速度收斂于最優(yōu)區(qū)域。比如第一級(jí)非支配層的個(gè)體標(biāo)上虛擬適應(yīng)值為1，第二級(jí)非支配層的個(gè)體標(biāo)上虛擬適應(yīng)值為0.9(或其他)，以此類推，直到所有的個(gè)體都被標(biāo)上虛擬適應(yīng)值。但是由于同一級(jí)非支配層中的個(gè)體擁有相同的適應(yīng)度值，某些個(gè)體在遺傳操作中可能被遺棄，導(dǎo)致最優(yōu)解集不具有多樣性，為了得到分布均勻的Pareto最優(yōu)解集，就要保證當(dāng)前非支配層上的個(gè)體具有多樣性。

共享小生境技術(shù)

NSGA的缺點(diǎn)：

帶精英策略的非支配排序遺傳算NSGA-Ⅱ開始輸出進(jìn)化代數(shù)Gen=1,初始化種群

Gen=最大代數(shù)Gen=Gen+1交叉,變異

i=i+1YNYNi=1

YN

快速非支配排序法

擁擠度比較算子

--