NSGA-NSGA-I算法詳解課件

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

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

共享小生境技術(shù)

NSGA的缺點：

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

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

i=i+1YNYNi=1

YN

快速非支配排序法

擁擠度比較算子

--