Perl用於實現遺傳算法
[編者的話]
遺傳算法在生物信息學尤其是蛋白結構預測與分析中有重要應用：Perl是現在生物信息學界中很熱門的一種編程語言（我們在以前專題中曾做過專門介紹）。Perl的長處是文本分析，那麼它在編寫算法上是否能一樣表現優異呢，它能不能做這方面的工作呢，別急，且看下文：）
創建您自己的達爾文式的繁殖基礎
Teodor Zlatanov (tzz@iglou.com)
程序員，Gold Software Systems
2001年8月
遺傳編程建立在達爾文適者生存的自然選擇法則的基礎之上，利用變異和複製來生成算法，該算法可創建不斷改進的計算機程序。在本專欄裡，您將開始瞭解用淺顯的術語表述的遺傳算法。Ted 給出了幾種特定的任務的 Perl 實現，您可以用於廣泛的用途。為了示範遺傳算法，Ted 繁殖了一些數字和字母，應用於公式以測試這些數字的適應性，而繁殖的字母則形成了英語單詞。
如果您的機器上已經安裝了Perl 5.005或者更高的版本，您可以運行一下文章中的例子。您的系統最好應該是安裝了最近的（2000年或者更遲些）主流的 UNIX（Linux，Solaris，BSD），但其它種類的操作系統可能也可以。文中的例子可能可以在更老的版本的Perl、UNIX以及其它操作系統下運行，但是如果不行的話，讀者應當把它看作是一次練習來解決。
歷史
進入20世紀以來，在速度和影響範圍方面遺傳學的發展只有電子學和計算機科學能與之相比。遺傳算法是20世紀出現的最令人感興趣的算法之一，這一說法是恰當的。
遺傳算法（以及普遍意義上的進化算法）出現在20世紀60年代早期，並在計算機科學的確定性和非確定性算法之間佔據了一席之位。本質上，遺傳算法具有如同您所希望的那樣的確定性，意味著用戶可以決定重複次數和結束條件。它模擬達爾文的自然選擇，還有變異，把「適應性」（正如適用於個體的公式所決定的那樣）作為主要因素選擇生存繁衍和變異的個體。
其它的進化算法試圖模擬拉馬克的進化論，在他看來，行為是一種生存的機制，可以在兩代之間傳遞，甚至有一些進化程序是出於某種目的而自然出現的。以上這些都不在本文的論述範圍之內。
Perl用於實現遺傳算法的主要缺點在於速度慢。由於遺傳算法的計算需要，用C語言或其它低級的預編譯語言來實現效率會更高。本文展示的Perl例程不如其C語言的等價程序快，但是可以使您明白遺傳算法是如何工作的，況且，對於一些問題來說，已經夠快了。
那麼什麼是遺傳算法呢？
遺傳算法是如此簡單，任何人只要用高中時學過的生物術語就可以理解。以一群個體為例，它們都有自己的DNA。然後衡量每一個個體的適應性（把它看作是適用於個體的DNA的官能來衡量），並且使那些更適應的個體更有可能繁衍。而最不適應的個體將會被滅絕。每個倖存者都會有機會繁衍（重要的是任何倖存者都可能會繁衍，如果不太適應的話，僅僅是降低了可能性）。合併雙親的DNA，對合併後的DNA應用隨機變異以模擬繁衍。理論上說來，新的個體是和雙親一樣適應的，由於變異或增或減會有些微小的變化。然後循環會週而復始。
雖然，有許多變化的因素在影響遺傳算法，包括人群大小、代（算法的迭代）、合併方法、適應性函數，適應性將如何影響繁衍的可能性，以及發生了多少變異。
該算法也存在一些缺陷。如果把應用於DNA的適應性官能看成是一系列的二進制位，效果最好。換句話說，如果DNA是一系列二進制的選項，是還是不是。藍眼睛？黑眼睛？紅頭髮？黑頭髮？合併雙親的DNA和隨後的變異應當不允許特定的一些位組合出現，因為得出的DNA可能不再是最初的問題的有效解答。請記住，所謂「DNA」僅僅是適應性公式純數學的一種解答。該公式中用到的一些值可能是無效的—例如，除數為零。
另外，遺傳算法不受時間限制。由您來挑選代的數目。您可以確定某個目標 — 比方說，「找一個適應性為0.99999 的個體」，找到後停止。但是，結果是算法永遠也不會結束，因為它沒找到那個個體。如果您制定了不切實際的目標，或者代的數目太小，就會出現問題。嘗試、出錯，以及深入的思考是解決這個問題的最佳途徑。
適應性公式返回的是介於0和1之間的一個浮點數。您也可以使用其它的範圍的數，但是我的經驗告訴我，浮點數是最有效的。比如，如果出於優選的考慮，您希望適應性是一個7位的整型數，您想要的範圍就是0到32767之間。
當然，把優選推遲到您認為有需要的時候，這是一個好主意，那麼您在開始的時候，最起碼得有一個簡單的適應性公式。適應性公式是遺傳算法中最常用的函數，（它將要被調用的次數是（人群大小）x（代的數目）次），所以您應當盡可能的使它簡單、快速。
有三種「好」的可以退出遺傳算法的方式！首先，當 DNA 池裡不再有變化時，您就可以決定退出。事實上，這是個棘手的測試，只要您能夠把DNA表示為字符串，就可以利用一個確定串之間的差異的CPAN模塊。第二，如果達到了適應性的目標，您也可以退出。除非對適應性公式非常瞭解（在這種情形下，無論如何，您都可能不再需要遺傳算法了），設定適應性目標的結果，或者是導致無窮循環，或者是得到一個僅僅是「足夠好」的個體。第三，在迭代了一定的次數或者說經歷了一定數目的「代」後，您也可以退出。
在實踐中，這三種方式（或者至少是第二種和第三種）都會被用於控制遺傳算法。只要經過為數不多的測試，可能是10次，也可能是20次，您就會清楚的知道算法彙集需要多長時間，以及您想要的適應性是什麼樣子的。
一個簡單的例子
清單 1 裡的代碼把一個字節看作是DNA（它的值介於0和255之間，8位）。對每個新個體應用適應性公式一次，用表示DNA的字節所具有的數值，去除以256。這樣適應性公式總是會返回一個介於0和255/256之間的數值，因此，它永遠也不會等於1。那麼，您認為最適應的DNA應當是多少呢？
清單1.繁殖字節以測試其適應性
numbers.pl source
清單1里有幾件非常有趣的事情。它的主循環位於程序的開始部分，您應當弄懂所有的程序片，以及它們是如何共同作用於人群的（既然這些部分是相互獨立的，因此我們還可以在下面的例子中重複使用）。您可以運行清單1，程序文件為numbers.pl。
通過把map()堆棧到grep()的上部，我們在select_parents()函數里建立了weights數組。雖然我們本來可以把它寫成循環，但是長度只有一行的解決方案要清楚得多，並且不會顯著降低程序運行的速度。
清單2.map和grep堆棧
my @weights = map { $_->{fitness} } grep { $_->{survived} } @$population;
$population數組引用是間接引用。那麼，只有帶「survived」域的數組元素（在前面由survive()函數設定的）通過grep。然後這些倖存者被蒸餾成代表其適應性的數字，並存入weights數組裡該倖存者所對應的位置。
取大小為256的人群，原因是這樣便於把個體都初始化成一個與其序號相等的數字。您可以自由選擇不同的人群大小開始。
大於1%的變異率使得適應性的最大值和最小值劇烈波動。人群絕不可能穩定在高適應性。變異率低導致了需要更多的時間人群才能整體上達到高適應性。最後，對於我們討論的人群大小而言，1%恰好合適。
繁衍選擇算法會查找weights數組，選擇第一個雙親 — 其實，每個個體都有可能成為雙親，但是雙親位置的數目是確定的。另一個雙親是隨機地從雙親人群中挑選的。為什麼呢？噢，本來我們可以在weights數組裡把另外一個雙親也確定下來，但是，這樣我們可以確保每個可以成為雙親的個體都有可能參與繁衍過程。
實際上實現繁殖的是一個隨機的8位位掩碼。我們只把這個位掩碼和第一個雙親的DNA（請記住，它只是一個字節）作AND運算，並且把位掩碼取反後和第二個雙親的DNA作AND運算。結果，我們可以從一個雙親上隨機選擇某些位，其餘的來自另外一個雙親。
變異是通過對個體的DNA和隨機生成的8位位掩碼作AND和OR運算實現的。
對了，順便說一下，最適應的DNA當然是255。您並不需要等待100,000代。當您只是在欣賞狀態行時，請按Ctrl-C結束。
繁殖單詞
在這個例子裡，我們用的DNA是32位（5個字節）的。每個字節代表一個字母或者一個空格。我們本來可以在一個字節中包含更多的信息，但是這樣可能會使這個例子的本意變得模糊。每一字節的值（介於0-255之間的數值）可能對應A到Z之間的一個字母（如果它的值在65到90之間，便於選擇同ASCII碼集相匹配），或者也可能是一個空格（如果數值介於0到64之間，或91到255之間的話）。
請關注一下下面的這個例子和清單1的例子的相似之處。dictionary的單詞跟在程序的後面。
清單3.繁殖單詞
words.pl source
這個例子的主要問題在於長度超過32位的DNA不好處理。開始我嘗試著自己做位操作，結果不僅僅是難處理，而且速度極慢。然後，我試了一下Math::BigInt包，用在這裡還是非常慢。 您可以運行清單3，程序文件為words.pl。
最後，我決定使用vec()函數—它的速度相當快，對於處理DNA而言，它無疑是正確的選擇（本質上，DNA是個位向量，一個內建的Perl數據結構）。用「perldoc-f vec」查找更多有關vec()函數的信息。
1024個個體的適應性為0的結果也是有可能出現的。這個例子比第一個例子能更有效的預防這樣的「意外」的原因正在於此。
修改init_population()、recombine()和mutate()函數以處理位向量而非字節。
dna_to_words()函數的效率不高，但並不經常調用它，所以問題不是很嚴重。速度慢的最主要的因素是fitness()函數試圖匹配dictionary裡的所有單詞，以及字母表裡的所有字母。
適應性是這樣計算的：DNA裡的每一個字母是一個2，加上那個字母在dictionary裡出現的頻率，再為DNA里長度為N的每個dictionary單詞加上2^N。dictionary數組以及字母頻率的散列只得到一次（使用closure）。您可以任意修改適應性函數和dictionary來繁殖您自己的英語單詞。如上所示的適應性公式很大程度上偏向字母，要彙集成英語單詞還需要一定的時間（儘管「on」和「in」頻繁出現）。
結束語
進化遺傳算法是個非常吸引人的話題，在一篇文章中想把所有內容都講清楚幾乎是不可能的。我希望您能實踐一下這些例子，並創建您自己的達爾文繁衍基礎。試試第二個例子中的fitness函數，看著英文單詞從原本無意義的字母和空格中出現，這真是一項非常有意思的娛樂。
上面的例子中用到的技巧涵蓋了從初級到高級的範圍，因此請盡量徹底理解這些內容。通常情況下仍有改進的空間。vec()函數尤為有趣。它非常適合於象DNA或者其它的數值數據之類的長的位向量。
編寫您自己的遺傳算法的實現。與我的進行比較，從缺點中學習（並不一定是您的缺點）。實現算法是一件巧妙的事。您會遇到許多錯誤的方法，但正確的卻只有為數不多的幾種。
參考資料
感謝Abigail，他的CPAN樣本模塊可以演示我在兩個例程中都用到的sample()函數。對於任何一個Perl程序員，Sample樣本模塊及其文檔都是非常棒的工具。
訪問CPAN，那裡有您想要的所有的Perl模塊。
在Perl.com尋找Perl信息和相關參考資料。
訪問perldoc.com，那裡有Perldoc在線信息。
「Perl 編程思想，第 3 版」，由Larry Wall、Tom Christiansen和Jon Orwant合著（O'Reilly & Associates 2000）。這是目前最好的Perl入門指導，更新到5.005和 5.6.0。
「用 Perl 精通算法」，由Jon Orwant、Jarkko Hietaniemi和John Macdonald合著（O'Reilly & Associates 1999），是以Perl表達算法的很棒的提綱。第14章的「概率」說明了如何用Perl來計算加權和不加權的概率分佈。
遺傳算法常見問題解答有些過時，但是它指向的的確是一些有用的遺傳算法的軟件，有免費的也有商業化的。
Teodor Zlatanov在developerWorks寫的相關文章，包括：
One-liners，101
對大畫面細節的觀察
瀏覽developerWorks上更多Linux參考資料。
瀏覽developerWorks上更多開放源代碼的參考資料。
關於作者Teodor Zlatanov於1999年畢業於波士頓大學計算機工程專業，獲碩士學位。自從1992年以來，他一直從事編程工作，使用的語言包括Perl、Java、C和C++。他的主要興趣是在文本解析、3層客戶機—服務器數據庫體系結構、UNIX系統管理、CORBA以及項目管理方面的開放源代碼工作。歡迎和Teodor聯絡，發電子郵件到mailto:tzz@bu.edu提出建議或者糾正錯誤。
本文出自IBM網站linux專欄（www.ibm.com/developworks/cn）,轉載請註明出處。
|
|
當前位置：開發者網絡 >> 技術教程 >> CGI教程 >> CGI文檔 >> 內容
