這一節的標題是
9.1 Genetic Algorithms: Inspired by Actual Events
因為方格子標題字數限制,所以沒完整顯現
在開發具備演化能力的程式系統時,所使用的主要手段,就是受到達爾文演化論啟發所發展出來的基因演算法(genetic algorithm),簡稱GA。在GA中,會讓問題可能的解答形成一個族群,然後這個族群會透過模仿自然界生物演化時的天擇方式,一代一代地進行演化。
雖然利用電腦來模擬演化過程可追溯至1950年代,但現在我們對基因演算法的許多理解,其實都源自於密西根大學John Holland教授的研究成果;他在1975年所發表,由MIT所出版的《Adaptation in Natural and Artificial》一書,開創了GA研究的先河。時至今日,GA已成為演化式運算(evolutionary computing)這個更廣泛領域的一部分。
關於GA,有一點要注意的是,雖然它是受到遺傳、演化等理論的啟發所發展出來的,但它並沒有要把這些領域的相關理論給全部拿來使用的意思,更不會想要精準地去模擬那些過程;那是計算生物學(computational biology)領域在做的事。所以,在這章中,會把重點放在如何把演化策略應用到程式中,而不會去模擬真實世界中生物實際進行的演化過程。嚴格來說,GA這個術語所指的,是以特定的方式來解決某些特定類型的問題所開發出來的演算法。這裡頭的細節很多,不過,有些細節對原書來說並不是那麼重要。雖然這章的範例是基於正規的GA所設計出來的,但因為我們的重點是在於如何發揮創意來把演化理論給應用到程式裡頭,所以也就不會太去強調精準無誤地實作出演算法這件事。基於這樣的考量,本章會區分為下面三個部分:
- 傳統的基因演算法:先從傳統教科書中會看到的GA介紹起。在電腦科學中,有些問題的解空間(solution space)非常大,使用暴力法來解會耗時過長。為了解決這個問題,所以開發出像GA這樣的演算法。例如,如果有個數字介於1和10億之間,那我們要花多少時間才能猜中這個數字?如果用暴力式的解法,那就必須一個數字一個數字去猜。運氣好的話,第一次就猜中;運氣背到極點的話,猜到最後一個數字才猜中。不過那都是極端的狀況,平均來說,如果從1開始猜,那也要猜個好幾年才能猜中。那如果每次猜的時候,都能知道猜得有多準,然後根據猜的結果來選擇下一個要猜的數字,這樣不就能快一點猜中數字了嗎?這也就是說,我們所猜的數字透過演化的方式,不斷地接近正確的數字,最後找出正確的數字。傳統的GA,就是這麼做的。
- 互動式挑選(interactive selection):介紹過傳統的GA之後,會來看看GA在視覺藝術中的應用。「互動式挑選」指的是透過與使用者互動的方式所進行的演化過程。例如,你有一些圖片,透過互動式挑選的方式,你挑出幾張喜歡的,然後演算法就可以根據你的喜好,產製新的圖片出來。
- 生態系統模擬:傳統的GA和互動式挑選技術雖然都有演化的功能在其中,但並不能真正的針對發生在真實世界的演化過程進行模擬。在這一章中,也會針對由人造生物所組成的生態系統,探討可用於模擬其演化過程的技術。例如,要怎麼做,才能讓模擬世界中的物件相遇、交配,並把它們的基因傳遞給下一代呢?