遺傳算法入門

轉載自：http://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html

優化算法入門系列文章目錄（更新中）：

1.?模擬退火算法

2.?遺傳算法

遺傳算法 ( GA , Genetic Algorithm ) ，也稱進化算法 。 遺傳算法是受達爾文的進化論的啟發，借鑒生物進化過程而提出的一種啟發式搜索算法。因此在介紹遺傳算法前有必要簡單的介紹生物進化知識。

一.進化論知識

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

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

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

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

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

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

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

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

二.遺傳算法思想

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

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

編碼：需要將問題的解編碼成字符串的形式才能使用遺傳算法。最簡單的一種編碼方式是二進制編碼，即將問題的解編碼成二進制位數組的形式。例如，問題的解是整數，那么可以將其編碼成二進制位數組的形式。將0-1字符串作為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; } }

交叉(Crossover)：2條染色體交換部分基因，來構造下一代的2條新的染色體。例如：

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

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

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

變異前：

000001110000000010000

變異后：

000001110000100010000

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

三.基本遺傳算法的偽代碼

/* * 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 )

四.基本遺傳算法優化

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

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

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

機器學習

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。