元胞自动机的构成

森之张卫东

元胞自动机的构成

元胞自动机最基本的组成：元胞、元胞空间、邻居及规则四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。

1.元胞

元胞又可称为单元或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。

2.状态

状态可以是{0,1}的二进制形式。或是{s0,s2,……si……sk}整数形式的离散集。严格意义上，元胞自动机的元胞只能有一个状态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。李才伟(1997)在其博士论文工作中，就设计实现了这样一种称之为"多元随机元胞自动机"模型。并且定义了元胞空间的邻居(Neighbor)关系。由于邻居关系，每个元胞有有限个元胞作为它的邻居;

3.元胞空间(Lattice)

元胞所分布在的空间网点集合就是这里的元胞空间。

(l)元胞空间的几何划分:理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元抱自动机。元胞空间的划分只有一种。而高维的元胞自动机。元胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机。二维元胞空间通常可按三角、四万或六边形三种网格排列 (图2-5)。

file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image003.jpg

这三种规则的元胞空间划分在构模时各有优缺点:

三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有用;其缺点是在计算机的表达与显示不方便，需要转换为四方网格。

四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表达显示;其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。

六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型;其缺点同三角网格一样，在表达显示上较为困难、复杂。

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

周期型(Pehodic Boundary)是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的"圈"。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面 (Torus)，形似车胎或甜点圈。周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间型作为试验。

反射型(Reflective Boundary)指在边界外邻居的元胞状态是以边界为轴的镜面反射。例如在一维空间中，当r=1时的边界情形:

file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image004.jpg

定值型 (Constant Boundary)指所有边界外元胞均取某一固定常量，如0，1等。

需要指出的是，这三种边界类型在实际应用中，尤其是二维或更高维数的构模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型 (相对边界中。不能一方单方面采用周期型)。

(3)构形:在这个元胞、状态、元胞空间的概念基础上，我们引入另外一个非常重要的概念，构形(Configuration)。构形是在某个时刻，在元胞空间上所有元胞状态的空间分布组合。通常。在数学上，它可以表示为一个多维的整数矩阵。

4.邻居 (Neighbor)

以上的元胞及元胞空间只表示了系统的静态成分，为将"动态"引入系统，必须加入演化规则。在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常以下几有种形式(我们以最常用的规则四方网格划分为例)。见图2-6，黑色元胞为中心元胞，灰色元胞为其邻居，它们的状态一起来计算中心元胞在下一时刻的状态。file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image006.jpg

l)冯-诺依曼(Von. Neumann)型

一个元胞的上、下、左、右有相邻四个元胞为该元胞的邻居。这里，邻居半径r为1，相当于图像处理中的四邻域、四方向。其邻居定义如下:
file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image007.pngvixviy表示邻居元胞的行列坐标值，vox表示中心元胞的行列坐标值。此时，对于四方网格，在维数为d时，一个元胞的邻居个数为2d。

2)摩尔(Moore)型

一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该元胞的邻居。邻居半径r同样为1，相当于图像处理中的八邻域、八方向。其邻居定义如下:
file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image008.png
vixviyvox意义同前。此时，对于四方网格，在维数为d时。一个元胞的邻居个数为 (3d-1)。

3)扩展的摩尔(Moore)型

将以上的邻居半径r扩展为2或者更大，即得到所谓扩展的摩尔型邻居。其数学定义可以表示为:
file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image009.png
此时，对于四方网格，在维数为d时，一个元胞的邻居个数为((2r十1)d-1)。

4)马哥勒斯 (Margolus)型

这是一种同以上邻居模型迥然不同的邻居类型，它是每次将一个2x2的元胞块做统一处理，而上述前三种邻居模型中，每个元胞是分别处理的。这种元胞自动机邻居是由于格子气的成功应用而受到人们关注的，关于这种邻居模型的详细介绍，请参照本文对格子气动机的介绍。

5.规则(Rule)

根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。我们将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数 (史忠植，1998)。这个函数构造了一种简单的、离散的空间/时间的局部物理成分。要修改的范围里采用这个局部物理成分对其结构的"元胞"重复修改。这样，尽管物理结构的本身每次都不发展。但是状态在变化(史忠植，1998)。它可以记为f: sit+1=f(sit,sNt)，sNt为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表示将Sn映射到S上的一个局部转换函数。所有的元胞位于d维空间上，其位置可用一个d元的整数矩阵Zd来确定。

详细内容见附件：