程序代碼里的“遺傳”

陳凱

遺傳算法是一種計算模型，它模擬了達爾文的生物進化理論：針對特定問題構造一個環境及一組“基因”不同的個體，根據優勝劣汰原則，對符合繁衍條件的個體，借助組合交叉、隨機變異等方法，產生出擁有和前輩有相似之處，但又略有變化的“基因”新個體，一代代遺傳變異后，生存下來的個體的“基因”，其實就是問題較優的解答。

● 有趣的遺傳算法演示案例

筆者在網絡上找到了一些有趣的遺傳算法實施案例，有一些還提供了源代碼下載。

1.Flappy Bird（https：//github.com/ssusnic/Machine-Learning-Flappy-Bird）

Flappy Bird的玩法可能大家都不陌生，在這個程序中（如圖1），十只鳥一起以波浪狀飛行試著穿過樹叢縫隙，在Game Over時，表現最好的四只鳥將包含有自己的行為模式的基因略加變異或者交叉組合后傳到下一代。最終，程序生成的鳥的飛行精確性遠超人類。

2.牧場（http：//math.hws.edu/eck/js/genetic-algorithm/GA.html）

牧場上的綠色植物（小方塊）不完全是隨機生長的（如圖2），而是依賴某個群體逐漸往外擴展，剛開始的時候，牧場上的動物（T形）幾乎是隨機行走的，因此要花費很長時間才能遇見食物，隨著這些動物的一代代進化，它們開始變“聰明”了，能越來越快地找到食物。

3.迷宮（https：//code.msdn.microsoft.com/Genetic-algorithm-for-2D-74dd9e10）

從迷宮的某處通往另一處有很多條路（如圖3），哪條路最短呢？這個程序在走廊里設置多處“假墻”來限定行走路徑，那么如何設置假墻才最有效呢？這就要靠一代代的遺傳進化了。

● 簡易遺傳算法流程的實證

雖然上述程序代碼的演示有趣、直觀，但問題是這些遺傳算法實施項目的代碼實在太長，學習者沒有辦法在短時間里讀懂，也就難以體會到遺傳算法的設計要點。筆者希望能有這樣一個例子：①任務情境要簡單，盡量少涉及其他學科的知識；②代碼要盡可能簡單；③項目要有趣直觀；④問題的解答必須是借助算法實現的，而不是靠人力能推演出來；⑤要能給學習者一定的參與性。因為無法在網絡上找到符合以上要求的例子，所以筆者決定自己設計一個項目。該項目是讓某“生物”在迷宮中行動，目標是讓某生物個體盡可能長時間地留在迷宮中（這個目標比快速離開迷宮更有趣）。最后，筆者用Python編寫了半個遺傳算法程序，用來描述遺傳算法的大致實施過程。

1.項目情境設置

該項目名為“一維生物的迷宮”，把二維迷宮變成一維迷宮，是為了簡化環境的構造。迷宮由五種符號構成，分別是“[”“]”“#”“|”“_”，分別表示左邊界、右邊界、一型柵欄、二型柵欄、石板路。當迷宮中的生物從左往右行走時用“c”表示，從右往左行走時用“@”表示。開始時，生物位于迷宮正中，周圍放置若干柵欄，整個迷宮環境可用一個字符串表示：[____#_#_________c_______|_|__ _________]。

可見，生物左側有兩個一型柵欄，右側有兩個二型柵欄、生物碰見柵欄后的行為預設了若干種，大致是跨越并摧毀柵欄、跨越并修好柵欄、被柵欄撞向反方向等。生物的行為可用簡單的字符串替換來實現。例如，可以把“c#”替換成“_c”，表示朝右跨越并摧毀柵欄（柵欄變成了石板路）。又如，可以把“c|”替換成“@|”，表示碰撞柵欄被迫改變方向。大家應該能發現，簡單的行為模式組合在一起，也能有各種復雜的效果。至于生物個體究竟擅長怎樣的行動，這是隨機決定的。

至于生物的行走，也可以用兩個簡單的替換來進行，把“c_”替換成“_c”，它就能向右走，將“_@”替換成“@_”，它就向左走。

2.初始個體的生成

首先生成十個個體，每個個體都由隨機函數得到一串有十位數字的“基因”，每一位數字代表一種行為，生物行動前（被替換字符串）的狀態存放在be數組中，行動后的狀態（替換字符串）存放在af數組中，代碼只是看上去比較長，其實相當簡單，其功能就是按隨機數設置字符串替換規則，走石板路的兩條規則，即把“c_”替換成“_c”，把“_@”替換成“@_”為必選規則，因此不受隨機函數影響（如上頁圖4）。

除了走石板路的兩條規則，其他行動規則按隨機值分成三個檔次，0號到2號行動規則出現機會最少，3號到5號出現較多，6號到9號出現最多。上頁圖5的循環結構，目的就是借助替換規則，讓迷宮中的生物動起來。

代碼運行時，可以看到生物體在迷宮中亂竄（如上頁圖6）。

至于包含有生物個體行動特征的基因，被保存在gene.txt文檔中，該個體行動的效果，則被保存在result.txt文本中，實現方法很簡單，在程序開頭用代碼設置需要讀寫的文件：

input=open（d：/gene.txt）

output=open（d：/result.txt，a）

在每個個體行動結束后，將結果保存到文件中：

output.write（actstr+ +str（steep）+ +str（i））

output.write（＼n）

為了讓學習者有充分的參與感，同時也為了項目實施的代碼足夠簡單，調整基因這一環節，是由人而不是由程序代碼實施的，所以程序自身并不向gene.txt文件輸出內容。

3.遺傳和變異

打開result.txt文件，可以看到數據分為三欄，第一欄是隨機生成的十條基因，第二欄是生物個體在迷宮中行走的步數，第三欄是生物個體到達迷宮邊緣時的時間值，但若時間值達到最大點200，則說明該個體有可能“僵死”在迷宮中。所以優秀的基因是第三欄數字未達到200，而第二欄數字比較大的基因。實際上，真正優秀的基因在迷宮中行動時間可以很長，200這個數值的設置，只是為了程序調試和演示上的方便（如圖7）。endprint

然后，就可以自己制訂遺傳規則了。例如，先手工選出前三條優秀基因，即1959027339、0034334533和2115520901，這三條基因保持原樣繼承到下一代；接著將最優秀的基因首位數字放到末尾，得到基因9590273391繼承到下一代；然后將三條基因每條前兩位數字放到末位后，得到5902733919、3433453300和1552090121，繼承到下一代；最后雜交三條優秀基因，生成三條新的基因繼承到下一代，雜交方法是將第一條基因的末兩位數給第二個基因，第二條基因的末兩位數給第三個基因，第三條基因的末兩位數給第一條基因，然后再取一個字符串中出現最少的數字，替換掉這三條基因的倒數第三位數，得到1959027601、0034334639和2115520633。把新得到的十條基因保存到gene.txt文件中。

這里只是用了比較機械的方法來調整基因。在實際操作時，調整方法可以有很多種。例如，考慮以下基因變化策略：首先選出當前表現最優秀的基因，然后找出在這些基因里出現最多的兩種數字，將某個數置換掉當前基因的前半部分的某一位，將另一個數置換掉當前基因的后半部分的某一位，反復操作后，基因中的數字種類會逐漸變少。這樣的基因變化策略就要比先前的機械方法有效，原因是，為使得后代生存時間更長，某些低效的數字（對應跨越并破壞柵欄的行為）要盡量被剔除掉，但有些數字又是必須存在的（若完全不破壞柵欄，生物個體會僵死在迷宮中）；與此同時，還要想辦法盡可能把對生物個體行走起到阻礙作用的替換規則放到高概率區域。當然，對遺傳算法來說，它并不會真正去想辦法，而只是把表現不佳的基因給踢出局了。

接下來，只要對先前的程序稍做修改，把隨機生成基因的部分，改成從gene.txt文件中讀取基因，就可以再一次運行程序，驗證第二代個體乃至更多代個體的行動效果了（如第34頁圖8）。

可以看出，4376041569這條基因在迷宮中走了197步。為什么這條基因的效果那么好？如何才能得到更好的基因呢？若只看程序運行過程與結果，而不看程序代碼，一時半會兒是無法推斷出來的。所以，對代碼運行后數據的分析，仿佛真的變成了科學研究（如第34頁圖9）。

● 更多探索

以下幾個問題值得深入探索：①本案例所構建的替換規則還是很簡單的，由于幾個替換事件之間不存在因果關系，因而就無法體現出遺傳算法在執行效率上的優勢來，為了使得迷宮環境充分體現出遺傳算法的效率，就要讓不同的替換事件之間呈現樹狀關聯的結構。②本文采用的手動基因編輯方法雖然簡單，但無法處理稍微復雜一些的數據，若要使本項目成為真正有用的遺傳算法，終究還是需要編寫與雜交和變異有關的代碼。③由于替換規則受隨機作用影響，某些優秀基因無法傳到下一代，如能回溯一代或幾代查看基因記錄，就更有利于優秀基因片段的傳承，這就涉及遺傳算法中的精英保留策略。④只要能識別出基因片段的作用，人工干預的基因編輯就必然強過隨機編輯，那么，怎樣將人工的干預和識別，也變得自動化呢？希望有興趣的讀者能將研究繼續下去。endprint