發表文章

目前顯示的是 4月, 2014的文章

路徑搜尋之演化論

圖片
我現在要作一個實驗,模擬一個虛擬的世界,這個世界的構造很簡單,是一張10乘10的地圖,總共100個格子所組成。在這個世界裡面,會隨機產生金幣,機率是一半一半,也就是說大約在這100個格子裡面,平均會有50個金幣。還要模擬某種生物,這種生物的生存目的很簡單,就是儘可能的吃金幣,因為這個世界的食物只有金幣。能夠吃愈多金幣的生物就愈能夠生存下來並把它的基因繼續傳播下去。生活在這個世界的生物就把它命名為吃金幣的人...吃金幣的人在這個世界能作的事情很有限,除了吃金幣外,他只能作上下左右四種方向的移動,每次只能移動一個格子。 這個實驗的目的是想辨法找到一個最佳的路徑搜尋方法,讓吃金幣的人儘可能吃愈到愈多的金幣。為了評估吃金幣的人的路徑搜尋方法有多好,需要有一個可以量化的方法。所以就很簡單的設定,如果吃金幣的人每吃到一個金幣就能獲得10分,分數愈高就表示它的路徑搜尋方法愈好。當然也不能讓吃金幣的人任意的作無限次移動,因為這樣一來就沒有意義了,因為吃金幣的人一定可以吃光世界上所有金幣。所以我們要限制移動次數,比如說200次,每200次移動後再來作評分。 我們將會使用基因算法(genetic algorithm),讓吃金幣的人自行進化,得到一個認為最棒的路徑搜尋方法。 基因算法的主要精神是,對於所要解決的問題以模擬生物界物競天擇適者生存的自然法則,讓所摸擬的人工生物自行進化出在模擬世界中的優勢物種,也就是得到所求的最佳解。不過這裡講到的進化這二個字有誤導的嫌疑,實際上這也是大多數人對於進化及演化之間的誤解。進化這二字裡面隱含了方向性,而事實上演化是沒有方向性的,演化是生物對生存環境的適應。生物會演化成什麼樣子,沒有任何的目的性和方向性,這裡面帶有隨機性,主要取決於環境變因。 自然選擇和變異再加上時間是演化的基本原則,所以我們將要模擬的程式也是使用到這幾個基本原則。雖然實際上的細節,和真實世界生物界的演化並不相同,但因為我們利用這幾個演化的基本原則來模擬我們的世界,結果也會得到類似的結果。我們可以看到我們所模擬的吃金幣的人果真在這個金幣世界裡面,慢慢的演化出愈來愈聰明的路徑搜尋方法。而同自然界的生物演化一樣,你甚至無法知道也無法分析它到底是怎麼辨到的。 前面提到這個世界是個10x10的地圖,共有100個格子,在這個世界面裡有會隨機產生的金幣。如果一個格子上