元胞自动机理论幻灯片.ppt

第十一章 元胞自动机理论 及其应用;参考文献：;1.元胞自动机的定义 2.初等元胞自动机 3.交通流的元胞自动机模型 4.火灾逃生的元胞自动机模型;典型应用：; 1. 元胞自动机模型 元胞自动机(Cellular Automata，简称CA)是一个时间和空间都离散的动力系统。散布在规则格网 中的每一元胞取有限的离散状态，遵循同样的规则作同步更新。 大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的方程或函数确定，而是用一系列的规则构成。 凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。;2.初等元胞自动机;初等元胞自动机是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=1的一维元胞自动机。它是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取 {0，1}，{-1，1}，{静止，运动} 等等，重要的是S所含的符号个数，通常我们将其记为 {0，1}。此时，邻居集N的个数2·r=2，局部映射f：S3→S可记为:;;Three centuries ago science was transformed by the dramatic new idea that rules based on mathematical equations could be used to describe the natural world. My purpose in this book is to initiate another such transformation, and to introduce a new kind of science that is based on the much more general types of rules that can be embodied in simple computer programs. ;256种初等CA规则;3. 交通流的元胞自动机模型 特别注意：第184号规则 车辆行驶规则为：黑色元胞表示被一辆车占据，白色表示无车，若前方格子有车，则停止。若前方为空，则前进一格。;NS 模型是一个随机CA交通流模型，每辆车的状态都由它的速度和位置所表示，其状态按照以下演化规则并行更新 ： a) 加速过程 b）安全刹车过程 c）随机慢化过程 （以随机慢化概率p） d）位置更新 ;;在NS 模型的基础上，又陆续地提出了一系列一维CA交通模型，如TT、BJH、VDR、FI等模型； 双车道CA交通模型：STNS模型 机非混合CA模型： CCA模型 城市路网CA模型： BML、CTM模型;高速公路自发形成的堵塞;随机慢化概率p=0.2；密度ρ=13.3veh/km/lan（0.1）； ;随机慢化概率p=0.2；密度ρ=20veh/km/lan（0.15）； ;随机慢化概率p=0.2；密度ρ=27veh/km/lan（0.2）； ;随机慢化概率p=0.2；密度ρ=33veh/km/lan（0.25）； ;4.火灾逃生的元胞自动机模型;（1）元胞的划分 火灾的发生均是在一定区域中，因此火灾逃生区域是一个二维的空间。在模型中，将所研究的二维空间按矩形方式进行均匀的网格划分，每个格点即为元胞，所有元胞共同构成了元胞空间。 在模型中，将每个元胞的大小划分为只能容纳一个人的大小，如0.4m ×0.4m。这是密集人流中的典型的人员空间分配。 ;（2）邻域空间 在一个给定的元胞点阵中，规定每个元胞在计算自己的下一个状态时所考察的邻域。 模拟火灾逃生的正方形网格空间下, 选择两种邻域形式。 （a）由Von. Neumann限定每个元胞只注意它四个最临近的元胞,即上、下、左、右四个邻居。 （b）由Moore邻域除了包含元胞的四个邻居外,还包含另外四个对角的次临近元胞。;这两种邻域的形式实际上是火灾逃生中人员的视野概念。随着人员视野的扩大,其对当前时间步运动方向的确定就可以按照下一时间步的最优选择来进行。此外,视野还可以用来模拟人员在火灾中由于烟气存在而导致的视力范围缩小等问题。;（3）元胞状态 在元胞空间中, 每个元胞有两种状态：一是被人占据，另一种空，没有人员。在数学公式里，元胞的状态数就是Si 可能的取值数，或叫做它的域。 所有元胞的状态是同时发生变化的，在时刻t+1的第i个元胞的状态是由时刻 t 的第 i个元胞以及相邻的距离不超过r的 2r个元胞的状态决定的。;(4) 元胞状态变化的规则 元胞下一时间的状态主要有两个并行的变更阶段。第一个阶段是目