元胞自动机调研报告.pptxVIP

元胞自动机调研报告 清华大学自动化系 自45班 林子坤 1 目录 预备知识：名词解释 元胞自动机的提出及发展历史 元胞自动机的说明与描述 元胞自动机的分类 元胞自动机的实际程序运行 元胞自动机的意义 预备知识：名词解释 元胞：又可称为基元, 是元胞自动机的最基本的组成部分,每一个元胞都有记忆贮存状态的功能, 或者可以说元胞就是一种状态.最简单的情况下, 元胞只有两种可能状态; 较复杂情况下,元胞具有多种状态.系统中所有元胞的状态都按照元胞自动机的动力规则不断更新。 元胞空间：是元胞所分布在的空间网格集合（它可以是任意维数欧几里德空间的规则划分）。对于一维元胞自动机,元胞空间的划分只有一种,而二维元胞自动机,二维元胞空间通常可以按三角、正方形、六边形三种网格排列。 预备知识：名词解释 预备知识：名词解释 元胞边界：理论上的元胞空间通常是在各维上是无限的,但却无法在计算机上实现,因此, 我们需要定义不同的边界条件。有周期边界（在2维中主要指上下连接，左右连接）、固定边界、绝热边界、映射边界。 元胞邻居：在给出规则之前,必须定义一定的邻居规则,明确哪些元胞属于该元胞的邻居。在一维元胞自动机中,通常以半径r 来确定邻居,距离一个胞r 内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂,但通常有Von. Neumann 型、Moore 型及扩展Moore 型。 预备知识：名词解释 元胞状态：取值于一个有限的离散集。严格意义上,元胞自动机的元胞只能有一个状态变量, 但在实际应用中, 往往将其进行了扩展。 元胞自动机的提出及发展历史 元胞自动机由冯诺依曼和数学家斯塔尼斯拉夫乌拉姆（氢弹之父）于1948年首先提出。 1964年埃德加·弗兰克·科德（关系数据库之父）对冯诺依曼的元胞自动机进行简化。 1970年生命游戏诞生。 20世纪80年代斯蒂芬·沃尔夫勒姆对元胞自动机进行简化 元胞自动机的提出及发展历史 20世纪90年代，元胞自动机发展百花齐放，以美国圣达菲为代表，提出了人工生命。 进入21世纪蒂芬·沃尔夫勒姆的A MEW KIND OF Science将元胞提升到更高一层。 元胞自动机的说明与描述 元胞自动机是离散(discrete)动力学(dynamic), 用简单规则控制相互作用的元胞模拟复杂世界。 散布在规则网格中的每一个元胞去有限的离散状态，遵循一定的局部规则做出相应的更新，大量的元胞通过简单的相互作用够成动态系统的演化，元胞不是有严格的物理方程或函数确定，而是由一系列的模型构造的规则构成，凡是满足这些规则的模型都是元胞自动机。 元胞自动机的说明与描述 元胞自动机不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。 因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。 元胞自动机的分类 元胞自动机的构建没有固定的数学公式，构成方式繁杂，变种很多，行为复杂。故其分类难度也较大，自元胞自动机产生以来，对于元胞自动机分类的研究就是元胞自动机的一个重要的研究课题和核心理论，在基于不同的出发点，元胞自动机可有多种分类，其中，最具影响力的当属S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类，而基于维数的元胞自动机分类也是最简单和最常用的划分。除此之外，在1990年，Howard A.Gutowitz提出了基于元胞自动机行为的马尔科夫概率量测的层次化、参量化的分类体系（Gutowitz,H. A.,1990）。 元胞自动机的分类 基于维数的分类： 一维元胞：初等元胞自动机(ECA)是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=l的一维元胞自动机。它几乎是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取 {0，1}，{-l，1}，{静止，运动}，{黑，白}，{生，死}等等，这里重要的是S所含的符号个数，通常我们将其记为 {0，1}。此时，邻居集N的个数2r=2，局部映射f:S3→S可记为 考虑有等长的L个格子的线段，每一个格子i都有两种状态 0和 1，在t时刻i格子的状态记为： ，记 其中变量有三个，每个变量取两个状态值，那么就有2×2×2=8种组合，只要给出在这八个自变量组合上的值，f就完全确定了。 元胞自动机的分类 二维元胞：元胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以J. H. Conway的“生命游戏”为代表，“深林火灾”，应用最为广泛。由于，世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到二维空间上，所以