摘要：編碼需要將問題的解編碼成字符串的形式才能使用遺傳算法。遺傳算子遺傳算法有個(gè)最基本的操作選擇，交叉，變異。實(shí)驗(yàn)發(fā)現(xiàn)，比較大的種群的規(guī)模并不能優(yōu)化遺傳算法的結(jié)果。災(zāi)變遺傳算法的局部搜索能力較強(qiáng)，但是很容易陷入局部極值。

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

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

個(gè)體：組成種群的單個(gè)生物。

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

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

生存競(jìng)爭(zhēng)，適者生存：對(duì)環(huán)境適應(yīng)度高的、牛B的個(gè)體參與繁殖的機(jī)會(huì)比較多，后代就會(huì)越來越多。適應(yīng)度低的個(gè)體參與繁殖的機(jī)會(huì)比較少，后代就會(huì)越來越少。

遺傳與變異：新個(gè)體會(huì)遺傳父母雙方各一部分的基因，同時(shí)有一定的概率發(fā)生基因變異。

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

GA的組成:

編碼（產(chǎn)生初始種群）

適應(yīng)度函數(shù)

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

運(yùn)行參數(shù)

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

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

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

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

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

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

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

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

值編碼 （二進(jìn)制編碼不好用時(shí)，解決復(fù)雜的數(shù)值問題）

在值編碼中，每個(gè)基因就是一串取值。這些取值可以是與問題有關(guān)任何值：整數(shù)，實(shí)數(shù)，字符或者其他一些更復(fù)雜的東西。

適應(yīng)度函數(shù) ( Fitness Function )：用于評(píng)價(jià)某個(gè)染色體的適應(yīng)度，用f(x)表示。有時(shí)需要區(qū)分染色體的適應(yīng)度函數(shù)與問題的目標(biāo)函數(shù)。例如：0-1背包問題的目標(biāo)函數(shù)是所取得物品價(jià)值，但將物品價(jià)值作為染色體的適應(yīng)度函數(shù)可能并不一定適合。適應(yīng)度函數(shù)與目標(biāo)函數(shù)是正相關(guān)的，可對(duì)目標(biāo)函數(shù)作一些變形來得到適應(yīng)度函數(shù)。

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

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

輪盤賭算法

/*

* 按設(shè)定的概率，隨機(jī)選中一個(gè)個(gè)體

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

*/

int RWS()

{

m =0;

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

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

{

/* 產(chǎn)生的隨機(jī)數(shù)在m~m+P[i]間則認(rèn)為選中了i

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

*/

m = m + P[i];

if(r<=m) return i;

所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算在GA中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

染色體交叉是以一定的概率發(fā)生的，這個(gè)概率記為Pc 。

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

交叉前：

01 |0010| 11

11 |0111| 01

交叉后：

11 |0010| 01

01 |0111| 11

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

交叉前：

01001011

11011101

交叉后：

01001001

11011111

還有其他交叉方法，參考遺傳算法學(xué)習(xí)心得

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

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

在繁殖過程，新產(chǎn)生的染色體中的基因會(huì)以一定的概率出錯(cuò)，稱為變異。變異發(fā)生的概率記為Pm 。

基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。

變異前：

000001110000000010000

變異后：

000001110000100010000

在個(gè)體中隨機(jī)挑選兩個(gè)逆轉(zhuǎn)點(diǎn)，再將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因交換。 如：

變異前： 1346798205

變異后： 1246798305

GA運(yùn)行時(shí)選擇的參數(shù)應(yīng)該視解決的具體問題而定，到目前為止，還沒有一個(gè)適用于GA所有應(yīng)用領(lǐng)域的關(guān)于算法參數(shù)的理論。下面是一般情況下使用GA時(shí)推薦的參數(shù)：

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

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

種群規(guī)模指的是群體中個(gè)體的個(gè)數(shù)。實(shí)驗(yàn)發(fā)現(xiàn)，比較大的種群的規(guī)模并不能優(yōu)化遺傳算法的結(jié)果。種群的大小推薦使用20-30，一些研究表明，種群規(guī)模 的大小取決于編碼的方法，具體的說就是編碼串（Encoded String）的大小。也就是說，如果說采用32位為基因編碼的時(shí)候種群的規(guī)模大小最好為32的話，那么當(dāng)采用16位為基因編碼時(shí)種群的規(guī)模相應(yīng)應(yīng)變?yōu)樵?來的兩倍。

個(gè)人的想法是，設(shè)定一個(gè)計(jì)數(shù)器，如果連續(xù)N代出現(xiàn)的最優(yōu)個(gè)體的適應(yīng)度都一樣時(shí)，（嚴(yán)格的說應(yīng)該是，連續(xù)N代子代種群的最優(yōu)個(gè)體適應(yīng)度都<=父代最優(yōu)個(gè)性的適應(yīng)度）可以終止運(yùn)算。

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

基本遺傳算法偽代碼



/*

* Pc：交叉發(fā)生的概率

* Pm：變異發(fā)生的概率

* M：種群規(guī)模

* G：終止進(jìn)化的代數(shù)

* Tf：進(jìn)化產(chǎn)生的任何一個(gè)個(gè)體的適應(yīng)度函數(shù)超過Tf，則可以終止進(jìn)化過程

*/

初始化Pm，Pc，M，G，Tf等參數(shù)。隨機(jī)產(chǎn)生第一代種群Pop



do

{ 

　　計(jì)算種群Pop中每一個(gè)體的適應(yīng)度F(i)。

　　初始化空種群newPop

　　do

　　{

　　　　根據(jù)適應(yīng)度以比例選擇算法從種群Pop中選出2個(gè)個(gè)體

　　　　if ( random ( 0 , 1 ) < Pc )

　　　　{

　　　　　　對(duì)2個(gè)個(gè)體按交叉概率Pc執(zhí)行交叉操作

　　　　}

　　　　if ( random ( 0 , 1 ) < Pm )

　　　　{

　　　　　　對(duì)2個(gè)個(gè)體按變異概率Pm執(zhí)行變異操作

　　　　}

將2個(gè)新個(gè)體加入種群newPop中

} until ( M個(gè)子代被創(chuàng)建 )

用newPop取代Pop

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

下面的方法可優(yōu)化遺傳算法的性能。

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

六千五百萬年以前，恐龍和靈長(zhǎng)類動(dòng)物并存，恐龍?jiān)诘厍蛏险冀^對(duì)統(tǒng) 治地位，如果恐龍沒有滅絕靈長(zhǎng)類動(dòng)物是絕沒有可能統(tǒng)治地球的。正是恐龍的滅絕才使靈長(zhǎng)類動(dòng)物有了充分進(jìn)化的余地，事實(shí)上地球至少經(jīng)歷了5次物種大滅絕，每 次物種滅絕都給更加高級(jí)的生物提供了充分進(jìn)化的余地。所以要跳出局部極值就必須殺死當(dāng)前所有的優(yōu)秀個(gè)體，從而讓遠(yuǎn)離當(dāng)前極值的點(diǎn)有充分的進(jìn)化余地。這就是災(zāi)變的思想。”

災(zāi)變就是殺掉最優(yōu)秀的個(gè)體，這樣才可能產(chǎn)生更優(yōu)秀的物種。那何時(shí)進(jìn)行災(zāi)變，災(zāi)變次數(shù)又如何設(shè)定？

何時(shí)進(jìn)行災(zāi)變，可以采用災(zāi)變倒計(jì)數(shù)的方式。如果n代還沒有出現(xiàn)比之前更優(yōu)秀的個(gè)體時(shí)，可以發(fā)生災(zāi)變。災(zāi)變次數(shù)可以這樣來確定，如果若干次災(zāi)變后產(chǎn)生的個(gè)體的適應(yīng)度與沒災(zāi)變前的一樣，可停止災(zāi)變。

當(dāng)利用交叉和變異產(chǎn)生新的一代時(shí)，我們有很大的可能把在某個(gè)中間步驟中得到的最優(yōu)解丟失。

精英主義的思想是,在每一次產(chǎn)生新的一代時(shí)，首先把當(dāng)前最優(yōu)解原封不動(dòng)的復(fù)制到新的一代中。然后按照前面所說的那樣做就行。精英主義方法可以大幅提高運(yùn)算速度，因?yàn)樗梢苑乐箒G失掉找到的最好的解。

精英主義是基本遺傳算法的一種優(yōu)化。為了防止進(jìn)化過程中產(chǎn)生的最優(yōu)解被交叉和變異所破壞，可以將每一代中的最優(yōu)解原封不動(dòng)的復(fù)制到下一代中。

由上面看來,災(zāi)變與精英主義之間似乎存在著矛盾.前者是將產(chǎn)生的最優(yōu)個(gè)體殺掉,而后者是將最優(yōu)秀個(gè)體基因直接保存到下一代.

應(yīng)該辯證地看待它們之間的矛盾,兩者其實(shí)是可以共存的.我們?cè)诿恳淮M(jìn)行交叉運(yùn)算時(shí),均直接把最優(yōu)秀的個(gè)體復(fù)制到下一代;但當(dāng)連續(xù)N代,都沒有更優(yōu) 秀的個(gè)體出現(xiàn)時(shí),便可以猜想可能陷入局部最優(yōu)解了,這樣可以采用災(zāi)變的手段.可以說,精英主義是伴隨的每一代的,但災(zāi)變卻不需要經(jīng)常發(fā)生,否則算法可能下 降為隨機(jī)搜索了.

當(dāng)然,每個(gè)算法中不一定要用精英主義和災(zāi)變的手段,應(yīng)該根據(jù)具體的問題而定

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

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

不是盲目窮舉，而是啟發(fā)式搜索；

適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。

容易實(shí)現(xiàn)。一旦有了一個(gè)遺傳算法的程序，如果想解決一個(gè)新的問題，只需針對(duì)新的問題重新進(jìn)行基因編碼就行；如果編碼方法也相同，那只需要改變一下適應(yīng)度函數(shù)就可以了。

全局搜索能力不強(qiáng),很容易陷入局部最優(yōu)解跳不出來；(可結(jié)合SA進(jìn)行改進(jìn),因?yàn)镾A在理率上是100%得到全局最優(yōu)的,但搜索代價(jià)高)

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

參考文獻(xiàn)都是干貨！！！參考文獻(xiàn)都是干貨！！！參考文獻(xiàn)都是干貨！！！

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

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

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

遺傳算法理論基礎(chǔ)與簡(jiǎn)單應(yīng)用實(shí)例
博主總結(jié)整理的內(nèi)容，挺不錯(cuò)的，文中的鏈接有實(shí)例應(yīng)用。

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

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

遺傳算法學(xué)習(xí)心得

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