当前位置：文档之家› 基于元胞自动机的快速路交织区交通流仿真建模

基于元胞自动机的快速路交织区交通流仿真建模

收稿日期:2009-08-15;修回日期:2009-09-24。

作者简介:熊胜辉(1982-),男,江西丰城人,硕士研究生,主要研究方向:计算机仿真、交通信息系统、控制理论; 李星毅(1969-),男,江苏镇江人,副教授,博士,主要研究方向:数据挖掘、空间数据库、交通信息系统、控制理论; 施化吉(1964-),男,江苏镇江人,教授,博士研究生,主要研究方向:数据挖掘、计算机网络与分布计算、企业应用集成。

文章编号:1001-9081(2010)02-0551-04

基于元胞自动机的快速路交织区交通流仿真建模

熊胜辉,李星毅,施化吉

(江苏大学计算机科学与通信工程学院,江苏镇江212013)

(frank .11@163.co m )

摘要:城市快速路交织区由于复杂的交通流容易造成拥塞,成为快速路交通的瓶颈。充分考虑到辅道交通流

对交织区的影响,以元胞自动机NS 模型为基础,通过设定跟车规则、换道规则,对一个包含入口匝道、出口匝道、主线车道和辅道的快速路交织区路网建立模型进行微观仿真。仿真得出交织区长度对流量、密度、速度等交通流参数的影响并给出了最优交织区长度参考值,最后用HCM 经验公式的计算结果验证了仿真模型。

关键词:元胞自动机;跟车规则;换道规则;仿真模型;交织区长度中图分类号:T P391.9 文献标志码:A

Traffic modeli ng and simulation of

express way w eavi ng area based on cell ul ar auto mata

X I ONG Sheng hu,i LI X ing y ,i SH IH ua ji

(S c h ool of Compu ter S cience and Teleco mmun i ca ti on Engineeri ng,Ji ang s u Un i v e rsit y,Zh e njiang Jiang su 212013,Ch i na )

Abstract :Comp licated traffic fl ow i n the express way weav i ng area can eas il y cause tra ffi c congesti on ,wh i ch has become the traffi c bottleneck .The m icro si m ulation about express w ay w eaving area composed o f an off ramp ,an on ra mp ,a m ain li ne

l ane and an assistant road w as m ade t hrough m ode ling ,based on Cell u l ar A uto m ata (CA )N S mode,l and w as carr i ed ou t by se tti ng car fo llo w i ng rules and l ane chang i ng rules .The si m ulati on sho w s the opti m a l re ference v al ue o f the leng t h o fw eav i ng area and the effect on traffic fl ow para m eters ,such as fl ow,density and veloc it y,and t he si m u lati on m ode lwas ve rified by the calculati on result o fHCM e m pir i ca l for m ula .

K ey words :Ce ll u lar A utoma ta (CA );car foll ow i ng ru l e ;lane chang i ng ru l e ;si m u lati on m ode ;l length o f weav i ng area

0 引言

随着交通设施建设资金投入不断增加,城市化、机动化进程迅速加快,我国城市快速路迅猛发展,已经成为联系城市各区域的重要干道。快速路交织区作为进出口车辆较多的路段,各股车流容易相互干扰,在入口匝道和出口匝道处经常造成交通拥塞,甚至将拥塞蔓延到整个基本路段,严重影响了快速路的重要功能,成为制约城市交通的一个瓶颈,因此对快速路交织区的交通流进行研究有十分重要的意义。

Ji a 等人[1]采用元胞自动机(Ce llular A utom aton ,CA )模型分析研究了匝道入口和出口附近的交通流特性。文献[2-3]采用流体动力学模型研究了交织区入匝车流和主线车道车流之间的关系。K erner 等人

[4]

采用实测数据对快速路

交织区交通流特性进行了深入分析。钟连德等人[5]利用北京、上海和广州的实测数据,重新标定了美国HC M 2000交织区的运行速度公式。文献[6]对交织区长度和车道变换频率相互关系进行研究,运用动力学理论、概率论等方法定量分析了交织区长度对车道变换产生的影响。文献[7]利用元胞自动机模型对入匝道的交通流进行了数值模拟,研究了入匝道

合流处对快速路主路交通的影响。文献[8]采用元胞自动机模型研究高速公路入匝控制问题,模拟分析了各种参数对主路和匝道交通的影响。

快速路交织区的交通流比较复杂,目前大多数学者对交织区的研究只考虑了入口匝道和出口匝道合流的影响,没有把辅路交通流考虑进去,而实际交通中在辅路与入口匝道、出口匝道的衔接处的车流存在冲突。文献[9-10]表明交通流对交织区的影响是不可忽略的辅路交通流的影响是不可忽略的,因此本文基于元胞自动机理论将快速路交织区的主线车道、匝道、辅道组成一个系统进行研究,更反应实际的交通状况。元胞自动机[11]作为一种离散性微观模型,关注交通流中个体车辆的运动状态,可以方便灵活地修改其更新规则,大量的研究成果[1-3,7-8]表明元胞自动机适合用来模拟道路交通流,便于再现和分析各种非线性交通现象。本文采用自定义的元胞自动机模型,对快速路交织区进行模拟仿真。

1 元胞自动机理论

CA 是一个时间和空间都离散的动力学系统。元胞自动机把研究对象划分成规则的网格,散布在网格中的每一个元胞取有限个离散状态,遵循相同的作用规则,依据确定的局部

规则作同步更新,大量元胞通过简单的相互作用而构成动态系统的演化。元胞自动机不同于一般的动力学模型,不是由严格定义的物理方程或函数确定,而是由一系列模型构造的规则构成,凡是满足这些规则的模型都可以算作是元胞自动机模型。因此,元胞自动机是一类模型的总称,或者说是一个

第30卷第2期

2010年2月

计算机应用

Journal o f Computer A pp licati ons

V o.l 30N o .2F eb .2010

方法框架,其特点是时间、空间、状态都离散,每个变量只取有限多个状态,且其状态改变的规则在时间和空间上都是局部的[11]。具体地说,每个元胞根据某一时刻它本身的状态及其邻域元胞的状态来决定该元胞下一时刻的状态,因此整个网格上的元胞状态进行同步变化。

基于元胞自动机的微观仿真模型大致分为单车道模型、多车道模型及城市交通模型。1992年,德国学者N ag el 和Schreckenberg 提出了一维交通流C A 模型(NS 模型)[11]。在此模型中,道路被划分为离散的元胞,每个元胞为空或被一辆车所占,车辆按照相同的演化规则来同步变化。N S 交通流模型的模拟结果能重现交通流从畅行运动到拥塞的启止波临界相变过程,适用于模拟高速公路交通流。与早期的交通流CA 模型相比,该模型的模拟结果与实际观测结果较为吻合,因此得到了普遍应用。

N S 模型源于最简单的交通流元胞自动机模型!!!CA 184模型[12],但规则更为复杂。在CA 184模型中,一条道路看作由一系列元胞组成,每个元胞的长度为1,用元胞状态表示道路上某个位置的状态。每个元胞只有两种状态(0和1),0代表此元胞上无车辆,1代表有一辆车占据该位置(这里假定一个元胞内最多只能有一辆车);定义邻居半径为1,即左右各有一个元胞作为中心元胞的邻居;对于行车规则的定义是假定汽车的速度为1,即车辆在每个时段都只能由所在元胞跳至其相邻元胞,也就是说如果汽车行驶方向上的相邻元胞内没有汽车,汽车将行驶到相邻元胞,否则汽车原地不动。

如图1所示,标有1的元胞表示有车,标有0的元胞表示无车,假设车流方向为自左向右。图1(a )~(h)定义了不同元胞状态下的演化规则,中心元胞根据它本身以及左邻居、右邻居这3个元胞的状态确定其下一时刻的状态。

图1(a)定义的规则表示中心元胞有车,左邻居有车,右邻居有车,规定中心元胞下一时刻状态为1(即有车)。图1(b)定义的规则表示中心元胞有车,左邻居有车,右邻居为空,规定中心元胞下一时刻状态为0(即无车),其余规则类似,3个元胞共有8种不同状态,共需定义如图1所示的8

种演化规则。

图1 CA 184元胞模型演化规则

2 仿真建模

本文仿真模型主要包括跟车模型和换道模型两部分。跟车模型基于一维交通流元胞自动机N S 模型[11]设定跟车规则;换道模型根据交织区不同的换道情形自定义换道规则。2.1 问题描述

本文研究的交织区结构如图2所示,交织区路网含主线车道、辅道、入口匝道、出口匝道以及主线车道右边的交织区段;本文假设主线车道、辅道上的车流方向为自左向右,入口

匝道长度为L 1,出口匝道长度为L 2,交织区长度为L w ;主线预

驶离快速路的车辆必须先换道至交织区MN ,再进入出口匝道,驶入辅道;辅道预驶入快速路的车辆,必须先通过入口匝道,进入交织区M N,再换道至主线车道。

图2 交织区示意图

将交织区各路段离散成元胞(如图3所示),本文的关键是定义合适的跟车规则和换道规则,建立仿真模型,然后通过模拟结果分析研究交织区长度对车流密度、流量、平均速度等交通流参数的影响,找出最优的交织区长度。

图3 交织区元胞结构图

2.2 跟车模型

如图3所示,将研究的交织区离散成元胞,元胞长度 X =7.5m ,并道区域由N 个元胞构成,以元胞自动机NS 模型[11]为基础,考虑交织区的交通特性,设定相跟车规则。2.2.1 跟车规则

模拟时间步长取1s ,每一时刻每个元胞或为空或被一辆车所占据。设V max 为最大车速,V n 为第n 辆车的速度,X n 为第n 辆车的位置,L n 为第n 辆车与前车之间的空元胞数。模型考虑了车辆加速、减速、随机慢化和位置更新四个过程。

第一阶段加速过程:V n ?m in (V n +1,V m ax ),只要车速未达到最大速度,车速加1。

第二阶段减速过程:如果V n >L n ,则V n ?m in (V m ax ,L n ),当前车辆的速度大于与前车的净车距时,为避免碰撞,车速降至前车的净车距。

第三阶段随机慢化:在概率p 下,V n ?m ax (V n -1,0),车辆以随机慢化概率p 速度减1,这是由于考虑到驾驶员的过度反应,随机慢化车速以增强安全性。

第四阶段位置更新:X n ?X n +V n ,车辆以新的车速更新位置。

2.2.2 边界条件及跟车冲突的解决

本文模型采用完全开放边界,即车辆到达右边界(交织区右端)时都将驶离模型。假设主线车道最大车速为V m ax 1,辅道、入口匝道、出口匝道最大车速为V m ax2;每一时间步长主线车道入口的车辆达到率为 ,入口匝道入口车辆到达率为 ,

辅道入口的车辆达到率为!;如果到达车辆因入口位置元胞被占而不能进入系统,就将其删除,这种假设与实际交通中因交织区发生堵塞车辆无法进入交织区是一致的。

出口匝道和辅道车辆在出口匝道合流处(图3的元胞K 处)容易出现跟车冲突。设主线车道的头车为m 1,位置为X m 1,辅道的头车为m 2,位置为X m 2;连接出口匝道和辅道的元胞K (如图2所示),位置为X;t 1,t 2分别为头车m 1,m 2到达元胞K 的时间。

由图3及速度路程关系,可以计算得出t 1,t 2的表达式:

t 1=X -X m 1-1

m in (V m ax1,X m 1-1,V m 1+1)

(1)

552 计算机应用第30卷

t 2=

X -X m 2-1

m i n (V m ax2,X m 2-1,V m 2+1)

(2)

若t 1>t 2,则m 2继续前行,m 1减速行驶;

若t 1

若t 1=t 2且X -X m 1#X -X m 2,则m 2继续前行,m 1减速行驶;

若t 1=t 2且X -X m 1

减速行驶。2.3

换道模型

车辆从一个车道进入其他车道时发生换道行为,本节根据交织区不同的换道情形,定义了相应的换道规则。2.3.1 换道规则

主线车道的车辆要进入辅道必须先换道到交织区车道M N,再从出口匝道进入辅道;入口匝道的车辆要想进入快速路必须先进入区域M N,再换道到主线车道。本文将每个时间步分为2个子步:

1)车辆根据是否满足换道条件平行地更换车道;

车辆像单车道一样按照跟车规则更新位置。

图4 换道示意图

1)因为辅道交通堵塞连接辅道和入口匝道的元胞J 处车

辆(如图3所示)车辆想获得者理想速度,将产生换道动机,定义换道条件如下:

gap

(3)

gap +

>gap (4)其中:gap 表示元胞J (如图3所示)处车辆与辅道上的前车的净车距,gap +表示元胞J 处车辆与入口匝道上前车的净车距,V 表示车速,V max 2表示辅道和入口匝道允许的最大车速。

上述换道条件表示位置J 的车辆在辅道达不到最大车速,且与辅道前车的空隙小于与入口匝道前车的空隙时,产生换道动机,若入口匝道空元胞数能满足换道间隙,就进行换道以获得理想车速。本文为了表述方便,把这部分车辆称为绕行车辆。辅道进入入口匝道的车辆,除了绕行车辆,其余入口匝道的车辆是以上快速路为目的,不需要满足上述条件,直接按照跟车规则运行。

2)主线车道和交织区MN 车辆的换道。主线上预进入辅道的车辆和交织区预进入快速路的车辆,在判断目标车道前车和后车是否满足安全条件,若满足则进行换道,定义换道规则如下:

gap +i

#m i n (V i +1,V m ax2)

(5)gap -i #d sa fe (6)rand ()

(7)

其中:gap i 表示第i 辆车与前车间的空元胞数,V i 表示第i 辆车的速度,V m ax 表示车辆的最大车速。gap +i 表示第i 辆车与换道目标车道前车间的空元胞数,gap -i 表示第i 辆车与目标车道后车的空元胞数。d sa fe 表示换道的安全距离,d s afe 为目标车道允许的最大车速,在主线车道d sa fe =V m ax1,在交织区d sa fe =V m ax2;rand ()为(0,1)内的随机数,p c 为主线车道的换道概率。

2.3.2 特殊换道

针对换道中可能出现的两种特殊换道情况,定义相应换

道规则如下:

1)换道过程中如果出现同一车道的前后两车都有换道需求,且它们在目标车道具有相同换道间隔,在目标车道不能满足两车同时换道情况下,规定前车优先换道。

2)主线车道和交织区段的车辆在运行到交织区末端,一直未能获得合适的换道时机,最后将停留在主线车道或者交织区的末端不停地等待换道时机,而换道条件又始终无法满足,造成死锁现象。为了避免上述死锁现象的产生,我们作如下规定:当有换道意图的车辆运动到交织区的末端还未能完成换道的,本模型强制把该车辆置于目标车道的最后一个元胞位置;若目标车道的最后一个元胞已经有车辆,则删除该换道车辆。

3 仿真结果分析

在该模型中,将各车道都划分为80个元胞,交织区路段划分为L w 个元胞,每个元胞代表7.5m,时间步长为1s 。根据交织区交通流特性[3-7],设定快速路主线车道允许的最大速度V ma x1=3元胞/时间步长(相当于实际车速81k m /h),入口匝道、出口匝道和辅道允许的最大车速V m ax2=2元胞/时间步长(相当于实际车速54km /h)。借鉴文献[2-4]的参数设置方法,本文跟车模型中的随机慢化概率p 取0.2,主线车道

车辆的换车道概率p c 取0.2。对15000个时间步进行数值模拟,前5000个时间步长作为预热,不进行统计,对后10000个时间步长统计分析,得到各交通流参数随交织区长度变化的曲线。

3.1 车流密度、出匝流量与交织区长度关系

设主线车道、入口匝道、辅道的入匝率分别为、、!,交织区常长度为L w 。模拟仿真时分别取 = =!=0.2, = =!=0.7得到图5所示的密度、流量与交织区长度的关系曲线。

图5关系曲线中,当 = =!=0.2时,交织区车各车道的入流较小,导致各车道车流密度都较小。当交织区长度为10~30元胞变化时,主线密度、交织段密度、辅道密度都呈下降趋势,出匝道流量呈上升趋势;当交织区长度为30~60元胞变化时,各车道车流密度的下降趋势越来越不明显,出匝流量也基本稳定。这是因为在交织区入流较小时,随着交织区长度的减小,交织区换道车辆的换道要求越来越迫切,上匝道车流和主线车流在交织区的相互影响更为明显,随着交织区长度增大,换道车辆都能比较顺利地完成换道,各车道车流密度都趋于稳定,出匝流量也趋于稳定,整个交织区车辆处于自由流状态。当 = =!=0.7时,交织区入流较大,交织区处于高流量状态,图5(b )各车道车辆密度曲线均高于图5(a)的密度曲线,当交织区长度在10~30元胞变化时,主线密度、交织段密度、辅道密度下降较为明显,出匝流量有所上升;当交织区长度在30~60元胞变化时,各车道的密度变化较为平缓,出匝道流量变化较小。这是因为在高流量的情况下,交织区长度越小,入口匝道和主线车道的换道车流的在交织区域的冲突就越大,车流趋于饱和状态,各车道密度迅速减小;当交织区长度增大30元胞以后,交通流冲突得到缓和,车流处于一个平稳状态,因此各车道的密度变化趋于平缓。

对图5曲线分析得出:在低流量下,主线车道、入口匝道、辅道车辆都运行通畅,各车道都处于自由流状态,交织区长度对各车道的密度和出匝流量的影响不大;在高流量下,当交织

553第2期熊胜辉等:基于元胞自动机的快速路交织区交通流仿真建模

区长度L w 小于30元胞时,主线、入口匝道、辅道的车辆密度都呈明显的下降趋势,出匝流量呈增大趋势,直到L w 大于30元胞时,各车道密度和出匝道流量变化才趋于平缓。实验结果表明随着交织区长度的增加,整个交织区的交通状况得到改善,但是当交织区长度并不是越大越好,当大到一定程度对交通流的影响并不大,由图5可以看出L w =30元胞(约225m ),

可作为最优交织区长度的参考值。

图5 流量、密度与交织区长度关系曲线

3.2 主线平均速度与交织区长度关系

模拟时分别取 = =!=0.2, = =!=0.7,交织区长度L w 分别取10,20,30,40,50,60个元胞(相当于在75~450m 取值)得到相应的主线车道平均速度关系曲线。图6中,当 = =!=0.2时,主线车道的平均速度接近最大车速,车辆运行通畅,随交织区长度增加平均速度变化不大,说明交织区长度在低下流量下对主线速度影响不明显。当 = =!=0.5和 = =!=0.7时,随着交织区长度变小,主线平均车速减小,在交织区长度较小时,主线车道的平均车速度下降趋势更为明显;交织区长度对主线车速的影响在入流概率 = =!=0.7时的影响比 = =!=0.5时更大,说明随着交织区流量的上升,主线车速对交织区长度更为敏感。图6所示的试验结果说明:当交织区区流量较小时,交织区长度对主线平均速度的影响不大;交织区流量较大时,交织区长度增大,

主线车道的平均速度得到明显增大。

图6 主线车道平均速度随交织区长度变化曲线

HC M 经验公式计算结果

[9]

表明:交织区主线速度与交

织区长度的变化基本呈线性关系。本模型的模拟结果在 = =!=0.2, = =!=0.5, = =!=0.7不同流量

下的模拟结果均反应了主线车速与交织区长度这种线性关系,与HC M 经验公式计算结果所反应速度变化关系是一致的。

3.3 模型验证

在相同的交通流条件下,分别采用本文模型与常用于微观仿真的V ISSI M 模型[10]对同一交织区进行仿真,并将仿真结果及美国HC M 经验计算公式值[9]进行比较。

实验测试的交通流条件:如图2,A !C 为1490veh /h ,B !C 为785veh /h ,A -D 为1020veh /h ,C !D 为540veh /h (注:V ISSI M 模型仿真时不含辅道)。实验中交织区长度分别取50,100,150,200,250,300,400m ,表1为交织区速度在上述各种交织区长度下,本文模型﹑V ISSI M 模型仿真所得数据及HC M 经验公式的计算值。表中相对差是指仿真数据与H C M 验公式计算值的相对差。

表1 交织区速度仿真结果比较

交织区长度/m HCM

数据

V I SS I M 速度相对差/%

本文模型

速度相对差/%5032.924.027.024.525.110039.144.513.742.89.415044.150.915.448.49.720048.257.318.753.611.225051.856.99.956.89.630054.858.66.858.77.1400

59.6

61.5

2.7

62.3

4.5

从实验结果数据比较来看,本文仿真数据的相对差除个别略大于V ISS M 外,大部分均小于V ISS I M 数据的相对差,说明本文模型在交织区仿真方面优于V ISS I M 。本文仿真数据与HC M 经验公式的计算结果相比较,大部分数据相对差别不大,都在10%以内,个别数据超过15%。在交织区长度为50m 时相对差达到25.1%,这是由于交织区长度过小时交通流处于紊乱状态。实验数据与HC M 经验公式的计算值及仿真系统V ISSI M 的仿真数据比较表明本文定义的模型用于交织区仿真是可靠的。

4 结语

充分考虑到辅道交通流对交织区的影响,本文基于元胞自动机理论对一个包含出口匝道、入口匝道、主线车道和辅道的快速路交织区建立仿真模型进行了模拟仿真。文中引入N S 模型的跟车规则,对边界条件和跟车车冲突进行修正,根据交织区不同的换道情况自定义换道规则,建立了一个能反应交织区交通流特性的仿真模型,并通过数值模拟得出交织区各车道密度、出匝流量与交织区长度的关系曲线。模拟结果表明:在交织区流量较小时,交织区长度对整个交织区的交通状况影响不大;在交织区流量较大时,交织区的车流速度和密度对交织区长度较为敏感,增加交织区长度能明显改善交织区交通状况,但是交织区不是越大越好,当交织区长度达到某个定值时,继续增加交织区长度对整个交织区交通状况影响并不大。本文给通过模拟分析找出了这个定值约为

30元胞(实际长度225m ),可作为最优交织区长度的参考值,最后通过与V ISS M 仿真结果﹑HC M 经验公式计算值的比较验证了仿真模型。

(下转第570页)

力,在系统设计过程中增加了结果的分析与验证单元。

结果分析与验证的基础是系统所具有的先验知识,我们不但知道系统应该分割为多少个语音单元,而且知道每一个语音单元的文本内容。因此,我们可以借助于这些先验知识对系统的分割结果进行正确性验证。对于中文来讲,一个汉字就是一个音节,而对于常用的英语单词则可以建立一个音节词典,记录每一个单词所对应的音节数量。

假设有效语音文件(去除开始和结束部分的空白段)的总长度用S T 表示,语音段的数量用Q 表示,第i 与第i+1个语音段的间隔时间用T i 表示,第i 个语音单元的音节总数用S i 表示,语音单元的总数量用N 表示,音节的平均发音时间用A VS t 表示,则:

AVS t =(S T -

Q-1

i=1

T i )/(

i=0

S i )

则对于任意语音单元M i (i %N ),如果其语音段的数量与音节的数量不相等,且|S i *A VS t -TP i |/T P i >0.2,则认为系

统分割存在错误,并给出相应提示。

5 实验结果

系统的测试分为不同的语音单元要求略微停顿,但无须刻意等待和正常语速两种情况,由三位录音员分别进行,测试内容采用外语教学与研究出版的英语学生用书(小学一年级起第三册)进行,该教材共有53页。测试结果如表7所示,Er1表示阈值自适应调整过程中发现语音文件错在问题而需要人工分割或者重新录音文件的数量,Er2表示通过结果验证算法发现存在问题的语音文件数量,Ers 表示对于系统的最终划分结果通过人工验证后存在划分错误的文件数。

表7 系统测试结果

项目页码数量正常语速E r1E r2E rs 不同单元略作停顿E r1Er2E rs 录音员A 521110000录音员B 521521210录音员C 521211110合计156394

0百分比

25%

2.6%1.3%2.0%1.3%

由表7可以看出,采用正常语速录音时由于经常出现不同语音单元的间隔小于同一语音单元内部不同音节间隔的情况,在自适应分割过程中即有25%的文件被提示需要人工分割,2.6%被结果验证算法检查出错误而需要人工分割,而机器自动分割部分经人工检验其准确率为98.7%。而在录音过程中,在不同语音单元间略作停顿时系统的运行情况则明显好转,在156个语音文件中,在自适应分割过程中仅有2%的文件被提示需要人工分割,而系统分割过程中仅有的2个分割错误还被结果验证算法发现,这样实际需要人工分割的数量仅仅5个,机器分割率为96.7%,且正确率100%。参考文献:

[1] LA M EL L F ,RAB I NER L R ,ROSENBERG A E,e t a l .An i m

p roved endpoi n t detector for is olat ed w ord recogn i ti on [J ].I EEE

Transactions on Acoust ,V oice ,and S ignal Processi ng ,1981,29

(8):777-785.

[2] L IQ I ,Z HENG JI N SONG ,Z HOU Q I RU,et a l .A robu st real ti m e

endpoi n t detector w i th energy nor ma li zation for ASR i n adverse envi ronm en ts [C ]//Proceed i ngs of I CASSP 2001.

Salt Lake C ity :

IEEE,2001:233-236.

[3] WU B F ,W ANG K C.Robust endpo i nt detection al gorit hm based

on the adap ti ve band parti ti on i ng s pectral entropy i n adverse environ m en ts [J ].

I EEE T ran s acti on s on Sp eec h and Audio Process i ng ,

2005,13(5):762-775.

[4] WU G D,L I N C T .W ord boundary detection w it h m el scale fre

quen cy b ank i n no i sy env i ron m en t [J ].

IEEE Transactions on

Sp eech and Aud i o Processi ng ,2000,8(5):541-554.

[5] NEMM ER E ,GIBRAN R ,M A M OUR S.Robust voi ce acti vity de

tection us i ng h i gher order st ati sti cs i n the LPC residu aldoma i n [J].I EEE T ran s acti on s on Speech and Aud i o P rocess i ng ,2001,9(3):217-231.

[6] PARSONS T W.Vo i ce and speech p rocess i ng [M ].New York:

M c G ra w H il,l 1986.

[7] RAB I NER L R ,J UANG B H.Funda m entals of s p eech recogniti on

[M ].M u rrayH il:l Prenti ceH al,l 1993.

[8] YOU C H,KOH S N ,RAHARD J A S.An i nverti b le frequen cy do

m ai n tran sfor m ation for mas k i ng based sub s p ace s peech enhance m en t[J].IEEE S i gnalP rocess i ng Letters ,2005,12(1):461-464.

(上接第554页)参考文献:

[1] JI ANG RU I ,WU QI NG SONG ,Z HU Z UO JI N .A new con ti nuum

model for traffic fl ow and nu m eri cal tests [J ].T ransportation R e search Part B :M et hodol og i ca,l 2002,36(5):405-419.

[2] LEE H Y,LEE H W,KI M D .O ri gi n of s ynchron i zed traffi c flo w on

h i ghw ay and i ts dyna m i c phas e tran siti ons[J].Phys ics Revie w Let t ers ,1998,81(5):1130-1133.

[3] H ELB I NG D ,TRE I BER M.C ri ti cal d i scu ssi on of s yn cron i zed fl ow

[J].Cooperative T ran s portati on Dyna m ics ,2002,35(1):1-24.[4] KEENER B S .Three ph ase traffic t h eory and h i ghw ay capaci ty[J].

Physica A,2004,333:379-440.

[5] 钟连德,荣建,孙小端,等.快速路交织区运行研究[J].北京

工业大学学报,2006,32(10):907-912.

[6] 张琨,裴玉龙.交织区长度对车道变换频率的影响[J ].城市交

通,2007,6(5):33-35.

[7] 雷丽,董力耘,葛红霞.基于元胞自动机模型的入口匝道合流处

交替通行控制的研究[J].物理学报,2007,56(12):6874-6880.

[8] 梅超群,黄海军,唐铁桥.高速公路入匝控制的一个元胞自动机

模型[J].物理学报,2008,57(8):4786-4793.

[9] Transportati on Res earch Board.H i ghw ay C apaci tyM anual [M ].

W ash i ngt on,DC:Nati onal Research Counci,l TRB ,2000.[10]陈小鸿,肖海峰.交织区交通特性的微观仿真研究[J ].中国公

路学,2001,14(Z1):88-92.

[11]NAGEL K ,SCHRECKENBERG M.A cell u lar au to m at on m odel f or

free w ay traffi c[J].Jou rnal of Physics ,1992,12(2):2221-2229.[12]F UKU I M ,

I SH I BASH I Y.T raffi c fl ow i n 1D cell u l ar au to m aton

m odel i nclud i ng cars m ovi ng w ith h i gh speed [J ].J ou rnal of the

Physics Societ y of Japan,1996,65(6):1868-1870.

[13]王振报,郭南,李金山.辅路对城市快速路出口交通流特性的影

响研究[J ].交通运输工程与信息学报,2008,6(1):31-37.[14]王元生.辅路有附加车道的城市快速路出口交通特性研究[D ].

北京:北京工业大学,2004.

元胞自动机(CA)代码及应用

元胞自动机(CA)代码及应用引言元胞自动机（CA）是一种用来仿真局部规则和局部联系的方法。典型的元胞自动机是定义在网格上的，每一个点上的网格代表一个元胞与一种有限的状态。变化规则适用于每一个元胞并且同时进行。典型的变化规则，决定于元胞的状态，以及其（4或8 ）邻居的状态。元胞自动机已被应用于物理模拟，生物模拟等领域。本文就一些有趣的规则，考虑如何编写有效的MATLAB的程序来实现这些元胞自动机。 MATLAB的编程考虑元胞自动机需要考虑到下列因素，下面分别说明如何用MATLAB实现这些部分。并以Conway的生命游戏机的程序为例，说明怎样实现一个元胞自动机。 ●矩阵和图像可以相互转化，所以矩阵的显示是可以真接实现的。如果矩阵 cells的所有元素只包含两种状态且矩阵Z含有零，那么用image函数来显示cat命令建的RGB图像，并且能够返回句柄。 imh = image(cat(3,cells,z,z)); set(imh, 'erasemode', 'none') axis equal axis tight ●矩阵和图像可以相互转化，所以初始条件可以是矩阵，也可以是图形。以下代码生成一个零矩阵，初始化元胞状态为零，然后使得中心十字形的元胞状态= 1。 z = zeros(n,n); cells = z; cells(n/2,.25*n:.75*n) = 1; cells(.25*n:.75*n,n/2) = 1; ●Matlab的代码应尽量简洁以减小运算量。以下程序计算了最近邻居总和，并按照CA规则进行了计算。本段Matlab代码非常灵活的表示了相邻邻居。 x = 2:n-1; y = 2:n-1; sum(x,y) = cells(x,y-1) + cells(x,y+1) + ... cells(x-1, y) + cells(x+1,y) + ... cells(x-1,y-1) + cells(x-1,y+1) + ... cells(x+1,y-1) + cells(x+1,y+1); cells = (sum==3) | (sum==2 & cells); ●加入一个简单的图形用户界面是很容易的。在下面这个例子中，应用了三个按钮和一个文本框。三个按钮，作用分别是运行，停止，程序退出按钮。文框是用来显示的仿真运算的次数。 %build the GUI %define the plot button plotbutton=uicontrol('style','pushbutton',...

交通流中的NaSch模型及MATLAB代码元胞自动机完整

元胞自动机NaSch模型及其MATLAB代码作业要求根据前面的介绍，对NaSch模型编程并进行数值模拟： ●模型参数取值：Lroad=1000，p=，Vmax=5。 ●边界条件：周期性边界。 ●数据统计：扔掉前50000个时间步，对后50000个时间步进行统计,需给出的结果。 ●基本图（流量-密度关系）：需整个密度范围内的。 ●时空图（横坐标为空间，纵坐标为时间，密度和文献中时空图保持一致, 画 500个时间步即可）。 ●指出NaSch模型的创新之处，找出NaSch模型的不足，并给出自己的改进思路。 ●? 流量计算方法：密度＝车辆数/路长；流量flux=density×V_ave。在道路的某处设置虚拟探测计算统计时间T内通过的车辆数N；流量flux=N/T。 ●? 在计算过程中可都使用无量纲的变量。 1、NaSch模型的介绍作为对184号规则的推广，Nagel和Schreckberg在1992年提出了一个模拟车辆交通的元胞自动机模型，即NaSch模型（也有人称它为NaSch模型）。 ●时间、空间和车辆速度都被整数离散化。

● 道路被划分为等距离的离散的格子，即元胞。 ● 每个元胞或者是空的，或者被一辆车所占据。 ● 车辆的速度可以在（0～Vmax ）之间取值。 2、NaSch 模型运行规则在时刻t 到时刻t+1的过程中按照下面的规则进行更新：（1）加速：),1min(max v v v n n +→ 规则（1）反映了司机倾向于以尽可能大的速度行驶的特点。（2）减速：),min(n n n d v v → 规则(2)确保车辆不会与前车发生碰撞。（3）随机慢化：以随机概率p 进行慢化，令：)0, 1-min(n n v v → 规则(3)引入随机慢化来体现驾驶员的行为差异，这样既可以反映随机加速行为，又可以反映减速过程中的过度反应行为。这一规则也是堵塞自发产生的至关重要因素。（4）位置更新：n n n v x v +→ ，车辆按照更新后的速度向前运动。其中n v ，n x 分别表示第n 辆车位置和速度；l （l ≥1）为车辆长度；11--=+n n n x x d 表示n 车和前车n+1之间空的元胞数；p 表示随机慢化概率；max v 为最大速度。 3、NaSch 模型实例根据题目要求，模型参数取值：L=1000，p=，Vmax=5，用matlab 软件进行编程，扔掉前11000个时间步，统计了之后500个时间步数据，得到如下基本图和时空图。程序简介初始化：在路段上，随机分配200个车辆，且随机速度为1-5之间。图是程序的运行图，图中，白色表示有车，黑色是元胞。

基于元胞自动机模型的城市历史文化街区的仿真

文章编号: 1673 9965(2009)01 079 05 基于元胞自动机模型的城市历史文化街区的仿真* 杨大伟1,2,黄薇3,段汉明4 (1.西安工业大学建筑工程系,西安710032;2.西安建筑科技大学建筑学院,西安710055; 3.陕西师范大学历史文化学院,西安710061; 4.西北大学城市与资源学系,西安710069) 摘要: 为了探讨当前城市规划中远期预测的科学性和准确性问题,将自组织理论与元胞自动机模型结合,在一定的时空区域,构建了一个城市增长仿真模型.将元胞自动机模型应用于西安市最具历史文化特色的区域中,形成自下而上的规划模型.元胞自动机模型对于西安回民区的空间发展城市历史文化特色街区的模拟具有一定的原真性和时效性,在时空中能反应当前的空间格局.元胞自动机在城市规划的预测中具有图式与范式结合的特点,在中长期的预测中形成符合城市规划发展战略的空间格局. 关键词: 元胞自动机;自组织;历史文化特色街区;空间演化中图号: T U984 文献标志码: A 自组织理论是当前城市复杂性研究的主要研究方向之一.自组织是相对他组织而言,即自我、本身自主地组织化、有机化,意味着一种自动的、自发性的行为,一种自下而上、由内至外的发展方式.其主要涵义可以简单概括:在大多数情况下,作用于系统的外部力量并不能直接对系统的行为产生作用,而是作为一种诱因,即引入序参量引发系统内部发生相变,系统通过这一系列的变化自发地组织起来,最终大量微观个体的随机过程表现出宏观有序的现象[1]. 20世纪40年代U lam提出元胞自动机模型(Cellular Autom at o n M odel,CA),V on N eu m ann将其用于研究自复制系统的逻辑特性,且很快用于研究自组织系统的演变过程,其中对城市系统自组织过程的模拟是焦点问题[2 9]. CA是定义在一个具有离散状态的单元(细胞)组成的离散空间上,按一定的局部规则在离散时间维演化的动力学系统.一个CA模型通常包括单元、状态、邻近范围和转换规则4要素[9],单元是其最小单位,而状态则是单元的主要属性.根据转换规则,单元可以从一个状态转换为另外一个状态,转换规则通过多重控制函数来实现. 自组织理论的提出,对于解释相对封闭,具有自身演化规律的复杂适应系统中的复杂现象和问题具有重要意义和应用前景.而CA 自下而上的研究思路,强大的复杂计算功能、固有的并行计算能力、高度动态特征以及具有空间概念等特征,使其在模拟空间复杂系统的时空演变方面具有很强的能力,在城市学研究中具有天然优势[9 15].本文将自组织理论引入CA模型,并将该模型首次应用于西安回民区这一复杂的相对独立的历史街区中,就是为了得出其在自组织的作用下,未来20年空间发展的变化模型,为城市规划的制定做出科学的预测.下面对西安回民区做一简单介绍. 西安回民区位于西安旧城中心的中西地段,东接西安历史文化遗产钟楼和北大街,西接洒金桥,南到西大街,北到莲湖路,面积约为93.4公顷,人口约为77600人,在此居住的居民中有43.6%以第29卷第1期西安工业大学学报 V o l.29No.1 2009年02月 Jo urnal o f Xi!an T echnolo g ical U niver sity Feb.2009 *收稿日期:2008 06 04 基金资助:国家自然科学基金(50678149) 作者简介:杨大伟(1981 ),男,西安工业大学助教,西安建筑科技大学博士研究生,主要研究方向为城市空间复杂性. E mail:yangdaw ei@https://www.doczj.com/doc/786510069.html,.

CA元胞自动机优化模型原代码

CA优化模型原代码: M=load(‘d:\ca\jlwm’) N=load(‘d:\ca\jlwn.asc’) lindishy=load(‘d:\ca\ldfj3.asc’) caodishy=load(‘d:\ca\cdfj3.asc’) gengdishy=load(‘d:\ca\htfj3.asc’) [m,n]=size(M); Xr=[1 1 -1 1 1 1 -1 -1 1 1;1 1 1 1 -1 -1 1 1 1 -1;-1 1 1 1 -1 -1 -1 1 -1 -1;1 1 1 1 1 1 -1 1 1 I; l -1 -1 1 1 -1 -1 -1 1 1;1 -1 -1 1 -1 1 -1 1 -1 -1;-1 1 -1 -1 -1 -1 1 -1 -1 -1;-1 1 1 1 -1 1 -1 1 -1 -1;1 1 -1 1 1 -1 -1 -1 1 1;1 -1 -1 1 1 -1 -1 -1 1 1]; caodi=0;lindi=0;gengdi=0; for i=1:m forj=l:n if M(i,j)==4 caodi=caodi+1; elseif M(i,j)==3 lindi=lindi+1; elseif M(i,j)==2 gengdi=gengdi+1; end end end for i=1:m for j=1:n if M(i,j)==4 if lindishy(i,j)>gengdishy(i,j) if lindishy(i,j)>caodishy(i,j) z=0; for P=max(1,i-1):min(i+1,m) for q=max(j-1,1):min(j+1,n) if (M(p,q)~=0)&&xr(M(p,q),3)==-1 z=1; end end end if z== 0 caodi=eaodi-1; M(i,j)=3; lindi=lindi+1; end elseif lindishy(i,j)==caodishy(i,j) caoditemp=0; linditemp=0; gengditemp=0;

交通流元胞自动机模型综述

第23卷　第1期2006年1月公　路　交　通　科　技 Journal of Highway and Transportation Research and Development Vol .23　No .1 Jan .2006 文章编号:1002-0268(2006)01-0110-05 收稿日期:2004-09-27 作者简介:郑英力(1971-),女,福建宁德人,讲师,研究方向为交通控制与仿真.(z hengyl71@s ina .com ) 交通流元胞自动机模型综述郑英力,翟润平,马社强 (中国人民公安大学　交通管理工程系,北京　102623) 摘要:随着交通流模拟的需要及智能交通系统的发展,出现了基于元胞自动机理论的交通流模型。交通流元胞自动机模型由一系列车辆运动应遵守的运动规则和交通规则组成,并且包含驾驶行为、外界干扰等随机变化规则。文章介绍了交通流元胞自动机模型的产生与发展,总结和评述了国内外各种元胞自动机模型,并对元胞自动机模型的发展提出展望。关键词:元胞自动机;交通流;微观模拟;模型中图分类号:U491.1+23 文献标识码:A Survey of Cellular Automata Model of Traffic Flow ZH ENG Ying -li ,ZH AI Run -p ing ,MA She -q iang (Department of Traffic Management Engineering ,Chinese People 's Public Security University ,Beijing 102623,China )Abstract :With the increas ing demand of traffic flow si mulation and the development of ITS research ,the traffic flow model based on cellular automata has been developed .Cellular automata model of traffic flow incorporates a series of vehicle movement rules and traffic regulations .Meanwhile ,the model works under some stochastic rules takin g into consideration of drivers 'behaviors and ambient interfer -ences .This paper introduces the establishment and development of cellular automata model of traffic flow ,su mmarizes and comments on different kinds of typical cellular automata models of traffic flow ,and furthermore ,presents a new perspective for further stud y of the model . Key words :Cellular automata ;Traffic flow ;Microscopic simulation ;Model 0　引言交通流理论是运用物理学和数学定律来描述交通特性的理论。经典的交通流模型主要有概率统计模型、车辆跟驰模型、流体动力学模型、车辆排队模型等 [1] 。20世纪90年代,随着交通流模拟的需要及智能交通系统的发展,人们开始尝试将物理学中的元胞自动机(Cellular Automata ,简称CA )理论应用到交通领域,出现了交通流元胞自动机模型。交通流C A 模型的主要优点是:(1)模型简单,特别易于在计算机上实现。在建立模型时,将路段分为若干个长度为L 的元胞,一个元胞对应一辆或几辆汽车,或是几个元胞对应一辆汽车,每个元胞的状态或空或是其容纳车辆的速度,每辆车都同时按照所建立的规则运动。这些规则由车辆运动应遵守的运动规则和交通规则组成,并且包含驾驶行为、外界干扰等随机变化规则。(2)能够再现各种复杂的交通现象,反映交通流特性。在模拟过程中人们通过考察元胞状态的变化,不仅可以得到每一辆车在任意时刻的速度、位移以及车头时距等参数,描述交通流的微观特性,还可以得到平均速度、密度、流量等参数,呈现交通流的宏观特性。

元胞自动机与Matlab

元胞自动机与MATLAB 引言元胞自动机（CA）是一种用来仿真局部规则和局部联系的方法。典型的元胞自动机是定义在网格上的，每一个点上的网格代表一个元胞与一种有限的状态。变化规则适用于每一个元胞并且同时进行。典型的变化规则，决定于元胞的状态，以及其（4或8 ）邻居的状态。元胞自动机已被应用于物理模拟，生物模拟等领域。本文就一些有趣的规则，考虑如何编写有效的MATLAB的程序来实现这些元胞自动机。 MATLAB的编程考虑元胞自动机需要考虑到下列因素，下面分别说明如何用MATLAB实现这些部分。并以Conway的生命游戏机的程序为例，说明怎样实现一个元胞自动机。 ●矩阵和图像可以相互转化，所以矩阵的显示是可以真接实现的。如果矩阵 cells的所有元素只包含两种状态且矩阵Z含有零，那么用image函数来显示cat命令建的RGB图像，并且能够返回句柄。 imh = image(cat(3,cells,z,z)); set(imh, 'erasemode', 'none') axis equal axis tight ●矩阵和图像可以相互转化，所以初始条件可以是矩阵，也可以是图形。以下代码生成一个零矩阵，初始化元胞状态为零，然后使得中心十字形的元胞状态= 1。 z = zeros(n,n); cells = z; cells(n/2,.25*n:.75*n) = 1; cells(.25*n:.75*n,n/2) = 1; ●Matlab的代码应尽量简洁以减小运算量。以下程序计算了最近邻居总和，并按照CA规则进行了计算。本段Matlab代码非常灵活的表示了相邻邻居。 x = 2:n-1; y = 2:n-1; sum(x,y) = cells(x,y-1) + cells(x,y+1) + ... cells(x-1, y) + cells(x+1,y) + ... cells(x-1,y-1) + cells(x-1,y+1) + ... cells(x+1,y-1) + cells(x+1,y+1); cells = (sum==3) | (sum==2 & cells); ●加入一个简单的图形用户界面是很容易的。在下面这个例子中，应用了三个按钮和一个文本框。三个按钮，作用分别是运行，停止，程序退出按钮。文框是用来显示的仿真运算的次数。

元胞自动机的定义与构成及其特征

元胞自动机的定义与构成及其特征 https://www.doczj.com/doc/786510069.html, 2005-4-17 15:05:00 来源：生命经纬尽管元胞自动机有着较为宽松，甚至近乎模糊的构成条件。但作为一个数理模型，元胞自动机有着严格的科学定义。同时，元胞自动机是一个地地道道的"混血儿"。是物理学家、数学家，计算机科学家和生物学家共同工作的结晶。因此。对元胞自动机的含义也存在不同的解释，物理学家将其视为离散的、无穷维的动力学系统;数学家将其视为描述连续现象的偏微分方程的对立体，是一个时空离散的数学模型;计算机科学家将其视为新兴的人工智能、人工生命的分支;而生物学家则将其视为生命现象的一种抽象。下面给出几种常见的定义: 1.元胞自动机的物理学定义元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。具体讲,构成元胞自动机的部件被称为"元胞"，每个元胞具有一个状态。这个状态只琵取某个有限状态集中的一个，例如或"生"或"死"，或者是256中颜色中的一种，等等;这些元胞规则地排列在被你为"元胞空间"的空间格网上;它们各自的状态随着时间变化。而根据一个局部规则来进行更新，也就是说，一个元胞在某时刻的状态取决于、而且仅仅家决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态;元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化。 2.元胞自动机的数学定义美国数学家L.P.Hurd和K·Culik等人在90年代初，对元胞自动机分别从集合论和拓扑学等角度进行了严格地描述和定义 (谢惠民，1994; Culik,II K，1990;李才伟,1997) 1)基于集合论的定义设d代表空间维数，k代表元胞的状态，并在一个有限集合S中取值，r表元胞的邻居半径。Z是整数集，表示一维空间，t代表时间。为叙述和理解上简单起见，在一维空间上考虑元胞自动机，即假定d=1。那么整个元胞空间就是在一维空间，将整数集Z上的状态集S的分布，记为S Z。元胞自动机的动

元胞自动机NaSch模型及其MATLAB代码

元胞自动机N a S c h模型及其M A T L A B代码 This manuscript was revised by the office on December 22, 2012

元胞自动机N a S c h模型及其M A T L A B代码作业要求根据前面的介绍，对NaSch模型编程并进行数值模拟：模型参数取值：Lroad=1000，p=0.3，Vmax=5。边界条件：周期性边界。数据统计：扔掉前50000个时间步，对后50000个时间步进行统计,需给出的结果。基本图（流量-密度关系）：需整个密度范围内的。时空图（横坐标为空间，纵坐标为时间，密度和文献中时空图保持一致,画500个时间步即可）。指出NaSch模型的创新之处，找出NaSch模型的不足，并给出自己的改进思路。流量计算方法：密度＝车辆数/路长；流量flux=density×V_ave。在道路的某处设置虚拟探测计算统计时间T内通过的车辆数N；流量flux=N/T。在计算过程中可都使用无量纲的变量。 1、NaSch模型的介绍作为对184号规则的推广，Nagel和Schreckberg在1992年提出了一个模拟车辆交通的元胞自动机模型，即NaSch模型（也有人称它为NaSch模型）。时间、空间和车辆速度都被整数离散化。道路被划分为等距离的离散的格子，即元胞。每个元胞或者是空的，或者被一辆车所占据。车辆的速度可以在（0～Vmax）之间取值。 2、NaSch模型运行规则在时刻t到时刻t+1的过程中按照下面的规则进行更新：（1）加速：vnmin(vn1,vmax) 规则（1）反映了司机倾向于以尽可能大的速度行驶的特点。（2）减速：vnmin(vn,dn) 规则(2)确保车辆不会与前车发生碰撞。（3）随机慢化：以随机概率p进行慢化，令：vnmin(vn-1,0) 规则(3)引入随机慢化来体现驾驶员的行为差异，这样既可以反映随机加速行为，又可以反映减速过程中的过度反应行为。这一规则也是堵塞自发产生的至关重要因素。（4）位置更新：vnxnvn，车辆按照更新后的速度向前运动。其中vn，xn分别表示第n辆车位置和速度；l（l≥1）为车辆长度； p表示随机慢化概率；dnxn1xn1表示n车和前车n+1之间空的元胞数； vmax为最大速度。 3、NaSch模型实例

数学建模常用算法模型

按模型的数学方法分：几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等按模型的特征分：静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等按模型的应用领域分：人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。按建模的目的分：预测模型、优化模型、决策模型、控制模型等一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应按对模型结构的了解程度分：有白箱模型、灰箱模型、黑箱模型等比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。按比赛命题方向分：国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策）数学建模十大算法 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）

3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理）算法简介 1、灰色预测模型（必掌握）

关于元胞自动机在交通流理论方面的应用

关于元胞自动机在交通流理论方面的应用一．概念阐述 1．元胞自动机定义：一种利用简单编码与仿细胞繁殖机制的非数值算法空间分析模式。不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。 2．交通流理论定义：是运用数学和物理学的定义来描述交通流特性的一门边缘科学。它以分析的方法阐述交通现象及其机理，探讨人和车在单独或成列运行中的动态规律及人流或车流流量、流速和密度之间的变化关系，以求在交通规划、设计和管理中达到协调和提高各种交通设施使用效果的目的。二．正文 1．初等元胞自动机：元胞自动机应用广泛，利用元胞自动机模拟交通流是可行的，比如说利用初等元胞自动机来模拟交通流，首先要建立元胞自动机模型，建立如下：考虑有等长的L 个格子的线段每一个格子i 都有两种状态0和1，在t 时刻i 格子的状态记为：X i t 任意一个格子的下一时刻状态与其当前及前后的格子状态有关，故：记：X i t+1=F(X i-1t ,X i t ,X i+1t ) 因为t 时刻格子的状态决定了t+1时刻的格子状态，故F 总共有256种定制规则，为了满足交通规则的需要，我们在这里定制一种称为184的交通流模型。首个格子与末尾的格子相连，整个线段构成环状。 184交通流模型：每个元胞只有在前进方向的元胞邻居状态无车辆时才前进一个元胞（位移），即前面有车就不能走。那么对应八种邻居为： 111 110 101 100 ↓ ↓ ↓ ↓ 1 0 1 1 011 010 001 000 ↓ ↓ ↓ ↓ 1 10111000——184

基于元胞自动机原理的微观交通仿真模型

2005年5月重庆大学学报(自然科学版)May2005第28卷第5期Journal of Chongqing University(Natural Science Editi on)Vol.28　No.5 文章编号:1000-582X(2005)05-0086-04 基于元胞自动机原理的微观交通仿真模型3 孙　跃,余　嘉,胡友强,莫智锋 (重庆大学自动化学院,重庆　400030) 摘　要:描述了一种对高速路上的交通流仿真和预测的模型。该模型应用了元胞自动机原理对复杂的交通行为进行建模。这种基于元胞自动机的方法是将模拟的道路量离散为均匀的格子,时间也采用离散量,并采用有限的数字集。同时,在每个时间步长,每个格子通过车辆跟新算法来变换状态,车辆根据自定义的规则确定移动格子的数量。该方法使得在计算机上进行仿真运算更为可行。同时建立了跟车模型、车道变换的超车模型,并根据流程对新建的VP算法绘出时空图。提出了一个设想:将具备自学习的神经网络和仿真系统相结合,再根据安装在高速路上的传感器所获得的统计数据,系统能对几分钟以后的交通状态进行预测。关键词:元胞自动机;交通仿真;数学模型中图分类号:TP15;TP391.9文献标识码:A 1　元胞自动机生物体的发育过程本质上是单细胞的自我复制过程,50年代初,计算机创始人著名数学家冯?诺依曼(Von Neu mann)曾希望通过特定的程序在计算机上实现类似于生物体发育中细胞的自我复制[1],为了避免当时电子管计算机技术的限制,提出了一个简单的模式。把一个长方形平面分成若干个网格,每一个格点表示一个细胞或系统的基元,它们的状态赋值为0或1,在网格中用空格或实格表示,在事先设定的规则下,细胞或基元的演化就用网格中的空格与实格的变动来描述。这样的模型就是元胞自动机(cellular aut omata)。 80年代,元胞自动机以其简单的模型方便地复制出复杂的现象或动态演化过程中的吸引子、自组织和混沌现象而引起了物理学家、计算机科学家对元胞自动机模型的极大兴趣[1]。一般来说,复杂系统由许多基本单元组成,当这些子系统或基元相互作用时,主要是邻近基元之间的相互作用,一个基元的状态演化受周围少数几个基元状态的影响。在相应的空间尺度上,基元间的相互作用往往是比较简单的确定性过程。用元胞自动机来模拟一个复杂系统时,时间被分成一系列离散的瞬间,空间被分成一种规则的格子,每个格子在简单情况下可取0或1状态,复杂一些的情况可以取多值。在每一个时间间隔,网格中的格点按照一定的规则同步地更新它的状态,这个规则由所模拟的实际系统的真实物理机制来确定。格点状态的更新由其自身和四周邻近格点在前一时刻的状态共同决定。不同的格子形状、不同的状态集和不同的操作规则将构成不同的元胞自动机。由于格子之间在空间关系不同,元胞自动机模型分为一维、二维、多维模型。在一维模型中,是把直线分成相等的许多等分,分别代表元胞或基元;二维模型是把平面分成许多正方形或六边形网格;三维是把空间划分出许多立体网格。一维模型是最简单的,也是最适合描述交通流在公路上的状态。 2　基于元胞自动机的交通仿真模型的优点目前,交通模型主要分为3类: 1)流体模型(Hydr odyna m ic Model),在宏观上,以流体的方式来描述交通状态; 2)跟车模型(Car-f oll owing Model),在微观上,描述单一车辆运动行为而建立的运动模型; 3)元胞自动机模型(Cellular Aut omat on),在微观 3收稿日期:2005-01-04 基金项目:重庆市自然科学基金项目(6972) 作者简介:孙跃(1960-),浙江温州人,重庆大学教授,博士,研究方向:微观交通仿真、电力电子技术、运动控制技术及系统。

疏散问题元胞自动机仿真方法

姓名：张雪蕾学号：201211131114 姓名：崔星宇学号：201211131072 姓名：王佳颖学号：201211131054 基于元胞自动机的人员疏散仿真研究摘要：本文要仿真模拟学校某层教学楼中的人员疏散[1]，主要方法是建立元胞自动机模型。本文首先规定了学校教室和走廊的规格，并将教室和走廊平面均匀地划分成大小相等且符合实际的正方形网格，每个网格作为一个元胞，可以由教室中的学生或者障碍物占据。模型的建立是先将此楼层的人员疏散过程分成教室和走廊两个部分分别考虑、并分别建立模型。在教室中，根据每一个元胞距离教室门口的位置长短，建立了元胞位置危险度矩阵，然后在此基础上给出教室中书桌所在元胞的位置和教室墙壁所在元胞的位置。我们采用Moore neighborhood的元胞邻居方式，学生的行走方式取决于其邻居八个元胞及其本身在位置危险度矩阵中所对应的危险度的大小；有多个学生竞争同一元胞时，则采用生成随机数作为前进概率的方法，概率最大的可以成功抢到该目标元胞位置。这样每一次时间步的更新，都会有至多一个人走出本间教室，一间90人的教室需要大约26.25s就可使教室人员全部走出教室。在走廊中，我们考虑走廊只能至多三排学生并行的情况，并规定走廊上的行走规则与教室里的一致。我们采用扩展的Von-Neumann neighborhood的元胞邻居方式，学生的行走方式取决于其邻居五个元胞及其本身在位置危险度矩阵中所对应的值的大小。每一时间步的更新会有至多三个人走出走廊。最终，我们将教室和走廊的情况整合在一起考虑，得到了模拟学校学生在进行疏散时的元胞自动机模型。用此元胞自动机模型对该层教学楼的人员疏散问题进行仿真模拟，若每一时间步为0.25秒，我们得到时间步更新次数为333（即83.25s），四间教室共360人均可全部逃离教学楼，该结果与实际情况十分相符。关键字：人员疏散元胞自动机位置危险度随机数法

基于元胞自动机模型的沙堆稳定模型建立

基于元胞自动机模型的沙堆稳定模型建立摘要：世界上任何一个有休闲海滩的地方，似乎都有人在海边建沙堡。不可避免地，海浪的流入和涨潮侵蚀了沙堡。然而，并非所有沙坑对波浪和潮汐的反应都是一样的。本文旨在通过建立数学模型来建立更稳定的沙堡。为了保持沙堡基础在波浪和潮汐作用下的稳定性，从结构力学和流体力学的知识出发，有必要尽可能减轻水流对地基的影响，减少地基砂的损失，保证地基的稳定。受鱼流线的启发，基座是由四分之一椭圆曲线和旋转180°的抛物线组成的半旋转结构。建立了半旋转体D0的最大半径、四分之一椭圆的半长轴LE、抛物线的水平投影长度LR、地基的总长度L和冲击力与地基体积的比值之间的函数关系。采用最优模型求解地基的最小冲击力与体积比D0= 0.22L，LE＝0.63L，LR= 0.37 L，是最佳的三维砂土地基模型。利用元胞自动机模拟砂土地基的形成过程，对砂地基模型进行优化，以两个砂桩的塌陷间隔长度为指标，测量砂桩基础的稳定性；从而确定了雨作用下沙基基础最稳定的三维形状。关键词：流线结构、元胞自动机模型一、问题分析我们针对海浪和潮汐对沙堆基础的影响分析中，我们主要考虑了来自侧向的水流冲击力对基础的影响，此时保持沙堆基础稳定性的一大主要因素是沙堆水平方向上的粘接力，如果将沙堆基础视为一个整体，那么基础整体与沙滩的水平向摩擦力保持了沙堆基础的稳定性。而雨水对于沙堆的作用力主要表现垂直方向上的冲击力，如果将沙堆基础视为一个整体，那么沙滩对沙堆垂直向上方向的支持力作为保持沙堆基础稳定性的主要因素。由受力结构分析，第一问所建立的模型为流线型结构，对雨水垂直向下的的作用有一定缓解作用，但显然不是抵抗雨水的最优结构。我们对上述模型进行优化，假设沙堆基础受到每一滴雨水的性质相同，那么基础结构仍为半旋体结构，为了方便分析我们对沙堆基础的侧面进行分析。二、模型建立我们这里使用元胞自动机对沙堆模型进行模拟，从上至下掉落的沙粒将使沙堆不断堆积，当达到一定的临界高度后沙堆即发生崩塌，我们认为崩塌后的沙堆基础本身是一个比较稳定的结构，而两次崩塌之间的时间间隔的长度也就代表了沙堆基础的稳定型结构。假设元胞个体的堆积和崩塌的最微小的运动都发生在一个 4×4 的单元块内，每次将一个 4×4 的元胞块做统一处理。这个小单元的划分方式是：在每个周期，单元区域分别向右和向下移动一格，在所有周期中循环这一过程，得到两次崩塌时间间隔最长的模型。我们假设雨水的性质都是相同的，因此抵抗雨水的最优沙基模型应为上述最稳定模型绕中心竖轴旋转过后所形成的三维图形。三、模型分析：利用元胞自动机模拟砂堡基础的形成过程，计算两个坍塌时间，确定最稳定的砂基模型。根据以上分析，我们将该模式的优缺点总结如下：优点：根据相关公式和规律对问题进行了仿真分析，证明了模型的有效性；利用MATLAB软件对砂桩模型进行仿真，生动地展示了砂桩的形成过程；模型通过合

元胞自动机理论基础

元胞自动机理论基础 Chapter1 元胞自动机(Cellular Automata，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。 1. 自动机自动机(Automaton)通常指不需要人们逐步进行操作指导的设备(夏培肃，1984)。例如，全自动洗衣机可按照预先安排好的操作步骤作自动地运行;现代计算机能自动地响应人工编制的各种编码指令。完成各种复杂的分析与计算;机器人则将自动控制系统和人工智能结合，实现类人的一系列活动。另一方面，自动机也可被看作为一种离散数字动态系统的数学模型。例如，英国数学家A.M.Turing于1936年提出的图灵机就是一个描述计算过程的数学模型(TuringA M.，1936)。它是由一个有限控制器、一条无限长存储带和一个读写头构成的抽象的机器，并可执行如下操作: ·读写头在存储带上向左移动一格; ·读写头在存储带上向右移动一格; ·在存储的某一格内写下或清除一符号; ·条件转移。图灵机在理论上能模拟现代数字计算机的一切运算，可视为现代数字计算机的数学模型。实际上，一切"可计算"函数都等价于图灵机可计算函数，而图灵机可计算函数类又等价于一般递归函数类。根据存储带是否有限，可将自动机划分为有限带自动机(Finite Automaton)和无限带自动机(Infinite Automaton)。由于图灵机有无限长的存储带，所以为一种无限带自动机。有限带自动机常用作数字电路的数学模型，也用来描述神经系统和算法;而无限带自动机主要用来描述算法，也用来描述繁殖过程 (如细胞型自动机和网络型自动机)。有限自动机是一种控制状态有限、符号集有限的自动机，是一种离散输入输出系统的数学模型。可将有限自动机设想成由一条划分为许多方格的输入带和一个控制器组成的机器:在输入带的每一个小格中可以容纳一个符号，这些符号取自一个有限符号集S-控制器具有有限个可能状态(构成集合Q)。并在每一时刻仅处于其中的一个状态q;控制器有一个读入头，可以从输入带中读入符号;时间是离散的，初始时控制器处在状态;控制器的功能是根据其当前状态g和读入头从输入带上得到的符号a,来确定控制器的下一时刻的状态实现从状态q到状态q'，实现从状态q到状态铲q'的转移，并将读入头右移一格。控制器另一功能是识别终止状态(它们构成Q的一个子集F)，也可将该识别功能视为有限自动机的输出。从数学上来定义，有限自动机是一个五元组: FA=(Q，S，δ，q0，F) 其中，Q是控制器的有限状态集、S是输入符号约有限集、δ是控制状态转移规律的Q×S到Q的映射(可用状态转移图或状态转移表表示)，q0是初始状态、F是终止状态集。若δ是单值映射，则称M为确定性有限自动机;若δ是多值映射，则称M为非确定性有限自动机。

基于元胞自动机模型的行人排队行为模拟

第9卷第3期2009年6月交通运输系统工程与信息 Journa l of T ransporta ti on Syste m s Eng i neering and Infor m ation T echno logy V o l 9N o 3 June 2009 文章编号:1009 6744(2009)03 0140 06 系统工程理论与方法基于元胞自动机模型的行人排队行为模拟廖明军1,2,孙剑*2,王凯英1 (1.北华大学交通建筑工程学院,吉林132013;2.同济大学交通运输工程学院,上海201804) 摘要: 排队行为模型是常态下行人交通仿真系统模型的基础.本文利用排队论、有限状态自动机原理以及元胞自动机模型对排队系统进行建模.排队行为模型以邻居方向与目标方向间的修正夹角作为主要因子构造了元胞自动机模型的转移概念率函数.利用C#对行人排队行为模型进行实现,并构造了两个不同数量的售票服务台的仿真场景.从仿真动画来看,该模型逼真地模拟行人的排队活动;从不同场景的队长与时间关系曲线可以看出,增加一个售票服务台明显可以减少队列长度,排队系统性能得到改善.由此说明该模型具有模拟行人排队行为的能力. 关键词: 行人仿真;排队行为;元胞自动机模型;修正夹角中图分类号: U491文献标志码: A Si m ulation of Queui ng Behavi or Based on Cellular Auto m ataM odel LI A O M i n g jun1,2,SUN Jian2,WANG K ai ying1 (1.T ra ffic and Construction Eng i neeri ng Co ll ege of Be i hua U nivers it y,Jili n132013,Ch i na; 2.Schoo l o f T ransportation Eng i nee ri ng,T ong jiU n i versity,Shangha i201804,Ch i na) A bstrac t: Q ueu i ng behav ior m ode l i s the basis o f pedestrian tra ffic si m u lati on syste m i n no r m al situati on. T he pape r mode l s queue syste m usi ng queu i ng theo ry,finite sta te m achi ne princi p le,and ce ll u lar au t om ata m ode.l The queuing behav ior mode l takesm od ifi ed i nc l uded ang le bet ween goa l directi on and ne i ghbor d i rec ti on as t he m a i n factors o f transiti on probab ili ty function.Then the queu i ng behav i or m ode l i s i m ple m ented w it h object or i ented prog ra m l anguag e C#.Two si m u l a ti on scenar i os are establi shed w it h different amoun t of ti cket sa l es w i ndow.The an i m a ti on of si m ulati on s how s t hat the queui ng m ode l effecti ve l y si m ulates queue ac ti v iti es.F ro m the re lati onship be t w een queue leng t h and ti m e,i t can be found tha t t he l eng th of queue can be decrease by addi ng ticket sa l es po i nt,and t he pe rf o r m ance o f queue syste m can a lso be i m proved,w hich de m onstrates that the m odel can be used to si m u l a te the pedestr i an queu i ng behav i o r. K ey word s: pedestrian s i m u l a tion;queu i ng behav i o r;ce ll u l a r auto m a t on mode;l m odifi ed i ncluded ang le CLC nu m ber: U491Docum en t code: A 收稿日期:2008 10 09 修回日期:2009 02 11 录用日期:2009 03 31 基金项目:同济大学青年优秀人才培养行动计划(2007K J027);上海市自然科学基金(07ZR14120);吉林教育厅十一五规划重点项目(2007-122). 作者简介:廖明军(1974-),男,湖南邵东人,博士生. *通讯作者:sun jian@126.co m

文档之家

基于元胞自动机的快速路交织区交通流仿真建模

元胞自动机(CA)代码及应用

交通流中的NaSch模型及MATLAB代码元胞自动机完整

基于元胞自动机模型的城市历史文化街区的仿真

CA元胞自动机优化模型原代码

交通流元胞自动机模型综述

元胞自动机与Matlab

元胞自动机的定义与构成及其特征

元胞自动机NaSch模型及其MATLAB代码

数学建模常用算法模型

关于元胞自动机在交通流理论方面的应用

基于元胞自动机原理的微观交通仿真模型

疏散问题元胞自动机仿真方法

基于元胞自动机模型的沙堆稳定模型建立

元胞自动机理论基础

最新中山大学GIS考研部分总结

基于元胞自动机模型的行人排队行为模拟