元胞自动机模型

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

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

3、部映射f：S3S可记为: 1 11 (,) tttt iiii Sf SS S . Wolfram的初等元胞自动机 由于只有0、1两种状态， 所以函数f共有28=256种状 态 256种初等CA规则 元胞自动机的构成 元胞自动机最基本的组成：元胞、 元胞空间、邻居及规则四部分。另 外，还应包含状态和时间。 可以视为由一个元胞空间和定义于 该空间的变换函数所组成。 元胞自动机的构成示意图 元胞:元胞又可称为单元、细胞或基元，是 元胞自动机的最基本的组成部分。元胞 分布在离散的一维、二维或多维欧几里 德空间的晶格点上。 具有以下特点： 1.元胞自动机最基本的单元. 2.元胞有记忆贮存状态的功能.

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

5、 种划分 B 二维元胞自动机通常有三种划分方 式:三角形,正方形,正六边形 三类网格划分的优缺点对比: B 元胞空间边界条件 理论上，元胞空间是无限的；实际应用 中无法达到这一理想条件。常用的边界 条件如下 *周期型 *定值型 *绝热型 *反射型 周期型边界条件： 定义：周期型是指相对边界连接起来的元 胞空间 *对一维空间，首尾相接形成一个圆环 *对二维空间，上下相接，左右相接，而 形成一个拓*扑圆环面，形似车胎或甜 点圈 *周期型空间与无限空间最为接近，因而 在理论探讨时，常以此类空间作为试验 定值型边界条件 定义：所有边界外元胞均取某一固定常量 绝热型边界条件 定义：在指边界外邻居元胞的状

6、态始终和边界元胞的状态保持 一致，即具有状态的零梯度 *反射型边界条件 定义：在边界外邻居的元胞状态是以边界元胞为轴 的镜面反射。 邻居: 冯-诺依曼(Von. Neumann)型 定义如下： 摩尔(Moore)型 规则: 根据元胞当前状态及其邻居状况确 定下一时刻该元胞状态的动力学函 数，简单讲，就是一个状态转移函 数。 根据上面对元胞自动机的组成分析，我 们可以更加深入地理解元胞自动机的概 念。 可以将元胞自动机概括为一个用数 学符号来表示的四元组。 A:代表一个元胞自动机系统；Ld：代表 元胞空间；d：为空间维数；S：是元胞 有限的离散的状态集合；N：表示邻域 内所有元胞的组合（包括中心

7、元胞在 内）；f：是局部转换函数，也就是规则。 元胞行为 局部变化引起全局变化 *可以简单认为元胞自动机在运动上 类似于波. *无胞的状态变化依赖于自身状态和 邻居的状态 元胞自动机的规则 某元胞下时刻的状态只决定于邻居的状 态以及自身的初始状态 元胞行为 元胞网格 元胞行为 元胞邻居 经典元胞 生命游戏 生命游戏 (Came of Life)是J. H. Conway 在2世纪6年代末设计的一种单人玩的计算 机游戏(Garclner，M.，97、97)。他与现 代的围棋游戏在某些特征上略有相似：围 棋中有黑白两种棋子。生命游戏中的元胞 有生，死两个状态 ，;围棋的棋盘是 规则划分的网格，黑白

8、两子在空间的分布 决定双方的死活，而生命游戏也是规则划 分的网格(元胞似国际象棋分布在网格内。 而不象围棋的棋子分布在格网交叉点上)。 根据元胞的局部空间构形来决定生死。只 不过规则更为简单。 生命游戏的构成及规则: *元胞分布在规则划分的网格上； *元胞具有，两种状态，代表“死”，l代表“生”； *元胞以相邻的8个元胞为邻居。即Moore邻居形式； *一个元胞的生死由其在该时刻本身的生死状态和周 围八个邻居的状态 (确切讲是状态的和)决定: 在当前时刻，如果一个元胞状态为“生”，且八 个相邻元胞中有两个或三个的状态为“生”，则在下- -时刻该元胞继续保持为“生”，否则“死”去； 在当前时刻。

9、如果一个元胞状态为死。且八 个相邻元胞中正好有三个为生。则该元胞在下一 时刻 复活。否则保持为死。 森林火灾 森林火灾的构成及规则: *元胞有3个不同的状态.状态为 0是空位,状态= 1是燃烧着 的树木, 状态 = 2是树木. *如果4个邻居中有一个或一个以上的是燃烧着的并且自身 是树木(状态 为2 ),那么该元胞下一时刻的状态是燃烧(状态为1). *森林元胞(状态为2 )以一个低概率(例如.5 )开始烧(因为闪 电). *一个燃烧着的元胞(状态为1)在下一时时刻变成空位的(状 态为 ). *空元胞以一个低概率(例如. )变为森林以模拟生长. *出于矩阵边界连接的考虑,如果左边界开始着火,火势

10、将向 右蔓延,右边 界同理.同样适用于顶部和底部. Y x 元胞自动机应用 生物学领域：因为元胞自动机的设计思 想本身就来源于生物学自繁殖的现象， 所以它在生物学上的应用更为自然而广 泛。 例如元胞自动机用于肿瘤细胞的增 长机理和过程模拟、人类大脑的机理探 索、爱滋病病毒HIV的感染过程、自组 织、自繁殖等生命现象的研究以及最新 流行的克隆 (clone)技术的研究等。另 外， 元胞自动机还可以用来模拟植物的 生长过程以及贝壳上的色素沉积图案 生态学领域：元胞自动机被用于兔 子-草，鲨鱼-小鱼等生态系统动态 变化过程的模拟，展示出令人满意 的动态效果;元胞自动机还成功地 应用于蚂蚁的行走路径，

11、大雁、鱼 类洄游等动物的群体行为的模拟； 另外，基于元胞自动机模型的生物 群落的扩散模拟也是当前的一个应 用热点。 物理学领域：在元胞自动机基础之上发展出来的 格子气自动机(LGA)和格子-波尔兹曼方法(LBM) 在计算流体领域获得了 巨大的成功。不仅能够解 决传统流体力学计算方法所能解决的绝大多数问 题，并且在多孔介质、 多相流、微小尺度方面具 有其独特的优越性。格子-波尔兹曼方法还被成功 地应用于磁场、电场、热扩散和热传导的模拟。 另外，元胞自动机还被用来模拟雪花等枝晶的形 成、液态金属材料的凝固结晶过程以及颗粒材料 的垮塌现象等。 交通科学领域：1986年，M. Cremer和J. Lu

12、dwig初次将元胞自动机运用到车辆交通的研究 中。随后，元胞自动机在车辆 交通中的应用主要 沿着两条主线展开：对城市道路交通流的研究， 以Nagel-Schreckenberg模型为代表;对城市交 通网络 的研究，以BML模型为代表。另外，80年 代以来，计算机水平日新月异的发展为元胞自动 机的 应用提供了强有力的支持。因此，在进入上 个世纪90年代后，元胞自动机在交通流理论研究 领域中得到了广泛的应用 计算机科学与信息学领域：元胞自动机的 逻辑思维方法为并行机的发展提供了另一 个理论框架。20世纪80年代，T. Toffoli和 N.H. Margolus 制造出第一台通用元胞自 动机计算机

13、CAM6，其性能可与当时的巨 型计算机相比拟，并且其图形显示功能明 显优于其他类型的计算机。元胞自动机还 被用来研究信息的保存、传递、扩散的过 程。除此之外，元胞自动机在图像处理和 模式识别中也体现出了其独到的优势 。 应用举例 数学建模中的应用 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 FpyNet Fp Fpx 程序实现 MATLAB的编程考虑

14、 矩阵和图形的相互转化 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