細胞自動機 (Cellular Automata )

Presentation on theme: "細胞自動機 (Cellular Automata )"— Presentation transcript:

1 細胞自動機 (Cellular Automata )
格狀自動機

2 Sierpinski's Triangle Sierpinski's Triangle is a very famous fractal that's been seen by most advanced math students. This fractal consists of one large triangle, which contains an infinite amount of smaller triangles within. The infinite amount of triangles is easily understood if the fractal is zoomed in many levels. Each zoom will show yet more previously unseen triangles embedded in the visible ones. Creating the fractal requires little computational power. Even simple graphing calculators can easily make this image. The fractal is created pixel by pixel, using random numbers; the fractal will be slightly different each time due to this. Although, if you were to run the program repeatedly, and allow each to use an infinite amount of time, the results would be always identical. No one has an infinite amount of time, but the differences in the finite versions are very small. To generate this fractal, a few steps are involved. First, initial X and Y values should be chosen, either by the program or the user. The values used have little effect on the fractal. Regardless of what's chosen, the same triangle will be created. Next, the program must create a random number, between 0 and 1. Then, three possible routes can be taken.

3 If the random number is less then 1/3, then the following equations should be applied to X and Y.
xn = 0.5 * (xn-1 + 1) yn = 0.5 * yn-1 If the random number is between 1/3 and 2/3, then these equations should be used. xn = xn-1 * 0.5 yn = yn-1 * 0.5 If the number is greater than 2/3, the the following equations should be applied. xn = 0.5 * (xn ) yn = 0.5 * (yn-1 + 1) Now that X and Y have changed, the point should be plotted on the screen. Finally, loop back to the random number generation and start over again. Only a few hundred iterations are needed to begin to see the triangles. A few thousand pixels will produce a good image.

4 Sierpinski's Triangle

5 細胞自動機 (cellular automata; CA )
細胞自動機的定義與組成 細胞自動機的發展歷史 細胞自動機的特點 細胞自動機的運作 細胞自動機的發展

6 細胞自動機的定義與組成 一種十分新穎的數學演算法。在網格資料結構上（將每一個網格視為一個細胞），利用其空間近鄰性，模擬其空間的自動演化過程。 這是一個抽象的圖案產生機制。給定初始值，即可按預先設定的規則，隨時間改變形狀。以人工生命的角度來看，細胞自動機可視為一個讓許多生命生存繁殖的世界(world)，類似地球孕育各種生物一般。

7 它包含許多細胞，各取一值（通常是二值的 0或1），其值與周圍細胞互相影響，整個平面即在不同時刻顯出不同特徵（例如，0表燈滅，1表燈明，則可構成各細胞格子有明有暗的圖型）。
細胞自動機是由規則（rules）所控制的數位建構，可產生各種類型（pattern）；它的細胞會「死」（關掉）、「再生」（影響周圍細胞成一樣），整體表現類似同時互動、平行處理。 設計一個細胞自動機需包含兩部份： 1.各個細胞的初始狀態(即整個自動機的初始形狀) 2.根據舊細胞產生新細胞的規則.

8 細胞自動機的發展歷史 人稱電腦之父的馮諾曼（John von Neumann）在1940年代開始研究細胞自動機（cellular automaton）或譯格子自動機，於1950 年代便發明細胞自動機以求發展具有自我複製能力的計算工具，促成self-replicating automata 的發展。 因為它狀似一大片格子，原為離散的（discrete）時空模型，做為模擬任何系統之用，例如，模擬生物細胞活動、組織族群；模擬化學分子系統與結晶成長的動力學；模擬物理粒子互動；模擬電腦科學中的平行處理等。 1970 年，John Conway 依據Von Neumann 的想法進一步發展成電腦上的生命遊戲（Game of Life ），從此CA 的概念逐漸普及到相關領域。

9 細胞自動機的人工生命具有動態、自我複製的特性，而其宏觀（Macro ）的演化現象是由微觀(Micro)層次的作用力在主導，而所謂的微觀作用是一個演化單元和其周遭環境中的關係，演化過程呈現一種具演化規則的明確機制。其演化的本身具有空間交互作用的特性，CA 所模擬或預測的現象也就具有空間幸，是一種具空間觀點的演化模式。巨觀的環境變化則需透過細胞的屬性變化與演化規則的調整來調適。

10 馮紐曼(von Neumann) Von Neumann（ ），匈裔美籍數學家，生於布達佩斯，卒於華盛頓特區。他是廿世紀少見的數學科學通才，在許多領域都有重要的基本貢獻。 Von Neumann 是猶太人。原姓Neumann，因為父親買下爵位，才加上貴族專稱的「von」。他自幼穎異，記憶力過人，對數學有驚人的天份，但父親希望他從商，幾經折衝，他同時在布達佩斯大學學數學，又在柏林大學學化學（後轉到蘇黎士學化工）。但即使在蘇黎士，他仍與知名數學家 Weyl 與 Polya 交遊。Polya 曾經這樣描述 Von Neumann 「他是我唯一害怕的學生。在課堂如果我提出一個當時未解的問題，通常他在下課後就會直接來找我，給我幾頁完整的解答。」

11 1926年 Von Neumann 以一篇集合論的論文獲得布達佩斯大學的博士學位，然後以 Rockefeller 獎學金前往哥廷根大學跟隨 Hilbert 作博士後研究，並在柏林，漢堡講學。Von Neumann 在廿餘歲時已經是數學圈中公認的年輕天才。 1930年 Von Neumann 應 Veblen 之邀，到普林斯頓大學客座，1931年普林斯頓大學即授予教授職位，1933年他成為新成立的普林斯頓高等研究院終身職院士。Von Neumann 的家庭宴會在普林斯頓非常熱鬧知名，這在數學家中是很少見的。

12 （5）Ergdic（遍歷性）定理的証明（1938）。
綜論 Von Neumann 的數學成就，大致如下： （1）初期工作以數理邏輯（尤其是公設集合論）、測度論、實分析為主。 （2）在《Mathematische Grundlagender Quantenmachanik》（1932）中， Von Neumann 為當時的量子力學打下堅實的數學基礎。 （3）自1929起，Von Neumann 即從事算子代數的先驅性工作，在 年間 Von Neumann 與 Murray 為後來所謂的 Von Neumann 代數寫下系列基本的文章。 （4）Von Neumann 為對局論的發明人，他首先証明零和對局的 minmax 定理，並與 Morgenstern 合著《對局論與經濟行為》，對社會科學、生命科學影響深遠。 （5）Ergdic（遍歷性）定理的証明（1938）。 （6）Von Neumann 對應用數學的興趣，從流體力學始，並對非線性偏微分方程產生莫大的興趣。而對他而言，數值計算是最可能的「實驗」方法，這也使 Von Neumann 成為今日電腦之奠基者，並因此發展 cellular automata 的理論。

13 另外 Von Neumann 也是氫彈的催生者，1940年起他即熱心 參與美國的各項國防計劃或實驗室，也因此獲得各式各樣的數學或非數學的獎章。

14 Cellular Automata and Complexity: Collected Papers
by Stephen Wolfram Are mathematical equations the best way to model nature? For many years it had been assumed that they were. But in the early 1980s, Stephen Wolfram made the radical proposal that one should instead build models that are based directly on simple computer programs. Wolfram made a detailed study of a class of such models known as cellular automata, and discovered a remarkable fact: that even when the underlying rules are very simple, the behavior they produce can be highly complex, and can mimic many features of what we see in nature. And based on this result, Wolfram began a program to develop what has become A New Kind of Science. The results of Wolfram's work found many applications, from the so-called Wolfram Classification central to fields such as artificial life, to new ideas about cryptography and fluid dynamics. This book is a collection of Wolfram's original papers on cellular automata and complexity. Some of these papers are widely known in the scientific community; others have never been published before. Together, the papers provide a highly readable account of what has become a major new field of science, with important implications for physics, biology, economics, computer science and many other areas. Published (1994): ISBN (hardcover) ISBN (paperback)

15 細胞自動機的特點 細胞自動機有三個特點： 1、平行計算 (parallel computation)
每一細胞應可以同步運作，可由平行處理器來進行運作。 2、局部的 (local) 細胞的狀態變化只受周遭近距離細胞的影響，全局的影響需透過細胞值的設定與運作規則的變化來執行。 3、一致性的 (homogeneous) 每一細胞都受同一組規則指導進行運作與相互影響。

16 細胞自動機的運作 CA 的組成要素包括：網格、網格狀態、鄰近空間、演化規則等四項。

17 1 、 網格（cells ） CA 是由一組的網格（或稱細胞）所構成。理論上這些網格可以是任何幾何形狀，甚至可以立體的單元，不過目前大部分的CA 研究都是以規則排列的方格為主，其空間結構和網格式資料模式的結構相同，及為一2維的矩陣。 2 、 網格狀態（states ） 每一個網格的內容是由一組有限的狀態來顯示，這些狀態的值域可以是二元的（Binary），如：活的、死的；空的（NULL）、已經被佔據的。也可以是多元的類別集合，例如：建地、空地、商業用地、住宅用地等土地利用類型。狀態，亦可以是實數或等第尺度的值域。在任一時間，每一個網格都將呈現這一組狀態中的唯一特定值。

18 3 、 鄰近區(neighborhood) CA 中每一個網格的狀態，會隨著其鄰近地區內的網格狀態來進行變化。設計一個CA 時需要界定其會相互影響的鄰近區大小。以網格式的資料結構而言，鄰近區可以是中心網格最近的周遭網格或一定距離內的所有網格。 4 、 演化規則 每一個網格在下一個時間點的狀態，是由其目前的型態及其鄰近區內網格對此網格影響的總組合而決定。由一條條明確的規則決定下一時間點型態的演變。在上述的時空結構下，CA 的演化循環是在一個離散的（discrete ）時間序列下（… ,t-1, t, t+1, …），所有網格依據演化規則進行同步更新。

19 細胞自動機的規則如下： A、活細胞如果有二或三個鄰居則可以活到下一世代, 否則就會死於獨居或壅擠 。 B、死細胞處如果恰好有三個活細胞鄰居，則可生出活細胞 ( 就某種意義上來說可視之為“繁殖”)。 細胞自動機可以遠較康威所設計的複雜得多，在細胞活動的空間上,可以是一維的，二維的，三維的,（多層的），或更高維，細胞的狀態可以有很多種，規則可以非常複雜，透過不同的設計，細胞自動機可以展現無限的多樣性，其中最讓人驚異的是有些細胞自動機可以產生存在於大自然的東西，例如貝殼上的圖案,、雪花的結構,、蜿蜒的河流 ... 等等。

20 宇宙就是一種極其複雜的細胞自動機? 有些研究學者更進一步猜測我們存在的這個宇宙是否就是一種極其複雜的細胞自動機，我們的宇宙的確與理論上的細胞自動機有很多相似的地方，像是上述細胞自動機的三個特點宇宙也都符合，宇宙是平行處理的，宇宙中的每一點受鄰近狀態的影響最大，宇宙各處遵循同樣的自然律(homogeneous)，比較不一樣的地方是在空間上及時間的進行上細胞自動機都是斷續的(descrete)，但是宇宙"似乎"都是連續的(continuous), 不過科學家也還不敢斷定是否如此，也許以後可以證明在極小尺度上空間與時間都是斷續的。不管怎樣，細胞自動機與宇宙有很大的關連，至少可以用它來模擬宇宙的運作及生命的行為模式，而不只是數學上的一個理論。

21 細胞自動機的發展 結合碎形（fractal）、混沌（chaos）、複雜科學(complexity)等相關理論與技術，細胞自動機(CA)將來可以成為有用的模擬工具。

22

23

24

25

26 一維 CA Rule table: Lattice: r = 1 1 1 1 1 1 1 t=0 t=1 1 1 1 1 t=2 1 1 1 1

27 Rule table: (GKL CA) Lattice: r = 1 1 1 1 1 1 1 t=0 t=1 1 1 1 1 1 1 t=2 1 1 1 1 1 1

28 Cellular Automata links

29 Cellular Automata Tutorial
Cellular Automata Gallery Mirek's Java Cellebration v.1.50  Modern Cellular Automata George Maydwell's Cellular Automata Page Home of SARCASim 一維細胞自動機，與其規則（一） 一維細胞自動機的有趣範例 細胞自動機和音樂 相關連結與資源

30 game of Life (生命遊戲) 數學家康威(John Horton Conway)在 1970年發明稱之為 game of Life(生命遊戲)的細胞自動機，他把平面(即二維的空間) 分割成很多方格子(類似圍棋棋盤)，每一格子為一細胞，每一細胞有八個鄰居，細胞有兩種狀態，“生” 或 “死”( 在電腦裡可以 1 或 0 來代表)，細胞自動機的規則如下： 1. 活細胞如果有二或三個鄰居則可以活到下一世代, 否則就會死於獨居或壅擠 。 2. 死細胞處如果恰好有三個活細胞鄰居，則可生出活細胞 ( 就某種意義上來說可視之為"繁殖")。

31 二維 CA (game of Life ) Lattice: t = 0 t = 1 1 1 1 1 1 1 1 1
活細胞 = 1 死細胞 = 0 1.活細胞如果有二或三個鄰居則可以活到下一世代, 否則就會死於獨居或壅擠 。 2.死細胞處如果恰好有三個活細胞鄰居，則可生出活細胞 ( 就某種意義上來說可視之為"繁殖") Lattice: t = t = 1 1 1 1 1 1 1 1 1

32 二維 CA 活細胞 = 1 死細胞 = 0 Lattice: t = t = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

33 A dead cell with exactly three live neighbors becomes a live cell (birth).
      

34 A live cell with two or three live neighbors stays alive (survival).

35 In all other cases, a cell dies or remains dead (overcrowding or loneliness).

36 Conway's Game of Life

37 Online Game of Life The Game of Life is not your typical computer game. It is a 'cellular automaton', and was invented by Cambridge mathematician John Conway. This game became widely known when it was mentioned in an article published by Scientific American in It consists of a collection of cells which, based on a few mathematical rules, can live, die or multiply. Depending on the initial conditions, the cells form various patterns throughout the course of the game.

38 game of Life http://serendip.brynmawr.edu/complexity/life.html
Modern Cellular Automata The Virtual cellular automaton - You better come on in my kitchen. It's going to be raining outdoors. -- Robert Johnson

39 Langton’s Ants 1. The ant takes a step forward
2. If the ant is now standing on a white point, then it paints the point black and turns 90 degrees to the right. 3. Otherwise, if the ant is standing on a black points, then it paints it white and turns 90 degrees to the left. Eight steps of Langton’s virtual ant, starting from an initially blank grid.

40 Langton's Ants

41 Langton's Ant

42 Langton's ant

43 ｅ蟻雄兵 誰說大腦發達的生物才聰明？頭腦簡單的螞蟻不但能建構驚人的地下蟻城，還將掀起一場人類電腦科技革命！
在”人不為己，天誅地滅”的天擇鐵律下，螞蟻、蜜蜂、甚至一些細菌卻選擇以相互合作為其生存策略。群體中每個個體僅執行一項動作，並針對外在情況做出簡單幾種反應。這種看似笨拙的行為卻使由動輒數萬隻個體組成的群體能極有效率的行動，甚至能表現某種程度的思考。現在這種生存行為模式已經成為科學家與工程師所師法的對象，在解決一些繁瑣的運算問題時，在電腦程式中放進一群虛擬的”螞蟻”，便能有效率的尋求最佳解答。 螞蟻是高度社會化的群體動物。當工蟻在巢穴外隨意地覓食時，發現食物的工蟻必須返回巢穴通知其他工蟻，而它的同伴們則必須跟隨它沿路留下的費洛蒙氣味，回到食物的地點。但是原先這隻工蟻所走的路徑可能並非最短路徑，其他的工蟻可能也跟著走冤枉路。所幸其他較便捷的路徑可能很快就由其他工蟻發現，並留下新的氣味以便友伴跟隨，這麼一來，蟻群便有可能找出通往食物的最短路徑。

44 這種解決問題的模式提供了專門解決繁瑣運算問題的電腦工程師們新的靈感。美國新墨西哥州聖塔菲研究所的Eric Bonabeau與其同僚在”自然”科學期刊上發表了這種新的電腦運算法。它的內容簡單的說，就是將所有可能的解算列出，再由電腦中的虛擬蟻群找出最佳答案﹔一個典型的例子就是一個推銷員如何以最短旅程造訪地圖上所有城鎮。電腦模擬一群出巢的螞蟻尋找目標，每隻虛擬螞蟻還會在它的運算路徑中留下”虛擬費洛蒙”，標示該路徑的長短。短的解算路徑比長的能夠吸引更多虛擬螞蟻﹔運算迴路中的虛擬費洛蒙也會以特定速率”蒸發”，以避免虛擬蟻群陷入次佳的解算路徑。研究人員稱這種運算為蟻群最佳化運算法(Ant Colony Optimization (ACO) algorithm)。現在ACO正被運用在計算瑞士運油卡車的運輸途徑。

45 真實的蟻群常常在開放的區域尋覓食物或標的﹔網路工程師們發現這種社會性昆蟲的特性也可運用在網路世界中。虛擬蟻群會穿梭在電腦網路中，標示最佳的通訊路徑﹔當遭遇網路壅塞的狀況時，這條路徑便不會被採用，而且替代的路徑很快便被找出。這種蟻群運算法有很高的彈性，而且能針對不同情形做出反應。英國電訊(British Telecom)目前正根據此一原理發展新的網路系統。 這種蟻群思考模式將來極有可能會應用在機器人的設計上：機器人將由共同運作的簡單操作元件組成﹔數量龐大的微機器人 (micro-robots)將比單一設計複雜的機器人更能有效執行任務，而且製造成本也會大幅降低，預料這種師法螞蟻雄兵的思考方式，將帶動新一波的科技革命。 --取材自: Bonabeau, E., Dorigo, M. & Theraulaz, G. Inspiration for optimization from social insect behaviour. Nature 406, (2000)

46 simple ant farm http://www.acme.com/software/xantfarm/
There are three Elements in the ant world: Air, Dirt, and Sand. Ants move through Air, dig up Dirt, and drop it as Sand. Ants have three Behaviors: Wandering, Carrying, and Panic. There are a few simple probabilities built in to the program that control the transitions between Wandering and Carrying. To see them Panic, try poking the ants with the cursor.

47 推銷員問題(TSP) 推銷員問題就是，給定一個有 n 個城市的集合，一個可憐的推銷員想要確實地拜訪每個城市然後再回到開始的地方。螞蟻是「有機的」、直覺的、強韌的，而且迅速（有些時候）。螞蟻王國是由一個看起很和氣的比利時人馬可‧朵麗哥（Marco Dorigo) 在觀察真正的螞蟻時得到的靈感。螞蟻可以在食物和巢穴間找到最短的路徑，所以為什麼不能用它們來解推銷員問題呢？在深入研究螞蟻王國前，我們先來看看自然界中這些神奇的螞蟻。  

48 因為螞蟻在行動的時候會釋放出一些費洛蒙，這些費洛蒙就是為什麼螞蟻會一隻一隻地跟著前面的同伴走的原因。下一隻螞蟻會跟著前一隻螞蟻走的機率跟前一隻螞蟻所釋放的費洛蒙成正比。換句話說費洛蒙越多，下一隻螞蟻會跟著走機會越大。也就是說，個體會偏好大眾的選擇。現在你可以解釋上圖的現象了嗎？ 螞蟻王國只有一個函數需要瞭解：                                     。 這個函數決定了螞蟻的下一步。t(r,s)是從城市 r到城市 s的費洛蒙強度。 e(r,s)是城市 r到城市 s的距離倒數（叫做能見度）。Mk 是螞蟻 k的記憶體，也就是說螞蟻記得它已經拜訪過的城市。每一隻螞蟻會根據從所在城市至還沒拜訪城市的機率 Pk(r,s)決定下一步。等到每一隻螞蟻完成旅行，便會分別將費洛蒙 Q散布在走過的路徑上。路徑越短，加得越多。這使得下一回合時，螞蟻們便會偏好能見度較高且費洛蒙較多的路徑。當然，每一回合結束時，一部份的費洛蒙會散發掉。這就是整個螞蟻王國運作原理。夠簡單吧？      

49 結語 細胞自動機可以遠較康威所設計的複雜得多，在細胞活動的空間上,可以是一維的，二維的，三維的,，或更高維，細胞的狀態可以有很多種，規則可以非常複雜，透過不同的設計，細胞自動機可以展現無限的多樣性，其中最讓人驚異的是有些細胞自動機可以產生存在於大自然的東西，例如貝殼上的圖案,、雪花的結構,、蜿蜒的河流 ... 等等。

50 Stephen Wolfram Cellular Automata as Simple Self-Organizing Systems (1982)

51 Cellular Automata + MIMD Parallel Computers
= CAMEL and CARPET

52 Cellular Automata

53 潛味音樂網 潛味音樂‧連網 新邏輯藝文網 澀柿子的世界 Radio Art Online Links Eddie's Jazz Page Electronic Music Foundation World Forum for Acoustic Ecology Forced Exposure 私密聆聽 用chaos的algorithm來做音樂應該不是難事， 之前試過先定義七種不同cell， 每個分別代表C D E F G A B， 做出來其實滿無聊的。 我想對cell增加定義和 繁殖/死亡 條件的修改， 應該可以做出很有趣的東西。

54 Artificial Life

55 Darwin Pond Darwin Pond is an imaginary gene pool, a primordial puddle of genetic surprises. More technically, Darwin Pond is an Artificial Life Simulation: a virtual world exhibiting the emergence of life-like behaviors. But it's more than just a fun and informative thing to watch, you can participate in this artificial life simulation by building little scenarios and setting up experiments.

56 (Artificial Intelligent)
              人工智慧 AI (Artificial Intelligent)