元胞自动机课件

1、元胞自动机2021/2/21元胞自动机2021/2/211 概述元胞自动机(Cellular Automata)作为描述处理复杂系统在离散空间、时间上演化规律的算法，通常采用对晶格格座的局域或整体的确定性和概率性变换规则进行具体操作。空间变量可以代表实空间、动量空间或波矢空间。晶格定义为具有固定数目的点，这些点可以看作是有限差分场中的结点。晶格一般是规则晶格， 其维数、大小可以是任意的。它表述了系统由基础实体(elementary entities)形成的构象，这些基础实体被认为与所用模型密切相关，它们可以是任意大小的连续体型体积单元、原子颗粒、晶格缺陷或生物界中的动物等等。 2021/2/2

2、21 概述元胞自动机(Cellular Automata)作为1 概述构成系统的基本实体，可以由广义态变量(诸如无量纲数、粒子密度、晶格缺陷密度、粒子速度、颜色、血压或动物种类等)进行量化表述。在每个独立的格座，这些态变量的实际取值都是确定的。并且认为，每一个结点代表有限个可能的离散状态中的一个态。将某些变换规则应用于每个结点状态，就会发生自动机的演化。这些规则决定着晶格格座的状态；对于局域规则，格座状态是其前一状态及近邻格点（座）状态的函数，而在整体变换规则下，则为所有格座状态的函数。传统元胞自动机大多采用局域变换规则。这种方法对于在规则晶格结构方面的应用是比较容易接受的。特别对于非均匀介质

3、，在讨论的晶格区域采用较小的晶格间距比较妥当； 而且，还必须考虑对变换速率进行合理修正和重正化。 2021/2/231 概述构成系统的基本实体，可以由广义态变量(诸如无量纲数、1 概述元胞自动机以离散时间步发展演化。经过一个时间间隔，要对所有结点的态变量值同时更新。近年来，通过对Wolfram (1986) 创立的经典元胞自动机(CCA)方法的合理拓展，已经建立起一批更广义的元胞自动机(GCA)方法。后者作为元胞自动机方法的变种，它比原来的方法有更强的适应性，尤其是在计算材料学中的一些特殊应用方面优点突出。广义微结构元胞自动机可以采用元胞或格座的离散空间格栅，这时的空间既可以是实空间，也可以是

4、动量空间或波矢空间。然而，在空间上通常被认为是均匀的，亦即所有格座都是等价的，并被排布在规则晶格上，其中的变换规则在各处都是一样的。 2021/2/241 概述元胞自动机以离散时间步发展演化。2021/2/241 概述同时，像常规自动机那样，假定它们是有限个可能状态中的一个，并对所有元胞状态同步更新。此外，它们与常规自动机不同的是，格座变换既可以按照确定性定律，也可以按照概率性定律。因而，广义微结构元胞自动机在计算材料学中的发展势头日益强劲。鉴于这些特点，元胞自动机方法为模拟动力学系统的演化提供了一种直接的手段，这些动力学系统包含有大量基于短程相互作用或长程相互作用的相似组元。对于一个简单的物

5、理系统，时间是其唯一个独立变量（自变量）这种直接方法，就相当于对多少有些复杂的偏微分方程组，利用有限差分近似法给出其离散解。 2021/2/251 概述2021/2/251 概述应该强调指出，这些元胞自动机方法对基础实体类型和选用的变换规则没有任何限制。它们可以对不同的处理状况进行描述，诸如：简单有限差分模拟中态变量值的分布，混合算法的色问题，“教室里的儿童健康情况 在任何变换条件下的模糊集合元素， 以及元胞的初级生长与衰减过程等。在计算材料学领域， 元胞自动机的变换规则般存在于有限差分、有限元，以及关于时间和2个或3个空间坐标的偏微分藕合方程组的蒙特卡罗近似之中。同时，局域变换描述近邻格座之

6、间的短程相互作用，而整体变换规则能够处理长程相互作用。通常，根据各个态变量的取值可以给出相应格座的状态。 2021/2/261 概述应该强调指出，这些元胞自动机方法对基础实体类型和1 概述元胞自动机通常被认为是离散计算方法的普遍化推广，具有更加广泛的适用性和多功能的特点。元胞自动机并不简单地等同于普通模拟方法，例如各种有限差分法、有限元法、伊辛( Ising) 法、波茨( Potts)方法等。这种灵活适用性是基于这样个事实：除了采用简明的数学表达式作为变量和变换规则之外，自动机还能够实际地包括任何元素或规则。2021/2/271 概述元胞自动机通常被认为是离散计算方法的普遍化推广，具有1 概述

7、在材料科学中，有时对常规有限差分计算方法补充一些“如果. . 就.”规则是很有意义的。在塑性学、断裂力学或晶体生长等领域遇到的情况。上述附加规则的方法为处理“ 数学上的奇点(即非光滑函数表述中的临界或自发效应)问题提供了一种简单有效的选择。这些规则经常出现在微结构模拟中：离散位错动力学模拟经常包含有这样一个规则“如果两个反平行螺位错相互靠近到其间距小于5个伯格斯矢量时，它们就会自发淹没。在断裂力学或弹簧模型中，会经常包含这样的规则“如果裂纹速度达到某个值，试验样品将自主损坏。在重结晶模拟中，会经常遇到这样的规则“如果晶体局域取向误差达到某一个值，格座将满足成核的动力学非稳定性临界条件” 或“局

8、域储存的弹性能达到某个临界值，格座将满足成核的热力学非稳定性条件”。2021/2/281 概述在材料科学中，有时对常规有限差分计算方法补充一些“如1 概述如果对主微分方程补充上述所说的“如果就”的变换规则，就可以对复杂系统的动力学行为特性进行模拟。通常而言，所考查粒子之间的局域相互作用是这一问题的根本基础。元胞自动机模拟一般是在基本尺度层次(例如原子、原子团簇、位错段、亚晶粒)上完成的， 但这些方法对连续体空间进行离散化和映射处理的派生方法，不存在物理特征线度或时间刻度的内禀标定问题。这就是说，对连续体系统的元胞自动机模拟，需要定义相应的基本单元和对应的变换规则，展现系统在给定层次上的行为特性

9、。这就解释了为什么将元胞自动机方法放在本章关于介观-微观方法中介绍，而不是与蒙特卡罗方法或分子动力学放在一起。2021/2/291 概述如果对主微分方程补充上述所说的“如果就”的变换规则1 概述同时，从物理角度看，分子动力学表示的是真正的微观模型，而在使用元胞自动机方法时，并不局限任何特定体系，可适用于任何系统。与蒙特卡罗方法相比，由元胞自动机方法得到的平衡系综的热力学量， 在物理上更缺少依据和基础。由于这个原因，在进行元胞自动机计算机实验之前，一个重要工作就是，检验基本模拟单元是否切实体现了基础物理实体的特性。由于元胞自动机的应用并不局限于微观体系， 所以它为在微结构模拟中实现不同空间及时间

10、尺度的方法之间的跨越，提供了一个非常方便的数值工具。2021/2/2101 概述同时，从物理角度看，分子动力学表示的是真正的微观模型元胞自动机(Cellular Automata)，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机。元胞自动机是一时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。构成: 元胞自动机最基本的组成:元胞、元胞空间、邻居及规则四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变

11、换函数所组成。2021/2/211元胞自动机(Cellular Automata)，简称CA，2元胞自动机在材料科学中多面性在对由再结晶、晶粒生长且相变现象等形成的微结构进行模拟时， 元胞自动机方法表现出特有的多面性。这种多面性归因于其在考虑大量可能的空间在变量且变换规则时所展现的广泛适用性和灵活性。例如，对再结晶和晶位生长，元胞自动机以离散化方式同时描述局域结晶结构及其形成过程。为了实现对这些特性的描述，一般是将局域晶体取向g、储存的弹性能（即某种近似可测量，诸如位错密度p或局域泰勒因子M) 以及温度T作为态变量，这些变量都是因变量，也就是它们依赖于自变量，如空间坐标(x1，x2，x3)和时

12、间t等，就所研究的特定现象来说，上述确定的状态变量应包含在所使用的各种局域结构演化定律中。这一思想表明，根据局域的信息、数据且变换规律，可以对诸如复原、成核及其生长等现象的机理给出相应合理的唯象解释。2021/2/2122元胞自动机在材料科学中多面性在对由再结晶、晶粒生长且相变现2元胞自动机在材料科学中多面性通过确定二维或三维空间格栅所对应的态变量， 元胞自动机模拟可以应用于对微结构的非均匀性质的研究，包括诸如第二相、微带、剪切带、过渡带、异相界面、晶界和孪晶等. 这些局域性缺陷结构， 可以借助其态变量的相应值或梯度值进行表述，用高位错密度和大的局域晶格曲率表征剪切带的特性。对于一个给定杂质含

13、量的晶界迁略率m， 可以采用相邻晶粒之间的取向偏差g和晶界法线的空间取向n来表征。2021/2/2132元胞自动机在材料科学中多面性通过确定二维或三维空间格栅所对3 常用元胞自动机 S. Wolfram和初等元胞自动机 初等元胞自动机是状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径r=l的一维元胞自动机，邻居集N的个数2r=2，局部映射f:S3S可记为: 其中变量有三个，每个变量取两个状态值，那么就有222=8种组合，只要给出在这八个自变量组合上的值，f就完全确定了。 2021/2/2143 常用元胞自动机 S. Wolfram和初等元胞自动机 对于任何一个一维的0，1序列，应用以

14、上规则，可以产生下一时刻的相应的序列，应用以上规则产生: t: 010111110101011100010t+1:1010001010101010001例如以下映射便是其中的一个规则:2021/2/215 对于任何一个一维的0，1序列，应用以上规则，可以产生下 八种组合分别对应0或1，这样的组合共有28=256种，即初等元胞自动机只可能有256种不同规则。 2021/2/216 八种组合分别对应0或1，这样的组合共有28=256种Converting a CAR to a binary stringRemember: 208 = 128 + 64 + 162021/2/217Convertin

15、g a CAR to a binary sCAR 30(00011110) ten time-steps2021/2/218CAR 30(00011110) ten time-stepJ. Conway和 “生命游戏”生命游戏的构成及规则:(1)元胞分布在规则划分的网格上；(2)元胞具有0，1两种状态，0代表“死”，l代表“生”；(3)元胞以相邻的8个元胞为邻居，即Moore邻居形式；2021/2/219J. Conway和 “生命游戏”生命游戏的构成及规则:(J. Conway和 “生命游戏”(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定: 在当

16、前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下一时刻该元胞继续保持为“生”，否则“死”去；在当前时刻。如果一个元胞状态为死。且八个相邻元胞中正好有三个为生。则该元胞在下一时刻 复活。否则保持为死“.2021/2/220J. Conway和 “生命游戏”(4)一个元胞的生死由其在2021/2/2212021/2/221格子气自动机格子气自动机 (Lattice一Gas Automata,LGA又称格气机)，是元胞自动机在流体力学与统计物理中的具体化，也是元胞自动机在科学研究领域成功应用的范例 (李才伟，1997)。相对于“生命游戏”来说，格子气自动机是个更注

17、重于模型的实用性。它利用元胞自动机的动态特征，来模拟流体粒子的运动。应当说，格子气自动机是一种特殊的元胞自动机模型，或者说是一个扩展的元胞自动机模型 (Extended Cellular Automata)。2021/2/222格子气自动机格子气自动机 (Lattice一Gas Aut早期格子气模型的特征如下: (1)由于流体粒子不会轻易从模型空间中消失，这个特征需要格子气自动机是一个可逆元胞自动机模型。(2)格子气自动机的邻居模型通常采用Margulos类型，即它的规则是基于一个2X2的网格空间的。 2021/2/223早期格子气模型的特征如下:2021/2/223格子气自动机 (3)依照规

18、则和邻居模型在计算完一次后，需要将这个2X2的模板沿对角方向滑动，再计算一次。那么，一个流体粒子的运动需要两步tt+lt+2才能完成。 2021/2/224格子气自动机 2021/2/2244元胞自动机的定义 元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。 具体讲,构成元胞自动机的部件被称为“元胞”，每个元胞具有一个状态。2021/2/2254元胞自动机的定义 元胞自动机是定义在一个由具有离散、4元胞自动机的定义 这些元胞规则地排列在被称为“元胞空间”的空间格网上，它们各自的状态随着时间变化，而根据一个局部规则来进行更新

19、，也就是说，一个元胞在某时刻的状态取决于、而且仅仅取决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态;元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化。2021/2/2264元胞自动机的定义 这些元胞规则地排列在被称为“元胞空间4元胞自动机的构成 元胞自动机最基本的组成元胞、元胞空间、邻居及规则四部分 2021/2/2274元胞自动机的构成 元胞自动机最基本的组成元胞、元胞空1.元胞 元胞又可称为单元,或基元，是元胞自动机的最基本的组成部分。 元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。2021/2/2281.元胞2021/2/

20、2282.状态状态可以是0,1的二进制形式，或是s0,s1, sisk 整数形式的离散集，严格意义上，元胞自动机的元胞只能有一个状态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量,李才伟(1997)在其博士论文工作中，就设计实现了这样一种称之为“多元随机元胞自动机”模型,并且定义了元胞空间的邻居(Neighbor)关系。由于邻居关系，每个元胞有有限个元胞作为它的邻居。2021/2/2292.状态状态可以是0,1的二进制形式，或是s3.元胞空间(Lattice) 元胞所分布在的空间网点集合就是这里的元胞空间。 (l)元胞空间的几何划分 理论上，它可以是任意维数的欧几里

21、德空间规则划分。目前研究多集中在一维和二维元胞自动机上,对于一维元胞自动机,元胞空间的划分只有一种。而高维的元胞自动机,元胞空间的划分则可能有多种形式,对于最为常见的二维元胞自动机,二维元胞空间通常可按三角、四方或六边形三种网格排列 。2021/2/2303.元胞空间(Lattice) 2021/2/230二维网格划分 2021/2/231二维网格划分 2021/2/231这三种规则的元胞空间划分在构模时各有优缺点:三角网格:优点: 拥有相对较少的邻居数目，这在某些时候很有用;缺点: 计算机表达与显示不方便，需转换为四方网格。2021/2/232这三种规则的元胞空间划分在构模时各有优缺点:20

22、21/2/2这三种规则的元胞空间划分在构模时各有优缺点:四方网格:优点: 直观而简单，而且特别适合于在现有计算机环境下进行表达显示; 缺点: 不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。2021/2/233这三种规则的元胞空间划分在构模时各有优缺点:2021/2/2这三种规则的元胞空间划分在构模时各有优缺点:六边形网格优点: 能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型; 缺点: 同三角网格一样，在表达显示上较为困难、复杂。2021/2/234这三种规则的元胞空间划分在构模时各有优缺点:2021/2/2(2)边界条件: 在理论上，元

23、胞空间通常是在各维向上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要定义不同的边界条件。 归纳起来，边界条件主要有三种类型:周期型、反射型和定值型。有时，为在应用中更加客观、自然地模拟实际现象，还有可能采用随机型，即在边界实时产生随机值。 2021/2/235(2)边界条件:2021/2/235ClosedPeriodic2021/2/236ClosedPeriodic2021/2/236周期型(Pehodic Boundary) 周期型是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的“圈”。对于二

24、维空间，上下相接，左右相接。而形成一个拓扑圆环面 (Torus)，形似车胎或甜点圈。周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间型作为试验。2021/2/2372021/2/237反射型(Reflective Boundary) 反射型指在边界外邻居的元胞状态是以边界为轴的镜面反射。定值型 (Constant Boundary) 定值型指所有边界外元胞均取某一固定常量，如0，1等。 2021/2/2382021/2/238 (3)构形: 在这个元胞、状态、元胞空间的概念基础上，我们引入另外一个非常重要的概念，构形(Configuration)。 构形是在某个时刻，在元胞空间上所

25、有元胞状态的空间分布组合。 通常,在数学上，它可以表示为一个多维的整数矩阵。 2021/2/239 2021/2/2394.邻居 (Neighbor) 以上的元胞及元胞空间只表示了系统的静态成分，为将“动态”引入系统，必须加入演化规则。 在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。 2021/2/2404.邻居 (Neighbor) 20214.邻居 (Neighbor) 在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞半径内的所有元胞均被认为是

26、该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式(我们以最常用的规则四方网格划分为例)。 2021/2/2414.邻居 (Neighbor) 2021/2/241von Neumann Neighborhood Moore Neighborhood Extended Moore Neighborhood 2021/2/242von Neumann Neighborhood Exten (l)冯-诺依曼(Von. Neumann)型 一个元胞的上、下、左、有相邻四个元胞为该元胞的邻居。这里，邻居半径r为1，相当于图像处理中的四邻域、四方向。其邻居定义如下: vix viy表示

27、邻居元胞的行列坐标值，vox表示中心元胞的行列坐标值。此时，对于四方网格，在维数为d时，一个元胞的邻居个数为2d。 2021/2/243 2021/2/243 (2) 摩尔(Moore)型 一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该元胞的邻居。邻居半径r同样为1，相当于图像处理中的八邻域、八方向。其邻居定义如下: 此时，对于四方网格，在维数为d时。一个元胞的邻居个数为 (3d-1)。 2021/2/244 2021/2/244 (3)扩展的摩尔(Moore)型 将以上的邻居半径r扩展为2或者更大，即得到所谓扩展的摩尔型邻居。其数学定义可以表示为: 此时，对于四方网格，在维

28、数为d时，一个元胞的邻居个数为 (2r十1)d-1)。 2021/2/245 2021/2/245 (4)马哥勒斯 (Margolus)型 这是一种同以上邻居模型迥然不同的邻居类型，它是每次将一个2x2的元胞块做统一处理，而上述前三种邻居模型中，每个元胞是分别处理的。 2021/2/246 2021/2/2465.规则(Rule)根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。我们将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数。这个函数构造了一种简单的、离散的空间/时间的局部物理成分。要修改的范围里采用这个局部物理成分对

29、其结构的“元胞”重复修改。2021/2/2475.规则(Rule)根据元胞当前状态及其邻居状况确5.规则(Rule)这样，尽管物理结构的本身每次都不发展。但是状态在变化。它可以记为 为t时刻的邻居状态组合，我们称f为元胞自动机的局部映射或局部规则 。2021/2/2485.规则(Rule)这样，尽管物理结构的本身每次都不发展6.时间 (Time)元胞自动机是一个动态系统，它在时间维上的变化是离散的，即时间t是一个整数值，而且连续等间距。 假设时间间距dt=1，若t=0为初始时刻。 那么,t=1为其下一时刻。 在上述转换函数中，一个元胞在t十1的时刻只(直接)决定于t时刻的该元胞及其邻居元胞的状

30、态，虽然，在t-1时刻的元胞及其邻居元胞的状态间接(时间上的滞后)影响了元胞在t+1的时刻的状态。2021/2/2496.时间 (Time)元胞自动机是一个动态系统，它在时间维 由以上对元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的概念。用数学符号来表示，标准的元胞自动机是一个四元组 :A=(Ld,S,N,f) A代表一个元胞自动机系统；L表示元胞空间，d是一正整数，表示元胞自动机内元胞空间的维数;S是元胞的有限的、离散的状态集合;N表示一个所有邻域内元胞的组合(包括中心元胞)，即包含n个不同元胞状态的一个空间矢量，记为:2021/2/250 由以上对元胞自动机的组成分析，我们可以更

31、加深入地理解N=(s1,s2,.,sn) n是元胞的邻居个数。siZ(整数集合)，i1，.,n；f表示将Sn映射到S上的一个局部转换函数。所有的元胞位于d维空间上，其位置可用一个d元的整数矩阵Zd来确定。 2021/2/2512021/2/251(1)同质性、齐性: 同质性反映在元胞空间内的每个元胞的变化都服从相同的规律，即元胞自动机的规则，或称为转换函数;而齐性指的是元胞的分布方式相同，大小、形状相同，空间分布规则整齐.5 元胞自动机特点2021/2/2525 元胞自动机特点2021/2/252(2)空间离散: 元胞分布在按照一定规则划分的离散的元胞空间.(3)时间离散: 系统的演化是按照等

32、间隔时间分步进行的，时间变量t只能取等步长的时刻点，形似整数形式的t0,t十l,t十2，而且，t时刻的状态构形只对其下一时刻，即t+1时刻的状态构形产生影响，而t+2时刻的状态构形完全决定于t+1的状态构形及定义在上面的砖换函数。元胞自动机的时间变量区别于微分方程中的时间变量t,那里t通常是个连续值变量；2021/2/253(2)空间离散:2021/2/253(4)状态离散有限: 元胞自动器的状态只能取有限(k)个离散值(s1,s2,.,sk)。相对于连续状态的动力系统，它不需要经过粗粒化处理就能转化为符号序列。而在实际应用中，往往需要将有些连续变量进行离散化，如分类，分级，以便于建立元胞自动

33、机模型; 2021/2/2542021/2/254(5)同步计算(并行性): 各个元胞的在时刻ti+1的状态变化是独立的行为，相互没有任何影响。若将元胞自动机的构形变化看成是对数据或信息的计算或处理，则元胞自动机的处理是同步进行的，特别适合于并行计算;2021/2/2552021/2/255(6)时空局部性: 每一个元胞的下一时刻ti+1的状态，取决于其周围半径为r的邻域(或者其它形式邻居规则定义下的邻域)中的元胞的当前时刻ti的状态，即所谓时间、空间的局部性。从信息传输的角度来看，元胞自动机中信息的传递速度是有限的; (7)维数高: 在动力系统中一般将变量的个数成为维数。 2021/2/25

34、6(6)时空局部性:2021/2/256 在实际应用过程中，许多元胞自动机模型已经对其中的某些特征进行了扩展，例如圣托斯兰州立大学(San Tose State University)研究的所谓连续型的元胞自动机，其状态就是连续的。但正如我们在元胞自动机的概念分析中指出的，在上述恃征中，同质性、并行性、局部性是元胞自动机的核心恃证，任何对元胞自动机的扩展应当尽量保持这些核心特征，尤其是局部性特征。 2021/2/257 在实际应用过程中，许多元胞自动机模型已经对其中的某些特6 概率性元胞自动机为了避免在讨论非确定性元胞自动机时发生混淆， 应该清楚地标明在算法中出现的统计元素。有两种基本方法可以

35、将确定性元胞自动机变为非确定性的。第一种方法：随机地选择所研究的晶格格座，而不是系统化地按顺序选择， 但是要使用确定性变换规则;第二种方法：用概率性变换代替确定性变换，但要系统地研究所有格座。2021/2/2586 概率性元胞自动机为了避免在讨论非确定性元胞自动机时发生混6 概率性元胞自动机第一种自功机的基本建立过程类似于波茨模型。我们将专门讨论第二种方法， 并将之归类为概率性或随机性元胞自动机。概率性元胞自动机， 就其基本过程和要素方面而言， 非常相似于普通的元胞自动机，只不过转变规则由确定性的换成了随机性的。设有N个格座组成一个一维链， 其中每个格座有 k个可能的状态Sv =0， 1， 2

36、， k-l。从而整个链共有kN个平同的排列方式。下面，由（S1， S2 ， Sn)描述的某给定晶格状态用下式整数标记：2021/2/2596 概率性元胞自动机第一种自功机的基本建立过程类似于波茨模型6 概率性元胞自动机在概率性元胞自动机中，假定每个状态i的存在概率为Pi，这个概率是时间的函数，即有Pi(t)，按照其转变概率Tij以离散时间步t=0， 1， 2. . .的方式变化发展。如果只考虑靠近的时间步(t-1)，这一规则可用下式给出：因此，如果系统在前个时间处于j状态的话，转移概率Tij就表示得到链配置组态i的概率。因为所考虑的是离散型元胞自动机方法，所以转替矩阵Tij是由局域规则决定的，

37、亦即：式中Svi和Svj分别表示状态i和j的格座变量，因而变量Svi的转换只与其最近邻及其自己的状态有关。2021/2/2606 概率性元胞自动机在概率性元胞自动机中，假定每个状态i的存6 概率性元胞自动机在概率元胞自动机中，总和型和分离型变换规则均可以使用。虽然概率性元胞自动机与Metropolis蒙特卡罗算法之间具有一定的相似性，但二者之间还是有差别的。这种差别主要表现在两个方面：第一，蒙特卡罗方法每个时间步只更新一个格座，而概率元胞自动机像大多数自动机一样，每次要全部一齐更新；第二，总体上说，元胞自动机都没有本征的长度或时间标度。2021/2/2616 概率性元胞自动机在概率元胞自动机中

38、，总和型和分离型变换规6 概率性元胞自动机尽管大多数元胞自动机，尤其它们的概率性变体（派生的)方法经常被用于处理在微观层次上的模拟问题。但是，它们的标定参数主要是由构成物理模型的基础来决定，而不是由所采用的元胞自动机算法来决定。2021/2/2626 概率性元胞自动机尽管大多数元胞自动机，尤其它们的概率性变7晶格气元胞自动机方法使用晶格气元胞自动机，通常可以在考虑统计涨落的情况下，能够对反应-扩散这类现象进行时间空间离散化模拟处理。尽管这些概率性自动机通常被用于微观体系的模拟，但是正像属于自动机类的所有模型那样，它们的使用并不仅限于在微观层次上的应用。如果能找到合适的元胞自动机变换规则，它们还

39、可以用于介观或宏观系统的模拟。2021/2/2637晶格气元胞自动机方法使用晶格气元胞自动机，通常可以在考虑统7晶格气元胞自动机方法同普通自动机一样，晶格气元胞自动机也具有一系列性质：时间、空间上都是离散的；使用离散晶格；通过简单的局域次近邻变换、反应及扩散定律，还可以用于宏观和介现层次上的复杂动力学系统特性的模拟。晶格气元胞自动机格栅(grid) 是由结点与其最近邻相互连接的规则排列组成，格栅可能具有立方或六角系对称性。格座之间的连接通常被称为 键。一般地认为，变换规则和反应定律与结点相联系，而与连接键无关。2021/2/2647晶格气元胞自动机方法同普通自动机一样，晶格气元胞自动机也具7晶

40、格气元胞自动机方法在传统的元胞自动机方法中，晶格格座是根据态变量的取值配置的，其态变量值被认为代表了所有允许状态中的一个态。在晶格气自动机中这些态变量由一个粒子组成的离散集合代替。这些粒子集通常具有一定速度，但没有质量和相互作用能。在模拟中粒子数量是守恒的，这反映了质量守恒定律。在晶格气自动机中，结点的状态是由局域粒子密度决定的，而不是由场变量决定。这一粒子的集合就被称为晶格气。2021/2/2657晶格气元胞自动机方法在传统的元胞自动机方法中，晶格格座是根7晶格气元胞自动机方法具有立方格栅对称性简单二维晶格气元胞自动机中： 每个结点最多被4 个粒子占据； 这些粒子可以有4个速度，但其绝对值相

41、等； 其不同点在于它们分别指向4个可能的方向。2021/2/2667晶格气元胞自动机方法具有立方格栅对称性简单二维晶格气元胞自7晶格气元胞自动机方法在具有平面六角对称性的格栅中： 每个结点被占据的粒子数可以达到6个； 这些粒子可以有6个不同的速度矢量。2021/2/2677晶格气元胞自动机方法在具有平面六角对称性的格栅中：20217晶格气元胞自动机方法无论是上述哪种情况，每个给定的状态最多只能填充一个粒子，不可能有两个粒子具有相同的格栅位置和相同的速度（矢量)方向。晶格气元胞自动机的动力学演化：在离散时间t间隔内，粒子将从它们所占据的格座运动到它们所指向的格座；在结点，将发生弹性碰撞，其中在新

42、的组态，质量(粒子数)、动量(速度大小)是守恒的。根据入射粒子的排列状态，可能会有几个碰撞后的组态。最终的结点状态通常是在这些组态中随机地给出，也可以通过给定的确定性碰撞定律进行选取。对于惰性粒子的情况，只考虑碰撞就可以了，对于改进型化学形式的晶格气元胞自动机，同时还要考虑反应问题，这时的碰撞将会形成具有不同性质的新的反应产物。2021/2/2687晶格气元胞自动机方法无论是上述哪种情况，每个给定的状态最多7晶格气元胞自动机方法Two-dimensional lattice gas cellular automaton with a hexagonal grid. The plots show

43、 some possible pre-collision configurations at a node together with some collision rules. The rules represent possible consecutive particle arrangements after elastic collision. Some lattice gas automata select these configurations randomly rather than from a fixed list. During the collision, the mo

44、mentum (magnitude of particle velocities) and the mass (particle number) axe conserved. The flight directions axe usually changed. 2021/2/2697晶格气元胞自动机方法Two-dimensional lat7晶格气元胞自动机方法所有可能的各种两粒子、三粒子、四粒子、五粒子甚至是六粒子碰撞后，其形成的产物和新组态，包括那些普通粒子与反应产物之间的碰撞在内，通常在模拟之前均被记录在数据库中。这些信息描述了粒子相互作用的微观物理与化学特征。近年来，人们提出了各种改进

45、型晶格气元胞自动机方法。晶格玻尔兹曼方法使用不同速度幅值的温度相关性晶格气自动机在运动之前考虑近邻粒子特性的各种多相模型等2021/2/2707晶格气元胞自动机方法所有可能的各种两粒子、三粒子、四粒子、8 元胞自动机的分类 S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类 :(1) 平稳型: 自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态,不随时间变化而变化。2021/2/2718 元胞自动机的分类 S. Wolfram在80年代初做的周期型: 经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable

46、Paterns)或周期结构(Perlodical Patterns)。由于这些结构可看作是一种滤波器(Filter)，故可应用到图像处理的研究中。 2021/2/272周期型:2021/2/272(3) 混沌型: 自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变化，通常表现为分形分维特征。复杂型: 出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。2021/2/2732021/2/273按元胞空间的维数分类，元胞自动机通常可以分为: (1) 一维元胞自动机:元胞按等间隔方式分布在一条向两侧无限延伸的直线上，每个元胞 (Cell)

47、具有有限个状态s，sS=s1,s2,.,sk，定义邻居半径r，元胞的左右两侧共有2r个元胞作为其邻居集合N，定义在离散时间维上的转换函数f:S2r+1S可以记为: 为第i个元胞在t时刻的状态。 称上述A=S,N,f三元组(维数d1)为一维元胞自动机 2021/2/274按元胞空间的维数分类，元胞自动机通常可以分为: 2021/2二维元胞自动机: 元胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以J. H. Conway的“生命游戏”为代表，应用最为广泛。由于，世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到二维空间上，所以，二维元胞自动机的应用最为广泛，

48、多数应用模型都是二维元胞自动机模型。2021/2/275二维元胞自动机:2021/2/275(3)三维元胞自动机：目前，Bays(Bays,C,1988)等人在这方面做了若干试验性工作，包括在三维空间上实现了生命游戏，延续和扩展了一维和二维元胞自动机的理论。(4)高维元胞自动机：只是在理论上进行少量的探讨，实际的系统模型较少。Lee Meeker在他的硕士论文中，进行了对四维元胞自动机的探索。 2021/2/276(3)三维元胞自动机：目前，Bays(Bays,C,19882021/2/2772021/2/2772021/2/2782021/2/2789 确定性元胞自动机解法冷加工金属中原级再

49、结晶模拟的确定性元胞自动机方法:假定成核和新结晶晶粒生长所需驱动力均来源于局域位错密度的梯度; 并且当有碰撞时生长终止。对于复原和成核，元胞自动机允许引入任意的条件。起始数据应包括格栅几何参数和态变量取值等信息，例如，温度、成核概率、晶界迁移率、位错密度和晶体取向。这些数据必须以三维基体的角度提供。也就是说， 这些数据能够描述作为空间函数的初始微结构的主要特征。为降低对计算机存储器的要求，可以指定所研究的晶粒数，并且每个元胞所储存的晶粒数只能是这个指定的数目。2021/2/2799 确定性元胞自动机解法冷加工金属中原级再结晶模拟的确定性元9 确定性元胞自动机解法计算机主存储器中储存的排列数组是

50、晶粒表格(grain list)和表面表格(surface list)：首先应含有晶粒结晶取向的信息。输入数据由晶粒数目和描述其晶粒取向的三个欧拉角组成。其次，描述那些只拥有同一个晶粒表面的元胞。为了进一步降低所需要的存储量，在上述表中只储存两个独立的数组，即元胞的坐标和共用同一个元胞的晶粒数目。2021/2/2809 确定性元胞自动机解法计算机主存储器中储存的排列数组是晶粒9 确定性元胞自动机解法2021/2/2819 确定性元胞自动机解法2021/2/2819 确定性元胞自动机解法在简单的有限差分公式中，可以计算出f1的因子，这个因子f与弛豫时间r，温度T和时间ti有关。这时，在时间ti时

51、的位错密度就可表示为：在更为复杂的方法中， 函数f还将依赖于局域取向(也就是把普通的复原转变为与取向相关的复原。2021/2/2829 确定性元胞自动机解法在简单的有限差分公式中，可以计算出f9 确定性元胞自动机解法在成核阶段，各个元胞或元胞团簇应该由变形态转变为再结晶状态。对所建立模型的体材料样品，可考虑给定半径球的排列情况，以几何学的角度给出所使用的格栅。同时，合理规定各种不同的确定性或统计性成核临界条件。在最简单的可能方法中，若不考虑特定的临界条件，可以采用变形基体中晶核晶粒的格座饱和的统计空间排列。2021/2/2839 确定性元胞自动机解法在成核阶段，各个元胞或元胞团簇应该由9 确定

52、性元胞自动机解法2021/2/2849 确定性元胞自动机解法2021/2/2849 确定性元胞自动机解法把这些反映晶粒取向特性的临界条件，以及产生的晶核应与基体有相似取向的规则结合起来，就相当于给出一个取向成核的假说。在成核阶段之后，晶核晶粒应添加到晶粒表中， 一般假定其形状为球形。所有属于这个球表面的晶胞都要增补到表面清单表格中。球内部的元胞被记作属于再结晶的。在使用这些球状晶粒时，必须避免格栅几何因素对成长晶粒的形状产生大的影响。 成核条件决定了在时间ti时所产生的晶核数Ni。为讨论问题之方便，可适当地补充其他成核条件，诸如格座饱和、固定成核速率等。2021/2/2859 确定性元胞自动机解法把这些反映晶粒取向特性的临界条件，以9 确定性元胞自动机解法在生长阶段，对于每个晶粒可执行个循环，这个循环就是遍及所有属于目标晶粒表面的元胞。在这个循环中，可以确定表面元胞与其非再结晶近邻元胞两者结晶取向之间的偏差。晶界迁移率是这个取向偏差g 和温度T的函数。迁移率的数值一般可以从现成表中查得，但对于Read-Shockley型小角晶界和孪晶晶界， 其值一致性较差，例如3或9，这时常通把迁移率设置为零。2021/2/2869 确定性元胞自动机解法在生长阶段，对于每个晶粒可执行个循环9 确定性元胞自动机解法在原级结晶