標籤：

如何通俗易懂地解釋遺傳演算法？有什麼例子？

12-28
方弦在科學松鼠會上這篇寫的就挺清楚：

這是個真實的故事。

從前在海岸邊有一群扇貝在悠哉游哉地生活繁衍著。它們自然是衣食不愁，連房子也有了著落。它們擔憂的只有一件事：每隔一段時間，總有一個人來挖走它們之中的一部分。當然啦，挖回去幹什麼這大家都知道。但扇貝們不知道的是，這人的家族圖騰是Firefox的圖標，所以他總是選擇那些貝殼花紋長得比較不像Firefox圖標的扇貝。

這種狀況持續了好幾十萬代。大家應該也猜到扇貝們身上發生什麼事情了：它們的貝殼上都印著很像Firefox圖標的圖案。

可能有些讀者會說：你這不是糊弄我們么，Firefox才有多少年歷史，你就搞了個幾十萬代的扇貝？

確有其事，但是這些扇貝不是真實的，它們在我電腦的內存裡邊生活。它們是一個遺傳演算法程序的一部分，這個程序的目的就是用100個半透明三角形把Firefox的圖標儘可能像地畫出來。

什麼是遺傳演算法呢？

簡單地說，遺傳演算法是一種解決問題的方法。它模擬大自然中種群在選擇壓力下的演化，從而得到問題的一個近似解。

在二十世紀五十年代，生物學家已經知道基因在自然演化過程中的作用了，而他們也希望能在新出現的計算機上模擬這個過程，用以嘗試定量研究基因與進化之間的關係。這就是遺傳演算法的濫觴。後來，有人將其用於解決優化問題，於是就產生了遺傳演算法。

那麼，具體來說，在計算機裡邊是怎麼模擬進化過程的呢？

我們還是以開頭提到的程序為例。

首先，我們知道，生物個體長什麼樣子很大程度上是由染色體上的基因決定的。同樣，如果我們把100個半透明三角形組成的東西看成一個生物個體的話（為了說話方便，稱為扇貝吧），我們也可以說它的樣子是由這些三角形的具體位置和顏色決定的。所以，我們可以把一個一個的半透明三角形看作是這些扇貝的「基因」。而組成扇貝的這100個基因就組成了每個扇貝個體的「染色體」（chromosome）。

從下面的圖可以大約看出來這些基因是怎麼決定扇貝的樣子的（為了觀看方便，我們只畫出其中五個三角形）：

然後，扇貝們除了生活，當然還要繁衍後代。生物界中的繁衍無非就是父母的基因組合產生新的個體，而在這個程序裡邊我們當然也這麼辦：選擇兩個原有的扇貝，然後從這兩個扇貝的染色體中隨機選取一共100個基因組成新個體的染色體。如圖所示：（仍然是將扇貝看成是五個三角形組成的）

為了產生新的基因，使基因的種類更多樣化，在組合的時候，新的扇貝的基因有一定的概率發生變異。也就是說，其中的一個透明三角形的位置或者顏色會隨機改變，如圖（仍然是五個三角形……我偷工減料……）：

其次，為了使扇貝的樣子向Firefox圖標靠近，我們要給它們加上一點選擇壓力，就是文章開頭故事中提到的那個人的行動：在每一代把最不像Firefox的扇貝淘汰出去，同時也給新的個體留下生存的空間。怎麼評價這個扇貝像不像Firefox呢？最直接的方法就是一個一個像素比較，顏色相差得越多就越不像。這個評價的函數叫做「適應函數」，它負責評價一個個體到底有多適應我們的要求。

在淘汰的過程中，為了便於編程，我們通常會在淘汰舊個體和產生新個體的數目上進行適當的調整，使種群的大小保持不變。淘汰的作用就是使適應我們要求的個體存在的時間更長，從而達到選擇的目的。

最後，在自然界中，種群的演化是一個無休止的過程，但程序總要停下來給出一個結果。那麼，什麼時候終止演化輸出結果呢？這就要訂立一個終止條件，滿足這個條件的話程序就輸出當前最好的結果並停止。最簡單的終止條件就是，如果種群經過了很多代（這裡的「很多」是一個需要設定的參數）之後仍然沒有顯著改變適應性的變異的話，我們就停止並輸出結果。我們就用這個終止條件。

好了，現在是萬事俱備只欠東風了。定義好基因，寫好繁衍、變異、評價適應性、淘汰和終止的代碼之後，只需要隨機產生一個適當大小的種群，然後讓它這樣一代代的繁衍、變異和淘汰下去，到最後終止我們就會獲得一個驚喜的結果：（這回是完整的了，圖片下的數字表示這個扇貝是第幾代中最好的）

怎麼樣？雖說細節上很欠缺，但是也算是不錯了。要不，你來試試用100個透明三角形畫一個更像的？就是這樣的看上去很簡單的模擬演化過程也能解決一些我們這些有智慧的人類也感到棘手的問題。

實際上，在生活和生產中，很多時候並不需要得到一個完美的答案；而很多問題如果要得到完美的答案的話，需要很大量的計算。所以，因為遺傳演算法能在相對較短的時間內給出一個足夠好能湊合的答案，它從問世伊始就越來越受到大家的重視，對它的研究也是方興未艾。當然，它也有缺點，比如說早期的優勢基因可能會很快通過交換基因的途徑散播到整個種群中，這樣有可能導致早熟（premature），也就是說整個種群的基因過早同一化，得不到足夠好的結果。這個問題是難以完全避免的。

其實，通過微調參數和繁衍、變異、淘汰、終止的代碼，我們有可能得到更有效的演算法。遺傳演算法只是一個框架，裡邊具體內容可以根據實際問題進行調整，這也是它能在許多問題上派上用場的一個原因。像這樣可以適應很多問題的演算法還有模擬退火演算法、粒子群演算法、蟻群演算法、禁忌搜索等等，統稱為元啟發式演算法（Meta-heuristic algorithms）。

另外，基於自然演化過程的演算法除了在這裡說到的遺傳演算法以外，還有更廣泛的群體遺傳演算法和遺傳編程等，它們能解決很多棘手的問題。這也從一個側面說明，我們不一定需要一個智能才能得到一個構造精巧的系統。

無論如何，如果我們要將遺傳演算法的發明歸功於一個人的話，我會將它歸功於達爾文，進化論的奠基人。如果我們不知道自然演化的過程，我們也不可能在電腦中模擬它，更不用說將它應用於實際了。

向達爾文致敬！

大三的時候上了一門人工智慧，其中有一次作業就用到了遺傳演算法，問題是這樣的：

求解函數 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在區間[0,9]的最大值。

這個函數大概長這樣：

那麼如何應用遺傳演算法如何來找到這個奇怪的函數的最大值呢？

事實上，不管一個函數的形狀多麼奇怪，遺傳演算法都能在很短的時間內找到它在一個區間內的(近似)最大值。

相當神奇，不是嗎？

接下來圍繞這個問題，講講我對遺傳演算法的一些理解。實現代碼以及在Matlab中使用遺傳演算法的小教程都附在最後。

1.介紹

遺傳演算法(Genetic Algorithm)遵循『適者生存』、『優勝劣汰』的原則，是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索演算法。

遺傳演算法模擬一個人工種群的進化過程，通過選擇(Selection)、交叉(Crossover)以及變異(Mutation)等機制，在每次迭代中都保留一組候選個體，重複此過程，種群經過若干代進化後，理想情況下其適應度達到***近似最優***的狀態。

自從遺傳演算法被提出以來，其得到了廣泛的應用，特別是在函數優化、生產調度、模式識別、神經網路、自適應控制等領域，遺傳演算法發揮了很大的作用，提高了一些問題求解的效率。

2.遺傳演算法組成

  • 編碼 -&> 創造染色體
  • 個體 -&> 種群
  • 適應度函數
  • 遺傳運算元
    • 選擇
    • 交叉
    • 變異
  • 運行參數
    • 是否選擇精英操作
    • 種群大小
    • 染色體長度
    • 最大迭代次數
    • 交叉概率
    • 變異概率

2.1 編碼與解碼

實現遺傳演算法的第一步就是明確對求解問題的編碼和解碼方式。

對於函數優化問題，一般有兩種編碼方式，各具優缺點

  • 實數編碼：直接用實數表示基因，容易理解且不需要解碼過程，但容易過早收斂，從而陷入局部最優
  • 二進位編碼：穩定性高，種群多樣性大，但需要的存儲空間大，需要解碼且難以理解

對於求解函數最大值問題，我選擇的是二進位編碼。

以我們的目標函數 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 為例。

假如設定求解的精度為小數點後4位，可以將x的解空間劃分為 (9-0)×(1e+4)=90000個等分。

2^16&<90000&<2^17，需要17位二進位數來表示這些解。換句話說，一個解的編碼就是一個17位的二進位串。

一開始，這些二進位串是隨機生成的。

一個這樣的二進位串代表一條染色體串，這裡染色體串的長度為17。

對於任何一條這樣的染色體chromosome，如何將它復原(解碼)到[0,9]這個區間中的數值呢？

對於本問題，我們可以採用以下公式來解碼：

x = 0 + decimal(chromosome)×(9-0)/(2^17-1)

decimal( ): 將二進位數轉化為十進位數

一般化解碼公式：

f(x), x∈[lower_bound, upper_bound]
x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/(2^chromosome_size-1)

lower_bound: 函數定義域的下限
upper_bound: 函數定義域的上限
chromosome_size: 染色體的長度

通過上述公式，我們就可以成功地將二進位染色體串解碼成[0,9]區間中的十進位實數解。

2.2 個體與種群

『染色體』表達了某種特徵，這種特徵的載體，稱為『個體』。

對於本次實驗所要解決的一元函數最大值求解問題，個體可以用上一節構造的染色體表示，一個個體里有一條染色體。

許多這樣的個體組成了一個種群，其含義是一個一維點集(x軸上[0,9]的線段)。

2.3 適應度函數

遺傳演算法中，一個個體(解)的好壞用適應度函數值來評價，在本問題中，f(x)就是適應度函數。

適應度函數值越大，解的質量越高。

適應度函數是遺傳演算法進化的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。

2.4 遺傳運算元

我們希望有這樣一個種群，它所包含的個體所對應的函數值都很接近於f(x)在[0,9]上的最大值，但是這個種群一開始可能不那麼優秀，因為個體的染色體串是隨機生成的。

如何讓種群變得優秀呢？

不斷的進化。

每一次進化都儘可能保留種群中的優秀個體，淘汰掉不理想的個體，並且在優秀個體之間進行染色體交叉，有些個體還可能出現變異。

種群的每一次進化，都會產生一個最優個體。種群所有世代的最優個體，可能就是函數f(x)最大值對應的定義域中的點。

如果種群無休止地進化，那總能找到最好的解。但實際上，我們的時間有限，通常在得到一個看上去不錯的解時，便終止了進化。

對於給定的種群，如何賦予它進化的能力呢？

  • 首先是選擇(selection)
    • 選擇操作是從前代種群中選擇***多對***較優個體，一對較優個體稱之為一對父母，讓父母們將它們的基因傳遞到下一代，直到下一代個體數量達到種群數量上限
    • 在選擇操作前，將種群中個體按照適應度從小到大進行排列
    • 採用輪盤賭選擇方法（當然還有很多別的選擇方法），各個個體被選中的概率與其適應度函數值大小成正比
    • 輪盤賭選擇方法具有隨機性，在選擇的過程中可能會丟掉較好的個體，所以可以使用精英機制，將前代最優個體直接選擇
  • 其次是交叉(crossover)
    • 兩個待交叉的不同的染色體(父母)根據交叉概率(cross_rate)按某種方式交換其部分基因
    • 採用單點交叉法，也可以使用其他交叉方法
  • 最後是變異(mutation)
    • 染色體按照變異概率(mutate_rate)進行染色體的變異
    • 採用單點變異法，也可以使用其他變異方法

一般來說，交叉概率(cross_rate)比較大，變異概率(mutate_rate)極低。像求解函數最大值這類問題，我設置的交叉概率(cross_rate)是0.6，變異概率(mutate_rate)是0.01。

因為遺傳演算法相信2條優秀的父母染色體交叉更有可能產生優秀的後代，而變異的話產生優秀後代的可能性極低，不過也有存在可能一下就變異出非常優秀的後代。這也是符合自然界生物進化的特徵的。

3.遺傳演算法流程

附上 matlab 實現代碼: genetic-algorithm

測試結果

  • 最優個體：00011111011111011
  • 最優適應度：24.8554
  • 最優個體對應自變數值：7.8569
  • 達到最優結果需要的迭代次數：多次實驗後發現，達到收斂的迭代次數從20次到一百多次不等

迭代次數與平均適應度關係曲線（橫軸：迭代次數，縱軸：平均適應度）

有現成的工具可以直接使用遺傳演算法，比如 Matlab。
最後就再介紹一下如何在 Matlab 中使用遺傳演算法。

在 MATLAB 中使用 GA 工具

1. 打開 Optimization 工具，在 Solver 中選擇 ga - genetic algorithm，在 Fitness function 中填入 @target

2. 在你的工程文件夾中新建 target.m，注意MATLAB的當前路徑是你的工程文件夾所在路徑

3. 在 target.m 中寫下適應度函數，比如

function [ y ] = target(x)
y = -x-10*sin(5*x)-7*cos(4*x);
end

*MATLAB中的GA只求解函數的(近似)最小值，所以先要將目標函數取反。

4. 打開 Optimization 工具，輸入 變數個數(Number of variables) 和 自變數定義域(Bounds) 的值，點擊 Start，遺傳演算法就跑起來了。最終在輸出框中可以看到函數的(近似)最小值，和達到這一程度的迭代次數(Current iteration)和最終自變數的值(Final point)

5. 在 Optimization - ga 工具中，有許多選項。通過這些選項，可以設置下列屬性

  • 種群(Population)
  • 選擇(Selection)
  • 交叉(Crossover)
  • 變異(Mutation)
  • 停止條件(Stopping criteria)
  • 畫圖函數(Plot functions)

Reference

  • Alex Yu , 簡單遺傳演算法MATLAB實現
  • 《機器學習》/（美）米歇爾 （Mitchell, T. M.）著；曾華軍等譯. —北京：機械工業出版社。

我想讓機器人Bob畫出我的夢中情人（最優解）。Bob當然不知道我夢中情人長啥樣。

Bob很無奈，只能一張張試。先畫一張，問我像不像？我說不像，Bob就重新畫一張。直到我覺得像。

然而Bob又不會畫畫，只會填格子。於是Bob準備了一張1000*1000的格子紙，每個格子可以填黑色或者白色。那麼總共有2^1000000種畫法。如果我能堅持到宇宙毀滅N次，那可以每張都看，然後找到那個最像的。顯然我沒這個耐心。

於是我只讓Bob畫10萬張，畫不出來我就砸了它。

Bob很緊張，開始想辦法，終於想到了遺傳演算法。

第一輪，Bob隨機畫了1萬張（初始種群）。這1萬張裡面，肯定各種亂七八糟，有像星空的，像豬的，像石頭的，等等。然後Bob讓我挑最像的。媽蛋，我強忍怒火，挑出來一堆豬、猴、狗，好歹是哺乳動物。

Bob拿著我挑的「豬猴狗們」，如獲至寶，開始第二輪，將這些畫各種交叉變異一下。比如把一幅畫的耳朵跟另一幅的鼻子換一下，或者再隨機改個眼睛。然後又生成了1萬張圖讓我挑。我挑出來一堆猴子猩猩，好歹是靈長類動物。

如此反覆好多輪後，挑出來的開始像人了，雖然有男人、女人、小孩。
慢慢地，開始有美女了。再慢慢地，就越來越像了。

在畫了10萬張圖後，終於找到一張還不錯的。雖然不是夢中情人，但也很不錯吶（次優解）。

這就是遺傳演算法。

微信公眾號：小牛八卦
關注小牛八卦，學習智能工具。

基因遺傳演算法是一種靈感源於達爾文自然進化理論的啟發式搜索演算法。該演算法反映了自然選擇的過程，即最適者被選定繁殖，併產生下一代。

以下文章選自Medium，作者：MallawaarachchiFollow，由機器之心編譯。原文地址在此。

教程 | 遺傳演算法的基本概念和實現（附Java實現案例）

如上圖（左）所示，遺傳演算法的個體由多條染色體組成，每條染色體由多個基因組成。上圖（右）展示了染色體分割和組合的方式。

遺傳演算法的概念

自然選擇的過程從選擇群體中最適應環境的個體開始。後代繼承了父母的特性，並且這些特性將添加到下一代中。如果父母具有更好的適應性，那麼它們的後代將更易於存活。迭代地進行該自然選擇的過程，最終，我們將得到由最適應環境的個體組成的一代。

這一概念可以被應用於搜索問題中。我們考慮一個問題的諸多解決方案，並從中搜尋出最佳方案。

遺傳演算法含以下五步：

  1. 初始化
  2. 個體評價（計算適應度函數）
  3. 選擇運算
  4. 交叉運算
  5. 變異運算

初始化

該過程從種群的一組個體開始，且每一個體都是待解決問題的一個候選解。

個體以一組參數（變數）為特徵，這些特徵被稱為基因，串聯這些基因就可以組成染色體（問題的解）。

在遺傳演算法中，單個個體的基因組以字元串的方式呈現，通常我們可以使用二進位（1 和 0 的字元串）編碼，即一個二進位串代表一條染色體串。因此可以說我們將基因串或候選解的特徵編碼在染色體中。

種群、染色體和基因

個體評價（計算適應度函數）

個體評價利用適應度函數評估了該個體對環境的適應度（與其它個體競爭的能力）。每一個體都有適應度評分，個體被選中進行繁殖的可能性取決於其適應度評分。適應度函數值越大，解的質量就越高。適應度函數是遺傳演算法進化的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。

選擇運算

選擇運算的目的是選出適應性最好的個體，並使它們將基因傳到下一代中。基於其適應度評分，我們選擇多對較優個體（父母）。適應度高的個體更易被選中繁殖，即將較優父母的基因傳遞到下一代。

交叉運算

交叉運算是遺傳演算法中最重要的階段。對每一對配對的父母，基因都存在隨機選中的交叉點。

舉個例子，下圖的交叉點為 3：

父母間在交叉點之前交換基因，從而產生了後代。

父母間交換基因，然後產生的新後代被添加到種群中。

變異運算

在某些形成的新後代中，它們的某些基因可能受到低概率變異因子的作用。這意味著二進位位串中的某些位可能會翻轉。

變異運算前後

變異運算可用於保持種群內的多樣性，並防止過早收斂。

終止

在群體收斂的情況下（群體內不產生與前一代差異較大的後代）該演算法終止。也就是說遺傳演算法提供了一組問題的解。

案例實現

種群的規模恆定。新一代形成時，適應度最差的個體凋亡，為後代留出空間。這些階段的序列被不斷重複，以產生優於先前的新一代。

這一迭代過程的偽代碼：

START
Generate the initial population
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
UNTIL population has converged
STOP

Java 中的實例實現

以下展示的是遺傳演算法在 Java 中的示例實現，我們可以隨意調試和修改這些代碼。給定一組五個基因，每一個基因可以保存一個二進位值 0 或 1。這裡的適應度是基因組中 1 的數量。如果基因組內共有五個 1，則該個體適應度達到最大值。如果基因組內沒有 1，那麼個體的適應度達到最小值。該遺傳演算法希望最大化適應度，並提供適應度達到最大的個體所組成的群體。注意：本例中，在交叉運算與突變運算之後，適應度最低的個體被新的，適應度最高的後代所替代。

import java.util.Random;

/**
*
* @author Vijini
*/

//Main class
public class SimpleDemoGA {

Population population = new Population();
Individual fittest;
Individual secondFittest;
int generationCount = 0;

public static void main(String[] args) {

Random rn = new Random();

SimpleDemoGA demo = new SimpleDemoGA();

//Initialize population
demo.population.initializePopulation(10);

//Calculate fitness of each individual
demo.population.calculateFitness();

System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);

//While population gets an individual with maximum fitness
while (demo.population.fittest &< 5) { ++demo.generationCount; //Do selection demo.selection(); //Do crossover demo.crossover(); //Do mutation under a random probability if (rn.nextInt()%7 &< 5) { demo.mutation(); } //Add fittest offspring to population demo.addFittestOffspring(); //Calculate new fitness value demo.population.calculateFitness(); System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest); } System.out.println(" Solution found in generation " + demo.generationCount); System.out.println("Fitness: "+demo.population.getFittest().fitness); System.out.print("Genes: "); for (int i = 0; i &< 5; i++) { System.out.print(demo.population.getFittest().genes[i]); } System.out.println(""); } //Selection void selection() { //Select the most fittest individual fittest = population.getFittest(); //Select the second most fittest individual secondFittest = population.getSecondFittest(); } //Crossover void crossover() { Random rn = new Random(); //Select a random crossover point int crossOverPoint = rn.nextInt(population.individuals[0].geneLength); //Swap values among parents for (int i = 0; i &< crossOverPoint; i++) { int temp = fittest.genes[i]; fittest.genes[i] = secondFittest.genes[i]; secondFittest.genes[i] = temp; } } //Mutation void mutation() { Random rn = new Random(); //Select a random mutation point int mutationPoint = rn.nextInt(population.individuals[0].geneLength); //Flip values at the mutation point if (fittest.genes[mutationPoint] == 0) { fittest.genes[mutationPoint] = 1; } else { fittest.genes[mutationPoint] = 0; } mutationPoint = rn.nextInt(population.individuals[0].geneLength); if (secondFittest.genes[mutationPoint] == 0) { secondFittest.genes[mutationPoint] = 1; } else { secondFittest.genes[mutationPoint] = 0; } } //Get fittest offspring Individual getFittestOffspring() { if (fittest.fitness &> secondFittest.fitness) {
return fittest;
}
return secondFittest;
}

//Replace least fittest individual from most fittest offspring
void addFittestOffspring() {

//Update fitness values of offspring
fittest.calcFitness();
secondFittest.calcFitness();

//Get index of least fit individual
int leastFittestIndex = population.getLeastFittestIndex();

//Replace least fittest individual from most fittest offspring
population.individuals[leastFittestIndex] = getFittestOffspring();
}

}

//Individual class
class Individual {

int fitness = 0;
int[] genes = new int[5];
int geneLength = 5;

public Individual() {
Random rn = new Random();

//Set genes randomly for each individual
for (int i = 0; i &< genes.length; i++) { genes[i] = rn.nextInt() % 2; } fitness = 0; } //Calculate fitness public void calcFitness() { fitness = 0; for (int i = 0; i &< 5; i++) { if (genes[i] == 1) { ++fitness; } } } } //Population class class Population { int popSize = 10; Individual[] individuals = new Individual[10]; int fittest = 0; //Initialize population public void initializePopulation(int size) { for (int i = 0; i &< individuals.length; i++) { individuals[i] = new Individual(); } } //Get the fittest individual public Individual getFittest() { int maxFit = Integer.MIN_VALUE; for (int i = 0; i &< individuals.length; i++) { if (maxFit &<= individuals[i].fitness) { maxFit = i; } } fittest = individuals[maxFit].fitness; return individuals[maxFit]; } //Get the second most fittest individual public Individual getSecondFittest() { int maxFit1 = 0; int maxFit2 = 0; for (int i = 0; i &< individuals.length; i++) { if (individuals[i].fitness &> individuals[maxFit1].fitness) {
maxFit2 = maxFit1;
maxFit1 = i;
} else if (individuals[i].fitness &> individuals[maxFit2].fitness) {
maxFit2 = i;
}
}
return individuals[maxFit2];
}

//Get index of least fittest individual
public int getLeastFittestIndex() {
int minFit = 0;
for (int i = 0; i &< individuals.length; i++) { if (minFit &>= individuals[i].fitness) {
minFit = i;
}
}
return minFit;
}

//Calculate fitness of each individual
public void calculateFitness() {

for (int i = 0; i &< individuals.length; i++) { individuals[i].calcFitness(); } getFittest(); } }

文章發佈於微信公眾號：機器之心（almosthuman2014），如需轉載，請私信聯繫，非常感謝。

大三軟體工程學生，以前只聽過遺傳演算法這個名字，但是真正是怎麼一回事沒有了解過。今天剛好看到 @sjyan 的回答，想起這學期正好選了人工智慧這堂課，就覺得想試著碼一下這個演算法，算是提前預習一下。於是花了兩個小時把這個演算法大概搞懂了，把思路寫一遍，也算是自己再熟悉一遍（如果哪裡搞錯了請大神們輕噴


理解這個演算法首先要理解一些術語。下圖(來自Genetic Algorithms Fundamentals)把術語之間的關係表示的很清楚。

遺傳演算法就是通過不斷地進化，將種群裡面我們最想要的染色體保留下來。進化多次之後，種群里的大部分染色體都會是比較優勢的染色體（我們想要的解），所以我們可以通過這個演算法獲取多個較優解。


ps: 關於基因和等位基因的區別：基因(gene)是指染色體上的特定位置，而等位基因(allele)則是當前染色體在該基因處的值。


知道一些術語之間的關係之後，可以試著嘗試搞懂演算法了。拿@sjyan剛剛這道題做例子。

求解函數 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在區間[0,9]的最大值。

用遺傳演算法解這道題的過程， 他說得很清楚，主要是三個階段：

初始化階段

  1. 確定染色體的形式。先選擇一種方式對x進行編碼，使其從實際的解空間(phenotype space)被映射到編碼空間(genotype space),也就是把實數x變成一條染色體。在這道題中我沿用了@sjyan的編碼方式，即把解空間劃分為2^{17}-1等份，然後通過一個17個bit的染色體來表達解空間的實數值。

  2. 確定好染色體形式之後，我們便可以拿它生成一個初始的種群。

進化迭代階段

接下來會進行不停地進化迭代，每次迭代主要由三個階段組成：選擇、交叉、變異。

  1. 選擇階段。選擇階段經歷了適應性選擇和隨機選擇。在適應性選擇中，我們通過適應性函數(fitness function)對種群中的每一條染色體進行適應性評估，按評估結果對染色體進行排序。篩選出適應性最好的一定數量（可以通過參數調節）的染色體，作為下一代的父母加入存貨列表。而在隨機選擇中，我們會隨機挑選一些沒有通過適應性選擇的個體也加入存活列表，這樣做是為了使得一些擁有潛在價值基因但適應性很差的個體得以生存下來。

  2. 交叉階段。每一代染色體的數量是一定的，我們淘汰了一部分染色體，就要生成新的染色體來補足空缺。從上一代中，我們保留了一部分存活的染色體，它們之間將會進行交叉。交叉是指隨機從存活列表中抽取兩個染色體，將這兩條染色體進行融合從而生成新的染色體（就是取一部分父染色體的基因，再在母染色體取在父染色體沒有取到的基因，把這些基因合成一條新的染色體），把新的染色體加入種群中。交叉操作會一直持續，直到種群數量跟之前的種群數量相同。

  3. 變異階段。對於種群中的每一條染色體，使其一定幾率地發生隨機變異（在這個例子下就是反轉染色體上某一個bit的值）。

驗收階段

經過很多代的進化之後，種群裡面的染色體基本上符合最優化的要求了。這時就可以去對裡面的染色體進行解碼(decode)，將其轉化為實際的解。

python實現

代碼寫的挺渣的，不過標了很多注釋。

#encoding=utf-8

import math
import random
import operator

class GA():
def __init__(self, length, count):
# 染色體長度
self.length = length
# 種群中的染色體數量
self.count = count
# 隨機生成初始種群
self.population = self.gen_population(length, count)

def evolve(self, retain_rate=0.2, random_select_rate=0.5, mutation_rate=0.01):
"""
進化
對當前一代種群依次進行選擇、交叉並生成新一代種群，然後對新一代種群進行變異
"""
parents = self.selection(retain_rate, random_select_rate)
self.crossover(parents)
self.mutation(mutation_rate)

def gen_chromosome(self, length):
"""
隨機生成長度為length的染色體，每個基因的取值是0或1
這裡用一個bit表示一個基因
"""
chromosome = 0
for i in xrange(length):
chromosome |= (1 &<&< i) * random.randint(0, 1) return chromosome def gen_population(self, length, count): """ 獲取初始種群（一個含有count個長度為length的染色體的列表） """ return [self.gen_chromosome(length) for i in xrange(count)] def fitness(self, chromosome): """ 計算適應度，將染色體解碼為0~9之間數字，代入函數計算 因為是求最大值，所以數值越大，適應度越高 """ x = self.decode(chromosome) return x + 10*math.sin(5*x) + 7*math.cos(4*x) def selection(self, retain_rate, random_select_rate): """ 選擇 先對適應度從大到小排序，選出存活的染色體 再進行隨機選擇，選出適應度雖然小，但是倖存下來的個體 """ # 對適應度從大到小進行排序 graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population] graded = [x[1] for x in sorted(graded, reverse=True)] # 選出適應性強的染色體 retain_length = int(len(graded) * retain_rate) parents = graded[:retain_length] # 選出適應性不強，但是倖存的染色體 for chromosome in graded[retain_length:]: if random.random() &< random_select_rate: parents.append(chromosome) return parents def crossover(self, parents): """ 染色體的交叉、繁殖，生成新一代的種群 """ # 新出生的孩子，最終會被加入存活下來的父母之中，形成新一代的種群。 children = [] # 需要繁殖的孩子的量 target_count = len(self.population) - len(parents) # 開始根據需要的量進行繁殖 while len(children) &< target_count: male = random.randint(0, len(parents)-1) female = random.randint(0, len(parents)-1) if male != female: # 隨機選取交叉點 cross_pos = random.randint(0, self.length) # 生成掩碼，方便位操作 mask = 0 for i in xrange(cross_pos): mask |= (1 &<&< i) male = parents[male] female = parents[female] # 孩子將獲得父親在交叉點前的基因和母親在交叉點後（包括交叉點）的基因 child = ((male mask) | (female ~mask)) ((1 &<&< self.length) - 1) children.append(child) # 經過繁殖後，孩子和父母的數量與原始種群數量相等，在這裡可以更新種群。 self.population = parents + children def mutation(self, rate): """ 變異 對種群中的所有個體，隨機改變某個個體中的某個基因 """ for i in xrange(len(self.population)): if random.random() &< rate: j = random.randint(0, self.length-1) self.population[i] ^= 1 &<&< j def decode(self, chromosome): """ 解碼染色體，將二進位轉化為屬於[0, 9]的實數 """ return chromosome * 9.0 / (2**self.length-1) def result(self): """ 獲得當前代的最優值，這裡取的是函數取最大值時x的值。 """ graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population] graded = [x[1] for x in sorted(graded, reverse=True)] return ga.decode(graded[0]) if __name__ == "__main__": # 染色體長度為17， 種群數量為300 ga = GA(17, 300) # 200次進化迭代 for x in xrange(200): ga.evolve() print ga.result()

簡陋的）運行結果，很接近

總結
遺傳演算法可以產出一組相對較優的解，而且不需要根據具體問題去進行過多的邏輯推演，速度也相對較快。缺點就是不能保證解是最優的。

http://alteredqualia.com/visualization/evolve/

我來補一個js實現，第一名也就是彈彈彈球已經說的很好了。

樓主可以簡單看一下代碼

可以看看《複雜》一書，裡面有關於遺傳演算法的介紹。

就是玄學。

樓上說了很多了，只舉個沒提到的例子。感覺這個例子更容易懂。

大學時搞過一個機器學習機器人，用的就是神經網路+遺傳演算法。

假設你要做一個機器人，目的是自動盯緊另一個亂串的機器人並想辦法抓住他。你的輸入是各種感測器讀數，你的輸出是輪子馬達的轉速（左右可以速率不同實現轉向）。

設計一個簡單的神經網路（圖片來自網路），

但是權值是什麼才能達到目的呢？需要training。我們就用遺傳演算法。

你可以開始random一組權值，測試一下能不能抓到？然後再random一組權值，測試一下能不能抓到？即使抓不到，是不是離對方很近？（就是樓上提到的fitness function評估）。

把評估結果好的留下，不好的扔掉，然後交叉繁殖。即一部分權值取爸爸的，另一部分權值取媽媽的，看看小孩結果怎樣？

最後，還要有變異，因為不變異，只靠random一些解來進行交叉繁殖，是很容易近親繁殖只找到次優解。變異就是某些權值（隨機一下）突然變了，不再繼承爸爸媽媽了。

經過若干輪的遺傳+變異之後呢，你確實可以看到機器人在不同地形會演化出各種策略抓捕哦，例如繞圈從旁邊繞到前面抓捕，等等。

補充幾個關於遺傳演算法的說明：

  • 現實問題轉換到遺傳演算法是一個難點，也就是現實問題的解如何映射到遺傳演算法的個體上，完成了這一步，後面的三個運算元操作就按部就班了（也要根據實際問題做調整）。
  • 將現實問題的解映射到遺傳演算法中的個體之後，接下來就要確定一個評估函數（也叫適應度函數），這個評估函數能夠定量地評估某個個體的好壞，從而指導整個進化過程朝著使群體適應度增加的方向進化，這樣一來，最終的群體中才會有較優解。
  • 遺傳演算法中最重要的就是幾個運算元，包括選擇運算元，交叉運算元，變異運算元，每一種運算元在解決問題的時候都需要根據實際情況仔細考究，比如交叉運算元是單點還是雙點，交叉點怎麼確定？選擇運算元中是輪盤賭選擇還是錦標賽選擇？這些運算元是遺傳演算法最重要的地方。而前面所說的適應度函數也在這裡使用，怎麼使用呢，簡單地說，就是適應度大的個體更有機會把基因遺傳給下一代，注意，這裡說的是更有機會，也就是說適應度小的個體基因也有一定機會往下一代遺傳，避免了出現尋優只尋到局部最優的情況（如果適應度小的沒有任何機會，那麼尋優過程就變成了爬坡，爬到一個山頭髮現還有一個更高的山頭，但這個時候已經下不去了，詳細過程看下文吧）。
  • 遺傳演算法中有很多參數，比如說初始種群的數量，交叉概率，變異概率，進化代數等等，這些參數影響演算法的收斂速度和收斂值。
  • 遺傳演算法是一種仿生演算法，類似這樣的演算法還有粒子群和蟻群演算法，這類演算法得益於自然界現象的啟發，而不是像確定性演算法那樣的數學論證。

------------以下是原答案------------


通俗地講，遺傳演算法是一種最優化方法，很多書上介紹說，它是一種「軟」演算法，軟演算法是相對於嚴格，確定，精確的硬演算法而言的，顯然遺傳演算法這種模擬自然界進化行為的計算屬於「軟」計算，扯遠了，既然遺傳演算法是一種求解最優化問題的方法，那麼本質上，它是一種尋優演算法，下面講一個例子，來說明它的尋優過程。


這個例子來自《複雜》這本書，書中講了一個大概，我用C語言實現了一遍這個例子，加上了我自己的理解，可能更好懂些。


我現在有一個叫做羅比的機器人，它的世界是二維的，你可以把它的世界想像成一個M乘以N的網格，它的世界裡到處是廢易拉罐，這些廢易拉罐的分布完全是隨機的，我現在要為它尋求一個策略，讓它去清掃這些易拉罐，而且是快速有效地清理。

上圖是羅比世界的示意圖，圖中散亂放著易拉罐，當然，只是示意圖，M和 N 可以隨意指定。我們假設它的世界周圍是高高的牆，每個格子裡面的易拉罐不多於１個，羅比本身並不是很聰明，也看不遠，它只能看到自己當前所在的格子和它周圍的四個格子，顯然，每個格子有三種狀態：空的，有一個易拉罐，牆壁。比如羅比現在看到它的東邊有易拉罐，北邊和西邊是牆，南邊的格子是空的。每次羅比的動作我們規定有以下幾種：

  • 向北移動
  • 向東移動
  • 向南移動
  • 向西移動
  • 隨機移動
  • 不動
  • 收集罐子

為它設計了如下的計分規則：

  • 如果當前格子中有罐子而且清理了，加 10 分。
  • 如果當前格子中沒有罐子卻執行清理的動作，扣 1 分。
  • 如果撞到了牆，扣 5 分，並且彈回原來的格子。

當然，羅比儘可能多撿罐子，不要撞牆，沒罐子的時候別去撿，得到的分數就會越多。顯然，這個問題是一個最優化問題，我們的目標是讓羅比取得最高的分數，問題本身也比較簡單，一個M乘以N的網格，網格中隨機地放上易拉罐，羅比有固定的幾種動作，制定好計分規則，問題是：尋求一個最佳策略，在這個策略下，羅比能夠快速地取得高分。


這個最佳策略就是我們要的最優解，用遺傳演算法解決問題的第一步就是確定進化的個體是什麼，這裡的個體對應於問題的解，正如有的個體好，有的個體差一樣，解也是有好有壞，我們的目的是找到一個最優解，類似於遺傳進化中的優勝劣汰，我們需要的就是遺傳演算法給出的那個最優個體（這裡不嚴謹，其實應該是較優個體，只保證全局較優）。


接下來我們就來確定要進化的個體到底是什麼，這裡的個體對應於問題的某個解，即羅比的一個策略，在這裡，定義羅比的策略是
K-V 形式的映射關係，其中的鍵是羅比當前的情況，值是羅比應該執行的動作。簡單點說，就是什麼情況下應該做什麼動作（動作是有限的，只有七種）。


我們把每個格子的三種狀態映射到整數（每個格子只有三種狀態）:

  • 空 --&> 0
  • 有罐子 --&> 1
  • 牆壁 --&> 2

把羅比可以執行的動作也映射到整數:

  • 向北移動 --&> 0
  • 向東移動 --&> 1
  • 向南移動 --&> 2
  • 向西移動 --&> 3
  • 隨機移動 --&> 4
  • 不動 --&> 5
  • 收集罐子 --&> 6

給定順序：[北，東，南，西，中]，那麼羅比在最開始那副圖中的「情況」就是 [ 2 , 1 , 0 , 2 , 0 ] ,這個「情況」對應於前面說的那個「K」，很顯然，現在它應該向東移動，那麼這個鍵對應的值就是 1（V），（好的策略是這樣，壞的策略可能面對這樣的情況偏偏要羅比撞牆）。


我們得對「情況」，也就是K進行數值化，對該情況下採取的"動作"（V）也得數值化，這樣才能計算。


先考慮羅比所處的「情況」都有哪些，包括羅比自己當前的格子，共有五個方向，每個方向又有三種可能的狀態，那麼，情況一共就有 3×3×3×3×3＝243 種（當然一些情況是不可能的，比如羅比當前的位置是牆，不過程序員都很懶，不想費勁找出所有不可能的情況，我們只要知道就行了）。


那麼一個策略就是 243 個鍵值對，這個 鍵值表(策略表) 就是我們的策略，應該說是羅比的策略，每次羅比只要抬頭四周望望（確定自身所處情況），然後根據自己當前的情況到策略表中找對應的動作（根據K查找鍵值表中的V），然後執行對應的動作（V），然後再抬頭望望，判斷一下自身情況，從策略表中找到對應的動作，然後執行，下一次再這樣，它就可以根據這個策略來進行遊走了。顯然，好的策略表讓它有高分，壞的策略表只會讓它亂走，撞得頭破血流，還撿不著罐子。


我們還可以把鍵的順序按照一定的原則固定下來，那麼只要有一個值的列表就可以了（鍵的位置即是索引），羅比會知道當前的情況是情況幾（確定索引），然後直接查對應的值去執行動作就行，這樣一來，羅比的策略就是
一個有243個元素的一維數組，比如說下面的這個是它的一個策略:


[2,5,0,4,2,1,3,2,4,1,2,3,2,4,1,2,3,2,1,2,1,2,1,2,1,2,4,2,2,2,4,…,3,5,6,0]


可是這樣的策略有多少種呢？一共有 7^{243} 種（243個元素，每個元素都有7種可能的取值），是個很大的數字，這也說明了我們的解空間是很大的，注意，這麼多策略中可能
90% 以上都是糟糕的策略，比如說羅比現在的北邊是牆壁，某一個策略讓它向北移動，那好，它一頭撞在牆上，所以我們的目的是為羅比找出最優的策略，讓它的得分儘可能地多。


如何在這麼多解中找到一個較優解，是遺傳演算法要做的事情。


下面來介紹一下大致思路，其實為羅比尋找最佳策略的過程就是一個進化的過程，你可以想像有一個種群，這個種群中有若干個個體，每個個體代表一個策略，其實前面我們說每個策略表示為一個長度為
243 的數組，這個就是編碼的過程，一個這樣的數組就是一個個體。不同的問題有不同的編碼方式，比較多的是二進位編碼，不過我們這裡更加適合字元串編碼方式，編碼完成之後，
我們讓這個種群按照適者生存，物競天擇的原則進行進化，最後進化到一定的代數之後，剩下來的就是那些比較優秀的個體，也就是那些比較好的策略，從最後一代中選出一個最好的個體，OK ,這個就是我們為羅比找到的好策略。


主函數中關鍵的就三行，選擇，重組，變異

void main()
{
//隨機生成解
int solu[POP_SIZE][SOLU_DIM];
init_solu(solu);

int i;
double fit[POP_SIZE];

//最初的解
get_fitness(solu,fit);
printf("當前的最高分數為:%f ",max(fit,POP_SIZE));

printf("
計算中........
");

//進化
for(i = 0; i &< GEN_NUM;i++) { ga_sel(solu); //選擇 ga_cross(solu); //交叉重組 ga_mut(solu); //變異 } //進化完畢，輸出最終的解 get_fitness(solu,fit); printf("最終的最高分數為:%f ",max(fit,POP_SIZE)); printf(" "); }

這裡面有幾個關鍵的地方：

  1. 每個個體怎麼表示？
  2. 如何度量一個個體的優劣程度？
  3. 種群如何不斷選擇，重組，變異?

問題一：個體和種群的表示

對於第一個問題，其實對應於遺傳演算法中的編碼過程，也就是將現實問題的解對應到程序中的具體表示，上文中說道我們可以把羅比所能碰到的所有情形和該情形下執行的動作當成一個鍵值表，那麼在這裡，問題的一個解就是一張鍵值表，而這個鍵值表在程序中我們可以很方便的表示，為了更方便一些，我們把鍵出現的順序固定下來，那麼只要用一個長度為243的一維數組就可以表示了，索引表示情形(可以把每種情形映射到一個0到242的整數，下文會講到)，數組的值表示該情形下羅比該執行的動作(前文中已經編號，0到6)，於是我們就可以用一個一維數組表示一個解，也就是一個策略，即一個個體，假定種群包含200個個體（200個策略，即200張鍵值表），我們設定種群的大小為 200 ，那麼這個種群就可以用一個 200×243 的矩陣來表示，就像下面這樣：

其中，每一行表示一個個體，這個矩陣表示的是一個有 200 個個體的種群。


下面說一下某一種情形如何映射到一個0~242的整數。


羅比所面對的某一種情形類似下面的形式：

  • 北 –&> 牆壁(2)
  • 東 –&> 易拉罐(1)
  • 南 –&> 空(0)
  • 西 –&> 牆壁(2)
  • 中 –&> 空(0)

第一列是方位，第二列是此處的狀態，這種情形對應的表示就是21020，我們可以把這個數字當做三進位的數，因為每一位都有三種取值，這種情形對應的十進位值就是:


2 imes3{^4} + 1 imes3{^3} + 0 imes3{^2} + 2 imes3{^1} + 0 imes3{^0} = 195

按照這種編碼方式，第1種情形到第243種情形都可以用一個0到242之間的整數表示，而且順序是唯一的，那麼具體情形到整數之間的映射就完成了，我們可以用這個整數值作為數組的索引，而羅比也可以根據自己面對的情形知道其所對應的編號，立刻得到對應索引位處的整數，即動作編號，然後執行相應的動作。


下面代碼用來生成一個初始種群：

/**生成初始解**/
void init_solu(int solu[][SOLU_DIM])
{
int i,j;
for(i = 0;i &< POP_SIZE;i++) for(j = 0;j &< SOLU_DIM;j++) solu[i][j] = m_round(rand_zo()*6); }

順便說下羅比的模擬世界，我們用一個二維數組生成羅比的網格世界，然後為它建好牆壁，撒上易拉罐。


void init_world(int world[][COL],double p)
{
int i,j;

//初始每個格子為空，用０表示
for(i = 0;i &< ROW;i++) for(j = 0;j &< COL;j++) world[i][j] = 0; //放置牆壁,2代表牆壁 for(i = 0;i &< ROW;i++) { world[0][i] = 2; world[i][0] = 2; world[ROW-1][i] = 2; world[i][COL-1] = 2; } //放置易拉罐 for(i = 1;i &< ROW - 1;i++) for(j = 1;j &< COL - 1;j++) if(rand_zo()&

該函數接收一個二維數組和概率 p ,以這個概率在羅比的世界裡放置易拉罐。


問題二：度量個體的優劣程度 對於每一個個體(策略)，我們讓羅比採用這個策略去清理 100 次，在每次清理過程中執行200次動作，每次清理都有一個得分，取這
100 次的平均成績作為它的最終得分，注意，100 次清理，每次清理的世界都不同(每次隨機放置易拉罐) , 這樣，我們就大致衡量出了每個個體的好壞。


在代碼中，這個評價函數接受一個種群，也就是
200 個個體，然後返回一個長度為 200的得分數組，裡面的元素對應每一個個體的分數，也叫做它的適應度，為了使適應度都為正值(因為後面要求和算比率), 我給每個個體的最終得分加上了最低得分的相反數，那麼每個個體的得分區間就是
[0,2000]。


/**適應度**/
void get_fitness(int solu[][SOLU_DIM],double fitness[])
{
int i,j;

int ST[SOLU_DIM]; //每個個體對應一張策略表

for(i = 0; i &< POP_SIZE;i++) { for(j = 0;j &< SOLU_DIM;j++) ST[j] = solu[i][j]; double per_sum = 0; /*對於每一個個體，給它CL_TIMES機會打掃,取平均成績做為它的適應度分數,每一次的世界都不同，但是策略表相同*/ for(j = 0;j &< CL_TIMES;j++) { int wor[ROW][COL]; init_world(wor,P); per_sum += do_clean(wor,ST); } //保證適應度是正數 fitness[i] = per_sum/CL_TIMES + 5*PER_DO_TIMES; } }

這段代碼中用到了一個函數do_clean()，這個函數用來模擬羅比清理的過程，它接收一個髒亂的世界和一個清掃策略，然後羅比按照這個清掃策略執行動作200次，返回這一次清掃過程的得分，下面是具體過程：


/**根據策略表ST,執行清掃動作,返回對應的分數**/
double do_clean(int wor[][COL],int ST[])
{
//約定：可以執行的動作有：
// 向北移動　０
// 向東移動　１
// 向南移動　２
// 向西移動　３
// 隨機移動　４
// 　不動　　５
// 清理罐子　６
//計分規則：
// 如果羅比所在的格子中有罐子，並且打掃了罐子，+10分
// 如果執行打掃的動作而當前格子中沒有罐子, -1分
// 如果撞到了牆，-5分，並且彈回原來的格子

//從左上角開始打掃
int pos[2] = {1,1};
double sc = 0;
int i;

for(i = 0; i &< PER_DO_TIMES;i++) { // 得到當前位置的情況 int situ[5]; situ[0] = wor[pos[0] - 1][pos[1]]; situ[1] = wor[pos[0]][pos[1] + 1]; situ[2] = wor[pos[0] + 1][pos[1]]; situ[3] = wor[pos[0]][pos[1] - 1]; situ[4] = wor[pos[0]][pos[1]]; // 得到此情況下的策略編號 int str_num = get_stra(situ); // 按照此策略進行行動，並對wor和sc進行對應更新 int dire; int rand_num; switch(ST[str_num]) { case 0: //向北移動 N: if(move(pos[0],pos[1],0)) sc -= 5; else pos[0]--; break; case 1: //向東移動 E: if(move(pos[0],pos[1],1)) sc -= 5; else pos[1]++; break; case 2: //向南移動 S: if(move(pos[0],pos[1],2)) sc -= 5; else pos[0]++; break; case 3: //向西移動 W: if(move(pos[0],pos[1],3)) sc -= 5; else pos[1]--; break; case 4: //隨機移動 rand_num = rand_zo(); if(rand_num &< 0.25) goto N; else if(rand_num &< 0.50) goto E; else if(rand_num &< 0.75) goto S; else goto W; break; case 5: //不動 break; case 6: //清理罐子 if(wor[pos[0]][pos[1]] == 1) sc += 10; else sc -= 1; break; } } return sc; }

問題三：進化過程

現在到了最有趣的地方，就是種群如何進行選擇,重組,變異，我們一個一個來說。


選擇

選擇，顧名思義，就是從種群中選擇一批比較優良的個體，讓它進行繁殖，而判斷某個個體是否優良自然就是看這個個體在評估函數下的得分高低，這裡我們使用比較簡單的輪盤賭的方式來選擇個體，想像有下面這個輪盤：

每個部分的面積不同，如果有一根指針，你旋轉這個輪盤，當然指針落在面積大的那一塊上的概率會大些，注意，這裡是
概率，具有更高適應度的個體僅僅是有比較大的概率被選中，這就保證了演算法具有一定的隨機性，一定程度上避免落入局部最優解，因為那些適應度不高的個體也有機會被選中，而你不能說這些適應度不高的個體就沒有好的基因片段遺傳給下一代，但是從總體上來講，適應度高的個體更多的機會把自己的基因遺傳給下一代。在代碼中，我們先計算出每個個體的被選概率，概率之和是1,然後計算累計概率，進行選擇，關於為什麼計算累計概率，這僅僅是種實現上的技巧，只要能夠按照輪盤賭的原則進行選擇就可以了，選擇的結果是一個新的種群，新的種群的大小和原來的種群大小是相同的，但是已經發生了變化，因為一些適應度高的個體可能被多次選中，有一些適應度很低的個體可能一次都沒有被選中，也就是被淘汰了，下面是選擇的具體過程：


//選擇運算元
void ga_sel(int old_pop[][SOLU_DIM])
{
int new_pop[POP_SIZE][SOLU_DIM];
double pr[POP_SIZE],cum_pr[POP_SIZE];
double pr_sum = 0;
int i,j,k;

//計算每個個體的適應度
get_fitness(old_pop,pr);

//計算累計概率
for(i = 0;i &< POP_SIZE;i++) pr_sum += pr[i]; for(i = 0;i &< POP_SIZE;i++) pr[i] = pr[i]/pr_sum; cum_pr[0] = pr[0]; for(i = 1;i &< POP_SIZE;i++) cum_pr[i] = cum_pr[i - 1] + pr[i]; //輪盤賭方法選擇 for(i = 0;i &< POP_SIZE;i++) { double rand_n = rand_zo(); for(j = 0; j &< POP_SIZE - 1;j++) { if(rand_n &< cum_pr[0]) { for(k = 0;k &< SOLU_DIM;k++) new_pop[i][k] = old_pop[0][k]; break; }else if(rand_n &>= cum_pr[j] rand_n &<= cum_pr[j+1]) { for(k = 0;k &< SOLU_DIM;k++) new_pop[i][k] = old_pop[j+1][k]; break; } } } for(i = 0;i &< POP_SIZE;i++) for(j = 0;j &< SOLU_DIM;j++) old_pop[i][j] = new_pop[i][j]; }

重組(交叉)

現在我們進入基因重組這個步驟，基因重組的概念不用多說，我們把上一步驟中選擇出來的個體，以一定的概率P_CROSS進行基因重組，提一句，這個程序的有很多參數，比如說種群大小，度量適應度時羅比清理的次數，每次清理中執行的動作次數，基因重組的概率，基因變異的概率，進化的代數，網格世界的大小，這些參數是可以適當調節的，對演算法的收斂速度和收斂值會有影響。回到正題，在選擇出一批個體之後（這些個體有向下一代傳遞基因的權利），讓他們兩兩之間進行交叉（啪啪啪），啪啪啪的結果當然就是產生了新的個體。交叉運算元的具體操作有很多種，這裡我們還是選擇比較簡單的單點交叉，如圖所示

圖中是以二進位來編碼的，採用單點交叉，它很好地說明了單點交叉的過程。
下面是代碼中的交叉過程


//交叉
void ga_cross(int new_pop[][SOLU_DIM])
{
//選擇需要交叉的個體
int count = 0;
int need_cr[POP_SIZE];
int i,j;
int temp[SOLU_DIM];

for(i = 0;i &< POP_SIZE;i++) if(rand_zo() &< P_CROSS) { need_cr[count] = i; count++; } if(count % 2 != 0) count++; //隨機決定一個不為0的交叉點 int cr_point = 0; while(cr_point == 0) cr_point = m_round(rand_zo()*SOLU_DIM); //進行交叉 for(i = 0;i &< count;i+=2 ) for(j = cr_point;j &< SOLU_DIM;j++) { temp[j] = new_pop[need_cr[i]][j]; new_pop[need_cr[i]][j] = new_pop[need_cr[i+1]][j]; new_pop[need_cr[i+1]][j] = temp[j]; } }

變異

正如自然界中的個體一樣，我們的進化過程也要考慮到變異的情況，與前面兩個過程不同的是，變異針對的是某個基因，比如說我們的種群大小是200，每個個體有243個基因，那麼這個種群的基因總數就是200×243，每一個基因都有變異的可能性，當然這個可能性通常來說是比較小的（就像自然界中的變異也不常發生一樣），在這裡我們給定每個基因變異的概率是0.005，下面是變異的具體過程


/***變異**/
void ga_mut(int pop[][SOLU_DIM])
{
int ge_sum = POP_SIZE*SOLU_DIM;
int i,j,k;
for(i = 0; i &< ge_sum;i++) { if(rand_zo() &< P_MUT) { //定位此基因所在的染色體,此處，染色體即個體，下同 int chr_loc; chr_loc = i/SOLU_DIM; //定位此基因所在染色體上的基因位 int gen_loc; gen_loc = i%SOLU_DIM; //進行變異 pop[chr_loc][gen_loc] = m_round(rand_zo()*6); } } }

至此，種群完成了第一次進化，選擇，交叉，變異，我們設定讓此種群進化1000代，最終倖存下來的個體就是我們所要找的好策略。


C語言運行的結果說一下，如果這個網格的大小是30×30，其中易拉罐的比例設在0.5,每次讓羅比行動200步，那麼，這個遊戲的滿分就是2000分，我自己事先按照我覺得比較好的策略給羅比用，就是向有罐子的地方移動，有罐子就撿起來，不要撞牆，羅比按照這個策略清理1000次，每次罐子的分布都隨機，平均得分是1210分，遺傳演算法進化出來的策略平均得分是1992分，完整代碼需要的話請留言，可以運行試一試。

來來來，我來舉個實際的用法。
我爸老宅那邊有個四戶緊鄰的人家。
A家，B家，C家，D家
A家是這樣的：兩個父母輩的人該吃吃該花花該用用，存款一點點，反正等動遷，也不急買房
B家是這樣的：我媽運氣不好養了個男娃，只好扣扣索索存錢，買了一套婚房以後，日子過舒坦了
C家是這樣的：她們家一門心思就是買房子，買了20年。
D家是這樣的：她們本來學著C買房，然後突然有一天腦抽了異想天開去買股票了

結果你也知道了。
A家的男娃三十好幾了，還是沒媳婦，因為動遷政策爛，鄉下地方拿了一套房，根本找不到媳婦
B家因為買了一套房，一切走上正軌，普普通通。
C家發財了。
D家本來發財了，後來突然虧得媽都不認識

然後從小到大，四家人的娃就同時看著三個家庭走向不同階層。
深刻明白一個道理：
有些人只會做愚蠢的決定，這些人會被時代淘汰。
有些人會因為運氣做一個聰明的決定，他們的後代會不會被淘汰，得看他們後代是否能做聰明決定
有些人只會做聰明的決定，這些人後代只會越來越富足

然後，你覺得，A家B家C家D家選一個策略作為你將來的戰略，
你選誰？

選A那叫破釜沉舟堵上人生
選B家那叫觀望待定猶豫不決
選C家那就叫遺傳演算法
選D家那個叫隨緣

其中，D家就是使用遺傳演算法的時候，變異那一步做得不好的例子。

一句話來說：
已經成功的群體，使用正確策略的幾率遠遠大於已經失敗的群體。

假設z = x^2 + y^2,其中x,y分別取[-50，50]內的整數。我們如何求得當z最小時對應的x,y呢？
對，大眼一瞅肯定是點(0，0)，但如果我們要每個坐標點帶進去計算，然後比較，然後求出最優點呢。這就意味需要計算101*101個點。這計算量太大了，我們並不想把所有的點帶進去計算，我們想讓機器學習去尋找，就用遺傳演算法。
第一步，我們先在[-50，50]裡面隨機選出10個數，然後再把這10個數兩兩組合，就是10*10=100個點，我們假設這100個點就是100個人，一個人一共有兩條DNA，一條記錄x的值，一條記錄y的值。
第二步，計算這100個點對應的 z值，然後排序，把z值越小的排到前面
第三步，給第一名發100張號碼牌，說，等會我叫1到100時，你記得出來；
給第二名發99張號碼牌，說，等會我叫101到199時，你記得出來;
...
以此類推，給第一百名發了一張號碼牌，牌號是5050。
第四步，找配偶了，假設我們有一個抽獎箱，裡面有5050張號碼牌，我們隨手摸一個出來，喊號碼，爸爸出來了，再從箱子里摸一個，媽媽出來了。
第五步，生孩子，爸爸媽媽結合，一共生出來四個寶寶，兩個是跟爸爸媽媽對應的x,y相同，兩個是繼承了爸爸的x媽媽的y和媽媽的x和爸爸的y。(這裡暫時不講變異，下面說。)
我們一共抽25次，就又有了100個點。又可以進行第二步，第三步，第四步，第五步。
那麼問題來了，啥時候結束呢？說個簡單的方法，我們把每次100個z值中的前10個z值加起來，你就會發現這個和會越來越小，每次和與上一次和的差值也在減小。我們規定，等這個和的差值小於20時我們停止計算，那麼第一個z值對應的x,y就是最優解。這就是遺傳演算法的大概思想了。
下面扯一下變異，父母在生寶寶時基因會變異，我們就在第五步後面加上第六步。四個寶寶一共8個基因，對每一個基因我們都擲一次篩子，要是出現1~4就基因不變，要是出現5就在原來的數上減1，如果數是-50不減。要是出現6就在原來的數上加1，如果數是50不加。
上面是通俗介紹遺傳演算法的思想，所以會不嚴謹，希望能幫有緣人入個門。

這是我碩士研究的內容啊哈哈哈。
想不多畢業兩年了還能用派上用場！！

遺傳演算法開始：需要初始個體種群
遺傳演算法過程：【交叉、變異、保留優良個體、淘汰差的個體】反覆循環。
遺傳演算法結束：種族的多樣性已經很低。

1. 初始種群，這個很好理解（理解成一個村子裡的人）
2. 交叉，也就是兩個個體之間部分基因交換，看看能否生成更好的個體（理解成村裡的高富帥與白富美的結合，生下的娃很大概率上要比隔壁村老王家的好）。
3. 變異，主要是為了給整個種群帶來新的基因，來看看這個新的基因是否可以促進種群進一步優化，同時也避免種群進入局部最優解（理解成，這村裡白富美偏愛隔壁村老王這個矮矬窮，而老王祖上血液里竟有洪荒之力，最後種入了白富美體內，嗯嗯...）
4. 種群多樣性，種族內基因片段的差異性。隨著遺傳演算法的進行，這個種族的基因差異必然會趨於一致，這時候不管如何交叉編譯也都無法有更好的結果，此時演算法應該停止了（這就是為什麼要避免一個村子裡近親結婚啊！！有事沒事去隔壁村轉轉啊）

上述幾個過程持續了一段時間後，所剩下的個體基本上從基因差異性角度來看也就差不多了。這個時候，再繼續下去也就沒有意義了。

整個過程中，最重要的2點有：
1. 適應度方程，也就是如何決定一個個體是好還是壞。
2. 交叉，變異的ratio取值選擇，這個其實沒有標準值，只有經驗數值。


附：種族多樣性差異隨著遺傳演算法進行下去的變化趨勢

四個字，優勝劣汰，最後說句，MATLAB真棒。

通俗的來講，遺傳演算法的目的是產生某個期望的東西。或者說搜索某個東西。

它是一種搜索演算法。


這個東西的特點是：

你能夠判斷它是不是你期望的，例如：

最大值：如何通俗易懂地解釋遺傳演算法？有什麼例子？ - 知乎

你的女神：如何通俗易懂地解釋遺傳演算法？有什麼例子？ - 知乎

是不是firefox的圖標：科學松鼠會 amp;amp;amp;quot; 遺傳演算法：內存中的進化。


但你不知道怎麼創造他：

給你一本字典你沒法寫一首詩，給你一堆三角形你沒法拼出一個達爾文。


總結來講，有以下特點

  • 有限的構成元素（基因）
  • 無窮大的構成可能（大到無法逐個判斷）

遺傳演算法就是在一大堆可能性中，尋找一條較短的路線來達到目標（最優or次優解）

下圖所示，基因只有兩個，x和y，

基因的表現是一個函數 f（x，y），

如果我想知道在x，y下的結果是不是我想要的，需要函數J=f（x，y）-E；

當J=0的時候，這個xy的組合就是最優解

我們用電腦算這個最優解的時候，需要把所有的xy和對應f都求出來。當基因數量太多的時候，那就算不完了。

所以才引入遺傳演算法，來抄近路，找到這個最優解

不需要遍歷所有可能，使用既定目標的篩選（fitness fucntion）來快速接近最優目標

這就是遺傳演算法。


舉例，給你一本詞典，寫一首古詩。


population：起始詩：

啊啊啊啊啊

啊啊啊啊啊

啊啊啊啊啊

啊啊啊啊啊


啵啵啵啵啵

啵啵啵啵啵

啵啵啵啵啵

啵啵啵啵啵


判斷：都不好


Generation：第一代：

1.1 單點交叉遺傳

啊啊啊啊啊

啊啊啊啊啊

啵啵啵啵啵

啵啵啵啵啵

1.2 均勻交叉遺傳

啊啵啊啵啊

啊啵啊啵啊

啊啵啊啵啊

啊啵啊啵啊

1.3 雙點交叉遺傳

啵啵啵啵啵

啊啊啊啊啊

啵啵啵啵啵

啵啵啵啵啵

1.4 變異

鵝鵝鵝鵝鵝

啊啊啊啊啊

啵啵啵啵啵

波波波波波

。

。

。

。

。


然後繼續n代，

大家說能不能遺傳出這麼一首詩呢：

鵝鵝鵝鵝鵝

曲項向天歌

白毛浮綠水

紅掌撥清波


我看行，但有個問題就是，怎麼做一個fitness function 來判斷出來的這首詩吼不吼。


這我就不知道了，大家仁者見智吧。

課後題：

既然遺傳演算法是一種搜索演算法，那麼請問：用遺傳演算法找最大值和用冒泡排序找最大值，有什麼區別？

遺傳演算法：
我子子孫孫那麼多（NP），總有一個長得又帥，又高，又聰明的（最優解），再不濟，也有一個差不多的（次優解）。

研究生期間就是研究遺傳演算法的，遺傳演算法就是一種枚舉演算法，首先選定解的可能空間，將這些解編碼，形成個體，組成種群，再選定適應度函數（判斷個體優劣的標準）對個體進行選擇，剔除適應度低的個體，再者進行遺傳操作（選擇，交叉，變異），也就是豐富解的多樣性，使個體按適應度大的方向發展，如此循環下去，直到個體的適應度值最大，通過解碼即為問題的解。補充一個例子，以前看文獻看到的，有一群生活在山下的袋鼠，因為生活所迫，必須要跳到更高的山頂去，因為那裡有豐富的食物，這裡每個袋鼠為一個個體，這群袋鼠為一個種群，山頂這個目標為問題的解，當然這群袋鼠有很多屬性，比如毛色，體型等，但這些都和跳到山頂沒關係，跳的高這個屬性直接影響到山頂這個目標，適應度函數就為跳得高這個屬性。我們不用探討如何尋找最捷徑的路線，只需在山一定的高度的地方，殺死跳的不高的袋鼠（雖然有些殘忍），這樣跳得高的袋鼠就容易存活，它們就有機會產生後代（遺傳操作），再在更高的地方殺死一批跳的不高的，如此這樣下去（迭代循環），跳的最高的會存活，而它會最終到達山頂，也即找到問題的解。。。。解答完畢。

下面是我大?某課程的結課論文，主要是從元啟發式搜索產生的淵源和作用的理論上講的。遺傳演算法是其中很基礎的一種，

它是一種極其重要的思想在演算法中的體現，那就是自然選擇：物競天擇，優勝劣汰。

我們把生物的生存能力看成目標函數，同時，很自然地，生存自然會受到一些限制，可以將它們設為一個個的限制函數，這些函數的變數應當是人的遺傳物質及其結構，即染色體和基因的序列。

我們不妨簡單地將函數的變數視為一個基因的序列，即基因型。

那麼，每個基因型對應的個體，在經歷了生存鬥爭之後，受到自然選擇的作用向著適合環境的優勢基因型進化。這種生存鬥爭包括種內鬥爭，種間鬥爭，與無機環境之間的鬥爭，其中，種內鬥爭可以類比於演算法中根據不同解的質量（對目標函數的滿足情況等）而進行的取捨過程；而與無機環境之間的鬥爭，則可以看成是演算法中根據不同解對於限制條件的滿足情況進行的取捨過程。兩者結合，將會發揮出巨大的功效。種間鬥爭則可以用來刻畫對滿足限制函數的不同結構的解的取捨過程。

19世紀中葉達爾文提出了自然選擇學說，在其後的一百多年內，隨著相應科學領域的進步，自然選擇學說逐漸被完善。而現代進化學說中，例如基因、可遺傳的變異這些概念，與問題解的優化過程具有一定的相似性。

而對於複雜度超越多項式時間的優化問題在近代以來，頻頻出現在生產生活中。同時，相應理論的完備與生產力發展的需求，促進了人們對高效且可移植性強的演算法的尋找。

於是，包括遺傳演算法在內的元啟發式搜索演算法應運而生。

上世紀60年代初，John Henry Holland的學生提出了「遺傳演算法」這個名詞，此人其後與其同事對這個事情進行了深入的研究，並在1975年出版了《自然系統和人工系統的自適應》（Adaptation in Natural and Artificial Systems），開啟了遺傳演算法的時代。

遺傳演算法的一個關鍵點在於從當前解產生新解，這個過程，需要包含「遺傳」和「變異」的過程，並且兩者的概率要相適應，這樣才能產生合適的進化。而無論是遺傳還是變異，其實都是對於解的鄰域問題的研究：如何使得新解在依據舊解產生的情況下，產生適當的偏移。

這個問題的解決，需要對解的結構做一些分析，這種分析有時非常簡單，例如背包問題，有時則十分困難，例如本文前面所舉的在有向帶權圖中求最優通路的問題。如果能夠確定一個合適的遺傳、變異機制，一個遺傳演算法就算是基本構建成功。

遺傳演算法的偽程序如下：

由於是原文檔是word堆的，很多符號都複製不過來，自製的偽程序（勿噴，強行自創偽程序，老師也沒說什麼。。。）用截圖發到下邊。

（這種偽代碼是當時只會C++的我使用的。。。語法和C++一樣，但是包含很多單純的數學表示，現在看起來相當的naive，但意思還是很清楚的。。對了，我不會用知乎編輯器編公式，下面一堆ctex代碼急求助！！）

其實說到遺傳演算法，遺傳和變異是其中用到的重要概念，遺傳是指一組新解（新一代個體）是基於舊解（上一代個體）產生的，如果新、舊解之間關聯性不夠，那麼遺傳演算法就變成了簡單的隨機搜索，即 瞎搞搜索。而變異是指舊解到新解過程發生的差異，這種差異的產生是隨機的，其方向和大小也是隨機的，你應當對這些隨機變數設定合適的均值和方差，因為如果變異過於劇烈，導致遺傳關係太不顯著的話，同樣遺傳演算法也成了 瞎搞搜索。

我們主要到優化領域裡的問題一般都是這樣一種形式：


{$ extit{f}_ extit{i}$} ($ extit{m}$)= extsl{true},$ extit{m}$ $in$ $ extit{M}$,$ extit{i}$=1,2,3,...,n;\
Ask for $ extit{m}_{0}$ $in extit{M}$ s.t $ extit{F}$ ($ extit{m}_{0}$)=max(or min);

而遺傳演算法就是把解$ extit{m}$看成一個序列$ extit{i}_1 extit{i}_2$...$ extit{i}_ extit{n}$，這個解或者說序列就像基因一樣，可以根據自然選擇而進化，變得更加適應於環境（滿足限制函數）並且處於生存的優勢（滿足目標函數）。
我們知道一個種群要生存，其種群數量不能太小，遺傳演算法中每一代都有一個「名單」，記著很多個個體（解）。這個事情，其實就是搜索演算法中「廣撒點」的思想——我們知道，讓一個點在空間中尋找目標，其效果不如讓很多點一起找。
遺傳演算法中有一些需要預先設置的參數，比如表示變異的劇烈程度的量化向量值，在自然界中，這個參數應該是大自然自己設置好的（雖然這並不意味著它是一個常量）。當然你也可以把每一代的個體數、每一個淘汰的個體數都當成需要預設的參數，這是根據需要來取定的。
遺傳演算法將解空間用一組基來表示，目標函數、限制函數是在這組基下的一個線性函數（或者線性函數衍生的判斷balabala的）。這是一種通過分析 「基因素」 來 尋找 好的結果的方法。

突發奇想一下，這種漫無目的的交叉是否這的符合自然界的規律，或許對具體的基因進行篩選，更加有目的的交叉，能夠獲得更好的效果。

打個比方，一個瞎子拿著一個固定大小的臉盆，在一個裝滿了，大小不等數量上萬的小球的屋子裡。那麼問題來了_怎麼才能讓他找到最大的球？

瞎子先隨機走一圈，往臉盆裡面裝小球_輸入。裝滿了，歇一會，比較比較臉盆里球的大小，小的扔掉_輸出。然後再走一圈，再歇會比較比較……………………loop，知道他實在走不動了，或感覺滿意了，或瞎子體力好-完成了終極十八摸，找到了最大的。

手機碼字，隨手一答，勿噴，當然了_裡面還有很多細節

推薦閱讀：

※如何看待IMO 2017中國隊團體總分位列第二？
※存不存在表面積與體積都相等的不同幾何體？
※調和級數既然是發散的,那麼就是無窮大量了,它發散的快嗎,什麼級別的,lnn,n,....?
※一元微分理論中，為什麼 d(dy/dx)/dx=d^2y/(dx)^2 ？
※推薦幾本數學建模的書？

TAG:演算法 | 數學 | 遺傳演算法 | 名詞解釋 | 解釋 |