高小艷

摘 要 遺傳算法通過(guò)模擬生物自適應(yīng)選擇過(guò)程和自適應(yīng)進(jìn)化過(guò)程，通過(guò)不斷迭代逼近最優(yōu)解，可以將其用于求解高度復(fù)雜的非線性最優(yōu)值問(wèn)題，多目標(biāo)遺傳算法在優(yōu)化多目標(biāo)問(wèn)題時(shí)具有良好的效果。本文在簡(jiǎn)單遺傳算法的理論基礎(chǔ)上，主要著重的介紹了NSGA與NSGA-II算法，得出，改進(jìn)后的算法時(shí)間開銷有所降低，既保證了種群的多樣性，同時(shí)引入擁擠距離排序機(jī)制使算法避免了預(yù)先設(shè)定參數(shù)的困難。

關(guān)鍵詞 多目標(biāo)優(yōu)化 遺傳算法 最優(yōu)解 生物進(jìn)化算法

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A

0前言

19世紀(jì)70年代初期，由于受到達(dá)爾文進(jìn)化理論的啟發(fā)，Rosenberg提出了采用達(dá)爾文進(jìn)化理論的思想解決多目標(biāo)優(yōu)化問(wèn)題。1993 年，Deb和 Srinivas 首先提出基于非劣分級(jí)排序的遺傳算法（NSGA）。Hom 提出 Pareto 遺傳算法。NSGA-II是針對(duì)原NSGA算法存在的不足的改進(jìn)，2002 年 Deb提出帶有精英策略的非劣分級(jí)排序的遺傳算法（NSGA-II），該算法通過(guò)采用快速分級(jí)排序以及精英策略，能夠提高算法收斂速度及保持結(jié)果多樣性。目前，NSGA-II算法已經(jīng)成為解決多目標(biāo)優(yōu)化問(wèn)題的優(yōu)秀算法，被廣泛應(yīng)用到科學(xué)工程領(lǐng)域等。

1 Pareto占優(yōu)

對(duì)于多目標(biāo)優(yōu)化問(wèn)題，通常存在一個(gè)解集，這些解之間就全體目標(biāo)函數(shù)而言是無(wú)法比較優(yōu)劣的，其特點(diǎn)是：無(wú)法在改進(jìn)任何目標(biāo)函數(shù)的同時(shí)不削弱至少一個(gè)其他目標(biāo)函數(shù)。這種解稱作非支配解或Pareto最優(yōu)解。對(duì)于組成Pareto最優(yōu)解集的所有Pareto最優(yōu)解，其對(duì)應(yīng)目標(biāo)空間中的目標(biāo)矢量所構(gòu)成的曲面稱作Pareto最優(yōu)前沿。

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

2 NSGA算法

NSGA-II擁擠度比較算子：經(jīng)過(guò)前面的快速非支配排序和擁擠度計(jì)算之后，種群中的每個(gè)個(gè)體i都擁有倆個(gè)屬性：非支配排序決定的配置配序irank和擁擠度id。只要下面任意一個(gè)條件成立，則個(gè)體i獲勝。勝出的個(gè)體進(jìn)入下一個(gè)操作。

（1）如果個(gè)體i所處的非支配層優(yōu)于個(gè)體j所處的非支配層，即irank

（2）如果他們具有相同的等級(jí)，且個(gè)體i比個(gè)體j有一個(gè)更大的擁擠距離，即：。

4結(jié)語(yǔ)

NSGA-II與NSGA比較而言，采用了快速非劣排序，新的多樣性保持策略，使得其計(jì)算復(fù)雜度由原來(lái)的為O（MN3）降低到O（MN2）（其中M為目標(biāo)數(shù)量，N為種群大?。?。

采用了擁擠度和擁擠度比較算子，不但克服了NSGA中需要人為指定共享參數(shù)的缺陷，而且將其將其作為種群中個(gè)體的比較標(biāo)準(zhǔn)，使得準(zhǔn)Pareto域中的個(gè)體能均勻地?cái)U(kuò)展到整個(gè)Pareto域，保證了種群的多樣性。

參考文獻(xiàn)

[1] 郭修豪. 改進(jìn)遺傳算法在多目標(biāo)問(wèn)題上的應(yīng)用研究[D].重慶師范大學(xué)，2016.

[2] 徐磊. 基于遺傳算法的多目標(biāo)優(yōu)化問(wèn)題的研究與應(yīng)用[D].中南大學(xué)，2007.

[3] 魏靜. 基于改進(jìn)NSGA2算法的給水管網(wǎng)多目標(biāo)優(yōu)化設(shè)計(jì)[D].北京工業(yè)大學(xué)，2016.