[新知] 細胞自動機

看板Cognitive作者nyc0125 (@)時間17年前 (2009/04/20 00:17)推噓4(4推 0噓 89→)

留言93則, 3人參與討論串1/3 (看更多)

簡明介紹：http://mmdays.com/2007/07/12/game_of_life/ 簡單模擬：http://www.bitstorm.org/gameoflife/ 更多例子：網址：http://www.atlas-zone.com/complex/alife/ca/index.html 細胞自動機　Cellular Automata 2002, 1, 10　吳文成　　細胞自動機（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」，意思是，細胞自動機的疊代演化是往前決定的，它有許多個可能的過去，但是它的未來發展只有一個，而這個唯一的未來發展所產生的複雜度，卻常常在人們的預期與想像之外。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.229.124.159

→