第2讲-2-元胞自动机简介2011.pptxVIP

元胞自动机简介（Cellular Automata）;元胞自动机(Cellular Automata)简要发展历程;一、元胞自动机的定义、构成和特征;一、元胞自动机的定义、构成和特征;; 对于局部规则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,……si……sk}整数形式的离散集，严格意义上。元胞自动机的元胞只能有一个状态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。就设计实现了这样一种称之为“多元随机元胞自动机”模型。在车辆交通元胞自动机模型中，对车辆占用的元胞，元胞中含有车辆的位置和速度等;;? 三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有用;其缺点是在计算机的表达与显示不方便，需要转换为四方网格。????四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表达显示;其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。??? 六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型;其缺点同三角网格一样，在表达显示上较为困难、复杂。 ;;;边界条件 在理论上，元胞空间通常是在各维向上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，需要定义不同的边界条件。 三种类型:周期型、反射型和定值型。 周期型：是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的“圈”。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面 ，形似车胎或甜点圈。周期型空间与无限空间最为接近，在理论探讨时，常以此类空间型作为试验。 反射型：指在边界外邻居的元胞状态是以边界为轴的镜面反射。 定值型：指所有边界外元胞均取某一固定常量，如0，1等。 在实际应用中，尤其是二维或更高维数的构模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型 ;;3 元胞自动机的特征;二、经典的元胞自动机模型;二、经典的元胞自动机模型;二、经典的元胞自动机模型;rule 18;3)元胞自动机种类 Stephen Wolfram 对初等元胞自动机的分类 平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。 周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Perlodical Patterns)。 混沌型:自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变化，通常表现为分形分维特征。 复杂型:出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。;三、元胞自动机应用 在社会学中，元胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。 在生物学中，元胞自动机的设计思想本身就来源于生物学自繁殖的思想，因而它在生物学上的应用更为自然而广泛。 例如：元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索(Victor.Jonathan.D. 1990)、爱滋病病毒HIV的感染过程(Sieburg.H.B.1990)、自组织、自繁殖等生命现象的研究以及必威体育精装版流行的克隆 (Clone)技术的研究等 (ErmentroutG.B.1993)。 应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、歹境、军事学等。;四、基于元胞自动机的基本交通模型;1.1模型的建立;1.2 结果;2 二维基本模型;2.1模型的建立;2.2 结果;快照;3 基本模型的改进;3.1 一维变速模型;3.2 结果;3.2 二维双向模型;3.2.2 结果;3.2.3 快照