第十二講  知識運作-細胞自動機(cellular automata; CA)（PPT）

☉本章重點

1、 細胞自動機(cellular automata; CA)的定義與組成

2、 細胞自動機的發展歷史

3、 細胞自動機的特點

4、 細胞自動機的運作

5、 空間性細胞自動機的發展

6、 參考資料 （Visual Simulation Based on Two-dimensional Surface Cellular Automata。賴進貴：1.細胞自動機與GIS結合 2.學術時髦或創新？─細胞自動機本質之探討。）及相關網站

一、 細胞自動機(cellular automata; CA) 的定義與組成

一種十分新穎的數學演算法。是近年來空間研究領域發展快速的一種空間模擬工具。係在網格資料結構上（將每一個網格視為一個細胞），利用其空間近鄰性，模擬其空間的自動演化過程，故在具空性的生態模擬、土地利用衝擊與變遷、都市演化等的模擬課題皆是分適合。這是一個抽象的圖案產生機制，一旦給定初始值，即可按預先設定的規則，隨時間改變形狀。以人工生命的角度來看，細胞自動機可視為一個讓許多生命生存繁殖的世界(world)，類似地球孕育各種生物一般。它包含許多細胞，各取一值（通常是二值的0或1），其值與周圍細胞互相影響，整個平面即在不同時刻顯出不同特徵（例如，0表燈滅，1表燈明，則可構成各細胞格子有明有暗的圖型）。因此，細胞自動機是由規則（rules）所控制的數位建構，可產生各種類型（pattern）；它的細胞會「死」（關掉）、「再生」（影響周圍細胞成一樣），整體表現類似同時互動、「平行處理」。

設計一個細胞自動機需包含兩部份：

(1.)各個細胞的初始狀態(即整個自動機的初始形狀)

(2.)根據舊細胞產生新細胞的規則.

一、 細胞自動機的發展歷史

人稱電腦之父的馮諾曼（John von Neumann）在1940年代開始研究細胞自動機（cellular automaton）或譯格子自動機，於1950 年代便發明細胞自動機以求發展具有自我複製能力的計算工具，促成self-replicating automata 的發展。因為它狀似一大片格子，原為離散的（discrete）時空模型，做為模擬任何系統之用，例如，模擬生物細胞活動、組織族群；模擬化學分子系統與結晶成長的動力學；模擬物理粒子互動；模擬電腦科學中的平行處理等。。1970 年，John Conway 依據Von Neumann 的想法進一步發展成電腦上的生命遊戲（Game of Life ），從此CA 的概念逐漸普及到相關領域。細胞自動機的人工生命具有動態、自我複製的特性，而其宏觀（Macro ）的演化現象是由微觀(Micro)層次的作用力在主導，而所謂的微觀作用是一個演化單元和其周遭環境中的關係，演化過程呈現一種具演化規則的明確機制。其演化的本身具有空間交互作用的特性，CA 所模擬或預測的現象也就具有空間幸，是一種具空間觀點的演化模式。巨觀的環境變化則需透過細胞的屬性變化與演化規則的調整來調適。

二、 細胞自動機的特點

細胞自動機有三個特點：

1、平行計算 (parallel computation)

每一細胞應可以同步運作，可由平行處理器來進行運作。

2、局部的 (local)

細胞的狀態變化只受周遭一定距離內細胞的影響，全局的影響需透過細胞值的設定與運作規則的變化來執行。

3、一致性的 (homogeneous)

每一細胞都受同一組規則指導進行運作與相互影響。

三、 細胞自動機的運作

CA 的組成要素包括：網格、網格型態、鄰近空間、演化規則等四項（Batty et al., 1997 ）。現就降此四項組成分別說明如下。

1 、 網格（cells ）

CA 是由一組的網格（或稱細胞）所構成。理論上這些網格可以是任何幾何形狀，甚至可以立體的單元，不過目前大部分的CA 研究都是以規則排列的方格為主，其空間結構和網格式資料模式的結構相同，及為一2維的矩陣。

2 、 網格狀態（states ）

每一個網格的內容是由一組有限的狀態來顯示，這些狀態的值域可以是二元的（Binary），如：活的、死的；空的（NULL）、已經被佔據的。也可以是多元的類別集合，例如：建地、空地、商業用地、住宅用地等土地利用類型。狀態，亦可以是實數或等第尺度的值域。在任一時間，每一個網格都將呈現這一組狀態中的唯一特定值。

3 、 鄰近區(neighborhood)

CA 中每一個網格的狀態，會隨著其鄰近地區內的網格狀態來進行變化。設計一個CA 時需要界定其會相互影響的鄰近區大小。以網格式的資料結構而言，鄰近區可以是中心網格最近的周遭網格或一定距離內的所有網格。

4 、 演化規則

每一個網格在下一個時間點的狀態，是由其目前的型態及其鄰近區內網格對此網格影響的總組合而決定。由一條條明確的規則決定下一時間點型態的演變。在上述的時空結構下，CA 的演化循環是在一個離散的（discrete ）時間序列下（… ,t-1, t, t+1, …），所有網格依據演化規則進行同步更新。

其細胞自動機的規則如下：

A、活細胞如果有二或三個鄰居則可以活到下一世代, 否則就會死於獨居或壅擠 。

B、死細胞處如果恰好有三個活細胞鄰居，則可生出活細胞 ( 就某種意義上來說可視之為"繁殖")。

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

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

圖1. CELL Matrix的相互影響

圖2. 一個CA擴散模擬的過程

圖3.多層次CELL之模擬

圖4. 多層次模擬作用之剖面

圖5. 光線的穿透與反射模擬

圖6. 污染的擴散模擬過程結果

四、 空間性細胞自動機的發展

早在CA被用在都市及環境模擬之前，地理資訊科學理論派的學者，如Tobler (1979)、Couclelis (1988, 1991, 1997) 即已經針對CA的特性及其和地理學的關係進行探討。由於碎形（fractal）、混沌（chaos）、複雜科學(complexity)等相關理論與技術之下的產物。目前CA仍在學術研究階段，將來可能成為GIS分析或模擬模組的功能之一。

1.空間尺度與非空間因子的影響會決定CA不同的考慮。

1） 在尺度層面而言

不同的空間規模對於模式的要求和定位會有所不同。大規模空間的研究，對於具體的位置不是那麼重要，重要的是機制和型態，小規模的空間對於實際區位的準確性要求將會比較高。空間規模的另一個影響是網格的大小和空間意涵。

2） 非空間因子的影響

決策層面的許多因素是非空間的，有些學者引入宏觀─微觀的架構來處理非空間的因素，例如在土地利用便前模擬中，將經濟發展、投資、人口成長等視為宏觀的被賦予條件（given conditions），依據這些因子推算出各類土地利用的面積，再利用CA 來推算各種土地利用的位置。

在White and Engelen(1997)的模式中，土地使用的轉變受到三個因素的影響：（1）各類土地利用的需求總量（2）土地本身的特性（3）鄰近區的土地利用形式。其中的第一項因素就被認為是宏觀因素，由經濟和人口成長的模式來計算，不屬於CA 的部份。非空間因素是CA模式所不能掌控，宏觀─微觀觀念的納入，解決大環境既成條件的問題，然而非空間的因素不全然可以化約成宏觀條件，例如道路建設、土地分區管制、個別土地所有人的投資決策等，這些既不是宏觀、也非空間的因素，正是CA模式所不能照顧的缺憾，但可能可以透過多層次細胞來加入此些微觀的因子。

2、 CA演化模式屬性、時空面向

演化規則是CA模式的核心。每一條演化規則包含三個面向的因素：屬性、時間、空間。

1） 屬性的層面

每一個網格的演化到底受到哪些因素的影響、權重多少，這些是偏重屬性層面的因素。針對屬性層面，每一個CA 模式需要確定每一條規則所要涵蓋的因素。目前的CA 模式普遍採用的作法包括：

專家訪談結合AHP 的作法(Wu, 1998)，或是由研究者逕行選定要納入的因子（Clarke et al., 1997 ）。這方面的因子選定是模式的內涵，由研究者選定。也有研究者的作法是由真實的資料，利用Monte Carlo 方法來計算出權重。

2） 在時間面向

CA 的演變是在離散的時間序列中進行持續的演化。每該段時間內是靜止的，而在特定時間做全面的更新。時間因素對於CA模式的影響和CA的應用目的有關。如果將CA當作空間規劃工具，則演化的目的在於尋求最適區位所在，演化的終點是以達到土地需求為目的，以White and Engelen的作法(1997)，他們的模式是由遞迴的作法一次次的演化，直到選擇出滿足理想的土地利用區位和面積，時間因素在模式中並不具有實質的意涵。然而如果以CA為模擬探討的基礎，則每一次演化是兩個時間點之間的離散時段，則演化時間的長短就會影響演化的次數，這種概念就如同採取複利法計算存款利率的道理相通，以年為單位或以月為單位，所累積的成果會有所差異。這種情形下時間點的長短會造成演化結果的差異。真實的現象是否真是每一年平滑進行，或是呈現如地震活動般，在累積一定能量後有階段性的巨變，這其實是值得關切的。目前的模擬者往往受限於所取得資料的時間限制來設計演化的時間，實際上演化的過程和資料點也不見得相同。時間的因素是模式建構者所需要思考的。

3 ）空間結構

目前一般的CA模式都是以方正的規則網格為單元。CA中的網格有兩個層面的意義。一、它代表CA演化的基本單位；二、它同時是影響演化的鄰近區。這兩個層面的意義對於CA演化分別有其影響，值得我們思考。網格的空間結構可以進一步從網格大小和結構、鄰近區大小、距離作用等三個層面來討論。

A、網格大小和結構

作為演化的單元，到底每一個網格應該定在多大？演化單元應該要反應CA模式中所謂的微觀作用，網格大小應該要能代表真正的土地利用變遷單元。在都市的尺度，作用單元最有可能是一塊塊地籍上的坵塊（parcel），也是可以進行變更利用的基本單元。這種坵塊的變遷往往是因為它鄰近道路、或周圍已經開發，由於接鄰（contiguity）的關係或相近（proximity）而引發改變。由於實際的土地坵塊大小差異甚大，如果能直接以向量式的結構來表現實際的土地坵塊，將會提升CA模式的真實性. Shi and Pang (2000)嘗試以Voronoi作為CA的資料結構，其目的即在於測試打破現有CA的限制。如果用規則網格而進行，這些網格被視為一個作用的單元，約略等於一個實際的向量多邊形。這方面的網格訂定應該要有所根據，目前很多的分析都是因為資料的解析度作為依據，沒有明確的道理可言。White 等（1993）在土地利用變遷研究上所使用的網格解析度即為500公尺X500公尺。這樣的網格大小訂定，必須自圓其說。

B、 鄰近區範圍

每一個網格也是構成鄰近區的一部份。在CA的規則中，每一個演化是受到鄰近區的組成影響。鄰近區有多大、如何影響，是規則中的重要部分。原始CA的鄰近區是中心網格上下左右四個網格所構成的Von Neumann Neighborhood，或以其周遭的八個網格所構成的Morre Neighborhood (Batty et al.,1997)。鄰近區訂定的假設是這個地區的組成，會影響到中心網格的演變。在土地利用模式中，有許多研究者是以一定半徑去選取一個圓形區域中的苦格，並假設這個地區是均質的。如果採用半徑─面積作為比例，如White & Engelen (1993) 用了113格，則網格大小並不構成立即的影響，然而如果是以3X3或5X5 的網格之間的接鄰關係為基礎，則網格大小的影響就會非常大，考量的必需要很周詳。圖層網格解析度的影響，在實際應用上將牽涉到如何選擇地理資料的解析度。

4）距離作用

不同網格之間的影響，反映在鄰近區的大小，也反應因為距離的大小所帶來的權重關係。不同的因素或現象的影響距離是不一樣的。例如，對於一個空地網格轉換成住宅區網格的可能性而言，鄰近商業區或工廠等就業機會來源可視為一項正面的因素，而這樣正面因素的影響距離可能高達數十公里，如果居民願意接受長距離通勤。而鄰近公園、綠地的優勢，可能只在5分鐘的路程。影響範圍的距離長短顯然是因個別因素的特性而異。距離所帶來的權重也有正負的差異。有些現象是正向的因素，有些則是負向。例如，近鄰垃圾掩埋場、高速公路沿線的噪音等，可能帶來負面影響，而接近公園綠地、高速公路交流道可能又是正向的影響。這些正副作用可能發生在不同的因子之間。

3、CA研究的兩個基本取向

尋求CA的演化規則，除了是一種手段外，也可以是一種目的。對於將CA當成瞭解都市演化或土地利用變遷的研究者而言，找尋到規則就是找到演化的機制，從而可以瞭解演化的因素和作用力，因此尋找規則本身即是一種目的。尋找規則有兩種方法可以採行，一種是從資料中學習，另一種是由模擬產生。

1）從資料或案例中歸納學習產生模式

從實際資料中尋找規則的作法，比較偏向是資料探索（data mining）的理念，從資料中尋求因子之間的關係。這樣的學習結果不見得是完整的模式，然而可以顯示之間的關係。以資料探索（data mining）作法，需要提供大量的資料，並且要選擇相關的因素加入土地適宜性的考量。另一個方式是把土地適宜的因素考量，當成學習的一部份，如此資料探索的結果將會反映土地適宜性的因素。

2）由舊知識直接設計模式

相對於由資料學習的由下而上（bottom- up）作法，另一種方法是直接建立模式，由模式中的演化和真實資料的比對，來產生及探討CA的規則。至於模式的主旨要反應什麼樣的資訊，則視CA的功能而定。例如，有些作為都市發展型態的討論。這樣的模式發展，必需要能包括檢核與修正的功能，如此所發展的模式將可以比較忠實的反應演化現象的本質。