《Java遺傳算法程式設計》—— 1.8 參數

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

雖然所有的遺傳算法都基于同樣的概念，但它們的具體實作可以差别很大。具體實作不同的一種方式，就是通過它們的參數。一個基本的遺傳算法在實作時，至少有幾個參數需要考慮。主要的3個是變異率、種群規模和交叉率。

變異率是在解的染色體中，特定基因将要變異的機率。技術上，遺傳算法的變異率沒有正确的值，但有些變異率将比其他變異率提供好得多的結果。較高的變異率允許種群中有更多的遺傳多樣性，也能有助于算法避免局部最優。然而，變異率過高會導緻每一代之間太多的遺傳變異，導緻失去以前種群中良好的解。

如果變異率太低，算法可能用過長的時間在搜尋空間中移動，妨礙它找到滿意解的能力。變異率過高，也可能延長它找到一個可接受的解所需的時間。雖然高變異率可以幫助遺傳算法避免陷入局部最優解，但如果它被設定得太高，就可能對搜尋産生負面影響。如前所述，這是由于每一代的解被變異的程度很大，在實施變異後，它們實際上随機化了。

為了了解配置良好的變異率非常重要的原因，請考慮兩個二進制編碼的候選方案，“100”和“101”。如果沒有變異，新的解隻能來自交叉。然而，如果交叉我們的解，後代隻有兩個可能的結果，“100”或“101”。這是因為，親代基因組中唯一的差別就是它們的最後一位。如果後代從第一個親代接收其最後一位，将是一個“1”，否則，如果它從第二個親代接收，将是一個“0”。如果該算法需要找到一個替代解，就需要變異現有的解，得到基因庫中沒有的新基因資訊。

變異率應設定為一個值，該值允許足夠的多樣性，以防止算法停滞不前，但這個值又不是太高，不會導緻該算法失去以前的群體中有價值的遺傳資訊。這種平衡取決于要解決的問題的性質。

種群規模就是遺傳算法中任意一代種群的個體數。較大的種群規模，算法可以在搜尋空間中取樣更多。這将有助于将它導向更準确、全局最優解的方向。小的種群規模通常會導緻該算法在搜尋空間的局部最優區域發現不太理想的解，但是它們每一代需要的計算資源較少。

這裡一樣，就像變異率，為了遺傳算法的最佳表現，需要找到一種平衡。同樣，根據要解決的問題的性質，需要改變種群的規模。為了找到最佳解，山頭很多的搜尋空間通常需要較大的種群規模。有趣的是，選擇種群規模時有一個點，超過這個點，增加規模也不會為算法提供多少改進以找到精度更好的解。相反，由于需要額外的計算來處理增加的個體，它會讓執行變慢。在這個轉折點附近的種群規模，通常提供了資源和結果之間的最佳平衡。

應用交叉的頻率也對遺傳算法的整體表現有影響。更改交叉率調整了種群中的解接受交叉算子的機會。高交叉率在交叉階段會産生許多新的、潛在優越的解。較低的交叉率有助于保持較适應個體的基因資訊在下一代中不受破壞。交叉率通常應設定為合理的高低，既促進新解的搜尋，又讓種群的一小部分保持不受影響，進入下一代。