霍蘭德的主要興趣在于適應現(xiàn)象——生物如何進化以應對其他生物和環(huán)境變化，計算機系統(tǒng)是不是也可以用類似的規(guī)則產(chǎn)生適應性。他在1975年的著作《自然和人工系統(tǒng)的適應》中列出了一組適應性的普遍原則，并且提出了遺傳算法的構(gòu)想。

遺傳算法菜譜

算法其實就是圖靈說的明確程序，就好比做菜的菜譜：一步一步將輸入變成輸出。

對于遺傳算法（GA），期望的輸出就是特定問題的解。GA的輸入包括兩部分：候選程序群體和適應性函數(shù)。適應性函數(shù)用來確定候選程序的適應度，度量程序完成指定任務的能力。候選程序可以表示成位、數(shù)字或符號組成的字符串。

下面是GA菜譜。我們將下面的步驟重復代數(shù)：

• 第1步：生成候選方案的初始群體。生成初始群體最簡單的辦法就是隨機生成大量“個體”，在這里個體是程序（字符串）。
• 第2步：計算當前群體中各個個體的適應度。
• 第3步：選擇一定數(shù)量適應度最高的個體作為下一代的父母。
• 第4步：將選出的父母進行配對。用父母進行重組產(chǎn)生出后代，伴有一定的隨機突變概率，后代加入形成新一代群體。選出的父母不斷產(chǎn)生后代，直到新的群體數(shù)量達到上限（即與初始群體數(shù)量一樣）。新的群體成為當前群體。
• 第5步：轉(zhuǎn)到第2步。

上面描述GA時似乎很簡單，但是遺傳算法已被用于解決科學和工程領(lǐng)域的許多難題，甚至應用到藝術(shù)、建筑和音樂。

掃易拉罐的機器人小黃

下面我們用一個更詳細的例子來進一步闡述GA的主要思想。

我有一個叫小黃的機器人，它的世界是二維的，到處是丟棄的易拉罐。我們將用遺傳算法為小黃進化出一個"腦"(即控制策略)。

小黃的工作是清理它的世界中的空易拉罐。由上圖所示，小黃的世界由10x10的100個格子組成。小黃在位置(0, 0)。我們可以假設周圍圍繞著一堵墻。許多格子中散落著易拉罐（每個格子中的易拉罐不會多于一個）。 小黃貌似不是很聰明的樣子，他只能看到東南西北相鄰的4個格子以及本身所在格子中的情況。格子可以是空的(沒有罐子)，或者有一個罐子，或者是墻。

每次清掃工作小黃可以執(zhí)行200個動作。動作可以是以下7種：

• 往北移動

• 往南移動

• 往東移動

• 往西移動

• 隨機移動

• 不動

• 收集罐子

每個動作都會受到獎賞或懲罰，如果小黃所在的格子中有罐子并且收集起來了，就會得到10分的獎賞。如果進行收集罐子的動作而格子中又沒有罐子，就會被罰1分。如果撞到了墻，會被罰5分，并彈回原來的格子。

顯然，小黃盡可能地多收集罐子，別撞墻，沒罐子的時候別去撿，得到的分數(shù)就最高。

這是一個比較簡單的問題，人工為小黃設計一個好策略可能也不是很難。不過，有了遺傳算法我們就可以什么也不用干，我們只需要等著計算機替我們進化出來。

下面我們用遺傳算法來為小黃進化出一個好策略。

要做的第一步，就是搞清楚我們想要進化的到底是啥？也就是說具體策略是啥？

一般來說，策略指的是一組規(guī)則，規(guī)則給出了在各種情形下你應當采取的行動。那么多少種可能的情形呢？小黃可以看到5個格子(當前格子、東、南、西、北)，每個格子可以標為空、罐和墻。這樣就有243種可能情形($3^5$種可能)

比如說，下面這張策略表顯示的就是一個策略：

要知道下一步怎么做，小黃只需要查看策略表。

小黃在(0, 0)位置時，查到對應的行動是往西移動。因此它往西移動一格，結(jié)果一頭撞到墻上。

我之前并沒有說這是個好的策略，尋找好策略不關(guān)我的事，這事歸遺傳算法管。

我們寫了一個遺傳算法程序來進化小黃的策略。算法中，群體里每一個個體都是一個策略(與各種可能情形相對應的行動列表)。也就是說，對于上面策略表中的策略，GA用來演化的個體就是最右側(cè)243個行動依次列出的列表。

現(xiàn)在，我們再次解釋一下GA的工作原理：

• 第1步：生成初始群體，初始群體有200個隨機個體，程序中用一個偽隨機數(shù)發(fā)生器來進行各種隨機選擇。

從現(xiàn)在開始我們重復1000次步驟2~步驟4。

• 第2步：計算群體中每個個體的適應度。比如說，通過讓小黃執(zhí)行100次不同的清掃任務來確定策略的適應度。每次將小黃置于位置(0, 0)，隨機撒一些易拉罐(每個格子至多1個易拉罐，格子有易拉罐的概率是50%)。然后讓小黃根據(jù)策略在每次任務中執(zhí)行200個動作。小黃的得分就是策略執(zhí)行各任務的分數(shù)。策略的適應度是執(zhí)行100次任務的平均得分，每次的罐子分布都不一樣。
• 第3步：進化，讓當前群體進化，產(chǎn)生出下一代群體，直到新群體有200個個體。進化的步驟如下：(a)根據(jù)適應度隨機選擇出一對個體A和B作為父母。策略的適應度越高，被選中的概率則越大。(b)父母交配產(chǎn)生兩個子代個體。隨機選擇一個位置將兩個數(shù)字串截斷；將A的前段與B的后段合在一起形成一個子代個體，將A的后段與B的前段個體合在一起形成另一個子代個體。?讓子代個體以很小的概率產(chǎn)生變異。以小概率選出1個或幾個數(shù)，用0到6之間的隨機數(shù)替換。
• 第4步：新群體產(chǎn)生200個個體后，回到第2步，對新一代群體進行處理。

GA如何演化出好的技巧

要回答GA如何演化出好的技巧這個問題，我們可以看一看策略是如何一代一代改進的。下圖繪制出了每一代中最佳策略的適應度：

由上圖可以看出，前300代提高得很快，此后的提高要慢一些。

第1代有200個隨機生成的策略，可以想象它們都很糟糕。最好的策略適應度才-81，最糟糕的到了-825。在一些環(huán)境設定中，小黃移動了幾步就卡住了，之后在整個任務過程中都停止不動。在一些情況下，則不停地撞墻，直到任務結(jié)束。有時候則一直不斷地去撿罐子，雖然當前位置上沒有罐子。

到第10代，群體中最佳策略的適應度已經(jīng)變成正數(shù)了。這個策略經(jīng)常會停滯不動，有時候還會在兩個格子之間不停地來回移動。但基本不怎么撞墻。

到200代時，最好的策略已經(jīng)具有向罐子移動并撿起罐子這個最重要的能力—至少大部分時候是這樣。不過，如果周圍沒有罐子，它也會浪費很多時間用來隨機游走。

到了400代，適應度超過了400分。

到800代時，GA發(fā)現(xiàn)了將罐子留作相鄰罐子的路標的技巧。

GA就這樣不斷改進最佳適應度。

在實際應用中，GA經(jīng)常能演化出有用的答案，但是很難看出為什么會有用。這是因為GA找到的好答案與人類想出的相當不同。美國國家航空航天局（NASA）的遺傳算法專家羅恩曾這樣說：“進化算法是探索設計死角的偉大工具。但是，我們經(jīng)常發(fā)現(xiàn)進化出來的設計完全無法理解?！?/font>