发布时间 : 星期四 文章元胞自动机理论基础更新完毕开始阅读
其中当xi=yi时δ(xi,yi)=0，当xi≠yi时δ(xi,yi)=1。然后。在S中可以建立起开、闭、紧等拓扑概念。
在S中定义移位算子δ为δ(xi)=xi-1，i∈Z。若连续映射F:S->S产与δ可交换，即Fδ=δF。或对任意的x∈S有F((δ(x))=δ(F(x))，则称F为元胞自动机 (谢惠民，1994)。
对于以上定义，我们很容易将它扩展到一个任意维空间，所要做的工作只是将S记为S，S为S
(2r+1)^d
Z
Z^d
2r+1
ZZ
Z
ZZ
记
等，同时对一些描述作相应改变即可。
元胞自动机的构成
元胞自动机最基本的组成元胞、元胞空间、邻居及规则四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。
1.元胞
元胞又可称为单元。或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。 2.状态
状态可以是{0,1}的二进制形式。或是{s0,s2,??si??sk}整数形式的离散集，严格意义上。元胞自动机的元胞只能有一个犬态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。李才伟(1997)在其博士论文工作中，就设计实现了这样一种称之为\多元随机元胞自动机\模型。并且定义了元胞空间的邻居(Neighbor)关系。由于邻居关系，每个元胞有有限个元胞作为它的邻居; 3.元胞空间(Lattice)
元胞所分布在的空间网点集合就是这里的元胞空间。
(l)元胞空间的几何划分:理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元抱自动机。元胞空间的划分只有一种。而高维的元胞自动机。元胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机。二维元胞空间通常可按三角、四万或六边形三种网格排列 (图2-5)。
这三种规则的元胞空间划分在构模时各有优缺点:
三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有用;其缺点是在计算机的表达与显示不方便，需要转换为四方网格。
四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表达显示;其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。
六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型;其缺点同三角网格一样，在表达显示上较为困难、复杂。
(2)边界条件:在理论上，元胞空间通常是在各维向上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要定义不同的边界条件。归纳起来，边界条件主要有三种类型:周期型、反射型和定值型。有时，在应用中，为更加客观、自然地模拟实际现象，还有可能采用随机型，即在边界实时产生随机值。
周期型(Pehodic Boundary)是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的\圈\。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面 (Torus)，形似车胎或甜点圈。周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间型作为试验。
反射型(Reflective Boundary)指在边界外邻居的元胞状态是以边界为轴的镜面反射。例如在一维空间中，当r=1时的边界情形:
定值型 (Constant Boundary)指所有边界外元胞均取某一固定常量，如0，1等。
需要指出的是，这三种边界类型在实际应用中，尤其是二维或更高维数的构模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型 (相对边界中。不能一方单方面采用周期型)。
(3)构形:在这个元胞、状态、元胞空间的概念基础上，我们引入另外一个非常重要的概念，构形(Configuration)。构形是在某个时刻，在元胞空间上所有元胞状态的空间分布组合。通常。在数学上，它可以表示为一个多维的整数矩阵。 4.邻居 (Neighbor)
以上的元胞及元胞空间只表示了系统的静态成分，为将\动态\引入系统，必须加入演化规则。在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞，内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式(我们以最常用的规则四方网格划分为例)。
见图2-6，黑色
元胞为中心元胞，灰色元胞为其邻居，它们的状态一起来计算中心元胞在下一时刻的状态。
l)冯-诺依曼(Von. Neumann)型
一个元胞的上、下、左、有相邻四个元胞为该元胞的邻居。这里，邻居半径r为1，相当于图像处理中的四邻域、四方向。其邻居定义如下:
vixviy表示邻居元胞的行列坐标值，vox表示中心元胞的行列坐标值。此时，对于四方网格，在维数为d时，一个元胞的邻居个数为2d。
2)摩尔(Moore)型
一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该元胞的邻居。邻居半径r同样为1，相当于图像处理中的八邻域、八方向。其邻居定义如下:
vixviyvox意义同前。此时，对于四方网格，在维数为d时。一个元胞的邻居个数为 (3-1)。 3)扩展的摩尔(Moore)型
将以上的邻居半径r扩展为2或者更大，即得到所谓扩展的摩尔型邻居。其数学定义可以表示为:
d
此时，对于四方网格，在维数为d时，一个元胞的邻居个数为 ((2r十1)-1)。 4)马哥勒斯 (Margolus)型
这是一种同以上邻居模型迥然不同的邻居类型，它是每次将一个2x2的元胞块做统一处理，而上述前三种邻居模型中，每个元胞是分别处理的。这种元胞自动机邻居是由于格子气的成功应用而受到人们关注的，关于这种邻居模型的详细介绍，请参照本文对格子气动机的介绍。 5.规则(Rule)
根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。我们将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数 (史忠植，1998)。这个函数构造了一种简单的、离散的空间/时间的局部物理成分。要修改的范围里采用这个局部物理成分对其结构的\元胞\重复修改。这样，尽管物理结构的本身每次都不发展。但是状态在变化(史
d
忠植，1998)。它可以记为f: si=f(si,sN)，sN为t时刻的邻居状态组合，我们称f为元胞自动机的局部映
射或局部规则 (谢惠民，1994)。 6.时间 (Time)
元胞自动机是一个动态系统，它在时间维上的变化是离散的，即时间f是一个整数值，而且连续等间距。假设时间间距dt=1，若t=O为初始时刻。那么。t=1为其下一时刻。在上述转换函数中，一个元胞在t十1的时刻只(直接)决定于t时刻的该元胞及其邻居元胞的状态，虽然，在t-1时刻的元胞及其邻居元胞的状态间接(时间上的滞后)影响了元胞在t+1的时刻的状态。
由以上对元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的概念。用数学符号来表示，标准的元胞自动机是一个四元组 (Amoroso，S.，1972): A=(Ld,S,N,f)
这里A代表一个元胞自动机系统；L表示元胞空间，d是一正整数，表示元胞自动机内元胞空间的维数;S是元胞的有限的、离散的状态集合;N表示一个所有邻域内元胞的组合(包括中心元胞)，即包含n个不同元胞状态的一个空间矢量，记为: N=(s1,s2,...,sn)
n是元胞的邻居个数。si∈Z(整数集合)，i∈{1，...,n}；f表示将S映射到S上的一个局部转换函数。所有的元胞位于d维空间上，其位置可用一个d元的整数矩阵Z来确定。
元胞自动机的一般特征
从元胞自动机的构成及其规则上分析，标准的元胞自动机应具有以下几个特征（谢惠民，1994；李才伟，1997)：
(1)同质性、齐性，同质性反映在元胞空间内的每个元胞的变化都服从相同的规律，即元胞自动机的规则，或称为转换函数;而齐性指的是元胞的分布方式相同，大小、形状相同，空间分布规则整齐; (2)空间离散:元胞分布在按照一定规则划分的离散的元胞空间上;
(3)时间离散:系统的演化是按照等间隔时间分步进行的，时间变量t只能取等步长的时刻点，形似整数形式的t0,t十l,t十2?，而且，t时刻的状态构形只对其下一时刻，即t+1时刻的状态构形产生影响，而t+2时刻的状态构形完全决定于t+1的状态构形及定义在上面的砖换函数。元胞自动机的时间变量区别于微分方程中的时间变量t,那里t通常是个连续值变量；
(4)状态离散有限:元胞自动器的状态只能取有限(k)个离散值(s1,s2,...,sk)。相对于连续状态的动力系统，它不需要经过粗粒化处理就能转化为符号序列。而在实际应用中，往往需要将有些连续变量进行离散化，如分类，分级，以便于建立元胞自动机模型;
(5)同步计算(并行性):各个元胞的在时刻ti+1的状态变化是独立的行为，相互没有任何影响。若将元胞自动机的构形变化看成是对数据或信息的计算或处理，则元胞自动机的处理是同步进行的，特别适合于并行计算;
(6)时空局部性:每一个元胞的下一时刻ti+1的状态，取决于其周围半径为r的邻域(或者其它形式邻居规则定义下的邻域)中的元胞的当前时刻ti的状态，即所谓时间、空间的局部性。从信息传输的角度来看，元胞自动机中信息的传递速度是有限的;
(7)维数高:在动力系统中一般将变量的个数成为维数。例如，将区间映射生成的动力系统称为一维动力系统;将平面映射生成的动力系统称为二维动力系统;对于偏微分方程描述的动力系统则称为无穷维动力系统。从这个角度来看，由于任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集，每个元胞的状态便是这个动力学系统的变量。因此，元胞自动机是一类无穷维动力系统。在具体应用中或计算机模拟时当然不可能处理无限个变量，但一股也总是处理数量很大的元胞组成的系统。因此可以说维
d
n
t+1ttt