元胞自動機

不同於一般的動力學模型，元胞自動機不是由嚴格定義的物理方程或函數確定，而是用一系列模型構造的規則構成。凡是滿足這些規則的模型都可以算作是元胞自動機模型。因此，元胞自動機是一類模型的總稱，或者説是一個方法框架。其特點是時間、空間、狀態都離散，每個變量只取有限多個狀態，且其狀態改變的規則在時間和空間上都是局部的。

元胞自動機是一個像圖1中所示的那種燈泡陣列，每個燈有“開”和“關”兩種狀態，每個燈與周圍的8個燈相連（邊上的燈會認為與另一邊的相連，比如最左邊的燈，會認為與最右邊的燈相連。這樣所有燈都與8個燈相連）。初始階段，部分燈開部分燈關。元胞自動機像CPU一樣一步一步地進行計算（如果不理解，可以參考劉慈欣《三體》裏的人列計算機，有人喊號子讓大家一步一步地動作）。每個元胞自動機有一個規則，來説明每個燈怎麼根據之前周圍8個燈及自己的狀態決定自己下一步時的狀態（比如一種規則可以是：採用鄰域佔多數的狀態。圖1中即展示了這種規則下下一步此元胞自動機會怎麼變化）。這種計算模型，是馮諾依曼提出的，稱為馮諾依曼結構。與圖靈機的計算能力是等價的。

（思想與圖的來源：梅拉妮米歇爾《複雜》2008 ^[2]  。這也許只是元胞自動機的一種）

元胞自動機的構建沒有固定的數學公式，構成方式繁雜，變種很多，行為複雜。故其分類難度也較大，自元胞自動機產生以來，對於元胞自動機分類的研究就是元胞自動機的一個重要的研究課題和核心理論，在基於不同的出發點，元胞自動機可有多種分類，其中，最具影響力的當屬S. Wolfram在80年代初做的基於動力學行為的元胞自動機分類，而基於維數的元胞自動機分類也是最簡單和最常用的劃分。除此之外，在1990年，Howard A.Gutowitz提出了基於元胞自動機行為的馬爾科夫概率量測的層次化、參量化的分類體系（Gutowitz,H. A.,1990）。下面就上述的前兩種分類作進一步的介紹。同時就幾種特殊類型的元胞自動機進行介紹和探討S. Wolfrarm在詳細分析研究了一維元胞自動機的演化行為，並在大量的計算機實驗的基礎上，將所有元胞自動機的動力學行為歸納為四大類（Wolfram. S.，1986）：

⑴平穩型:自任何初始狀態開始，經過一定時間運行後，元胞空間趨於一個空間平穩的構形，這裏空間平穩即指每一個元胞處於固定狀態。不隨時間變化而變化。

⑵週期型：經過一定時間運行後，元胞空間趨於一系列簡單的固定結構（Stable Patterns）或週期結構（Perlodical Patterns）。由於這些結構可看作是一種濾波器（Filter），故可應用到圖像處理的研究中。

⑶混沌型：自任何初始狀態開始，經過一定時間運行後，元胞自動機表現出混沌的非週期行為，所生成的結構的統計特徵不再變止，通常表現為分形分維特徵。

⑷複雜型：出現複雜的局部結構，或者説是局部的混沌，其中有些會不斷地傳播。

從另一角度，元胞自動機可視為動力系統，因而可將初始點、軌道、不動點、週期軌和終極軌等一系列概念用到元胞自動機的研究中，上述分類，又可以分別描述為：

⑴均勻狀態，即點態吸引子，或稱不動點；

⑵簡單的週期結構，即週期性吸引子，或稱週期軌；

⑶混沌的非週期性模式，即混沌吸引子；

⑷這第四類行為可以與生命系統等複雜系統中的自組織現象相比擬，但在連續系統中沒有相對應的模式。但從研究元胞自動機的角度講，最具研究價值的具有第四類行為的元胞自動機，因為這類元胞自動機被認為具有"突現計算"（Emergent Computation）功能，研究表明，可以用作廣義計算機（Universal Computer）以仿真任意複雜的計算過程。另外，此類元胞自動機在發展過程中還表現出很強的不可逆（lrreversibility）特徵，而且，這種元胞自動機在若干有限循環後，有可能會 "死"掉，即所有元胞的狀態變為零。

元胞自動機可用來研究很多一般現象。其中包括通信、信息傳遞（Communication）、計算（Compulation）、構造（Construction）、材料學、複製（Reproduction）、競爭（Competition）與進化（Evolution）等（Smith A.,1969;Perrier，J.Y.,1996）。同時。它為動力學系統理論中有關秩序（Ordering）、紊動（Turbulence）、混沌（Chaos）、非對稱（Symmetry-Breaking）、分形（Fractality）等系統整體行為與複雜現象的研究提供了一個有效的模型工具（Vichhac。G，1984; Bennett，C,1985）。

元胞自動機自產生以來，被廣泛地應用到社會、經濟、軍事和科學研究的各個領域。應用領域涉及社會學、生物學、生態學、信息科學、計算機科學、數學、物理學、材料學、化學、地理、環境、軍事學等。

元胞自動機用於研究經濟危機的形成與爆發過程、個人行為的社會性，流行現象，如服裝流行色的形成等。在生物學中，元胞自動機的設計思想本身就來源於生物學自繁殖的思想，因而它在生物學上的應用更為自然而廣泛。例如元胞自動機用於腫瘤細胞的增長機理和過程模擬、人類大腦的機理探索（Victor.Jonathan.D.，1990）、艾滋病病毒HIV的感染過程（Sieburg，H.B.，1990）、自組織、自繁殖等生命現象的研究以及最新流行的克隆 （Clone）技術的研究等（ErmentroutG.B.，1993）。

元胞自動機用於兔子-草，鯊魚-小魚等生態動態變化過程的模擬，展示出令人滿意的動態效果；元胞自動機還成功地應用於螞蟻、大雁、魚類洄游等動物的羣體行為的模擬；另外，基於元胞自動機模型的生物羣落的擴散模擬也是當前的一個應用熱點。在信息學中。元胞自動機用於研究信息的保存、傳遞、擴散的過程。另外。Deutsch（1972）、Sternberg（1980）和Rosenfeld（1979）等人還將二維元胞自動機應用到圖像處理和模式識別中 （WoIfram.S.，1983）。

元胞自動機可以被看作是並行計算機而用於並行計算的研究（Wolfram.S.1983）。另外。元胞自動機還應用於計算機圖形學的研究中。

在數學中，元胞自動機可用來研究數論和並行計算。例如Fischer（1965）設計的素數過濾器（Prime Number Sieves）（Wolfram,S.1983）。

除了格子氣元胞自動機在流體力學上的成功應用。元胞自動機還應用於磁場、電場等場的模擬，以及熱擴散、熱傳導和機械波的模擬。另外。元胞自動機還用來模擬雪花等枝晶的形成。

元胞自動機可用來通過模擬原子、分子等各種微觀粒子在化學反應中的相互作用，而研究化學反應的過程。例如李才偉（1997）應用元胞自動機模型成功模擬了由耗散結構創始人I·Prgogine所領導的Brussel學派提出的自催化模型---Brusselator模型，又稱為三分子模型。Y·BarYam等人利用元胞自動機模型構造了高分子的聚合過程模擬模型，在環境科學上，有人應用元胞自動機來模擬海上石油泄露後的油污擴散、工廠周圍廢水、廢氣的擴散等過程的模擬。

元胞自動機模型可用來進行戰場的軍事作戰模擬，提供對戰爭過程的aq理解（譚躍進等，1996）。

元胞自動機作為一種動態模型，更多的是作為一種通用性建模的方法，其應用幾乎涉及社會和自然科學的各個領域。