複雜性科學 - 複雜適應性系統人工生命 思辨 部落格 信箱 阿特拉斯

細胞自動機 Cellular Automata
2002, 1, 10 吳文成
吳文成老師的個人網頁 [最新完整]: http://www.fractal-wu.com/
吳文成老師的系列演講影片: http://www.youtube.com/user/sinner66s
  細胞自動機(Cellular Automata)最初由數學家 Stanislaw M. Ulam(1909-1984)與 John von Neumann(1903-1957)於 1950 年代所提出 ,在型態表現上,細胞自動機是一個離散型的動力系統( Discrete Dynamical Systems)。在 1940 年代 ,von Neumann 與共事的科學家們合作設計了可儲存程式的數位電腦之後,他就對自我複製發生興趣:能儲存程式的機器能不能自我複製
? von Neumann 認為,至少在原則上與形式上是可行的,於是他開始作這方面的理論研究,過程中他提出了「細胞自動機」的概念, 這個實際構想是由羅沙拉摩斯的數學家 Ulam 所建議的
。當細胞自動機在電腦上模擬的時候,幾乎可以複製出類似於自然界當中實際發生的動力系統運作,這使得細胞自動機成為了研究複雜系統行為的最初理論框架,羅沙拉摩斯的博士後研究員 Christopher Langton 因而提出了「人工生命」( Artificial Life )這個名詞 , 細胞自動機便是人工生命的第一個雛形,並且變成複雜性科學,或者說是複雜適應性系統的其中一支。

  細胞自動機是由一些特定規則的格子所組成,每個格子看做是一個細胞;每一個細胞可以具有一些狀態,但是在某一時刻只能處一種狀態之中。隨著時間的變化(我們稱作「疊代」過程),格子上的每一個細胞根據周圍細胞的情形,按照相同的法則而改變狀態,換句話說,一個細胞的狀態是由上一個時刻所圍繞的細胞的狀態所決定。以人工生命的角度來看,細胞自動機可以視為一個讓許多單細胞生物生活的世界,在我們設定好這個世界的初始狀態之後,它們便按照同一個規則做演化。

  設計一個細胞自動機需要包含幾個部份:

  ◆ 決定細胞活動空間的維度
  ◆ 定義細胞可能具有的狀態
  ◆ 定義細胞改變狀態的規則
  ◆ 設定細胞自動機中各個細胞的初始狀態

  細胞自動機,在細胞活動的空間上,可以是一維的,二維的,三維的,或更高維度,在這個網頁,筆者要分別介紹二維的細胞自動機(也稱作「生命遊戲」),與一維的細胞自動機。透過不同的設計,細胞自動機可以展現無限的多樣性,其中最讓人驚異的是有些細胞自動機可以產生存在於大自然的景象,例如貝殼上的圖案、雪花的結構、蜿蜒的河流等等,另外,我們也可以發現,這些小方格的變化似乎展現了許多真實生命的特質,例如,細胞自動機中的細胞們會像有機生物一般,有移動、成長、滅亡與自我複製等類似的行為。

  就形式而言,細胞自動機有三個特徵:

  ◆ 平行計算(parallel computation):每一個細胞個體都同時同步的改變
  ◆ 局部的(local):細胞的狀態變化只受周遭細胞的影響。
  ◆ 一致性的(homogeneous):所有細胞均受同樣的規則所支配

  事實上,有些研究學者更進一步猜測,我們存在的這個宇宙是否就是一種極其複雜的細胞自動機,我們的宇宙的確與理論上的細胞自動機有很多相似的地方,像是上述的細胞自動機之三個特徵,宇宙也都符合:宇宙是平行處理的,宇宙中的每一點受鄰近狀態的影響最大,宇宙各處遵循著同樣的自然律。雖然與整個宇宙相比,細胞自動機的規則是過於簡單,但是它裡面所蘊含的道理可能與宇宙的機制是相通的。 理論物理學家 Stephen Wolfram(1959-)就指出 ,細胞自動機的數學架構,與一些造成真實世界的複雜物理系統之數學架構是完全一樣的,也許這正是掌管遺傳重任的 DNA 所賴以工作的原理 。當你看到自然界那些貝殼或指紋曲折的圖案時,不免要問 :「這麼複雜的圖案要如何編碼到 DNA 裡頭呢?」Wolfram 說 :「如果我猜的不錯,那些圖形是由類似於細胞自動機的簡單法則所產生的,而這樣的編碼顯然是易如反掌。」

  細胞自動機以簡單的規則,卻能夠產生複雜的動態交互現象,顯然我們不該只是以一個數學遊戲,來看待它。這些年來,細胞自動機已經被運用於不同領域的研究,包括通訊、計算、建設、生長、再生、競爭及演化。細胞自動機已為物理中平常的微分方程式提供極為簡單的模型,例如熱和波的波動方程,同時也為湍流、混沌、碎形等提供了離散型的模型,最後,利用細胞自動機所做的生物模型也被提出。接下來,筆者將盡可能地介紹細胞自動機的規則、範例與相關資訊,以下的介紹分為兩種不同類型的細胞自動機:

  
  ├─ 二維的細胞自動機:
     
     ├─ 生命遊戲,與其規則
     ├─ 生命遊戲的有趣範例
     ├─ 生命遊戲的規則變化(一)
     ├─ 生命遊戲的規則變化(二)
     ├─ 生命遊戲的規則變化(三)
     └─ 生命起源於混沌的邊緣
  
  ├─ 一維的細胞自動機:
     
     ├─ 一維細胞自動機,與其規則(一)
     ├─ 一維細胞自動機,與其規則(二)
     ├─ 一維細胞自動機,與其規則(三)
     ├─ 一維細胞自動機的有趣範例
     └─ 四個普遍性等級的再探討
  
  └─ 相關連結與資源

  瞭解了細胞自動機的疊代過程之後,你會發現:細胞自動機在某一疊代的細胞形態只會產生「唯一」形態的下一代,而我們卻無法從新一代的形態而回溯得知上一代確定的細胞形態,因為這樣的「回溯」有太多種可能性,而且可能性的數量會隨著一次接著一次的「回溯」而以指數比例地增加,這使得我們即使看見某一疊代中有趣的細胞演化,卻無法準確地推回出它的初始狀態 。這種性質,我們稱呼為「Forward-Deterministic」,意思是,細胞自動機的疊代演化是往前決定的,它有許多個可能的過去,但是它的未來發展只有一個,而這個唯一的未來發展所產生的複雜度,卻常常在人們的預期與想像之外。



上一頁 上一層 下一頁