元胞自动机.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,元胞自动机,1,概述,元胞自动机,(Cellular Automata),作为描述处理复杂系统在离散空间,、,时间上演化规律的算法，通常采用对,晶格格座,的,局域或整体,的,确定性和概率性,变换规则进行具体操作。,空间变量可以代表,实空间、动量空间或波矢空间,。,晶格定义为具有固定数目的点，这些点可以看作是有限差分场中的结点。,晶格一般是,规则晶格,，其,维数,、,大小,可以是,任意,的。它表述了系统由,基础实体,(elementary entities),形成的构象，这些,基础实体,被认为与所用模型密切相关，它们可以是,任意大小的连续体型体积单元、原子颗粒、晶格缺陷或生物界中的动物,等等。,1,概述,构成系统的基本实体，可以由,广义态变量,(,诸如无量纲数、粒子密度、晶格缺陷密度、粒子速度、颜色、血压或动物种类等,),进行,量化,表述。在每个,独立的格座,，这些态变量的实际取值都是,确定的,。并且认为，每一个结点代表,有限个可能,的,离散状态,中的,一个,态。,将某些,变换规则,应用于,每个结点状态,，就会发生自动机的,演化,。,这些,规则,决定着,晶格格座,的,状态,；对,于,局域规则，,格座状态,是其,前一状态,及,近邻格点,（座）状态的,函数,，而在,整体,变换规则下，则为,所有格座状态的函数,。传统元胞自动机大多采用局域变换规则。,这种方法对于在,规则晶格结构方面,的应用是比较容易接受的。特别对于非均匀介质，在讨论的晶格区域采用较小的晶格间距比较妥当；而且，还必须考虑对变换速率进行合理修正和重正化。,1,概述,元胞自动机以,离散时间,步发展演化。,经过一个,时间间隔,，要对所有结点的,态变量,值同时更新。,近年来，通过对,Wolfram(1986),创立的经典元胞自动机,(CCA),方法的合理拓展，已经建立起一批更,广义的,元胞自动机,(GCA),方法。,后者作为元胞自动机方法的变种，它比原来的方法有更强的适应性，尤其是在,计算材料学,中的一些特殊应用方面优点突出。,广义微结构元胞自动机可以采用元胞或格座的离散空间格栅，这时的空间既可以是实空间，也可以是动量空间或波矢空间。然而，在空间上通常被认为是均匀的，亦即所有格座都是等价的，并被排布在规则晶格上，其中的变换规则在各处都是一样的。,1,概述,同时，像常规自动机那样，假定它们是有限个可能状态中的一个，并对所有元胞状态同步更新。此外，它们与常规自动机不同的是，格座变换既可以按照,确定性定律,，也可以按照,概率性定律。,因而，广义微结构元胞自动机在计算材料学中的发展势头日益强劲。,鉴于这些特点，元胞自动机方法为,模拟动力学系统,的演化提供了一种,直接的手段,，这些动力学系统包含有大量基于,短程相互作用,或,长程相互作用,的相似组元,。,对于一个简单的物理系统，,时间,是其,唯一个独立变量,（自变量）这种直接方法，就相当于对多少有些复杂的偏微分方程组，利用,有限差分近似法,给出其,离散解,。,1,概述,应该强调指出，这些元胞自动机方法,对,基础实体,类型和选用的变换规则没有任何限制。它们可以对不同的处理状况进行描述，诸如：简单有限差分模拟中态变量值的分布，混合算法的色问题，“教室里的儿童健康情况,在任何变换条件下的模糊集合元素，以及元胞的初级生长与衰减过程等。,在计算材料学领域，元胞自动机的变换规则般存在于有限差分、有限元，以及关于时间和,2,个或,3,个空间坐标的偏微分藕合方程组的蒙特卡罗近似之中。同时，局域变换描述近邻格座之间的短程相互作用，而整体变换规则能够处理长程相互作用。通常，根据各个,态,变量的取值可以给出相应格座的状态。,1,概述,元胞自动机通常被认为是离散计算方法的普遍化推广,，,具有更加,广泛的适用性,和,多功能,的特点,。,元胞自,动,机并不简单地等同于普通模拟方法，例如各种有限,差,分法、有限,元,法、伊辛,(Ising),法、波茨,(Potts),方法等。,这种灵活适用性是基于这样个事实：除了采用简明的数学表达式作为变量和变换规则之外，自动机,还,能够实际地包括任何元素或规则。,1,概述,在材料科学中，有时对常规有限差分计算方法补充一些“如果,.,就,.,”规则是很有意义的。,在塑性学、断裂力学或晶体生长等领域遇到的情况。上述附加规则的方法为处理,“,数学上的奇点,(,即非光滑函数表述中的临界或自发效应,),问题提供了一种简单有效的选择。这些规则经常出现在微结构模拟中,：,离散位错动力学模拟经常包含有这样一个规则“如果两个反平行螺位错相互靠近到其间距小于,5,个伯格斯矢量时，它们就会自发淹没,。,在断裂力学或弹簧模型中，会经常包含这样的规则“如果裂纹速度达到某个值，试验样品将自主损坏,。,在重结晶模拟中，会经常遇到这样的规则“如果晶体局域取向误差达到某一个值，格座将满足成核的动力学非稳定性临界条件”或“局域储存的弹性能达到某个临界值，格座将满足成核的热力学非稳定性条件”。,1,概述,如果对主微分方程补充上述所说的,“如果就”,的变换规则，就可以对复杂系统的动力学行为特性进行模拟。通常而言，所考查粒子之间的局域相互作用是这一问题的根本基础。,元胞自动机模拟一般是在,基本尺度层次,(,例如原子、原子团簇、位错段、亚晶粒,),上完成的，但这些方法对连续体空间进行离散化和映射处理的派生方法，,不存在物理,特,征线度或时间刻度的内禀标定问题,。这就是说，对连续体系统的元胞自动机模拟，需要定义相应的,基本单元,和,对应的变换规则,，展现系统在给定层次上的行为特性。这就解释了为什么将元胞自动机方法放在本章关于介观,-,微观方法中介绍，而不是与蒙特卡罗方法或分子动力学放在一起。,1,概述,同时，,从,物理角度看，,分子动力学表示的是真正的微观模型,，而在使用,元胞自动机,方法时，并不局限任何特定体系，,可适用于任何系统,。,与,蒙特卡罗方法,相比，由元胞自动机方法得到的平衡系综的热力学量，在物理上更缺少依据和基础。由于这个原因，在进行元胞自动机计算机实验之前，,一个重要工作就是,，检验基本模拟单元,是否切实体现了,基础物理实体,的特性,。,由于元胞自动机的应用并不局限于微观体系，所以它为在微结构模拟中实现不同空间及时间尺度的方法之间的跨越，提供了一个非常方便的数值工具。,元胞自动机,(Cellular Automata),，简称,CA,，也有人译为,细胞自动机、点格自动机、分子自动机或单元自动机,。,元胞自动机,是一时间和空间都离散的动力系统。散布在规则格网,(Lattice Grid),中的每一元胞,(Cell),取,有限的,离散状态，遵循,同样的,作用规则，依据确定的局部规则作,同步更新,。大量元胞通过简单的相互作用而构成动态系统的演化。,构成,:,元胞自动机最基本的组成,:,元胞、元胞空间、邻居及规则,四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。,2,元胞自动机在材料科学中多面性,在对由,再结晶、晶粒生长且相变现象,等形成的微结构进行模拟时，元胞自动机方法表现出特有的多面性。这种多面性归因于其在考虑大量可能的空间在变量且变换规则时所展现的广泛适用性和灵活性。,例如，对再结晶和晶位生长，元胞自动机以离散化方式同时描述局域结晶结构及其形成过程。为了实现对这些特性的描述，一般是将局域晶体取向,g,、储存的弹性能（即某种近似可测量，诸如位错密度,p,或局域泰勒因子,M),以及温度,T,作为态变量，这些变量都是因变量，也就是它们依赖于自变量，如空间坐标,(x1,，,x2,，,x3),和时间,t,等，就所研究的特定现象来说，上述确定的状,态,变量应包含在所使用的各种局域结构演化定律中。这一思想表明，根据局域的信息、数据且变换规律，可以对诸如复原、成核及其生长等现象的机理给出相应合理的唯象解释,。,2,元胞自动机在材料科学中多面性,通过确定二维或三维空间格栅所对应的态变量，元胞自动机模拟可以应用于对微结构的非均匀性质的研究，包括诸如第二相、微带、剪切带、过渡带、异相界面、晶界和孪晶等,.,这些局域性缺陷结构，可以借助其态变量的相应值或梯度值进行表述，用高位错密度和大的局域晶格曲率表征剪切带的特性。对于一个给定杂质含量的晶界迁略率,m,，可以采用相邻晶粒之间的取向偏差,g,和晶界法线的空间取向,n,来表征。,3,常用元胞自动机,S.Wolfram,和初等元胞自动机,初等元胞自动机是状态集,S,只有两个元素,s,1,，,s,2,，即状态个数,k=2,，邻居半径,r=l,的一维元胞自动机，邻居集,N,的个数,2r=2,，局部映射,f:S,3,S,可记为,:,其中变量有三个，每个变量取两个状态值，那么就有,2,2,2=8,种组合，只要给出在这八个自变量组合上的值，,f,就完全确定了。,对于任何一个一维的,0,，,1,序列，应用以上规则，可以产生下一时刻的相应的序列，应用以上规则产生,:,t:010111110101011100010t+1:1010001010101010001,例如以下映射便是其中的一个规则,:,八种组合分别对应,0,或,1,，这样的组合共有,2,8,=256,种，即初等元胞自动机只可能有,256,种不同规则。,Converting a CAR to a binary string,Remember:208=128+64+16,CAR 30(00011110)ten time-steps,J.Conway,和“生命游戏”,生命游戏的构成及规则,:,(1),元胞分布在规则划分的网格上；,(2),元胞具有,0,，,1,两种状态，,0,代表,“,死,”,，,l,代表,“,生,”,；,(3),元胞以相邻的,8,个元胞为邻居，即,Moore,邻居形式；,J.Conway,和“生命游戏”,(4),一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态,(,确切讲是状态的和,),决定,:,在当前时刻，如果一个元胞状态为,“,生,”,，且八个相邻元胞中有两个或三个的状态为,“,生,”,，则在下一时刻该元胞继续保持为,“,生,”,，否则,“,死,”,去；,在当前时刻。如果一个元胞状态为,死,。且八个相邻元胞中正好有三个为,生,。则该元胞在下一时刻,复活,。否则保持为,死,“,.,格子气自动机,格子气自动机,(Lattice,一,Gas Automata,LGA,又称格气机,),，是元胞自动机在流体力学与统计物理中的具体化，也是元胞自动机在科学研究领域成功应用的范例,(,李才伟，,1997),。相对于,“,生命游戏,”,来说，格子气自动机是个更注重于模型的实用性。它利用元胞自动机的动态特征，来模拟流体粒子的运动。,应当说，格子气自动机是一种特殊的元胞自动机模型，或者说是一个扩展的元胞自动机模型,(Extended Cellular Automata),。,早期格子气模型的特征如下,:,(1),由于流体粒子不会轻易从模型空间中消失，这个特征需要格子气自动机是一个可逆元胞自动机模型。,(2),格子气自动机的邻居模型通常采用,Margulos,类型，即它的规则是基于一个,2X2,的网格空间的。,格子气自动机,(3),依照规则和邻居模型在计算完一次后，需要将这个,2X2,的模板沿对角方向滑动，再计算一次。那么，一个流体粒子的运动需要两步,t,t+l,t+2,才能完成。,4,元胞自动机的定义,元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。,具体讲,构成元胞自动机的部件被称为,“,元胞,”,，每个元胞具有一个状态。,4,元胞自动机的定义,这些元胞规则地排列在被称为,“,元胞空间,”,的空间格网上，它们各自的状态随着时间变化，而根据一个局部规则来进行更新，,也就是说，一个元胞在某时刻的状态取决于、而且仅仅取决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态,;,元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化,。,4,元胞自动机的构成,元胞自动机最基本的组成元胞、元胞空间、邻居及规则四部分,1.,元胞,元胞又可称为单元,或基元，是元胞自动机的最基本的组成部分。,元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。,2.,状态,状态可以是,0,1,的二进制形式，或是,s,0,s,1,s,i,s,k,整数形式的离散集，严格意义上，元胞自动机的元胞只能有一个状态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量,李才伟,(1997),在其博士论文工作中，就设计实现了这样一种称之为,“,多元随机元胞自动机,”,模型,并且定义了元胞空间的邻居,(Neighbor),关系。由于邻居关系，每个元胞有有限个元胞作为它的邻居。,3.,元胞空间,(Lattice),元胞所分布在的空间网点集合就是这里的元胞空间。,(l),元胞空间的几何划分,理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上,对于一维元胞自动机,元胞空间的划分只有一种。而高维的元胞自动机,元胞空间的划分则可能有多种形式,对于最为常见的二维元胞自动机,二维元胞空间通常可按三角、四方或六边形三种网格排列。,二维网格划分,这三种规则的元胞空间划分在构模时各有优缺点,:,三角网格,:,优点,:,拥有相对较少的邻居数目，这在某些时候很有用,;,缺点,:,计算机表达与显示不方便，需转换为四方网格。,这三种规则的元胞空间划分在构模时各有优缺点,:,四方网格,:,优点,:,直观而简单，而且特别适合于在现有计算机环境下进行表达显示,;,缺点,:,不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的,HPP,模型。,这三种规则的元胞空间划分在构模时各有优缺点,:,六边形网格,优点,:,能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的,FHP,模型,;,缺点,:,同三角网格一样，在表达显示上较为困难、复杂。,(2),边界条件,:,在理论上，元胞空间通常是在各维向上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要定义不同的边界条件。,归纳起来，边界条件主要有三种类型,:,周期型、反射型和定值型。,有时，为在应用中更加客观、自然地模拟实际现象，还有可能采用随机型，即在边界实时产生随机值。,Closed,Periodic,周期型,(Pehodic Boundary),周期型是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的,“,圈,”,。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面,(Torus),，形似车胎或甜点圈。周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间型作为试验。,反射型,(Reflective Boundary),反射型指在边界外邻居的元胞状态是以边界为轴的镜面反射。,定值型,(Constant Boundary),定值型指所有边界外元胞均取某一固定常量，如,0,，,1,等。,(3),构形,:,在这个元胞、状态、元胞空间的概念基础上，我们引入另外一个非常重要的概念，,构形,(Configuration),。,构形是在某个时刻，在元胞空间上所有元胞状态的空间分布组合。,通常,在数学上，它可以表示为一个多维的整数矩阵。,4.,邻居,(Neighbor),以上的元胞及元胞空间只表示了系统的静态成分，为将,“,动态,”,引入系统，必须加入演化规则。,在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。,4.,邻居,(Neighbor),在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞半径内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式,(,我们以最常用的规则四方网格划分为例,),。,von Neumann Neighborhood,Moore Neighborhood,Extended Moore Neighborhood,(l),冯,-,诺依曼,(Von.Neumann),型,一个元胞的上、下、左、有相邻四个元胞为该元胞的邻居。这里，邻居半径,r,为,1,，相当于图像处理中的四邻域、四方向。其邻居定义如下,:,v,ix,v,iy,表示邻居元胞的行列坐标值，,v,ox,表示中心元胞的行列坐标值。此时，对于四方网格，在维数为,d,时，一个元胞的邻居个数为,2,d,。,(2),摩尔,(Moore),型,一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该元胞的邻居。邻居半径,r,同样为,1,，相当于图像处理中的八邻域、八方向。其邻居定义如下,:,此时，对于四方网格，在维数为,d,时。一个元胞的邻居个数为,(3,d,-1),。,(3),扩展的摩尔,(Moore),型,将以上的邻居半径,r,扩展为,2,或者更大，即得到所谓扩展的摩尔型邻居。其数学定义可以表示为,:,此时，对于四方网格，在维数为,d,时，一个元胞的邻居个数为,(2r,十,1),d,-1),。,(4),马哥勒斯,(Margolus),型,这是一种同以上邻居模型迥然不同的邻居类型，它是每次将一个,2x2,的元胞块做统一处理，而上述前三种邻居模型中，每个元胞是分别处理的。,5.,规则,(Rule),根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。我们将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数。这个函数构造了一种简单的、离散的空间,/,时间的局部物理成分。要修改的范围里采用这个局部物理成分对其结构的,“,元胞,”,重复修改。,5.,规则,(Rule),这样，尽管物理结构的本身每次都不发展。但是状态在变化。它可以记为,为,t,时刻的邻居状态组合，我们称,f,为元胞自动机的局部映射或局部规则。,6.,时间,(Time),元胞自动机是一个动态系统，它在时间维上的变化是离散的，即时间,t,是一个整数值，而且连续等间距。,假设时间间距,dt=1,，若,t=0,为初始时刻。,那么,t=1,为其下一时刻。,在上述转换函数中，一个元胞在,t,十,1,的时刻只,(,直接,),决定于,t,时刻的该元胞及其邻居元胞的状态，虽然，在,t-1,时刻的元胞及其邻居元胞的状态间接,(,时间上的滞后,),影响了元胞在,t+1,的时刻的状态。,由以上对元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的概念。用数学符号来表示，标准的元胞自动机是一个四元组,:,A=(L,d,S,N,f),A,代表一个元胞自动机系统；,L,表示元胞空间，,d,是一正整数，表示元胞自动机内元胞空间的维数,;S,是元胞的有限的、离散的状态集合,;N,表示一个所有邻域内元胞的组合,(,包括中心元胞,),，即包含,n,个不同元胞状态的一个空间矢量，记为,:,N=(s,1,s,2,.,s,n,),n,是元胞的邻居个数。,s,i,Z(,整数集合,),，,i1,，,.,n,；,f,表示将,S,n,映射到,S,上的一个局部转换函数。所有的元胞位于,d,维空间上，其位置可用一个,d,元的整数矩阵,Z,d,来确定。,(1),同质性、齐性,:,同质性反映在元胞空间内的每个元胞的变化都服从相同的规律，即元胞自动机的规则，或称为转换函数,;,而齐性指的是元胞的分布方式相同，大小、形状相同，空间分布规则整齐,.,5,元胞自动机特点,(2),空间离散,:,元胞分布在按照一定规则划分的离散的元胞空间,.,(3),时间离散,:,系统的演化是按照等间隔时间分步进行的，时间变量,t,只能取等步长的时刻点，形似整数形式的,t0,t,十,l,t,十,2,，而且，,t,时刻的状态构形只对其下一时刻，即,t+1,时刻的状态构形产生影响，而,t+2,时刻的状态构形完全决定于,t+1,的状态构形及定义在上面的砖换函数。元胞自动机的时间变量区别于微分方程中的时间变量,t,那里,t,通常是个连续值变量；,(4),状态离散有限,:,元胞自动器的状态只能取有限,(k),个离散值,(s,1,s,2,.,s,k,),。相对于连续状态的动力系统，它不需要经过粗粒化处理就能转化为符号序列。而在实际应用中，往往需要将有些连续变量进行离散化，如分类，分级，以便于建立元胞自动机模型,;,(5),同步计算,(,并行性,):,各个元胞的在时刻,t,i,+1,的状态变化是独立的行为，相互没有任何影响。若将元胞自动机的构形变化看成是对数据或信息的计算或处理，则元胞自动机的处理是同步进行的，特别适合于并行计算,;,(6),时空局部性,:,每一个元胞的下一时刻,t,i,+1,的状态，取决于其周围半径为,r,的邻域,(,或者其它形式邻居规则定义下的邻域,),中的元胞的当前时刻,ti,的状态，即所谓时间、空间的局部性。从信息传输的角度来看，元胞自动机中信息的传递速度是有限的,;,(7),维数高,:,在动力系统中一般将变量的个数成为维数。,在实际应用过程中，许多元胞自动机模型已经对其中的某些特征进行了扩展，例如圣托斯兰州立大学,(San Tose State University),研究的所谓连续型的元胞自动机，其状态就是连续的。但正如我们在元胞自动机的概念分析中指出的，在上述恃征中，,同质性、并行性、局部性,是元胞自动机的核心恃证，任何对元胞自动机的扩展应当尽量保持这些核心特征，尤其是局部性特征。,6,概率性元胞自动机,为了避免在讨论非确定性元胞自动机时发生混淆，应该清楚地标明在算法中出现的统计元素。有两种基本方法可以将确定性元胞自动机变为非确定性的。,第一种方法：随机地选择所研究的晶格格座，而不是系统化地按顺序选择，但是要使用确定性变换规则,;,第二种方法：用概率性变换代替确定性变换，但要系统地研究所有格座。,6,概率性元胞自动机,第一种自功机的基本建立过程类似于波茨模型。我们将专门讨论第二种方法，并将之归类为概率性或随机性元胞自动机。,概率性元胞自动机,，就其基本过程和要素方面而言，非常相似于普通的元胞自动机，只不过转变规则由,确定性的换成了随机性的,。,设有,N,个格座组成一个一维链，其中每个格座有,k,个可能的状态,S,v,=0,，,1,，,2,，,k-l,。从而整个链共有,k,N,个平同的排列方式。下面，由（,S,1,，,S,2,，,S,n,),描述的某给定晶格状态用下式整数标记：,6,概率性元胞自动机,在概率性元胞自动机中，假定每个状态,i,的存在概率为,P,i,，,这个概率是时间的函数，即有,P,i,(t),，按照其,转变概率,T,ij,以离散时间步,t=0,，,1,，,2.,的方式变化发展。如果只考虑靠近的时间步,(t-1),，这一规则可用下式给出：,因此，如果系统在前个时间处于,j,状态的话，,转移概率,T,ij,就表示得到链配置组态,i,的概率。,因为所考虑的是,离散型元胞自动机方法,，所以,转替矩阵,T,ij,是由,局域规则,决定的，亦即：,式中,S,v,i,和,S,v,j,分别表示状态,i,和,j,的格座变量，因而变量,S,v,i,的转换只与其最近邻及其自己的状态有关。,6,概率性元胞自动机,在概率元胞自动机中，总和型和分离型变换规则均可以使用。虽然概率性元胞自动机与,Metropolis,蒙特卡罗算法之间具有一定的相似性，但二者之间还是有差别的。这种差别主要表现在两个方面：,第一，蒙特卡罗方法每个时间步只更新一个格座，而概率元胞自动机像大多数自动机一样，每次要全部一齐更新；,第二，总体上说，元胞自动机都没有本征的长度或时间标度。,6,概率性元胞自动机,尽管大多数元胞自动机，尤其它们的概率性变体（派生的,),方法经常被用于处理在微观层次上的模拟问题。但是，它们的标定参数主要是由构成物理模型的基础来决定，而不是由所采用的元胞自动机算法来决定。,7,晶,格气元胞自动机方法,使用,晶格气元胞自动机,，通常可以在考虑,统计涨落,的情况下，能够对,反应,-,扩散,这类现象进行,时间空间离散化,模拟处理。,尽管这些,概率性自动机,通常被用于,微观,体系的模拟，,但是正像属于自动机类的所有模型那样,，它们的使用并不仅限于在微观层次上的应用。如果能找到,合适的,元胞自动机,变换规则,，它们还可以用于,介观或宏观系统,的模拟。,7,晶,格气元胞自动机方法,同普通自动机一样，晶格气元胞自动机也具有一系列性质：,时间、空间上都是离散的；,使用离散晶格；,通过简单的局域次近邻变换、反应及扩散定律，还可以用于宏观和介现层次上的复杂动力学系统特性的模拟,。,晶格气元胞自动机,格栅,(grid),是由结点与其最近邻相互连接的规则排列组成，格栅可能具有立方或六角系对称性。,格座之间的连接通常被称为,键,。,一般地认为，变换规则和反应定律与结点相联系，而与连接键无关。,7,晶,格气元胞自动机方法,在,传统的元胞自动机,方法中,，晶格格,座,是根据态变量,的,取值配置,的,，其态变量值被认为,代表了所有允许状态中,的一个态。在,晶格气自动机,中,这些态变量由一个粒子组成,的,离散集合,代替。,这些粒子集通常具有一定速度,，但没有质量和相互作用能,。,在,模拟,中粒子数量是守恒,的,，这,反映了质量守恒定律,。,在晶格气,自动机中,，,结点,的,状态是由局域粒子密度,决定的,，而,不是由场变量决定。,这一粒子的集合就被称为,晶格,气,。,7,晶,格气元胞自动机方法,具有立方格栅对称性简单二维晶格气元胞自动机中：,每个结点最多被,4,个粒子占据；,这些粒子可以有,4,个速度，但其绝对值相等；,其不同点在于它们分别指向,4,个可能的方向。,7,晶,格气元胞自动机方法,在具有平面六角对称性的格栅中：,每个结点被占据的粒子数可以达到,6,个；,这些粒子可以有,6,个不同的速度矢量。,7,晶,格气元胞自动机方法,无论是上述哪种情况，每个给定的状态最多只能填充一个粒子，不可能有两个粒子具有相同的格栅位置和相同的速度（矢量,),方向。,晶格气元胞自动机的动力学演化：,在离散时间,t,间隔,内，粒子将从它们所,占据的,格座运动到它们,所指向的,格座；,在结点，将发生弹性碰撞，其中在新的组态，质量,(,粒子数,),、动量,(,速度大小,),是守恒的。,根据入射粒子的排列状态，可能会有几个碰撞后的组态。最终的结点状态通常是在这些组态中随机地给出，,也,可以通过给定的确定性碰撞定律进行选取。,对于惰性粒子的情况，只考虑碰撞就可以了，对于改进型化学形式的晶格气元胞自动机，同时还要考虑反应问题，这时的碰撞将会形成具有不同性质的新的反应产物。,7,晶,格气元胞自动机方法,Two-dimensional lattice gas cellular automaton with a hexagonal grid.The plots show 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 momentum(magnitude of particle velocities)and the mass(particle number)axe conserved.The flight directions axe usually changed.,7,晶,格气元胞自动机方法,所有可能的各种两粒子、三粒子、四粒子、五粒子甚至是六粒子碰撞后，其形成的产物和新组态，包括那些普通粒子与反应产物之间的碰撞在内，通常在模拟之前均被记录在数据库中。这些信息描述了粒子相互作用的微观物理与化学特征。,近年来，人们提出了各种改进型晶格气元胞自动机方法。,晶格玻尔兹曼方法,使用不同速度幅值的温度相关性晶格气自动机,在运动之前考虑近邻粒子特性的各种多相模型等,8,元胞自动机的分类,S.Wolfram,在,80,年代初做的基于动力学行为的元胞自动机分类,:,(1),平稳型,:,自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态,不随时间变化而变化。,周期型,:,经过一定时间运行后，元胞空间趋于一系列简单的固定结构,(Stable Paterns),或周期结构,(Perlodical Patterns),。由于这些结构可看作是一种滤波器,(Filter),，故可应用到图像处理的研究中。,(3),混沌型,:,自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变化，通常表现为分形分维特征。,复杂型,:,出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。,按元胞空间的维数分类，元胞自动机通常可以分为,:,(1),一维元胞自动机,:,元胞按等间隔方式分布在一条向两侧无限延伸的直线上，每个元胞,(Cell),具有有限个状态,s,，,sS=s,1,s,2,.,s,k,，定义邻居半径,r,，元胞的左右两侧共有,2r,个元胞作为其邻居集合,N,，定义在离散时间维上的转换函数,f:S,2r+1,S,可以记为,:,为第,i,个元胞在,t,时刻的状态。称上述,A=S,N,f,三元组,(,维数,d1),为一维元胞自动机,二维元胞自动机,:,元胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以,J.H.Conway,的,“,生命游戏,”,为代表，应用最为广泛。由于，世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到二维空间上，所以，二维元胞自动机的应用最为广泛，多数应用模型都是二维元胞自动机模型。,(,3),三维元胞自动机：目前，,Bays(Bays,C,1988),等人在这方面做了若干试验性工作，包括在三维空间上实现了生命游戏，延续和扩展了一维和二维元胞自动机的理论。,(4),高维元胞自动机：只是在理论上进行少量的探讨，实际的系统模型较少。,Lee Meeker,在他的硕士论文中，进行了对四维元胞自动机的探索。,9,确定性元胞自动机解法,冷加工金属中原级再结晶模拟的确定性元胞自动机,方法,:,假定成核和新结晶晶粒生长所需驱动力均来源于局域位错密度,的,梯,度,;,并且当有碰撞时生长终止,。对于,复原和成核，元胞自动机允许,引,入,任意,的条件,。,起始数据,应包括,格栅几何参数,和,态变量取值,等信息，例如,，温度,、成核概率、晶界迁移率、位错密度和晶体取向。这些数据必须以三维基体的角度提供。也就是说，这些数据能够描述作为,空间函数的初始微结构,的,主要特征,。,为降低对计算机存储器的要求，可以指定所研究的晶粒数，并且每个元胞所储存的晶粒数只能是这个指定的数目。,9,确定性元胞自动机解法,计算机主存储器中储存的排列数组是晶粒表格,(grain list),和表面表格,(surface list),：,首先应含有,晶粒结晶取向,的信息。输入,数,据,由,晶粒数目和描述其晶粒取向的三个欧拉角组成。,其次，描述那些只拥有同一个晶粒表面的元胞。,为了进一步降低所需要的存储量，在上述表中只储存两个独立的数组，即,元胞的坐标,和,共用同一个元胞的晶粒数目,。,9,确定性元胞自动机解法,9,确定性元胞自动机解法,在简单的有限差分公式中，可以计算出,f,1,的因子，这个因子,f,与弛豫时间,r,，温度,T,和时间,t,i,有关。这时，在时间,t,i,时的位错密度就可表示为：,在更为复杂的方法中，函数,f,还将依赖于局域取向,(,也就是把普通的复原转变为与取向相关的复原。,9,确定性元胞自动机解法,在,成核阶段,，各个,元胞或元胞团簇应该由变形态转变为,再结晶状态。,对所,建立,模型的,体材料样品,，可,考虑给定,半径球的,排列情况,，以,几何学的,角度,给出,所使用,的,格栅,。,同时,，,合理规定,各种不同的,确定性或统计性,成核,临界条件,。,在,最简单的可能方法中，若不考虑特定的临界条件，可以采用变形基体中,晶核,晶粒,的,格座饱和,的,统计空间排列,。,9,确定性元胞自动机解法,9,确定性元胞自动机解法,把这些,反映晶粒取向特性,的,临界条件,，以及,产生的晶核应与基体有相似取向的规则,结合起来,，就,相当于给出一个,取向成核的假说,。,在成核阶段之后,，晶核,晶粒应添加到晶粒表中，一般假定其形状为球形。,所有,属于这个球表面,的晶胞,都要增补到表面清单,表格中。,球,内部的元胞被记作属于再结晶,的。,在,使用这些,球状晶粒,时,，必须避免格栅,几何,因素对成长晶粒,的形状产生大的,影响。,成核条件决定,了在时间,t,i,时,所产生的晶核,数,N,i,。,为,讨论问题之方便，可,适当,地补充其他成核条件,，诸如格座,饱和、固定成核速率,等。,9,确定性元胞自动机解法,在生长阶段，对于每个晶粒可执行个循环，这个循环就是遍及所有属于目标晶粒表面的元胞。,在这个循环中，可以确定,表面元胞,与其,非再结晶近邻元胞,两者结晶,取向之间的偏差,。,晶界迁移率,是这个,取向偏差,g,和,温度,T,的函数。,迁移率的数值一般可以从现成表中查得，但对于,Read-Shockley,型小角晶界和孪晶晶界，其值一致性较差，例如,3,或,9,，这时常通把迁移率设置为零。,9,确定性元胞自动机解法,在原级结晶的情况下，,局域驱动力,取决于非结晶元胞的实际位错密度,。,驱动力,和,迁移率,决定着,晶界运动的速度,，晶界速度即是指在单个时间增量内的生长置,(,以元胞直径为单位,),。,事实上，由于是在其近邻方向上进行元胞数目的计算，因而所考查的表面元胞会横向转移到周围环境当中，这一运动可以通过适用于三维环境的,Bresen-ham,算法进行处理，在这种转移运动中所遇到的所有元胞均记作再结晶的。,当再结晶元胞发生相互碰撞时，生长即刻终止。,10,元胞自动机与蒙特卡罗方法,元胞自动机经常与波茨蒙特卡罗自旋模型发生混淆，然而，在这两种方法之间确实存在着本质上的区别。,首先，元胞自动机方法对微观体系不存在内禀标度；如果选择有合适的基础单元，且能建立与场变量相匹配的代数、微分或积分方程，那么元胞自动机可以用于任意空间和时间尺度上的问题处理。但是，对于蒙特卡罗模型则不是这样的，因为它关于微观体系是有内禀标度的,;,第二点，在所有,Metropolis,和波茨蒙特卡罗方法中，广义自旋格座是用随机抽样顺序考察的，而元胞自动机则是同步一齐更新；,第三点，元胞自动机比多态波茨模型使用了更多的确定性或概率性变换规则。,表中列出了波茨型,Metropolis,蒙特卡罗和元胞自动机算法之间的主要异同点。,預測凝固時,grain structure,包含,nucleation,、,growth kinetics of a dendrite tip,、,crystallographic orientations,等物理機制,可顯示微組織隨時間演變的情形,11,元胞自动机应用实例,Nucleation,Continuous nucleation model：,two different Gaussian Distributions for,heterogeneous nucleation,both on,mold wall,and in the,bulk liquid,dn,：grain density inc