元胞自動機

元胞自動機

元胞自動機(Cellular Automaton,複數為Cellular Automata,簡稱CA,也有人譯為細胞自動機、點格自動機、分子自動機或單元自動機)。是一時間和空間都離散的動力系統。散布在規則格網 (Lattice Grid)中的每一元胞(Cell)取有限的離散狀態,遵循同樣的作用規則,依據確定的局部規則作同步更新。大量元胞通過簡單的相互作用而構成動態系統的演化。

基本解釋

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

具體解釋

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

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

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

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

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

分別描述

從另一角度,元胞自動機可視為動力系統,因而可將初試點、軌道、不動點、周期軌和終極軌等一系列概念用到元胞自動機的研究中,上述分類,又可以分別描述為(譚躍進,1996;謝惠民,1994;李才偉、1997);

⑴均勻狀態,即點態吸引子,或稱不動點;

⑵簡單的周期結構,即周期性吸引子,或稱周期軌;

⑶混沌的非周期性模式,即混沌吸引子;

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

套用

元胞自動機可用來研究很多一般現象。其中包括通信、信息傳遞(Communicahon)、計算(Compulation)、構造 (Construction)、生長 (Growth)、複製 (Reproduction)、競爭(Competition)與進化(Evolutio,])等(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)。

其他

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

相關搜尋

熱門詞條

聯絡我們