元胞自動(dòng)機(jī)在數(shù)學(xué)模型中的應(yīng)用

1、January 23, 2016Give me space and motion and I will give you the world元胞自動(dòng)機(jī)在數(shù)學(xué)模型中的應(yīng)用Application Of Cellular Automata In Mathematical Modeling應(yīng)當(dāng) 盡可能簡(jiǎn)單 而是 比較簡(jiǎn)單地 做每一件事.A.愛(ài)因斯坦提要元 胞 簡(jiǎn) 介 元 胞 構(gòu) 成 元 胞 為 元 胞 特 征 元 胞 分 類(lèi) 經(jīng) 典 元 胞 應(yīng) 用 舉 程 序 實(shí) 現(xiàn) 參 考 文 獻(xiàn)元胞簡(jiǎn)介 （Introduction）么是元胞（CA）自動(dòng)機(jī)元胞自動(dòng)機(jī)是離散（discrete）動(dòng)學(xué)系統(tǒng)（ dynami

2、c ）CA之所以是離散系統(tǒng)，是因?yàn)樵嵌x在有限的時(shí)間和 空間上的，并且元胞的狀態(tài)是有限。CA被認(rèn)為是動(dòng)學(xué)模型，是因?yàn)樗呐e止為具有動(dòng)學(xué) 特征asic IdeaSimulate complex systems by interaction of cells following easy rules.To put it another way“Not to describe a complex system with complex equations, but letthe complexity emerge by interaction of simple individuals foll

3、owing simple rules.”元胞簡(jiǎn)介 （Introduction）Original concept of CA is most strongly associated with John von Neumann.von Neumann was interested in the connections between biology and the then new study of automata theory.Stanislaw Ulam suggested that von Neumann use a cellular automata as a framework for

4、 researching these connections.The original concept of CA can be credited to Ulam, while the early development of the concept is credited to von Neumann.Ironically, although von Neumann made many contributions and developments in CA, they are commonly referred to as “non-von Neumann style”, while th

5、e standard model of computation (CPU, globally addressable memory, serial processing) is know as “von Neumann style”.元胞自動(dòng)機(jī)的歷史（History）元胞構(gòu)成（Components）元胞自動(dòng)機(jī)最基本的單元. 元胞有記憶貯存狀態(tài)的功能. 所有元胞狀態(tài)都安照元胞規(guī)則斷新格子 (Lattice)元胞的網(wǎng)格空間.Cell and lattice元胞（Cell）元胞為 (Behavior)局部變化引起全局變化可以簡(jiǎn)單認(rèn)為元胞自動(dòng)機(jī)在運(yùn)動(dòng)上類(lèi)似于波.無(wú)胞的狀態(tài)變化依賴(lài)于自身狀態(tài)和鄰居的狀態(tài)

6、元胞自動(dòng)機(jī)的規(guī)則(Rule)某元胞下時(shí)刻的狀態(tài)只決定于鄰居的狀態(tài)以及自身的 初始狀態(tài)元胞為 (Behavior)元胞網(wǎng)格(Lattice)SquareTriangleHexagon元胞為 (Behavior)VonNeumann NeighborhoodMoore neighborhoodExtended Moore neighborhood元胞鄰居(Neighborhood)元胞為 (Behavior)其它元胞網(wǎng)格(Neighborhood)元胞為(Behavior)其它元胞網(wǎng)格(Neighborhood)元胞為 (Behavior)其它元胞網(wǎng)格(Neighborhood)元胞為(Behav

7、ior)其它元胞網(wǎng)格(Neighborhood)元胞為(Behavior)邊界條件(boundary)元胞為(Behavior)邊界條件(boundary)元胞為 (Behavior)邊界條件(boundary)元胞為 (Behavior)規(guī)則系統(tǒng)元胞自動(dòng)機(jī)的規(guī)則決定元胞的為征.即使一個(gè)簡(jiǎn)單的系統(tǒng), 也有很多種規(guī)則決定下一時(shí)刻的狀態(tài).Could base the next state of the cell off of the sum of the states of your neighbors (Game of Life).Could modify the scope of the ne

8、ighborhood, so the resulting neighbors could be local (touching), close (neighbors neighbors) or global (anywhere in the system) or possibly use random neighborsCould allow the cells to grow and die.元胞特征 (Characteristics)離散的網(wǎng)格元胞的同質(zhì) 離散的狀態(tài) 局部的作用 離散的時(shí)間元胞分類(lèi) (Classes)同的分類(lèi)方式空間上元胞可分為三類(lèi)一維元胞自動(dòng)機(jī)二維元胞自動(dòng)機(jī)三維元胞自動(dòng)機(jī)

9、概機(jī)與非概機(jī)典型概機(jī)：森火災(zāi)經(jīng)典元胞生命游戲生命游戲 (Came of Life)是J. H. Conway在2世紀(jì)6代末設(shè)計(jì)的一 種單人玩的計(jì)算機(jī)游戲(Garclner，M.，97、97)。他與現(xiàn)代的圍棋游戲 在某些特征上有相似：圍棋中有黑白兩種棋子。生命游戲中的元胞有生，死兩個(gè)狀態(tài) ，;圍棋的棋盤(pán)是規(guī)則劃分的網(wǎng)格，黑白兩子在空 間的分布決定雙方的死活，而生命游戲也是規(guī)則劃分的網(wǎng)格(元胞似國(guó)際 象棋分布在網(wǎng)格內(nèi)。而象圍棋的棋子分布在格網(wǎng)交叉點(diǎn)上)。根據(jù)元胞 的局部空間構(gòu)形來(lái)決定生死。只過(guò)規(guī)則為簡(jiǎn)單。經(jīng)典元胞生命游戲的構(gòu)成及規(guī)則: 元胞分布在規(guī)則劃分的網(wǎng)格上； 元胞具有，兩種狀態(tài)，代表“死”，

10、l代表“生”； 元胞以相鄰的8個(gè)元胞為鄰居。即Moore鄰居形式； 一個(gè)元胞的生死由其在該時(shí)刻本身的生死狀態(tài)和周?chē)藗€(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īng)典元胞元胞有3個(gè)同的狀態(tài).狀態(tài)為 0是空位,狀態(tài)= 1是燃燒著的樹(shù)木, 狀態(tài)= 2是樹(shù)木.如果4個(gè)鄰居中有一個(gè)或一個(gè)以上的是燃燒著的并且自身是樹(shù)木(狀態(tài) 為2 ),那么該元胞下一時(shí)刻的狀態(tài)是燃

11、燒(狀態(tài)為1).森元胞(狀態(tài)為2 )以一個(gè)低概(如.5 )開(kāi)始燒(因?yàn)殚W電). 一個(gè)燃燒著的元胞(狀態(tài)為1)在下一時(shí)時(shí)刻變成空位的(狀態(tài)為 ). 空元胞以一個(gè)低概(如. )變?yōu)樯阅M生長(zhǎng).出于矩陣邊界連接的考慮,如果左邊界開(kāi)始著火,火勢(shì)將向右蔓延,右邊 界同.同樣適用于頂部和底部.森火災(zāi)森火災(zāi)的構(gòu)成及規(guī)則:應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)

12、建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Tolls for Thee應(yīng)用舉數(shù)學(xué)建模中的應(yīng)用The Booth Toll

13、s for Thee應(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 CarolinaCell 0 xCell 2xCell 0yCell 2yCell 1FgxFgyYxFpyNet FpFpx程序?qū)崿F(xiàn)MATLAB的編程考慮矩陣和圖形的相互轉(zhuǎn)化ImageimreadImshowpcolor1 1 0 1 10 1 1 1 01 0 1 0 11 1 1 1 0程序?qū)崿F(xiàn)MATLAB的編程考慮初始化元胞狀態(tài)z = zeros(n,n); cells = z;cel

14、ls(n/2,.25*n:.75*n) =1 ;cells(.25*n:.75*n,n/2) =1;程序?qū)崿F(xiàn)MATLAB的編程考慮簡(jiǎn)單的實(shí)現(xiàn)規(guī)則y=2:n-1;x=2:n-1;sum = veg(y,x+1)+veg(y, x -1)+ . veg(y+1, x )+ veg(y -1, x ) ;(y+1,x)(y,x-1)(y,x)(y,x-1)(y-1,x)程序?qū)崿F(xiàn)MATLAB的編程考慮簡(jiǎn)單的實(shí)現(xiàn)規(guī)則x = 2:n-1;y = 2:n-1;sum(x,y) = cells(x,y-1) + cells(x,y+1) + .cells(x-1, y) + cells(x+1,y) + .c

15、ells(x-1,y-1) + cells(x-1,y+1) + . cells(x+1,y-1) + cells(x+1,y+1);cells = (sum=3) | (sum=2 & cells);程序?qū)崿F(xiàn)典型元胞程序精講森火災(zāi)sum = (veg(1:n,n 1:n-1)=1) + (veg(1:n,2:n 1)=1) + .(veg(n 1:n-1, 1:n)=1) + (veg(2:n 1,1:n)=1) ;veg = .2*(veg=2) - (veg=2) & (sum 0 | (rand(n,n) Plightning) + . 2*(veg=0) & rand(n,n) Pgrowth) ;程序?qū)崿F(xiàn)典型元胞程序精講交通參考文獻(xiàn)（References）物系統(tǒng)的元胞自動(dòng)機(jī)模擬(Cellular Automata Modeling of Physical Systems). Bastien Chopard, Michel Droz祝玉學(xué)趙學(xué)龍譯Introduction to the Theory of Cellular Automata and One- Dimensional Traffic Simulation. Cochinos, Richard.Cellular A