精華區beta Cognitive 關於我們 聯絡資訊
簡明介紹: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
sardine:稍微看了一下 我覺得這中間有些小問題.. 04/20 12:25
sardine:一面是數學家把生物想的太簡單了.. 04/20 12:25
sardine:在公理集合論裡面對探討的集合跟邏輯是非常嚴正的 04/20 12:27
sardine:數學家也把一些生物上的序列看的很簡單 就像直線一樣 04/20 12:28
sardine:把生物資訊的特徵值數化量化 做出等量的刻度 04/20 12:28
sardine:之後才能引進數學理論 但這個過程在生物界就有很大的問題 04/20 12:29
sardine:另一面是生物學家也把數學想的太粗糙的 04/20 12:29
sardine:就如同上面所說的嚴正的尺度...1跟1.0000000000000000001 04/20 12:32
sardine:到底一不一樣...差不多一樣在數學上是不被接受的 04/20 12:32
sardine:可是自然界中卻存在很多差很多卻是本質一樣的東西 04/20 12:33
sardine:簡化一個系統也許真的可以看出個什麼特別的隱藏意義 04/20 12:35
sardine:但就如同圖片壓縮檔一樣...從bmp軟成jpeg時已經遺失了大半 04/20 12:36
sardine:的資訊...這些資訊到底重不重要 到底會不會影響推理.. 04/20 12:36
sardine:不是神誰也不知道... 04/20 12:37
sardine:我只是覺得不管他做這種系統的動機為何 04/20 12:37
sardine:中間這段猜想宇宙的機制已經有點變過度的幻想.. 04/20 12:39
cog5566:最近在看一本書也有提到這個,就是天下文化翻譯的理性之夢 04/20 21:22
cog5566:覺得翻成"格狀自動機"比較不會讓人誤會(讓我這種英文爛的) 04/20 21:35
cog5566:我覺得他們會這樣想還滿容易理解的,畢竟科學的一個目標就 04/20 21:37
cog5566:是尋找最萬物最簡單的規則。而格狀自動機就是定義簡單規則 04/20 21:38
cog5566:卻可以模擬出一些生物特性。再加上他是一個平行處理的動態 04/20 21:40
cog5566:系統,而且也遵照局部性。這樣就和我們概念上的宇宙是相同 04/20 21:41
cog5566:性質的。(當然這些性質有沒有定論應該還早。這一期個科) 04/20 21:42
cog5566:學人就在講局部性的爭議)。不過想法就是如果宇宙的時空性 04/20 21:44
cog5566:質,在微觀上是以離散的方式組成的話,格狀自動機就可以模 04/20 21:45
cog5566:擬許多現象。我覺得這個遊戲倒不是真的想要把宇宙模擬的一 04/20 21:49
cog5566:模一樣,而是想要展現一些我們認為是複雜的現象,如生物活 04/20 21:55
cog5566:動,可以由簡單的規則和數位運算的方式創造出來。 04/20 21:56
takanaka:一個有趣的問題是科學的目的何在 04/21 00:36
takanaka:我想多少是在求真與求簡之間找到平衡 04/21 00:37
takanaka:對一個複雜系統的科學解釋必定要比所觀察到的更簡單 04/21 00:38
takanaka:不然一般的結局就是循環解釋或是根本沒解釋 04/21 00:39
takanaka:比方說我們要解釋為什麼我們可以辨識人臉 04/21 00:40
takanaka:一個古老的循環解釋為因something in the head可以辨識 04/21 00:44
takanaka:所以這個問題到底人臉是怎麼被辨識的還是沒有被回答 04/21 00:45
takanaka:儘管scope從人變成something in the head再變成大腦等等 04/21 00:46
takanaka:這是為什麼資訊處理的演算法則通常是被抽象化來分開研究 04/21 00:47
takanaka:因為reduce了physical scope仍未必能回答機制上的問題 04/21 00:48
sardine:求真與求簡的平衡也是數學跟自然界的鴻溝... 04/21 01:10
sardine:我對心理學跟社會科學部份不了解 04/21 01:11
sardine:不過就生物資訊方面 多半的人都希望越簡越好 04/21 01:12
sardine:可是這個簡化的過程並沒有一個標準或公認的定論.. 04/21 01:12
sardine:要一直延伸到組織/細胞層級以下 對標準化的共識才比較深 04/21 01:13
sardine:舉個例來說~在生物的野調上~~樣區邊界半外半內的區域該如 04/21 01:16
sardine:何計量~~~這個只有經驗~並沒有統計標準. 04/21 01:16
sardine:可是對幾百千億萬平方公里的的母群體來說 這種誤差絕對 04/21 01:18
sardine:超過數學上付予機率跟統計可容許的標準 04/21 01:18
sardine:但我在野調時也不怎麼在意這種事... 04/21 01:19
sardine:光是肯定無異議的樣區內~對生物特徵的量化 每個調查員的主 04/21 01:21
sardine:觀意識就已經造成我不太能接受的誤差了.. 04/21 01:21
sardine:只是生態學家似乎不太在意這種事 團隊中的大家長說了就算 04/21 01:22
sardine:在物理/化學對狀態的描述還滿精確的 每種現象背後都有種 04/21 01:25
sardine:強大的趨動力而且幾乎是不可違背的 也經過實驗 (直接證明 04/21 01:26
sardine:or反證) 04/21 01:28
sardine:這種背後的趨動力相對於數學就是公理 04/21 01:28