遺傳演算法 - 基礎知識

本節介紹理解遺傳演算法所需的基本術語。此外，還以**虛擬碼和圖形形式**展示了遺傳演算法的通用結構。建議讀者充分理解本節介紹的所有概念，並在閱讀本教程的其他部分時牢記這些概念。

基本術語

在開始討論遺傳演算法之前，必須熟悉一些在本教程中將反覆使用的基本術語。

**種群** − 它是在給定問題的所有可能（編碼）解中的一部分。遺傳演算法的種群類似於人類的種群，只不過我們用候選解來表示人類。
**染色體** − 染色體是給定問題的一個解。
**基因** − 基因是染色體的一個元素位置。
**等位基因** − 它是一個基因對於特定染色體所取的值。

**基因型** − 基因型是在計算空間中的種群。在計算空間中，解以一種易於使用計算系統理解和操作的方式表示。
**表現型** − 表現型是在實際現實世界解空間中的種群，其中解以現實世界中表示的方式表示。
**解碼和編碼** − 對於簡單問題，**表現型和基因型**空間相同。但是，在大多數情況下，表現型和基因型空間是不同的。解碼是從基因型到表現型空間轉換解的過程，而編碼是從表現型到基因型空間轉換的過程。解碼應該很快，因為它在遺傳演算法中在適應度值計算期間被反覆執行。

例如，考慮0/1揹包問題。表現型空間包含僅包含要選擇的物品的物品編號的解。

但是，在基因型空間中，它可以表示為長度為n的二進位制字串（其中n是物品的數量）。**位置x處的0**表示**第x個**物品被選中，而1表示相反。這是一種基因型和表現型空間不同的情況。

**適應度函式** − 簡單來說，適應度函式是一個以解作為輸入併產生解的適用性作為輸出的函式。在某些情況下，適應度函式和目標函式可能相同，而在其他情況下，根據問題可能不同。
**遺傳運算元** − 這些改變後代的遺傳組成。這些包括交叉、變異、選擇等。

基本結構

遺傳演算法的基本結構如下：

我們從一個初始種群開始（可以隨機生成或由其他啟發式演算法播種），從該種群中選擇父母進行交配。對父母應用交叉和變異運算元以生成新的後代。最後，這些後代替換種群中的現有個體，並且該過程重複。這樣，遺傳演算法實際上在一定程度上模仿了人類進化。

以下每個步驟將在本教程後面的單獨章節中介紹。

遺傳演算法的通用虛擬碼在以下程式中解釋：

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best

列印頁面