遺傳算法 python_Python實作入門級遺傳算法

關于遺傳算法，網上已經有很多相關的入門級介紹了，這裡稍微推薦幾個：

關于遺傳算法的代碼網上有很多，http://www.pudn.com/search_db.asp?keyword=%D2%C5%B4%AB%CB%E3%B7%A8，不過更多的都是用Matlab以及常見的c語言編寫的，用Python的并不多，而且pudn網站是需要提供代碼注冊的，本人也并未注冊，于是處于自己的喜好，用Python對此進行了實作。

(建議看完上述的基本介紹再往下看實作方法，一些基本屬于下面不多做解釋)

代碼部分可見https://coding.net/u/zealseeker/p/geneticAlgorithm/git，雖然一直在用csdn的代碼托管，不過最近發現coding.net也是個很不錯的托管代碼地方，而且它有WebIDE，可以線上編輯以及調試，是以就嘗試了一番。

改代碼分兩個類，基因類和染色體類(我用基因組geneome表示)，基因類包含基因的序列(一般我們用0或1表示)以及長度，适應值函數(評價改基因的好壞标準)以及與之相關的基因突變率。上述的對遺傳算法介紹裡都僅僅講了怎麼突變，卻沒怎麼提該不該突變。一般現實中基因突變是有一定機率的，是以我預設了一下突變機率函數,mutaterate，而且該函數取決于最優适應值函數以及最低适應值函數，盡管這種機率設定不見得合乎生理，不過為了更快速得到結果加上本身我們也當然希望盡可能讓不好的基因多突變，是以這樣設定。使用者也可以将consider_rate設為False，那麼就必然突變。

而基因組類就包含了遺傳的幾個常見過程，交叉重組、突變(其實就是讓每個候選基因進行單點突變)以及選擇(即決定怎麼樣基因被保留)，這裡面本人也設定了兩種方案，一種是大多數博文提到的賭盤選擇法，但是本人發現對于适應值函數差異并不大的情況，用賭盤選擇法效果并不好，比如10分于12分對應比例即45%與55%，10分被保留的機率仍然很大，相比之下我們可能會特别想追求12分，于是本人加了一種看似并不合理的方法，即隻保留适應值函數高的基因(被遺傳到下一代)。

在test.py的預設子產品中進行測試發現，如果用随機模型(賭盤選擇)法，即使遺傳100次，也就隻有500-600的打分(滿分10*75=750)，比如下面這種情況，可見随機性還較大

[0, 0, 1, 1, 1, 1, 1, 1, 0, 0] 38

[1, 1, 1, 1, 1, 0, 0, 1, 1, 1] 57

[1, 0, 0, 0, 1, 1, 1, 1, 1, 0] 21

[1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 56

[0, 1, 1, 1, 0, 0, 0, 0, 0, 0] 59

[0, 1, 1, 1, 0, 0, 0, 0, 0, 0] 59

[1, 1, 1, 1, 0, 1, 0, 0, 0, 0] 56

[0, 1, 1, 1, 0, 0, 0, 0, 0, 0] 59

[1, 1, 1, 1, 1, 1, 0, 0, 0, 1] 61

[1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 56

522

而如果使用适應值最優的遺傳方法，那麼10次遺傳後則有600-750之間，100次以後大多數都是750分。

這可能跟基因的長度太短有關，這裡就不多做測試了，主要還是以學習了解為主。可能将來能夠用上，如果當适應值打分函數換成别的需要的找最優化的函數或算法後，則理論上就能找到接近最高的序列