遺傳演算法復雜度

Ⅶ 多目標優化問題

形式化定義：

特點：

①包含多個可能有沖突的目標函數。

②希望找到能夠很好平衡全部優化目標的解集；

帕累托最優是指資源分配的一種理想狀態。給定固有的一群人和可分配的資源，如果從一種分配狀態到另一種分配狀態，在沒有使得任何人的境況變壞的前提下，使得至少有一個人變得更好，這就是帕累托改善的狀態；換言之，不可能在不是任何其他人受損的情況下再改善某些人的境況。

支配（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/

Ⅷ 遺傳演算法和粒子群演算法比較過程中，可以用那些指標進行比較

時間復雜度、空間復雜度、穩定性、求解精度等等

Ⅸ 請問簡單遺傳演算法的時間復雜度和空間復雜度是多少

遺傳演算法其實就是二重迭代，時間復雜度不超過n平方
空間復雜度自己計算吧

Ⅹ 請問怎樣確定遺傳演算法的參數

遺傳演算法的參數設計對於不同的實際問題都不同
目前還沒有完整的理論來參考

種群大小越大 收斂效果越好 但計算量也會增大
在空間復雜度（內存大小）和計算速度允許的情況下 盡量大一些 不過如果問題的解空間不大或者是變化的話 則要另加考慮（解空間不大就沒必要把種群定得很大了）

交叉率。。。一般都是全部參與交叉（染色體都會交叉嘛） 只是交叉方式的設計問題，有單點，多點，隨機等等 另外還要考慮交叉後解的可行性 對於具體問題，可以各種方法都試一下（這方面的理論實在是很弱）

變異率不要設高，一般在%5以下，變異是為了避免把個體局限在較優的局部解空間內（模擬退火演算法就有這個問題，所以經常會結合遺傳演算法）

總結一下，這個演算法的理論支持目前還較弱，但是很實用，反正算得快，多算幾遍，參數多改改，一般和近似解都很接近