交通流理论-元胞自动机模型

元胞自动机模型 主讲人 李新刚办公地点 8710 51684936 Email lixingang 主要内容 2元胞自动机的定义和构成 3184号规则 4NS模型简介 5BML模型简介 元胞自动机交通流模型 6双车道模型简介 1绪论 1绪论 StephenWolfram ANewKindofScience WolframMedia 2002 1绪论 三个世纪以前 人们发现建立在数学方程基础上的规律能够用于对自然界的描述 伴随着这种新观念 科学发生了转变 在此书中我的目的是将要用简单的电脑程序来表达更为一般类型的规律 并在此种规律基础上建立一种新的科学 从而启动另一场科学变革 著名的物理学家 数学家和计算机科学家S Wolfram以这样的惊世之言开始了他的宏篇巨著 一种新科学 Wolfram认为传统科学未能建立起解释宇宙复杂性的理论 靠数学方程做不到这一点 所以他要发动一场新的科学革命 革命的内容就是要用简单的电脑程序取代数学方程 Wolfram所钟情的这种简单电脑程序的核心基础就是我们将要介绍的元胞自动机 元胞自动机 CellularAutomata 简称CA 实质上是定义在一个由具有离散 有限状态的元胞组成的元胞空间上 并按照一定的局部规则 在离散的时间维度上演化的动力学系统 1绪论 在元胞自动机中 空间被一定形式的规则网格分割为许多单元 这些规则网格中的每一个单元都称为元胞 cell 并且它只能在有限的离散状态集中取值 所有的元胞遵循同样的作用规则 依据确定的局部规则进行更新 大量的元胞通过简单的相互作用而构成动态系统的演化 1绪论 1绪论 元胞自动机发展历程20世纪50年代 JohnvonNeumann最早提出 vonNeumann J 1963 collectedworks editedbyA H Taub 1970年 JohnConway提出生命游戏 Conway J 1970 InM Gardner Ed ScientificAmerican 223 4 pp 120 123 1983年 StephenWolfram初等元胞自动机 StephenWolfram ReviewsofModernPhysics 1983 Vol 55 StephenWolfram Nature 1984 Vol 311 1986年至今 理论及应用 1绪论 元胞自动机自产生以来 被广泛地应用到社会 经济 军事和科学研究的各个领域 到目前为止 其应用领域涉及生物学 生态学 物理学 化学 交通科学 计算机科学 信息科学 地理 环境 社会学 军事学以及复杂性科学等 1绪论 元胞自动机应用生物学领域 因为元胞自动机的设计思想本身就来源于生物学自繁殖的现象 所以它在生物学上的应用更为自然而广泛 例如元胞自动机用于肿瘤细胞的增长机理和过程模拟 人类大脑的机理探索 爱滋病病毒HIV的感染过程 自组织 自繁殖等生命现象的研究以及最新流行的克隆 clone 技术的研究等 另外 元胞自动机还可以用来模拟植物的生长过程以及贝壳上的色素沉积图案 1绪论 元胞自动机应用生态学领域 元胞自动机被用于兔子 草 鲨鱼 小鱼等生态系统动态变化过程的模拟 展示出令人满意的动态效果 元胞自动机还成功地应用于蚂蚁的行走路径 大雁 鱼类洄游等动物的群体行为的模拟 另外 基于元胞自动机模型的生物群落的扩散模拟也是当前的一个应用热点 1绪论 元胞自动机应用物理学领域 在元胞自动机基础之上发展出来的格子气自动机 LGA 和格子 波尔兹曼方法 LBM 在计算流体领域获得了巨大的成功 不仅能够解决传统流体力学计算方法所能解决的绝大多数问题 并且在多孔介质 多相流 微小尺度方面具有其独特的优越性 格子 波尔兹曼方法还被成功地应用于磁场 电场 热扩散和热传导的模拟 另外 元胞自动机还被用来模拟雪花等枝晶的形成 液态金属材料的凝固结晶过程以及颗粒材料的垮塌现象等 1绪论 元胞自动机应用交通科学领域 1986年 M Cremer和J Ludwig初次将元胞自动机运用到车辆交通的研究中 随后 元胞自动机在车辆交通中的应用主要沿着两条主线展开 对城市道路交通流的研究 以Nagel Schreckenberg模型为代表 对城市交通网络的研究 以BML模型为代表 另外 80年代以来 计算机水平日新月异的发展为元胞自动机的应用提供了强有力的支持 因此 在进入上个世纪90年代后 元胞自动机在交通流理论研究领域中得到了广泛的应用 1绪论 元胞自动机应用计算机科学与信息学领域 元胞自动机的逻辑思维方法为并行机的发展提供了另一个理论框架 20世纪80年代 T Toffoli和N H Margolus制造出第一台通用元胞自动机计算机CAM6 其性能可与当时的巨型计算机相比拟 并且其图形显示功能明显优于其他类型的计算机 元胞自动机还被用来研究信息的保存 传递 扩散的过程 除此之外 元胞自动机在图像处理和模式识别中也体现出了其独到的优势 元胞自动机 CellularAutomata 简称CA 实质上是定义在一个由具有离散 有限状态的元胞组成的元胞空间上 并按照一定的局部规则 在离散的时间维度上演化的动力学系统 元胞自动机的定义 2元胞自动机的定义和构成 2元胞自动机的定义和构成 元胞自动机的构成 元胞自动机最基本的组成 元胞 元胞空间 邻居及规则四部分 另外 还应包含状态和时间 可以视为由一个元胞空间和定义于该空间的变换函数所组成 元胞自动机的构成示意图 2元胞自动机的定义和构成 元胞 元胞又可称为单元 细胞或基元 是元胞自动机的最基本的组成部分 元胞分布在离散的一维 二维或多维欧几里德空间的晶格点上 2元胞自动机的定义和构成 元胞状态 元胞的状态可以是二进制形式 如 0 1 生 死 黑 白 等 也可以在一个有限整数集内S内取值 如交通领域的CA模型中 有时元胞状态可在 Vmax 1 Vmax 1 之间取值 状态参量 严格意义上的CA只能有一个状态参量 但是 在实际应用中 可以具有多个状态参量 2元胞自动机的定义和构成 元胞空间 元胞在空间中分布的空间格点的集合就是元胞空间 元胞空间的几何划分元胞空间的边界条件 2元胞自动机的定义和构成 元胞空间的几何划分 理论上 它可以是任意维数的欧几里德空间规则划分 常用的元胞自动机一般是一维和二维的 二维元胞自动机通常有三种划分方式三角形正方形正六边形 一维元胞自动机的元胞空间只有一种划分 2元胞自动机的定义和构成 二维元胞自动机的三种网格划分 2元胞自动机的定义和构成 三类网格划分的优缺点对比 2元胞自动机的定义和构成 元胞空间边界条件 理论上 元胞空间是无限的 实际应用中无法达到这一理想条件 常用的边界条件如下 周期型定值型绝热型反射型 2元胞自动机的定义和构成 元胞空间边界条件 周期型边界条件 periodicboundary 定义 周期型是指相对边界连接起来的元胞空间 对一维空间 首尾相接形成一个圆环对二维空间 上下相接 左右相接 而形成一个拓扑圆环面 形似车胎或甜点圈周期型空间与无限空间最为接近 因而在理论探讨时 常以此类空间作为试验 2元胞自动机的定义和构成 元胞空间边界条件 定值型边界条件 ConstantBoundary 定义 所有边界外元胞均取某一固定常量 绝热型边界条件 AdiabaticBoundary 定义 在指边界外邻居元胞的状态始终和边界元胞的状态保持一致 即具有状态的零梯度 2元胞自动机的定义和构成 定义 在边界外邻居的元胞状态是以边界元胞为轴的镜面反射 元胞空间边界条件 反射型边界条件 ConstantBoundary 2元胞自动机的定义和构成 构形 Configuration 定义 构形是在某个时刻 在元胞空间上所有元胞状态的空间分布组合 在数学上 它通常可以表示为一个多维的整数矩阵 2元胞自动机的定义和构成 邻居 Neighbor 冯 诺依曼 Von Neumann 型 定义如下 分别表示邻居元胞的行坐标和列坐标 分别表示中心元胞的行坐标和列坐标 邻居的数目 2元胞自动机的定义和构成 邻居 Neighbor 摩尔 Moore 型 定义如下 邻居的数目 2元胞自动机的定义和构成 邻居 Neighbor 扩展的摩尔 Moore 型 定义如下 邻居的数目 2元胞自动机的定义和构成 邻居 Neighbor 马哥勒斯 Margolus 型 与前几种邻居的本质区别 以2 2的元胞块为单元进行处理 而不是向前面几种 对每个元胞分别处理 主要应用领域 格子气流体 颗粒流等 Margolus邻居的表现形式和几个演化规则 2元胞自动机的定义和构成 规则 Rule 根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数 简单讲 就是一个状态转移函数 称f为元胞自动机的局部映射或局部规则 2元胞自动机的定义和构成 时间 元胞自动机中的时间是离散的 是一系列的整数值 是一个无量纲的整数 若时间步长为dt 1 t 0为初始时刻 则t 1就为下一个时刻 2元胞自动机的定义和构成 根据上面对元胞自动机的组成分析 我们可以更加深入地理解元胞自动机的概念 可以将元胞自动机概括为一个用数学符号来表示的四元组 A 代表一个元胞自动机系统 Ld 代表元胞空间 d 为空间维数 S 是元胞有限的离散的状态集合 N 表示邻域内所有元胞的组合 包括中心元胞在内 f 是局部转换函数 也就是规则 2元胞自动机的定义和构成 1986年 Cremer和Ludwig初次将元胞自动机运用到车辆交通的研究中 交通流的元胞自动机模型大致可分为两大类 研究高速公路交通的模型 以NS模型为代表 研究城市网络交通的模型 以BML模型为代表 这两类模型是以Wolfram命名的184号模型为基础发展而来的 3184号规则 184号模型 道路被划分为等距格子 每个格点表示一个元胞 某个时刻 元胞或者是空的 或者被一辆车占据 所有车辆的行进方向都是一致的 如向右 在每一个时间步内 若第n辆车的前方元胞是空的 则该车可以向前行驶一步 若前面的元胞被另一辆车n 1所占据 即使第n 1辆车在本时间步内离开此元胞 第n辆车也停在原地不动 整个系统采用周期性边界条件以确保车辆数守恒 3184号规则 Rule184 3184号规则 t t 1 t 2 23 24 25 27 184 3184号规则 作为对184号规则的推广 Nagel和Schreckberg在1992年提出了一个模拟车辆交通的元胞自动机模型 即NS模型 也有人称它为NaSch模型 时间 空间和车辆速度都被整数离散化 道路被划分为等距离的离散的格子 即元胞 每个元胞或者是空的 或者被一辆车所占据 车辆的速度可以在 0 Vmax 之间取值 4NS模型 在时刻t到时刻t 1的过程中按照下面的规则进行更新 4NS模型 在时刻t到时刻t 1的过程中按照下面的规则进行更新 4NS模型 更新过程图示 4NS模型 更新过程图示 4NS模型 更新过程图示 4NS模型 更新过程图示 4NS模型 边界条件 周期性边界条件在每次更新结束后 我们要监测道路上头车的位置X lead 如果X lead L road 那么这两车将从道路的另一端进入系统 变为道路上的尾车 并且X lead X lead L road V last V lead 开口边界条件假设道路最左边的元胞对应于X 1 并且道路的入口端包含V max个元胞 也就是说 车辆可以从元胞 1 2 V max 进入到道路中 在t t 1时刻 当道路上的车辆更新完成后 监测道路上的头车和尾车的位置X lead和X last 如果X last V max 则一辆速度为V max的车将以概率a进入元胞min X last V max V max 在道路的出口处 如果X lead L road 那么道路上的头车以概率b驶出路段 而紧跟其后的第二辆车成为新的头车 4NS模型 与184号模型相比 NS模型的主要改进之处是引入了慢化概率和最大车速不再是1 NS模型虽然具有十分简单的形式 但却可以描述一些实际交通现象 比如NS模型可以模拟出自发产生的堵塞现象以及拥挤交通情况下的时走时停波等 4NS模型 堵塞的形成 4NS模型 时走时停波 4NS模型 模拟结果 d 0 05 p 0 3 4NS模型 模拟结果 d 0 1 p 0 3 4NS模型 模拟结果 d 0 2 p 0 3 4NS模型 模拟结果 d 0 4 p 0 3 4NS模型 模拟结果 d 0 8 p 0 3 4NS模型 模拟结果 d 0 2 p 0 4NS模型 NS模型的衍生和发展 以NS模型为基础 研究者主要做了以下三个方面的工作 理论方面为了能够模拟出交通实测中的各种现象 他们提出了各种各样的改进模型 如通过改进慢化规则 提出慢启动模型 巡航控制极限 CruiseControlLimit 模型 密度相关的慢启动概率模型 通过改进加速规则 提出Fukui Ishibashi FI 模型 以及考虑前车速度效应的模型 三相交通状态模型 舒适驾驶模型等等 4NS模型 NS模型的衍生和发展 理论方面他们对元胞自动机模型 主要是NS模型及FI模型 做了相关的解析分析 主要是平均场分析 加深了人们对元胞自动机模型的理解 引入换道规则用来模拟多车道可以超车的情况 考察了双向交通情况 4NS模型 NS模型的衍生和发展 应用方面利用NS模型对大型交通系统的模拟近年来取得了可喜的进展 到目前 NS模型已经应用于美国城市智能交通项目TRANSIMS 杜伊斯堡的内城交通 达拉斯 福斯 华斯地区的交通规划 以及北莱茵 魏斯特伐利亚地区的交通公路网中 4NS模型 NS模型及其衍生和发展 介于理论和应用之间利用NS模型操作灵活简单易行的特点 考察了各种交通瓶颈对交通的影响 一方面发现了一些新的物理现象 另一方面又为交通工程建设及交通管理规则的制定提供了合理建议和科学依据 4NS模型 4NS模型 BML模型