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

元胞自动机模型主讲人：李新刚办公地点：8710（51684936）Email:[e-mail]•主要内容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元胞自动机的定义和构成•元胞空间元胞在空间中分布的空间格点的集合就是元胞空间。A.元胞空间的几何划分B.元胞空间的边界条件2元胞自动机的定义和构成A.元胞空间的几何划分理论上，它可以是任意维数的欧几里德空间规则划分。常用的元胞自动机一般是一维和二维的。•二维元胞自动机通常有三种划分方式三角形正方形正六边形•一维元胞自动机的元胞空间只有一种划分2元胞自动机的定义和构成二维元胞自动机的三种网格划分2元胞自动机的定义和构成网格类型优点缺点三角形拥有相对较少的邻居数目，易于处理复杂边界在计算机的表达与显示不方便，需要转换为四方网格。正方形直观而简单，而且特别适合于在现有计算机环境下进行表达显示不能较好地模拟各向同性的现象正六边形能较好地模拟各向同性的现象，因此，模型能更加自然而真实在表达显示上较为困难、复杂三类网格划分的优缺点对比2元胞自动机的定义和构成B.元胞空间边界条件理论上，元胞空间是无限的；实际应用中无法达到这一理想条件。常用的边界条件如下：•周期型•定值型•绝热型•反射型2元胞自动机的定义和构成B.元胞空间边界条件•周期型边界条件（periodicboundary）定义：周期型是指相对边界连接起来的元胞空间对一维空间，首尾相接形成一个圆环对二维空间，上下相接，左右相接，而形成一个拓扑圆环面，形似车胎或甜点圈周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间作为试验。2元胞自动机的定义和构成B.元胞空间边界条件•定值型边界条件(ConstantBoundary)定义：所有边界外元胞均取某一固定常量•绝热型边界条件(AdiabaticBoundary)定义：在指边界外邻居元胞的状态始终和边界元胞的状态保持一致，即具有状态的零梯度。2元胞自动机的定义和构成定义：在边界外邻居的元胞状态是以边界元胞为轴的镜面反射。B.元胞空间边界条件•反射型边界条件(ConstantBoundary)2元胞自动机的定义和构成C.构形(Configuration)定义：构形是在某个时刻，在元胞空间上所有元胞状态的空间分布组合。在数学上，它通常可以表示为一个多维的整数矩阵。2元胞自动机的定义和构成•邻居(Neighbor)a)冯-诺依曼(Von.Neumann)型定义如下：2),(,1),(ZvvvvvvvvvNiyixoyiyoxixiyixiNeumanniyixvv,分别表示邻居元胞的行坐标和列坐标：oyoxvv,分别表示中心元胞的行坐标和列坐标：邻居的数目＝d22元胞自动机的定义和构成•邻居(Neighbor)b)摩尔(Moore)型定义如下：2),(,1,1),(ZvvvvandvvvvvNiyixoyiyoxixiyixiMoore邻居的数目＝13d2元胞自动机的定义和构成•邻居(Neighbor)c)扩展的摩尔(Moore)型定义如下：2),(,2,2),(ZvvvvandvvvvvNiyixoyiyoxixiyixiMoore邻居的数目＝112dr2元胞自动机的定义和构成•邻居(Neighbor)d)马哥勒斯(Margolus)型与前几种邻居的本质区别：以2×2的元胞块为单元进行处理，而不是向前面几种，对每个元胞分别处理。主要应用领域：格子气流体，颗粒流等Margolus邻居的表现形式和几个演化规则2元胞自动机的定义和构成•规则(Rule)根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。tNtitiSSfSf,:1称f为元胞自动机的局部映射或局部规则2元胞自动机的定义和构成•时间元胞自动机中的时间是离散的，是一系列的整数值，是一个无量纲的整数。若时间步长为dt=1,t=0为初始时刻，则t+1就为下一个时刻。2元胞自动机的定义和构成•根据上面对元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的概念。可以将元胞自动机概括为一个用数学符号来表示的四元组。A:代表一个元胞自动机系统；Ld：代表元胞空间；d：为空间维数；S：是元胞有限的离散的状态集合；N：表示邻域内所有元胞的组合（包括中心元胞在内）；f：是局部转换函数，也就是规则。fNSLAd,,,2元胞自动机的定义和构成1986年，Cremer和Ludwig初次将元胞自动机运用到车辆交通的研究中。交通流的元胞自动机模型大致可分为两大类：研究高速公路交通的模型（以NS模型为代表）；研究城市网络交通的模型（以BML模型为代表）这两类模型是以Wolfram命名的184号模型为基础发展而来的。3184号规则184号模型道路被划分为等距格子，每个格点表示一个元胞；某个时刻，元胞或者是空的，或者被一辆车占据；所有车辆的行进方向都是一致的（如向右）；在每一个时间步内：若第n辆车的前方元胞是空的，则该车可以向前行驶一步；若前面的元胞被另一辆车n+1所占据，即使第n+1辆车在本时间步内离开此元胞，第n辆车也停在原地不动；整个系统采用周期性边界条件以确保车辆数守恒。3184号规则10001110111110101100011010001000tt+10015061714130211184270iiiRRule184：3184号规则tt+1t+223+24+25+27=1843184号规则作为对184号规则的推广，Nagel和Schreckberg在1992年提出了一个模拟车辆交通的元胞自动机模型，即NS模型（也有人称它为NaSch模型）。时间、空间和车辆速度都被整数离散化道路被划分为等距离的离散的格子，即元胞每个元胞或者是空的，或者被一辆车所占据车辆的速度可以在（0～Vmax）之间取值4NS模型在时刻t到时刻t+1的过程中按照下面的规则进行更新：4NS模型在时刻t到时刻t+1的过程中按照下面的规则进行更新：4NS模型更新过程图示