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

1、元胞自动机模型元胞自动机模型 主要内容主要内容 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 3 1843 184号规则号规则 4 NS4 NS模型简介模型简介 5 BML5 BML模型简介模型简介 元胞自动机交通流模型元胞自动机交通流模型 6 6 双车道模型简介双车道模型简介 1 1 绪论绪论 1 1 绪论绪论 Stephen Wolfram. A New Kind of Science. Wolfram Media, 2002. 1 1 绪论绪论 “三个世纪以前，人们发现建立在数学方程基础上的规律三个世纪以前，人们发现建立在数学方程基础上的规律 能够用于对自然界的描述，伴随着这种新

2、观念，科学发生能够用于对自然界的描述，伴随着这种新观念，科学发生 了转变。了转变。 在此书中我的目的是将要用简单的电脑程序来表在此书中我的目的是将要用简单的电脑程序来表 达更为一般类型的规律，并在此种规律基础上建立一种新达更为一般类型的规律，并在此种规律基础上建立一种新 的科学，从而启的科学，从而启 动另一场科学变革。动另一场科学变革。”著名的物理学家、著名的物理学家、 数学家和计算机科学家数学家和计算机科学家S. Wolfram以这样的惊世之言开始以这样的惊世之言开始 了他的宏篇巨著了他的宏篇巨著一种新科学一种新科学。 Wolfram认为传统科学未能建立起解释宇宙复杂性的理论，认为传统科学未

3、能建立起解释宇宙复杂性的理论， 靠数学方程做不到这一点。所以他要发动一场新的科学革靠数学方程做不到这一点。所以他要发动一场新的科学革 命，革命的内容就是要用简单的电脑程序取代数学方程。命，革命的内容就是要用简单的电脑程序取代数学方程。 Wolfram所钟情的这种简单电脑程序的核心基础就是我们所钟情的这种简单电脑程序的核心基础就是我们 将要介绍的元胞自动机。将要介绍的元胞自动机。 1 1 绪论绪论 1 1 绪论绪论 1 1 绪论绪论 元胞自动机发展历程元胞自动机发展历程 20世纪世纪50年代，年代，John von Neumann 最早提出；最早提出； (von Neumann,J.1963 (

4、von Neumann,J.1963，collected works, edited by A.H.Taub)collected works, edited by A.H.Taub) 1970年，年，John Conway 提出生命游戏提出生命游戏 (Conway, J. (1970). In M. Gardner, (Ed.), Scientific American, 223(4), pp. 120-123.) 1983年，年，Stephen Wolfram 初等元胞自动机初等元胞自动机 (Stephen Wolfram. Reviews of Modern Physics,1983,Vo

5、l.55.(Stephen Wolfram. Reviews of Modern Physics,1983,Vol.55. Stephen Wolfram. Nature,1984,Vol.311) Stephen Wolfram. Nature,1984,Vol.311) 1986年至今，理论及应用年至今，理论及应用 1 1 绪论绪论 元胞自动机自产生以来，被广泛地应用到社元胞自动机自产生以来，被广泛地应用到社 会、经济、军事和科学研究的各个领域。会、经济、军事和科学研究的各个领域。 到目前为止，其应用领域涉及生物学、到目前为止，其应用领域涉及生物学、 生生 态学、物理学、化学、交通科学、计

6、算机态学、物理学、化学、交通科学、计算机 科学、信息科学、地理、环境、社会学、科学、信息科学、地理、环境、社会学、 军事学以及复杂性科学等。军事学以及复杂性科学等。 1 1 绪论绪论 元胞自动机应用元胞自动机应用 生物学领域：生物学领域：因为元胞自动机的设计思想本身就来源于生物因为元胞自动机的设计思想本身就来源于生物 学自繁殖的现象，所以它在生物学上的应用更为自然而广泛学自繁殖的现象，所以它在生物学上的应用更为自然而广泛 。 例如元胞自动机用于例如元胞自动机用于肿瘤细胞的增长机理和过程模拟肿瘤细胞的增长机理和过程模拟、人人 类大脑的机理探索类大脑的机理探索、爱滋病病毒爱滋病病毒HIV的感染过程

7、的感染过程、自组织自组织、 自繁殖自繁殖等生命现象的研究以及最新流行的等生命现象的研究以及最新流行的克隆克隆 (clone)技术技术 的研究等。另外，的研究等。另外， 元胞自动机还可以用来模拟植物的生长过元胞自动机还可以用来模拟植物的生长过 程以及贝壳上的色素沉积图案。程以及贝壳上的色素沉积图案。 1 1 绪论绪论 元胞自动机应用元胞自动机应用 生态学领域：生态学领域：元胞自动机被用于兔子元胞自动机被用于兔子-草，鲨鱼草，鲨鱼-小鱼等生态小鱼等生态 系统动态变化过程的模拟，展示出令人满意的动态效果系统动态变化过程的模拟，展示出令人满意的动态效果;元元 胞自动机还成功地应用于蚂蚁的行走路径，大雁

8、、鱼类洄游胞自动机还成功地应用于蚂蚁的行走路径，大雁、鱼类洄游 等动物的群体行为的模拟；另外，基于元胞自动机模型的生等动物的群体行为的模拟；另外，基于元胞自动机模型的生 物群落的扩散模拟也是当前的一个应用热点。物群落的扩散模拟也是当前的一个应用热点。 1 1 绪论绪论 元胞自动机应用元胞自动机应用 物理学领域：物理学领域：在元胞自动机基础之上发展出来的格子气自动在元胞自动机基础之上发展出来的格子气自动 机机(LGA)和格子和格子-波尔兹曼方法波尔兹曼方法(LBM)在计算流体领域获得在计算流体领域获得 了了 巨大的成功。不仅能够解决传统流体力学计算方法所能巨大的成功。不仅能够解决传统流体力学计算

9、方法所能 解决的绝大多数问题，并且在多孔介质、解决的绝大多数问题，并且在多孔介质、 多相流、微小尺多相流、微小尺 度方面具有其独特的优越性。格子度方面具有其独特的优越性。格子-波尔兹曼方法还被成功波尔兹曼方法还被成功 地应用于磁场、电场、热扩散和热传导的模拟。另外，元地应用于磁场、电场、热扩散和热传导的模拟。另外，元 胞自动机还被用来模拟胞自动机还被用来模拟雪花等枝晶的形成雪花等枝晶的形成、液态金属材料液态金属材料 的凝固结晶的凝固结晶过程以及过程以及颗粒材料的垮塌现象颗粒材料的垮塌现象等。等。 1 1 绪论绪论 元胞自动机应用元胞自动机应用 交通科学领域：交通科学领域：1986年，年，M.

10、Cremer和和J. Ludwig初次将元胞初次将元胞 自动机运用到车辆交通的研究中。随后，元胞自动机在车自动机运用到车辆交通的研究中。随后，元胞自动机在车 辆辆 交通中的应用主要沿着两条主线展开：对城市道路交通交通中的应用主要沿着两条主线展开：对城市道路交通 流的研究，以流的研究，以Nagel-Schreckenberg模型模型为代表为代表;对城市对城市 交通网络交通网络 的研究，以的研究，以BML模型模型为代表。另外，为代表。另外，80年代以来年代以来 ，计算机水平日新月异的发展为元胞自动机的，计算机水平日新月异的发展为元胞自动机的 应用提供了应用提供了 强有力的支持。因此，在进入上个世纪

11、强有力的支持。因此，在进入上个世纪90年代后，元胞自年代后，元胞自 动机在交通流理论研究领域中得到了广泛的应用。动机在交通流理论研究领域中得到了广泛的应用。 1 1 绪论绪论 元胞自动机应用元胞自动机应用 计算机科学与信息学领域：计算机科学与信息学领域：元胞自动机的逻辑思维方法为并元胞自动机的逻辑思维方法为并 行机的发展提供了另一个理论框架。行机的发展提供了另一个理论框架。20世纪世纪80年代，年代，T. Toffoli和和N.H. Margolus 制造出第一台制造出第一台通用元胞自动机计通用元胞自动机计 算机算机CAM6，其性能可与当时的巨型计算机相比拟，并且，其性能可与当时的巨型计算机相

12、比拟，并且 其图形显示功能明显优于其他类型的计算机。元胞自动机其图形显示功能明显优于其他类型的计算机。元胞自动机 还被用来研究还被用来研究信息的保存、传递、扩散信息的保存、传递、扩散的过程。除此之外的过程。除此之外 ，元胞自动机在图像处理和模式识别中也体现出了其独到，元胞自动机在图像处理和模式识别中也体现出了其独到 的优势的优势 。 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 元胞自动机的构成示意图 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 元胞 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 元胞状态 2 2

13、元胞自动机的定义和构成元胞自动机的定义和构成 元胞空间 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 理论上，它可以是任意维数的欧几里德空间规则划 分。常用的元胞自动机一般是一维和二维的。 二维元胞自动机通常有三种划分方式 三角形 正方形 正六边形 一维元胞自动机的元胞空间只有一种划分 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 二维元胞自动机的三种网格划分 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 网格 类型 优点缺点 三角形 拥有相对较少的邻居数目，易 于处理复杂边界 在计算机的表达与 显示不方便，需要 转换为四方网格。 正方形 直观而简单，而且特别适合于 在

14、现有计算机环境下进行表达 显示 不能较好地模拟各 向同性的现象 正六 边形 能较好地模拟各向同性的现象， 因此，模型能更加自然而真实 在表达显示上较为 困难、复杂 三类网格划分的优缺点对比 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 理论上，元胞空间是无限的；实际应用中无法达到 这一理想条件。常用的边界条件如下： 周期型 定值型 绝热型 反射型 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 周期型边界条件（periodic boundary） 定义：周期型是指相对边界连接起来的元胞空间 对一维空间，首尾相接形成一个圆环 对二维空间，上下相接，左右相接，而形成 一个拓扑圆环面，

15、形似车胎或甜点圈 周期型空间与无限空间最为接近，因而在理 论探讨时，常以此类空间作为试验。 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 定值型边界条件(Constant Boundary) 定义：所有边界外元胞均取某一固定常量 绝热型边界条件(Adiabatic Boundary) 定义：在指边界外邻居元胞的状态始终和边界元胞 的状态保持一致，即具有状态的零梯度。 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 定义：在边界外邻居的元胞状态是以边界元胞为轴 的镜面反射。 反射型边界条件(Constant Boundary) 2 2 元胞自动机的定义和构成元胞自动机的定义和构成

16、(Configuration) 定义：构形是在某个时刻，在 元胞空间上所有元胞状态的空 间分布组合。在数学上，它通 常可以表示为一个多维的整数 矩阵。 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 邻居(Neighbor) 定义如下： 2 ),( , 1),(ZvvvvvvvvvN iyixoyiyoxixiyixiNeumann iyix vv , 分别表示邻居元胞的行坐标和列坐标： oyox vv , 分别表示中心元胞的行坐标和列坐标： 邻居的数目d2 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 邻居(Neighbor) 定义如下： 2 ),( , 1, 1),(Zvvv

17、vandvvvvvN iyixoyiyoxixiyixiMoore 邻居的数目 13 d 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 邻居(Neighbor) 定义如下： 2 ),( , 2, 2),(ZvvvvandvvvvvN iyixoyiyoxixiyixiMoore 邻居的数目112 d r 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 邻居(Neighbor) 与前几种邻居的本质区别：以22的元胞块为单元进 行处理，而不是向前面几种，对每个元胞分别处理。 主要应用领域：格子气流体，颗粒流等 MargolusMargolus邻居的表现形式和几个演化规则邻居的表现形式

18、和几个演化规则 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 规则(Rule) t N t i t i SSfSf,: 1 称f为元胞自动机的局部映射或局部规则 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 时间 若时间步长为dt=1dt=1,t=0t=0为初始时刻，则t+1 就为下一个时刻。 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 根据上面对元胞自动机的组成分析，我们可以更加深 入地理解元胞自动机的概念。 可以将元胞自动机概括 为一个用数学符号来表示的四元组。 A:A:代表一个元胞自动机系统；L Ld d：代表元 胞空间；d d：为空间维数；S S：是元胞有限

19、的离散的状态集合；N N：表示邻域内所有元 胞的组合（包括中心元胞在内）；f f：是局 部转换函数，也就是规则。 fNSLA d , 2 2 元胞自动机的定义和构成元胞自动机的定义和构成 l 19861986年，年，CremerCremer和和LudwigLudwig初次将元胞自动机运初次将元胞自动机运 用到车辆交通的研究中。用到车辆交通的研究中。 3 1843 184号规则号规则 184184号模型号模型 道路被划分为等距格子，每个格点表示一个元胞；道路被划分为等距格子，每个格点表示一个元胞； 某个时刻，元胞或者是空的，或者被一辆车占据；某个时刻，元胞或者是空的，或者被一辆车占据； 所有车辆

20、的行进方向都是一致的（如向右）；所有车辆的行进方向都是一致的（如向右）； 在每一个时间步内：若第在每一个时间步内：若第n n辆车的前方元胞是空的，则该车辆车的前方元胞是空的，则该车 可以向前行驶一步；可以向前行驶一步； 若前面的元胞被另一辆车若前面的元胞被另一辆车n+1n+1所占据，即使第所占据，即使第n+1n+1辆车在本辆车在本 时间步内离开此元胞，第时间步内离开此元胞，第n n辆车也停在原地不动；辆车也停在原地不动； 整个系统采用周期性边界条件以确保车辆数守恒。整个系统采用周期性边界条件以确保车辆数守恒。 3 1843 184号规则号规则 1 0 001110 111 110 101 10

21、0 011 010 001 000 t t+1 0 0 1 5 0 6 1 7 1 4 1 3 0 2 1 1 1842 7 0 i i i R Rule 184： 3 1843 184号规则号规则 t t+1 t+2 23+24+25+27=184 3 1843 184号规则号规则 作为对184号规则的推广，Nagel和Schreckberg在 1992年提出了一个模拟车辆交通的元胞自动机模型， 即NS模型（也有人称它为NaSch模型）。 时间、空间和车辆速度都被整数离散化 道路被划分为等距离的离散的格子，即元胞 每个元胞或者是空的，或者被一辆车所占据 车辆的速度可以在（0 0VmaxVma

22、x）之间取值 4 NS4 NS模型模型 在时刻t到时刻t+1的过程中按照下面的规则进 行更新： 4 NS4 NS模型模型 在时刻t到时刻t+1的过程中按照下面的规则进 行更新： 4 NS4 NS模型模型 更新过程图示： 4 NS4 NS模型模型 max 2v 更新过程图示： 4 NS4 NS模型模型 max 2v 更新过程图示： 4 NS4 NS模型模型 max 2v 更新过程图示： 4 NS4 NS模型模型 max 2v 边界条件边界条件 周期性边界条件周期性边界条件 在每次更新结束后，我们要监测道路上头车的位置在每次更新结束后，我们要监测道路上头车的位置X_lead，如果，如果 X_lea

23、dL_road，那么这两车将从道路的另一端进入系统，变为道，那么这两车将从道路的另一端进入系统，变为道 路上的尾车，并且路上的尾车，并且X_lead = X_lead-L_road, V_last= V_lead。 开口边界条件开口边界条件 假设道路最左边的元胞对应于假设道路最左边的元胞对应于X=1，并且道路的入口端包含，并且道路的入口端包含V_max个个 元胞，也就是说，车辆可以从元胞元胞，也就是说，车辆可以从元胞 (1, 2, V_max)进入到道路中。进入到道路中。 在在t t+1时刻，当道路上的车辆更新完成后，监测道路上的头车和时刻，当道路上的车辆更新完成后，监测道路上的头车和 尾车的

24、位置尾车的位置X_lead和和X_last。如果。如果X_lastV_max，则一辆速度为，则一辆速度为 V_max的车将以概率的车将以概率 进入元胞进入元胞minX_last-V_max, V_max。在道路。在道路 的出口处，如果的出口处，如果X_leadL_road，那么道路上的头车以概率，那么道路上的头车以概率b b驶出路驶出路 段，而紧跟其后的第二辆车成为新的头车。段，而紧跟其后的第二辆车成为新的头车。 4 NS4 NS模型模型 与与184号模型相比，号模型相比，NS模型的主要改进之处是引入了慢化模型的主要改进之处是引入了慢化 概率和最大车速不再是概率和最大车速不再是1。 NS模型虽

25、然具有十分简单的形式，但却可以描述一些实际模型虽然具有十分简单的形式，但却可以描述一些实际 交通现象。比如交通现象。比如NS模型可以模拟出自发产生的堵塞现象以模型可以模拟出自发产生的堵塞现象以 及拥挤交通情况下的时走时停波等。及拥挤交通情况下的时走时停波等。 4 NS4 NS模型模型 堵塞的形成堵塞的形成 4 NS4 NS模型模型 时走时停波 4 NS4 NS模型模型 模拟结果： d=0.05 ,p=0.3 4 NS4 NS模型模型 模拟结果： d=0.1 ,p=0.3 4 NS4 NS模型模型 模拟结果： d=0.2 ,p=0.3 4 NS4 NS模型模型 模拟结果： d=0.4 ,p=0.

26、3 4 NS4 NS模型模型 模拟结果： d=0.8,p=0.3 4 NS4 NS模型模型 模拟结果： d=0.2，p=0 4 NS4 NS模型模型 NS模型的衍生和发展模型的衍生和发展 以以NS模型为基础，研究者主要做了以下三个方面的工作模型为基础，研究者主要做了以下三个方面的工作 理论方面理论方面 为了能够模拟出交通实测中的各种现象，他们提出了为了能够模拟出交通实测中的各种现象，他们提出了 各种各样的改进模型。如通过改进慢化规则，提出慢各种各样的改进模型。如通过改进慢化规则，提出慢 启动模型，巡航控制极限启动模型，巡航控制极限(Cruise Control Limit)模型，模型， 密度相

27、关的慢启动概率模型；通过改进加速规则，提密度相关的慢启动概率模型；通过改进加速规则，提 出出Fukui-Ishibashi(FI)模型；以及考虑前车速度效应的模型；以及考虑前车速度效应的 模型，三相交通状态模型，舒适驾驶模型等等模型，三相交通状态模型，舒适驾驶模型等等 。 4 NS4 NS模型模型 NS模型的衍生和发展模型的衍生和发展 理论方面理论方面 他们对元胞自动机模型他们对元胞自动机模型(主要是主要是NS模型及模型及FI模模 型型)做了相关的解析分析做了相关的解析分析(主要是平均场分析主要是平均场分析)， 加深了人们对元胞自动机模型的理解。加深了人们对元胞自动机模型的理解。 引入换道规则

28、用来模拟多车道可以超车的情引入换道规则用来模拟多车道可以超车的情 况，考察了双向交通情况况，考察了双向交通情况. 4 NS4 NS模型模型 NSNS模型的衍生和发展模型的衍生和发展 应用方面应用方面 利用利用NSNS模型对大型交通系统的模拟近年来取模型对大型交通系统的模拟近年来取 得了可喜的进展。到目前，得了可喜的进展。到目前，NSNS模型已经应用模型已经应用 于美国城市智能交通项目于美国城市智能交通项目TRANSIMSTRANSIMS，杜伊斯，杜伊斯 堡的内城交通，达拉斯堡的内城交通，达拉斯/ /福斯福斯- -华斯地区的交华斯地区的交 通规划，以及北莱茵通规划，以及北莱茵- -魏斯特伐利亚地

29、区的交魏斯特伐利亚地区的交 通公路网中。通公路网中。 4 NS4 NS模型模型 NSNS模型及其衍生和发展模型及其衍生和发展 介于理论和应用之间介于理论和应用之间 利用利用NSNS模型操作灵活简单易行的特点，考察了各模型操作灵活简单易行的特点，考察了各 种交通瓶颈对交通的影响。一方面发现了一些新种交通瓶颈对交通的影响。一方面发现了一些新 的物理现象，另一方面又为交通工程建设及交通的物理现象，另一方面又为交通工程建设及交通 管理规则的制定提供了合理建议和科学依据。管理规则的制定提供了合理建议和科学依据。 4 NS4 NS模型模型 http:/ Applet.html

30、/mm/traffic/ca.html http:/bolay.de/kai/RoadApplet/ http:/smtca.dyns.cx/ 4 NS4 NS模型模型 BML模型模型 1992年，年，Biham, Middleton, Levine提出了第一个二提出了第一个二 维交通流元胞自动机模型。维交通流元胞自动机模型。 模型定义于一个模型定义于一个NN的方形格点的网络上；的方形格点的网络上； 每一个格点具有三种状态：每一个格点具有三种状态： 1）没有车辆；）没有车辆；2）被一辆向北行驶的车辆占据被一辆向北行驶的车辆占据() ；3）被被 一辆向东行驶的车辆占据（一辆向东行驶的车辆占据（）； 在奇数时间步，按在奇数时间步，按184号规则并行更新号规则