筆者最近在學(xué)習(xí)有關(guān)多目標(biāo)優(yōu)化的內(nèi)容，并對(duì)內(nèi)容進(jìn)行一些整理。這篇文章算是筆者的一篇個(gè)人學(xué)習(xí)筆記，也希望能對(duì)他人提供一定的幫助，若有不足之處，也歡迎指正和建議。

注：本文中所舉例子均為最小化問(wèn)題。

一.多目標(biāo)優(yōu)化的基本概念

?(1)? 多目標(biāo)優(yōu)化問(wèn)題（Multiobjective optimization problem,MOP）

? ? ? ? ? ?一個(gè)多目標(biāo)優(yōu)化問(wèn)題可以用下面的數(shù)學(xué)形式來(lái)表述：

????????????????????????????????

? ? ? ? ? 其中，x為決策向量，所在空間稱為決策空間；F(x)為目標(biāo)向量，所在空間稱為目標(biāo)空間，由m個(gè)目標(biāo)函數(shù)組成，在多目標(biāo)優(yōu)化中，m一般為2或3，相對(duì)應(yīng)的，單目標(biāo)優(yōu)化的m=1.

(2)? ?支配（Dominance）?

? ? ? ? ?對(duì)于兩個(gè)解x與y，若對(duì)于任意i=1,2,...,m，均有fi(x)<=fi(y)，且存在i，使fi(x)<fi(y)，?則稱x支配y，記為。

? ? ? ? ?簡(jiǎn)單記憶方法：全部小于等于，至少1個(gè)小于。

?(3)? ?Pareto最優(yōu)

? ? ? ? ?Pareto最優(yōu)原為經(jīng)濟(jì)學(xué)中的一個(gè)概念，在多目標(biāo)優(yōu)化中，由于對(duì)于不同目標(biāo)的優(yōu)化通常是互相矛盾的，故引入該概念。在多目標(biāo)優(yōu)化中，若對(duì)于解x*，當(dāng)且僅當(dāng)x*不被任何其他解支配，稱x*為Pareto最優(yōu)解，由所有Pareto最優(yōu)解構(gòu)成的集合，稱為Pareto集（Pareto Set），記為PS。相對(duì)應(yīng)的，PS中所有解在目標(biāo)空間中對(duì)應(yīng)的目標(biāo)函數(shù)值的集合稱為Pareto前沿(Pareto Front),記為PF。

? ? ? （注意，Pareto最優(yōu)的概念僅是說(shuō)該解不被其他解支配，并不是說(shuō)該解可以支配其他所有解。）

二.NSGA-II

(1) NSGA-II簡(jiǎn)介

? ? ? ? NSGA-II，全稱為Non-dominated Sorting Genetic Algorithm-II，即非支配排序遺傳算法，是一種基于支配的多目標(biāo)優(yōu)化算法。從其全稱我們可以看出，NSGA-II本質(zhì)上是一種遺傳算法，其選擇、交叉、變異算子均與遺傳算法相同。那么，NSGA-II相較于普通的GA，有什么不同呢？筆者認(rèn)為，NSGA-II主要多了兩個(gè)部分，其一就是其算法名中提到的，非支配排序。其二則是擁擠距離的定義以及基于其的精英保留策略。下面，我們就分開(kāi)來(lái)介紹下這兩個(gè)部分。

?(2) 非支配排序

? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?非支配排序的原理可以用這幅圖來(lái)進(jìn)行解釋，如圖，對(duì)于一整個(gè)種群，首先選出當(dāng)前的Pareto最優(yōu)解，記為支配等級(jí)1；將支配等級(jí)1中的解排除后，再?gòu)氖Ｓ喾N群中選出Pareto最優(yōu)解，記為支配等級(jí)2；以此類(lèi)推，直到整個(gè)種群被分級(jí)完畢。在各支配等級(jí)中，每個(gè)解和當(dāng)前等級(jí)中的其他任意解均互不支配，支配等級(jí)較前（數(shù)字較?。┑慕庵渲涞燃?jí)較后（數(shù)字較大）的解。這就是非支配排序。

? ? ? ?在實(shí)際操作過(guò)程中，由于發(fā)現(xiàn)最初的非支配排序流程時(shí)間復(fù)雜度較高，為,其中M為目標(biāo)數(shù)目，N為種群大小。因此，本文提出了一種快速非支配排序方法，將時(shí)間復(fù)雜度從降為了。其流程如下：

? ? ? 1.對(duì)于種群P中的所有個(gè)體p，統(tǒng)計(jì)支配其的解的個(gè)數(shù)和其支配的個(gè)體的集合。統(tǒng)計(jì)結(jié)束后，將當(dāng)前的個(gè)體全部加入集合中，并計(jì)其支配等級(jí)為1。

? ? ??2.??

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ?令(相當(dāng)于消除支配等級(jí)1的解對(duì)其的支配，即相當(dāng)于將支配等級(jí)1的個(gè)體“移出”當(dāng)前種群)。

? ? ? ? ? ? ? ? ? ? ??if?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(將q加入F2中)

? ? ? ? ? ? ? ? ? ? ? end

? ? ? ? ? ? ? end

? ? ? ? end

? ?3.對(duì)中的個(gè)體，計(jì)其支配等級(jí)為2，并重復(fù)2中的操作，以此類(lèi)推，直到整個(gè)種群排序完畢。

(3)? 擁擠距離

? ? ? ? ?除了非支配排序外，NSGA-II還定義了擁擠距離的概念，我們同樣用圖來(lái)進(jìn)行解釋：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?如圖，對(duì)于二目標(biāo)問(wèn)題，對(duì)于當(dāng)前的解i（圖中黑點(diǎn)i），擁擠距離定義為其相鄰解i-1和i+1所形成的四邊形的周長(zhǎng)，注意，在作圖時(shí)，這個(gè)四邊形中不應(yīng)包含除i外的其他解。由此可見(jiàn)，對(duì)于一個(gè)解，其擁擠距離越大，這個(gè)解周?chē)驮较∈?，選取這樣的解，對(duì)于保持種群的多樣性有益。對(duì)于邊界解（圖中黑點(diǎn)0和l），我們計(jì)其擁擠距離為無(wú)窮。

(4) NSGA-II流程

? ? ? ? 有了快速非支配排序和擁擠距離的概念，我們接下來(lái)就可以闡述NSGA-II的工作流程.

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?如圖是NSGA-II的簡(jiǎn)要流程，首先，對(duì)于當(dāng)前種群,我們使用遺傳算法的選擇、交叉、變異算子，產(chǎn)生與其個(gè)體數(shù)目相同的子代,將和合并，記為,并對(duì)進(jìn)行快速非支配排序，注意，此時(shí)的個(gè)體數(shù)目為2N(,各為N)。

? ? ? ?非支配排序完后，根據(jù)支配等級(jí)順序，依次將各等級(jí)個(gè)體加入下一種群中，直至當(dāng)前等級(jí)個(gè)體不能全部放入為止。如圖中，F(xiàn)1、F2個(gè)體可以全部放入，而F3不能全部放入。

? ? ? ?此時(shí)，對(duì)當(dāng)前等級(jí)個(gè)體(圖中為F3)按照擁擠距離進(jìn)行排序，并將擁擠距離較大的個(gè)體依次加入下一種群中，直到填滿為止（個(gè)體數(shù)達(dá)到N）。此時(shí)，將剩余的解全部淘汰。接下來(lái)的流程依次類(lèi)推，直到達(dá)到終止條件為止。

? ? ? ?通過(guò)對(duì)NSGA-II流程的闡述，我們可以看到，NSGA-II首先會(huì)將支配等級(jí)較前的個(gè)體加入當(dāng)前種群，這是算法對(duì)收斂性的保證；此外，NSGA-II還會(huì)對(duì)最后一層個(gè)體按照擁擠距離排序，優(yōu)先選擇擁擠距離較大的個(gè)體，即邊界解和密度較稀疏的個(gè)體會(huì)被優(yōu)先保留，這體現(xiàn)了算法對(duì)多樣性的保證。因此，NSGA-II算法可以同時(shí)做到對(duì)收斂性和多樣性的保證。

(5) NSGA-II的優(yōu)點(diǎn)與缺點(diǎn)

? ? ? ? NSGA-II的優(yōu)點(diǎn)正如上文提到，由于注意對(duì)邊界解的保留，所以其在解決一些極凸或極凹問(wèn)題時(shí)會(huì)較優(yōu)優(yōu)勢(shì)，可以保留較多的邊界解。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? 如圖為NSGA-II對(duì)于極凸PF面的處理，可以看到，使用NSGA-II可以保留較多的邊界解。

? ? ? ? ? NSGA-II的缺點(diǎn)同樣很明顯，前文也有提到，NSGA-II是一種基于支配的多目標(biāo)優(yōu)化算法。而根據(jù)支配的定義，我們可以看到，當(dāng)多目標(biāo)優(yōu)化問(wèn)題的維度越大時(shí)，我們?cè)诫y找到這種支配關(guān)系，甚至可能無(wú)法找到，從而使整個(gè)種群都互不支配，這樣，基于支配的算法就失去了意義。因此，NSGA-II，以及其他基于支配的多目標(biāo)優(yōu)化算法，都不適合解決高維多目標(biāo)優(yōu)化問(wèn)題（一般我們認(rèn)為m>3即為高維問(wèn)題），或者又稱為Many-Objective Problem（MaOP）。

參考文獻(xiàn)：

????????K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," in IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, April 2002, doi: 10.1109/4235.996017.

????????H. Li, Q. Zhang and J. Deng, "Biased Multiobjective Optimization and Decomposition Algorithm," in IEEE Transactions on Cybernetics, vol. 47, no. 1, pp. 52-66, Jan. 2017, doi: 10.1109/TCYB.2015.2507366.

????????Wang, Z., Li, Q., Yang, Q.?et al.?The dilemma between eliminating dominance-resistant solutions and preserving boundary solutions of extremely convex Pareto fronts.?Complex Intell. Syst.?(2021). https://doi.org/10.1007/s40747-021-00543-2

特別感謝：

????????遺傳算法之NSGA-Ⅱ原理分析和代碼解讀 - 知乎

????????????????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-404492.html

到了這里，關(guān)于[多目標(biāo)優(yōu)化算法]1.NSGA-II——非支配排序遺傳算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！