1. 本文目的

本文簡要地對遺傳算法進行闡述，讓以前沒有接觸過遺傳算法的人有個大概的認識，并了解遺傳算法的工作原理

2. 生物的遺傳與進化

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

(2)雜交(crossover)：當兩個生物機體配對和復制時，它們的染色體互相混合，產生一個 由雙方基因組成的全新染色體組，這一過程就叫雜交。這意味著后代繼承的大部分可能 是上一代的優良基因，也可能繼承了它們的不良基因。如果是前一種情況，后代就可能 變得比它的父母更優秀，而對于后一種情況，后代就可能變得不如它的父母。

(3)變異(mutate)：當基因傳遞給子孫后代的過程中，會有很小的概率發生差錯，從而使 基因得到微小的改變。生物的進化都是利用無數微小的變異發展而來的，前提是這些變 異是對生物生存有利的變異。

(4)適應性分數(fitness)：越是能適應環境的子孫后代就越有可能繼續復制基因并將其傳 給下一個子孫后代。由此就會顯示一種趨勢，每一代總是比它的上一代更優秀。

3. 計算機中的遺傳算法

遺傳算法在計算機中的工作過程實質上就是模擬了生物的進化過程。

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

(2)然后創建一個由隨機的染色體組成的初始群體(每個染色體代表一個不同的候選解)， 并在一段時期中用于培育適應性最強的個體的辦法，讓它們進化。

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

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

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

4. 遺傳算法中對其他名詞的解釋

(1)雜交率：雜交率就是用來確定兩個染色體進行局部互換以產生兩個新的子代的概率。

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

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

5. 遺傳算法的實現

通常代表可行解的染色體采用某種方式進行編碼。在運行開始時，首先創建一個染 色體的種群，當一個初始群體已經被創建好了后，就開始做下面的一系列工作了：

不斷循環，直到尋找出一個解

1. 檢查每個染色體，看它解決問題的性能怎樣，并相應地為它分配一個適應性分 數。

2. 從當前群體選出兩個成員。選出的概率與染色體的適應性成正比，適應分數越 高，被選中的概率越大。常用的方法就是輪賭選擇法(roulette wheel selection)。

3. 按照預先設定的雜交率(crossover rate),從每個選中染色體的一個隨機確定的點 上進行雜交。

4. 按照預定的變異率(mutation rate),通過對被選染色體的位的循環，把相應的位進 行翻轉。

5. 重復步驟 2，3，4，直到新的群體被創建出來。 結束循環

算法由步驟 1 到步驟 5 的一次循環稱為一代(generation)。這里把整個的循環稱 為一個時代(epoch)。