元胞自动机总结

1、元胞自动机元胞自动机的概念元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。具体讲，构成元胞自动机的部件被称为“元胞，每个元胞具有一个状态。这个状态只琵取某个有限状态集中的一个，例如或生或死，或者是256中颜色中的一种，等等；这些元胞规则地排列在被你为“元胞空间”的空间格网上；它们各自的状态随着时间变化。而根据一个局部规则来进行更新，也就是说，一个元胞在某时刻的状态取决于、而且仅仅家决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态；元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维

2、上的变化。元胞自动机的构成元胞自动机最基本的组成元胞、元胞空间、邻居及规则四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。ffl24元咆H动机的组成1 .元胞元胞又可称为单元。或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的品格点上。2 .状态状态可以是0,1的二进制形式。或是S0,S2,SSk整数形式的离散集，严格意义上。元胞自动机的元胞只能有一个犬态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。李才伟（1997）在其博士论文工作中，就设计实现了这样一种称之为多元随机元胞自动机”模型。并且定义

3、了元胞空间的邻居（Neighbor）关系。由于邻居关系，每个元胞有有限个元胞作为它的邻居;3 .元胞空间（Lattice）元胞所分布在的空间网点集合就是这里的元胞空间。(l)元胞空间的几何划分：理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元抱自动机。元胞空间的划分只有一种。而高维的元胞自动机。元胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机。二维元胞空间通常可按三角、四万或六边形三种网格排列(图2-5)。(C)六边网格2-5一维元胞自动机的三种网络划分(根据李/楮，1997)这三种规则的元胞空间划分在构模时各有优缺点：三角网格的优

4、点是拥有相对较少的邻居数目，这在某些时候很有用；具缺点是在计算机的表达与显示不方便，需要转换为四方网格。四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表达显示；其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型;其缺点同三角网格一样，在表达显示上较为困难、复杂。(2)边界条件:在理论上，元胞空间通常是在各维向上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要定义不同的边界条件。归纳起来

5、，边界条件主要有三种类型:周期型、反射型和定值型。有时，在应用中，为更加客观、自然地模拟实际现象，还有可能采用随机型，即在边界实时产生随机值。周期型(PehodicBoundary)ll指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的圈。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面(Torus),形似车胎或甜点圈。周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间型作为试验。反射型(ReflectiveBoundary)指在边界外邻居的元胞状态是以边界为轴的镜面反射。例如在一维空间中，当r=1时的边界情形：定值型(ConstantBoundary后所

6、有边界外元胞均取某一固定常量，如0,1等。需要指出的是，这三种边界类型在实际应用中，尤其是二维或更高维数的构模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型(相对边界中。不能一方单方面采用周期型)。（3）构形:在这个元胞、状态、元胞空间的概念基础上，我们引入另外一个非常重要的概念，构形（Configuration）o构形是在某个时刻，在元胞空间上所有元胞状态的空间分布组合。通常。在数学上，它可以表示为一个多维的整数矩阵。4 .令口居（Neighbor）以上的元胞及元胞空间只表示了系统的静态成分，为将“动态引入系统，必须加入演化规则。在元胞自动机中，这些规则是定义在空

7、间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞，内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式（我们以最常用的规则四方网格划分为例）。见图2-6,黑色元胞为中心元胞，灰色元胞为其邻居，它们的状态一起来计算中心元胞在下一时刻的状态。1*3-6元施行动机的郭居模喂S），忧的Mocrt型森林火灾模拟：元胞有3个不同的状态。状态为0是空位，状态=1是燃烧着的树木，状态等于2是树木。如果4个邻居中有一

8、个或一个以上的是燃烧着的并且自身是树木（状态为2）那么该元胞下一时刻的状态是燃烧（状态为1）。森林元胞（状态为2）以一个低概率（例如0.000005）开始烧（因为闪电）。一个燃烧着的元胞（状态为1）在下一时时刻变成空位的（状态为0）。空元胞以一个低概率（例如0.01）变为森林以模拟生长。出于矩阵边界连接的考虑，如果左边界开始着火，火势将向右蔓延，右边界同理。同样适用于顶部和底部。81RuniSOopjQuit269LRunJSkipQuit：204。60阴100204060ISO1Q0137RmISlopQuit427RunIStopQuit2tJ4Q5000WO204Q5080WQ其中黑色表

9、述没有任何东西，绿色表示树木，红色表示火。动态过程显示，火将树木烧掉，然后树木又重生，周而复始。clfclearall%=%GU界面，控制迭代，三个按钮和一个现实迭代次数的文本%Run按钮，开始执行，回调函数让run=1,开始迭代plotbutton=uicontrol(style,pushbutton,.string,Run,.fontsize,12,.position,100,400,50,20,.callback,run=1;);%stop按钮，回调函数让freeze=1,停止迭代erasebutton=uicontrol(style,pushbutton,.string,Stop,.f

10、ontsize,12,.position,200,400,50,20,.callback,freeze=1;);%Quit按钮，推出quitbutton=uicontrol(style,pushbutton,.string,Quit,.fontsize,12,.position,300,400,50,20,.callback,stop=1;close;);%示迭代次数文本number=uicontrol(style,text,.string,1,.fontsize,12,.position,20,400,50,20);%=n=100;Plightning=.000005;%树木自燃的概率Pgr

11、owth=.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)axisequalaxistight%没有物体用0表示，燃烧用1表示，树木用2表示stop=0;%默认开始没有，暂停run=0;%默认开始直接不进行迭代，用户按下Run按钮，在回调函数中设置Run=1,开始迭代freeze=0;%waitforafreezewhile(stop=0)1)=1)if(run=1)sum=(veg(1:n,n1:n-1)=1)+(veg(1:n,2:n%计算方便四个位置燃烧树木个数(veg(n1:n-1,1:n)=1)+(veg(2:n1,1:n)=1);veg计算下一个状态2*(veg=2)-(veg=2)&(sum0|(rand(n,n)Plightning)2*(veg=0)&rand(n,n)