元胞自动机简介课件.ppt

《元胞自动机简介课件.ppt》由会员分享，可在线阅读，更多相关《元胞自动机简介课件.ppt（39页珍藏版）》请在三一办公上搜索。

1、元胞自动机简介（Cellular Automata）,元胞自动机(Cellular Automata)简要发展历程,元胞自动机是定义在一个由离散、有限状态的元胞组成的元胞空间上，按照一定的局部规则，在离散时间维度上演化的动力学系统。冯诺依曼提出模仿人脑的行为，人脑包含自控制和自维护机理。考虑在完全离散的框架下处理，每个元胞都具有内在的状态，由有限数量的信息为组成；这个元胞系统按照离散时间进行演化1970年数学家Conway提出了著名的生命游戏(Game of life)。尽管生命游戏的规则简单，但具有出乎预料的复杂行为Wolfram著名的物理学家，他在研究一维和二维元胞自动机，注意到，元胞自动

2、机是一个离散的动力学系统，但显现出许多连续系统中遇到的行为。2002年一种新科学，对自然选择提出挑战，对时间单向流逝，怎样制造人造生命，股市如何涨落给出了解释；探索了树叶、数目、贝壳为什么是其形状；在其新科学的到统一解释，即元胞自动机生物学、生态学（兔子-草），物理学（流体力学、场的模拟）、化学（各种粒子在化学反应中的相互作用）、交通科学等,一、元胞自动机的定义、构成和特征,1 定义(1)物理学的定义 元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。,一、元胞自动机的定义、构成和特征,1 元胞自动机的定义(2)数学定义(基

3、于集合论的定义)设d代表空间维数，k代表元胞的状态，并在一个有限集合S中取值，r表元胞的邻居半径。Z是整数集，表示一维空间，t代表时间。为叙述和理解上简单起见，在一维空间上考虑元胞自动机，即假定d=1。那么整个元胞空间就是在一维空间，将整数集Z上的状态集S的分布，记为SZ。元胞自动机的动态演化就是在时间上状态组合的变化，可以记为:,这个动态演化又由各个元胞的局部演化规则f所决定的。这个局部函数f通常又常常被称为局部规则。对于一维空间，元胞及其邻居可以记为S2r+1，局部函数则可以记为:F(Sit+1)=f(sti-r,sti,sti+r)sti 表示在t时刻位置i处的元胞，至此，我们就得到了一

4、个元胞自动机模型,对于局部规则f来讲，函数的输入、输出集均为有限集合，实际上。它是一个有限的参照表。例如，r=1，f的形式则形似如下:0,0,0-O;0,0,1-0;0,1,0-1;1,0,0-0;0,1,1-1;1,0,1-0;1,1,0-0;1,1,1-0对元胞空间内的元胞，独立施加上述局部函数，则可得到全局的演化。,2 元胞自动机的构成,1)元胞元胞又可称为单元。或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。状态可以是0,1的二进制形式。或是s0,s2,sisk整数形式的离散集，严格意义上。元胞自动机的元胞只能有一个状态变量。但在实际应用

5、中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。就设计实现了这样一种称之为“多元随机元胞自动机”模型。在车辆交通元胞自动机模型中，对车辆占用的元胞，元胞中含有车辆的位置和速度等,2)元胞空间元胞所分布在的空间网点集合就是这里的元胞空间。理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元抱自动机。元胞空间的划分只有一种。而高维的元胞自动机。元胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机。二维元胞空间通常可按三角、四万或六边形三种网格排列。,三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有用;其缺点是在计算机的表达与显

6、示不方便，需要转换为四方网格。四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表达显示;其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型;其缺点同三角网格一样，在表达显示上较为困难、复杂。,3)邻居 元胞及元胞空间只表示了系统的静态成分，为将动态引入系统，必须加入演化规则。在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻

7、居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞，内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式(我们以最常用的规则四方网格划分为例),(1)冯-诺依曼(Von Neumann)：上下左右 4个(2)摩尔型(Moore)：上下左右；左上、左下、右上、右下；8个(3)扩展摩尔(Moore)型：r 扩展为2或更多(4)马哥勒斯(Margolus)型：它是每次将一个2x2的元胞块做统一处理，而上述前三种邻居模型中，每个元胞是分别处理的,边界条件 在理论上，元胞空间通常是在各维向上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，

8、我们无法在计算机上实现这一理想条件，因此，需要定义不同的边界条件。三种类型:周期型、反射型和定值型。周期型：是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的“圈”。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面，形似车胎或甜点圈。周期型空间与无限空间最为接近，在理论探讨时，常以此类空间型作为试验。反射型：指在边界外邻居的元胞状态是以边界为轴的镜面反射。定值型：指所有边界外元胞均取某一固定常量，如0，1等。在实际应用中，尤其是二维或更高维数的构模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型,4)规则(Rule)根据元胞当前状态及其邻

9、居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。记为f:sit+1=f(sit,sNt)，sNt为t时刻的邻居状态组合，我们称f为元胞自动机的局部映射或局部规则,3 元胞自动机的特征,1)同质性、齐性:同质性，每个元胞的变化服从相同的规律；齐性，元胞的分布方式相同，大小形状相同，空间分布规则整齐2)时间离散:元胞按一定规律分布在离散的元胞空间上3)空间离散:演化按等间隔时间分步进行,时间只取等步长的时刻点4)状态离散有限：5)同步计算:元胞自动机的处理同步进行，适合并行计算6)时空局域性:元胞在t+1时刻的状态，取决于其周围半径r的邻域中的元胞在t时刻的状态，及所谓的时

10、间、空间局限性7)维数高:在动力系统中一般讲变量的个数称为维数。由于任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集，每个元胞的状态便是这个动力学系统的变量。因此，元胞自动机是一类无穷维动力系统。,二、经典的元胞自动机模型,1 Conway和他的“生命游戏”1)“生命游戏”的构成及演化规则(1)”生命游戏”的构成：元胞分布在规则换分的二维方形网格上；元胞具有0、1两种状态，0代表死，1代表生；元胞以相邻的上下左右好对焦线上的8个元胞维邻居；一个元胞的生死有其在该时刻本身的生死状态和周围8个邻居的状态决定。(2)“生命游戏”的演化规则：生存：对一个活的元胞，如果它的邻居中有2个

11、或3个元胞是活的，那么该元胞将继续生存；死亡：对于一个活的元胞，如果它的邻居中有4个或4个以上的元胞是活的，该元胞死亡；如果它的邻居中只有1个或没有活的元胞，那么死亡；繁殖：对1个空的元胞，如果它的邻居中有3个活的，那么该元胞将成为活的元胞,二、经典的元胞自动机模型,2)“生命游戏”中一些演化形态,二、经典的元胞自动机模型,2 Wolfram和他的初等元胞自动机 1)初等元胞自动机,初等元胞自动机是状态集S只有两个元素，即k=2，邻居半径r=1的一维元胞自动机。,初等一维元胞自动机可能的8种输入状态组合111 110 101 100 011 010 001 000,rule 18,rule 5

12、7,rule 150,rule 30,rule 73,rule 126,rule 124,rule 169,2）典型的Wolfram规则,3)元胞自动机种类Stephen Wolfram 对初等元胞自动机的分类平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Perlodical Patterns)。混沌型:自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征

13、不再变化，通常表现为分形分维特征。复杂型:出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。,三、元胞自动机应用 在社会学中，元胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。在生物学中，元胞自动机的设计思想本身就来源于生物学自繁殖的思想，因而它在生物学上的应用更为自然而广泛。例如：元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索(Victor.Jonathan.D.1990)、爱滋病病毒HIV的感染过程(Sieburg.H.B.1990)、自组织、自繁殖等生命现象的研究以及最新流行的克隆(Clone)技术的研究等(Erme

14、ntroutG.B.1993)。应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、歹境、军事学等。,四、基于元胞自动机的基本交通模型,1.1模型的建立,考虑一个有等长的L个格子的线段，每个格子可有一个向右行驶的车或为空。行驶规则为：若前方格子有车，则停止。若前方为空，则前进一格，不能跟驰。采用周期边界，此即为NS模型即：f为：,1一维模型,1.2 结果,时空分布图,横轴：空间纵轴：时间,2 二维基本模型,2.1模型的建立,考虑一个L*L的网格，对任一格子(i,j),共有三种状态，即有一个向右行驶的车、有一个向上行驶的车和空。行驶规则为奇数时间向右行驶的车可以前

15、进，且一辆车只有前方格子里空时可前进一格。不能跟驰，偶数时间步向上的车可以行驶，规则同右行。,2.2 结果,平均速度和平均车流密度的关系,快照,3 基本模型的改进,3.1 一维变速模型,在NS模型的基础上，考虑车可有不同的速度，并制定相应的运行规则，最大速度为Vmax为正整数，这样，每个格子的状态为空，或具有一个小于等于Vmax的非负整数的车。运行规则考虑加速、减速、随机事件等因素。,3.1模型,3.2 结果,3.2 二维双向模型,在原二维的元胞自动机基础上，考虑双向行驶机制，则每个格子有七中状态：空，右行，上行，左行，下行，左右，上下。运行规则类似于原二维模型。,模型,3.2.2 结果,平均速度和平均车流密度的关系,3.2.3 快照,