元胞自动机理论基础

数高

是元胞自动机研究中的一个特点。

在实际应用过程中，许多元胞自动机模型已经对其中的某些特征进行了扩展，例如圣托斯兰州立大学(San Tose State University)研究的所谓连续型的元胞自动机，其状态就是连续的。但正如我们在元胞自动机的概念分析中指出的，在上述恃征中，同质性、并行性、局部性是元胞自动机的核心恃证，任何对元胞自动机的扩展应当尽量保持这些核心特征，尤其是局部性特征。

Chapter4

元胞自动机的构建没有固定的数学公式，构成方式繁杂，变种很多，行为复杂。故其分类难度也较大，自元胞自动机产生以来，对于元胞自动机分类的研究就是元胞自动机的一个重要的研究课题和核心理论，在基于不同的出发点，元胞自动机可有多种分类，其中，最具影响力的当属S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类，而基于维数的元胞自动机分类也是最简单和最常用的划分。除此之外，在1990年，Howard A.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)这第四类行为可以与生命系统等复杂系统中的自组织现象相比拟，但在连续系统中没有相对应的模式。但从研究元胞自动机的角度讲，最具研究价值的具有第四类行为的元胞自动机，因为这类元胞自动机被认为具有\突现计算\功能，研究表明，可以用作广义计算机(Universal Computer)以仿真任意复杂的计算过程。另外，此类元胞自动机在发展过程中还表现出很强的不可逆(lrreversibility)特征，而且，这种元胞自动机在若干有限循环后，有可能会 \死\掉，即所有元胞的状态变为零。 S·Wolfram还近似地给出了上述四种一维元胞自动机中各类吸引子或模式所占地比见 (表1-1)，可以看出，具有一定局部结构的复杂模式出现的概率相对要小一些。而第三种混沌型则出现的概率最大，并且，其概率随着k和r的增大而呈现增大的趋势。

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

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

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

2r+1

→S可以记为:

，Si为第i个元胞在t时刻的状态。

t

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

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

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

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

Chapter5

元胞自动机与相关理论和方法的发展有着千丝万缕的联系，一方面，元胞自动机的发展得益于相关理论的研究，如逻辑数学、离散数学、计算机中的自动机理论，图灵机思想;另一方面，元胞自动机的发展也促进了一些相关学科和理论(如人工智能、非线性科学、复杂性科学)的发展，甚至还直接导致了人工生命科学的产生。另外，在表现上，元胞自动机模型还与一些理论方法存在着较大的相似性，或者相对性。下面，我们对元胞自动机的一些相关理论方法，以及它们与元胞自动机模型的关系进行简要讨论。 1.元胞自动机与人工生命研究

人工生命是90年代才刚刚诞生的新生科学，是复杂性科学研究的支柱学科之一。人工生命是研究能够展示自然界生命系统行为特征的人工系统的一间科学，它试图在计算机、机器人等人工媒体上仿真、合成和生物有机体相关联的一些基本现象，如自我复制、寄生、竞争、进化、协作等，并研究和观察\可能的生命现象\，从而使人们能够加深理解\已知的生命现象\，C·G·，1987;吴建兵，1998)。

元胞自动机是人工生命的重要研究工具和理论方法分支，兰顿(Christopher Langton)等人正是基于对元胞自动机的深入研究提出和发展了人工生命。同时，人工生命的发展又为元胞自动机赋予了新的涵义，元胞自动机模型得到科学家们的重新认识和认可，并在90年代又一次成为科学研究的前沿课题，其理论和方法得到进一步的提高。另外，元胞自动机与其他的人工生命研究方法有着很大的相似性。元胞自动机模型与神经网络、遗传算法等其他人工生命方法一样，都是基于局部的相互作用，来研究系统的整体行

为。另外，元胞自动机、神经网络、L—系统都可以归为非线性动力学中的网络动力学模型，它们相互联系，关系密切。目前，一种被称为元胞神经网络(Cellular Neural Network，简称CNN)的模型就是元胞自动机与神经网络结合的产物。 2.元胞自动机与\混沌的边缘\

\混沌的边缘 (On the Edge of Chaos)(Langton C. G.，1992;M. Waldrop，1997)\是当前复杂性科学研究的一个重要成果和标志性口号，为圣塔菲(Santa Fee)学派的旗帜。所谓的\混沌\并非科学意义上的\混沌\，而是Chaos本身的原有涵义，即与有序相对的\混乱\、\无序\的概念。因此，\混沌的边缘\应当被理解为\混乱的边缘\。或\无序的边缘\，而与混沌动力学的\混沌\没有直接联系。其实，\混沌的边缘\完整的含义是指:生命等复杂现象和复杂系统存在和产生于\混沌的边缘\。有序不是复杂，无序同样也不是复杂，复杂存在于无序的边缘。

\混沌的边缘\这个概念是Norman Packard和Chhstopher Langton在对元胞自动机深入研究的基础上提出的，在此我们予以简要介绍。

Langton在对S. Wolfram动力学行为分类的分析和研究基础上，提出\混沌的边缘\这个响亮的名词，认为元胞自动机，尤其是第四类元胞自动机是最具创造性动态系统--复杂状态，它恰恰界于秩序和混沌之间，在大多数的非线性系统中，往往存在一个相应于从系统由秩序到混沌变化的转换参数。例如，我们日常生活中的水龙头的滴水现象，随着水流速度的变化而呈现不同的稳定的一点周期、两点或多点周期乃至混沌、极度紊乱的复杂动态行为，显然，这里的水流速度。或者说水压就是这个非线性系统的状态参数。Langton则相应地定义了一个关于转换函数的参数，从而将元胞自动机的函数空间参数比。该参数变化时，元胞自动机可展现不同的动态行为，得到与连续动力学系统中相图相类似的参数空间，Langton的方法加下 (谭跃进，1996):

首先定义元胞的静态(Quiescent State)。元胞的静态具有这样的特征，如果元胞所有领域都处于静态。则该元胞在下一时刻将仍处于这种静态(类似于映射中的不动点)。现考虑一元胞自动机，每个元胞具有k种状态(状态集为Σ)，每个元胞与n个相邻元胞相连。则共存在kn种邻域状态。选择k种状态中任意一种s∈Σ并称之为静态sq。假设对转换函数而言，共有nq种变换将邻域映射为该静态，剩下的kn-nq种状态被随机地、均匀地映射为Σ-{sq} 中的每一个状态。则可定义:

这样，对任意一个转换函数。定义了一个对应的参数值λ。随着参数λ由0到1地变化，元胞自动机的行为可从点状态吸引子变化到周期吸引子，并通过第四类复杂模式达到混沌吸引子 因此，第四类具有局部结构的复杂模式处于。秩序\与\混沌\之间，被称之为\混沌的边缘\，在上述的参数空间中。元胞自动机的动态行为(定性1具有点吸引于十周期吸引子->\复杂模式\混沌吸引子这样的演化模式。同时，它又给元胞自动机的动力学行为的分类赋予了新的意义:即λ低于一定值(这里约为0.6)，那么系统将过于简单。换句话说，太多的有序而使得系统缺乏创造性;另外一个极端情况，λ接近1时。系统变的过于紊乱，无法找出结构特征;那么，λ只有在某个值附近，所谓\混沌的边缘\，系统使得极为复杂。也只有在此时，\生命现象\才可能存在。在这个基础上，兰顿提出和发展了人工生命科学。在现代系统科学中。耗散结构学指出\生命\以负墒为生，而Langton则创造性的提出生命存在于\混沌的边缘\。从另外一个角度对生命的复杂现象进行了更深层次 探讨的。

3.元胞自动机与微分方程

微分方程有着三百多年的发展历史。一批伟大的科学家，如Euler、Caus。Langrange、Laplace、Poisson都作出了卓越的贡献。而且，后来发展的偏微分万程对量子力学等现代物理学的产生相发展有着