摘要：編碼需要將問題的解編碼成字符串的形式才能使用遺傳算法。遺傳算子遺傳算法有個最基本的操作選擇，交叉，變異。實驗發現，比較大的種群的規模并不能優化遺傳算法的結果。災變遺傳算法的局部搜索能力較強，但是很容易陷入局部極值。

作為遺傳算法生物背景的介紹，下面內容了解即可：

種群(Population)：生物的進化以群體的形式進行，這樣的一個群體稱為種群。

個體：組成種群的單個生物。

基因 ( Gene ) ：一個遺傳因子。

染色體 ( Chromosome ) ：包含一組的基因。

生存競爭，適者生存：對環境適應度高的、牛B的個體參與繁殖的機會比較多，后代就會越來越多。適應度低的個體參與繁殖的機會比較少，后代就會越來越少。

遺傳與變異：新個體會遺傳父母雙方各一部分的基因，同時有一定的概率發生基因變異。

簡單說來就是：繁殖過程，會發生基因交叉( Crossover ) ，基因突變 ( Mutation ) ，適應度( Fitness )低的個體會被逐步淘汰，而適應度高的個體會越來越多。那么經過N代的自然選擇后，保存下來的個體都是適應度很高的，其中很可能包含史上產生的適應度最高的那個個體。

GA的組成:

編碼（產生初始種群）

適應度函數

遺傳算子（選擇、交叉、變異）

運行參數

借鑒生物進化論，遺傳算法將要解決的問題模擬成一個生物進化的過程，通過復制、交叉、突變等操作產生下一代的解，并逐步淘汰掉適應度函數值低的解，增加適應度函數值高的解。這樣進化N代后就很有可能會進化出適應度函數值很高的個體。

舉個例子，使用遺傳算法解決“0-1背包問題”的思路：0-1背包的解可以編碼為一串0-1字符串（0：不取，1：?。?；首先，隨機產生M個0-1字符串，然后評價這些0-1字符串作為0-1背包問題的解的優劣；然后，隨機選擇一些字符串通過交叉、突變等操作產生下一代的M個字符串，而且較優的解被選中的概率要比較高。這樣經過G代的進化后就可能會產生出0-1背包問題的一個“近似最優解”。

需要將問題的解編碼成字符串的形式才能使用遺傳算法。最簡單的一種編碼方式是二進制編碼，即將問題的解編碼成二進制位數組的形式。例如，問題的解是整數，那么可以將其編碼成二進制位數組的形式。將0-1字符串作為0-1背包問題的解就屬于二進制編碼。

基因在一定能夠意義上包含了它所代表的問題的解。基因的編碼方式有很多，這也取決于要解決的問題本身。常見的編碼方式有：

二進制編碼，基因用0或1表示（常用于解決01背包問題） 如：基因A：00100011010 (代表一個個體的染色體)

互換編碼（用于解決排序問題，如旅行商問題和調度問題） 如旅行商問題中，一串基因編碼用來表示遍歷的城市順序，如：234517986，表示九個城市中，先經過城市2，再經過城市3，依此類推。

樹形編碼（用于遺傳規劃中的演化編程或者表示）

如,問題：給定了很多組輸入和輸出。請你為這些輸入輸出選擇一個函數，使得這個函數把每個輸入盡可能近地映射為輸出。 編碼方法：基因就是樹形結構中的一些函數。

值編碼 （二進制編碼不好用時，解決復雜的數值問題）

在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關任何值：整數，實數，字符或者其他一些更復雜的東西。

適應度函數 ( Fitness Function )：用于評價某個染色體的適應度，用f(x)表示。有時需要區分染色體的適應度函數與問題的目標函數。例如：0-1背包問題的目標函數是所取得物品價值，但將物品價值作為染色體的適應度函數可能并不一定適合。適應度函數與目標函數是正相關的，可對目標函數作一些變形來得到適應度函數。

遺傳算子：遺傳算法有3個最基本的操作：選擇，交叉，變異。

選擇一些染色體來產生下一代。一種常用的選擇策略是 “比例選擇”，也就是個體被選中的概率與其適應度函數值成正比。假設群體的個體總數是M，那么那么一個體Xi被選中的概率為f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) ) 。比例選擇實現算法就是所謂的“輪盤賭算法”( Roulette Wheel Selection )。

輪盤賭算法

/*

* 按設定的概率，隨機選中一個個體

* P[i]表示第i個個體被選中的概率

*/

int RWS()

{

m =0;

r =Random(0,1); //r為0至1的隨機數

for(i=1;i<=N; i++)

{

/* 產生的隨機數在m~m+P[i]間則認為選中了i

* 因此i被選中的概率是P[i]

*/

m = m + P[i];

if(r<=m) return i;

所謂交叉運算，是指對兩個相互配對的染色體依據交叉概率按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算在GA中起關鍵作用，是產生新個體的主要方法。

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

染色體交叉是以一定的概率發生的，這個概率記為Pc 。

選擇兩個交叉點,子代基因在兩個交叉點間部分來自一個父代基因,其余部分來自于另外一個父代基因. 如：

交叉前：

01 |0010| 11

11 |0111| 01

交叉后：

11 |0010| 01

01 |0111| 11

對父代按位"與”邏輯運算產生一子代A;按位”或”邏輯運算產生另一子代B。該交叉策略在解背包問題中效果較好 . 如：

交叉前：

01001011

11011101

交叉后：

01001001

11011111

還有其他交叉方法，參考遺傳算法學習心得

變異是指依據變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。GA中的變異運算是產生新個體的輔助方法，它決定了GA的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。

注：變異概率Pm不能太小，這樣降低全局搜索能力；也不能太大，Pm > 0.5，這時GA退化為隨機搜索。

在繁殖過程，新產生的染色體中的基因會以一定的概率出錯，稱為變異。變異發生的概率記為Pm 。

基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變為1；反之，若原有基因值為1，則變異操作將其變為0。

變異前：

000001110000000010000

變異后：

000001110000100010000

在個體中隨機挑選兩個逆轉點，再將兩個逆轉點間的基因交換。 如：

變異前： 1346798205

變異后： 1246798305

GA運行時選擇的參數應該視解決的具體問題而定，到目前為止，還沒有一個適用于GA所有應用領域的關于算法參數的理論。下面是一般情況下使用GA時推薦的參數：

交叉率一般來說應該比較大，推薦使用80％-95％。

變異率一般來說應該比較小，一般使用0.5％-1％最好。

種群規模指的是群體中個體的個數。實驗發現，比較大的種群的規模并不能優化遺傳算法的結果。種群的大小推薦使用20-30，一些研究表明，種群規模 的大小取決于編碼的方法，具體的說就是編碼串（Encoded String）的大小。也就是說，如果說采用32位為基因編碼的時候種群的規模大小最好為32的話，那么當采用16位為基因編碼時種群的規模相應應變為原 來的兩倍。

個人的想法是，設定一個計數器，如果連續N代出現的最優個體的適應度都一樣時，（嚴格的說應該是，連續N代子代種群的最優個體適應度都<=父代最優個性的適應度）可以終止運算。

SGA（基本遺傳算法）中采用輪盤賭選擇方法

基本遺傳算法偽代碼



/*

* Pc：交叉發生的概率

* Pm：變異發生的概率

* M：種群規模

* G：終止進化的代數

* Tf：進化產生的任何一個個體的適應度函數超過Tf，則可以終止進化過程

*/

初始化Pm，Pc，M，G，Tf等參數。隨機產生第一代種群Pop



do

{ 

　　計算種群Pop中每一個體的適應度F(i)。

　　初始化空種群newPop

　　do

　　{

　　　　根據適應度以比例選擇算法從種群Pop中選出2個個體

　　　　if ( random ( 0 , 1 ) < Pc )

　　　　{

　　　　　　對2個個體按交叉概率Pc執行交叉操作

　　　　}

　　　　if ( random ( 0 , 1 ) < Pm )

　　　　{

　　　　　　對2個個體按變異概率Pm執行變異操作

　　　　}

將2個新個體加入種群newPop中

} until ( M個子代被創建 )

用newPop取代Pop

}until ( 任何染色體得分超過Tf， 或繁殖代數超過G )

下面的方法可優化遺傳算法的性能。

遺傳算法的局部搜索能力較強，但是很容易陷入局部極值。引用網上的一段原話: “那么如何解決遺傳算法容易陷入局部極值的問題呢？讓我們來看看大自然提供的方案。

六千五百萬年以前，恐龍和靈長類動物并存，恐龍在地球上占絕對統 治地位，如果恐龍沒有滅絕靈長類動物是絕沒有可能統治地球的。正是恐龍的滅絕才使靈長類動物有了充分進化的余地，事實上地球至少經歷了5次物種大滅絕，每 次物種滅絕都給更加高級的生物提供了充分進化的余地。所以要跳出局部極值就必須殺死當前所有的優秀個體，從而讓遠離當前極值的點有充分的進化余地。這就是災變的思想?！?

災變就是殺掉最優秀的個體，這樣才可能產生更優秀的物種。那何時進行災變，災變次數又如何設定？

何時進行災變，可以采用災變倒計數的方式。如果n代還沒有出現比之前更優秀的個體時，可以發生災變。災變次數可以這樣來確定，如果若干次災變后產生的個體的適應度與沒災變前的一樣，可停止災變。

當利用交叉和變異產生新的一代時，我們有很大的可能把在某個中間步驟中得到的最優解丟失。

精英主義的思想是,在每一次產生新的一代時，首先把當前最優解原封不動的復制到新的一代中。然后按照前面所說的那樣做就行。精英主義方法可以大幅提高運算速度，因為它可以防止丟失掉找到的最好的解。

精英主義是基本遺傳算法的一種優化。為了防止進化過程中產生的最優解被交叉和變異所破壞，可以將每一代中的最優解原封不動的復制到下一代中。

由上面看來,災變與精英主義之間似乎存在著矛盾.前者是將產生的最優個體殺掉,而后者是將最優秀個體基因直接保存到下一代.

應該辯證地看待它們之間的矛盾,兩者其實是可以共存的.我們在每一代進行交叉運算時,均直接把最優秀的個體復制到下一代;但當連續N代,都沒有更優 秀的個體出現時,便可以猜想可能陷入局部最優解了,這樣可以采用災變的手段.可以說,精英主義是伴隨的每一代的,但災變卻不需要經常發生,否則算法可能下 降為隨機搜索了.

當然,每個算法中不一定要用精英主義和災變的手段,應該根據具體的問題而定

可在3個基本操作的基礎上增加一個插入操作。插入操作將染色體中的某個隨機的片段移位到另一個隨機的位置。

群體搜索，易于并行化處理；

不是盲目窮舉，而是啟發式搜索；

適應度函數不受連續、可微等條件的約束，適用范圍很廣。

容易實現。一旦有了一個遺傳算法的程序，如果想解決一個新的問題，只需針對新的問題重新進行基因編碼就行；如果編碼方法也相同，那只需要改變一下適應度函數就可以了。

全局搜索能力不強,很容易陷入局部最優解跳不出來；(可結合SA進行改進,因為SA在理率上是100%得到全局最優的,但搜索代價高)

將遺傳算法用于解決各種實際問題后，人們發現遣傳算法也會由于各種原因過早向目標函數的局部最優解收斂，從而很難找到全局最優解。其中有些是由于目標函數的特性造成的，例如函數具有欺騙性，不滿足構造模塊假說等等；另外一些則是由于算法設計不當。為此，不斷有人對遺傳算法提出各種各樣的改進方案。例如：針對原先的定長二進制編碼方案；提出了動態編碼、實數編碼等改進方案；針對按比例的選擇機制，提出了競爭選擇、按續挑選等改進方案；針對原先的一點交算子，提出了兩點交、多點交、均勻交等算子；針對原先遺傳算法各控制參數在進化過程中不變的情況，提出了退化遺傳算法、自適應遺傳算法等。另外，針對不同問題還出現了分布式遺傳算法、并行遺傳算法等等。

參考文獻都是干貨?。?！參考文獻都是干貨?。?！參考文獻都是干貨?。?！

遺傳算法入門-博客園-蒼梧
本文主要參考，推薦！感謝作者~

經典算法研究系列：七、深入淺出遺傳算法
July大神寫的，通俗易懂，推薦！??！

HELLO，遺傳算法！
博主語言輕松，用python描述了遺傳算法求解一個函數最大值的例子。

遺傳算法理論基礎與簡單應用實例
博主總結整理的內容，挺不錯的，文中的鏈接有實例應用。

遺傳算法入門到掌握（一） CSDN-GA代碼下載
袋鼠跳的例子來描述了GA算法，幫助理解GA。

非常好的理解遺傳算法的例子
求下述二元函數的最大值的例子

遺傳算法學習心得

歡迎來我的博客看看~
Michael翔的小窩-GA總結