遺傳演算法求近似解

A. 遺傳演算法的基本原理

遺傳演算法的基本原理和方法

一、編碼

編碼：把一個問題的可行解從其解空間轉換到遺傳演算法的搜索空間的轉換方法。

解碼（解碼）：遺傳演算法解空間向問題空間的轉換。

二進制編碼的缺點是漢明懸崖（Hamming Cliff），就是在某些相鄰整數的二進制代碼之間有很大的漢明距離，使得遺傳演算法的交叉和突變都難以跨越。

格雷碼（Gray Code）：在相鄰整數之間漢明距離都為1。

（較好）有意義的積木塊編碼規則：所定編碼應當易於生成與所求問題相關的短距和低階的積木塊；最小字元集編碼規則，所定編碼應採用最小字元集以使問題得到自然的表示或描述。

二進制編碼比十進制編碼搜索能力強，但不能保持群體穩定性。

動態參數編碼（Dynamic Paremeter Coding）：為了得到很高的精度，讓遺傳演算法從很粗糙的精度開始收斂，當遺傳演算法找到一個區域後，就將搜索現在在這個區域，重新編碼，重新啟動，重復這一過程，直到達到要求的精度為止。

編碼方法：

1、 二進制編碼方法

缺點：存在著連續函數離散化時的映射誤差。不能直接反映出所求問題的本身結構特徵，不便於開發針對問題的專門知識的遺傳運算運算元，很難滿足積木塊編碼原則

2、 格雷碼編碼滾如：連續的兩個整數所對應的編碼之間僅僅只有一個碼位是不同的，其餘碼位都相同。

3、 浮點數編碼方法：個體的每個基因值用某一范圍內的某個浮點數來表示，個體的編碼長度等於其決策變數的位數。

4、 各參數級聯編碼：對含有多個變數的個體進行編碼的方法。通常將各個參數分別以某種編碼方法進行編碼，然後再將他們的編碼按照一定順序連接在一起就組成了表示全部參數的個體編碼。

5、 多參數交叉編碼：將各個參數中起主要作用的碼位集中在一起，這樣它們就不易於被遺傳運算元破壞掉。

評估編碼的三個規范：完備性、健全性、非冗餘性。

二、選擇

遺傳演算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取那些個體遺傳到下一代群體中的一種遺傳運算，用來確定重組或交叉個體，以及被選個體將產生多少個子代個體。

常用的選擇運算元：

1、 輪盤賭選擇（Roulette Wheel Selection）：是一種回放式隨機采樣方法。每個個體進入下一代的概率等於它的適應度值與整個種群中個體適應度值和的比例。選擇誤差較大。

2、 隨機競爭選擇（Stochastic Tournament）：每次按輪盤賭選擇一對個體，然後讓這兩個個體進行競爭，適應度高的被選中，如此反復，直到選滿為止。

3、 最佳保留選擇：首先按輪盤賭選擇方法執行遺傳演算法的選擇操作，然後將當前群體中適應度最高的大宏啟個體結構完整地復制到下一代群體中。

4、 無回放隨機選擇（也叫期望值選擇Excepted Value Selection）：根據每個個體在下一代群體中的生存期望來進行隨機選擇運算。方法如下

（1） 計算群體中每個個體在下一代群體中的生存期望數目N。

（2） 若某一個體被選中參與交叉運算，則它在下一代中的生存期望數目減去0.5，若某一個體未被選中參與交叉運算，則它絕配在下一代中的生存期望數目減去1.0。

（3） 隨著選擇過程的進行，若某一個體的生存期望數目小於0時，則該個體就不再有機會被選中。

5、 確定式選擇：按照一種確定的方式來進行選擇操作。具體操作過程如下：

（1） 計算群體中各個個體在下一代群體中的期望生存數目N。

（2） 用N的整數部分確定各個對應個體在下一代群體中的生存數目。

（3） 用N的小數部分對個體進行降序排列，順序取前M個個體加入到下一代群體中。至此可完全確定出下一代群體中M個個體。

6、無回放余數隨機選擇：可確保適應度比平均適應度大的一些個體能夠被遺傳到下一代群體中，因而選擇誤差比較小。

7、均勻排序：對群體中的所有個體按期適應度大小進行排序，基於這個排序來分配各個個體被選中的概率。

8、最佳保存策略：當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用它來代替掉本代群體中經過交叉、變異等操作後所產生的適應度最低的個體。

9、隨機聯賽選擇：每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中。

10、排擠選擇：新生成的子代將代替或排擠相似的舊父代個體，提高群體的多樣性。

三、交叉

遺傳演算法的交叉操作，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。

適用於二進制編碼個體或浮點數編碼個體的交叉運算元：

1、單點交叉（One－pointCrossover）：指在個體編碼串中只隨機設置一個交叉點，然後再該點相互交換兩個配對個體的部分染色體。

2、兩點交叉與多點交叉：

（1） 兩點交叉（Two－pointCrossover）：在個體編碼串中隨機設置了兩個交叉點，然後再進行部分基因交換。

（2） 多點交叉（Multi－pointCrossover）

3、均勻交叉（也稱一致交叉，UniformCrossover）：兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新個體。

4、算術交叉（ArithmeticCrossover）：由兩個個體的線性組合而產生出兩個新的個體。該操作對象一般是由浮點數編碼表示的個體。

四、變異

遺傳演算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基因來替換，從而形成以給新的個體。

以下變異運算元適用於二進制編碼和浮點數編碼的個體：

1、基本位變異（SimpleMutation）：對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。

2、均勻變異（UniformMutation）：分別用符合某一范圍內均勻分布的隨機數，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。（特別適用於在演算法的初級運行階段）

3、邊界變異（BoundaryMutation）：隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的一類問題。

4、非均勻變異：對原有的基因值做一隨機擾動，以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後，相當於整個解向量在解空間中作了一次輕微的變動。

5、高斯近似變異：進行變異操作時用符號均值為P的平均值，方差為P2的正態分布的一個隨機數來替換原有的基因值。

B. 遺傳演算法原理簡介

遺傳演算法（Genetic Algorithm, GA）是一種進化計算（Evolutionary Computing）演算法，屬於人工智慧技術的一部分。遺傳演算法最早是由John Holland和他的學生發明並改進的，源於對達芬奇物種進化理論的模仿。在物種進化過程中，為了適應環境，好的基因得到保留，不好的基因被淘汰，這樣經過很多代基因的變化，物種的基因就是當前自然環境下適應度最好的基因。該演算法被廣泛應用於優化和搜索中，用於尋求最優解（或最優解的近似），其最主要的步驟包括交叉（crossover）和突變（mutation）。

所有的生物體都由細胞組成，每個細胞中都包含了同樣的染色體（chromosome）。染色體由一串DNA組成，我們可以簡單地把一個生物個體表示為一條染色體。每條染色體上都包含著基因，而基因又是由多個DNA組成的。每個基因都控制著個體某個性狀的表達，例如眼睛的顏色、眼皮的單雙等。在物種繁衍的過程中，首先發生交叉，來自於父母的染色體經過分裂和重組，形成後代的染色體。之後，後代有一定概率發生基因突變，即染色體上某個位置處的基因以一定概率發生變化。之後，對每一代都重復進行交叉和突變兩個步驟。對於每一個後代，我們可以通過一定的方式測量其適應度。適應度越好的個體，在下一次交叉中被選中的概率越大，它的基因越容易傳給下一代。這樣，後代的適應度就會越來越好，直到收斂到一個穩定值。

在優化問題中，可行解總是有很多個，我們希望尋找一個最優解，它相對於其他可行解來說具有更好的適應度（即目標函數值更大或更小）。每個可行解就是一個「生物個體」，可以表示為狀態空間中的一個點和適應度。每個解都是一個經過編碼的序列，已二進制編碼為例，每個解都是一個二進制序列。這樣每個染色體就是一個二進制序列。遺傳演算法從從一組可行解開始，稱為population，從population中隨機選擇染色體進行交叉產生下一代。這一做法的基於下一代的適應度會好於上一代。遺傳演算法的過程如下：

終止條件可以是達到了最大迭代次數，或者是前後連續幾代的最優染色體的適應度差值小於一個閾值。以上演算法描述也許還不夠直觀，我們舉例說明。假設解可以用二進制編碼表示，則每個染色體都是一個二進制序列。假設序列長度為16，則每個染色體都是一個16位的二進制序列：

首先，我們隨機生成一個population，假設population size為20，則有20個長度為16的二進制序列。計算每個染色體的適應度，然後選取兩個染色體進行交叉，如下圖所示。下圖在第6為上將染色體斷開再重組，斷開的位置是可以隨機選擇的。當然，斷裂位置也可以不止一個。可以根據具體問題選擇具體的交叉方式來提升演算法性能。

之後，隨機選取後代染色體上某個基因發生基因突變，突變的位置是隨機選取的。並且，基因突變並不是在每個後代上都會發生，只是有一定的概率。對於二進制編碼，基因突變的方式是按位取反：

上述例子是關於二進制編碼的，像求解一元函數在某個區間內的最大最小值就可以使用二進制編碼。例如，求解函數f(x)=x+sin(3x)+cos(3x)在區間[0,6]內的最小值。假設我們需要最小值點x保留4位小數，那麼求解區間被離散成60000個數。因為2 {15}<60000<2 {16}，所以，需要16位二進制數來表示這60000個可能的解。其中0x0000表示0，0x0001表示0.0001，以此類推。針對這個例子，文末給出了demo code．

然而，在排序問題中無法使用二進制編碼，應該採用排列編碼（permutation encoding）。例如有下面兩個染色體：

交叉：隨機選取一個交叉點，從該出將兩個染色體斷開。染色體A的前部分組成後代1的前部分，然後掃描染色體B，如果出現了後代1中不包含的基因，則將其順序加入後代1中。同理，染色體B的前部分組成了後代2的前部分，掃描染色體A獲得後代2的後部分。注意，交叉的方式多種多樣，此處只是舉出其中一種方式。

( 1 5 3 2 6 | 4 7 9 8) + ( 8 5 6 7 2 | 3 1 4 9) => ( 1 5 3 2 6 8 7 4 9) + ( 8 5 6 7 2 1 3 4 9)

突變：對於一個染色體，隨機選中兩個基因互換位置。例如第3個基因和倒數第2個基因互換：

(1 5 3 2 6 8 7 4 9) => (1 5 4 2 6 8 7 3 9)

此外還有值編碼（value encoding）和樹編碼（tree encoding）等，具體例子可以參考這個鏈接： http://obitko.com/tutorials/genetic-algorithms/encoding.php

在實際的遺傳演算法中，往往會保留上一代中的少數幾個精英（elite），即將上一代population中適應度最好的幾個染色體加入到後代的poulation中，同時去除後代population中適應度最差的幾個染色體。通過這個策略，如果在某次迭代中產生了最優解，則最優解能夠一直保留到迭代結束。

用GA求函數最小值的demo code： https://github.com/JiaxYau/GA_test

參考資料 ：

[1] Introction to Genetic Algorithm, http://obitko.com/tutorials/genetic-algorithms/index.php

[2] Holland J H. Adaption in natural and artificial systems

C. 遺傳演算法與牛頓迭代法的優劣的比較

每個演算法都各自的特點和它的優劣性。
牛頓迭代法是一種求近似解的方法。遺傳演算法也是一種可以全程求最優值的方法，一般就演算法之間沒有辦法說優劣性，只能是說在特定的條件下該用什麼方法。
就好比專家系統是一個具有專門知識的計算機程序系統，人工神經網路有很好的學習能力，但他們也有自身的缺點。
按樓主的意思來，牛頓迭代法是一種局部演算法，遺傳演算法是全程演算法，畢竟遺傳參數里迭代次數也是一個很重要的參考因素。

D. 關於遺傳演算法

遺傳演算法（Genetic Algorithm，簡稱GA）是美國 Michigan大學的 John Golland提出的一種建立在自然選擇和群體遺傳學機理基礎上的隨機、迭代、進化、具有廣泛適用性的搜索方法。現在已被廣泛用於學習、優化、自適應等問題中。圖4-1 給出了 GA搜索過程的直觀描述。圖中曲線對應一個具有復雜搜索空間（多峰空間）的問題。縱坐標表示適應度函數（目標函數），其值越大相應的解越優。橫坐標表示搜索點。顯然，用解析方法求解該目標函數是困難的。採用 GA時，首先隨機挑選若干個搜索點，然後分別從這些搜索點開始並行搜索。在搜索過程中，僅靠適應度來反復指導和執行 GA 搜索。在經過若干代的進化後，搜索點後都具有較高的適應度並接近最優解。

一個簡單GA由復制、雜交和變異三個遺傳運算元組成：

圖4-2 常規遺傳演算法流程圖