《元胞自动机理论基础》由会员分享，可在线阅读，更多相关《元胞自动机理论基础（22页珍藏版）》请在金锄头文库上搜索。
1、元胞自动机理论基础元胞自动机理论基础Chapter1Chapter1元胞自动机(Cellular Automata，简称 CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一
2、个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。1.1. 自动机自动机自动机(Automaton)通常指不需要人们逐步进行操作指导的设备(夏培肃，1984)。例如，全自动洗衣机可按照预先安排好的操作步骤作自动地运行;现代计算机能自动地响应人工编制的各种编码指令。完成各种复杂的分析与计算;机器人则将自动控制系统和人工智能结合，实现类人的一系列活动。另一方面，自动机也可被看作为一种离散数字动态系统的数学模型。例如，英国数学家 A.M.Turing 于 1936 年提出的图灵机就是一个描述计算过程的数学模型(TuringA M.，19
3、36)。它是由一个有限控制器、一条无限长存储带和一个读写头构成的抽象的机器，并可执行如下操作:读写头在存储带上向左移动一格;读写头在存储带上向右移动一格;在存储的某一格内写下或清除一符号;条件转移。图灵机在理论上能模拟现代数字计算机的一切运算，可视为现代数字计算机的数学模型。实际上，一切“可计算“函数都等价于图灵机可计算函数，而图灵机可计算函数类又等价于一般递归函数类。根据存储带是否有限，可将自动机划分为有限带自动机(Finite Automaton)和无限带自动机(Infinite Automaton)。由于图灵机有无限长的存储带，所以为一种无限带自动机。有限带自动机常用作数字电路的数学模型
4、，也用来描述神经系统和算法;而无限带自动机主要用来描述算法，也用来描述繁殖过程 (如细胞型自动机和网络型自动机)。 有限自动机是一种控制状态有限、符号集有限的自动机，是一种离散输入输出系统的数学模型。可将有限自动机设想成由一条划分为许多方格的输入带和一个控制器组成的机器:在输入带的每一个小格中可以容纳一个符号，这些符号取自一个有限符号集 S-控制器具有有限个可能状态(构成集合 Q)。并在每一时刻仅处于其中的一个状态 q;控制器有一个读入头，可以从输入带中读入符号;时间是离散的，初始时控制器处在状态;控制器的功能是根据其当前状态 g 和读入头从输入带上得到的符号 a,来确定控制器的下一时刻的状态
5、，实现从状态 q 到状态铲 q的转移，并将读入头右移一格。控制器另一功能是识别终止状态(它们构成 Q 的一个子集 F)，也可将该识别功能视为有限自动机的输出。从数学上来定义，有限自动机是一个五元组:FA=(Q，S，q0，F)其中，Q 是控制器的有限状态集、S 是输入符号约有限集、 是控制状态转移规律的 QS 到 Q 的映射 (可用状态转移图或状态转移表表示)，q0是初始状态、F 是终止状态集。若 是单值映射，则称 M 为确定性有限自动机;若 是多值映射，则称 M 为非确定性 有限自动机。Chapter2在元胞自动机是由空间上各项同性的一系列元胞所组成，是在有限元胞自动机基础上发展起来的，用于模
6、拟和分析几何空间内的各种现象。2.2.1 典型的元胞自动机在元胞自动机的发展过程中，科学家们构造了各种各样的元胞自动机模型。其中，以下几个典型模型对元胞自动机的理论方法的研究起到了极大的推动作用，因此，它们又被认为是元胞自动机发展历程中的几个里程碑。l. S.S. WolframWolfram 和初等元胞自动机和初等元胞自动机初等元胞自动机(Elementary Cellular Automata，简称 ECA)是状态集 S 只有两个元素s1，s2，即状态个数 k=2，邻居半径 r=l 的一维元胞自动机(谢惠民，1994、李才伟，1997、Wolfram，S，1986)。它几乎是最简单的元胞自
7、动机模型。由于在 S 中具体采用什么符号并不重要，它可取 0，1，-l，1，静止，运动，黑，白，生，死等等，这里重要的是 S 所含的符号个数，通常我们将其记为 0，1。此时，邻居集 N 的个数 2r=2，局部映射 f:S3S 可记为:其中变量有三个，每个变量取两个状态值，那么就有 222=8 种组合，只要给出在这八个自变量组合上的值，f 就完全确定了。例如以下映射便是其中的一个规则:通常这种规则也可表示为以下图形方式 (黑色方块代表 l，白色方块代表 0):这样，对于任何一个一维的 0，1 序列，应用以上规则，可以产生下一时刻的相应的序列。以下序列就是应用以上规则产生的:t: 01011111
8、0101011100010t+1:1010001010101010001以上八种组合分别对应 0 或 1，因而这样的组合共有 28=256 种，即初等元胞自动机只可能有 256 种不同规则。S. Wolfram 定义由上述八种构形产生的八个结果组成一个二进制(注意高低位顺序)，如上可得 01001100，然后计算它的十进制值 R:R 在0，255内，S. Wolfram 定义 R 为初等元胞自动机的标号，则上面的元胞自动机模型就是 76 号初等元胞自动机 (谢惠民，1994；李才伟，1997)。S. Wolfram 对这 256 种模型一一进行了详细而深入的研究。研究表明，尽管初等元胞自动机是
9、如此简单，但它们表现出各种各样的高度复杂的空间形态。经过一定时间，有些元胞自动机生成一种稳定状态，或静止，或产生周期性结构，那么，有些产生自组织、自相似的分形结构。S. Wolham(1983)借用分形理论计算了它们的维数约为 1.59 或 1.69(Wolfram，S.，1983)。但 256 种元胞自动机中没有一种属于 S. Wolfram 元胞自动机动力学分类得第四种，所谓复杂型。S. Wolfram 对一维元胞自动机，尤其是初等元胞自动机的深入研究奠定了元胞自动机理论的基石。对元胞自动机的理论研究，以及后来的人工生命研究和近来兴起的复杂性科学 (Science of Complexit
10、y)研究作出了卓越的贡献。2. J.J. ConwayConway 和和 “ “生命游戏生命游戏“ “生命游戏 (Came of Life)是 J. H. Conway 在 20 世纪 60 年代末设计的一种单人玩的计算机游戏(Garclner，M.，1970、1971)。他与现代的围棋游戏在某些特征上略有相似：围棋中有黑白两种棋子。生命游戏中的元胞有“生“，“死“两个状态 0，1;围棋的棋盘是规则划分的网格，黑白两子在空间的分布决定双方的死活，而生命游戏也是规则划分的网格(元胞似国际象棋分布在网格内。而不象围棋的棋子分布在格网交叉点上)。根据元胞的局部空间构形来决定生死。只不过规则更为简单。
11、下面介绍生命游戏的构成及规则:(1)元胞分布在规则划分的网格上；(2)元胞具有 0，1 两种状态，0 代表“死“，l 代表“生“；(3)元胞以相邻的 8 个元胞为邻居。即 Moore 邻居形式；(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定:在当前时刻，如果一个元胞状态为“生“，且八个相邻元胞中有两个或三个的状态为“生“，则在下-时刻该元胞继续保持为“生“，否则“死“去；在当前时刻。如果一个元胞状态为“死“。且八个相邻元胞中正好有三个为“生“。则该元胞在下一时刻 “复活“。否则保持为“死“。尽管它的规则看上去很简单。但生命游戏是具有产生动态图案和动
12、态结构能力的元胞自动机模型。它能产生丰富的、有趣的图案。生命游戏的优化与初始元胞状态值的分布有关，给定任意的初始状态分布。经过若干步的运算，有的图案会很快消失。而有的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行。有的则保持图案定向移动，形似阅兵阵，其中最为著名的是“滑翔机 (叫 Glider)“的图案。生命游戏模型已在多方面得到应用。他的演化规则近似地描述了生物群体的生存繁殖规律:在生命密度过小(相邻元胞数之 2)时，由于孤单、缺乏配种繁殖机会、缺乏互助也会出现生命危机，元胞状态值由1 变为 0;在生命密度过大 (相邻元胞数3)时，由于环境恶化、资源短缺以及相互竞争而出现生存危
13、机，元胞状态值由 1 变为 0;只有处于个体适中(相邻元胞数为 2 或 3)位置的生物才能生存(保持元胞的状态值为 1)和繁衍后代(元胞状态值由 0 变为 1)。正由于它能够模拟生命活动中的生存、灭绝、竞争等等复杂现象，因而得名“生命游戏“。JHConway 还证明，这个元胞自动机具有通用图灵机的计算能力(谢惠民，1994;李才伟，1997)，与图灵机等价，也就是说给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。从数学模型的角度看，该模型将平面划分成方格棋盘，每个方格代表一个元胞。元胞状态:0 死亡，1- 活着领域半径:1领域类型：Moore 型其中 St表示 t 时刻元胞的状态，S
14、为 8 个相邻元胞中活着的元胞数。另外，需要指出的是，目前随着人们对 “生命游戏“研究的深入，产生了许多变种和扩展。在 80 年代末，AKDewdney (Dewdney，AK，1987)和 CBays (Bays，C，1987)Dewdney，AK，1990)将Conway 的生命游戏扩展到了三维空间上，构建了三维生命游戏，并对其规则作了具有普遍性的扩展(图 2-3)。CBays 的学生 Lee Meeker 在此基础上进一步构建了四维的生命游戏。另外，Gardner (Gardner，M，1970、1971、1983)等人也曾在这方面作了很多迸一步的研究工作。对游戏规则的扩展主要是引入了
15、4 个参数 EbEkFbFk，Eb表示对于一个“活“元胞，在下一个时刻，继续保持其状态所需要的最少的“活“邻居的数目，而 Fb则表示对于一个 “死“元胞，在下一时刻，“复活“所需要的最小的“活“邻居的数目，Ek和 Fk则分别表示上述情况的上限值。演化规则修改为 3.3.格子气自动机格子气自动机格子气自动机 (Lattice 一 GasAutomata,LGA 又称格气机)，是元胞自动机在流体力学与统计物理中的具体化，也是元胞自动机在科学研究领域成功应用的范例 (李才伟，1997)。相对于“生命游戏“来说，格子气自动机是个更注重于模型的实用性。它利用元胞自动机的动态特征，来模拟流体粒子的运动。第
16、一个时空、速度等变量完全离散的格子气自动机是 1973 年由法国的 JHardy、YPomeau 和OPazzis 提出的 HPP 模型，它的模拟结果已经很接近流体力学中描述流体运动的 Navier-Strokes 方程。但模型中的流体粒子的运动只允许有四个方向，造成应力张量各向异性的致命弱点，尚不能充分反映流体的特征，因此在较长时间内没有受到足够的重视。直到 20 世纪 80 年代，SWolfram 等人的研究工作使得元胞自动机理论产生了质的飞跃，同时也带动了格子气自动机的进一步发展。1986 年，法国的UFrish、YPomeau 和美国的 BHassIacher 在 HPP 模型的基础上提出了一个有实用价值的、基于六角形网络的格子气自动机模型，得名为 FHP(Fritsch-Has，lacher-Pomeau)模型，并证明该模型的宏观行为符合标准的 Navier-Stokes 方程(李才伟，1997)。FHP 模型是第一个成功的格子气模型，并激发了研究格子
