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

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

中圖分類號：U293.13

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻：

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

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

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

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

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