《元胞自动机.ppt》由会员分享，可在线阅读，更多相关《元胞自动机.ppt（39页珍藏版）》请在三一办公上搜索。
1、智能化空间分析 元胞自动机,讲述人：王爱平,建筑与城乡规划系,2011年6月,地 理 元 胞 自 动 机 Geo-Cellular Automata,提纲：一、自动机二、元胞自动机三、几种常见的元胞自动机四、元胞自动机的分类五、元胞自动机与GIS的关系,地 理 元 胞 自 动 机 Geo-Cellular Automata,一、自动机 自动机（Automaton)通常指不需要人们逐步进行操作指导的设备，例如，全自动洗衣机可按照预先安排好的操作步骤作自动地运行；现代计算机能自动地响应人工编制的各种编码指令，完成各种复杂的分析与计算；机器人则将自动控制系统和人工智能结合，实现类人的一系列活动。另一
2、方面，自动机也可被看作为一种离散数字动态系统的数学模型。,地 理 元 胞 自 动 机 Geo-Cellular Automata,二、元胞自动机 1948年，数学家和“现代计算机之父”Von Neumann 和 Ulam 首次提出元胞自动机（CA）的概念，其目的主要是从计算的角度来设计出一种可自我复制的自动机。由于CA有很强的模拟复杂系统的自组织现象的能力，其很快被应用于生物演化、环境变化、地理演变、景观更替、交通流、林火扩散和城市系统等的模拟研究当中，取得了许多有意义的研究成果。,地 理 元 胞 自 动 机 Geo-Cellular Automata,元胞自动机(Cellular Autom
3、ata.简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)，是一个时间和空间都离散的动力系统。散布在规则格网(LattceGrid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。元胞自动机最基本的组成：元胞、元胞空间、邻居及规则。简单地讲，元胞自动机可以视为一个元胞空间和定义与该
4、空间的变换函数所组成。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。,地 理 元 胞 自 动 机 Geo-Cellular Automata,地 理 元 胞 自 动 机 Geo-Cellular Automata,1.元胞：元胞又可称为单元,或基元，是元胞自动机的最基本的组成部分。元胞 分布在离散的一维、二维或多维欧几里德空间的晶格点上。2.状态：状态可以是0,1的二进制形式。或是s0,s1,sisk整数形式的离散集，严格意义上,元胞自动机的元胞只能有一个状态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。由于
5、邻居关系，每个元胞有有限个元胞作为它的邻居。3.元胞空间(Lattice)：元胞所分布在的空间网点集合就是这里的元胞空间。元胞空间的几何划分:理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元胞自动机，元胞空间的划分只有一种。而高维的元胞自动机，元胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机，通常可按三角、四边或六边形三种网格排列(图2-5)。,地 理 元 胞 自 动 机 Geo-Cellular Automata,地 理 元 胞 自 动 机 Geo-Cellular Automata,4.邻居(Neighbor)：以上的元胞及元胞
6、空间只表示了系统的静态成分，为将“动态”引入系统，必须加入演化规则。在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式(我们以最常用的规则四方网格划分为例)。见图2-6，,地 理 元 胞 自 动 机 Geo-Cellular Automata,地 理 元 胞 自 动 机 Geo-Cellular Automata,黑
7、色元胞为中心元胞，灰色元胞为其邻居，利用它们所处的状态一起来计算中心元胞在下一时刻的状态。,l)冯-诺依曼(Von.Neumann)型 一个元胞的上、下、左、右相邻四个元胞为该元胞的邻居。这里，邻居半径r为1，相当于图像处理中的四邻域、四方向。2)摩尔(Moore)型 一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该元胞的邻居。邻居半径r同样为1，相当于图像处理中的八邻域、八方向。3)扩展的摩尔(Moore)型 将以上的邻居半径r扩展为2或者更大，即得到所谓扩展的摩尔型邻居。,地 理 元 胞 自 动 机 Geo-Cellular Automata,5.规则(Rule)：根据元胞
8、当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。我们将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数。这个函数构造了一种简单的、离散的空间/时间的局部物理成分。要修改的范围里采用这个局部物理成分对其结构的“元胞”重复修改。这样，尽管物理结构的本身每次都不发展，但是状态在变化。它可以记为f:sit+1=f(sit,sNt)，sNt为t时刻的邻居状态组合，我们称f为元胞自动机的局部映射或局部规则。,地 理 元 胞 自 动 机 Geo-Cellular Automata,6.时间(Time)：元胞自动机是一个动态系统，它在时间维上的变化
9、是离散的，即时间t是一个整数值，而且连续等间距。假设时间间距dt=1，若t=O为初始时刻。那么。t=1为其下一时刻。在上述转换函数中，一个元胞在t十1的时刻只(直接)决定于t时刻的该元胞及其邻居元胞的状态，在t=1时刻的元胞及其邻居元胞的状态间接(时间上的滞后)影响了元胞在t+1的时刻的状态。由以上对元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的概念。用数学符号来表示，标准的元胞自动机是一个四元组:A=(Ld,S,N,f)这里A代表一个元胞自动机系统；L表示元胞空间，d是一正整数，表示元胞自动机内元胞空间的维数;S是元胞的有限的、离散的状态集合;N表示一个所有邻域内元胞的组合(包括中
10、心元胞)，即包含n个不同元胞状态的一个空间矢量，记为:N=(s1,s2,.,sn)n是元胞的邻居个数。siZ(整数集合)，i1，.,n；f表示将Sn映射到S上的一个局部转换函数。所有的元胞位于d维空间上，其位置可用一个d元的整数矩阵Zd来确定。,地 理 元 胞 自 动 机 Geo-Cellular Automata,三、几种常见的元胞自动机1、S.Wolfram和初等元胞自动机 初等元胞自动机(Elementary Cellular Automata，简称ECA)是状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径r=l的一维元胞自动机。它几乎是最简单的元胞自动机模型。由于在S中具体采
11、用什么符号并不重要，它可取 0，1，-l，1，静止，运动，黑，白，生，死等等，这里重要的是S所含的符号个数，通常我们将其记为 0，1。此时，邻居集N的个数2r=2，局部映射f:S3S可记为:,地 理 元 胞 自 动 机 Geo-Cellular Automata,其中变量有三个，每个变量取两个状态值，那么就有222=8种组合，只要给出在这八个自变量组合上的值，f就完全确定了。例如以下映射便是其中的一个规则：通常这种规则也可表示为以下图形方式(黑色方块代表l，白色方块代表0):,地 理 元 胞 自 动 机 Geo-Cellular Automata,这样，对于任何一个一维的0，1序列，应用以上规
12、则，可以产生下一时刻的相应的序列。以下序列就是应用以上规则产生的:t:010111110101011100010 t+1:1010001010101010001 以上八种组合分别对应0或1，因而这样的组合共有28=256种，即初等元胞自动机只可能有256种不同规则。S.Wolfram定义由上述八种构形产生的八个结果组成一个二进制(注意高低位顺序)，如上可得01001100，然后计算它的十进制值R:,地 理 元 胞 自 动 机 Geo-Cellular Automata,R在0，255内，S.Wolfram定义R为初等元胞自动机的标号，则上面的元胞自动机模型就是76号初等元胞自动机,地 理 元
13、胞 自 动 机 Geo-Cellular Automata,S.Wolfram对这256种模型一一进行了详细而深入的研究。研究表明，尽管初等元胞自动机是如此简单，但它们表现出各种各样的高度复杂的空间形态。经过一定时间，有些元胞自动机生成一种稳定状态，或静止，或产生周期性结构，那么，有些产生自组织、自相似的分形结构。S.Wolham(1983)借用分形理论计算了它们的维数约为1.59或1.69(Wolfram，S.，1983)。但256种元胞自动机中没有一种属于S.Wolfram元胞自动机动力学分类的第四4种，即所谓复杂型。,地 理 元 胞 自 动 机 Geo-Cellular Automata
14、,2、J.Conway和 生命游戏“生命游戏(Came of Life)是J.H.Conway在20世纪60年代末设计的一种单人玩的计算机游戏(Garclner，M.，1970、1971)。他与现现代的围棋游戏在某些特征上略有相似：围棋中有黑白两种棋子，生命游戏中的元胞有生，死两个状态 0，1;围棋的棋盘是规则划分的网格，黑白两子在空间的分布决定双方的死活，而生命游戏也是规则划分的网格。根据元胞的局部空间构形来决定生死。只不过规则更为简单。,地 理 元 胞 自 动 机 Geo-Cellular Automata,生命游戏的构成及规则:(1)元胞分布在规则划分的网格上；(2)元胞具有0，1两种状
15、态，0代表“死”，1代表“生”；(3)元胞以相邻的8个元胞为邻居。即Moore邻居形式；(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态(确切讲是状态的和)决定:在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下一时刻该元胞继续保持为“生”，否则“死”去；在当前时刻。如果一个元胞状态为死。且八个相邻元胞中正好有三个为生。则该元胞在下一时刻 复活。否则保持为死。,地 理 元 胞 自 动 机 Geo-Cellular Automata,生命游戏的优化与初始元胞状态值的分布有关，给定任意的初始状态分布。经过若干步的运算，有的图案会很快消失。而有
16、的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行。有的则保持图案定向移动，形似阅兵阵，其中最为著名的是滑翔机(叫Glider)的图案。,地 理 元 胞 自 动 机 Geo-Cellular Automata,生命游戏模型已在多方面得到应用。他的演化规则近似地描述了生物群体的生存繁殖规律:在生命密度过小(相邻元胞数之2)时，由于孤单、缺乏配种繁殖机会、缺乏互助也会出现生命危机，元胞状态值由1变为0;在生命密度过大(相邻元胞数3)时，由于环境恶化、资源短缺以及相互竞争而出现生存危机，元胞状态值由1变为0;只有处于个体适中(相邻元胞数为2或3)位置的生物才能生存(保持元胞的状态值为1)
17、和繁衍后代(元胞状态值由0变为1)。正由于它能够模拟生命活动中的生存、灭绝、竞争等等复杂现象，因而得名“生命游戏”。给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。,地 理 元 胞 自 动 机 Geo-Cellular Automata,从数学模型的角度看，该模型将平面划分成方格棋盘，每个方格代表一个元胞。元胞状态:0 死亡，1-活着领域半径:1领域类型：Moore型 其中St表示t时刻元胞的状态，S为8个相邻元胞中活着的元胞数。,地 理 元 胞 自 动 机 Geo-Cellular Automata,另外，需要指出的是，目前随着人们对 生命游戏研究的深入，产生了许多变种和扩展。在80
18、年代末，AKDewdney(Dewdney，AK，1987)和CBays(Bays，C，1987)Dewdney，AK，1990)将Conway的生命游戏扩展到了三维空间上，构建了三维生命游戏，并对其规则作了具有普遍性的扩展(图2-3)。,地 理 元 胞 自 动 机 Geo-Cellular Automata,对游戏规则的扩展主要是引入了4个参数EbEkFbFk，Eb表示对于一个“活”元胞，在下一个时刻，继续保持其状态所需要的最少的“活”邻居的数目，而Fb则表示对于一个“死”元胞，在下一时刻，“复活”所需要的最小的“活”邻居的数目，Ek和Fk则分别表示上述情况的上限值。演化规则修改为：,地 理
19、 元 胞 自 动 机 Geo-Cellular Automata,3、格子气自动机 格子气自动机(Lattice一GasAutomata,LGA又称格气机)，是元胞自动机在流体力学与统计物理中的具体化，也是元胞自动机在科学研究领域成功应用的范例。相对于“生命游戏”来说，格子气自动机是个更注重于模型的实用性。它利用元胞自动机的动态特征，来模拟流体粒子的运动。格子气自动机是一种特殊的元胞自动机模型，或者说是一个扩展的元胞自动机模型(Extended Cellular Automata)。,地 理 元 胞 自 动 机 Geo-Cellular Automata,其特征如下:(1)由于流体粒子不会轻易
20、从模型空间中消失，这个特征需要格子气自动机是一个可逆元胞自动机模型。(2)格子气自动机的邻居模型通常采用Margulos类型，即它的规则是基于一个2X2的网格空间的。它的规则形似如下:这里黑色球代表流体粒子，白色球代表空的元胞。可以看出，格子气自动机不同于其它的元胞自动机模型，以一个元胞(常被称为中心元胞）为研究对象，考虑其状态的转换，而是考虑包含四个元胞的一个四方块。(3)依照上述规则和邻居模型在计算完一次后，需要将这个2X2的模板沿对角方向滑动，再计算一次。那么，一个流体粒子的运动需要两步t-t+l-t+2才能完成。,地 理 元 胞 自 动 机 Geo-Cellular Automata,
21、4、Langton和“能自我复制的元胞自动机”Langton在二维元胞自动机中发现的一个能自我复制的“圈”或称“能自我复制的元胞自动机”。Langton在von Neumann和Codd工作的基础上，设计了一个能自我复制的圈。元胞状态在(0，1，2，3，4，5，6，7)中取值，其中，0，1，2，3构成元胞自动机的基本结构，04，05，06，07代表信号。l代表核元胞;2代表壳元胞，是边界;2包围的部分构成信息通道或称数据路径。邻居模型采用Von Neumann的4邻居模型。,地 理 元 胞 自 动 机 Geo-Cellular Automata,元胞自动机通过信号元胞替代相邻的元胞，如状态为1
22、的元胞，要完成信号传递，信号传播的过程可以通过下面的例子说明:数据路径可以分支，在分支的节点处，信号在各个分支中复制本身，产生多个复制品。下图中，07信号在T形的交叉点处，复制自身:,地 理 元 胞 自 动 机 Geo-Cellular Automata,地 理 元 胞 自 动 机 Geo-Cellular Automata,这个元胞自动机模型的另外一个重要特征就是路径扩张。即一定的信号可以产生数据路径的延伸，如下图所示：有了上面的论述，下面的具有路径扩张的、能自我复制的圈的工作机理应当容易理解了。,地 理 元 胞 自 动 机 Geo-Cellular Automata,四、元胞自动机的分类1
23、、S.Wolfram在80年代初做的基于动力学行为的元胞自动机分类:平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态,不随随时间变化而变化。周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Perlodical Patterns)。由于这些结构可看作是一种滤波器(Filter)，故可应用到图像处理的研究中。混沌型:自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变化，通常表现为分形分维特征。复杂型:出现复杂的局部结构，或
24、者说是局部的混沌，其中有些会不断地传播。,地 理 元 胞 自 动 机 Geo-Cellular Automata,2、按维数分类（1）一维元胞自动机:元胞按等间隔方式分布在一条向两侧无限延伸的直线上，每个元胞(Cell)具有有限个状态s，sS=s1,s2,.,sk，定义邻居半径r，元胞的左右两侧共有2r个元胞作为其邻居集合N，定义在离散时间维上的转换函数f:S2r+1S可以记为:Sit为第i个元胞在t时刻的状态。称上述A=S,N,f三元组(维数d1)为一维元胞自动机。,地 理 元 胞 自 动 机 Geo-Cellular Automata,（2）二维元胞自动机:元胞分布在二维欧几里德平面上规则
25、划分的网格点上，通常为四边行网格划分。以J.H.Conway的生命游戏为代表，应用最为广泛。由于世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到二维空间上，所以，二维元胞自动机的应用最为广泛，多数应用模型都是二维元胞自动机模型。,地 理 元 胞 自 动 机 Geo-Cellular Automata,（3）三维元胞自动机：目前，Bays(Bays,C,1988)等人在这方面做了若干试验性工作，包括在三维空间上实现了生命游戏，延续和扩展了一维和二维元胞自动机的理论。（4）高维元胞自动机：只是在理论上进行少量的探讨，实际的系统模型较少。,地 理 元 胞 自 动 机 Geo-
26、Cellular Automata,五、元胞自动机与GIS的关系 GIS的出现是现代地理学的一次重要革命，使地理学由定性的描述转向定量的观测和分析。但是，到目前为止，地理信息系统仍沉溺于描述和处理静态的空间信息，难以有效的表达时空动态数据，更谈不上时空过程的分析能力，对于动态时空信息的表达和分析显得力不从心。而地理复杂现象，如土地利用变化、城市发展、疾病扩散、火灾蔓延、人口迁移、环境演变、沙漠化等都表现为复杂的时空动态过程，这些地理现象的发展过程往往比其最终形成的空间格局更为重要。GIS现有的空间分析功能受到了挑战，需要寻求新的理论和方法来解决地理学经常遭遇到的时空动态问题。元胞自动机等地理模
27、拟系统的及时出现消除了地理学的这种尴尬的境况。元胞自动机等地理模拟系统是建立于复杂系统理论基础上的，复杂性科学一般都采用“自下而上”的研究方法，即微观离散的模拟方法。复杂性科学认为复杂系统的形成是因为简单个体或元素的相互作用，“复杂来自于简单”是复杂性科学的精髓。这种微观离散的研究方法恰好能与GIS想匹配，因为GIS对地理数据的时空表达也是离散的。因此元胞自动机等地理模拟系统能够很好地与GIS进行耦合，并且这种耦合能够相互弥补各自的缺陷。一方面，GIS能够为地理模拟系统提供丰富的空间信息，并作为其空间数据处理的平台，及时显示和反馈地理模拟系统在各种情境下的模拟效果，更为重要的是，GIS还能对模
28、拟结果进行有关空间分析；另一方面，地理模拟系统则大大弥补了GIS较弱的过程模拟能力的不足。所以在很大程度上，地理模拟系统是GIS的重要拓展。,地 理 元 胞 自 动 机 Geo-Cellular Automata,推荐书籍：1、地理模拟系统：元胞自动机与多智能体 作者：黎夏 叶嘉安 刘小平 杨青生 科学出版社 2008年2、地理元胞自动机研究 作者：周成虎 孙战利 谢一春 科学出版社 1999年,地 理 元 胞 自 动 机 Geo-Cellular Automata,常用的CA模拟软件：1、人工生命游戏的模拟：http:/alife.santafe.edu/joke/zooland;http:
29、/www.bangor.ac.uk/ma/links/delllist.html;http:/wwwhome.cs.utwente.nl/heylen/art-2.html;http:/www.fourmilab.ch/cellab/;http:/psoup.math.wisc.edu/sink.html基于Windows的CA软件WINLIFE可以在下面的网站下载：http:/psoup.math.wisc.edu/sink.html2、不同转换规则对模拟结果的影响（CelLab软件）http:/www.fourmilab.ch/cellab/3、研究现存的CA转换规则和模式（MCell软件）http:/psoup.math.wisc.edu/mcell/download.html,地 理 元 胞 自 动 机 Geo-Cellular Automata,地 理 元 胞 自 动 机 Geo-Cellular Automata,谢谢大家！,
