1. 本文目的

本文簡(jiǎn)要地對(duì)遺傳算法進(jìn)行闡述，讓以前沒(méi)有接觸過(guò)遺傳算法的人有個(gè)大概的認(rèn)識(shí)，并了解遺傳算法的工作原理

2. 生物的遺傳與進(jìn)化

(1)基因組(genome)：生物細(xì)胞中的染色體組包含了復(fù)制該生物所需的全部信息，染色體 中的這一集合就被稱為生物機(jī)體的基因組。

(2)雜交(crossover)：當(dāng)兩個(gè)生物機(jī)體配對(duì)和復(fù)制時(shí)，它們的染色體互相混合，產(chǎn)生一個(gè) 由雙方基因組成的全新染色體組，這一過(guò)程就叫雜交。這意味著后代繼承的大部分可能 是上一代的優(yōu)良基因，也可能繼承了它們的不良基因。如果是前一種情況，后代就可能 變得比它的父母更優(yōu)秀，而對(duì)于后一種情況，后代就可能變得不如它的父母。

(3)變異(mutate)：當(dāng)基因傳遞給子孫后代的過(guò)程中，會(huì)有很小的概率發(fā)生差錯(cuò)，從而使 基因得到微小的改變。生物的進(jìn)化都是利用無(wú)數(shù)微小的變異發(fā)展而來(lái)的，前提是這些變 異是對(duì)生物生存有利的變異。

(4)適應(yīng)性分?jǐn)?shù)(fitness)：越是能適應(yīng)環(huán)境的子孫后代就越有可能繼續(xù)復(fù)制基因并將其傳 給下一個(gè)子孫后代。由此就會(huì)顯示一種趨勢(shì)，每一代總是比它的上一代更優(yōu)秀。

3. 計(jì)算機(jī)中的遺傳算法

遺傳算法在計(jì)算機(jī)中的工作過(guò)程實(shí)質(zhì)上就是模擬了生物的進(jìn)化過(guò)程。

(1)首先，應(yīng)確定一種編碼方法，使得問(wèn)題的任何一個(gè)潛在的可行解都能表示成為一個(gè)“數(shù) 字”染色體。

(2)然后創(chuàng)建一個(gè)由隨機(jī)的染色體組成的初始群體(每個(gè)染色體代表一個(gè)不同的候選解)， 并在一段時(shí)期中用于培育適應(yīng)性最強(qiáng)的個(gè)體的辦法，讓它們進(jìn)化。

(3)在此期間，染色體的某些位置上要加入少量的變異。

(4)經(jīng)過(guò)許多代后，遺傳算法將會(huì)收斂到一個(gè)解，但遺傳算法不能確保一定能得到解，如 果有解也不確保找到的是最優(yōu)解，但只要采用的方法正確，通常都能為遺傳算法編出一 個(gè)能夠運(yùn)行很好的程序。

(5)遺傳算法的最大優(yōu)點(diǎn)就是，你不需要知道怎么去解決一個(gè)問(wèn)題，僅需要知道用什么樣 的方式對(duì)可行解進(jìn)行編碼，使得它能被遺傳算法機(jī)制所利用。

4. 遺傳算法中對(duì)其他名詞的解釋

(1)雜交率：雜交率就是用來(lái)確定兩個(gè)染色體進(jìn)行局部互換以產(chǎn)生兩個(gè)新的子代的概率。

(2)變異率：變異率就是對(duì)染色體進(jìn)行位變異操作的概率。

(3)TSP巡回銷售員問(wèn)題(Traveling Salesman Problem) ： 給定幾個(gè)城市，巡回銷售員必須決定一條最短的路線，使他能夠訪問(wèn)到每個(gè)城市一次， 然后返回他的起點(diǎn)。

5. 遺傳算法的實(shí)現(xiàn)

通常代表可行解的染色體采用某種方式進(jìn)行編碼。在運(yùn)行開(kāi)始時(shí)，首先創(chuàng)建一個(gè)染 色體的種群，當(dāng)一個(gè)初始群體已經(jīng)被創(chuàng)建好了后，就開(kāi)始做下面的一系列工作了：

不斷循環(huán)，直到尋找出一個(gè)解

1. 檢查每個(gè)染色體，看它解決問(wèn)題的性能怎樣，并相應(yīng)地為它分配一個(gè)適應(yīng)性分 數(shù)。

2. 從當(dāng)前群體選出兩個(gè)成員。選出的概率與染色體的適應(yīng)性成正比，適應(yīng)分?jǐn)?shù)越 高，被選中的概率越大。常用的方法就是輪賭選擇法(roulette wheel selection)。

3. 按照預(yù)先設(shè)定的雜交率(crossover rate),從每個(gè)選中染色體的一個(gè)隨機(jī)確定的點(diǎn) 上進(jìn)行雜交。

4. 按照預(yù)定的變異率(mutation rate),通過(guò)對(duì)被選染色體的位的循環(huán)，把相應(yīng)的位進(jìn) 行翻轉(zhuǎn)。

5. 重復(fù)步驟 2，3，4，直到新的群體被創(chuàng)建出來(lái)。 結(jié)束循環(huán)

算法由步驟 1 到步驟 5 的一次循環(huán)稱為一代(generation)。這里把整個(gè)的循環(huán)稱 為一個(gè)時(shí)代(epoch)。