Perl用于實(shí)現(xiàn)遺傳算法

addwin

Perl用于實(shí)現(xiàn)遺傳算法

　

[編者的話(huà)]

遺傳算法在生物信息學(xué)尤其是蛋白結(jié)構(gòu)預(yù)測(cè)與分析中有重要應(yīng)用：Perl是現(xiàn)在生物信息學(xué)界中很熱門(mén)的一種編程語(yǔ)言（我們?cè)谝郧皩?zhuān)題中曾做過(guò)專(zhuān)門(mén)介紹）。Perl的長(zhǎng)處是文本分析，那么它在編寫(xiě)算法上是否能一樣表現(xiàn)優(yōu)異呢，它能不能做這方面的工作呢，別急，且看下文：）

　

創(chuàng)建您自己的達(dá)爾文式的繁殖基礎(chǔ)

Teodor Zlatanov (tzz@iglou.com)
程序員，Gold Software Systems
2001年8月

遺傳編程建立在達(dá)爾文適者生存的自然選擇法則的基礎(chǔ)之上，利用變異和復(fù)制來(lái)生成算法，該算法可創(chuàng)建不斷改進(jìn)的計(jì)算機(jī)程序。在本專(zhuān)欄里，您將開(kāi)始了解用淺顯的術(shù)語(yǔ)表述的遺傳算法。Ted 給出了幾種特定的任務(wù)的 Perl 實(shí)現(xiàn)，您可以用于廣泛的用途。為了示范遺傳算法，Ted 繁殖了一些數(shù)字和字母，應(yīng)用于公式以測(cè)試這些數(shù)字的適應(yīng)性，而繁殖的字母則形成了英語(yǔ)單詞。

如果您的機(jī)器上已經(jīng)安裝了Perl 5.005或者更高的版本，您可以運(yùn)行一下文章中的例子。您的系統(tǒng)最好應(yīng)該是安裝了最近的（2000年或者更遲些）主流的 UNIX（Linux，Solaris，BSD），但其它種類(lèi)的操作系統(tǒng)可能也可以。文中的例子可能可以在更老的版本的Perl、UNIX以及其它操作系統(tǒng)下運(yùn)行，但是如果不行的話(huà)，讀者應(yīng)當(dāng)把它看作是一次練習(xí)來(lái)解決。

歷史
進(jìn)入20世紀(jì)以來(lái)，在速度和影響范圍方面遺傳學(xué)的發(fā)展只有電子學(xué)和計(jì)算機(jī)科學(xué)能與之相比。遺傳算法是20世紀(jì)出現(xiàn)的最令人感興趣的算法之一，這一說(shuō)法是恰當(dāng)?shù)摹?

遺傳算法（以及普遍意義上的進(jìn)化算法）出現(xiàn)在20世紀(jì)60年代早期，并在計(jì)算機(jī)科學(xué)的確定性和非確定性算法之間占據(jù)了一席之位。本質(zhì)上，遺傳算法具有如同您所希望的那樣的確定性，意味著用戶(hù)可以決定重復(fù)次數(shù)和結(jié)束條件。它模擬達(dá)爾文的自然選擇，還有變異，把“適應(yīng)性”（正如適用于個(gè)體的公式所決定的那樣）作為主要因素選擇生存繁衍和變異的個(gè)體。

其它的進(jìn)化算法試圖模擬拉馬克的進(jìn)化論，在他看來(lái)，行為是一種生存的機(jī)制，可以在兩代之間傳遞，甚至有一些進(jìn)化程序是出于某種目的而自然出現(xiàn)的。以上這些都不在本文的論述范圍之內(nèi)。

Perl用于實(shí)現(xiàn)遺傳算法的主要缺點(diǎn)在于速度慢。由于遺傳算法的計(jì)算需要，用C語(yǔ)言或其它低級(jí)的預(yù)編譯語(yǔ)言來(lái)實(shí)現(xiàn)效率會(huì)更高。本文展示的Perl例程不如其C語(yǔ)言的等價(jià)程序快，但是可以使您明白遺傳算法是如何工作的，況且，對(duì)于一些問(wèn)題來(lái)說(shuō)，已經(jīng)夠快了。

那么什么是遺傳算法呢？
遺傳算法是如此簡(jiǎn)單，任何人只要用高中時(shí)學(xué)過(guò)的生物術(shù)語(yǔ)就可以理解。以一群個(gè)體為例，它們都有自己的DNA。然后衡量每一個(gè)個(gè)體的適應(yīng)性（把它看作是適用于個(gè)體的DNA的官能來(lái)衡量），并且使那些更適應(yīng)的個(gè)體更有可能繁衍。而最不適應(yīng)的個(gè)體將會(huì)被滅絕。每個(gè)幸存者都會(huì)有機(jī)會(huì)繁衍（重要的是任何幸存者都可能會(huì)繁衍，如果不太適應(yīng)的話(huà)，僅僅是降低了可能性）。合并雙親的DNA，對(duì)合并后的DNA應(yīng)用隨機(jī)變異以模擬繁衍。理論上說(shuō)來(lái)，新的個(gè)體是和雙親一樣適應(yīng)的，由于變異或增或減會(huì)有些微小的變化。然后循環(huán)會(huì)周而復(fù)始。

雖然，有許多變化的因素在影響遺傳算法，包括人群大小、代（算法的迭代）、合并方法、適應(yīng)性函數(shù)，適應(yīng)性將如何影響繁衍的可能性，以及發(fā)生了多少變異。

該算法也存在一些缺陷。如果把應(yīng)用于DNA的適應(yīng)性官能看成是一系列的二進(jìn)制位，效果最好。換句話(huà)說(shuō)，如果DNA是一系列二進(jìn)制的選項(xiàng)，是還是不是。藍(lán)眼睛？黑眼睛？紅頭發(fā)？黑頭發(fā)？合并雙親的DNA和隨后的變異應(yīng)當(dāng)不允許特定的一些位組合出現(xiàn)，因?yàn)榈贸龅腄NA可能不再是最初的問(wèn)題的有效解答。請(qǐng)記住，所謂“DNA”僅僅是適應(yīng)性公式純數(shù)學(xué)的一種解答。該公式中用到的一些值可能是無(wú)效的—例如，除數(shù)為零。

另外，遺傳算法不受時(shí)間限制。由您來(lái)挑選代的數(shù)目。您可以確定某個(gè)目標(biāo) — 比方說(shuō)，“找一個(gè)適應(yīng)性為0.99999 的個(gè)體”，找到后停止。但是，結(jié)果是算法永遠(yuǎn)也不會(huì)結(jié)束，因?yàn)樗鼪](méi)找到那個(gè)個(gè)體。如果您制定了不切實(shí)際的目標(biāo)，或者代的數(shù)目太小，就會(huì)出現(xiàn)問(wèn)題。嘗試、出錯(cuò)，以及深入的思考是解決這個(gè)問(wèn)題的最佳途徑。

適應(yīng)性公式返回的是介于0和1之間的一個(gè)浮點(diǎn)數(shù)。您也可以使用其它的范圍的數(shù)，但是我的經(jīng)驗(yàn)告訴我，浮點(diǎn)數(shù)是最有效的。比如，如果出于優(yōu)選的考慮，您希望適應(yīng)性是一個(gè)7位的整型數(shù)，您想要的范圍就是0到32767之間。

當(dāng)然，把優(yōu)選推遲到您認(rèn)為有需要的時(shí)候，這是一個(gè)好主意，那么您在開(kāi)始的時(shí)候，最起碼得有一個(gè)簡(jiǎn)單的適應(yīng)性公式。適應(yīng)性公式是遺傳算法中最常用的函數(shù)，（它將要被調(diào)用的次數(shù)是（人群大�。﹛（代的數(shù)目）次），所以您應(yīng)當(dāng)盡可能的使它簡(jiǎn)單、快速。

有三種“好”的可以退出遺傳算法的方式！首先，當(dāng) DNA 池里不再有變化時(shí)，您就可以決定退出。事實(shí)上，這是個(gè)棘手的測(cè)試，只要您能夠把DNA表示為字符串，就可以利用一個(gè)確定串之間的差異的CPAN模塊。第二，如果達(dá)到了適應(yīng)性的目標(biāo)，您也可以退出。除非對(duì)適應(yīng)性公式非常了解（在這種情形下，無(wú)論如何，您都可能不再需要遺傳算法了），設(shè)定適應(yīng)性目標(biāo)的結(jié)果，或者是導(dǎo)致無(wú)窮循環(huán)，或者是得到一個(gè)僅僅是“足夠好”的個(gè)體。第三，在迭代了一定的次數(shù)或者說(shuō)經(jīng)歷了一定數(shù)目的“代”后，您也可以退出。

在實(shí)踐中，這三種方式（或者至少是第二種和第三種）都會(huì)被用于控制遺傳算法。只要經(jīng)過(guò)為數(shù)不多的測(cè)試，可能是10次，也可能是20次，您就會(huì)清楚的知道算法匯集需要多長(zhǎng)時(shí)間，以及您想要的適應(yīng)性是什么樣子的。

一個(gè)簡(jiǎn)單的例子
清單 1 里的代碼把一個(gè)字節(jié)看作是DNA（它的值介于0和255之間，8位）。對(duì)每個(gè)新個(gè)體應(yīng)用適應(yīng)性公式一次，用表示DNA的字節(jié)所具有的數(shù)值，去除以256。這樣適應(yīng)性公式總是會(huì)返回一個(gè)介于0和255/256之間的數(shù)值，因此，它永遠(yuǎn)也不會(huì)等于1。那么，您認(rèn)為最適應(yīng)的DNA應(yīng)當(dāng)是多少呢？

清單1.繁殖字節(jié)以測(cè)試其適應(yīng)性

numbers.pl source


清單1里有幾件非常有趣的事情。它的主循環(huán)位于程序的開(kāi)始部分，您應(yīng)當(dāng)弄懂所有的程序片，以及它們是如何共同作用于人群的（既然這些部分是相互獨(dú)立的，因此我們還可以在下面的例子中重復(fù)使用）。您可以運(yùn)行清單1，程序文件為numbers.pl。

通過(guò)把map()堆棧到grep()的上部，我們?cè)趕elect_parents()函數(shù)里建立了weights數(shù)組。雖然我們本來(lái)可以把它寫(xiě)成循環(huán)，但是長(zhǎng)度只有一行的解決方案要清楚得多，并且不會(huì)顯著降低程序運(yùn)行的速度。

清單2.map和grep堆棧

my @weights = map { $_->;{fitness} } grep { $_->;{survived} } @$population;


$population數(shù)組引用是間接引用。那么，只有帶“survived”域的數(shù)組元素（在前面由survive()函數(shù)設(shè)定的）通過(guò)grep。然后這些幸存者被蒸餾成代表其適應(yīng)性的數(shù)字，并存入weights數(shù)組里該幸存者所對(duì)應(yīng)的位置。

取大小為256的人群，原因是這樣便于把個(gè)體都初始化成一個(gè)與其序號(hào)相等的數(shù)字。您可以自由選擇不同的人群大小開(kāi)始。

大于1%的變異率使得適應(yīng)性的最大值和最小值劇烈波動(dòng)。人群絕不可能穩(wěn)定在高適應(yīng)性。變異率低導(dǎo)致了需要更多的時(shí)間人群才能整體上達(dá)到高適應(yīng)性。最后，對(duì)于我們討論的人群大小而言，1%恰好合適。

繁衍選擇算法會(huì)查找weights數(shù)組，選擇第一個(gè)雙親 — 其實(shí)，每個(gè)個(gè)體都有可能成為雙親，但是雙親位置的數(shù)目是確定的。另一個(gè)雙親是隨機(jī)地從雙親人群中挑選的。為什么呢？噢，本來(lái)我們可以在weights數(shù)組里把另外一個(gè)雙親也確定下來(lái)，但是，這樣我們可以確保每個(gè)可以成為雙親的個(gè)體都有可能參與繁衍過(guò)程。

實(shí)際上實(shí)現(xiàn)繁殖的是一個(gè)隨機(jī)的8位位掩碼。我們只把這個(gè)位掩碼和第一個(gè)雙親的DNA（請(qǐng)記住，它只是一個(gè)字節(jié)）作AND運(yùn)算，并且把位掩碼取反后和第二個(gè)雙親的DNA作AND運(yùn)算。結(jié)果，我們可以從一個(gè)雙親上隨機(jī)選擇某些位，其余的來(lái)自另外一個(gè)雙親。

變異是通過(guò)對(duì)個(gè)體的DNA和隨機(jī)生成的8位位掩碼作AND和OR運(yùn)算實(shí)現(xiàn)的。

對(duì)了，順便說(shuō)一下，最適應(yīng)的DNA當(dāng)然是255。您并不需要等待100,000代。當(dāng)您只是在欣賞狀態(tài)行時(shí)，請(qǐng)按Ctrl-C結(jié)束。

繁殖單詞
在這個(gè)例子里，我們用的DNA是32位（5個(gè)字節(jié)）的。每個(gè)字節(jié)代表一個(gè)字母或者一個(gè)空格。我們本來(lái)可以在一個(gè)字節(jié)中包含更多的信息，但是這樣可能會(huì)使這個(gè)例子的本意變得模糊。每一字節(jié)的值（介于0-255之間的數(shù)值）可能對(duì)應(yīng)A到Z之間的一個(gè)字母（如果它的值在65到90之間，便于選擇同ASCII碼集相匹配），或者也可能是一個(gè)空格（如果數(shù)值介于0到64之間，或91到255之間的話(huà)）。

請(qǐng)關(guān)注一下下面的這個(gè)例子和清單1的例子的相似之處。dictionary的單詞跟在程序的后面。

清單3.繁殖單詞

words.pl source


這個(gè)例子的主要問(wèn)題在于長(zhǎng)度超過(guò)32位的DNA不好處理。開(kāi)始我嘗試著自己做位操作，結(jié)果不僅僅是難處理，而且速度極慢。然后，我試了一下Math::BigInt包，用在這里還是非常慢。 您可以運(yùn)行清單3，程序文件為words.pl。

最后，我決定使用vec()函數(shù)—它的速度相當(dāng)快，對(duì)于處理DNA而言，它無(wú)疑是正確的選擇（本質(zhì)上，DNA是個(gè)位向量，一個(gè)內(nèi)建的Perl數(shù)據(jù)結(jié)構(gòu)）。用“perldoc-f vec”查找更多有關(guān)vec()函數(shù)的信息。

1024個(gè)個(gè)體的適應(yīng)性為0的結(jié)果也是有可能出現(xiàn)的。這個(gè)例子比第一個(gè)例子能更有效的預(yù)防這樣的“意外”的原因正在于此。

修改init_population()、recombine()和mutate()函數(shù)以處理位向量而非字節(jié)。

dna_to_words()函數(shù)的效率不高，但并不經(jīng)常調(diào)用它，所以問(wèn)題不是很?chē)?yán)重。速度慢的最主要的因素是fitness()函數(shù)試圖匹配dictionary里的所有單詞，以及字母表里的所有字母。

適應(yīng)性是這樣計(jì)算的：DNA里的每一個(gè)字母是一個(gè)2，加上那個(gè)字母在dictionary里出現(xiàn)的頻率，再為DNA里長(zhǎng)度為N的每個(gè)dictionary單詞加上2^N。dictionary數(shù)組以及字母頻率的散列只得到一次（使用closure）。您可以任意修改適應(yīng)性函數(shù)和dictionary來(lái)繁殖您自己的英語(yǔ)單詞。如上所示的適應(yīng)性公式很大程度上偏向字母，要匯集成英語(yǔ)單詞還需要一定的時(shí)間（盡管“on”和“in”頻繁出現(xiàn)）。

結(jié)束語(yǔ)
進(jìn)化遺傳算法是個(gè)非常吸引人的話(huà)題，在一篇文章中想把所有內(nèi)容都講清楚幾乎是不可能的。我希望您能實(shí)踐一下這些例子，并創(chuàng)建您自己的達(dá)爾文繁衍基礎(chǔ)。試試第二個(gè)例子中的fitness函數(shù)，看著英文單詞從原本無(wú)意義的字母和空格中出現(xiàn)，這真是一項(xiàng)非常有意思的娛樂(lè)。

上面的例子中用到的技巧涵蓋了從初級(jí)到高級(jí)的范圍，因此請(qǐng)盡量徹底理解這些內(nèi)容。通常情況下仍有改進(jìn)的空間。vec()函數(shù)尤為有趣。它非常適合于象DNA或者其它的數(shù)值數(shù)據(jù)之類(lèi)的長(zhǎng)的位向量。

編寫(xiě)您自己的遺傳算法的實(shí)現(xiàn)。與我的進(jìn)行比較，從缺點(diǎn)中學(xué)習(xí)（并不一定是您的缺點(diǎn)）。實(shí)現(xiàn)算法是一件巧妙的事。您會(huì)遇到許多錯(cuò)誤的方法，但正確的卻只有為數(shù)不多的幾種。

參考資料

感謝Abigail，他的CPAN樣本模塊可以演示我在兩個(gè)例程中都用到的sample()函數(shù)。對(duì)于任何一個(gè)Perl程序員，Sample樣本模塊及其文檔都是非常棒的工具。

訪(fǎng)問(wèn)CPAN，那里有您想要的所有的Perl模塊。

在Perl.com尋找Perl信息和相關(guān)參考資料。

訪(fǎng)問(wèn)perldoc.com，那里有Perldoc在線(xiàn)信息。

“Perl 編程思想，第 3 版”，由Larry Wall、Tom Christiansen和Jon Orwant合著（O'Reilly & Associates 2000）。這是目前最好的Perl入門(mén)指導(dǎo)，更新到5.005和 5.6.0。

“用 Perl 精通算法”，由Jon Orwant、Jarkko Hietaniemi和John Macdonald合著（O'Reilly & Associates 1999），是以Perl表達(dá)算法的很棒的提綱。第14章的“概率”說(shuō)明了如何用Perl來(lái)計(jì)算加權(quán)和不加權(quán)的概率分布。

遺傳算法常見(jiàn)問(wèn)題解答有些過(guò)時(shí)，但是它指向的的確是一些有用的遺傳算法的軟件，有免費(fèi)的也有商業(yè)化的。

Teodor Zlatanov在developerWorks寫(xiě)的相關(guān)文章，包括：

One-liners，101

對(duì)大畫(huà)面細(xì)節(jié)的觀察

瀏覽developerWorks上更多Linux參考資料。

瀏覽developerWorks上更多開(kāi)放源代碼的參考資料。


關(guān)于作者Teodor Zlatanov于1999年畢業(yè)于波士頓大學(xué)計(jì)算機(jī)工程專(zhuān)業(yè)，獲碩士學(xué)位。自從1992年以來(lái)，他一直從事編程工作，使用的語(yǔ)言包括Perl、Java、C和C++。他的主要興趣是在文本解析、3層客戶(hù)機(jī)—服務(wù)器數(shù)據(jù)庫(kù)體系結(jié)構(gòu)、UNIX系統(tǒng)管理、CORBA以及項(xiàng)目管理方面的開(kāi)放源代碼工作。歡迎和Teodor聯(lián)絡(luò)，發(fā)電子郵件到mailto:tzz@bu.edu提出建議或者糾正錯(cuò)誤。

　

本文出自IBM網(wǎng)站linux專(zhuān)欄（www.ibm.com/developworks/cn）,轉(zhuǎn)載請(qǐng)注明出處。