陳凱

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

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

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

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

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

2.牧場(chǎng)（http：//math.hws.edu/eck/js/genetic-algorithm/GA.html）

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

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

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

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

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

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

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

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

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

2.初始個(gè)體的生成

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

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

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

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

input=open（d：/gene.txt）

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

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

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

output.write（＼n）

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

3.遺傳和變異

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

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

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

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

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

● 更多探索

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