元胞自动机理论基础 5——元胞自动机与相关理论和方法

森之张卫东

Chapter5

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

1.元胞自动机与人工生命研究

人工生命是90年代才刚刚诞生的新生科学，是复杂性科学研究的支柱学科之一。人工生命是研究能够展示自然界生命系统行为特征的人工系统的一间科学，它试图在计算机、机器人等人工媒体上仿真、合成和生物有机体相关联的一些基本现象，如自我复制、寄生、竞争、进化、协作等，并研究和观察"可能的生命现象"(Life-as-it-could-be)，从而使人们能够加深理解"已知的生命现象"(Life-as-we-know-it)(Longton，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} 中的每一个状态。则可定义:

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

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

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

微分方程有着三百多年的发展历史。一批伟大的科学家，如Euler、Caus。Langrange、Laplace、Poisson都作出了卓越的贡献。而且，后来发展的偏微分万程对量子力学等现代物理学的产生相发展有着重要的意义，一大批的物理规律就是利用偏微分方程来惟理和表达的，如麦克斯维方程等。恩格斯还指出“自然界的统一性，显示在关于各种现象领域的微分方程的 '惊人类似'之中"。总之，微分方程是现代科学的语言，也是科学研究中最为重要的研究工具之一。
微分方程的主要特点是时间、空间均连续(如果方程中有空间因子的话），这是建立在时空连续的哲学认识基础上的。而元胞自动机则是完全的空间离散、时间离散，在这个意义上，微分方程和元胞自动机一对相对的计算方法 (Toffoli.T.，1987)。
在人工计算的情况下。由符号组成的(偏)微分方程可以灵活地进行约简等符号运算，而得到精确的定量解。这是其优势。但在现代计算机日益发展，已成为我们科学研究的重要工具时，微分方程却遇到了一个尴尬的问题。即计算机是建立在离散的基础上的，微分方程在计算时不得不对自身进行时空离散化，建立差分方程等;或者展开成幂系列方程，截取部分展开式;或者采用某种转换用离散结构来表示连续变量。这个改造过程不仅是繁杂的，甚至是不可能解决的，但最重要的是在这个过程中，微分方程也失去了它的自身最重要的特性----精确性、连续性。

而对于元胞自动机来讲，脱离计算机环境来进行运算几乎是不可能的，但是借助计算机进行计算，则非常自然而合理，甚至它还是下一代并行计算机的原型。因此，在现代计算机的计算环境下，以元胞自动机为代表的离散计算方式在求解方面，尤其是动态系统模拟方面有着更大的优势。元胞自动机虽然在理论上具备计算的完备性，但满足特定目的构模尚无完备的理论支持，其构造往往是一个直觉过程。用元胞自动机得到一个定量的结果非常困难，即便是可能的话，元胞自动机也将陷入一个尴尬，元胞自动机的状态、规则等构成必然会复杂化，从而不可避免地失去其简单、生动的特性。

然而，证如物理学家玻尔所说，"相对的并不一定是矛盾的，有可能是相互补充和相互完善的"。二者互有优缺点，相互补充，都有其存在的理由。但在现代计算机环境下，对于元胞自动机这一类相对来讲还处于幼年阶段的离散计算方式，需要予以更多的关注和支持。在地理学中，Lowry、Wilson、张新生(张新生，1997)等人的空间动力学模型都是基于微分方程的模型，由于这些模型大多是复杂的非线性微分方程，无法求得其解析解，需要按Euler方法或Runge-Kutta方法对微分方程进行一步或多步差分，完成相应的计算机模型或在GIS支持下的空间分析模型。对于这些模型，我们都可以构建相应的元胞自动机模型。

4.元胞自动机与分形分维

元胞自动机与分形分维理论有着密切的联系。元胞自动机的自复制、混沌等特征，往往导致元胞自动机模型在空间构形上表现出自相似的分形特征，即元胞自动机的模拟结果通常可以用分形理论来进行定量的描述。同时，在分形分维的经典范例中，有些模型本身就是，或者很接近元胞自动机模型，例如下面我们提到的凝聚扩散模型，因此，某些元胞自动机模型本身就是分形动力学模型。但是，究其本质，元胞自动机与分形理论有着巨大的差别。

元胞自动机重在对想象机理的模拟与分析;分形分维重在对现象的表现形式的表达研究。元胞自动机建模时，从现象的规律入手，构建具有特定涵义的元胞自动机模型;而分形分维多是从物理或数学规律、规则构建模型，而后应用于某种特定复杂现象，其应用方式多为描述现象的自相似性和分形分维特征。然而，这些分数分维究竟能够给我们提供多少更有价值的信息?分形理论的进一步应用问题尚末得到解决 (仪垂祥，1995)。
此外，两者都强调一个从局部到整体的过程，但在这个过程的实质上，二者却存在巨大的差异。分形论的精髓是自相似性。这种自相似性不局限于几何形态而具有更广泛更深刻的含义;它是局部(部分)与整体在形态、功能、信息和结构特性等方面而具有统计意义上的相似性。因此，分形理论提供给我们分析问题的方法论就是从局部结构推断整体特征(陈述彭，1998)。相反，元胞自动机的精华在于局部的简单结构在一定的局部规则作用下，所产生的整体上的"突现"性复杂行为;即系统(整体)在宏观层次上，其部分或部分的加和所不具有的性质(谭跃进等，1996)。因此，分形理论强调局部与整体的相似性和相关性，但元胞自动机重在表现"突现"特征，即局部行为结构与整体行为的不确定性、非线性关系。

5.元胞自动机与马尔科夫(链)过程

马尔科夫过程(MarKov Process)是一个典型的随机过程。设X(t)是一随机过程，当过程在时刻t0所处的状态为已知时，时刻t(t>t0)所处的状态与过程在t0时刻之前的状态无关，这个特性成为无后效性。无后效的随机过程称为马尔科夫过程。马尔科夫过程中的时同和状态既可以是连续的，又可以是离散的。我们称时间离散、状态离散的马尔科夫过程为马尔科夫链。马尔科夫链中，各个时刻的状态的转变由一个状态转移的概率矩阵控制。

马尔科夫链与元胞自动机都是时间离散、状态离散的动力学模型，二者在概念上有一定的相通性。尤其是对于随机型的元胞自动机来讲，每个元胞的行为可以视为一个不仅时间上无后效，而且在空间上无外效的马尔科夫链。

但是，即使是随机型的元胞自动机也与马尔科夫链存在相当大的差别。首先,马尔科夫链没有空间概念，只有一个状态变量;而元胞自动机的状态量则是与空间位置概念紧密相关的;其次，马尔科夫链中的状态转移概率往往是预先设定好的，而随机型元胞自动机中的元胞状态转移概率则是由当前元胞的邻居构型所决定的。

6.元胞自动机、随机行走模型和凝聚扩散模型

随机行走模型(Random Walk Model)模拟的是统计数学中提供"最可能状态"常用的数学模型。它的基本思想为:给定空间中的一个粒子:它在空间中的移动矢量 (包括方向和距离)是由跃迁概率的随机量所控制，由此可以模拟诸如自然界中的分子布朗运动、电子在金属中的随机运动等复杂过程。其理论研究主要集中在对单个粒子的运动规律的研究。但是，随机行走模型中粒子可以是很多个，但是它们遵循的规则都是一个统一的随机规程，而且它们之间的运动是相互独立的，互不影响。如果考虑它们之间的相互作用，就可能构造出其他基于随机行走的模型，例如凝聚扩散模型。

凝聚扩散(Diffusion-Limited Aggregation)模型，简称DLA，可以看作是一个多粒子的随机行走模型，而且它的计算空间也往往是一个离散的格网。它是由A·Written和Sander于1981年首先提出的。其基本思想如下:给定初始点作为凝聚点，以它作为圆心做一个大圆，在圆周上的一个随机点释放一个粒子，为简单起见，它的运动通常规定为一个随机行走过程，直到它运动至与已有的凝聚点相邻，改变它的状态为凝聚点，不再运动;再随机释放一个粒子;直至凝聚。重复上述过程，就可以得到一个凝聚点的连通集，形似冬日里玻璃上的冰花。凝聚扩散模型还可以有不同的形式，如释放点可以在一个四边形中的顶部，从而在下面省长出形似荆棘的灌丛。而1984年，R·F·Voss提出的多粒子凝聚扩散(Multi-Particle Diffusion Aggregation)模型是对凝聚扩散模型的改进和发展。其基本思想是:在给定的离散空间中，依照一定的密度随机散布自由粒子，在中心设置一个凝聚点作为种子点，也可以随机布设若干个凝聚点作为种子，然后各自由粒子随机行走，一旦与凝聚点相邻，则变为新的凝聚点，直至所有的自由粒子"凝聚"。

元胞自动机、随机行走模型、凝聚扩散模型都是典型的分形图形的生成方法，在很多情况下，它们都可以生成相似的复杂图案。但它们之间仍存在着一定的差别。

随机行走模型与元胞自动自动机的差别在于以下几个方面:第一、随机行走模型通常只是考虑单个粒子的运动，而元胞自动机模型中则通常存在众多的元胞;第二、即使模型中，存在多个粒子，随机行走模型通常并不考虑粒子间的相互作用，粒子的运动是相互独立的;第三、随机行走中的粒子是运动的概念，而元胞自动机的元胞通常是一个状态变化的过程;第四、随机行走中的粒子的运动空间可以是离散的，也可以是连续的，但在元胞自动机中，元胞都分布在离散的空间网格上。

凝聚扩散模型。尤其是多粒子凝聚扩散模型与元胞自动机则非常相似:时间空间离散;模型中存在粒子的相互作用，且这种作用具有局部特征，即自由粒子在有凝聚点为邻居时，状态转变为凝聚点。特殊的是这种转变只是一个单向的转变，凝聚扩散模型在最终达到一种定态吸引子;粒子的运动遵循相通的规律，可以进行同步计算。因此。在广义上，凝聚扩散模型可以归为元胞自动机的一个特例。但是，它们之间仍存在以下几个不同点:一、元胞自动机模型面向的是整个网格空间，而凝聚扩散模型面向的是特定粒子的运动;二、元胞自动机的元胞通常只有状态的改变，其空间位置是固定的，而凝聚扩散模型中的粒子不仅有状态的变化，更是一个运动的粒子。三、凝聚扩散中，多个粒子通常可以同时占据一个格网空间点，而元胞自动机模型中，每个格网点只能有一个元胞。因此，在某种意义上讲，凝聚扩散模型与下面提到的多主体模型更相似，可以看作是粒子间不存在目的性、竞争、协作等智能特征的"无头脑"的主体模型。

7.元胞自动机与多主体系统

多主体系统(Multi-Agent System，简称MAS)是分布式人工智能的热点课题 (史忠植.1998)，主要研究为了共同的、或各自的不同目标，自主的智能主体之间智能行为的协作、竞争等相互作用。基于主体的模型(Agent Based Model，简记为ABM)，简称主体模型，又称基于实体的模型(Entity Based Model，简记为EBM)，或基于个体的模型(lndividual Based Model，简记为IBM)，是多主体系统的一个子集，其主要特征是每个主体代表了现实世界中一个智能性、自治的实体或个体，如人群中的个人，生态系统中的植物个体、动物个体，交通流中的汽车，计算网络中的计算机，经济系统中的经营者等。而在多主体系统中，组成系统的个体可以是任何系统部件，如组成专家系统的是一条条意见。

一些基于主体的模型中的主体是具有空间概念的，交通流中的汽车，生态系统中的动植物个体等;但有些并不具有空间概念，如计算网络中的计算机。对于那些有空间概念的主体，其空间表示即可以是连续的，如一组实数坐标对;也可以是离散的，即格网空间中的行列值。而元胞自动机与这种具有离散空间概念的主体模型非常相近，二者均研究在离散空间上个体间的相互作用而形成整体上的复杂行为。但仍然存在很大的区别;

(l)主体模型中的主体可能是可以移动的，如动物个体;但也有可能是不可以移动的;而元胞自动机模型中的元胞个体通常是不可以移动的，元胞自动机在整体上的运动是通过元胞个体的状态变化来实现的。

(2)在基于网格空间的主体模型中，格网只是作为主体的空间定位，多个主体可以占据一个格网点;而在元胞自动机模型中，每个格网点只能拥有一个特定状态的元胞。

(3)在本质上讲，可以说，主体模型是面向(通常是稀疏，分布在网格空间上的个体的)，而元胞自动机则是面向整个网格空间的。在模型运行时，主体模型将只考虑个体的行为，而元胞自动机将考虑整个元胞空间上的每个格网 (元胞)的状态。
8.元胞自动机与系统动态学模型
系统动力学 (SystemDynamics，简称SD)是一间分析研究反馈系统的学科，也是一门认识系统问题和解决系统问题交叉的综合性学科。它最初由美国麻省理工学院的Jay W·Forrestr教授于1956年开发提出，其特点是引入了系统分析的概念，强调信息反馈控制，是系统论、信息论、控制论和决策论的综合产物，非常适于研究复杂系统的结构、功能与动态行为之间的关系。通过分析系统结构，选取适当因素，建立它们之间的反馈关系，并在此基础上建立一系列微分方程，构建系统动态学方程，进一步考察系统在不同参数和不同策略因素输入时的系统动态变化行为和趋势，为决策者提供决策支持。由于它能够对实际系统进行动态仿真，因而系统动力学模型可作为实际系统，特别是社会、经济、生态复杂大系统的"实验室"(Forrester。J·W·，1969;裴相斌，1999;李一智等，1987)。
系统动态学模型在地球科学研究中具有比较广泛的实用性。因为它着眼于系统的整体最佳目标，不是单纯追求个别子系统的最佳目标，有助于实现人口、资源、环境与社会、经济各子系统之间的协调，采用无量纲的综合研究。同时，该模型仍采用的一阶微分方程组，带有延迟函数和表函数，又能引入投入——产出反馈回路的概念，能比较直观、形象地处理某些比较复杂的非线性问题 (陈述彭，1991)。但是，系统动态学也有"先天不足"，而限制了它在地球科学中的应用。
(1)首先，SD对系统的描述带有主观性。建模者对系统结构的认识，主要包括因素的选取及其相关关系的描述，就直接反映在模型中。而复杂系统的不确定性、非线性等复杂性特征决定了它的系统结构具有混沌性，不同人对它的描述可能有很大的差别，因而，系统动态学在地学建模中，难免会受到个人主观性的干扰，而影响模型的模拟结果。

(2)其次，SD缺乏全面的协调指标体系。复杂系统中有许多因素是定性的，需要一个量化的过程。那么，多个相关因子的分类、分级定量标准就需要从系统的高度进行协调，这往往是系统动态学模型的一个难题。

(3)最后，缺乏空间因素的处理功能，难以刻画空间系统中各要素在空间上的相互作用和相互反馈关系(张新生，1997;裴相斌，1999)。这对其应用于空间复杂系统研究是个致命的限制。

系统动态学模型与元胞自动机都是采用"自下而上"的研究思路，利用系统要素间的反馈等相互作用，来模拟和预测系统的整体的动态行为，它们都是研究复杂系统动态变化约有力工具。但是，二者又有所不同:首先，在模型机制上，CA模型基于系统要素间的空间相互作用，而SD则更多的考虑要素间指标属性的关联关系;其次，在模型表现形式上，CA是时间、空间、状态全离散的，转换规则也往往表现为参照表形式，而SD则表现为系列的微分方程组，时间、属性及要素间反馈关系的表达都是连续性质的i第三，在结果表现上，CA模型表现为系统空间结构的时空动态演化，而SD模型的结果是系统某个社会经济指标的动态变化;最后，在应用上，CA模型多用于复杂系统的时空演化模拟，而SD模型缺乏空间概念，更适于社会经济系统的模拟预测。

peter凯

理论挺深的得得得

peter凯

很不错呀呀呀呀呀呀

小琳琳xiao

啦啦啦 谢谢楼主