1、元胞自動(dòng)機(jī)調(diào)研報(bào)告,清華大學(xué)自動(dòng)化系 自45班 林子坤,1,目錄,預(yù)備知識(shí)：名詞解釋 元胞自動(dòng)機(jī)的提出及發(fā)展歷史 元胞自動(dòng)機(jī)的說明與描述 元胞自動(dòng)機(jī)的分類 元胞自動(dòng)機(jī)的實(shí)際程序運(yùn)行 元胞自動(dòng)機(jī)的意義,預(yù)備知識(shí)：名詞解釋,元胞：又可稱為基元, 是元胞自動(dòng)機(jī)的最基本的組成部分,每一個(gè)元胞都有記憶貯存狀態(tài)的功能, 或者可以說元胞就是一種狀態(tài).最簡(jiǎn)單的情況下, 元胞只有兩種可能狀態(tài); 較復(fù)雜情況下,元胞具有多種狀態(tài).系統(tǒng)中所有元胞的狀態(tài)都按照元胞自動(dòng)機(jī)的動(dòng)力規(guī)則不斷更新。 元胞空間：是元胞所分布在的空間網(wǎng)格集合（它可以是任意維數(shù)歐幾里德空間的規(guī)則劃分）。對(duì)于一維元胞自動(dòng)機(jī),元胞空間的劃分只有一種,而二

2、維元胞自動(dòng)機(jī),二維元胞空間通?？梢园慈?、正方形、六邊形三種網(wǎng)格排列。,預(yù)備知識(shí)：名詞解釋,預(yù)備知識(shí)：名詞解釋,元胞邊界：理論上的元胞空間通常是在各維上是無限的,但卻無法在計(jì)算機(jī)上實(shí)現(xiàn),因此, 我們需要定義不同的邊界條件。有周期邊界（在2維中主要指上下連接，左右連接）、固定邊界、絕熱邊界、映射邊界。 元胞鄰居：在給出規(guī)則之前,必須定義一定的鄰居規(guī)則,明確哪些元胞屬于該元胞的鄰居。在一維元胞自動(dòng)機(jī)中,通常以半徑r 來確定鄰居,距離一個(gè)胞r 內(nèi)的所有元胞均被認(rèn)為是該元胞的鄰居。二維元胞自動(dòng)機(jī)的鄰居定義較為復(fù)雜,但通常有Von. Neumann 型、Moore 型及擴(kuò)展Moore 型。,預(yù)備知識(shí)：名

3、詞解釋,元胞狀態(tài)：取值于一個(gè)有限的離散集。嚴(yán)格意義上,元胞自動(dòng)機(jī)的元胞只能有一個(gè)狀態(tài)變量, 但在實(shí)際應(yīng)用中, 往往將其進(jìn)行了擴(kuò)展。,元胞自動(dòng)機(jī)的提出及發(fā)展歷史,元胞自動(dòng)機(jī)由馮諾依曼和數(shù)學(xué)家斯塔尼斯拉夫?yàn)趵罚鋸椫福┯?948年首先提出。 1964年埃德加弗蘭克科德（關(guān)系數(shù)據(jù)庫(kù)之父）對(duì)馮諾依曼的元胞自動(dòng)機(jī)進(jìn)行簡(jiǎn)化。 1970年生命游戲誕生。 20世紀(jì)80年代斯蒂芬沃爾夫勒姆對(duì)元胞自動(dòng)機(jī)進(jìn)行簡(jiǎn)化,元胞自動(dòng)機(jī)的提出及發(fā)展歷史,20世紀(jì)90年代，元胞自動(dòng)機(jī)發(fā)展百花齊放，以美國(guó)圣達(dá)菲為代表，提出了人工生命。 進(jìn)入21世紀(jì)蒂芬沃爾夫勒姆的A MEW KIND OF Science將元胞提升到更高一層。

4、,元胞自動(dòng)機(jī)的說明與描述,元胞自動(dòng)機(jī)是離散(discrete)動(dòng)力學(xué)(dynamic), 用簡(jiǎn)單規(guī)則控制相互作用的元胞模擬復(fù)雜世界。 散布在規(guī)則網(wǎng)格中的每一個(gè)元胞去有限的離散狀態(tài)，遵循一定的局部規(guī)則做出相應(yīng)的更新，大量的元胞通過簡(jiǎn)單的相互作用夠成動(dòng)態(tài)系統(tǒng)的演化，元胞不是有嚴(yán)格的物理方程或函數(shù)確定，而是由一系列的模型構(gòu)造的規(guī)則構(gòu)成，凡是滿足這些規(guī)則的模型都是元胞自動(dòng)機(jī)。,元胞自動(dòng)機(jī)的說明與描述,元胞自動(dòng)機(jī)不同于一般的動(dòng)力學(xué)模型，元胞自動(dòng)機(jī)不是由嚴(yán)格定義的物理方程或函數(shù)確定，而是用一系列模型構(gòu)造的規(guī)則構(gòu)成。凡是滿足這些規(guī)則的模型都可以算作是元胞自動(dòng)機(jī)模型。 因此，元胞自動(dòng)機(jī)是一類模型的總稱，或者說

5、是一個(gè)方法框架。其特點(diǎn)是時(shí)間、空間、狀態(tài)都離散，每個(gè)變量只取有限多個(gè)狀態(tài)，且其狀態(tài)改變的規(guī)則在時(shí)間和空間上都是局部的。,元胞自動(dòng)機(jī)的分類,元胞自動(dòng)機(jī)的構(gòu)建沒有固定的數(shù)學(xué)公式，構(gòu)成方式繁雜，變種很多，行為復(fù)雜。故其分類難度也較大，自元胞自動(dòng)機(jī)產(chǎn)生以來，對(duì)于元胞自動(dòng)機(jī)分類的研究就是元胞自動(dòng)機(jī)的一個(gè)重要的研究課題和核心理論，在基于不同的出發(fā)點(diǎn)，元胞自動(dòng)機(jī)可有多種分類，其中，最具影響力的當(dāng)屬S. Wolfram在80年代初做的基于動(dòng)力學(xué)行為的元胞自動(dòng)機(jī)分類，而基于維數(shù)的元胞自動(dòng)機(jī)分類也是最簡(jiǎn)單和最常用的劃分。除此之外，在1990年，Howard A.Gutowitz提出了基于元胞自動(dòng)機(jī)行為的馬爾科夫概

6、率量測(cè)的層次化、參量化的分類體系（Gutowitz,H. A.,1990）。,元胞自動(dòng)機(jī)的分類,基于維數(shù)的分類： 一維元胞：初等元胞自動(dòng)機(jī)(ECA)是狀態(tài)集S只有兩個(gè)元素s1，s2，即狀態(tài)個(gè)數(shù)k=2，鄰居半徑r=l的一維元胞自動(dòng)機(jī)。它幾乎是最簡(jiǎn)單的元胞自動(dòng)機(jī)模型。由于在S中具體采用什么符號(hào)并不重要，它可取 0，1，-l，1，靜止，運(yùn)動(dòng)，黑，白，生，死等等，這里重要的是S所含的符號(hào)個(gè)數(shù)，通常我們將其記為 0，1。此時(shí)，鄰居集N的個(gè)數(shù)2r=2，局部映射f:S3S可記為 考慮有等長(zhǎng)的L個(gè)格子的線段，每一個(gè)格子i都有兩種狀態(tài) 0和 1，在t時(shí)刻i格子的狀態(tài)記為： ，記 其中變量有三個(gè)，每個(gè)變量取兩個(gè)狀

7、態(tài)值，那么就有222=8種組合，只要給出在這八個(gè)自變量組合上的值，f就完全確定了。,元胞自動(dòng)機(jī)的分類,二維元胞：元胞分布在二維歐幾里德平面上規(guī)則劃分的網(wǎng)格點(diǎn)上，通常為方格劃分。以J. H. Conway的“生命游戲”為代表，“深林火災(zāi)”，應(yīng)用最為廣泛。由于，世界上很多現(xiàn)象是二維分布的，還有一些現(xiàn)象可以通過抽象或映射等方法，轉(zhuǎn)換到二維空間上，所以，二維元胞自動(dòng)機(jī)的應(yīng)用最為廣泛，多數(shù)應(yīng)用模型都是二維元胞自動(dòng)機(jī)模型。,元胞自動(dòng)機(jī)的分類,三維元胞：,元胞自動(dòng)機(jī)的分類,S. Wolfrarm在詳細(xì)分析研究了一維元胞自動(dòng)機(jī)的演化行為，并在大量的計(jì)算機(jī)實(shí)驗(yàn)的基礎(chǔ)上，將所有元胞自動(dòng)機(jī)的動(dòng)力學(xué)行為歸納為四大類（

8、Wolfram. S.，1986): 平穩(wěn)型:自任何初始狀態(tài)開始，經(jīng)過一定時(shí)間運(yùn)行后，元胞空間趨于一個(gè)空間平穩(wěn)的構(gòu)形，這里空間平穩(wěn)即指每一個(gè)元胞處于固定狀態(tài)。不隨時(shí)間變化而變化。 周期型：經(jīng)過一定時(shí)間運(yùn)行后，元胞空間趨于一系列簡(jiǎn)單的固定結(jié)構(gòu)（Stable Patterns）或周期結(jié)構(gòu)（Perlodical Patterns)。由于這些結(jié)構(gòu)可看作是一種濾波器（Filter），故可應(yīng)用到圖像處理的研究中。 混沌型：自任何初始狀態(tài)開始，經(jīng)過一定時(shí)間運(yùn)行后，元胞自動(dòng)機(jī)表現(xiàn)出混沌的非周期行為，所生成的結(jié)構(gòu)的統(tǒng)計(jì)特征不再變止，通常表現(xiàn)為分形分維特征。 復(fù)雜型：出現(xiàn)復(fù)雜的局部結(jié)構(gòu)，或者說是局部的混沌，其中有

9、些會(huì)不斷地傳播。,元胞自動(dòng)機(jī)的分類,從另一角度，元胞自動(dòng)機(jī)可視為動(dòng)力系統(tǒng)，因而可將初試點(diǎn)、軌道、不動(dòng)點(diǎn)、周期軌和終極軌等一系列概念用到元胞自動(dòng)機(jī)的研究中，上述分類，又可以分別描述為（譚躍進(jìn)，1996；謝惠民，1994；李才偉、1997）； 均勻狀態(tài)，即點(diǎn)態(tài)吸引子，或稱不動(dòng)點(diǎn)； 簡(jiǎn)單的周期結(jié)構(gòu)，即周期性吸引子，或稱周期軌； 混沌的非周期性模式，即混沌吸引子； 這第四類行為可以與生命系統(tǒng)等復(fù)雜系統(tǒng)中的自組織現(xiàn)象相比擬，但在連續(xù)系統(tǒng)中沒有相對(duì)應(yīng)的模式。但從研究元胞自動(dòng)機(jī)的角度講，最具研究?jī)r(jià)值的具有第四類行為的元胞自動(dòng)機(jī)，因?yàn)檫@類元胞自動(dòng)機(jī)被認(rèn)為具有突現(xiàn)計(jì)算(Emergent Computation）

10、功能，研究表明，可以用作廣義計(jì)算機(jī)（Universal Computer）以仿真任意復(fù)雜的計(jì)算過程。另外，此類元胞自動(dòng)機(jī)在發(fā)展過程中還表現(xiàn)出很強(qiáng)的不可逆（lrreversibility）特征，而且，這種元胞自動(dòng)機(jī)在若干有限循環(huán)后，有可能會(huì) 死掉，即所有元胞的狀態(tài)變?yōu)榱恪?元胞自動(dòng)機(jī)的實(shí)際程序運(yùn)行,生命游戲,#include using namespace std; struct Cell bool live; int others; ;,元胞自動(dòng)機(jī)的實(shí)際程序運(yùn)行,void main() Cell cell1010; for(int i=0;i10;i+) for(int j=0;j10;j+)

11、 cellij.live=true; cellij.others=0; ,while(1) for(int i=0;i10;i+) for(int j=0;j10;j+) cellij.others=0; for(int i=0;i10;i+) for(int j=0;j10;j+) if(cellij.live) cout$ ; else cout- ; coutendl; ,元胞自動(dòng)機(jī)的實(shí)際程序運(yùn)行,for(int i=0;i=0 ,元胞自動(dòng)機(jī)的實(shí)際程序運(yùn)行,switch(cellij.others) case 2:break; case 3:cellij.live=true;break;

12、 default:cellij.live=false;break; Sleep(1000); /clrscr(); system(cls);/可以用這個(gè)清屏 ,運(yùn)行視頻,元胞自動(dòng)機(jī)的實(shí)際程序運(yùn)行,生命游戲的構(gòu)成及規(guī)則: 元胞分布在規(guī)則劃分的網(wǎng)格上； 元胞具有，兩種狀態(tài)，代表“死”，l代表“生”； 元胞以相鄰的8個(gè)元胞為鄰居。即Moore鄰居形式； 一個(gè)元胞的生死由其在該時(shí)刻本身的生死狀態(tài)和周圍八個(gè)鄰居的狀態(tài) (確切講是狀態(tài)的和)決定:在當(dāng)前時(shí)刻，如果一個(gè)元胞狀態(tài)為“生”，且八個(gè)相鄰元胞中有兩個(gè)或三個(gè)的狀態(tài)為“生”，則在下-時(shí)刻該元胞繼續(xù)保持為“生”，否則“死”去；在當(dāng)前時(shí)刻。如果一個(gè)元胞狀態(tài)為

13、死。且八個(gè)相鄰元胞中正好有三個(gè)為生。則該元胞在下一時(shí)刻 復(fù)活。否則保持為死。,元胞自動(dòng)機(jī)的實(shí)際程序運(yùn)行,生命游戲的設(shè)計(jì)中,我們將平面劃分成方格棋盤,每個(gè)方格代表一個(gè)元胞,元胞狀態(tài)為0 表示死亡,1 表示活著,鄰域半徑為1 ,鄰域類型為Moore 型,演化規(guī)則為: 若S (t) = 1 若S (t) = 0 , 其中S (t) 表示t 時(shí)刻元胞的狀態(tài),而S為8 個(gè)相鄰元胞中活著的元胞數(shù)。,元胞自動(dòng)機(jī)的意義,元胞自動(dòng)機(jī)可用來研究很多一般現(xiàn)象。其中包括通信、信息傳遞（Communicahon）、計(jì)算（Compulation）、構(gòu)造 (Construction）、生長(zhǎng) (Growth）、復(fù)制 (Rep

14、roduction）、競(jìng)爭(zhēng)（Competition）與進(jìn)化（Evolutio，）等（Smith A.,1969;Perrier，J.Y.,1996）。同時(shí)。它為動(dòng)力學(xué)系統(tǒng)理論中有關(guān)秩序 (Ordering）、紊動(dòng) (Turbulence）、混沌 (Chaos）、非對(duì)稱（Symmetry-Breaking）、分形（Fractality）等系統(tǒng)整體行為與復(fù)雜現(xiàn)象的研究提供了一個(gè)有效的模型工具 (Vichhac。G，1984; Bennett，C,1985）。 元胞自動(dòng)機(jī)自產(chǎn)生以來，被廣泛地應(yīng)用到社會(huì)、經(jīng)濟(jì)、軍事和科學(xué)研究的各個(gè)領(lǐng)域。應(yīng)用領(lǐng)域涉及社會(huì)學(xué)、生物學(xué)、生態(tài)學(xué)、信息科學(xué)、計(jì)算機(jī)科學(xué)、數(shù)學(xué)、物

15、理學(xué)、化學(xué)、地理、環(huán)境、軍事學(xué)等。,元胞自動(dòng)機(jī)的意義,在社會(huì)學(xué)中： 元胞自動(dòng)機(jī)用于研究經(jīng)濟(jì)危機(jī)的形成與爆發(fā)過程、個(gè)人行為的社會(huì)性，流行現(xiàn)象，如服裝流行色的形成等。在生物學(xué)中，元胞自動(dòng)機(jī)的設(shè)計(jì)思想本身就來源于生物學(xué)自繁殖的思想，因而它在生物學(xué)上的應(yīng)用更為自然而廣泛。例如元胞自動(dòng)機(jī)用于腫瘤細(xì)胞的增長(zhǎng)機(jī)理和過程模擬、人類大腦的機(jī)理探索（Victor.Jonathan.D.，1990）、艾滋病病毒HIV的感染過程（Sieburg，H.B. 1990）、自組織、自繁殖等生命現(xiàn)象的研究以及最新流行的克隆 (Clone）技術(shù)的研究等 (ErmentroutG。B。，1993）。,元胞自動(dòng)機(jī)的意義,在生態(tài)學(xué)中

16、： 元胞自動(dòng)機(jī)用于兔子-草，鯊魚-小魚等生態(tài)動(dòng)態(tài)變化過程的模擬，展示出令人滿意的動(dòng)態(tài)效果；元胞自動(dòng)機(jī)還成功地應(yīng)用于螞蟻、大雁、魚類洄游等動(dòng)物的群體行為的模擬；另外，基于元胞自動(dòng)機(jī)模型的生物群落的擴(kuò)散模擬也是當(dāng)前的一個(gè)應(yīng)用熱點(diǎn)。在信息學(xué)中。元胞自動(dòng)機(jī)用于研究信息的保存、傳遞、擴(kuò)散的過程。另外。Deutsch(1972）、Sternberg(1980）和Rosenfeld(1979）等人還將二維元胞自動(dòng)機(jī)應(yīng)用到圖像處理和模式識(shí)別中 (WoIfram.S.，1983）。,元胞自動(dòng)機(jī)的意義,在計(jì)算機(jī)科學(xué)中： 元胞自動(dòng)機(jī)可以被看作是并行計(jì)算機(jī)而用于并行計(jì)算的研究（Wolfram.S.1983）。另外。元胞自動(dòng)機(jī)還應(yīng)用于計(jì)算機(jī)圖形學(xué)的研究中。 在數(shù)學(xué)中，元胞自動(dòng)機(jī)可用來研究數(shù)論和并行計(jì)算。例如Fischer(1965）設(shè)計(jì)的素?cái)?shù)過濾器（Prime Number Sieves)(Wolfram,S.1983）。,元胞自動(dòng)機(jī)的意義,在物理學(xué)中： 除了格子氣元胞自動(dòng)機(jī)在流體力學(xué)上的成功應(yīng)用。元胞自動(dòng)機(jī)還應(yīng)用于磁場(chǎng)、電場(chǎng)等場(chǎng)的模擬，以及熱擴(kuò)散、熱傳導(dǎo)和機(jī)械波的模擬。另外。元胞自動(dòng)機(jī)還用來模擬雪花等枝晶的形成。,元胞自動(dòng)機(jī)的意義,在化學(xué)中： 元胞自動(dòng)機(jī)可用來通過模擬原子、分子等各種微觀粒子在化學(xué)反應(yīng)中的相互作用，而研究化學(xué)反應(yīng)的過程。例如李才偉 (1997）應(yīng)用元胞自動(dòng)機(jī)模型成功模擬了