本書的前兩章從某種抽象意義上定義了演化演算法。計分、選擇、種群、交叉和突變都是演化演算法的重要特點，但是我們尚未將所有這些特點整合到一個具體演算法中。

遺傳演算法是一種特殊的演化演算法，但是在描述遺傳演算法的文獻中，其定義各不相同。本書將遺傳演算法定義為一種可以用交叉和突變運算元最佳化固定長度向量的演化演算法。計分函式可以區分優劣方案，以最佳化該固定長度的向量。這個定義說明了遺傳演算法的本質。

此外，可以將可選特徵新增到遺傳演算法中，以增強其效能。例如物種形成、精英和其他選擇方法之類的技術，有時可以改善遺傳演算法的執行效果。

3.1　離散問題的遺傳演算法

與其他演算法相似，針對連續學習和離散學習，遺傳演算法採用略有不同的方法。連續學習涉及計算數值，而離散學習涉及識別非數值。本節將展示如何將離散學習和連續學習應用於以下兩個經典的AI問題：

旅行商問題；鳶尾花物種建模。

對於旅行商問題，我們將展示如何將遺傳演算法應用於離散學習的組合問題，目標是找到最佳的城市序列。同時，我們將擬合RBF神經網路的權重以識別鳶尾花種類，這將作為連續問題的遺傳演算法示例，即對數字權重進行調整。

3.1.1　旅行商問題

旅行商問題（Traveling Salesman Problem，TSP）涉及為旅行商確定最短路徑。旅行商必須訪問一定數量的城市，儘管他可以從任何城市開始和結束，但他只能訪問每個城市一次。TSP有多個變體，其中一些變體允許多次訪問每個城市，或為每個城市分配不同的值。本章中的TSP只是尋求一條儘可能短的路線，每個城市訪問一次。圖3-1展示了這裡介紹的TSP和最短路徑。

圖3-1　旅行商問題

對於普通的迭代程式而言，找到最短的路徑似乎很容易。但是，隨著城市數量的增加，可能的組合數量也會急劇增加。如果問題有一個或兩個城市，則只能選擇一條路徑；如果包括3個城市，則可能的路徑將增加到6個。以下列表展示了路徑數量增長的速度：

1個城市有1條路徑2個城市有2條路徑3個城市有6條路徑4個城市有24條路徑5個城市有120條路徑6個城市有720條路徑7個城市有5 040條路徑8個城市有40 320條路徑9個城市有362 880條路徑10個城市有3 628 800條路徑11個城市有39 916 800條路徑12個城市有479 001 600條路徑13個城市有6 227 020 800條路徑……50個城市有3.041 × 10ˆ64條路徑

在上表中，用於計算總路徑條數的公式是階乘。使用階乘運算子！作用於城市數n。某個任意值n的階乘由n×(n − 1)×(n − 2)×…×3× 2×1給出。當程式必須執行蠻力搜尋時，這些值會變得非常大。TSP是“非確定性多項式時間”（non-deterministic polynomialtime，NP）難題的一個例子。“NP困難”（NP-hard）被非正式地定義為“一系列不能用暴力搜尋法求解的問題”。當超過10個城市時，TSP滿足這個定義。NP困難的正式定義可以在Computers and Intractability: A Guide to the Theory of NP-Completeness [1]一書中找到。

動態程式設計是解決TSP的另一種常用方法，如圖3-2的漫畫所示。

圖3-2　解決TSP的方法（來自xkcd網站）

3.1.2　為旅行商問題設計遺傳演算法

TSP是最著名的計算機科學問題之一。由於傳統的迭代演算法通常無法解決NP困難問題，因此程式設計師必須使用遺傳演算法來生成潛在解。因此，我們將研究如何將遺傳演算法應用於TSP。

離散遺傳演算法決定了你要使用的交叉和突變運算元的型別。由於離散問題是分類問題，因此你無須處理數值。所以，你可能訪問的城市就是TSP中的分類資訊。按照訪問順序，城市列表是每個解的基因組。下面展示瞭如何表達TSP基因組：

[洛杉磯, 芝加哥, 紐約]

你的初始種群將是這些城市的隨機排列。例如，初始隨機種群可能類似於以下列表：

[洛杉磯, 芝加哥, 紐約] [芝加哥, 洛杉磯, 紐約] [紐約, 洛杉磯, 芝加哥]

你可以計算在每條路徑上行駛的英里（1英里=1 609.344米）數，從而為上述城市建立一個計分函式。考慮第一個種群成員。根據Google Maps的駕駛導航，洛杉磯至芝加哥為2 016英里，芝加哥至紐約為790英里。因此，第一個種群成員覆蓋的整個距離為2 806英里。距離是我們要最小化的分數。以上3個種群成員及其分數顯示如下。

[洛杉磯, 芝加哥, 紐約] -> 分數: 2 016 + 790 = 2 806[芝加哥, 洛杉磯, 紐約] -> 分數: 2 016 + 2 776 = 4 792 [紐約, 洛杉磯, 芝加哥] -> 分數: 2 776 + 2 016 = 4 792

如你所見，最後兩條路徑的分數相同，因為旅行商可以從任何城市開始，所以最後兩條路徑產生相同的距離。旅行商問題的某些變體可以固定起點和終點城市。作為旅行商的家鄉，起點和終點是相同的。其他變體讓旅行商可以多次訪問同一座城市。簡而言之，如何定義旅行商問題的規則將決定如何實現計算機程式。

考慮一下這種情況：旅行商總是從同一城市（即他的家鄉）開始，並最終返回這裡。在這個例子中，家鄉城市是密蘇里州的聖路易斯。此外，分數將是兩個城市間最便宜機票的價格。由於基因組仍將由洛杉磯、芝加哥和紐約的排列組成，因此聖路易斯沒有必要出現在基因組的開始和結尾。這樣可以防止演算法將聖路易斯更改為不是路徑的起點或終點。換言之，計分函式隱式地將聖路易斯作為路徑的起點和終點，並對其進行適當的處理。檢查第一個種群成員，如下所示。

[洛杉磯, 芝加哥, 紐約]

該示例包括以下旅程。

聖路易斯至洛杉磯 -> 費用: $393洛杉磯至芝加哥 -> 費用: $452芝加哥至紐約 -> 費用: $248 紐約至聖路易斯 -> 費用: $295 總計:　$1388

對問題的微小改動帶來了很大的複雜性。由於聖路易斯位於美國中部，旅行商無法再從東到西或從西到東走一條簡單的路。此外，機票價格不可互換，因為從芝加哥到聖路易斯的票價不一定與從聖路易斯到芝加哥的票價相同。旅行當天機票價格的變化使這個問題更加複雜。因此，基因組可以包括開始和結束日期。這樣，遺傳演算法可以優化出行計劃和城市順序。

你還可以建立演算法，以允許旅行商多次訪問同一座城市，但是，這個要求增大了計分函式的複雜性。如果你放寬要求，讓旅行商可以多次訪問同一座城市，則最佳分數可能來自以下解：

[芝加哥, 芝加哥, 芝加哥]

上述解的分數十分理想。該演算法選擇了從聖路易斯到最便宜的目的地芝加哥的路徑。然後，演算法再次選擇芝加哥作為第2和第3站。因為從芝加哥到芝加哥的機票是0美元，所以這次旅行的分數非常好。顯然，在這種情況下，該演算法沒有為程式設計師做任何額外的工作。因此，計分函式需要更復雜才能傳達真正最優解的引數。也許有些城市更有價值，需要拜訪，而另一些則是可選的。設計計分函式對於遺傳演算法程式設計至關重要。

3.1.3　旅行商問題在遺傳演算法中的應用

現在，我們將看到一個簡單的遺傳演算法的示例，它用一條好路徑穿過一系列城市。50個城市隨機放置在256×256網格上。該程式使用了1 000條路徑的種群，來演化出穿過這些城市的最佳路徑。因為城市列表是分類值，所以TSP是一個離散的問題。在這個示例中，計分函式計算出一條城市路徑所覆蓋的總距離，這些城市中的任何一個都不會被訪問兩次。

這些引數決定了最合適的突變和交叉運算元的選擇。對於這個示例，改組突變運算元是最佳選擇。如第2章所述，改組突變運算元可與固定長度的分類資料配合使用。同樣，我們將使用無重複的拼接交叉運算元。兩個運算元都允許1 000條路徑的種群演化，並且無重複的交叉強制實現了我們的要求，即同一城市只被訪問一次。

我對該程式進行了數百次迭代，直到連續經過50次迭代而沒有出現一次改善最佳路徑長度的情況。一次迭代即經過了一個世代。程式的輸出在下面列出。

Iteration: 1 , Best Path Length = 5308.0Iteration: 2 , Best Path Length = 5209.0Iteration: 3 , Best Path Length = 5209.0Iteration: 4 , Best Path Length = 5209.0Iteration: 5 , Best Path Length = 5209.0Iteration: 6 , Best Path Length = 5163.0Iteration: 7 , Best Path Length = 5163.0Iteration: 8 , Best Path Length = 5163.0Iteration: 9 , Best Path Length = 5163.0Iteration: 10 , Best Path Length = 5163.0...Iteration: 260 , Best Path Length = 4449.0Iteration: 261 , Best Path Length = 4449.0Iteration: 262 , Best Path Length = 4449.0Iteration: 263 , Best Path Length = 4449.0Iteration: 264 , Best Path Length = 4449.0Iteration: 265 , Best Path Length = 4449.0Good solution found:22>1>37>30>11>33>39>24>9>16>40>3>17>49>31>48>46>20>13>47>23>0>2>29>27>14>34>26>15>7>35>19>21>18>6>28>25>45>8>38>43>32>41>5>10>4>44>36>12>42

如你所見，在程式確定一個解之前，發生了265次迭代。由於城市是隨機的，因此它們沒有實際名稱，而是將城市標記為“1”“2”“3”等。上面顯示的最優解從城市22開始，接下來是城市1，最終在城市42停止。你可以在以下網址檢視線上的TSP實現：

http://www.heatonresearch.com/aifh/vol2/tsp_genetic.html

3.2　連續問題的遺傳演算法

程式設計師還可以利用遺傳演算法來演化連續的（即數值的）資料。在下面的示例中，我們將基於4個輸入測量值來預測鳶尾花的種類。因此，我們的遺傳演算法將訓練一個徑向基函式（Radial-Basis Function，RBF）網路模型。

模型是一種演算法，它基於輸入向量進行預測，這稱為預測建模。對於鳶尾花資料集，我們將為RBF網路提供4個描述鳶尾花的測量值。RBF網路將根據這4個測量結果預測鳶尾花種屬。它透過訓練示例中的150朵花的資料來進行學習預測。該模型可以預測訓練集中未包含的新花的種屬。

讓我們回顧一下如何訓練模型。3個主要部分確定了遺傳演算法如何訓練任何模型：

訓練設定；超引數；引數。

訓練設定是遺傳演算法所獨有的，例如種群數量、精英數、交叉演算法和突變演算法。在本書的後文，我們將學習粒子群最佳化（PSO）和蟻群最佳化（ACO），它們是RBF網路模型的訓練演算法。PSO和ACO的訓練設定具有獨有的特徵。程式設計師通常會建立訓練引數，因此，選擇最佳的引數可能需要反覆試驗。

超引數定義模型的結構。考慮圖3-3，該圖展示了RBF網路的結構。

圖3-3　以鳶尾花資料集為輸入的RBF網路的結構

在圖3-3中，第2列顯示的是3個具有凸起形狀曲線的框，它們是RBF，使RBF網路能夠做出預測。這個任務所需的RBF網路的數量是一個超引數，程式設計師或計算機可以確定該超引數。儘管RBF數量不影響遺傳訓練，但是如果你正在使用PSO和ACO進行訓練，你仍然需要設定RBF數量。不過，你要小心，如果將RBF數量設定得太低，則建立的模型會很簡單，以至於無法從資訊中學習；如果將RBF數量設定得太高，則建立的網路會很複雜且難以訓練，並可能導致過度擬合。這是我們不希望的情況，這時模型開始將資料儲存在資料集中，而不是學習更通用的解。第10章將介紹過度擬合及其避免方法。在本章中，我們將RBF數量設定為5，這對於鳶尾花資料集似乎效果很好。我透過試驗確定了這個數字。

計算機也可以確定超引數，其中試錯法通常是找到超引數的方法。只需在1～10個RBF之間迴圈，並讓計算機嘗試每種情況。一旦測試了全部10個RBF，程式就會選擇獲得最佳分數的模型。該模型將告訴你RBF數量超引數的最佳設定。

最後的組成部分是引數向量。在訓練模型時，模型會調整引數向量。這方面與超引數有所不同，因為一旦訓練開始，模型就不會調整超引數。實際上，超引數定義了模型，無法更改。對引數向量進行調整是一種訓練演算法（例如遺傳演算法、PSO或ACO）教給模型針對給定輸入的正確響應的方法。遺傳演算法利用交叉和突變來調整引數向量。

下面列出的輸出展示了使用遺傳演算法針對鳶尾花資料集訓練RBF網路的進度。如你所見，分數在前10次迭代中並沒有提高。這些迭代中的每一次迭代代表一代潛在解。分數代表錯誤分類的150朵鳶尾花的百分比，我們力求讓這個分數最小。

Iteration #1, Score = 0.1752302452792032, Species Count: 1Iteration #2, Score = 0.1752302452792032, Species Count: 1Iteration #3, Score = 0.1752302452792032, Species Count: 1Iteration #4, Score = 0.1752302452792032, Species Count: 1Iteration #5, Score = 0.1752302452792032, Species Count: 1Iteration #6, Score = 0.1752302452792032, Species Count: 1Iteration #7, Score = 0.1752302452792032, Species Count: 1Iteration #8, Score = 0.1752302452792032, Species Count: 1Iteration #9, Score = 0.1752302452792032, Species Count: 1Iteration #10, Score = 0.1752302452792032, Species Count: 1...Iteration #945, Score = 0.05289116605845716, Species Count: 1Iteration #946, Score = 0.05289116605845716, Species Count: 1Iteration #947, Score = 0.05289116605845716, Species Count: 1Iteration #948, Score = 0.051833695704776035, Species Count: 1Iteration #949, Score = 0.05050776383877834, Species Count: 1Iteration #950, Score = 0.04932340367757065, Species Count: 1Final score: 0.04932340367757065[- 0.55, 0.24, -0.86, -0.91] -> Iris-setosa, Ideal: Iris-setosa　[-0.66, -0.16, -0.86, -0.91] -> Iris-setosa, Ideal: Iris-setosa[-0.77, 0. 0, -0.89, -0.91] -> Iris-setosa, Ideal: Iris-setosa...[0.22, -0.16, 0.42, 0.58] -> Iris-virginica, Ideal: Iris-virginica[0.05, 0.16, 0.49, 0.83] -> Iris-virginica, Ideal: Iris-virginica[-0.11, -0.16, 0.38, 0.41] -> Iris-virginica, Ideal: Iris-virginica

在以上輸出中，你可能還看到了物種計數（species count）。由於我們目前不使用物種，因此它保持為1。第5章將介紹物種。

3.3　遺傳演算法的其他應用

鳶尾花資料集和旅行商問題是人工智慧文獻中的常見例子。觀察各種演算法如何解決相同的問題，可以有助於理解它們的差異，檢查新問題與遺傳演算法相符合的方式同樣有價值。本節將說明如何讓各種問題適應遺傳演算法。

儘管本書目前未實現這些應用程式，但將來可能會包含它們。以下各小節的主要目的是演示遺傳演算法在各種情況下的應用。

3.3.1　標籤雲

標籤雲是一種方便的工具，可用於視覺化文件中的單詞頻率計數。實際上，一個小的標籤雲可以代表一個很長的文件中的常用單詞，但是，標籤雲演算法通常會從單詞數統計中刪除結構化單詞（例如“the”）。圖3-4展示了根據《人工智慧演算法（卷1）：基礎演算法》英文版建立的標籤雲。

圖3-4　卷1的標籤雲

圖3-4所示的標籤雲展示了每個單詞出現的頻率。你可以輕鬆地看到，“algorithm”是卷1中最常見的單詞。

要建立標籤雲，必須統計單詞數。下面展示了構建圖3-4所示標籤雲的單詞計數：

341 algorithm239 training203 data201 output198 random192 algorithms169 number163 input...

單詞計數提供每個單詞的出現頻率，並與其他單詞對比。標籤雲中的單詞互相交織，使得單詞之間的空白空間最小。在示例中，較小的單詞填充了“algorithm”的“h”和“m”下的空白。

建立標籤雲的第一步是選擇一些單詞並確定它們的大小。上面的單詞計數說明了這個步驟。最有可能的是，你會在標籤雲中包含文件中大約100個最常見的單詞。標籤雲中的確切字數將根據顯示美觀度進行調整。單詞在文字中出現的次數將決定單詞的大小。

消除空白是遺傳演算法的一項重要應用。x和y座標、方向指示共同代表了每個單詞。其中x和y座標表明每個單詞在顯示屏上的位置，方向指示表明單詞是水平的還是垂直的。這3個數據項產生的向量長度等於標籤雲中單詞數量的3倍。如果顯示100個單詞，則向量的長度為300個元素。對於空白和重疊文字，基因組將接受罰分。標籤雲不應該有重疊的文字。因此，你需要建立類似於以下內容的計分函式：

[空白畫素數] + ([重疊畫素數] × 100)

遺傳演算法應設法最小化這個計分函式。如果文字重疊，則需要增加係數100。

3.3.2　馬賽克藝術

藝術生成是遺傳演算法的另一個非常常見的例子。編寫計算機藝術的計分函式非常容易。你需要將源影象與遺傳演算法建立的影象進行比較；還要為遺傳演算法提供一組工具，以便它可以生成影象並顯示其模擬的創造力。

人類畫家的工作方式基本相同。顯然，產生影象的最簡單方法是用數碼相機照相，但是，畫家用自己的工具（畫筆和顏料）創造了藝術。對於遺傳演算法，工具是程式語言的圖形命令，計分函式只是將原始影象與遺傳演算法產生的影象進行比較。例如，你可以限制遺傳演算法，讓它僅用少數幾種顏色畫圓。僅使用程式中允許的元素，遺傳演算法將透過演化，產生原始照片的最佳渲染效果。透過這種方式，它展示了模擬的創造力。

用遺傳演算法建立計算機藝術的一個例子是馬賽克，它是由較小影象集合組成的較大影象。主影象包含一個影象網格，較小的影象將放置在每個網格單元中。圖3-5展示了一幅馬賽克。

圖3-5　玄鳳鸚鵡馬賽克

圖3-5描繪了由動物影象生成的玄鳳鸚鵡馬賽克。玄鳳鸚鵡的影象尺寸為2 048畫素×2 048畫素，每張尺寸為32畫素×32畫素的較小動物影象的網格將構成該馬賽克。將這些較小的動物影象的網格覆蓋到較大的影象上，則將形成64×64的網格。（圖3-5經過裁剪，僅展示其中一部分。）選擇一組較小的動物影象放入64×64的網格中，使得網格在整體上可以最佳地呈現出一隻玄鳳鸚鵡的樣子。

每個基因組都是固定長度的陣列，長度等於64×64即4 096位元組。使用計分函式比較生成的馬賽克影象和原始影象之間的差異。一旦得分降到最低，你將擁有與玄鳳鸚鵡非常相似的馬賽克。

3.4　本章小結

遺傳演算法利用種群、計分、交叉和突變來解決實際的程式設計問題。遺傳演算法是在第1章和第2章中學到的概念的具體實現，這些概念與交叉和突變一起工作，可以為下一代提供更好的解。

為了超越定長陣列，第4章將介紹如何演化實際的程式。實際上，遺傳程式設計可以將計算機程式表示為樹狀結構，以便為下一代建立更好的程式。

本文摘自《人工智慧演算法 卷2 受大自然啟發的算》

法是人工智慧技術的核心，大自然是人工智慧演算法的重要靈感來源。本書介紹了受到基因、鳥類、螞蟻、細胞和樹影響的演算法，這些演算法為多種型別的人工智慧場景提供了實際解決方法。全書共10章，涉及種群、交叉和突變、遺傳演算法、物種形成、粒子群最佳化、蟻群最佳化、細胞自動機、人工生命和建模等問題。書中所有演算法均配以具體的數值計算來進行講解，每章都配有程式示例，讀者可以自行嘗試。

本書適合人工智慧入門讀者以及對人工智慧演算法感興趣的讀者閱讀參考。