元胞自动机理论基础 4——元胞自动机的构建

森之张卫东

Chapter4

元胞自动机的构建没有固定的数学公式，构成方式繁杂，变种很多，行为复杂。故其分类难度也较大，自元胞自动机产生以来，对于元胞自动机分类的研究就是元胞自动机的一个重要的研究课题和核心理论，在基于不同的出发点，元胞自动机可有多种分类，其中，最具影响力的当属S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类，而基于维数的元胞自动机分类也是最简单和最常用的划分。

除此之外，在1990年，HowardA.Gutowitz提出了基于元胞自动机行为的马尔科夫概率量测的层次化、参量化的分类体系(Gutowitz, H. A.,1990)。下面就上述的前两种分类作进一步的介绍。同时就几种特殊类型的元胞自动机进行介绍和探讨S. Wolfrarm在详细分忻研究了一维元胞自动机的演化行为，并在大量的计算机实验的基础上，将所有元胞自动机的动力学行为归纳为四大类(Wolfram. S.，1986):

(1)平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。

(2)周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Perlodical Patterns)。由于这些结构可看作是一种滤波器(Filter)，故可应用到图像处理的研究中。

(3)混沌型:自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统汁特征不再变止，通常表现为分形分维特征。

(4)复杂型:出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。从另一角度，元胞自动机可视为动力系统，因而可将初试点、轨道、不动点、周期轨和终极轨等一系列概念用到元胞自动机的研究中，上述分类，又可以分别描述为(谭跃进，1996；谢惠民，1994；李才伟、1997)；

(1)均匀状态，即点态吸引子，或称不动点;

(2)简单的周期结构，即周期性吸引子，或称周期轨;

(3)混沌的非周期性模式，即混沌吸引子;

(4)这第四类行为可以与生命系统等复杂系统中的自组织现象相比拟，但在连续系统中没有相对应的模式。

但从研究元胞自动机的角度讲，最具研究价值的具有第四类行为的元胞自动机，因为这类元胞自动机被认为具有"突现计算"(Emergent Computation)功能，研究表明，可以用作广义计算机(Universal Computer)以仿真任意复杂的计算过程。另外，此类元胞自动机在发展过程中还表现出很强的不可逆(lrreversibility)特征，而且，这种元胞自动机在若干有限循环后，有可能会 "死"掉，即所有元胞的状态变为零。

S·Wolfram还近似地给出了上述四种一维元胞自动机中各类吸引子或模式所占地比见 (表1-1)，可以看出，具有一定局部结构的复杂模式出现的概率相对要小一些。而第三种混沌型则出现的概率最大，并且，其概率随着k和r的增大而呈现增大的趋势。

这种分类不是严格的数学分类，但S·Wolfram将众多(也许所有)的元胞自动机的动力学行为归纳为数量如此之少的四类，是非常有意义的发现，对于元胞自动机的研究具有很大的指导意义。它反映出这种分类方法可能具有某种普适性，很可能有许多物理系统或生命系统可以按这样的分类方法来研究，尽管在细节上可以不同，但每一类中的行为在定性上是相同的 (谢惠民，1994)。

理论上，元胞自动机可以是任意维数的。那么，按元胞空间的维数分类，元胞自动机通常可以分为:

(l)一维元胞自动机:元胞按等间隔方式分布在一条向两侧无限延伸的直线上，每个元胞 (Cell)具有有限个状态s，s∈S={s1,s2,...,sk}，定义邻居半径r，元胞的左右两侧共有2r个元胞作为其邻居集合N，定义在离散时间维上的转换函数f:S2r+1→S可以记为:

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

Sti为第i个元胞在t时刻的状态。称上述A={S,N,f}三元组(维数d≡1)为一维元胞自动机(Amoroso，S，1972;李才伟，l997)。
对一维元胞自动机的系统研究最早，相对来讲，其状态、规则等较为简单，往往其所有可能的规则可以一一列出，易于处理，研究也最为深入。目前，对于元胞自动机的理论研究多集中在一维元胞自动机上。S.Wolfram对元胞自动机的动力学分类也是基于对一维初等元胞自动机(ElementaryCellular Automata)的分析研究得出的。它的最大的一个特征在于容易实现元胞自动机动态演化的可视化:二维显示中，一维显示其空间构形，空间维;另外一维显示其发展演化过程，时间维。

(2)二维元胞自动机:元胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以J. H.Conway的"生命游戏"为代表，应用最为广泛。由于，世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到二维空间上，所以，二维元胞自动机的应用最为广泛，多数应用模型都是二维元胞自动机模型。

(3)三维元胞自动机：目前，Bays(Bays,C,1988)等人在这方面做了若干试验性工作，包括在三维空间上实现了生命游戏，延续和扩展了一维和二维元胞自动机的理论。

(4)高维元胞自动机：只是在理论上进行少量的探讨，实际的系统模型较少。LeeMeeker在他的硕士论文中，进行了对四维元胞自动机的探索。