非支配排序演算法
一、插入排序
介紹
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。
演算法適用於少量數據的排序，時間復雜度為O(n^2)。
插入排演算法是穩定的排序方法。
步驟
①從第一個元素開始，該元素可以認為已經被排序
②取出下一個元素，在已經排序的元素序列中從後向前掃描
③如果該元素（已排序）大於新元素，將該元素移到下一位置
④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
⑤將新元素插入到該位置中
⑥重復步驟2
排序演示
演算法實現
二、冒泡排序
介紹
冒泡排序（Bubble Sort）是一種簡單的排序演算法，時間復雜度為O(n^2)。
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
原理
循環遍歷列表，每次循環找出循環最大的元素排在後面；
需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。
步驟
①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
③針對所有的元素重復以上的步驟，除了最後一個。
④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
演算法實現：
三、快速排序
介紹
快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。
基本思想
快速排序的基本思想是：挖坑填數 + 分治法。
首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
實現步驟
①從數列中挑出一個元素，稱為 「基準」（pivot）；
②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；
③對所有兩個小數列重復第二步，直至各區間只有一個數。
排序演示
演算法實現
四、希爾排序
介紹
希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法，時間復雜度為：O(1.3n)。
希爾排序是基於插入排序的以下兩點性質而提出改進方法的：
·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；
·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。
基本思想
①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；
②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。
排序演示
演算法實現
五、選擇排序
介紹
選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。
基本思想
選擇排序的基本思想：比較 + 交換。
第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；
第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；
以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。
排序演示
選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。
演算法實現
六、堆排序
介紹
堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。
利用數組的特點快速指定索引的元素。
基本思想
堆分為大根堆和小根堆，是完全二叉樹。
大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。
在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
排序演示
演算法實現
七、歸並排序
介紹
歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
基本思想
歸並排序演算法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。
演算法思想
自上而下遞歸法（假如序列共有n個元素）
① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；
② 將上述序列再次歸並，形成 floor(n/4)個序列，每個序列包含四個元素；
③ 重復步驟②，直到所有元素排序完畢。
自下而上迭代法
① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；
② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；
④ 重復步驟③直到某一指針達到序列尾；
⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。
排序演示
演算法實現
八、基數排序
介紹
基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。
基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。
在某些時候，基數排序法的效率高於其他的穩定性排序法。
基本思想
將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。
基數排序按照優先從高位或低位來排序有兩種實現方案：
MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。
LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。
排序效果
演算法實現
九、總結
各種排序的穩定性、時間復雜度、空間復雜度的總結：
平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；
從時間復雜度來說：
線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；
O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；
線性階O(n)排序：基數排序，此外還有桶、箱排序。
2. 多目標優化問題
形式化定義：
特點：
①包含多個可能有沖突的目標函數。
②希望找到能夠很好平衡全部優化目標的解集；
帕累托最優是指資源分配的一種理想狀態。給定固有的一群人和可分配的資源，如果從一種分配狀態到另一種分配狀態，在沒有使得任何人的境況變壞的前提下，使得至少有一個人變得更好，這就是帕累托改善的狀態；換言之，不可能在不是任何其他人受損的情況下再改善某些人的境況。
支配（Dominace） ：當x1和x2滿足如下條件時稱x1支配x2：①對於所有目標函數x1不比x2差；②至少在一個目標函數上，x1嚴格比x2要好。
對於點1和點2：對於目標函數f1是越大越好，在取相同f2時，點1比點2好；對於目標函數f2是越小越好，在取相同f1時，點1比點2好。所以點1支配點2。
對於點1和點4：目標函數f1上，取相同f2時，點4比點1好；目標函數f2上，取相同f1時，點1比點4好。所以點1和點4互不支配。
不可支配解集（Non-dominated solution set） ：當一個解集中任何一個解都不能被該集合中其他解支配，那麼就稱該解集為不可支配解集。
帕累托最優解集（Pareto-optimal set ）：所有可行中的不可支配解集被稱為帕累托最優解集。
帕累托最優前沿面（Pareto-optimal front） ：帕累托最優解集的邊界（boundary）被稱為帕累托最優前沿面。
多目標優化問題的目標 ：①尋找盡可能接近最優的解集；②盡可能增大找到解的多樣性。
優點：簡單
缺點：①很難設定一個權重向量能夠獲得帕累托最優解；②在一些非凸情況下不能夠保證獲得帕累托最優解。
優點：能夠應用到凸函數和非凸函數場景下。
缺點：函數需要精心選擇，需要在獨立函數的最小值或最大值之內。
優點：weighted Techebycheff metirc能夠保證獲得所有帕累托最優解。
缺點：①需要有每個函數最大值和最小值的先驗知識；②需要每個目標函數的z*能夠獨立被找到；③對於較小的p值，不一定保證所有能夠獲得所有的帕累托最優解；④隨著p增加，問題會變得不可求導。
①隨機產生初始種群；
②計算各點的目標函數值和約束函數值；
③根據目標函數值對種群分級；
④根據約束函數值和分級結果計算各點的約束罰項、劣解罰項及總罰項；
⑤根據各點的總罰項計算適應度；
⑥根據各點的適應度，進行選擇、交叉和變異操作，生成新種群；
⑦將總罰項為0的點放入非劣解集候選表，對候選表進行檢查，保留第1級非劣點，刪除其他點；
⑧檢查是否收斂，如沒有，轉到步驟②；
⑨刪除候選表中與其他店距離太近的點；
⑩輸出候選表中的帕累托最優解集及對應的目標函數值；
最後，決策人根據個人偏好從帕累托最優解集中挑選出最適合該問題的解。
遺傳演算法相比傳統的演算法的優點是能夠得到一個最優解集，而不是單單一個最優解，這樣會提供更多的選擇，但是計算的復雜度可能稍高，而且裡面涉及的一些函數需要精心設計。
1.權重系數轉換法
對每個目標函數fi(x)賦予權重wi，wi為目標函數的重要程度。μ=Σwi·fi(x)，這里就將多目標轉化為單目標函數，將μ作為評價函數。
2.並列選擇法
主要步驟：(1)將種群按照目標函數個數等分為子種群，為每個子種群分配一個目標函數。(2)將子種群中的個體按照各自的目標函數選擇出適應度高的個體，然後將其組成一個子種群。(3)再將子種群進行交配、變異、生成下一代父親種群。然後再重復第一步。
並列選擇法的缺點在於易於生成單個目標函數的極端最優解，而較難生成一種多個目標在某種程度上都比較滿意的折中解。
3.排序選擇法
基本思想就是基於「帕累托最優個體」的概念對群體中的個體進行排序，然後根據這個次序進行種群選擇。這樣的話，就能夠讓帕累托最優個體有更多的機會遺傳到下一代。這種方法的缺點是僅僅度量了各個個體之間的優越次序，而並未度量各個個體的分散程度，所以容易生成相似的解，而不是分布較廣的多個最優解。
4.共享函數法
針對排序選擇方法的缺點，即所求的幾個最優解通常都是集中於最優解集合的某一個小區域內，而不是分散在整個帕累托最優解集合。由此，引出了基於共享函數的 小生境技術 （小生境技術就是將每一代個體劃分為若干類，每個類中選出若干適應度較大的個體作為一個類的優秀代表組成一個群，再在種群中，以及不同種群中之間，雜交，變異產生新一代個體群。同時採用預選擇機制和排擠機制或分享機制完成任務。）。該演算法對相同個體或類似個體的數目加以限制，以便能夠產生出種類較多的不同的最優解。這就引出一個問題，怎麼衡量兩個個體之間的相似度？這就是小生境數。顧名思義，小生境就是在一個小環境中相似的個體種群。最常見的公式為：
s(d)為共享函數，是表示群體中兩個個體之間密切關系程度的一個函數。d(X,Y)為個體X,Y之間的hanmin距離，也是用於衡量個體間相似度的一個函數。在計算出小生境數後，可以是小生境數較小的個體能夠有更多的機會被選中，遺傳到下一代群體中，即相似程度較小的個體能夠有更多的機會被遺傳到下一代群體中。
缺點：每次選擇操作時都需要進行大量的個體之間的優越關系的評價和比較運算，使得演算法搜索效率較低。
5.Horn和Nafploitis印的基於小生境帕累托多目標遺傳演算法(NPGA)
類似於第2個的並列選擇法，將每一代個體劃分為若干類，每個類別選出若干適應度較大的個體作為一個類的優秀代表組成一個種群，然後交配變異產生新一代種群。基於這種小生境的遺傳演算法（Niched Genetic Algorithms，NGA），可以更好地保持解的多樣性，同時具有很高的全局尋優能力和收斂速度，特別適合於復雜多峰函數的優化問題。
6.Srinvivas和Deb的非支配排序遺傳演算法NSGA
1980年提出來的，在遺傳演算法的基礎上對選擇再生方法進行改進：將每個個體按照他們的支配和非支配關系進行再分層，再做選擇操作，從而達到目的。
其分層的含義就是取出種群中的非支配個體組成一個小種群（第一個非支配最優層），並賦予其中所有個體一個共享的虛擬適應度值。然後再取出個體後的種群中繼續取出非支配個體，再將它們組成一個小種群（第二個非支配最優層），並且賦予所有個體一個共享的虛擬適應度值。重復上述步驟，直到原始種群分配完畢，這就是分層，也叫非支配型排序。
非支配型排序遺傳演算法的缺點：①計算復雜度較高；②沒有精英策略；③需要制定共享半徑。
針對以上問題，k·Deb 於2002年提出了 7 的方法。
7.帶精英策略的非支配排序遺傳散發——NSGAII
1).採用快速非支配型排序，降低了演算法復雜度。其復雜度降為了O(MN**2)。
2).提出了擁擠度和擁擠度比較運算元，代替需要指定共享半徑的適應度共享策略。並在快速排序後的同級比較中作為勝出標准。使准pareto解中的個體能擴展到整個pareto域中，並均勻分布，保持了種群的多樣性。
3).引入精英策略，擴大采樣空間。將父代種群和子代種群合並，保證優良個體能夠留存下來。
其演算法步驟如下：1.首先隨機產生數量為n的初始種群，然後對其進行非支配型排序。接下來，就是常規的選擇，交叉，變異操作產生第一代子代種群。2.然後，從第二代開始，將父代和子代合並。然後對其進行快速非支配型排序，同時計算每個非支配層的個體進行擁擠度的計算。然後根據非支配關系和擁擠度來選擇合適的個體組成新的父代種群。最後通過再通過選擇，交叉，變異產生子代。3.接下來，重復第二步。
具體做法參考：https://blog.csdn.net/quinn1994/article/details/80679528/
3. 學習多目標優化需要掌握哪些python知識
多目標優化
目標優化問題一般地就是指通過一定的優化演算法獲得目標函數的最優化解。當優化的目標函數為一個時稱之為單目標優化(Single-
objective Optimization Problem,
SOP)。當優化的目標函數有兩個或兩個以上時稱為多目標優化(Multi-objective Optimization Problem,
MOP)。不同於單目標優化的解為有限解，多目標優化的解通常是一組均衡解。
多目標優化演算法歸結起來有傳統優化演算法和智能優化演算法兩大類。
1. 傳統優化演算法包括加權法、約束法和線性規劃法等，實質上就是將多目標函數轉化為單目標函數，通過採用單目標優化的方法達到對多目標函數的求解。
2. 智能優化演算法包括進化演算法（Evolutionary Algorithm, 簡稱EA）、粒子群演算法（Particle Swarm Optimization, PSO）等。
Pareto最優解：
若x*∈C*,且在C中不存在比x更優越的解x，則稱x*是多目標最優化模型式的Pareto最優解，又稱為有效解。
一般來說，多目標優化問題並不存在一個最優解，所有可能的解都稱為非劣解，也稱為Pareto解。傳統優化技術一般每次能得到Pareo解集中的一個，而
用智能演算法來求解，可以得到更多的Pareto解，這些解構成了一個最優解集，稱為Pareto最優解。它是由那些任一個目標函數值的提高都必須以犧牲其
他目標函數值為代價的解組成的集合,稱為Pareto最優域，簡稱Pareto集。
Pareto有效(最優)解非劣解集是指由這樣一些解組成的集合：與集合之外的任何解相比它們至少有一個目標函數比集合之外的解好。
求解多目標優化問題最有名的就是NSGA-II了，是多目標遺傳演算法，但其對解的選擇過程可以用在其他優化演算法上，例如粒子群，蜂群等等。這里簡單介紹一下NSGA-II的選擇演算法。主要包含三個部分：
1. 快速非支配排序
要先講一下支配的概念，對於解X1和X2，如果X1對應的所有目標函數都不比X2大（最小問題），且存在一個目標值比X2小，則X2被X1支配。
快速非支配排序是一個循環分級過程：首先找出群體中的非支配解集，記為第一非支配層，irank=1（irank是個體i的非支配值），將其從群體中除去，繼續尋找群體中的非支配解集，然後irank=2。
2. 個體擁擠距離
為了使計算結果在目標空間比較均勻的分布，維持種群多樣性，對每個個體計算擁擠距離，選擇擁擠距離大的個體，擁擠距離的定義為：
L[i]d=L[i]d+(L[i+1]m−L[i−1]m)/(fmaxm−fminm)
L[i+1]m是第i+1個個體的第m目標函數值，fmaxm 和 fminm是集合中第m個目標函數的最大和最小值。
3. 精英策略選擇
精英策略就是保留父代中的優良個體直接進入子代，防止獲得的Pareto最優解丟失。將第t次產生的子代種群和父代種群合並，然後對合並後的新種群進行非支配排序，然後按照非支配順序添加到規模為N的種群中作為新的父代。
4. NSGA_2需不需要像遺傳演算法那樣計算適應度函數
不需要的，NSGA-II里直接通過非支配排序來分級，後面再根據分級和精英保留策略來選擇更好的解
5. NSGA2演算法
多目標的遺傳演算法。剛看的。希望能幫助你……
其實其他方面都和普通的遺傳演算法差不多，只是在選擇之前，要進行非支配排序，並且要計算crowding distance，選擇的時候，選擇非支配的rank小的，如果同意的rank時，選擇distance大的。