元胞自动机模型

1、編1脚怙釵剁元炮言动机模型元胞自动最具代表_Neumann 和 Ulam 提出。东南大学22011122王东岩 22011223 王果 22011323王语海 22011326周崎轩 22011328rr么是亍丿自:动元胞自动机（Cellular Automcitci,简称CA） 实质上是定义在一个由具有离散、有限状态 的元胞组成的元胞空间上，并按照一定的局 部规则，在离散的时间维度上演化的动力学 系统。1. CA之所以是离散系统，是因为元胞是定义在有限 的时间和空间上的，并且元胞的状态是有限。CA被认为是动力学模型，是因为它的举止行为 具有动力学特征A元胞自动机不是由严格定义的 物理方程或函

2、数确定，而是用 一系列模型构造的规则构成。凡是满足这些规则的模型都可 以算作是元胞自动机模型。因 此，元胞自动机是一类模型的 总称，或者说是一个方法框架初等元胞自动机是状态集S只有两个元素si, s2,即状态个数k=2,邻居半径的一维元 胞自动机。由于在S中具体采用什么符号并不 重要，它可取0, 1, -1, 1, 静止，运动 等等，重要的是S所含的符号个数，通常我们将其记为0, lo此时，邻居集N的个数2=2,111t+11101: EZJJ QXJ U I Lrn 匚： ZIH! LU_Iv i V v 77i： L2 勺 匚 ZJ 1 厂I 口 由于只有0、1两种状态， 所以函数f共有2

3、8=256种状 态r111110101100oil01000100000000001rule 100000010rnle 200000011rule 300000100mle 4t+ 10111000rule 184 1 1 1 1 1 1 1 0 rule 25511111111rule 256对给定初值及规则齐可通过计算机得到N步以后的演化结果A兀胞自动机最基本的组成：兀胞、 元胞空间、邻居及规则四部分。另 夕卜，还应包含状态和时间。可以视为由一个元胞空间和定义于 该空间的变换函数所组成。規则/变検痢致元啊空间元胞又可称为单元、细胞或基元，是 元胞自动机的最基本的组成部分。元胞分 布在离散

4、的一维、二维或多维欧几里德空 间的晶箱点上。具有以下特点：1 元胞自动机最基本的单元.2. 元胞有记忆贮存状态的功能.3. 所有元胞状态都安照元胞规则不断更新A元胞的状态可以是二进制形式，女口：(0, 1),(生，死)，(黑、白)等； 也可以在一个有限整数集内S内取值： 如交通领域的CA模型中，有时元胞状 态可在卜(Vmax+1)Vmcix+1)之间取 值。状态参量：严格意义上的CA只能有一 个状态参量；但是，在实际应用中，可 以具有多个状态参量。元胞在空间中分布的空间格点的集 合就是元胞空间。A元胞空间的几何划分B元胞空间的边界条件A理论上，它可以是任意维数的欧几 里德空间规则划分。常用的元

5、胞自 动机一般是一纟卷和二维芮OA 一维元胞自动机的元胞空间只有一 种划分B二维元胞自动机通常有三种划分方 式:三角形,正方形，正六边形(c)六边网格I优点缺点三角形拥有相对较少的邻居数目，易 于处理复杂边界在计算机的表达与 显示不方便，需要 转换为四方网格。正方形直观而简单，而且特别适合于 在现有计算机环境下进行表达 显示不能较好地模拟各 向同性的现象正六 边形能较好地模拟各向同性的现象， 因此，模型能更加自然而真实在表达显示上较为 困难、复杂A理论上，元胞空间是无限的；实际应用 中无法达到这一理想条件。常用的边界 条件如下*周期型*定值型*绝热型*反射型A周期型边界条件：定义：周期型是指相

6、对边界连接起来的元 胞空间*对一维空间，首尾相接形成一个圆环*对二维空间，上下相接，左右相接，而 形成一个拓*扑圆环面，形似车胎或甜点 圈*周期型空间与无限空间最为接近，因而 在理论探讨时，常以此类空间作为试验定值型边界条件a固定边界定义：所有边界外元胞均取某一固定常量A绝热型边界条件ia绝热边界定义:在指边界外邻居元胞的状态始终和边界元胞的状态保持一致，即具有状态的零梯度*反射型边界条件ba映射边界豔点界外邻居的元胞状态是以边界元胞为轴冯-诺依曼(Vori. Neumann)型定义如下：，IN咖z =比 （匕心）V. - V+V - V(XOXIV0Yr1?K，v(v)gZ2分别表示邻居元胞

7、的行坐标和列坐标分别表示中心元胞的行坐标和列坐标:摩尔(Moore)型邻居的数目=卫加怙乙.1J.v-v,v;v)gZ2(根据元胞当前状态及其邻居状况确 定下一时刻该元胞状态的动力学函 挈，简单讲，就是一个状态转移函 数。 s；f(s;,sj称为元胞自动机的局部映射或局部规则A根据上面对元胞自动机的组成分析，我 们可以更加深入地理解元胞自动机的概 念。可以将元胞自动机概括为一个用数 学符号来表示的四元组。A =（厶厂S, N,/）A A：代表一个元胞自动机系统；Ld：代表 元胞空间；d：为空间维数；S：是元胞 有限的离散的状态集合；N：表示邻域 内所有元胞的组合（包括中心元胞在 内）；f：是局

8、部转换函数，也就是规则。局部变化引起全局变化*可以简单认为元胞自动机在运动上 类似于波.*无胞的状态变化依赖于自身状态和 邻居的状态元胞自动机的规则某元胞下时刻的状态只决定于邻居的状 态以及自身的初始状态.元胞网格三角形元胞邻居生命游戏(Came of Life)是J. H. Conway 在2椎纪6年代耒设计的一和单人玩的并負机 游戏(Gardner, M., 97、97)。他写现代的 围棋游戏作某些特征上略有相似：围棋中有 死”两个状态，；围棋的棋盘是规则韧分的 网格，黑白两子在空间的分布决定双方的死 活，一而生命游戏也是规则划分血网格(元胞彳以 国际負桃分布在网格内。而不象围棋血棋子 分

9、布社*各网交叉点上丄根据元胞的局部空间 构形来决定生死。只体过规则更为简单。生命游戏的构成及规则：*元胞分布在规则划分的网格上；*元胞具有，两种状态，代表“死”，I代表“生”；*元胞以相邻的8个元胞为邻居。即Moore邻居形式； *一个元胞的生死由其在该时刻本身的生死状态和周 围八个邻居的状态（确切讲是状态的和）决定：在当前时刻，如果一个元胞状态为“生”，且八 个相邻元胞中有两个或三个的状态为“生”，则在下 -时刻该元胞继续保持为“生”,否则“死”去；在当前时刻。如果一个元胞状态为死“。且八个 相邻元胞中正好有三个为“生蔦则该元胞在下一时刻“ 复活J否则保持为“死仁森林火灾森林火灾的构成及规则

10、：*元胞有3个不同的状态状态为0是空位，状态=1是燃烧着 的树木，状态=2是树木.水如果4个邻居中有一个或一个以上的是燃烧着的并且自身 是树木（状态为2）,那么该元胞下一时刻的状态晟燃烧（状态为1）. *森林元胞（状态为2 ）以一个低概率（例如5 ）开始烧（因为闪 也.* 一个燃烧着的元胞（状态为1）在下一时时刻变成空位的（状 态为）*空元胞以一个低概率（例如.）变为森林以模拟生长.*出于矩阵边界连接的考虑,如果左边界开始着火，火势将向 右蔓延，右边界同理同样适用于顶部和底部.A生物学领域：因为元胞自动机的设计思 想本身就来源于生物学自繁殖的现象， 所以它在生物学上的应用更为自然而广 泛。例如

11、元胞自动机用于肿瘤细胞的增 长机理和过程模拟、人类大脑的机理探 索、爱滋病病毒HIV的感染过程、自组 织、自繁殖等生命现象的研究以及最新 流行的克隆(clone)技术的研究等。另 夕卜，元胞自动机还可以用来模拟植物的 生长过程以及贝壳上的色素沉积图案A生态学领域：元胞自动机被用于兔 子草，鲨鱼小鱼等生态系统动态 变化过程的模拟，展示岀令人满意 的动态效果;元胞自动机还成功地 应用于蚂蚁的行走路径，大雁、鱼 类汹游等动物的群体行为的模拟； 另外，基于元胞自动机模型的生物 群落的扩散模拟也是当前的一个应 用热点。物理学领域：在元胞自动机基础之上发展出来的 格子气自动机(LGA)和格子-波尔兹曼方S

12、(LBM) 在计算流体领域获得了巨大的成功。不仅能够解 决传统流体力学计算方法所能解决的绝大多数问 题，并且在多孔介质、多相流、微小尺度方面具 有其独特的优越性。格子-波尔兹曼方法还被成功 地应用于磁场、电场、热扩散和热传导的模拟。 丙外,，元胞自动机还被用来模拟雪花等枝晶的形 成、液态金属材料的凝固结晶过程以及颗粒材料的垮塌现象等。交通科学领域：1986年，M. CremerDJ.Ludwig初次将元胞自动机运用到车辆交通的研究 中。随后，元胞自动机在车辆交通中的应用主要 沿着两条主线展开：对城市道路交通流的研究， 以N ogel-SchGckenbeg模型为代表;对城市交 通网络的研究，以

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