元胞自动机模型

1、元胞自动机模型,元胞自动机(cellular automata， CA) 模型是最具代表性的微观离散模型， 最早由 V on Neumann 和 Ulam 提出。 22011122 王东岩 22011223 王果 22011323 王语海 22011326 周崎轩 22011328 宋国强,东南大学,元胞自动机（Cellular Automata，简称CA）实质上是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定的局部规则，在离散的时间维度上演化的动力学系统。 1.CA之所以是离散系统，是因为元胞是定义在有限的时间和空间上的，并且元胞的状态是有限。 2.CA被认为是动力学模型，

2、是因为它的举止行为具有动力学特征,什么是元胞（CA）自动机,元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架,初等元胞自动机,初等元胞自动机是状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径r=1的一维元胞自动机。由于在S中具体采用什么符号并不重要，它可取 0，1，-1，1，静止，运动 等等，重要的是S所含的符号个数，通常我们将其记为 0，1。此时，邻居集N的个数2r=2，局部映射f：S3S可记为:,. Wolfram的初等元胞自动机,由于只有0、1两

3、种状态， 所以函数f共有28=256种状态,256种初等CA规则,元胞自动机的构成,元胞自动机最基本的组成：元胞、元胞空间、邻居及规则四部分。另外，还应包含状态和时间。 可以视为由一个元胞空间和定义于该空间的变换函数所组成。,元胞自动机的构成示意图,元胞:元胞又可称为单元、细胞或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。 具有以下特点： 1.元胞自动机最基本的单元. 2.元胞有记忆贮存状态的功能. 3.所有元胞状态都安照元胞规则不断更新,元胞状态 元胞的状态可以是二进制形式，如：（0，1），（生，死），（黑、白）等 ；也可以在一个有限整数集内

4、S内取值：如交通领域的CA模型中，有时元胞状态可在-(Vmax+1)Vmax+1)之间取值。 状态参量：严格意义上的CA只能有一个状态参量；但是，在实际应用中，可以具有多个状态参量。,元胞空间 元胞在空间中分布的空间格点的集合就是元胞空间。 A 元胞空间的几何划分 B 元胞空间的边界条件,A 元胞空间的几何划分 理论上，它可以是任意维数的欧几里德空间规则划分。常用的元胞自动机一般是一维和二维的。 A 一维元胞自动机的元胞空间只有一种划分 B 二维元胞自动机通常有三种划分方式:三角形,正方形,正六边形,三类网格划分的优缺点对比:,B 元胞空间边界条件 理论上，元胞空间是无限的；实际应用中无法达到

5、这一理想条件。常用的边界条件如下 *周期型 *定值型 *绝热型 *反射型,周期型边界条件： 定义：周期型是指相对边界连接起来的元胞空间 *对一维空间，首尾相接形成一个圆环 *对二维空间，上下相接，左右相接，而形成一个拓*扑圆环面，形似车胎或甜点圈 *周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间作为试验,定值型边界条件 定义：所有边界外元胞均取某一固定常量 绝热型边界条件 定义：在指边界外邻居元胞的状态始终和边界元胞的状态保持一致，即具有状态的零梯度 *反射型边界条件 定义：在边界外邻居的元胞状态是以边界元胞为轴的镜面反射。,邻居:,冯-诺依曼(Von. Neumann)型 定义

6、如下： 摩尔(Moore)型,规则: 根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。,根据上面对元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的概念。 可以将元胞自动机概括为一个用数学符号来表示的四元组。 A:代表一个元胞自动机系统；Ld：代表元胞空间；d：为空间维数；S：是元胞有限的离散的状态集合；N：表示邻域内所有元胞的组合（包括中心元胞在内）；f：是局部转换函数，也就是规则。,元胞行为,局部变化引起全局变化 *可以简单认为元胞自动机在运动上类似于波. *无胞的状态变化依赖于自身状态和邻居的状态 元胞自动机的规则 某元胞下时刻的状态只

7、决定于邻居的状态以及自身的初始状态,元胞行为,元胞网格,元胞行为,元胞邻居,经典元胞,生命游戏 生命游戏 (Came of Life)是J. H. Conway在2世纪6年代末设计的一种单人玩的计算机游戏(Garclner，M.，97、97)。他与现代的围棋游戏在某些特征上略有相似：围棋中有黑白两种棋子。生命游戏中的元胞有生，死两个状态 ，;围棋的棋盘是规则划分的网格，黑白两子在空间的分布决定双方的死活，而生命游戏也是规则划分的网格(元胞似国际象棋分布在网格内。而不象围棋的棋子分布在格网交叉点上)。根据元胞的局部空间构形来决定生死。只不过规则更为简单。,生命游戏的构成及规则: *元胞分布在规则

8、划分的网格上； *元胞具有，两种状态，代表“死”，l代表“生”； *元胞以相邻的8个元胞为邻居。即Moore邻居形式； *一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定: 在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下-时刻该元胞继续保持为“生”，否则“死”去； 在当前时刻。如果一个元胞状态为死。且八个相邻元胞中正好有三个为生。则该元胞在下一时刻 复活。否则保持为死。,森林火灾 森林火灾的构成及规则: *元胞有3个不同的状态.状态为 0是空位,状态= 1是燃烧着的树木, 状态 = 2是树木. *如果4个邻居中有一

9、个或一个以上的是燃烧着的并且自身是树木(状态 为2 ),那么该元胞下一时刻的状态是燃烧(状态为1). *森林元胞(状态为2 )以一个低概率(例如.5 )开始烧(因为闪电). *一个燃烧着的元胞(状态为1)在下一时时刻变成空位的(状态为 ). *空元胞以一个低概率(例如. )变为森林以模拟生长. *出于矩阵边界连接的考虑,如果左边界开始着火,火势将向右蔓延,右边 界同理.同样适用于顶部和底部.,Y,x,元胞自动机应用,生物学领域：因为元胞自动机的设计思想本身就来源于生物学自繁殖的现象，所以它在生物学上的应用更为自然而广泛。 例如元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索、爱滋

10、病病毒HIV的感染过程、自组织、自繁殖等生命现象的研究以及最新流行的克隆 (clone)技术的研究等。另外， 元胞自动机还可以用来模拟植物的生长过程以及贝壳上的色素沉积图案,生态学领域：元胞自动机被用于兔子-草，鲨鱼-小鱼等生态系统动态变化过程的模拟，展示出令人满意的动态效果;元胞自动机还成功地应用于蚂蚁的行走路径，大雁、鱼类洄游等动物的群体行为的模拟；另外，基于元胞自动机模型的生物群落的扩散模拟也是当前的一个应用热点。,物理学领域：在元胞自动机基础之上发展出来的格子气自动机(LGA)和格子-波尔兹曼方法(LBM)在计算流体领域获得了 巨大的成功。不仅能够解决传统流体力学计算方法所能解决的绝大

11、多数问题，并且在多孔介质、 多相流、微小尺度方面具有其独特的优越性。格子-波尔兹曼方法还被成功地应用于磁场、电场、热扩散和热传导的模拟。另外，元胞自动机还被用来模拟雪花等枝晶的形成、液态金属材料的凝固结晶过程以及颗粒材料的垮塌现象等。,交通科学领域：1986年，M. Cremer和J. Ludwig初次将元胞自动机运用到车辆交通的研究中。随后，元胞自动机在车辆 交通中的应用主要沿着两条主线展开：对城市道路交通流的研究，以Nagel-Schreckenberg模型为代表;对城市交通网络 的研究，以BML模型为代表。另外，80年代以来，计算机水平日新月异的发展为元胞自动机的 应用提供了强有力的支持

12、。因此，在进入上个世纪90年代后，元胞自动机在交通流理论研究领域中得到了广泛的应用,计算机科学与信息学领域：元胞自动机的逻辑思维方法为并行机的发展提供了另一个理论框架。20世纪80年代，T. Toffoli和N.H. Margolus 制造出第一台通用元胞自动机计算机CAM6，其性能可与当时的巨型计算机相比拟，并且其图形显示功能明显优于其他类型的计算机。元胞自动机还被用来研究信息的保存、传递、扩散的过程。除此之外，元胞自动机在图像处理和模式识别中也体现出了其独到的优势 。,应用举例,数学建模中的应用,The Booth Tolls for Thee,应用举例,数学建模中的应用,Modeling

13、 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:.7

14、5*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) + . cell