元胞自动机.pptVIP

智能化空间分析 ——元胞自动机 讲述人：王爱平 地 理 元 胞 自 动 机 Geo-Cellular Automata 提纲： 一、自动机 二、元胞自动机 三、几种常见的元胞自动机 四、元胞自动机的分类 五、元胞自动机与GIS的关系 一、自动机 自动机（Automaton) 通常指不需要人们逐步进行操作指导的设备，例如，全自动洗衣机可按照预先安排好的操作步骤作自动地运行；现代计算机能自动地响应人工编制的各种编码指令，完成各种复杂的分析与计算； 机器人则将自动控制系统和人工智能结合，实现类人的一系列活动。另一方面，自动机也可被看作为一种离散数字动态系统的数学模型。 二、 元胞自动机 1948年，数学家和“现代计算机之父”Von Neumann 和 Ulam 首次提出元胞自动机（CA）的概念，其目的主要是从计算的角度来设计出一种可自我复制的自动机。由于CA有很强的模拟复杂系统的自组织现象的能力，其很快被应用于生物演化、环境变化、地理演变、景观更替、交通流、林火扩散和城市系统等的模拟研究当中，取得了许多有意义的研究成果。 元胞自动机(Cellular Automata. 简称CA， 也有人译为细胞自动机、点格自动机、分子自动机或单元自动机) ，是一个时间和空间都离散的动力系统。散布在规则格网(LattíceGrid) 中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。 不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。元胞自动机最基本的组成：元胞、元胞空间、邻居及规则。简单地讲，元胞自动机可以视为一个元胞空间和定义与该空间的变换函数所组成。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。 1.元胞：元胞又可称为单元,或基元，是元胞自动机的最基本的组成部分。元胞 分布在离散的一维、二维或多维欧几里德空间的晶格点上。 2.状态：状态可以是{0,1}的二进制形式。或是{s0,s1,……si……sk}整数形式的离散集，严格意义上,元胞自动机的元胞只能有一个状态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。由于邻居关系，每个元胞有有限个元胞作为它的邻居。 3.元胞空间(Lattice)：元胞所分布在的空间网点集合就是这里的元胞空间。元胞空间的几何划分:理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元胞自动机，元胞空间的划分只有一种。而高维的元胞自动机，元胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机，通常可按三角、四边或六边形三种网格排列 (图2-5)。 4.邻居 (Neighbor)：以上的元胞及元胞空间只表示了系统的静态成分，为将“动态”引入系统，必须加入演化规则。在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式(我们以最常用的规则四方网格划分为例)。见图2-6， l)冯-诺依曼(Von. Neumann)型 一个元胞的上、下、左、右相邻四个元胞为该元胞的邻居。这里，邻居半径r为1，相当于图像处理中的四邻域、四方向。 2)摩尔(Moore)型 一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该元胞的邻居。邻居半径r同样为1，相当于图像处理中的八邻域、八方向。 3)扩展的摩尔(Moore)型 将以上的邻居半径r扩展为2或者更大，即得到所谓扩展的摩尔型邻居。 5.规则(Rule)： 根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。我们将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数 。这个函数构造了一种简单的、离散的空间/时间的局部物理成分。要修改的范围里采用这个局部物理成分对其结构的“元胞”重复