《Java遺傳算法程式設計》—— 2.4 基本實作

本節書摘來異步社群《java遺傳算法程式設計》一書中的第2章，第2.4節，作者： 【英】lee jacobson（雅各布森） , 【美】burak kanber（坎貝爾），更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

為了消除所有不必要的細節，保持最初的實作容易嘗試，本書中介紹的第一個遺傳算法将是簡單的二進制遺傳算法。

二進制遺傳算法比較容易實作，對于解決許多種優化問題，它可能是非常有效的工具。你可能還記得第1章提到，二進制遺傳算法是由holland（1975）提出的原創的遺傳算法。

首先，讓我們回顧一下“全一”問題，它是可以用二進制遺傳算法來解決的一個非常基本的問題。

該問題不是很有趣，但作為一個簡單的問題，它的作用是強調所涉及的基本技術。顧名思義，該問題就是發現全部由1構成的字元串。是以，對于長度為5的字元串，最優解是“11111”。

既然有了要解決的問題，讓我們繼續研究實作。我們要做的第一件事就是建立遺傳算法參數。如前所述，這3個主要參數是種群規模、變異率和交叉率。本章中，我們還引入了一個名為“精英主義（elitism）”的概念，并将它作為遺傳算法的參數之一。

首先，建立一個名為geneticalgorithm的類。如果你使用eclipse，可以通過選擇file new class來做到這一點。在本書中，我們選擇用對應的章名來命名包，是以我們會在包“chapter2”中工作。

這個geneticalgorithm類将包含遺傳算法本身的操作所需的方法和變量。例如，這個類包括處理交叉、變異、适應度評估和終止條件檢查的邏輯。該類建立後，添加一個構造方法，它接受4個參數：種群規模、變異率、交叉率和精英成員數。

傳入所需的參數，這個構造方法将利用所需的配置，建立geneticalgorithm類的新執行個體。

現在，我們應該建立引導類：回想一下，每章都需要一個引導類，用于初始化遺傳算法，并作為應用程式的起點。将該類命名為“allonesga”，并定義一個main方法：

暫時，我們就用一些典型的參數值：種群規模=100，變異率=0.01，交叉率=0.95，精英計數為 0（實際上暫且禁用它）。在本章結束，當你已完成了以上的内容時，可以嘗試更改這些參數，看看它們如何影響算法的表現。

下一步就是初始化一個潛在解構成的種群。這通常是随機的，但偶爾也可能采用系統化的方法會更好，可以利用對搜尋空間的已知資訊來初始化種群。在這個例子中，種群中每個個體将随機初始化。我們可以為染色體的每個基因随機選擇1或0，實作這一點。

初始化種群之前，我們需要建立兩個類，一個管理并建立種群，另一個管理和建立種群的個體。這此類包含一些方法，例如擷取個體适應度，或在種群中取得最适應的個體。

首先，讓我們從建立individual類開始。請注意，為了節省篇幅，我們省略了所有注釋和方法的文檔注釋塊！你可以在附帶的eclipse項目中找到該類的完全注釋版本。

individual類代表一個候選解，主要負責存儲和操作一條染色體。請注意，individual類也有兩個構造方法。一個構造方法接受一個整數（代表染色體的長度），在初始化對象時将建立一條随機的染色體。另一個構造方法接受一個整數數組，用它作為染色體。

除了管理individual的染色體，它也追蹤個體的适應度值，也知道如何将自己列印為一個字元串。

下一步驟是建立population類，它提供管理群體中一組個體所需的功能。

像往常一樣，注釋和文檔注釋塊在這一章中已經省略了，一定要看看eclipse項目，了解更多背景！

population類相當簡單，它的主要功能是儲存由個體構成的一個數組，能夠通過類方法友善地通路。例如getfittest()和setindividual()這樣的方法，能夠通路并更新種群中的個體。除了儲存個體，它也存儲了種群的總體适應度，在稍後實作選擇方法時，這很重要。

既然我們有了種群和個體類，就可以在<code>geneticalgorithm</code>類中将它們執行個體化。要做到這一點，隻需建立一個名為“initpopulation”方法，放在geneticalgorithm類中的任意位置。

既然有了population和individual類，我們就可以回到allonesga類，開始使用initpopulation方法。回想一下，allonesga類隻有一個main方法，而且它代表本章前面介紹的僞代碼。

在main方法中初始化種群時，還需要指定個體染色體的長度，這裡，我們取長度為50：

在評估階段，種群中的每個個體都計算其适應度值，并存儲以便将來使用。為了計算個體的适應度，我們使用所謂的“适應度函數”。

遺傳算法通過選擇來引導進化過程，得到更好的個體。因為正是适應度函數使得這種選擇成為可能，是以适應度函數應該設計良好，提供個體适應度的準确值，這很重要。如果适應度函數設計得不夠好，可能需要更長的時間才能找到滿足的最低标準的解，也可能根本找不到可以接受的解。

适應度函數往往是遺傳算法中需要最多計算的元件。正因為如此，适應度函數做好優化，有助于預防瓶頸，讓算法高效地運作。這很重要。

每個特定的優化問題，都需要一個特别開發的适應度函數。在“全一”問題的例子中，适應度函數相當簡單，隻需計算個體染色體中1的數量。

現在為geneticalgorithm類添加一個calcfitness方法。該方法将計算染色體中1的個數，然後除以染色體的長度，使輸出規格化，在0和1之間。你可以在geneticalgorithm類的任意位置添加此方法，是以下面省略了其周圍的代碼：

我們也需要一個簡單的輔助方法，周遊每個個體并評估它們（即對每個個體調用calcfitness）。我們稱這個方法為evalpopulation，并将它也添加到geneticalgorithm類中。它看起來應該像下面這樣，同樣可以将它添加在任何位置：

此時，geneticalgorithm類應該具有以下方法。簡潔起見，我們省略了函數體，隻是顯示類的折疊視圖：

如果缺少其中任何屬性或方法，請現在就回去實作它們。我們還有4個方法要在geneticalgorithm類中實作：isterminationconditionmet、selectparent、crossoverpopulation和mutatepopulation。

接下來需要檢查終止條件是否已經滿足。有許多不同類型的終止條件。有時可能知道最佳解是什麼（更确切地說，是可能知道最佳解的适應度值），在這種情況下，我們可以直接檢查正确解。然而，并非總是能夠知道最佳解的适應度是什麼，是以我們可以在解變得“足夠好”時終止，即解超過某個适應度門檻值。如果算法運作了太長時間（太多世代），我們也可以終止，或者可以結合一些因素，決定終止該算法。

由于“全一”問題很簡單，事實上，我們知道正确的适應度應該是1，在這種情況下，找到正确的解就終止，這是合理的。但情況并非總是這樣！事實上，很少會這樣。但我們很幸運，這是一個簡單的問題。

首先，我們必須建構一個函數，檢查終止條件是否已發生。我們可以在geneticalgorithm類中添加如下代碼來實作這一點。代碼添加在任意位置，和往常一樣，為了簡潔，我們省略了其他的類。

上述方法檢查種群中的每個個體，如果種群中任何個體的适應度為1，就傳回true（這表明，我們已經找到了一個終止條件，可以停止）。

既然已經建立了終止條件，就可以在allonesga類的主引導方法中添加一個循環，并使用新添加的終止檢查作為其循環條件。如果終止檢查傳回true，遺傳算法将停止循環，并傳回其結果。

為了建立進化循環，将執行類allonesga的main方法修改為如下所示。下面代碼片段的前兩行已經在main方法中。通過添加這段代碼，我們将繼續實作本章開頭展示的僞代碼：回憶一下，main方法是遺傳算法僞代碼的具體表現。下面是main方法現在的樣子：

我們添加了一個進化循環，檢查isterminationconditionmet的輸出。main方法的新内容還包括在循環之前和循環之内添加了evalpopulation調用，用于追蹤世代數目的generation變量，以及調試消息，以便讓你知道每一代的最佳解是怎樣的。

我們還增加了程式結束時的代碼：循環退出時，列印關于最終解的一些資訊。

然而，現在我們的遺傳算法會運作，但不會永遠進化！我們将陷入一個無限循環中，除非我們很幸運，随機産生的一個個體恰好是“全一”。你可以點選eclipse中的“run”按鈕，直接看到這樣的行為。相同的解将一遍又一遍地送出，循環永遠不會結束。你不得不點選eclipse控制台上方的“terminate”按鈕，強制程式停止。

為了繼續建立我們的遺傳算法，需要實作另外兩個概念：交叉和變異。通過随機變異和最适者生存，這些概念實際上推動了種群向前進化。

現在，是時候開始運用變異和交叉來進化種群了。交叉算子是一個過程，在這個過程中，種群中的個體交換它們的遺傳資訊，希望建立一個新的個體，包含親代基因組中最好的部分。

在交叉過程中，考慮種群中每個個體是否參與交叉，這時使用交叉率參數。通過比較交叉率和一個随機數，我們可以決定個體是應該參與交叉，還是應該直加入下一個種群，不受交叉影響。如果選擇了一個個體參與交叉，就需要找到第二個親代。要找到第二個親代，我們需要在多種可能的選擇方法中挑一種。