元 胞 自 动 机

《元 胞 自 动 机》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、元胞自动机一.元胞自动机的定义及构成元胞自动机(CellularAutomata，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网(LatticeGrid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。构成:元胞自动机最基本的组成:元胞、元胞空间、邻居及规则四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。二.常用元胞自动机1.S.Wolf

2、ram和初等元胞自动机初等元胞自动机(ElementaryCellularAutomata，简称ECA)是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=l的一维元胞自动机(谢惠民，1994、李才伟，1997、Wolfram，S，1986)。它几乎是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取{0，1}，{-l，1}，{静止，运动}，{黑，白}，{生，死}等等，这里重要的是S所含的符号个数，通常我们将其记为{0，1}。此时，邻居集N的个数2r=2，局部映射f:S3→S可记为:其中变量有三

3、个，每个变量取两个状态值，那么就有2×2×2=8种组合，只要给出在这八个自变量组合上的值，f就完全确定了。例如以下映射便是其中的一个规则:通常这种规则也可表示为以下图形方式(黑色方块代表l，白色方块代表0):2.J.Conway和"生命游戏"下面介绍生命游戏的构成及规则:(1)元胞分布在规则划分的网格上；(2)元胞具有0，1两种状态，0代表"死"，l代表"生"；(3)元胞以相邻的8个元胞为邻居。即Moore邻居形式；(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态(确切讲是状态的和)决定:·在当前时刻

4、，如果一个元胞状态为"生"，且八个相邻元胞中有两个或三个的状态为"生"，则在下--时刻该元胞继续保持为"生"，否则"死"去；·在当前时刻。如果一个元胞状态为"死"。且八个相邻元胞中正好有三个为"生"。则该元胞在下一时刻"复活"。否则保持为"死"。从数学模型的角度看，该模型将平面划分成方格棋盘，每个方格代表一个元胞。元胞状态:0死亡，1-活着领域半径:1领域类型：Moore型演化规则修改为:3.格子气自动机格子气自动机(Lattice一GasAutomata,LGA又称格气机)，是元胞自动机在流体力学与统计物理中的具体化，

5、也是元胞自动机在科学研究领域成功应用的范例(李才伟，1997)。相对于"生命游戏"来说，格子气自动机是个更注重于模型的实用性。它利用元胞自动机的动态特征，来模拟流体粒子的运动。应当说，格子气自动机是一种特殊的元胞自动机模型，或者说是一个扩展的元胞自动机模型(ExtendedCellularAutomata)。以早期的格子气模型为例，描述其特征如下:    (1)由于流体粒子不会轻易从模型空间中消失，这个特征需要格子气自动机是一个可逆元胞自动机模型。    (2)格子气自动机的邻居模型通常采用Margulos类型，即它的规则是

6、基于一个2X2的网格空间的。它的规则形似如下:4.Langton和“能自我复制的元胞自动机”Langton在vonNeumann和Codd工作的基础上，设计了一个能自我复制的"圈"。元胞状态在(0，1，2，3，4，5，6，7)中取值，其中，0，1，2，3构成元胞自动机的基本结构，04，05，06，07代表信号。l代表"核"元胞;2代表"壳"元胞，是边界;2包围的部分构成信息通道或称数据路径。邻居模型采用VonNeumann的4邻居模型。    元胞自动机通过信号元胞替代相邻的元胞，如状态为1的元胞，而完成信号传递。信号传播的过

7、程可以通过下面的例子说明:数据路径可以分支，在分支的节点处，信号在各个分支中复制本身，产生多个复制品。下图中，07信号在T形的交叉点处，复制自身:这个元胞自动机模型的另外一个重要特征就是路径扩张。即一定的信号可以产生数据路径的延伸，如下图所示：有了上面的论述，下面的具有路径扩张的、能自我复制的"圈"的工作机理应当容易理解了。三.元胞自动机在数学建模中的应用