由一道實例看遺傳算法

摘 要：本文由一道題目為例，講解了遺傳算法的步驟。遺傳算法由選擇，交叉，變異三個操作組成，選擇就是將實際問題數(shù)學化，對問題進行編碼，組成二進制代碼。交叉就是二進制代碼的雜交，產生下一代族群，并且通過適應度函數(shù)，計算出一個適應值，從而產生生存能力更強（適應值大）的個體，淘汰生存能力差（適應值?。┑膫€體，從而實現(xiàn)優(yōu)勝劣汰。在遺傳算法中，還有可能產生變異，變異的基因有可能讓個體更具有生命力。

關鍵詞：遺傳算法；概率搜索；尋優(yōu)算法

中圖分類號：U293.13

遺傳算法（GA），是一種概率搜索的尋優(yōu)算法，它采用的策略就是模擬自然選擇，利用編碼技術將一些二進制串表示為染色體，然后用計算數(shù)學的方法，模擬這些染色體組成群體的進化過程。GA是建立在達爾文進化論的基礎上的，以優(yōu)勝劣汰和自然選擇為推動力，找出適應環(huán)境能力更強的基因，并認為在自然發(fā)展過程中，良好的基因相交以及基因突變都有可能會產生生存能力更強的后代來。正是根據(jù)這一理論，美國科學家John.Holland在1975年的時候，提出來遺傳算法基本定理-模式定理，從而奠定了遺傳算法的理論基礎，也成為了21世紀最重要的智能算法之一。

遺傳算法的過程主要有三個的操作，這三個操作就是模擬自然界生物進化和遺傳的過程，第一個步驟就是選擇，所謂選擇就是找出要解決的問題，并且將其表示為染色體，即將要解決的問題用計算機數(shù)學的方式表達出來，遺傳算法中是用二進制編碼的串來表示“染色體”，這些染色體是假設的問題的可行解。第二個操作就是交叉，所謂交叉就是模擬自然界中生物雜交的過程，經(jīng)過雜交全產生新一代，從中選擇更適合的染色體。第三個操作是變異，所謂變異就是指在交叉過程中產生的新一代染色體中，有些可能已和上一代有明顯的差別，這就是變異，變異的染色體，有的更適合問題的解，當然也有的是要淘汰的。經(jīng)過這樣一代代的復制，交叉，變異的過程后，問題會收斂在唯一（也有可能是多個）的染色體上，那么這個染色體就是此問題的最優(yōu)解，這就是遺傳算法的工作原理和步驟。

下面我們通過一個例子來說明，遺傳算法的過程。

首先就要把這個題目轉換成遺傳算法最基本的表達方式，基因染色體的表達。在區(qū)間[-1，2]內的所有點在不知道答案前都有可能是此題目的解。所以如何將這個區(qū)間所有的點編碼就成了遺傳算法中最關鍵的一步，并且要求編碼空間的所有染色體（點），和空間的所有潛在解要實現(xiàn)一一對應。

假設此題目要求是精確到6位小數(shù)，那么應該用幾位二進制編碼來表示區(qū)間的所有點呢？區(qū)間的長度是3，精確到6位小數(shù)則總的長度為3×106，即將這個區(qū)間平分成3×106等份。因為221<3×106<222，所以這里需要22（n21n20n19…n1n0）位二進制數(shù)，來表示區(qū)間內的所有可能解。

將一個二進制數(shù)（n21n20n19…n1n0）轉換成對應區(qū)間的十進制數(shù)就是非常簡單的事情了：

利用這種方法可以將十進制區(qū)間的數(shù)字轉化成二進制，完成遺傳算法的很重要的一步——編碼。接下來要做的事情就是定義一個適應度函數(shù)和適應值，所謂適應度函數(shù)主要用于評價個體的優(yōu)劣程度，應度越大個體越好，根據(jù)適應度的大小對個體進行選擇，遺傳算法中要求適應度函數(shù)值必須是非負數(shù)。

對于本題來說，求的是最大值的問題，這里定義適應度函數(shù)為g（x），采用下述方法：

通過公式（4），我們可以得出上述所選四個個體的入選概率分別是p（x1）=0.175636，p（x2）=0.147918，p（x3）=0，p（x4）=0.676446。所謂入選概率，就是指的其生存能力，入選概率大的個體說明其生存能力強，即染色體比較健壯，可以選入下一代種群，而入選概率較小的個體則淘汰出局，在淘汰的同時，需要將入選概率最大的個體補入，得到與原族群個數(shù)相同的群體。由上術入選概率可以看出，我們需要淘汰的是每三個個體，同時要將第一個個體補入。也就是新的族群中，有兩個相同的個體。

數(shù)據(jù)交叉，交叉對應了自然界中的雜交，也就是繁衍下一代，將族群中的兩個體染色體上的二進制數(shù)交換得到新染色體，從而生成新的群體。在做雜交時，基因完全相同的不能配對，不相同的兩兩配對，進行交叉，交叉可以在任何位置截取。比如前兩個個體，這是組合前的一組數(shù)據(jù)（為了更好的說明問題，我把兩個染色體給分了段）101010100 1011000111011，100100101 0110001110101，交叉組合后變成了1010101000110001110101，1001001011011000111011，同樣的道理，以第一個個體代替淘汰的第三個個體，和第四個個體交叉也可以得到新的兩個個體：0010001011010110010110，1110101101110101101110，和剛才生成的那兩個就形成了一個新群體。

在生成新群體時，也有可能產生變異，所謂的變異，在遺傳算法上就表現(xiàn)為隨機位置上數(shù)字翻轉，由1變成0，或由0變成1，并對由此產生的新的群體進重新上述的操作，如此循環(huán)往復，使群體中最優(yōu)個體的適應度和平均適應度不斷提高。變異可保持群體的多樣性，可使遺傳算法跳出局部極值點。

這是遺傳算法的一個完整的步驟，然后一直重復上述步驟，進行選擇，交叉直至滿足最終條件為止。從以上描述可以看出，如果用人工的方式去用遺傳算法，可以說是繁瑣無比，但是用在計算數(shù)學上，它就是一種很好的智能優(yōu)化算法。

參考文獻：

[1]謝小山.基于遺傳算法和BP神經(jīng)網(wǎng)絡的鐵路客運量預測研究[D]，西南交通大學，2010.

[2]傅薈璇，趙紅.MATLAB神經(jīng)網(wǎng)絡應用設計[M].北京：機械工業(yè)出版社.2009：27-29.

[3]馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究，2012（04）.

作者簡介：程憲寶（1978-），男，山東人，講師，碩士，研究方向：智能算法。

作者單位：廣州工商學院，廣州 510850；中山大學信息科學與技術學院，廣州 510275