元胞自动机.doc

元胞自动机
   元胞自动机(Cellular Automata,简称CA,也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网(Lattice Grid)中的每一元胞(Cell)取有限的离散状态,遵循同样的作用规则,依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型,元胞自动机不是由严格定义的物理方程或函数确定,而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此,元胞自动机是一类模型的总称,或者说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个状态,且其状态改变的规则在时间和空间上都是局部的。
    元胞自动机的构建没有固定的数学公式,构成方式繁杂,变种很多,行为复杂。故其分类难度也较大,自元胞自动机产生以来,对于元胞自动机分类的研究就是元胞自动机的一个重要的研究课题和核心理论,在基于不同的出发点,元胞自动机可有多种分类,其中,最具影响力的当属S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类,而基于维数的元胞自动机分类也是最简单和最常用的划分。除此之外,在1990年,Howard 、参量化的分类体系(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)这第四类行为可以与生命系统等复杂系统中的自组织现象相比拟,但在连续系统中没有相对应的模式。但从研究元胞自动机的角度讲,最具研究价值的具有第四类行为的元胞自动机,因为这类元胞自动机被认为具有"突现计算"(putation)功能,研究表明,可以用作广义计算机(puter)以仿真任意复杂的计算过程。另外,此类元胞自动机在发展过程中还表