元胞自动机在数学模型中的应用

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,元胞自动机在数学模型中的应用,January 2,28,Give me space and motionand I will give you the world,Application Of Cellular Automata In Mathematical Modeling,应当尽可能简单,而不是比较简单地做每一件事,.,A.,爱因斯坦,提要,元 胞 简 介,元 胞 构 成,元 胞 行 为,元 胞 特 征,元 胞 分 类,经 典 元 胞,应 用 举 例,程 序 实 现,参 考 文 献,元胞简介（,Introduction,）,元胞自动机是离散（,discrete,）动力学系统（,dynamic,）,CA,之所以是离散系统，是因为元胞是定义在有限的时间和空间上的，并且元胞的状态是有限。,CA,被认为是动力学模型，是因为它的举止行为具有动力学特征,什么是元胞（,CA,）自动机,To put it another way,“Not to describe a complex system with complex equations,but let the complexity emerge by interaction of simple individuals following simple rules.”,asic,Idea,Simulate complex systems by interaction of cells,following easy rules.,元胞简介（,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 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 the standard model of computation(CPU,globally addressable memory,serial processing)is know as“von,Neumann style”.,元胞自动机的历史（,History,）,元胞构成（,Components,）,元胞（,Cell,）,元胞自动机最基本的单元,.,元胞有记忆贮存状态的功能,.,所有元胞状态都安照元胞规则不断更新,格子,(Lattice),元胞的网格空间,.,Cell and lattice,元胞行为,(,Behavior,),局部变化引起全局变化,可以简单认为元胞自动机在运动上类似于波,.,无胞的状态变化依赖于自身状态和邻居的状态,元胞自动机,的规则,(Rule),某元胞下时刻的状态只决定于邻居的状态以及自身的初始状态,元胞行为,(,Behavior,),元胞网格,(Lattice),Square Triangle Hexagon,元胞行为,(,Behavior,),V,onNeumann,Neighborhood,Moore,neighborhood,Extended Moore,neighborhood,元胞邻居,(,Neighborhood,),元胞行为,(,Behavior,),其它,元胞网格,(,Neighborhood,),元胞行为,(,Behavior,),边界条件,(boundary),元胞行为,(,Behavior,),元胞自动机的规则决定了元胞的行为征,.,即使一个简单的系统,也有很多种规则决定下一时刻的状态,.,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,neighborhood,so the,resulting,neighbors,could be local(touching),close,(,neighbors,neighbors,)or global(anywhere in the,system)or possibly use random,neighbors,Could allow the cells to grow and die.,规则系统,元胞特征,(Characteristics),离散的网格,元胞的同质,离散的状态,局部的作用,离散的时间,元胞分类,(Classes),空间上元胞可分为三类,一维元胞自动机,二维元胞自动机,三维元胞自动机,不同的分类方式,概率机与非概率机,典型概率机：森林火灾,经典元胞,生命游戏,生命游戏,(Came of Life),是,J.H.Conway,在,2,世纪,6,年代末设计的一种单人玩的计算机游戏,(,Garclner,，,M.,，,97,、,97),。他与现代的围棋游戏在某些特征上略有相似：围棋中有黑白两种棋子。生命游戏中的元胞有,生,，,死,两个状态,，,;,围棋的棋盘是规则划分的网格，黑白两子在空间的分布决定双方的死活，而生命游戏也是规则划分的网格,(,元胞似国际象棋分布在网格内。而不象围棋的棋子分布在格网交叉点上,),。根据元胞的局部空间构形来决定生死。只不过规则更为简单。,经典元胞,生命游戏的构成及规则,:,元胞分布在规则划分的网格上；,元胞具有，两种状态，代表,“,死,”,，,l,代表,“,生,”,；,元胞以相邻的,8,个元胞为邻居。即,Moore,邻居形式；,一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态,(,确切讲是状态的和,),决定,:,在当前时刻，如果一个元胞状态为,“,生,”,，且八个相邻元胞中有两个或三个的状态为,“,生,”,，则在下,-,时刻该元胞继续保持为,“,生,”,，否则,“,死,”,去；在当前时刻。如果一个元胞状态为,死,。且八个相邻元胞中正好有三个为,生,。则该元胞在下一时刻,复活,。否则保持为,死,。,生命游戏,经典元胞,元胞有,3,个不同的状态,.,状态为,0,是空位,状态,=1,是燃烧着的树木,状态,=2,是树木,.,如果,4,个邻居中有一个或一个以上的是燃烧着的并且自身是树木,(,状态,为,2),那么该元胞下一时刻的状态是燃烧,(,状态为,1).,森林元胞,(,状态为,2),以一个低概率,(,例如,.5),开始烧,(,因为闪电,).,一个燃烧着的元胞,(,状态为,1),在下一时时刻变成空位的,(,状态为,).,空元胞以一个低概率,(,例如,.),变为森林以模拟生长,.,出于矩阵边界连接的考虑,如果左边界开始着火,火势将向右蔓延,右边,界同理,.,同样适用于顶部和底部,.,森林火灾,森林火灾的构成及规则,:,应用举例,数学建模中的应用,The Booth Tolls for Thee,应用举例,数学建模中的应用,Modeling Flooding from a Dam,Failure in South Carolina,Cell 0 x,Cell 2x,Cell 0y,Cell 2y,Cell 1,Fgx,Fgy,Y,x,Fpy,Net,Fp,Fpx,程序实现,MATLAB,的编程考虑,矩阵和图形的相互转化,Image,Imshow,pcolor,imread,1 0 1 1,0 1 1 1 0,0 1 0 1,1 1 1 1 0,程序实现,MATLAB,的编程考虑,初始化元胞状态,z=,zeros(n,n,);,cells=z;,cells(n/2,.25*n:.75*n)=1;,cells(.25*n:.75*n,n/2)=1;,程序实现,MATLAB,的编程考虑,简单的实现规则,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),程序实现,MATLAB,的编程考虑,简单的实现规则,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)+.,cells(x-1,y-1)+cells(x-1,y+1)+.,cells(x+1,y-1)+cells(x+1,y+1);,cells=(sum=3)|(sum=2,程序实现,典型元胞程序精讲,森林火灾,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,);,程序实现,典型元胞程序精讲,交通流,参考文献（,References,）,物理系统的元胞自动机模拟,(Cellular Automata,Modeling,of Physical Systems).,Bastien,Chopard,Michel,Droz,祝玉学赵学龙译,Introduction to the Theory of Cellular Automata and One-Dimensional Traffic Simulation.,Cochinos,Richard.,Cellular Automata:A Discrete Universe.,Ilachinski,.,Introduction to Cellular Automata.,Rennard,Jean-,Philepe,.,http:/cell- in Cellular Automata:A Selected Review.Mitchell,Melanie.,Rucker R.,Walker J.,Introduction to,CelLab,http:/www.fourmilab.ch/cellab/,THE END,