書名：代碼本色：用編程模擬自然系統(tǒng)
作者：Daniel Shiffman
譯者：周晗彬
ISBN：978-7-115-36947-5
第9章目錄
9.6 遺傳算法，第三部分：繁殖
1、繁殖
- 現(xiàn)在我們已經(jīng)有了選擇父代的策略，下面就開始討論繁殖下一代的方法，這一步的關(guān)鍵在于達(dá)爾文的遺傳法則——子代能繼承父代的特性。
- 繁殖的實現(xiàn)方式也有很多種。
- 無性繁殖就是一種合理（并容易實現(xiàn)）的策略，該策略用單個父本復(fù)制出子代個體。
- 但遺傳算法的標(biāo)準(zhǔn)方法是用兩個父本繁殖后代，具體步驟如下。
1.交叉
2.突變
2、交叉
交叉就是根據(jù)雙親的遺傳密碼創(chuàng)建一個子代。
-
拿猴子敲鍵盤舉例，假設(shè)我們從交配池中選擇了兩個句子（如選擇部分所述）。
父本A：FORK
父本B：PLAY
下面，我們要根據(jù)這兩個語句創(chuàng)建子代。最直觀的方法（我們稱為50/50方法）就是取A的前兩個字符，取B的后兩個字符，把這兩部分拼接在一起：
-
這種交叉方法能進(jìn)一步改進(jìn)：我們不一定從每個父本中都各選一半的遺傳密碼，而應(yīng)該選擇隨機(jī)的中間分割點。
改進(jìn)后，我們還可能得到“FLAY”或“FORY”。這種方法比50/50方法更好，因為它能提高子代的多樣性。
-
還有一種方式是為子代的每個字符隨機(jī)選擇父代。你可以把它想象成擲4次硬幣：正面朝上則選擇A，反面朝上則選擇B。如此一來，我們就能得到各種結(jié)果，如：“PLRY”“FLRK”“FLRY”“FORY”……
這種方法產(chǎn)生的結(jié)果和選擇隨機(jī)中間點法基本上一樣；
但是如果基因的順序?qū)Ρ憩F(xiàn)型有一定程度的決定作用，你就應(yīng)該根據(jù)具體需求選擇其中的一種方法。
3、突變
交叉過程產(chǎn)生子代DNA，但還要經(jīng)歷突變過程才能最終確定。突變是一個可選的過程，某些場景不會涉及突變。根據(jù)達(dá)爾文的進(jìn)化學(xué)說，突變是普遍存在的。在初始化過程中，我們用隨機(jī)的方式創(chuàng)建種群，確保種群有一定的多樣性。但在孕育第一代時，種群的多樣性就已經(jīng)確定了；而突變的作用就是在進(jìn)化過程中不斷引入多樣性。
-
突變可以用突變率描述。一個遺傳算法可能有5%、1%或0.1%的突變率。假設(shè)交叉完成后，某子代個體是“FORY”，如果突變率為1%，這意味著每個字符有1%的突變概率。而字符怎么發(fā)生突變呢？在本例中，我們把突變定義為用一個隨機(jī)的字符替換原字符。1%是一個很低的突變率，對于由4個字符組成的字符串來說，在大部分時間它都不會發(fā)生突變（確切地說，在96%的時間都不會發(fā)生突變）。一旦突變發(fā)生，當(dāng)前字符就會被替換成另一個隨機(jī)字符（如圖9-6所示）。
在某些場景中，突變率能顯著地影響系統(tǒng)行為。高突變率（比如，80%的突變率）會阻礙進(jìn)化過程。如果大部分子代基因是隨機(jī)產(chǎn)生的，我們就無法保證“合適”的基因能頻繁地出現(xiàn)在后代中。
在獲得新種群之前，我們會不斷地進(jìn)行選擇（選擇兩個父本）和繁殖（交叉和突變）操作。一旦子代種群代替了當(dāng)前種群，我們還會回到之前的步驟：再次評估適應(yīng)度，再次進(jìn)行選擇和繁殖操作。
4、代碼實現(xiàn)
到目前為止，我們已經(jīng)詳細(xì)地描述了遺傳算法的所有步驟，接下來，我們需要將這些步驟翻譯成Processing代碼。由于前面的描述有些冗長，我們先對此作個總結(jié)，把遺傳算法分成幾個步驟。
SETUP
第1步：初始化 創(chuàng)建由N個個體組成的種群，隨機(jī)確定個體的DNA。
LOOP
第2步：選擇 評估個體的適應(yīng)度，創(chuàng)建交配池。
第3步：繁殖 重復(fù)N次。
a) 根據(jù)相對適應(yīng)度，概率性地選擇兩個父本。
b) 雜交——結(jié)合父本的DNA，創(chuàng)建出一個“子代個體”。
c) 突變——以一定的概率使子代的DNA發(fā)生突變。
d) 將這個子代加入新種群。
第4步：用新種群替換舊種群，再回到第2步。
