這一節的標題是
9.3 How Genetic Algorithms Work
因為方格子標題字數限制，所以沒完整顯現
在寫程式之前先來看一下，傳統的GA是透過哪些步驟來讓生物族群一代一代地演化下去的。要注意一下，這裡所指的「生物」，就只是個通稱，指的是要模擬的東西，而不一定是真正活生生的生物；它可以是模擬世界中的物件，也可以就只是字串。
要用程式寫出像自然界中的天擇(natural selection)效果，就必須把達爾文演化論的三個核心原則給寫進程式中。這三個核心原則是：
- 遺傳(heredity)：一定會有個機制，可以讓某一代的生物將其特徵傳遞給下一代。
- 變異(variation)：生物族群必定具有多種特徵，或者具有可以引入變異的手段，演化才能夠進行。一群長得一模一樣具有完全相同特徵的甲蟲，如果沒有任何變異，那它們所產下的下一代，就會跟父母長得一模一樣，而彼此之間也沒任何不同。因為永遠不會有新的特徵組合，所以也就沒什麼可以演化的。
- 挑選(selection)：一定有會個機制，可以只讓一部分生物成為父母，並將遺傳資訊傳遞給下一代。這個機制通常稱為「適者生存」(survival of the fittest)。例如，貓抓老鼠，警覺性高、跑得快、比較會躲的老鼠，比較有機會躲過一劫而倖存下來，也才有機會能繁衍下一代，並把遺傳訊息給傳遞下去。這裡要注意的是，不要誤以為「適者」兩個字，所指的就是最大、跑最快、最強壯的那些個體；它實際上指的是最能適應生存環境的個體。天擇的核心意義在於，任何特徵，只要能讓個體最佳地適應環境而生存下來，而最終得以繁衍下一代，就是會被挑選出來讓個體成為「適者」的特徵。所以，體型比較大的老鼠，雖然可能在同類中佔有優勢，但如果因此而比較容易讓貓兒發現而被抓，那這個特徵可就不一定能讓這些老鼠成為天擇下的「適者」了。所以，關於「適者」，比較能夠說明其意義的說法是：能夠繁衍下一代的個體。
Step 1: Population Creation
以電腦猴打字的例子來看，GA的第一步是造出片語族群。這裡的「片語」，泛指任何由字元所構成的字串，而這些片語，也就是這個例子中的「生物」。
在製造片語族群時，根據達爾文演化論的變異原則，這些片語之間必須存在變異，這樣演化才會進行。不過，在使用GA時，如果一開始所造出的族群變異程度不足，那會很難演化到產生最佳的解答。
什麼叫「族群變異程度不足」呢？來看個簡單的例子就知道了。
假設我們想讓片語族群演化出「cat」一詞，而我們造出來的片語族群是rid、won、hug這三個片語。這三個片語之間沒有任何相同的字母，它們之間顯然存在變異。不過，很明顯的，不管用什麼樣的排列組合方式，都沒辦法用這三個片語中的字母來拼出我們想要的「cat」這個片語；這就是族群變異不足所造成的結果。
那怎麼辦呢？要怎麼提高族群的變異程度呢？方法其實挺簡單的，用亂數造個含有幾千個片語的族群就可以了。幾千個由亂數造出的片語，總會有個片語第一個字母是c、總會有個片語第二個字母是a、總會有個片語第三個字母是a吧？族群越大，這個機率就會越高。這樣子就有足夠的變異來演化出「cat」這個片語了。
等等！那萬一運氣就這麼背，幾千個片語中，就是沒有一個含有字母c，那怎麼辦？把族群再造大一點？那還是不能保證一定有片語含有字母c啊！這個倒不用擔心，後面的Step 3中，有另一個可以增加變異的機制，可以補救一開始時變異不足的問題；到時再說。
由上面的說明，Step 1可以描述為：
製造一個由隨機產生的元素所組成的族群。
這裡改用「元素」這個詞來指稱族群的成員，這樣會比用「生物」一詞來得好一些；畢竟萬事萬物都可以是GA中族群的成員，如果成員是「片語」，用「生物」來指稱「片語」，還真是挺彆扭的。
元素有個特點，就是它們都具有虛擬DNA。什麼是DNA呢？就是一組用來描述元素長相和行為的性質；這些性質也稱為基因。例如，在電腦猴打字的例子中，元素是指「片語」，因而DNA就可以是由字元所組成的字串。
讓元素具備DNA之後，GA的Step 1可以進一步地描述為：
製造一個由N個元素所組成的族群，而每個元素都具有隨機產生的DNA。
要想活用GA，就必須能夠清楚地區分基因型(genotype)與表現型(phenotype)這兩個遺傳學領域的重要概念。基因型是生物DNA中特定的分子序列，是真正的遺傳密碼，也是會一代一代傳下去的東西。至於表現型，則是生物體可觀察到的，如大小、血型、毛色等特徵。
在設計模擬世界中的物件時，我們必須考慮要用什麼樣的資料結構來儲存物件的屬性，以及這些屬性所取得的值；這些就是物件的基因型。除此之外，我們也必須根據這些資訊來設計物件的表現型，也就是要決定這些變數所代表的，究竟是什麼東西。
又是基因型，又是表現型，講得很有學問，好像很難，但其實我們早就用這樣的方式在寫程式了。例如，在繪圖的時候，我們使用0～255的整數來代表灰階顏色的濃淡；0代表全黑、255代表全白。這些個0～255的整數，就是基因型；而這些數字所展現出來的顏色，就是表現型。
基因型提供的資訊要轉換成什麼樣的表現型，完全取決於我們。我們也可以讓0～255的整數代表紅色的濃淡，甚至於代表線段的長度。當然啦，你要讓0～255的整數就代表0～255的整數也可以。這也就是說，基因型和表現型並非一定要有所不同，它們也可以是完全相同的東西，就看我們怎麼設計。以電腦猴打字的例子來說，基因型是那一串字串，而表現型也同樣是那一串字串，兩者之間沒有任何不同。
Step 2: Selection
GA的第二個步驟要進行的，是依據達爾文演化論中的挑選原則，挑出族群中適合繁殖下一代的個體。挑選的過程可分為兩個步驟：
1. 評估適應度(fitness)
2. 建立交配群(mating pool)
要進行第一個步驟，我們需要先設計一個適應度函數(fitness function)。這個函數的主要用途，是要根據個體適應得好不好來幫它打分數；適應得越好，分數會越高。當然啦，在真實世界中，根本就不會用打分數的方式來決定個體適應得好不好。大自然採用的方式很直接也很簡單：能夠成功繁殖下一代的，就是適應得好的；沒辦法繁殖的，就是適應得不好的。傳統GA的主要功用，是用來找出問題的最佳解，所以才會需要用打分數的方式來評估眾多不同的解中，哪個比較好，哪個比較差。
那這個適應度函數要怎麼設計呢？看個例子就知道了。
假設我們希望電腦猴能夠打出「cat」這個片語，而現在族群中有三個個體：hut、car、box。很顯然的，這三個個體中，適應得最好的是car，因為有兩個正確的字母在正確的位置上；hut次之，因為只有一個正確的字母在正確的位置上；box最差，因為沒有任何正確的字母在正確的位置上。所以，適應度函數就可以設計成
fitness = 正確的字元數量
而這三個個體的適應度分數，也就是函數中的fitness，就會是
DNA fitness
car 2
hut 1
box 0
這就是適應度函數的設計方式。不過要注意的是，這只是其中一種可行的設計方式；只要能達到幫個體適應程度打分數的目的，任何設計方式都是可行的。
幫個體打完分數之後，接下來的步驟就是要挑出適合繁殖下一代的個體，並把它們聚集起來準備交配。這些挑出來準備讓它們交配的個體所組成的群體，就叫做mating pool。很多人看到pool這個字，就直接翻譯成「交配池」。但這樣的翻法，其實並不怎麼好，會讓人誤以為就是個讓個體交配用的池子。「pool」這個英文單字，根據奇摩英英字典的解釋，有個意思是
a group of people available for work when required or considered as a resource
所以，把「mating pool」翻成「交配群」，應該會比較接近原意，也比較不容易產生誤解。
建立交配群的做法有很多種，各有各的優缺點。例如，菁英法(elitist method)會挑出分數最高的兩個個體來產生下一代。這個方法很簡單，但卻會牴觸變異原則。整個群體中就只有兩個個體可以繁殖下一代，那下一代將不會有太大的變化，因而會阻礙演化的進行。
既然只挑前兩名太少，那挑前50%如何？這個方法也挺簡單的，不過結果也不會是最好的。這麼做的話，分數最高的個體和分數中間的個體，它們被選中來繁殖下一代的機會是一樣的；這明顯就會讓人覺得不合理。由1000個個體所組成的群體，第500名憑什麼和第1名平起平坐，擁有相同的機會被挑選出來？還有，第500名有實實在在的機會被挑中，而只差了一名的第501名，卻一丁點機會都沒有，這又是個什麼道理？
其實，小兵也可以立大功的。分數低的個體並非一無是處，它說不定擁有分數高的個體所沒有的東西。例如，如果我們想讓A、B、C三個元素所組成的群體演化出「to be or not to be」這個字串，而各個元素的DNA如下：
元素 DNA
A to be or not to go
B to be or not to pi
C purrrrrrrrrrrrr be
用先前提到的適應函數來評分，顯然元素C的分數會遠低於元素A、B的分數。然而，元素C的DNA中，最後兩個字元卻恰好是正確的字元，而這是元素A、B所沒有的。就此來看，讓分數最低的元素C也能繁殖下一代，反而有助於演化出我們想要的答案。
所以，與其一刀切，只挑出分數比較高的而完全屏棄分數比較低的，那倒不如讓每個個體都有機會被挑中；當然啦，分數高的個體機會應該要多一些。
那要怎麼做，才能讓分數高的機會比較多，而分數低的也不至於機會全無呢？其實，根據分數的高低來決定被挑中的機率大小就可以了。
要根據分數的高低來決定被挑中的機率大小，最簡單的做法，就是把分數正規化；正規化後的分數，會介於0～1之間，所以這個正規化之後的分數，就可以作為元素被挑中的機率。來看個實際的例子會更清楚一些。假設有個由5個元素所組成的族群，各個元素的分數為：
元素 分數
A 3.0
B 4.0
C 0.5
D 1.0
E 1.5
元素的分數除以所有元素分數的總和，就是這個元素正規化之後的分數。在這個例子中，元素分數的總和為10，所以算出來各個元素正規化後的分數為：
元素 分數 正規化分數
A 3.0 0.30
B 4.0 0.40
C 0.5 0.05
D 1.0 0.10
E 1.5 0.15
從上表可以看出來，每個元素都有被挑中的機率，而且分數越高的機率越高；分數最高的元素B，最有機會被挑中，而分數最低的元素C，儘管機率很低，還是有機會被挑中，不至於機會全無。
Step 3: Reproduction
挑選出適合繁殖下一代的個體建立交配群之後，接下來就是要讓它們繁殖產生下一代。繁殖時，根據達爾文演化論的遺傳原則，必須讓它們將特徵傳遞給下一代。有很多做法可以達到這個目的。例如，直接複製父母其中一個的特徵給下一代。這個做法挺合理的，程式寫起來也簡單，但卻與演化論的變異原則背道而馳。那要怎麼做比較好呢？GA的標準做法，是透過下列兩個步驟來產生下一代：
1. 交配(crossover)
2. 突變(mutation)
交配這個步驟要做的，是分別提取父母的一部分特徵來給下一代。例如，假設在交配群中有下列兩個元素：
元素 DNA
A coding
B nature
元素A、B的DNA是由6個字元所組成的字串，所以交配這個步驟要做的，就是分別從A、B的DNA中取出幾個字元，組成一個含有6個字元的字串。
那是要怎麼個取法呢？方式有很多，最直接會想到的，就是A的DNA取前半部3個字元、B的DNA取後半部3個字元，分別當作下一代DNA的前、後半部。所以，A、B交配之後所生出的下一代，其DNA會是「codure」。
另一種從前面那種切一半的做法所衍生出來的做法，是隨機選取要下刀的地方。例如，不切成3加3，而切成1加5，或者切成4加2。切成1加5所產生的下一代，其DNA會是cature；切成4加2所產生的下一代，其DNA則是codire。這種做法要比切一半的做法好，因為可以提高下一代變異的可能性。
除了前面那種一刀切的方式之外，也可以一個一個字元用隨機的方式選取，看是要用A的DNA字元，還是要用B的DNA字元。例如，如果丟6次銅板的結果是「正反反正反反」，那下一代的DNA就會是「catire」。
當下一代的DNA經由交配產生之後，針對這個DNA，還有個可做可不做的步驟：突變。
突變這個步驟的主要目的，是要進一步地確保繁殖過程能遵循變異原則。剛開始時，族群內的各個元素都是隨機產生的，這確保了族群元素的多樣性。然而，這雖然能讓元素間在一開始時存在差異，但這差異的程度會受限於族群的規模，而且隨著一次又一次的挑選，元素間的差異會越來越小，導致越來越難遵循變異原則進行演化。透過突變這個步驟，可以引進額外的多樣性，確保元素間仍存在一定的差異，使其仍能繼續遵循變異原則進行演化。
突變會以突變率來表示；例如突變率1%、5%等。那實際上要怎麼進行突變呢？假設完成交配步驟所得到的下一代DNA是「catire」，而突變率是0.1%。這就表示「catire」這個字串中的每個字元，都有0.1%的機率轉變成其他字元。至於要透過什麼方式轉變，又會轉變成什麼字元，則可以根據需要來設計。例如，可以利用亂數來決定要轉變成什麼字元。
突變率的高低影響系統的演化行為甚鉅；突變率越高，越會對系統的演化行為造成負面影響，而讓GA變得越來越像是暴力演算法；當突變率是100%時，下一代DNA中的所有字元都會是隨機產生的，這不十足就是暴力演算法嗎？！
從配對群中選出個體讓它們交配並生出下一代，這個過程會不斷地進行，直到下一代個體的數量跟這一代個體的數量相同為止。這時，新一代的族群出現了，而舊一代的族群個體，也完成了它們的演化工作。
Step 4: Repetition!
透過Step 2、Step 3所產生的族群，會再透過Step 2、Step 3產生下一代的族群，如此一代一代不斷地演化下去。透過這樣子不斷演化的方式，系統也會越來越接近我們所想要的答案。
以上就是傳統GA的運作方式。在介紹這些步驟時，原書是使用DNA來指稱要進行演化的個體特徵，而不是使用一般GA文獻資料中所使用的「染色體」(chromosome)一詞。在生物學上，染色體和DNA是兩種不同的東西。簡單來說，染色體、DNA、基因這三者的關係是：染色體中含有DNA，而DNA中又含有基因。不過，既然GA只是借用生物學上的概念，所以在實際運作時，染色體和DNA所指的，其實是同樣的東西。事實上，在GA中，個體、染色體、DNA都是指同樣的東西；而個體的特徵、性質、基因，也都是指同樣的東西。在閱讀GA相關的資料時，應該要能夠清楚地認知到，這些只是從生物學中借用的名詞，頂多在概念上有相同之處，並不一定會跟生物學中所指有嚴絲合縫的對應關係。
