元胞自動機總結

1、元胞自動機元胞自動機的概念 元胞自動機是定義在一個由具有離散、 有限狀態(tài)的元胞組成的元胞空間上， 并按 照一定局部規(guī)則，在離散的時間維上演化的動力學系統(tǒng)。具體講，構成元胞自動機的部件被稱為"元胞"，每個元胞具有一個狀態(tài)。這個狀態(tài) 只琵取某個有限狀態(tài)集中的一個，例如或"生"或"死"，或者是256中顏色中的一 種，等等這些元胞規(guī)則地排列在被你為"元胞空間"的空間格網(wǎng)上；它們各自的狀 態(tài)隨著時間變化。而根據(jù)一個局部規(guī)則來進行更新， 也就是說，一個元胞在某時 刻的狀態(tài)取決于、而且僅僅家決于上一時刻該元胞的狀態(tài)以及該元胞的所

2、有鄰居 元胞的狀態(tài)；元胞空間內(nèi)的元胞依照這樣的局部規(guī)則進行同步的狀態(tài)更新，整個 元胞空間則表現(xiàn)為在離散的時間維上的變化。元胞自動機的構成元胞自動機最基本的組成元胞、元胞空間、鄰居及規(guī)則四部分。簡單講，元 胞自動機可以視為由一個元胞空間和定義于該空間的變換函數(shù)所組成。圖2亠元胞自功機的組成1. 元胞元胞又可稱為單元?；蚧?，是元胞自動機的最基本的組成部分。元胞分布 在離散的一維、二維或多維歐幾里德空間的晶格點上。2. 狀態(tài)狀態(tài)可以是0,1的二進制形式?；蚴荢0,S2, i“Ss整數(shù)形式的離散集，嚴格 意義上。元胞自動機的元胞只能有一個犬態(tài)變量。但在實際應用中，往往將其進行了擴展。例如每個元胞可以

3、擁有多個狀態(tài)變量。李才偉(1997)在其博士論文工作中，就設計實現(xiàn)了這樣一種稱之為"多元隨機元胞自動機"模型。并且定義了元 胞空間的鄰居(Neighbor)關系。由于鄰居關系，每個元胞有有限個元胞作為它的 鄰居；3. 元胞空間(Lattice)元胞所分布在的空間網(wǎng)點集合就是這里的元胞空間。目前研究多集中在一維和二維元胞自動機上。劃分只有一種。而高維的元胞自動機。元胞空間的劃分則可能有多種形式。 最為常見的二維元胞自動機。格排列(圖2-5)。(r)六兩網(wǎng)|2 :角網(wǎng)格(I)元胞空間的幾何劃分：理論上，它可以是任意維數(shù)的歐幾里德空間規(guī)則劃分。 對于一維元抱自動機。元胞空間的 對

4、于 二維元胞空間通?？砂慈?、四萬或六邊形三種網(wǎng)ta 3-5 二維元機的三種網(wǎng)格劃分根站帶，1997)這三種規(guī)則的元胞空間劃分在構模時各有優(yōu)缺點：三角網(wǎng)格的優(yōu)點是擁有相對較少的鄰居數(shù)目，這在某些時候很有用；其缺點是在計算機的表達與顯示不方便，需要轉(zhuǎn)換為四方網(wǎng)格。四方網(wǎng)格的優(yōu)點是直觀而簡單，而且特別適合于在現(xiàn)有計算機環(huán)境下進行表 達顯示;其缺點是不能較好地模擬各向同性的現(xiàn)象，例如后面提到的格子氣模型 中的HPP模型。六邊形網(wǎng)格的優(yōu)點是能較好地模擬各向同性的現(xiàn)象，因此，模型能更加自然 而真實，如格氣模型中的FHP模型;其缺點同三角網(wǎng)格一樣，在表達顯示上較為 困難、復雜。(2)邊界條件：在理論上，元

5、胞空間通常是在各維向上是無限延展的，這有利于 在理論上的推理和研究。但是在實際應用過程中，我們無法在計算機上實現(xiàn)這一 理想條件，因此，我們需要定義不同的邊界條件。歸納起來，邊界條件主要有三 種類型:周期型、反射型和定值型。有時，在應用中，為更加客觀、自然地模擬 實際現(xiàn)象，還有可能采用隨機型，即在邊界實時產(chǎn)生隨機值。周期型(P ehodic Boun dary)是指相對邊界連接起來的元胞空間。對于一維空間， 元胞空間表現(xiàn)為一個首尾相接的"圈"。對于二維空間，上下相接，左右相接。而 形成一個拓撲圓環(huán)面(Torus)，形似車胎或甜點圈。周期型空間與無限空間最為 接近，因而在理論探

6、討時，常以此類空間型作為試驗。反射型(Reflective Boundary指在邊界外鄰居的元胞狀態(tài)是以邊界為軸的鏡面反 射。例如在一維空間中，當r=1時的邊界情形：If 口?定值型(Constant Boundary指所有邊界外元胞均取某一固定常量，女口0, 1等。需要指出的是，這三種邊界類型在實際應用中，尤其是二維或更高維數(shù)的構模時， 可以相互結合。如在二維空間中，上下邊界采用反射型，左右邊界可采用周期型 (相對邊界中。不能一方單方面采用周期型)。(3)構形:在這個元胞、狀態(tài)、元胞空間的概念基礎上，我們引入另外一個非常重 要的概念，構形(Configuration)。構形是在某個時刻，在元

7、胞空間上所有元胞狀 態(tài)的空間分布組合。通常。在數(shù)學上，它可以表示為一個多維的整數(shù)矩陣。4. 鄰居(Neighbor)以上的元胞及元胞空間只表示了系統(tǒng)的靜態(tài)成分，為將 "動態(tài)"引入系統(tǒng)，必須加 入演化規(guī)則。在元胞自動機中，這些規(guī)則是定義在空間局部范圍內(nèi)的， 即一個元 胞下一時刻的狀態(tài)決定于本身狀態(tài)和它的鄰居元胞的狀態(tài)。因而，在指定規(guī)則之前，必須定義一定的鄰居規(guī)則，明確哪些元胞屬于該元胞的鄰居。 在一維元胞自 動機中，通常以半徑，來確定鄰居，距離一個元胞，內(nèi)的所有元胞均被認為是該 元胞的鄰居。二維元胞自動機的鄰居定義較為復雜，但通常有以下幾種形式(我們以最常用的規(guī)則四方網(wǎng)格劃分

8、為例)。見圖2-6,黑色 元胞為中心元胞，灰色元胞為其鄰居，它們的狀態(tài)一起來計算中心元胞在下一時 刻的狀態(tài)。圖元曲白前機的鄰居«俎2護梅的Mooftr型森林火災模擬:狀態(tài)為0是空位，狀態(tài)=1是燃燒著的樹木，狀態(tài)等于元胞有3個不同的狀態(tài)。2是樹木。如果4個鄰居中有一個或一個以上的是燃燒著的并且自身是樹木 （狀態(tài)為2）那 么該元胞下一時刻的狀態(tài)是燃燒（狀態(tài)為 1）。1 ）在下一時時刻變成空位的（狀態(tài)為 0 ）。 ）變?yōu)樯忠阅M生長。如果左邊界開始著火，火勢將向右蔓延，右邊界同理。森林元胞（狀態(tài)為2 ）以一個低概率（例如 ）開始燒（因為閃電）。 一個燃燒著的元胞（狀態(tài)為 空元胞以一個低概

9、率（例如 出于矩陣邊界連接的考慮， 同樣適用于頂部和底部。9» wiiWKM 如幻1*1My護5 -丿紅色表示火。動態(tài)過程顯示，火將其中黑色表述沒有任何東西，綠色表示樹木, 樹木燒掉，然后樹木又重生，周而復始。cifclear all%=%GUI界面，控制迭代，三個按鈕和一個現(xiàn)實迭代次數(shù)的文本 % Run按鈕，開始執(zhí)行，回調(diào)函數(shù)讓run=1,開始迭代pl otbutt on=uic on trol('style',' pushbutt on',.'stri ng','Ru n',.fon tsize',12, .

10、'p ositio n',100,400,50,20, .'callback', 'ru n=1;');% stop按鈕，回調(diào)函數(shù)讓freeze=1停止迭代erasebutt on=uic on trol('style', 'p ushbutt on',.'stri ng','St op',.'fon tsize',12, .'p ositio n' ,200,400,50,20, .'callback','freeze=1;&

11、#39;);% Quit按鈕，推出quitbutton=uicontrol('style','pushbutton',.'string','Quit', .'fontsize',12, .'position',300,400,50,20, .'callback','stop=1;close;');%顯示迭代次數(shù)文本number = uicontrol('style','text', .'string','1

12、9;, .'fontsize',12, .'position',20,400,50,20);%=n=100;Plightning = .000005;%樹木自燃的概率Pgrowth = .01;%樹木自己重生的概率z=zeros(n,n);o=ones(n,n);veg=z;sum=z;imh = image(cat(3,z,veg*.02,z);set(imh, 'erasemode', 'none')axis equalaxis tight% 沒有物體用 0 表示，燃燒用 1 表示，樹木用 2 表示stop= 0;% 默認開始

13、沒有，暫停run = 0;% 默認開始直接不進行迭代，用戶按下Run 按鈕，在回調(diào)函數(shù)中設置Run=1開始迭代freeze = 0; %wait for a freezewhile (stop=0)if (run=1)%計sum = (veg(1:n,n 1:n-1)=1) + (veg(1:n,2:n 1)=1) + . 算方便四個位置燃燒樹木個數(shù)(veg(n 1:n-1, 1:n)=1) + (veg(2:n 1,1:n)=1) ;veg%計算下一個狀態(tài)2*(veg=2) - (veg=2) & (sum>0 | (rand(n,n)<Plightning) + . 2*(veg=0) & rand(n,n)<Pgrowth) ;%設置迭代次set(i