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

2、化。元胞自動機(jī)的構(gòu)成元胞自動機(jī)最基本的組成元胞、元胞空間、鄰居及規(guī)則四部分。簡單講，元胞自動機(jī)可以視為由一個元胞空間和定義于該空間的變換函數(shù)所組成。1.元胞元胞又可稱為單元。或基元，是元胞自動機(jī)的最基本的組成部分。元胞分布在離散的一維、二維或多維歐幾里德空間的晶格點(diǎn)上。2.狀態(tài)狀態(tài)可以是0,1的二進(jìn)制形式?；蚴莝0,s2,sisk整數(shù)形式的離散集，嚴(yán)格意義上。元胞自動機(jī)的元胞只能有一個犬態(tài)變量。但在實際應(yīng)用中，往往將其進(jìn)行了擴(kuò)展。例如每個元胞可以擁有多個狀態(tài)變量。李才偉(1997)在其博士論文工作中，就設(shè)計實現(xiàn)了這樣一種稱之為多元隨機(jī)元胞自動機(jī)模型。并且定義了元胞空間的鄰居(neighbor)

3、關(guān)系。由于鄰居關(guān)系，每個元胞有有限個元胞作為它的鄰居;3.元胞空間(lattice)元胞所分布在的空間網(wǎng)點(diǎn)集合就是這里的元胞空間。(l)元胞空間的幾何劃分:理論上，它可以是任意維數(shù)的歐幾里德空間規(guī)則劃分。目前研究多集中在一維和二維元胞自動機(jī)上。對于一維元抱自動機(jī)。元胞空間的劃分只有一種。而高維的元胞自動機(jī)。元胞空間的劃分則可能有多種形式。對于最為常見的二維元胞自動機(jī)。二維元胞空間通?？砂慈?、四萬或六邊形三種網(wǎng)格排列 (圖2-5)。這三種規(guī)則的元胞空間劃分在構(gòu)模時各有優(yōu)缺點(diǎn):三角網(wǎng)格的優(yōu)點(diǎn)是擁有相對較少的鄰居數(shù)目，這在某些時候很有用;其缺點(diǎn)是在計算機(jī)的表達(dá)與顯示不方便，需要轉(zhuǎn)換為四方網(wǎng)格。四方

4、網(wǎng)格的優(yōu)點(diǎn)是直觀而簡單，而且特別適合于在現(xiàn)有計算機(jī)環(huán)境下進(jìn)行表達(dá)顯示;其缺點(diǎn)是不能較好地模擬各向同性的現(xiàn)象，例如后面提到的格子氣模型中的hpp模型。六邊形網(wǎng)格的優(yōu)點(diǎn)是能較好地模擬各向同性的現(xiàn)象，因此，模型能更加自然而真實，如格氣模型中的fhp模型;其缺點(diǎn)同三角網(wǎng)格一樣，在表達(dá)顯示上較為困難、復(fù)雜。(2)邊界條件:在理論上，元胞空間通常是在各維向上是無限延展的，這有利于在理論上的推理和研究。但是在實際應(yīng)用過程中，我們無法在計算機(jī)上實現(xiàn)這一理想條件，因此，我們需要定義不同的邊界條件。歸納起來，邊界條件主要有三種類型:周期型、反射型和定值型。有時，在應(yīng)用中，為更加客觀、自然地模擬實際現(xiàn)象，還有可能采

5、用隨機(jī)型，即在邊界實時產(chǎn)生隨機(jī)值。周期型(pehodic boundary)是指相對邊界連接起來的元胞空間。對于一維空間，元胞空間表現(xiàn)為一個首尾相接的圈。對于二維空間，上下相接，左右相接。而形成一個拓?fù)鋱A環(huán)面 (torus)，形似車胎或甜點(diǎn)圈。周期型空間與無限空間最為接近，因而在理論探討時，常以此類空間型作為試驗。反射型(reflective boundary)指在邊界外鄰居的元胞狀態(tài)是以邊界為軸的鏡面反射。例如在一維空間中，當(dāng)r=1時的邊界情形:定值型 (constant boundary)指所有邊界外元胞均取某一固定常量，如0，1等。需要指出的是，這三種邊界類型在實際應(yīng)用中，尤其是二維或更

6、高維數(shù)的構(gòu)模時，可以相互結(jié)合。如在二維空間中，上下邊界采用反射型，左右邊界可采用周期型 (相對邊界中。不能一方單方面采用周期型)。(3)構(gòu)形:在這個元胞、狀態(tài)、元胞空間的概念基礎(chǔ)上，我們引入另外一個非常重要的概念，構(gòu)形(configuration)。構(gòu)形是在某個時刻，在元胞空間上所有元胞狀態(tài)的空間分布組合。通常。在數(shù)學(xué)上，它可以表示為一個多維的整數(shù)矩陣。4.鄰居 (neighbor)以上的元胞及元胞空間只表示了系統(tǒng)的靜態(tài)成分，為將動態(tài)引入系統(tǒng)，必須加入演化規(guī)則。在元胞自動機(jī)中，這些規(guī)則是定義在空間局部范圍內(nèi)的，即一個元胞下一時刻的狀態(tài)決定于本身狀態(tài)和它的鄰居元胞的狀態(tài)。因而，在指定規(guī)則之前，必

7、須定義一定的鄰居規(guī)則，明確哪些元胞屬于該元胞的鄰居。在一維元胞自動機(jī)中，通常以半徑，來確定鄰居，距離一個元胞，內(nèi)的所有元胞均被認(rèn)為是該元胞的鄰居。二維元胞自動機(jī)的鄰居定義較為復(fù)雜，但通常有以下幾種形式(我們以最常用的規(guī)則四方網(wǎng)格劃分為例)。見圖2-6，黑色元胞為中心元胞，灰色元胞為其鄰居，它們的狀態(tài)一起來計算中心元胞在下一時刻的狀態(tài)。森林火災(zāi)模擬：元胞有3個不同的狀態(tài)。狀態(tài)為 0是空位，狀態(tài)= 1是燃燒著的樹木，狀態(tài)等于2是樹木。如果4個鄰居中有一個或一個以上的是燃燒著的并且自身是樹木（狀態(tài)為2 ） 那么該元胞下一時刻的狀態(tài)是燃燒（狀態(tài)為 1 ） 。 森林元胞（狀態(tài)為 2 ）以一個低概率（例如

8、0.000005 ）開始燒（因為閃電）。一個燃燒著的元胞（狀態(tài)為 1 ）在下一時時刻變成空位的（狀態(tài)為0 ） 。 空元胞以一個低概率（例如0.01 ）變?yōu)樯忠阅M生長。出于矩陣邊界連接的考慮，如果左邊界開始著火，火勢將向右蔓延，右邊界同理。同樣適用于頂部和底部。其中黑色表述沒有任何東西，綠色表示樹木，紅色表示火。動態(tài)過程顯示，火將樹木燒掉，然后樹木又重生，周而復(fù)始。clfclear all%=%gui界面，控制迭代，三個按鈕和一個現(xiàn)實迭代次數(shù)的文本% run按鈕，開始執(zhí)行，回調(diào)函數(shù)讓 run=1,開始迭代plotbutton=uicontrol(style,pushbutton,.strin

9、g,run, .fontsize,12, .position,100,400,50,20, .callback, run=1;);% stop按鈕，回調(diào)函數(shù)讓freeze=1,停止迭代erasebutton=uicontrol(style,pushbutton,.string,stop, .fontsize,12, .position,200,400,50,20, .callback,freeze=1;);% quit按鈕，推出quitbutton=uicontrol(style,pushbutton,.string,quit, .fontsize,12, .position,300,400,

10、50,20, .callback,stop=1;close;);%顯示迭代次數(shù)文本number = uicontrol(style,text, .string,1, .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% 沒

11、有物體用 0表示，燃燒用1表示，樹木用2表示stop= 0; % 默認(rèn)開始沒有，暫停run = 0; % 默認(rèn)開始直接不進(jìn)行迭代，用戶按下 run按鈕，在回調(diào)函數(shù)中設(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) & (sum0 | (rand(n,n)plightning) + . 2*(veg=0) & rand(n,n)pgrowth) ; set(imh, cdata,