| 導購 | 订阅 | 在线投稿
分享
 
 
 

功能豐富的Perl:Perl用于實現遺傳算法

來源:互聯網  2008-05-19 06:25:56  評論

如果您的機器上已經安裝了 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」頻繁出現)。

結束語

進化遺傳算法是個非常吸引人的話題,在一篇文章中想把所有內容都講清楚幾乎是

  如果您的機器上已經安裝了 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」頻繁出現)。   結束語   進化遺傳算法是個非常吸引人的話題,在一篇文章中想把所有內容都講清楚幾乎是   
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有