第十一章-元胞自动机理论

12020/2/9第十一章元胞自动机理论及其应用22020/2/9参考文献：StephenWolfram，ANewKindofScience，WolframMedia,Inc.,2002高原等，细胞自动机的多重分形特征和动力学根源，西北地震学报，1995，4何越磊，铁路选线中的元胞自动机模型，兰州交通大学学报，2004/0132020/2/91.元胞自动机的定义2.初等元胞自动机3.交通流的元胞自动机模型4.火灾逃生的元胞自动机模型42020/2/9典型应用：交通流模拟火灾逃生、人员疏散模型森林火灾模型城市、农村土地利用演化模拟社会学、生物学、生态学、信息科学、计算机科学、数理化52020/2/91.元胞自动机模型元胞自动机(CellularAutomata，简称CA)是一个时间和空间都离散的动力系统。散布在规则格网中的每一元胞取有限的离散状态，遵循同样的规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的方程或函数确定，而是用一系列的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。62020/2/92.初等元胞自动机初等元胞自动机是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=1的一维元胞自动机。它是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取{0，1}，{-1，1}，{静止，运动}等等，重要的是S所含的符号个数，通常我们将其记为{0，1}。此时，邻居集N的个数2·r=2，局部映射f：S3→S可记为:111(,,)ttttiiiiSfSSS72020/2/9初等元胞自动机是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=1的一维元胞自动机。它是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取{0，1}，{-1，1}，{静止，运动}等等，重要的是S所含的符号个数，通常我们将其记为{0，1}。此时，邻居集N的个数2·r=2，局部映射f：S3→S可记为:111(,,)ttttiiiiSfSSS2.初等元胞自动机82020/2/9由于只有0、1两种状态，所以函数f共有28=256种状态。t111110101100001010001000t+101001100S.Wolfram的初等元胞自动机92020/2/9Threecenturiesagosciencewastransformedbythedramaticnewideathatrulesbasedonmathematicalequationscouldbeusedtodescribethenaturalworld.Mypurposeinthisbookistoinitiateanothersuchtransformation,andtointroduceanewkindofsciencethatisbasedonthemuchmoregeneraltypesofrulesthatcanbeembodiedinsimplecomputerprograms.详见：Freeonlineaccess:种初等CA规则对给定初值及规则f，可通过计算机得到N步以后的演化结果t111110101100011010001000t+10000…1…110000…0…110000…1…110000…1…110000…1…110001…0…110110…0…111010…0…01rule1rule2rule3rule4…rule184…rule255rule256112020/2/93.交通流的元胞自动机模型特别注意：第184号规则车辆行驶规则为：黑色元胞表示被一辆车占据，白色表示无车，若前方格子有车，则停止。若前方为空，则前进一格。t111110101100011010001000t+1101110001992年，德国学者Nagel和Schreckenberg在第184号规则提出了一维交通流CA模型，即，NS模型（或NaSch模型）122020/2/9NS模型是一个随机CA交通流模型，每辆车的状态都由它的速度和位置所表示，其状态按照以下演化规则并行更新：a)加速过程b）安全刹车过程c）随机慢化过程（以随机慢化概率p）d）位置更新nnnxxvmax(1,0)nnvvmin(,1)nnnvvdmaxmin(1,)nnvvv其中：L---车辆长度~7.5m1nnndxxL132020/2/9a）加速过程b）安全刹车过程c）随机慢化过程（以随机慢化概率p）d）位置更新142020/2/9在NS模型的基础上，又陆续地提出了一系列一维CA交通模型，如TT、BJH、VDR、FI等模型；双车道CA交通模型：STNS模型机非混合CA模型：CCA模型城市路网CA模型：BML、CTM模型LosAlamosNationalLaboratory：TRANSIMS(TRansportationANalysisSIMulationSystem)详见：贾斌，高自友，基于元胞自动机的交通系统建模与模拟，科学出版社，2007-10152020/2/9高速公路自发形成的堵塞航拍图，1975年162020/2/9随机慢化概率p=0.2；密度ρ=13.3veh/km/lan（0.1）；172020/2/9随机慢化概率p=0.2；密度ρ=20veh/km/lan（0.15）；182020/2/9随机慢化概率p=0.2；密度ρ=27veh/km/lan（0.2）；192020/2/9随机慢化概率p=0.2；密度ρ=33veh/km/lan（0.25）；202020/2/94.火灾逃生的元胞自动机模型（1）元胞的划分（2）邻域空间（3）元胞状态（4）元胞状态变化的规则212020/2/9（1）元胞的划分火灾的发生均是在一定区域中，因此火灾逃生区域是一个二维的空间。在模型中，将所研究的二维空间按矩形方式进行均匀的网格划分，每个格点即为元胞，所有元胞共同构成了元胞空间。在模型中，将每个元胞的大小划分为只能容纳一个人的大小，如0.4m×0.4m。这是密集人流中的典型的人员空间分配。222020/2/9（2）邻域空间在一个给定的元胞点阵中，规定每个元胞在计算自己的下一个状态时所考察的邻域。模拟火灾逃生的正方形网格空间下,选择两种邻域形式。（a）由Von.Neumann限定每个元胞只注意它四个最临近的元胞,即上、下、左、右四个邻居。（b）由Moore邻域除了包含元胞的四个邻居外,还包含另外四个对角的次临近元胞。232020/2/9这两种邻域的形式实际上是火灾逃生中人员的视野概念。随着人员视野的扩大,其对当前时间步运动方向的确定就可以按照下一时间步的最优选择来进行。此外,视野还可以用来模拟人员在火灾中由于烟气存在而导致的视力范围缩小等问题。242020/2/9（3）元胞状态在元胞空间中,每个元胞有两种状态：一是被人占据，另一种空，没有人员。在数学公式里，元胞的状态数就是Si可能的取值数，或叫做它的域。所有元胞的状态是同时发生变化的，在时刻t+1的第i个元胞的状态是由时刻t的第i个元胞以及相邻的距离不超过r的2r个元胞的状态决定的。252020/2/9(4)元胞状态变化的规则元胞下一时间的状态主要有两个并行的变更阶段。第一个阶段是目标格点的选择,每个人员在本身所在格点及相邻视野范围内格点中根据自己的“危险度图”选择一个空的,危险度最低的格点作为运动的目标格点。第二个阶段的是解决冲突,所有人员按第一阶段变更之后,如果进入某个格点的人数大于0,则按每人相同的概率选择一位留下,其余回到原位。这两个阶段就完成了该时间步的人员位置变更。每个人员另外附带一个与建筑物空间大小一致的网格。该网格每个格点的值代表该人员对建筑物各处危险度的认识,称之为“危险度图”。