文章目錄
- 為何采用遺傳算法
- 哪些問題適合用遺傳算法解決
- 遺傳算法基本術語
- 一般遺傳算法的過程
- 基本遺傳算法的偽代碼
為何采用遺傳算法
遺傳算法是機器學習的子集。在實踐中，遺傳算法通常不是用來解決單一的、特定問題的最好算法。對任何一個問題，幾乎總有更好的、更有針對性的解決方案！那么何必麻煩呢？
遺傳算法是一個極好的多用途工具，可以應用于許多不同類型的問題。這是瑞士軍刀與合適的螺絲刀之間的差異。如果任務是擰緊300顆螺絲，你會跳起來找螺絲刀。但如果任務是擰幾顆螺絲、割開一些布、在皮革上打一個孔，然后打開一瓶冰蘇打水獎勵自己的努力工作，那么瑞士軍刀是更好的選擇。
此外，遺傳算法是整體研究機器學習的不錯入門。如果機器學習是一座冰山，遺傳算法就是尖端的一部分。遺傳算法有趣、令人興奮且充滿創新。遺傳算法的模型基于自然生物過程，建立了計算世界和自然世界之間的連接。編寫第一個遺傳算法，觀看從混亂和隨機中出現的驚人結果，讓人嘆為觀止。
機器學習冰山頂端的其他研究領域也同樣令人興奮，但它們往往關注的問題更狹窄，更難以理解。遺傳算法則不然，它很容易理解，是有趣的實現，它們引入了所有機器學習技術都會使用的許多概念。
哪些問題適合用遺傳算法解決
下面是一個問題特征列表，這類問題是采用遺傳算法的良好候選者：
- 如果問題足夠困難，難以寫代碼來解決；
- 如果人不知道如何解決這個問題；
- 如果問題是不斷變化的；
- 如果搜索每個可能解是不可行的；
- 如果可以接受“足夠好”的解。
遺傳算法基本術語
遺傳算法建立在生物進化的概念上的。
- 種群：這就是一個候選解（個體）集合，可以有變異和交叉這樣的遺傳操作應用于它們。
- 候選解（個體）：給定問題的一個可能的解。
- 基因：組成染色體的不可分割的構建塊。經典的基因包含0或1。
- 染色體：染色體是一串基因。染色體定義了一個特定的候選解（個體）。用二進制編碼一個典型的染色體可能包含“01101011”這樣的內容。
- 變異：一個過程，其中候選解中的基因被隨機改變，以創建新的性狀。
- 交叉：其中染色體被組合以創建新的候選解決方案的方法。這有時稱為重組。
- 選擇：這是選擇的候選解，繁殖下一代解的技術。
- 適應度：一個評分，衡量候選解適合給定問題的程度。
一般遺傳算法的過程
- 遺傳算法開始，初始化候選解（個體）的種群。這通常是隨機提供整個搜索空間的均勻覆蓋。涉及參數有種群規模。
- 接下來，通過為種群中的每個個體分配一個適應度值，對種群進行評估。在這個階段，常常要注意當前最優解，以及種群的平均適應度。
- 評估后，根據終止條件集，該算法決定它是否應該終止搜索。通常這是因為該算法已達到指定的世代數量，或已經找到適當的解。
- 如果終止條件最終滿足，算法會跳出循環，通常向用戶返回最后的搜索結果。
- 一些典型的終止條件是：
- 到達世代的最大數目;
- 超過分配給它的時間;
- 發現一個滿足所需條件的解;
- 該算法已經達到了一個穩定階段。
- 如果終止條件不滿足，種群經過一個選擇階段，基于適應度評分，從種群中選擇個體。適應度越高，個體就更有機會被選擇。選擇目的為下一步“交叉和變異”作準備。選擇方法有：
- 輪盤賭選擇（也稱為適應度比例選擇）。個體的適應度越高，在輪盤上占據的空間就越多，也就是選中的概率越大。（參考第2章）
- 錦標賽選擇。隨機從種群中選擇一些個體，進入錦標賽。以通過比較這些個體的適應度值來競爭，然后選擇適應度最高的個體作為親代。（參考第3章）
- 下一階段對選擇的個體應用交叉和變異。這個階段為下一代創建新個體。如果是種群中的精英（種群中適應度最靠前的一小部分個體），直接跳過進入下一代。涉及參數有交叉率、變異率。交叉和變異后，確保仍然得到一個有效解（合格的個體）。
- 交叉方法有：
- 均勻交叉（uniform crossover）。后代的每個基因都有50%的機會來自第一個親代或其第二個親代。（參考第2章）
- 單點交叉。隨機選擇基因組中的一個位置，確定哪些基因來自于哪個親代。交叉位置之前的遺傳信息來自于親代1，之后的遺傳信息來自于親代2。（參考第3章）
- 排序交叉。在這種交叉方法中，第一個親代染色體的一個子集被選中。然后該子集被添加到后代染色體的相同位置。下一步是將第二個親代的遺傳信息添加到后代的染色體中。通常從所選子集的結束位置開始，然后包括親代2的每個基因，只要后代染色體中還沒有該基因。（參考第4章）
- 交叉方法有：
- 此時新種群返回到評估步驟（步驟2），過程重新開始。我們稱這種循環的每一圈為一個世代。
基本遺傳算法的偽代碼
generation = 0;
population[generation] = initializePopulation(populationSize);
evaluatePopulation(population[generation]);
while isTerminationConditionMet() == false doparents = selectParents(population[generation]);population[generation+1] = crossover(parents);population[generation+1] = mutate(population[generation+1]);evaluatePopulation(population[generation]);generation++;
End loop;
)
