元胞自动关机模型.ppt

交通系统的重要性与当前存在的问题 交通运输在社会经济中占据了越来越重要的地位 交通事故、交通拥堵以及由此带来的环境污染等问题已经成为困扰着世界各国的普遍性问题 北京市交通拥堵日趋严重 灾祸导致的交通拥堵 Nagel –Schreckenberg（NS） 模型 Nagel –Schreckenberg（NS） 模型 元胞自动机模型 采用离散的时间和空间变量，用一系列的演化规则来描述车辆间的微观相互作用，进而推出系统的动态演化规律。 交通流元胞自动机模型的一般设定: 道路被均分为若干元胞，每个元胞的大小为一个车长 (7.5 米)或更小 同一时刻，每个元胞或者为空，或者仅被一辆车占据 车辆的位置和速度都是离散的整数值，速度更新过程也被离散为以1 秒为单位的跳跃式更新 在绝大多数元胞自动机模型中，道路上车辆的速度更新是并行的，且单道上不允许超车 Nagel –Schreckenberg（NS） 模型 NS 模型是能正确模拟交通现象的最简单的模型 NS模型的更新规则如下： 1. 加速过程： vn→min(vn+1, vmax) 2. 安全刹车： vn→min(vn, dn) 3.以一定概率随机慢化： vn→max(vn-1, 0) 4.位置更新： xn→xn+vn Nagel –Schreckenberg（NS） 模型 NS 模型是能正确模拟交通现象的最简单的模型 NS模型的更新规则如下： 1. 加速过程： vn→min(vn+1, vmax) 2. 安全刹车： vn→min(vn, dn) 3.以一定概率随机慢化： vn→max(vn-1, 0) 4.位置更新： xn→xn+vn Nagel –Schreckenberg（NS） 模型 Nagel –Schreckenberg（NS） 模型 Nagel –Schreckenberg（NS） 模型 Nagel –Schreckenberg（NS） 模型 Nagel –Schreckenberg（NS） 模型 Nagel –Schreckenberg（NS） 模型 练习 1 要求：模拟计算，统计出流量-密度关系图 x p p p NS 模型的特例：最大速度为1 流量：单位时间经过右边界的车辆数（统计平均） 练习 2 更一般的NS 模型：最大速度为 2，3，…,5 要求：1.模拟计算，统计出流量-密度关系图 2.画出时空图 时空图：不同时刻的车辆空间位置图（可带速度值） 练习 3 直行成功概率0.7，换道成功概率0.3 x p p p 双道，规则类似于练习1，需要考虑换道 Lane 1 Lane 2 q q p p p * * * * * 元胞自动机模型 生命游戏 生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。 生命游戏 生命游戏 每个格子的生死遵循下面的原则： 1． 如果一个细胞周围有3个细胞为生（一个细胞周围 共有8个细胞），则该细胞为生（即该细胞若原先 为死，则转为生，若原先为生，则保持不变） 。 2． 如果一个细胞周围有2个细胞为生，则该细胞的生 死状态保持不变； 3． 在其它情况下，该细胞为死（即该细胞若原先为 生，则转为死，若原先为死，则保持不变） 生和死的迭代演化，不但取决于自己目前的状态，还取决于8个邻居目前的状态 元胞自动机的定义 元胞自动机，即Cellular Automaton(CA)，也称为细胞自动机、点格自动机、分子自动机或单元自动机。它是一种利用简单编码与仿细胞繁殖机制的非数值算法的空间分析模式。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。 不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。 元胞自动机的定义 元胞自动机的分类 按元胞空间分类 一维元胞自动机 二维元胞自动机 三维元胞自动机 多维元胞自动机 元胞自动机的应用 元胞自动机自产生以来，被广泛地应用到社会、经济、军事和科学研究的各个领域。应用领域涉及社会学、交通、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、环境、军事学等。 元胞自动机模型 1. 元胞和元胞的划分 2.元胞的状态空间 3.邻居类型 4.边界条件 5