今天我們一起來搞雞，哦不，來探討雞兔同籠的問題。

雞兔同籠是中國古代的數(shù)學名題之一。大約在1500年前，《孫子算經(jīng)》中就記載了這個有趣的問題。書中是這樣敘述的：
今有雉兔同籠，上有三十五頭，下有九十四足，問雉兔各幾何？

常規(guī)的解法這里就不討論了，百度百科上面已經(jīng)說得非常全了，今天我想嘗試一下利用遺傳算法的思路來解這個問題。是的，你們都被標題騙了，遺傳算法才是今天的真正的主角，車門已經(jīng)焊死，請乘客不要強行跳窗下車。

先替這個算法作個自我介紹，來自百度百科：

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。該算法通過數(shù)學的方式,利用計算機仿真運算,將問題的求解過程轉(zhuǎn)換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為復(fù)雜的組合優(yōu)化問題時,相對一些常規(guī)的優(yōu)化算法,通常能夠較快地獲得較好的優(yōu)化結(jié)果.

劃重點，遺傳算法是一種求解最優(yōu)解的方法。我們這個雞兔同籠問題其實也可以看作是求最優(yōu)解的問題，所以應(yīng)用遺傳算法理論上也是可行的，只不過遺傳算法這里算是牛刀，用來殺雞確是大材小用了。

下面繼續(xù)來簡單看一下遺傳算法的計算過程：

1、選擇初始生命種群，也就是用于進化的初始染色體們
2、循環(huán)評價種群中的個體適應(yīng)度，這個適應(yīng)度可以簡單理解成染色體的優(yōu)秀程度，所以這一步就是進化論里的優(yōu)勝劣汰，越優(yōu)秀的染色體越容易保留下來，就是概率更高，注意，這里只是概率高，并不表示只會淘汰染色體里最差的，如果每一步都選最優(yōu)染色體，這就是典型的貪心，容易限入局部最優(yōu)，而非全局最優(yōu)。
3、改變種群，主要手段是交叉和變異，交叉就是交配，大家為了更美好的下一代交換一下祖?zhèn)魅旧w。變異就是基因突變，我們用上帝之手讓本來染色體上的基因發(fā)生一點小小的改變。
4、重復(fù)2和3，直到得到結(jié)果或者超過最大遺傳代數(shù)。

很簡單，就是在不斷的挑選染色體，然后改變?nèi)旧w，直到發(fā)展出我們需要的染色體為止。
這里面有一些設(shè)計算法時需要注意的地方，比如優(yōu)秀的基因只是被保留的概率比不優(yōu)秀的概率高，不是絕對要被保留，交配的概率需要大，這個好理解，如果完全不交配，那就不會產(chǎn)生比當前更好的染色體，變異的概率要小，因為如果變異概率過大，每次都產(chǎn)生我們不可預(yù)測的值，可能就變成隨機了，效果會變差。

那下面就讓小雞和小兔來給我們演示一下遺傳算法的工作過程。

選擇初始種群

先確定種群，也就是染色體，既然要求雞和兔子的個數(shù)，那就以雞和兔子的數(shù)量作為基因好了，比如這樣{10只雞，10只兔子}，是攜帶兩個基因的染色體，不過這樣的數(shù)據(jù)計算機可不太明白，我們要說機話，將其轉(zhuǎn)化成二進制序列，讓電腦能夠更方便的計算。從題目中我們可以推導出雞最多不超過35只，兔子最多不超過23只，那就給雞分配6個二進制位，給兔子分配5個二進制位，{10只雞，10只兔子}可以表示成{001010，01010}，然后連起來，變成00101001010，這就是我們設(shè)計的一條基因序列了。那么我們再多隨機幾條出來，比如說我們得到下面的初始染色體：

00101001010, 01011101010, 00101001100，重新說人話就是{10，10}，{23，10}， {10，12}

評價個體適應(yīng)度

接下來確定如何判斷染色體攜帶基因的好壞呢，上帝現(xiàn)在隨便決定一下，給每個染色體計算一下頭和腳的數(shù)量，如果頭大于35或者腳大于94了，就認為是最差的染色體，除此之外的，越接近35和94的更優(yōu)秀，如果兩兩相比，各有一大一小，那認為同樣優(yōu)秀。那上面的按照這個原則排個序就是

{23,10} > {10,12} > {10,10}

好，現(xiàn)在上帝決定把{10，10}淘汰掉

交叉和變異

接下來上帝決定讓留下的兩位交叉一下，過程就是彼此交換一下基因，但不變異了，這時得到新的種群

{23，10}， {10，12}, {23，12}， {10，10}

上帝換個坐姿，再來一次

我們回過頭再來評價一下，oh my god！{23，12}這個染色體竟然完美符合我們對優(yōu)秀染色體的判斷標準，我們的結(jié)果就得到了。

上面當然是我站在上帝視角精心設(shè)計的基因，才能在這么短的時間內(nèi)得到結(jié)果，以上這些都是我YY出來的，并沒有實驗支撐，模擬這樣的過程只是想深入?出的說明白這個算法。筆者先在這里挖個坑，后續(xù)會親自寫代碼作實驗，補充一下實驗過程及結(jié)果。

遺傳算法已經(jīng)在求解旅行商問題、 背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用，旅行商問題就是最優(yōu)路徑問題，而筆者所在的公司是開發(fā)物流系統(tǒng)的，也有規(guī)劃物流路徑，優(yōu)化貨物裝箱之類的需求，所以再次看到這個算法的時候勾起了學習的欲望，希望有一天能在公司的項目里落地。