元胞自動(dòng)機(jī)模型

1、編1腳怙釵剁元炮言動(dòng)機(jī)模型元胞自動(dòng)最具代表_Neumann 和 Ulam 提出。東南大學(xué)22011122王東巖 22011223 王果 22011323王語海 22011326周崎軒 22011328rr么是亍丿自:動(dòng)元胞自動(dòng)機(jī)（Cellular Automcitci,簡稱CA） 實(shí)質(zhì)上是定義在一個(gè)由具有離散、有限狀態(tài) 的元胞組成的元胞空間上，并按照一定的局 部規(guī)則，在離散的時(shí)間維度上演化的動(dòng)力學(xué) 系統(tǒng)。1. CA之所以是離散系統(tǒng)，是因?yàn)樵嵌x在有限 的時(shí)間和空間上的，并且元胞的狀態(tài)是有限。CA被認(rèn)為是動(dòng)力學(xué)模型，是因?yàn)樗呐e止行為 具有動(dòng)力學(xué)特征A元胞自動(dòng)機(jī)不是由嚴(yán)格定義的 物理方程或函

2、數(shù)確定，而是用 一系列模型構(gòu)造的規(guī)則構(gòu)成。凡是滿足這些規(guī)則的模型都可 以算作是元胞自動(dòng)機(jī)模型。因 此，元胞自動(dòng)機(jī)是一類模型的 總稱，或者說是一個(gè)方法框架初等元胞自動(dòng)機(jī)是狀態(tài)集S只有兩個(gè)元素si, s2,即狀態(tài)個(gè)數(shù)k=2,鄰居半徑的一維元 胞自動(dòng)機(jī)。由于在S中具體采用什么符號(hào)并不 重要，它可取0, 1, -1, 1, 靜止，運(yùn)動(dòng) 等等，重要的是S所含的符號(hào)個(gè)數(shù)，通常我們將其記為0, lo此時(shí)，鄰居集N的個(gè)數(shù)2=2,111t+11101: EZJJ QXJ U I Lrn 匚： ZIH! LU_Iv i V v 77i： L2 勺 匚 ZJ 1 廠I 口 由于只有0、1兩種狀態(tài)， 所以函數(shù)f共有2

3、8=256種狀 態(tài)r111110101100oil01000100000000001rule 100000010rnle 200000011rule 300000100mle 4t+ 10111000rule 184 1 1 1 1 1 1 1 0 rule 25511111111rule 256對(duì)給定初值及規(guī)則齊可通過計(jì)算機(jī)得到N步以后的演化結(jié)果A兀胞自動(dòng)機(jī)最基本的組成：兀胞、 元胞空間、鄰居及規(guī)則四部分。另 夕卜，還應(yīng)包含狀態(tài)和時(shí)間?？梢砸暈橛梢粋€(gè)元胞空間和定義于 該空間的變換函數(shù)所組成。規(guī)則/變検痢致元啊空間元胞又可稱為單元、細(xì)胞或基元，是 元胞自動(dòng)機(jī)的最基本的組成部分。元胞分 布在離散

4、的一維、二維或多維歐幾里德空 間的晶箱點(diǎn)上。具有以下特點(diǎn)：1 元胞自動(dòng)機(jī)最基本的單元.2. 元胞有記憶貯存狀態(tài)的功能.3. 所有元胞狀態(tài)都安照元胞規(guī)則不斷更新A元胞的狀態(tài)可以是二進(jìn)制形式，女口：(0, 1),(生，死)，(黑、白)等； 也可以在一個(gè)有限整數(shù)集內(nèi)S內(nèi)取值： 如交通領(lǐng)域的CA模型中，有時(shí)元胞狀 態(tài)可在卜(Vmax+1)Vmcix+1)之間取 值。狀態(tài)參量：嚴(yán)格意義上的CA只能有一 個(gè)狀態(tài)參量；但是，在實(shí)際應(yīng)用中，可 以具有多個(gè)狀態(tài)參量。元胞在空間中分布的空間格點(diǎn)的集 合就是元胞空間。A元胞空間的幾何劃分B元胞空間的邊界條件A理論上，它可以是任意維數(shù)的歐幾 里德空間規(guī)則劃分。常用的元

5、胞自 動(dòng)機(jī)一般是一纟卷和二維芮OA 一維元胞自動(dòng)機(jī)的元胞空間只有一 種劃分B二維元胞自動(dòng)機(jī)通常有三種劃分方 式:三角形,正方形，正六邊形(c)六邊網(wǎng)格I優(yōu)點(diǎn)缺點(diǎn)三角形擁有相對(duì)較少的鄰居數(shù)目，易 于處理復(fù)雜邊界在計(jì)算機(jī)的表達(dá)與 顯示不方便，需要 轉(zhuǎn)換為四方網(wǎng)格。正方形直觀而簡單，而且特別適合于 在現(xiàn)有計(jì)算機(jī)環(huán)境下進(jìn)行表達(dá) 顯示不能較好地模擬各 向同性的現(xiàn)象正六 邊形能較好地模擬各向同性的現(xiàn)象， 因此，模型能更加自然而真實(shí)在表達(dá)顯示上較為 困難、復(fù)雜A理論上，元胞空間是無限的；實(shí)際應(yīng)用 中無法達(dá)到這一理想條件。常用的邊界 條件如下*周期型*定值型*絕熱型*反射型A周期型邊界條件：定義：周期型是指相

6、對(duì)邊界連接起來的元 胞空間*對(duì)一維空間，首尾相接形成一個(gè)圓環(huán)*對(duì)二維空間，上下相接，左右相接，而 形成一個(gè)拓*撲圓環(huán)面，形似車胎或甜點(diǎn) 圈*周期型空間與無限空間最為接近，因而 在理論探討時(shí)，常以此類空間作為試驗(yàn)定值型邊界條件a固定邊界定義：所有邊界外元胞均取某一固定常量A絕熱型邊界條件ia絕熱邊界定義:在指邊界外鄰居元胞的狀態(tài)始終和邊界元胞的狀態(tài)保持一致，即具有狀態(tài)的零梯度*反射型邊界條件ba映射邊界豔點(diǎn)界外鄰居的元胞狀態(tài)是以邊界元胞為軸馮-諾依曼(Vori. Neumann)型定義如下：，IN咖z =比 （匕心）V. - V+V - V(XOXIV0Yr1?K，v(v)gZ2分別表示鄰居元胞

7、的行坐標(biāo)和列坐標(biāo)分別表示中心元胞的行坐標(biāo)和列坐標(biāo):摩爾(Moore)型鄰居的數(shù)目=衛(wèi)加怙乙.1J.v-v,v;v)gZ2(根據(jù)元胞當(dāng)前狀態(tài)及其鄰居狀況確 定下一時(shí)刻該元胞狀態(tài)的動(dòng)力學(xué)函 挈，簡單講，就是一個(gè)狀態(tài)轉(zhuǎn)移函 數(shù)。 s；f(s;,sj稱為元胞自動(dòng)機(jī)的局部映射或局部規(guī)則A根據(jù)上面對(duì)元胞自動(dòng)機(jī)的組成分析，我 們可以更加深入地理解元胞自動(dòng)機(jī)的概 念。可以將元胞自動(dòng)機(jī)概括為一個(gè)用數(shù) 學(xué)符號(hào)來表示的四元組。A =（厶廠S, N,/）A A：代表一個(gè)元胞自動(dòng)機(jī)系統(tǒng)；Ld：代表 元胞空間；d：為空間維數(shù)；S：是元胞 有限的離散的狀態(tài)集合；N：表示鄰域 內(nèi)所有元胞的組合（包括中心元胞在 內(nèi)）；f：是局

8、部轉(zhuǎn)換函數(shù)，也就是規(guī)則。局部變化引起全局變化*可以簡單認(rèn)為元胞自動(dòng)機(jī)在運(yùn)動(dòng)上 類似于波.*無胞的狀態(tài)變化依賴于自身狀態(tài)和 鄰居的狀態(tài)元胞自動(dòng)機(jī)的規(guī)則某元胞下時(shí)刻的狀態(tài)只決定于鄰居的狀 態(tài)以及自身的初始狀態(tài).元胞網(wǎng)格三角形元胞鄰居生命游戲(Came of Life)是J. H. Conway 在2椎紀(jì)6年代耒設(shè)計(jì)的一和單人玩的并負(fù)機(jī) 游戲(Gardner, M., 97、97)。他寫現(xiàn)代的 圍棋游戲作某些特征上略有相似：圍棋中有 死”兩個(gè)狀態(tài)，；圍棋的棋盤是規(guī)則韌分的 網(wǎng)格，黑白兩子在空間的分布決定雙方的死 活，一而生命游戲也是規(guī)則劃分血網(wǎng)格(元胞彳以 國際負(fù)桃分布在網(wǎng)格內(nèi)。而不象圍棋血棋子 分

9、布社*各網(wǎng)交叉點(diǎn)上丄根據(jù)元胞的局部空間 構(gòu)形來決定生死。只體過規(guī)則更為簡單。生命游戲的構(gòu)成及規(guī)則：*元胞分布在規(guī)則劃分的網(wǎng)格上；*元胞具有，兩種狀態(tài)，代表“死”，I代表“生”；*元胞以相鄰的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)為死“。且八個(gè) 相鄰元胞中正好有三個(gè)為“生蔦則該元胞在下一時(shí)刻“ 復(fù)活J否則保持為“死仁森林火災(zāi)森林火災(zāi)的構(gòu)成及規(guī)則

10、：*元胞有3個(gè)不同的狀態(tài)狀態(tài)為0是空位，狀態(tài)=1是燃燒著 的樹木，狀態(tài)=2是樹木.水如果4個(gè)鄰居中有一個(gè)或一個(gè)以上的是燃燒著的并且自身 是樹木（狀態(tài)為2）,那么該元胞下一時(shí)刻的狀態(tài)晟燃燒（狀態(tài)為1）. *森林元胞（狀態(tài)為2 ）以一個(gè)低概率（例如5 ）開始燒（因?yàn)殚W 也.* 一個(gè)燃燒著的元胞（狀態(tài)為1）在下一時(shí)時(shí)刻變成空位的（狀 態(tài)為）*空元胞以一個(gè)低概率（例如.）變?yōu)樯忠阅M生長.*出于矩陣邊界連接的考慮,如果左邊界開始著火，火勢(shì)將向 右蔓延，右邊界同理同樣適用于頂部和底部.A生物學(xué)領(lǐng)域：因?yàn)樵詣?dòng)機(jī)的設(shè)計(jì)思 想本身就來源于生物學(xué)自繁殖的現(xiàn)象， 所以它在生物學(xué)上的應(yīng)用更為自然而廣 泛。例如

11、元胞自動(dòng)機(jī)用于腫瘤細(xì)胞的增 長機(jī)理和過程模擬、人類大腦的機(jī)理探 索、愛滋病病毒HIV的感染過程、自組 織、自繁殖等生命現(xiàn)象的研究以及最新 流行的克隆(clone)技術(shù)的研究等。另 夕卜，元胞自動(dòng)機(jī)還可以用來模擬植物的 生長過程以及貝殼上的色素沉積圖案A生態(tài)學(xué)領(lǐng)域：元胞自動(dòng)機(jī)被用于兔 子草，鯊魚小魚等生態(tài)系統(tǒng)動(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é)領(lǐng)域：在元胞自動(dòng)機(jī)基礎(chǔ)之上發(fā)展出來的 格子氣自動(dòng)機(jī)(LGA)和格子-波爾茲曼方S

12、(LBM) 在計(jì)算流體領(lǐng)域獲得了巨大的成功。不僅能夠解 決傳統(tǒng)流體力學(xué)計(jì)算方法所能解決的絕大多數(shù)問 題，并且在多孔介質(zhì)、多相流、微小尺度方面具 有其獨(dú)特的優(yōu)越性。格子-波爾茲曼方法還被成功 地應(yīng)用于磁場、電場、熱擴(kuò)散和熱傳導(dǎo)的模擬。 丙外,，元胞自動(dòng)機(jī)還被用來模擬雪花等枝晶的形 成、液態(tài)金屬材料的凝固結(jié)晶過程以及顆粒材料的垮塌現(xiàn)象等。交通科學(xué)領(lǐng)域：1986年，M. CremerDJ.Ludwig初次將元胞自動(dòng)機(jī)運(yùn)用到車輛交通的研究 中。隨后，元胞自動(dòng)機(jī)在車輛交通中的應(yīng)用主要 沿著兩條主線展開：對(duì)城市道路交通流的研究， 以N ogel-SchGckenbeg模型為代表;對(duì)城市交 通網(wǎng)絡(luò)的研究，以

13、BML模型為代表。另外，80年 代以來，計(jì)算機(jī)水平日新月異的發(fā)展為元胞自動(dòng) 機(jī)的應(yīng)用提供了強(qiáng)有力的支持。因此，在進(jìn)入上 個(gè)世紀(jì)90年代后，元胞自動(dòng)機(jī)在交通流理論研究 領(lǐng)域中得到了廣泛的應(yīng)用計(jì)算機(jī)科學(xué)與信息學(xué)領(lǐng)域：元胞自動(dòng)機(jī)的 邏輯思維方法為并行機(jī)的發(fā)展提供了另一 個(gè)理論框架。20世紀(jì)80年代，T. Toffoli和 N.H. Margolus制造出第一臺(tái)通用元胞自 動(dòng)機(jī)計(jì)算機(jī)CAM6,其性能可與當(dāng)時(shí)的巨 型計(jì)算機(jī)相比擬，并且其圖形顯示功能明 顯優(yōu)于其他類型的計(jì)算機(jī)。元胞自動(dòng)機(jī)還 被用來研究信息的保存、傳遞、擴(kuò)散的過 程。除此之外，元胞自動(dòng)機(jī)在圖像處理和 模式識(shí)別中也體現(xiàn)出了其獨(dú)到的優(yōu)勢(shì)。應(yīng)用舉例數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉例數(shù)學(xué)建模中的應(yīng)用Modeling Flooding from a Dam Failure in South