路徑搜尋之演化論

我現在要作一個實驗，模擬一個虛擬的世界，這個世界的構造很簡單，是一張10乘10的地圖，總共100個格子所組成。在這個世界裡面，會隨機產生金幣，機率是一半一半，也就是說大約在這100個格子裡面，平均會有50個金幣。還要模擬某種生物，這種生物的生存目的很簡單，就是儘可能的吃金幣，因為這個世界的食物只有金幣。能夠吃愈多金幣的生物就愈能夠生存下來並把它的基因繼續傳播下去。生活在這個世界的生物就把它命名為吃金幣的人...吃金幣的人在這個世界能作的事情很有限，除了吃金幣外，他只能作上下左右四種方向的移動，每次只能移動一個格子。

這個實驗的目的是想辨法找到一個最佳的路徑搜尋方法，讓吃金幣的人儘可能吃愈到愈多的金幣。為了評估吃金幣的人的路徑搜尋方法有多好，需要有一個可以量化的方法。所以就很簡單的設定，如果吃金幣的人每吃到一個金幣就能獲得10分，分數愈高就表示它的路徑搜尋方法愈好。當然也不能讓吃金幣的人任意的作無限次移動，因為這樣一來就沒有意義了，因為吃金幣的人一定可以吃光世界上所有金幣。所以我們要限制移動次數，比如說200次，每200次移動後再來作評分。

我們將會使用基因算法(genetic algorithm)，讓吃金幣的人自行進化，得到一個認為最棒的路徑搜尋方法。

基因算法的主要精神是，對於所要解決的問題以模擬生物界物競天擇適者生存的自然法則，讓所摸擬的人工生物自行進化出在模擬世界中的優勢物種，也就是得到所求的最佳解。不過這裡講到的進化這二個字有誤導的嫌疑，實際上這也是大多數人對於進化及演化之間的誤解。進化這二字裡面隱含了方向性，而事實上演化是沒有方向性的，演化是生物對生存環境的適應。生物會演化成什麼樣子，沒有任何的目的性和方向性，這裡面帶有隨機性，主要取決於環境變因。

自然選擇和變異再加上時間是演化的基本原則，所以我們將要模擬的程式也是使用到這幾個基本原則。雖然實際上的細節，和真實世界生物界的演化並不相同，但因為我們利用這幾個演化的基本原則來模擬我們的世界，結果也會得到類似的結果。我們可以看到我們所模擬的吃金幣的人果真在這個金幣世界裡面，慢慢的演化出愈來愈聰明的路徑搜尋方法。而同自然界的生物演化一樣，你甚至無法知道也無法分析它到底是怎麼辨到的。

前面提到這個世界是個10x10的地圖，共有100個格子，在這個世界面裡有會隨機產生的金幣。如果一個格子上有金幣就不為空，反之表示這個格子是空的狀態，因此每一個格子有二種不同的狀態，所以我們可以用一個boolean值來表示一個格子。不過因為這個世界是有邊界的，為了讓吃金幣的人有辨法意識到邊界的存在，我們也需要把這個資訊編碼進來。所以加上有無金幣及邊界，每一個格子共有3種可能的狀態。我們可以用一個數字表示一個格子的3種不同狀態。

  0: 空
  1: 金幣
  2: 邊界

吃金幣的人在這個世界裡會有一個唯一個位置，我們簡單把座標定為0~99。他能作的動作有5種，吃金幣，往上往下往左或往右移動，移動的時候一次只走一步。因為吃金幣的人只能作4種方向其中一個方向的移動，再加上他目前所在的位置，所以可以說他的可見範圍有5個格子。

    0
  1 X 3
    2

如上，吃金幣的人的當前的位置是X，0123是其它4個方向所在的格子。因為每一個格子有3種可能狀態，5個格子就總共有3^5=243種可能狀態。如果我們把這243種不同狀態分別對應到吃金幣的人可以作的其中一種動作，例如吃或往上移動一格等等，就等於得到一個路徑搜尋的演算法。只要每次根據吃金幣的人的所在位置，以及他的視野上的5個格子的狀態來對這243種狀態表去查詢要作什麼動作，吃金幣的人就會自動的按照這個表的設定動起來。而這個表也就是這個吃金幣的人的基因！每一條基因所編碼的內容是狀態對動作，也就是生物對不同環境狀態作所出的不同反應。這看起來很機械，只是個查表動作。雖然只是機械式的查表，但生物所表現出來的行為就好像具有意識，只要這個表足夠複雜甚至能表現的好像擁有智慧一樣！

  0: 往上移動一格
  1: 往左移動一格
  2: 往下移動一格
  3: 往右移動一格
  4: 吃金幣

這一來每一個吃金幣的人都有一條長度是243個單位的基因，每一個單位就是一個數字，對應吃金幣的人所能執行的5種動作之一。當然243是理論數字，這裡面有一些狀態是不可能出現的而可以排除，但為了簡單起見我們就不特別處理了。

下面是一段長度是243的可能基因，不同位置的數字對應不同狀態的反應動作，而.是無動作的遮罩表示這個位置的基因是冗餘。

30.44.11.13.04.13.33.30....12.22.41.20.40.11.34.02....32.40.24.10.03.02.33.42....01.40.24.14.31.44.32.10....31.12.00.11.40.31.14.01....04.31.33.44.13.43.10.42....11.23.11.01.01.12.24.34....11.02.40.33.00.22.32.34...............................

模擬的方法如下：

1. 一次模擬200個吃金幣的人，每一個初代吃金幣的人都隨機給一組基因。
2. 讓吃金幣的人根據他自己的基因設定走個200步，最後再看看得分是多少。
3. 這裡面有個扣分的機制，如果吃金幣的人走出邊界了要扣分，因為這是不允許的。或者如果吃金幣的人作了吃金幣的動作，但那個格子裡面沒有金幣也要扣分，因為他亂吃。這個扣分的機制等於是讓不好的基因淘汰的機制，給他一個生存的壓力。
4. 上面讓每個吃金幣的人走200步的模擬，每一個吃金幣的人都作100次，然後再統計一個平均分數。
5. 針對每個吃金幣的人的平均分數作排序，由高到低。可以知道這200個吃金幣的人的基因，誰優誰劣。
6. 對這200個吃金幣的人兩兩配對來產生下一代。配對選擇的方法是，得分愈高的也就是基因愈優的就愈容易被選擇。得分低的也還是有可能被選擇，只不過機率較低，這樣一來也可以讓那些得分低，但在未來有潛力的基因有機會出頭。

7. 配對的方法是隨機選擇一個基因中間位置，將二個親代基因切斷並交換。當然還有其它配對方法，這裡只選擇最簡單的一種。
   
   00003333333
   44448888888
    =>
   00008888888
   44443333333
   
   

8. 新的子代基因再以一定機率產生突變。
9. 跳至2繼續模擬。

下圖是某個吃金幣的人的成長曲線圖，水平軸是時間，垂直軸是分數，Y-軸上的數字是平均最高分數。上面的點線是最大值，下面的點線是種群平均值。

這是某個吃金幣的人大約迭代了3000次的結果。

上圖分別是另外二個吃金幣的人迭代了約4000次及6000次的結果。

可以看到這三個吃金幣的人的成長曲線和速度都不同，但他們都是朝特定方向進化。我會說進化，是因為他們的演化的確是有方向性的，而這個方向是我刻意控制的，也就是讓這些吃金幣的人想盡辨法得高分。

在這些模擬裡面，有時候也會出現類似進入演化的死胡同的現象。這樣的現象是因為在模擬的過程中過早把那些具有潛力的基因給淘汰掉了，因為分數不夠而被選擇的機會太少。即使後來因為突變而又產生這些基因，也因為種群數量太少而沒有辨法讓這些基因傳播開來。結果就是化大概只能永遠停留在某個高度，不能再進一步成長。