遺傳演算法選擇策略

『壹』 遺傳演算法

根據問題的目標函數構造一個適值函數，對一個由多個解（每個解對應一個染色體）構成的種群進行評估、遺傳、選擇，經多代繁殖，獲得適應值最好的個體作為問題的最優解。

1，產生一個初始種群

2，根據問題的目標函數構造適值函數

3，根據適應值的好壞不斷選擇和繁殖

4，若干代後得到適應值最好的個體即為最優解

1.種群和種群大小

一般越大越好，但是規模越大運算時間越大，一般設為100~1000

2. 編碼方法 （基因表達方法

3. 遺傳運算元

包括交叉和變異，模擬了每一代中創造後代的繁殖過程。是遺傳演算法的精髓

交叉：性能在很大程度上取決於交叉運算的性能，交叉率Pc：各代中交叉產生的後與代數與種群中的個體數的比。Pc越高，解空間就越大，越耗時/

變異:Pm:種群中變異基因數在總基因數中的百分比。它控制著新基因導入種群的比例。太低，一些有用的基因就難以進入選擇；太高，後代就可能失去從雙親繼承下來的良好特性，也就失去了從過去中搜索的能力。

4.選擇策略

適者生存，優勝劣汰

5.停止准則

最大迭代數

初始種群的產生：隨機產生，具體依賴於編碼方法

編碼方法 ：二進制編碼法、浮點編碼法、符號編碼法。順序編碼，實數編碼，整數編碼。

適值函數 ：根據目標函數設計

遺傳運算 ： 交叉 ：單切點交叉，雙切點交叉，均勻交叉，算術交叉

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

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

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

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

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

選擇策略 ：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.排擠選擇：新生成的子代將代替或排擠相似的舊父代個體，提高群體的多樣性。

之前在網上看到的一個比方，覺得很有趣：

{

既然我們把函數曲線理解成一個一個山峰和山谷組成的山脈。那麼我們可以設想所得到的每一個解就是一隻袋鼠，我們希望它們不斷的向著更高處跳去，直到跳到最高的山峰。所以求最大值的過程就轉化成一個「袋鼠跳」的過程。

下面介紹介紹「袋鼠跳」的幾種方式。

爬山演算法：一隻袋鼠朝著比現在高的地方跳去。它找到了不遠處的最高的山峰。但是這座山不一定是最高峰。這就是爬山演算法，它不能保證局部最優值就是全局最優值。

模擬退火：袋鼠喝醉了。它隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了並朝最高峰跳去。這就是模擬退火演算法。

遺傳演算法：有很多袋鼠，它們降落到喜瑪拉雅山脈的任意地方。這些袋鼠並不知道它們的任務是尋找珠穆朗瑪峰。但每過幾年，就在一些海拔高度較低的地方射殺一些袋鼠。於是，不斷有袋鼠死於海拔較低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有機會生兒育女。就這樣經過許多年，這些袋鼠們竟然都不自覺地聚攏到了一個個的山峰上，可是在所有的袋鼠中，只有聚攏到珠穆朗瑪峰的袋鼠被帶回了美麗的澳洲。

}

（把那些總是愛走下坡路的袋鼠射殺，這就是遺傳演算法的精粹！）

遺傳演算法並不保證你能獲得問題的最優解，但是使用遺傳演算法的最大優點在於你不必去了解和操心如何去「找」最優解。（你不必去指導袋鼠向那邊跳，跳多遠。）而只要簡單的「否定」一些表現不好的個體就行了。（把那些總是愛走下坡路的袋鼠射殺，這就是遺傳演算法的精粹！）

改進與變形

編碼方法：

『貳』 遺傳演算法的主要步驟

為了使用遺傳演算法來解決優化問題，准備工作分為以下四步^{［56，57，61］}。

7.4.1 確定問題的潛在解的遺傳表示方案

在基本的遺傳演算法中，表示方案是把問題的搜索空間中每個可能的點表示為確定長度的特徵串（通常是二進制串）。表示方案的確定需要選擇串長l和字母表規模k。在染色體串和問題的搜索空間中的點之間選擇映射有時容易實現，有時又非常困難。選擇一個便於遺傳演算法求解問題的表示方案經常需要對問題有深入的了解。

7.4.2 確定適應值的度量

適應值度量為群體中每個可能的確定長度的特徵串指定一個適應值，它經常是問題本身所具有的。適應值度量必須有能力計算搜索空間中每個確定長度的特徵串的適應值。

7.4.3 確定控制該演算法的參數和變數

控制遺傳演算法的主要參數有群體規模Pop-Size、演算法執行的最大代數N-Gen、交叉概率P_c、變異概率P_m和選擇策略R等參數。

（1）群體規模Pop-Size。群體規模影響到遺傳演算法的最終性能和效率。當規模太小時，由於群體對大部分超平面只給出了不充分的樣本量，所以得到的結果一般不佳。大的群體更有希望包含出自大量超平面的代表，從而可以阻止過早收斂到局部最優解；然而群體越大，每一代需要的計算量也就越多，這有可能導致一個無法接受的慢收斂率。

（2）交叉率P_c。交叉率控制交叉運算元應用的頻率，在每代新的群體中，有P_c·Pop-Size個串實行交叉。交叉率越高，群體中串的更新就越快。如果交叉率過高，相對選擇能夠產生的改進而言，高性能的串被破壞得更快。如果交叉率過低，搜索會由於太小的探查率而可能停滯不前。

（3）變異率P_m。變異是增加群體多樣性的搜索運算元，每次選擇之後，新的群體中的每個串的每一位以相等的變異率進行隨機改變。對於M進制串，就是相應的位從1變為0或0變為1。從而每代大約發生P_m·Pop-Size·L次變異，其中L為串長。一個低水平的變異率足以防止整個群體中任一給定位保持永遠收斂到單一的值。高水平的變異率產生的實質是隨機搜索。

比起選擇和交叉，變異在遺傳演算法中是次要的，它在恢復群體中失去的多樣性方面具有潛在的作用。例如，在遺傳演算法執行的開始階段，串中一個特定位上的值1可能與好的性能緊密聯系，也就是說從搜索空間中某些初始隨機點開始，在那個位上的值1可能一致地產生適應性度量好的值。因為越好的適應值與串中那個位上的值1相聯系，復製作用就越會使群體的遺傳多樣性損失。當達到一定程度時，值0會從整個群體中的那個位上消失，然而全局最優解可能在串中那個位上是0。一旦搜索范圍縮小到實際包含全局最優解的那部分搜索空間，在那個位上的值0就可能正好是達到全局最優解所需的。這僅僅是一種說明搜索空間是非線性的方式，這種情形不是假定的，因為實際上所有我們感興趣的問題都是非線性的。變異作用提供了一個恢復遺傳多樣性的損失的方法。

（4）選擇策略R。有兩種選擇策略。一是利用純選擇，即當前群體中每個點復制的次數比與點的性能值成比例。二是利用最優選擇，即首先執行純選擇，且具有最好性能的點總是保留到下一代。在缺少最優選擇的情況下，由於采樣誤差、交叉和變異，最好性能的點可能會丟失。

通過指定各個參數Pop-Size、P_c、P_m和R的值，可以表示一個特定的遺傳演算法。

7.4.4 確定指定結果的方法和停止運行的准則

當遺傳的代數達到最大允許代數時，就可以停止演算法的執行，並指定執行中得到的最好結果作為演算法的結果。

基本的遺傳演算法

1）隨機產生一個由固定長度字元串組成的初始群體。

2）對於字元串群體，迭代地執行下述步驟，直到選擇標准被滿足為止。

①計算群體中的每個個體字元串的適應值；

②實施下列三種操作（至少前兩種）來產生新的群體，操作對象的選取基於與適應度成比例的概率。

選擇：把現有的個體串按適應值復制到新的群體中。

交叉：通過遺傳重組隨機選擇兩個現有的子串進行遺傳重組，產生兩個新的串。

變異：將現有串中某一位的字元隨機變異產生一個新串。

3）把在後代中出現的最好適應值的個體串指定為遺傳演算法運行的結果。這一結果可以是問題的解（或近似解）。

基本的遺傳演算法流程圖如圖7-1所示。

『叄』 遺傳演算法精英保留策略

我個人認為。直接復制本代的最優解到下一代的這種方法雖然會有益於形成較優解，但是違背了遺傳規律。個人見解，哈哈。

『肆』 優化演算法筆記（六）遺傳演算法

遺傳演算法(Genetic Algorithms，GA)是一種模擬自然中生物的遺傳、進化以適應環境的智能演算法。由於其演算法流程簡單，參數較少優化速度較快，效果較好，在圖像處理、函數優化、信號處理、模式識別等領域有著廣泛的應用。
在遺傳演算法（GA）中，每一個待求問題的候選解被抽象成為種群中一個個體的基因。種群中個體基因的好壞由表示個體基因的候選解在待求問題中的所的得值來評判。種群中的個體通過與其他個體交叉產生下一代，每一代中個體均只進行一次交叉。兩個進行交叉的個體有一定幾率交換一個或者多個對應位的基因來產生新的後代。每個後代都有一定的概率發生變異。發生變異的個體的某一位或某幾位基因會變異成其他值。最終將以個體的適應度值為概率選取個體保留至下一代。

遺傳演算法啟發於生物的繁殖與dna的重組，本次的主角選什麼呢？還是根據大家熟悉的孟德爾遺傳規律選豌豆吧，選動物的話又會有人疑車，還是植物比較好，本次的主角就是它了。

遺傳演算法包含三個操作（運算元）：交叉，變異和選擇操作。下面我們將詳細介紹這三個操作。
大多數生物的遺傳信息都儲存在DNA，一種雙螺旋結構的復雜有機化合物。其含氮鹼基為腺嘌呤、鳥嘌呤、胞嘧啶及胸腺嘧啶。

表格中表示了一個有10個基因的個體，它們每一個基因的值為0或者1。

生物的有性生殖一般伴隨著基因的重組。遺傳演算法中父輩和母輩個體產生子代個體的過程稱為交叉。

表中給出了兩個豌豆的基因，它們均有10個等位基因（即編號相同的基因）。
遺傳演算法的交叉過程會在兩個個體中隨機選擇1位或者n位基因進行交叉，即這兩個個體交換等位基因。
如，A豌豆和B豌豆在第6位基因上進行交叉，則其結果如下

當兩個個體交叉的等位基因相同時，交叉過程也有可能沒有產生新的個體，如交叉A豌豆和B豌豆的第2位基因時，交叉操作並沒有產生新的基因。

一般的會給群體設定一個交叉率，crossRate，表示會在群體中選取一定比例的個體進行交叉，交叉率相對較大，一般取值為0.8。

基因的變異是生物進化的一個主要因素。
遺傳演算法中變異操作相對簡單，只需要將一個隨機位基因的值修改就行了，因為其值只為0或1，那麼當基因為0時，變異操作會將其值設為1，當基因值為1時，變異操作會將其值設為0。

上圖表示了A豌豆第3位基因變異後的基因編碼。
與交叉率相似，變異操作也有變異率，alterRate，但是變異率會遠低於交叉率，否則會產生大量的隨機基因。一般變異率為0.05。

選擇操作是遺傳演算法中的一個關鍵操作，它的主要作用就是根據一定的策略隨機選擇個體保留至下一代。適應度越優的個體被保留至下一代的概率越大。
實現上，我們經常使用「輪盤賭」來隨機選擇保留下哪個個體。

假設有4個豌豆A、B、C、D，它們的適應度值如下：

適應度值越大越好，則它們組成的輪盤如下圖：

但由於輪盤賭選擇是一個隨機選擇過程，A、B、C、D進行輪盤賭選擇後產生的下一代也有可能出現A、A、A、A的情況，即雖然有些個體的適應度值不好，但是運氣不錯，也被選擇留到了下一代。
遺產演算法的三個主要操作介紹完了，下面我們來看看遺傳演算法的總體流程：

前面我們說了遺傳演算法的流程及各個操作，那麼對於實際的問題我們應該如何將其編碼為基因呢？

對於計算機來所所有的數據都使用二進制數據進行存放，如float類型和double類型的數據。
float類型的數據將保存為32位的二進制數據：1bit（符號位） 8bits（指數位） 23bits（尾數位）
如-1.234567f，表示為二進制位

Double類型的數據將保存為64位的二進制數據：1bit（符號位） 11bits（指數位） 53bits（尾數位）
如-1.234567d，表示為二進制為

可以看出同樣的數值不同的精度在計算機中存儲的內容也不相同。之前的適應度函數 ，由於有兩個double類型的參數，故其進行遺傳演算法基因編碼時，將有128位基因。
雖然基因數較多，但好在每個基因都是0或者1，交叉及變異操作非常簡單。

相比二進制編碼，十進制編碼的基因長度更短，適應度函數 有兩個輸入參數，那麼一個個體就有2個基因，但其交叉、變異操作相對復雜。
交叉操作
方案1：將一個基因作為一個整體，交換兩個個體的等位基因。
交換前

交換第1位基因後

方案2：將兩個個體的等位基因作為一個整體，使其和不變，但是值隨機
交換前

交換第1位基因後

假設A、B豌豆的第一位基因的和為40，即 ,第一位基因的取值范圍為0-30，那麼A、B豌豆的第一位基因的取值范圍為[10,30],即 為[0,30]的隨機數， 。
變異操作，將隨機的一位基因設置為該基因取值范圍內的隨機數即可。

這個過程說起來簡單但其實現並不容易。

我們要將它們的值映射到一個軸上才能進行隨機選擇，畢竟我們無法去繪制一個輪盤來模擬這個過程

如圖，將ABCD根據其值按順序排列，取[0,10]內的隨機數r，若r在[0,1]內則選擇A,在(1,3]內則選擇B,在(3,6]內則選擇C,在(6,10]則選擇D。
當然這仍然會有問題，即當D>>A、B、C時，假如它們的值分布如下

那麼顯然，選D的概率明顯大於其他，根據輪盤賭的選擇，下一代極有可能全是D的後代有沒有辦法均衡一下呢？
首先我想到了一個函數，

不要問我為什麼我不知道什麼是神經什麼網路的，什麼softmax、cnn統統沒聽說過。

這樣一來，它們之間的差距沒有之前那麼大了，只要個體適應度值在均值以上那麼它被保留至下一代的概率會相對較大，當然這樣縮小了個體之間的差距，對真正優秀的個體來說不太公平，相對應，我們可以在每次選擇過程中保留當前的最優個體到下一代，不用參與輪盤賭這個殘酷的淘汰過程。

最令人高興的環節到了，又可以愉快的湊字數了。

由於遺傳演算法的收斂速度實在是太慢，區區50代，幾乎得不到好的結果，so我們把它的最大迭代次數放寬到200代。

使用二進制編碼來進行求解
參數如下：

求解過程如上圖，可以看出基因收斂的很快，在接近20代時就圖中就只剩一個點了，之後的點大概是根據變異操作產生。看一下最後的結果。

可以看出最好的結果已經得到了最優解，但是10次實驗的最差值和平均值都差的令人發指。為什麼會這樣呢？

問題出在二進制編碼上，由於double類型的編碼有11位指數位和52位小數位，這會導致交叉、變異操作選到指數位和小數位的概率不均衡，在小數位上的修改對結果的影響太小而對指數為的修改對結果的影響太大，
如-1.234567d，表示為二進制為

對指數為第5位進行變異操作後的結果為-2.8744502924382686E-10，而對小數位第5為進行變異操作後的結果為-1.218942。可以看出這兩部分對數值結果的影響太不均衡，得出較好的結果時大概率是指數位與解非常相近，否則很難得出好的結果，就像上面的最差值和均值一樣。
所以使用上面的二進制編碼不是一個好的基因編碼方式，因此在下面的實驗中，將使用十進制來進行試驗。

使用:十進制編碼來進行求解
參數如下：

我們可以看到直到40代時，所有的個體才收束到一點，但隨後仍不斷的新的個體出現。我們發現再後面的新粒子總是在同一水平線或者豎直線上，因為交叉操作直接交換了兩個個體的基因，那麼他們會相互交換x坐標或者y坐標，導致新個體看起來像在一條直線上。
我們來看看這次的結果。

這次最優值沒有得到最優解，但是最差值沒有二進制那麼差，雖然也不容樂觀。使用交換基因的方式來進行交叉操作的搜索能力不足，加之輪盤賭的選擇會有很大概率選擇最優個體，個體總出現在矩形的邊上。
下面我們先改變輪盤賭的選擇策略，使用上面的sigmod函數方案，並且保留最優個體至下一代。

使用:十進制編碼來進行求解
參數如下：

看圖好像跟之前的沒什麼區別，讓我們們看看最終的結果：

可以看出，最優值沒有什麼變化，但是最差值和平均值有了較大的提升，說明該輪盤賭方案使演算法的魯棒性有了較大的提升。在每次保留最優個體的情況下，對於其他的個體的選擇概率相對平均，sigmod函數使得即使適應度函數值相差不太大的個體被選到的概率相近，增加了基因的多樣性。

使用:十進制編碼來進行求解，改變交叉方案，保持兩個個體等位基因和不變的情況下隨機賦值。
參數如下：

上圖可以看出該方案與之前有明顯的不同，在整個過程中，個體始終遍布整個搜索空間，雖然新產生的個體大多還是集中在一個十字架型的位置上，但其他位置的個體比之前的方案要多。
看看結果，

這次的結果明顯好於之前的所有方案，但仍可以看出，十進制的遺傳演算法的精度不高，只能找到最優解的附近，也有可能是演算法的收斂速度實在太慢，還沒有收斂到最優解。

遺傳演算法的探究到此也告一段落，在研究遺傳演算法時總有一種力不從心的感覺，問題可能在於遺傳演算法只提出了一個大致的核心思想，其他的實現細節都需要自己去思考，而每個人的思維都不一樣，一萬個人能寫出一萬種遺傳演算法，其實不僅是遺傳演算法，後面的很多演算法都是如此。
為什麼沒有對遺傳演算法的參數進行調優，因為遺傳演算法的參數過於簡單，對結果的影響的可解釋性較強，意義明顯，實驗的意義不大。

遺傳演算法由於是模仿了生物的進化過程，因此我感覺它的求解速度非常的慢，而且進化出來的結果不一定是最適應環境的，就像人的闌尾、視網膜結構等，雖然不是最佳的選擇但是也被保留到了今天。生物的進化的隨機性較大，要不是恐龍的滅絕，也不會有人類的統治，要不是人類有兩只手，每隻手有5根手指，也不會產生10進制。
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（五）粒子群演算法（3）
下一篇 優化演算法筆記（七）差分進化演算法

優化演算法matlab實現（六）遺傳演算法matlab實現

『伍』 遺傳演算法原理簡介

遺傳演算法（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

『陸』 遺傳演算法的基本原理

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

一、編碼

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

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

二進制編碼的缺點是漢明懸崖（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的正態分布的一個隨機數來替換原有的基因值。

『柒』 遺傳演算法中的排序選擇策略選擇最優的復制到下一代是不是已經包含了精英保留策略的作用

這得看你的排序選擇策略是怎樣的。
一種排序是只對當代種群進行排序，這種排序選擇方式並不包含精英保留策略的作用。
另一種排序是把上一次種群放一直排序，這種方式包含了精英保留策略的作用。
例如有初始種群包含個體為A1,A2,A3,A4，經過適應度計算後得知最優個體為順序為A2,A1,A3,A4，經過排序選擇後為A2,A2,A1,A3，然後經過交叉和變異後的變為B1,B2,B3,B4，而B1,B2,B3,B4的適應度均沒有A2大，那麼如果採用第一種排序方式，只對B1-B4排序選擇，那麼將丟失A2這一優良個體，所以並不包含精英保留作用。如果將B1-B4與A1-A2一起排序，那麼由於A2適應度最大，因此必然會選到A2，等效於精英保留策略。

『捌』 遺傳演算法的基本原理

遺傳演算法本質上是對染色體模式所進行的一系列運算，即通過選擇運算元將當前種群中的優良模式遺傳到下一代種群中，利用交叉運算元進行模式重組，利用變異運算元進行模式突變。