第十一章 元胞自动机理论

1、12022-6-29第十一章第十一章元胞自动机理论元胞自动机理论及其应用及其应用22022-6-29参考文献：nStephen Wolfram，A New Kind of Science，Wolfram Media, Inc., 2002 n高原等，细胞自动机的多重分形特征和动力学根源，西北地震学报，1995，4n何越磊，铁路选线中的元胞自动机模型，兰州交通大学学报，2004/0132022-6-29n1. .元胞自动机的定义元胞自动机的定义n2.2.初等元胞自动机初等元胞自动机n3.3.交通流的元胞自动机模型交通流的元胞自动机模型n4.4.火灾逃生的元胞自动机模型火灾逃生的元胞自动机模型42

2、022-6-29典型应用：n交通流模拟n火灾逃生、人员疏散模型n森林火灾模型n城市、农村土地利用演化模拟n社会学、生物学、生态学、信息科学、计算机科学、数理化 52022-6-29 1. 1. 元胞自动机模型元胞自动机模型n元胞自动机元胞自动机(Cellular Automata，简称，简称CA)是一个是一个时间时间和和空间空间都离散的动力系统。散布在规则格网都离散的动力系统。散布在规则格网 中的每一元胞中的每一元胞取有限的离散状态，遵循同样的规则作同步更新。取有限的离散状态，遵循同样的规则作同步更新。n大量元胞通过简单的相互作用而构成动态系统的大量元胞通过简单的相互作用而构成动态系统的演化演

3、化。不。不同于一般的动力学模型，元胞自动机不是由严格定义的方同于一般的动力学模型，元胞自动机不是由严格定义的方程或函数确定，而是用一系列的程或函数确定，而是用一系列的规则规则构成。构成。n凡是满足这些规则的模型都可以算作是元胞自动机模型。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是有限多个状态，且其状态改变的规则在时间和空间上都是局部的。局部

4、的。62022-6-292.2.初等元胞自动机n初等元胞自动机是状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径r=1的一维元胞自动机。它是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取 0，1，-1，1，静止，运动 等等，重要的是S所含的符号个数，通常我们将其记为 0，1。此时，邻居集N的个数2r=2，局部映射f：S3S可记为:111(,)ttttiiiiSf SS S72022-6-29n初等元胞自动机是状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径r=1的一维元胞自动机。它是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取 0，

5、1，-1，1，静止，运动 等等，重要的是S所含的符号个数，通常我们将其记为 0，1。此时，邻居集N的个数2r=2，局部映射f：S3S可记为:111(,)ttttiiiiSf SS S2.2.初等元胞自动机82022-6-29由于只有0、1两种状态，所以函数f共有28=256种状态。t111110101100001010001 000t+101001 100S. Wolfram的初等元胞自动机的初等元胞自动机 92022-6-29nThree centuries ago science was transformed by the dramatic new idea that rules bas

6、ed 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. 详见：详见：Free onli

7、ne access:http:/ t111110 101100011010001000 t+100001110000011000011100001110000111000101101100111010001rule 1rule 2rule 3rule 4rule 184rule 255rule 256112022-6-293. 交通流的元胞自动机模型交通流的元胞自动机模型特别注意：特别注意：第第184号规则号规则车辆行驶规则为：黑色元胞表示被一辆车占据，白色表示无车，若前方格子有车，则停止。若前方为空，则前进一格。t111110101100011010001000t+1101110001992

8、年，德国学者Nagel和Schreckenberg在第184号规则提出了一维交通流CA模型，即，NS 模型（或NaSch模型）122022-6-29nNS 模型是一个随机CA交通流模型，每辆车的状态都由它的速度和位置所表示，其状态按照以下演化规则并行更新 ： na) 加速过程 nb）安全刹车过程 nc）随机慢化过程 （以随机慢化概率p） nd）位置更新nnnxxvm a x (1, 0 )nnvvmin(,1)nnnvvdmaxmin(1,)nnvvv其中：L-车辆长度7.5m1nnndxxL132022-6-29a）加速过程 b）安全刹车过程 c）随机慢化过程（以随机慢化概率p）d）位置更新

9、142022-6-29n在NS 模型的基础上，又陆续地提出了一系列一维CA交通模型，如TT、BJH、VDR、FI等模型；n双车道CA交通模型：STNS模型n机非混合CA模型： CCA模型n城市路网CA模型： BML、CTM模型Los Alamos National Laboratory： TRANSIMS (TRansportation ANalysis SIMulation System) 详见：贾斌，高自友，基于元胞自详见：贾斌，高自友，基于元胞自动机的交通系统建模与模拟，科学动机的交通系统建模与模拟，科学出版社，出版社，2007-10 152022-6-29高速公路自发形成的堵塞航拍图，

10、1975年162022-6-29随机慢化概率p=0.2；密度=13.3veh/km/lan（0.1）； 172022-6-29随机慢化概率p=0.2；密度=20veh/km/lan（0.15）； 182022-6-29随机慢化概率p=0.2；密度=27veh/km/lan（0.2）； 192022-6-29随机慢化概率p=0.2；密度=33veh/km/lan（0.25）； 202022-6-294.4.火灾逃生的元胞自动机模型火灾逃生的元胞自动机模型n（1）元胞的划分n（2）邻域空间n（3）元胞状态n（4）元胞状态变化的规则212022-6-29（1）元胞的划分n火灾的发生均是在一定区域中，

11、因此火灾逃生区域是一个二维的空间。在模型中，将所研究的二维空间按矩形方式进行均匀的网格划分，每个格点即为元胞，所有元胞共同构成了元胞空间。n在模型中，将每个元胞的大小划分为只能容纳一个人的大小，如0.4m 0.4m。这是密集人流中的典型的人员空间分配。222022-6-29（2）邻域空间n在一个给定的元胞点阵中，规定每个元胞在计算自己的下一个状态时所考察的邻域。n模拟火灾逃生的正方形网格空间下, 选择两种邻域形式。n（a）由Von. Neumann限定每个元胞只注意它四个最临近的元胞,即上、下、左、右四个邻居。n（b）由Moore邻域除了包含元胞的四个邻居外,还包含另外四个对角的次临近元胞。2

12、32022-6-29n这两种邻域的形式实际上是火灾逃生中人员的视野概念。随着人员视野的扩大,其对当前时间步运动方向的确定就可以按照下一时间步的最优选择来进行。此外,视野还可以用来模拟人员在火灾中由于烟气存在而导致的视力范围缩小等问题。242022-6-29（3）元胞状态n在元胞空间中, 每个元胞有两种状态：一是被人占据，另一种空，没有人员。在数学公式里，元胞的状态数就是Si 可能的取值数，或叫做它的域。n所有元胞的状态是同时发生变化的，在时刻t+1的第i个元胞的状态是由时刻 t 的第 i个元胞以及相邻的距离不超过r的 2r个元胞的状态决定的。252022-6-29n(4) 元胞状态变化的规则n元胞下一时间的状态主要有两个并行的变更阶段。第一个阶段是目标格点的选择,每个人员在本身所在格点及