這是個真實的故事。
從前在海岸邊有一群扇貝在悠哉游哉地生活繁衍著。它們自然是衣食不愁，連房子也有了著落。它們擔憂的只有一件事：每隔一段時間，總有一個人來挖走它們之中的一部分。當然啦，挖回去干什么這大家都知道。但扇貝們不知道的是，這人的家族圖騰是Firefox的圖標，所以他總是選擇那些貝殼花紋長得比較不像Firefox圖標的扇貝。
這種狀況持續(xù)了好幾十萬代。大家應該也猜到扇貝們身上發(fā)生什么事情了：它們的貝殼上都印著很像Firefox圖標的圖案。
可能有些讀者會說：你這不是糊弄我們么，F(xiàn)irefox才有多少年歷史，你就搞了個幾十萬代的扇貝？
確有其事，但是這些扇貝不是真實的，它們在我電腦的內(nèi)存里邊生活。它們是一個遺傳算法程序的一部分，這個程序的目的就是用100個半透明三角形把Firefox的圖標盡可能像地畫出來。
什么是遺傳算法呢？
簡單地說，遺傳算法是一種解決問題的方法。它模擬大自然中種群在選擇壓力下的演化，從而得到問題的一個近似解。
在二十世紀五十年代，生物學家已經(jīng)知道基因在自然演化過程中的作用了，而他們也希望能在新出現(xiàn)的計算機上模擬這個過程，用以嘗試定量研究基因與進化之間的關(guān)系。這就是遺傳算法的濫觴。后來，有人將其用于解決優(yōu)化問題，于是就產(chǎn)生了遺傳算法。
那么，具體來說，在計算機里邊是怎么模擬進化過程的呢？
我們還是以開頭提到的程序為例。
首先，我們知道，生物個體長什么樣子很大程度上是由染色體上的基因決定的。同樣，如果我們把100個半透明三角形組成的東西看成一個生物個體的話（為了說話方便，稱為扇貝吧），我們也可以說它的樣子是由這些三角形的具體位置和顏色決定的。所以，我們可以把一個一個的半透明三角形看作是這些扇貝的“基因”。而組成扇貝的這100個基因就組成了每個扇貝個體的“染色體”（chromosome）。
從下面的圖可以大約看出來這些基因是怎么決定扇貝的樣子的（為了觀看方便，我們只畫出其中五個三角形）：
然后，扇貝們除了生活，當然還要繁衍后代。生物界中的繁衍無非就是父母的基因組合產(chǎn)生新的個體，而在這個程序里邊我們當然也這么辦：選擇兩個原有的扇貝，然后從這兩個扇貝的染色體中隨機選取一共100個基因組成新個體的染色體。如圖所示：（仍然是將扇貝看成是五個三角形組成的）
為了產(chǎn)生新的基因，使基因的種類更多樣化，在組合的時候，新的扇貝的基因有一定的概率發(fā)生變異。也就是說，其中的一個透明三角形的位置或者顏色會隨機改變，如圖（仍然是五個三角形……我偷工減料……）：
其次，為了使扇貝的樣子向Firefox圖標靠近，我們要給它們加上一點選擇壓力，就是文章開頭故事中提到的那個人的行動：在每一代把最不像Firefox的扇貝淘汰出去，同時也給新的個體留下生存的空間。怎么評價這個扇貝像不像Firefox呢？最直接的方法就是一個一個像素比較，顏色相差得越多就越不像。這個評價的函數(shù)叫做“適應函數(shù)”，它負責評價一個個體到底有多適應我們的要求。
在淘汰的過程中，為了便于編程，我們通常會在淘汰舊個體和產(chǎn)生新個體的數(shù)目上進行適當?shù)恼{(diào)整，使種群的大小保持不變。淘汰的作用就是使適應我們要求的個體存在的時間更長，從而達到選擇的目的。
最后，在自然界中，種群的演化是一個無休止的過程，但程序總要停下來給出一個結(jié)果。那么，什么時候終止演化輸出結(jié)果呢？這就要訂立一個終止條件，滿足這個條件的話程序就輸出當前最好的結(jié)果并停止。最簡單的終止條件就是，如果種群經(jīng)過了很多代（這里的“很多”是一個需要設(shè)定的參數(shù)）之后仍然沒有顯著改變適應性的變異的話，我們就停止并輸出結(jié)果。我們就用這個終止條件。
好了，現(xiàn)在是萬事俱備只欠東風了。定義好基因，寫好繁衍、變異、評價適應性、淘汰和終止的代碼之后，只需要隨機產(chǎn)生一個適當大小的種群，然后讓它這樣一代代的繁衍、變異和淘汰下去，到最后終止我們就會獲得一個驚喜的結(jié)果：（這回是完整的了，圖片下的數(shù)字表示這個扇貝是第幾代中最好的）
怎么樣？雖說細節(jié)上很欠缺，但是也算是不錯了。要不，你來試試用100個透明三角形畫一個更像的？就是這樣的看上去很簡單的模擬演化過程也能解決一些我們這些有智慧的人類也感到棘手的問題。
實際上，在生活和生產(chǎn)中，很多時候并不需要得到一個完美的答案；而很多問題如果要得到完美的答案的話，需要很大量的計算。所以，因為遺傳算法能在相對較短的時間內(nèi)給出一個足夠好能湊合的答案，它從問世伊始就越來越受到大家的重視，對它的研究也是方興未艾。當然，它也有缺點，比如說早期的優(yōu)勢基因可能會很快通過交換基因的途徑散播到整個種群中，這樣有可能導致早熟（premature），也就是說整個種群的基因過早同一化，得不到足夠好的結(jié)果。這個問題是難以完全避免的。
其實，通過微調(diào)參數(shù)和繁衍、變異、淘汰、終止的代碼，我們有可能得到更有效的算法。遺傳算法只是一個框架，里邊具體內(nèi)容可以根據(jù)實際問題進行調(diào)整，這也是它能在許多問題上派上用場的一個原因。像這樣可以適應很多問題的算法還有模擬退火算法、粒子群算法、蟻群算法、禁忌搜索等等，統(tǒng)稱為元啟發(fā)式算法（Meta-heuristic algorithms）。
另外，基于自然演化過程的算法除了在這里說到的遺傳算法以外，還有更廣泛的群體遺傳算法和遺傳編程等，它們能解決很多棘手的問題。這也從一個側(cè)面說明，我們不一定需要一個智能才能得到一個構(gòu)造精巧的系統(tǒng)。
無論如何，如果我們要將遺傳算法的發(fā)明歸功于一個人的話，我會將它歸功于達爾文，進化論的奠基人。如果我們不知道自然演化的過程，我們也不可能在電腦中模擬它，更不用說將它應用于實際了。
向達爾文致敬！
Bonus：如果你看明白了這篇文章，而且你懂英語的話，你自然明白下面這個冷笑話：（來自http://xkcd.com/534/）
Just to make sure you don’t have it maximize instead of minimize.
