第十一章 元胞自动机理论

1 2020 4 18 第十一章元胞自动机理论及其应用 2 2020 4 18 参考文献 StephenWolfram ANewKindofScience WolframMedia Inc 2002高原等 细胞自动机的多重分形特征和动力学根源 西北地震学报 1995 4何越磊 铁路选线中的元胞自动机模型 兰州交通大学学报 2004 01 3 2020 4 18 1 元胞自动机的定义2 初等元胞自动机3 交通流的元胞自动机模型4 火灾逃生的元胞自动机模型 4 2020 4 18 典型应用 交通流模拟火灾逃生 人员疏散模型森林火灾模型城市 农村土地利用演化模拟社会学 生物学 生态学 信息科学 计算机科学 数理化 5 2020 4 18 1 元胞自动机模型元胞自动机 CellularAutomata 简称CA 是一个时间和空间都离散的动力系统 散布在规则格网中的每一元胞取有限的离散状态 遵循同样的规则作同步更新 大量元胞通过简单的相互作用而构成动态系统的演化 不同于一般的动力学模型 元胞自动机不是由严格定义的方程或函数确定 而是用一系列的规则构成 凡是满足这些规则的模型都可以算作是元胞自动机模型 因此 元胞自动机是一类模型的总称 或者说是一个方法框架 其特点是时间 空间 状态都离散 每个变量只取有限多个状态 且其状态改变的规则在时间和空间上都是局部的 6 2020 4 18 2 初等元胞自动机 初等元胞自动机是状态集S只有两个元素 s1 s2 即状态个数k 2 邻居半径r 1的一维元胞自动机 它是最简单的元胞自动机模型 由于在S中具体采用什么符号并不重要 它可取 0 1 1 1 静止 运动 等等 重要的是S所含的符号个数 通常我们将其记为 0 1 此时 邻居集N的个数2 r 2 局部映射f S3 S可记为 7 2020 4 18 初等元胞自动机是状态集S只有两个元素 s1 s2 即状态个数k 2 邻居半径r 1的一维元胞自动机 它是最简单的元胞自动机模型 由于在S中具体采用什么符号并不重要 它可取 0 1 1 1 静止 运动 等等 重要的是S所含的符号个数 通常我们将其记为 0 1 此时 邻居集N的个数2 r 2 局部映射f S3 S可记为 2 初等元胞自动机 8 2020 4 18 由于只有0 1两种状态 所以函数f共有28 256种状态 S Wolfram的初等元胞自动机 9 2020 4 18 Threecenturiesagosciencewastransformedbythedramaticnewideathatrulesbasedonmathematicalequationscouldbeusedtodescribethenaturalworld Mypurposeinthisbookistoinitiateanothersuchtransformation andtointroduceanewkindofsciencethatisbasedonthemuchmoregeneraltypesofrulesthatcanbeembodiedinsimplecomputerprograms 详见 Freeonlineaccess 10 2020 4 18 256种初等CA规则 对给定初值及规则f 可通过计算机得到N步以后的演化结果 11 2020 4 18 3 交通流的元胞自动机模型特别注意 第184号规则车辆行驶规则为 黑色元胞表示被一辆车占据 白色表示无车 若前方格子有车 则停止 若前方为空 则前进一格 1992年 德国学者Nagel和Schreckenberg在第184号规则提出了一维交通流CA模型 即 NS模型 或NaSch模型 12 2020 4 18 NS模型是一个随机CA交通流模型 每辆车的状态都由它的速度和位置所表示 其状态按照以下演化规则并行更新 a 加速过程b 安全刹车过程c 随机慢化过程 以随机慢化概率p d 位置更新 其中 L 车辆长度 7 5m 13 2020 4 18 a 加速过程b 安全刹车过程c 随机慢化过程 以随机慢化概率p d 位置更新 14 2020 4 18 在NS模型的基础上 又陆续地提出了一系列一维CA交通模型 如TT BJH VDR FI等模型 双车道CA交通模型 STNS模型机非混合CA模型 CCA模型城市路网CA模型 BML CTM模型 LosAlamosNationalLaboratory TRANSIMS TRansportationANalysisSIMulationSystem 15 2020 4 18 高速公路自发形成的堵塞 航拍图 1975年 16 2020 4 18 随机慢化概率p 0 2 密度 13 3veh km lan 0 1 17 2020 4 18 随机慢化概率p 0 2 密度 20veh km lan 0 15 18 2020 4 18 随机慢化概率p 0 2 密度 27veh km lan 0 2 19 2020 4 18 随机慢化概率p 0 2 密度 33veh km lan 0 25 20 2020 4 18 4 火灾逃生的元胞自动机模型 1 元胞的划分 2 邻域空间 3 元胞状态 4 元胞状态变化的规则 21 2020 4 18 1 元胞的划分火灾的发生均是在一定区域中 因此火灾逃生区域是一个二维的空间 在模型中 将所研究的二维空间按矩形方式进行均匀的网格划分 每个格点即为元胞 所有元胞共同构成了元胞空间 在模型中 将每个元胞的大小划分为只能容纳一个人的大小 如0 4m 0 4m 这是密集人流中的典型的人员空间分配 22 2020 4 18 2 邻域空间在一个给定的元胞点阵中 规定每个元胞在计算自己的下一个状态时所考察的邻域 模拟火灾逃生的正方形网格空间下 选择两种邻域形式 a 由Von Neumann限定每个元胞只注意它四个最临近的元胞 即上 下 左 右四个邻居 b 由Moore邻域除了包含元胞的四个邻居外 还包含另外四个对角的次临近元胞 23 2020 4 18 这两种邻域的形式实际上是火灾逃生中人员的视野概念 随着人员视野的扩大 其对当前时间步运动方向的确定就可以按照下一时间步的最优选择来进行 此外 视野还可以用来模拟人员在火灾中由于烟气存在而导致的视力范围缩小等问题 24 2020 4 18 3 元胞状态在元胞空间中 每个元胞有两种状态 一是被人占据 另一种空 没有人员 在数学公式里 元胞的状态数就是Si可能的取值数 或叫做它的域 所有元胞的状态是同时发生变化的 在时刻t 1的第i个元胞的状态是由时刻t的第i个元胞以及相邻的距离不超过r的2r个元胞的状态决定的 25 2020 4 18 4 元胞状态变化的规则元胞下一时间的状态主要有两个并行的变更阶段 第一个阶段是目标格点的选择 每个人员在本身所在格点及相邻视野范围内格点中根据自己的 危险度图 选择一个空的 危险度最低的格点作为