多目標(biāo)優(yōu)化問題（Multi-Objective Optimization，MOO）
形式化定義：
特點(diǎn)：
①包含多個(gè)可能有沖突的目標(biāo)函數(shù)。
②希望找到能夠很好平衡全部優(yōu)化目標(biāo)的解集；
帕累托最優(yōu)（Pareto Optimal）
帕累托最優(yōu)是指資源分配的一種理想狀態(tài)。給定固有的一群人和可分配的資源，如果從一種分配狀態(tài)到另一種分配狀態(tài)，在沒有使得任何人的境況變壞的前提下，使得至少有一個(gè)人變得更好，這就是帕累托改善的狀態(tài)；換言之，不可能在不是任何其他人受損的情況下再改善某些人的境況。
支配（Dominace）：當(dāng)x1和x2滿足如下條件時(shí)稱x1支配x2：①對于所有目標(biāo)函數(shù)x1不比x2差；②至少在一個(gè)目標(biāo)函數(shù)上，x1嚴(yán)格比x2要好。
對于點(diǎn)1和點(diǎn)2：對于目標(biāo)函數(shù)f1是越大越好，在取相同f2時(shí)，點(diǎn)1比點(diǎn)2好；對于目標(biāo)函數(shù)f2是越小越好，在取相同f1時(shí)，點(diǎn)1比點(diǎn)2好。所以點(diǎn)1支配點(diǎn)2。
對于點(diǎn)1和點(diǎn)4：目標(biāo)函數(shù)f1上，取相同f2時(shí)，點(diǎn)4比點(diǎn)1好；目標(biāo)函數(shù)f2上，取相同f1時(shí)，點(diǎn)1比點(diǎn)4好。所以點(diǎn)1和點(diǎn)4互不支配。
不可支配解集（Non-dominated solution set）：當(dāng)一個(gè)解集中任何一個(gè)解都不能被該集合中其他解支配，那么就稱該解集為不可支配解集。
帕累托最優(yōu)解集（Pareto-optimal set）：所有可行中的不可支配解集被稱為帕累托最優(yōu)解集。
帕累托最優(yōu)前沿面（Pareto-optimal front）：帕累托最優(yōu)解集的邊界（boundary）被稱為帕累托最優(yōu)前沿面。
多目標(biāo)優(yōu)化問題的目標(biāo)：①尋找盡可能接近最優(yōu)的解集；②盡可能增大找到解的多樣性。
多目標(biāo)優(yōu)化問題的經(jīng)典方法
線性加權(quán)法（Weighted Sum Method）
優(yōu)點(diǎn)：簡單
缺點(diǎn)：①很難設(shè)定一個(gè)權(quán)重向量能夠獲得帕累托最優(yōu)解；②在一些非凸情況下不能夠保證獲得帕累托最優(yōu)解。
ε-constraint method，只保留一個(gè)目標(biāo)函數(shù)，其他目標(biāo)函數(shù)被設(shè)定的值約束。
優(yōu)點(diǎn)：能夠應(yīng)用到凸函數(shù)和非凸函數(shù)場景下。
缺點(diǎn)：函數(shù)需要精心選擇，需要在獨(dú)立函數(shù)的最小值或最大值之內(nèi)。
Weighted Metric Method
優(yōu)點(diǎn)：weighted Techebycheff metirc能夠保證獲得所有帕累托最優(yōu)解。
缺點(diǎn)：①需要有每個(gè)函數(shù)最大值和最小值的先驗(yàn)知識；②需要每個(gè)目標(biāo)函數(shù)的z*能夠獨(dú)立被找到；③對于較小的p值，不一定保證所有能夠獲得所有的帕累托最優(yōu)解；④隨著p增加，問題會變得不可求導(dǎo)。
Multi-Objective Genetic Algorithms，即基于遺傳算法的多目標(biāo)優(yōu)化問題，就是利用遺傳算法的原理來搜索帕累托最優(yōu)前沿面，基本流程如下：
①隨機(jī)產(chǎn)生初始種群；
②計(jì)算各點(diǎn)的目標(biāo)函數(shù)值和約束函數(shù)值；
③根據(jù)目標(biāo)函數(shù)值對種群分級；
④根據(jù)約束函數(shù)值和分級結(jié)果計(jì)算各點(diǎn)的約束罰項(xiàng)、劣解罰項(xiàng)及總罰項(xiàng)；
⑤根據(jù)各點(diǎn)的總罰項(xiàng)計(jì)算適應(yīng)度；
⑥根據(jù)各點(diǎn)的適應(yīng)度，進(jìn)行選擇、交叉和變異操作，生成新種群；
⑦將總罰項(xiàng)為0的點(diǎn)放入非劣解集候選表，對候選表進(jìn)行檢查，保留第1級非劣點(diǎn)，刪除其他點(diǎn)；
⑧檢查是否收斂，如沒有，轉(zhuǎn)到步驟②；
⑨刪除候選表中與其他店距離太近的點(diǎn)；
⑩輸出候選表中的帕累托最優(yōu)解集及對應(yīng)的目標(biāo)函數(shù)值；
最后，決策人根據(jù)個(gè)人偏好從帕累托最優(yōu)解集中挑選出最適合該問題的解。
遺傳算法相比傳統(tǒng)的算法的優(yōu)點(diǎn)是能夠得到一個(gè)最優(yōu)解集，而不是單單一個(gè)最優(yōu)解，這樣會提供更多的選擇，但是計(jì)算的復(fù)雜度可能稍高，而且里面涉及的一些函數(shù)需要精心設(shè)計(jì)。
使用遺傳算法解決帕累托最優(yōu)解問題有以下方法：
1.權(quán)重系數(shù)轉(zhuǎn)換法
對每個(gè)目標(biāo)函數(shù)fi(x)賦予權(quán)重wi，wi為目標(biāo)函數(shù)的重要程度。μ=Σwi·fi(x)，這里就將多目標(biāo)轉(zhuǎn)化為單目標(biāo)函數(shù)，將μ作為評價(jià)函數(shù)。
2.并列選擇法
主要步驟：(1)將種群按照目標(biāo)函數(shù)個(gè)數(shù)等分為子種群，為每個(gè)子種群分配一個(gè)目標(biāo)函數(shù)。(2)將子種群中的個(gè)體按照各自的目標(biāo)函數(shù)選擇出適應(yīng)度高的個(gè)體，然后將其組成一個(gè)子種群。(3)再將子種群進(jìn)行交配、變異、生成下一代父親種群。然后再重復(fù)第一步。
并列選擇法的缺點(diǎn)在于易于生成單個(gè)目標(biāo)函數(shù)的極端最優(yōu)解，而較難生成一種多個(gè)目標(biāo)在某種程度上都比較滿意的折中解。
3.排序選擇法
基本思想就是基于“帕累托最優(yōu)個(gè)體”的概念對群體中的個(gè)體進(jìn)行排序，然后根據(jù)這個(gè)次序進(jìn)行種群選擇。這樣的話，就能夠讓帕累托最優(yōu)個(gè)體有更多的機(jī)會遺傳到下一代。這種方法的缺點(diǎn)是僅僅度量了各個(gè)個(gè)體之間的優(yōu)越次序，而并未度量各個(gè)個(gè)體的分散程度，所以容易生成相似的解，而不是分布較廣的多個(gè)最優(yōu)解。
4.共享函數(shù)法
針對排序選擇方法的缺點(diǎn)，即所求的幾個(gè)最優(yōu)解通常都是集中于最優(yōu)解集合的某一個(gè)小區(qū)域內(nèi)，而不是分散在整個(gè)帕累托最優(yōu)解集合。由此，引出了基于共享函數(shù)的小生境技術(shù)（小生境技術(shù)就是將每一代個(gè)體劃分為若干類，每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)群，再在種群中，以及不同種群中之間，雜交，變異產(chǎn)生新一代個(gè)體群。同時(shí)采用預(yù)選擇機(jī)制和排擠機(jī)制或分享機(jī)制完成任務(wù)。）。該算法對相同個(gè)體或類似個(gè)體的數(shù)目加以限制，以便能夠產(chǎn)生出種類較多的不同的最優(yōu)解。這就引出一個(gè)問題，怎么衡量兩個(gè)個(gè)體之間的相似度？這就是小生境數(shù)。顧名思義，小生境就是在一個(gè)小環(huán)境中相似的個(gè)體種群。最常見的公式為：
s(d)為共享函數(shù)，是表示群體中兩個(gè)個(gè)體之間密切關(guān)系程度的一個(gè)函數(shù)。d(X,Y)為個(gè)體X,Y之間的hanmin距離，也是用于衡量個(gè)體間相似度的一個(gè)函數(shù)。在計(jì)算出小生境數(shù)后，可以是小生境數(shù)較小的個(gè)體能夠有更多的機(jī)會被選中，遺傳到下一代群體中，即相似程度較小的個(gè)體能夠有更多的機(jī)會被遺傳到下一代群體中。
缺點(diǎn)：每次選擇操作時(shí)都需要進(jìn)行大量的個(gè)體之間的優(yōu)越關(guān)系的評價(jià)和比較運(yùn)算，使得算法搜索效率較低。
5.Horn和Nafploitis印的基于小生境帕累托多目標(biāo)遺傳算法(NPGA)
類似于第2個(gè)的并列選擇法，將每一代個(gè)體劃分為若干類，每個(gè)類別選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群，然后交配變異產(chǎn)生新一代種群。基于這種小生境的遺傳算法（Niched Genetic Algorithms，NGA），可以更好地保持解的多樣性，同時(shí)具有很高的全局尋優(yōu)能力和收斂速度，特別適合于復(fù)雜多峰函數(shù)的優(yōu)化問題。
6.Srinvivas和Deb的非支配排序遺傳算法NSGA
1980年提出來的，在遺傳算法的基礎(chǔ)上對選擇再生方法進(jìn)行改進(jìn)：將每個(gè)個(gè)體按照他們的支配和非支配關(guān)系進(jìn)行再分層，再做選擇操作，從而達(dá)到目的。
其分層的含義就是取出種群中的非支配個(gè)體組成一個(gè)小種群（第一個(gè)非支配最優(yōu)層），并賦予其中所有個(gè)體一個(gè)共享的虛擬適應(yīng)度值。然后再取出個(gè)體后的種群中繼續(xù)取出非支配個(gè)體，再將它們組成一個(gè)小種群（第二個(gè)非支配最優(yōu)層），并且賦予所有個(gè)體一個(gè)共享的虛擬適應(yīng)度值。重復(fù)上述步驟，直到原始種群分配完畢，這就是分層，也叫非支配型排序。
非支配型排序遺傳算法的缺點(diǎn)：①計(jì)算復(fù)雜度較高；②沒有精英策略；③需要制定共享半徑。
針對以上問題，k·Deb 于2002年提出了 7 的方法。
7.帶精英策略的非支配排序遺傳散發(fā)——NSGAII
1).采用快速非支配型排序，降低了算法復(fù)雜度。其復(fù)雜度降為了O(MN**2)。
2).提出了擁擠度和擁擠度比較算子，代替需要指定共享半徑的適應(yīng)度共享策略。并在快速排序后的同級比較中作為勝出標(biāo)準(zhǔn)。使準(zhǔn)pareto解中的個(gè)體能擴(kuò)展到整個(gè)pareto域中，并均勻分布，保持了種群的多樣性。
3).引入精英策略，擴(kuò)大采樣空間。將父代種群和子代種群合并，保證優(yōu)良個(gè)體能夠留存下來。
其算法步驟如下：1.首先隨機(jī)產(chǎn)生數(shù)量為n的初始種群，然后對其進(jìn)行非支配型排序。接下來，就是常規(guī)的選擇，交叉，變異操作產(chǎn)生第一代子代種群。2.然后，從第二代開始，將父代和子代合并。然后對其進(jìn)行快速非支配型排序，同時(shí)計(jì)算每個(gè)非支配層的個(gè)體進(jìn)行擁擠度的計(jì)算。然后根據(jù)非支配關(guān)系和擁擠度來選擇合適的個(gè)體組成新的父代種群。最后通過再通過選擇，交叉，變異產(chǎn)生子代。3.接下來，重復(fù)第二步。
具體做法參考：https://blog.csdn.net/quinn1994/article/details/80679528/
