元胞自动机与"混沌的边缘“元胞自动机与人工生命研究

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} 中的每一个状态。则可定义:

    这样，对任意一个转换函数。定义了一个对应的参数值λ。随着参数λ由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)模型是对凝聚扩散模型的改进和发展。其基本思想是:在给定的离散空间中，依照一定的密度随机散布自由粒子，在中心设置一个凝聚点作为种子点，也可以随机布设若干个凝聚点作为种子，然后各自由粒子随机行走，一旦与凝聚点相邻，则变为新的凝聚点，直至所有的自由粒子"凝聚"。