程序代碼里的“遺傳”

陳凱

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

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

筆者在網(wǎng)絡(luò)上找到了一些有趣的遺傳算法實(shí)施案例，有一些還提供了源代碼下載。

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

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

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

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

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

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

● 簡易遺傳算法流程的實(shí)證

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

1.項(xiàng)目情境設(shè)置

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

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

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

2.初始個體的生成

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

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

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

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

input=open（d：/gene.txt）

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

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

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

output.write（＼n）

為了讓學(xué)習(xí)者有充分的參與感，同時也為了項(xiàng)目實(shí)施的代碼足夠簡單，調(diào)整基因這一環(huán)節(jié)，是由人而不是由程序代碼實(shí)施的，所以程序自身并不向gene.txt文件輸出內(nèi)容。

3.遺傳和變異

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

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

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

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

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

● 更多探索

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