多目标優化快速入門
多目标優化--引子
正如生活中，你想買一輛車，又想汽車的性能好，外觀不錯，價格還比較低，對于這同時滿足這三個條件，我們應該如何進行考慮呢？
在投資的時候，我們想投入的資金最少，所付出的風險最小，同時收益是最大的，如何同時進行實作呢？
在數學學習中，求求函數 f1(x1,x2,…,xn)=x1^2+x2^2 +…+xn^2 及函數 f2(x1,x2,…,xn)=(x1-1)^2+(x2-1)^2 +…+(xn-1)^2 同時達到最小的 (x1,x2,…,xn) 的取值，不存在一組 (x1,x2,…,xn) 的取值，使 f1 和 f2 同時達到最小值，這時候怎麼辦呢？
帕累托最優
帕雷托最優是指資源配置設定的一種理想狀态。帕雷托最優的狀态就是不可能再有更多的帕雷托改善的狀态；換句話說，不可能再改善某些人的境況，而不使任何其他人受損。
進化計算
最早的是達爾文的進化論-物競天擇，适者生存
後來是約翰.霍蘭德提出的遺傳算法
1.遺傳算法(Genetic Algorithm, GA)是模拟達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，通過模拟自然進化過程搜尋最優解。
2.該算法通過數學的方式,利用計算機仿真運算,将問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為複雜的組合優化問題時,相對一些正常的優化算法,通常能夠較快地獲得較好的優化結果。
3.遺傳算法已被人們廣泛地應用于組合優化、機器學習、信号處理、自适應控制和人工生命等領域。
具體步驟是：
(1)種群中個體随機初始化.
(2)每個個體通過評價得到一個适應度值.
(3)适應度值大的個體有更大的機率保留下來.
(4)通過對适應度值大的個體交叉變異産生新的個體.
不斷的疊代第 (2)-(4) 步驟，經過足夠多的疊代次後，最終能得到好的解.
基本概念
MOP
1.求解單個函數 f1 的最小值為單目标優化問題(SOP)
2.同時求解多個函數 f1 和 f2 的最小值為多目标優化問題(MOP)
3.多目标優化問題的一般數學描述：
4.對于兩個個體 X1 和 X2 以及目标函數 F(X)，若 X1 的每一個目标函數值 fi(X1) 都比 X2 對應的目标函數值 fi(X2) 要小，則認為 X1 要比 X2 更好，稱 X1 支配(dominate) X2 ，記作 X1 ≺ X2 (它具有傳遞性)
5.若存在 i 和 j 使得 fi(X1) < fi(X2) 且 fj(X1) > fj(X2)， 則認為 X1 和 X2 無法比較，視為一樣好，稱 X1 與 X2 是非支配 (non-dominated)的，記作 X1 ⊀ X2 且 X2 ⊀ X1
6.對于一組個體，若 Xa 不被其它任何一個個體支配，則 Xa 也稱為是非支配的；Xa 也叫做 Pareto 最優解
7.對于一個多目标優化問題，目的是求出一組 Pareto 最優解 Xi ，i=1,2,…，并使得目标函數的值盡可能地小
根據左圖中目标變量可知 ，帕累托最優解往往在左下角，值相對偏小。
在右圖中，可以看出，B支配C,D兩點，在A點，B是被支配的，其餘空間則是非支配
EC
1.想要求得多目标問題的最優解，我們利用計算機強大的計算能力，在決策空間中随機産生大量個體，并找出其中最好的(不被支配的)個體。也就是不斷地“試”，來找到越來越好的個體。随機尋找個體的過程稱為 搜尋
2.但無法做到周遊決策空間中每一個個體，我們需要在更短的時間裡利用随機的方法找到更好的個體
3.利用進化算法的政策，可以朝着越來越好的方向随機産生個體，而不是在決策空間中完全盲目地産生個體
4.作為一個随機性算法，進化算法有如下 特點：
•得到的不是問題的精确結果，而是近似的結果
•每次得到的結果不一樣
•結果的精度随着疊代次數的增加而不斷上升
•往往以算法得到的結果的精度來評價算法的性能
進化算法的一般政策
Indicator
1.不同的算法，産生的結果是不同的，從結果可以看出各個算法性能的好壞
2.算法産生的解集的好壞标準：
•接近真實前沿面(收斂性)
•在空間上分布性好(分布性)
3.還有許多量化的評價解集的好壞的标準
發展曆程
古典多目标時期
傳統的多目标優化方法是将各個子目标聚合成一個帶正系數的單目标函數，系數由決策者決定，或者由優化方法自适應調整。
為了擷取近似Pareto最優集，一些優化方法使用不同的系數來實施動态優化。
常見的古典方法有權重法(利用斜率來判斷最優解)、限制法、目标規劃法以及極大極小法等
進化多目标時期
最早提到可以利用EA來解決多目标優化問題的是Richard S. Rosenburg 于1967年在他的博士論文 “Simulation of genetic populations with biochemical properties”中
David Goldberg 于1989年首次提出了Pareto Ranking的概念：MOEA中個體必須經由Pareto支配關系來選出，同時他也指出了MOEA中分布性保持的重要性，主要采取Fitness Share的政策
Carlos M. Fonseca 和 Peter J. Fleming 于1993年提出了Multiobjective Optimization Genetic Algorithm (MOGA)。MOGA采用基于排序數的适應度指派機制以及自适應的适應度共享的政策，風靡一時
Kalyanmoy Deb于1994年提出了Non-dominated Sorting Genetic Algorithm (NSGA)，采用分層的非支配排序機制以及适應度共享機制。然而算法缺陷是計算複雜度為O(MN3)，随後，Deb跟他的學生在2000年提出了NSGA的改進版本NSGA2，文章于2002年發表TEVC。NSGA2采用快速非支配排序以及擁擠距離的政策，時間複雜度在O(MN2)。由于其速度及效果上的優勢，許多年來NSGA2都被作為對比算法。
Eckart Zitzler 在1998年一個會議上提出Strength Pareto Evolutionary Algorithm (SPEA)，第二年文章被TEVC收錄。SPEA在算法中使用了一個外部Archive來保留搜尋到的好解，稱之為Elitism。Elitism的使用随後也開始流行，随後不久Zitzler等人又對SPEA進行了改進SPEA2，主要引入了較細的适應度指派方式以及密度估計方式(Truncation Method)。
2006年，張青富跟李輝首次提出了基于分解的多目标優化算法，MOEAD，是将MOP問題分解成SOP問題并同時對這些子問題進行優化。MOEAD不僅在速度上有優勢，而且搜到的結果很規律。在MOEA領域開辟了一條新的通道。
2014年，Deb的NSGA3分成上下兩個部分發表在TEVC上。主要是用來處理高維多目标問題。采用了基于參考點以及分解的政策。是NSGA2 + MOEAD 的結合
其中目前最經典的算法還是NSGA-II 和MOEAD,
請持續關注，後期會總結出這些算法的文章。