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

　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-),浙江温州人,重庆大学教授,博士,研究方向:微观交通仿真、电力电子技术、运动控制技术及系统。

上,以一组自定义规则的来描述车辆行为。

在流体模型与跟车模型中,速度和密度的关系是由微分方程式中的V(P)或V(Δx)所确定的,而在元胞自动机模型中,基于平均场原理通过计算来确定二者之间的关系。

由此,元胞自动机模型有以下4个主要的优点:

1)在元胞自动机模型中,以易操作的规则取代复杂的方程式,所以易于以电脑来探讨其呈现的特性;

2)道路被划分大量细小的格子。当车辆转弯时,简化为直线运行,这样使道路的参数被简化;

3)元胞自动机模型是空间无限离散、状态有限离散、时间离散的全离散为整数一个动力学模型。该模型则用上述简单的描述来分析复杂的系统,同时模型中主要的参数为整数,该特性与真实的交通情况相吻合;

4)元胞自动机模型通过定义局部的元胞邻近关系以及使用局部演化的规则,来描述现象的变化。类似车辆的行为也是由其周围车辆行为所决定。同时元胞自动机模型中,网络的交点占据中心地位,实际的交通系统中道口在网络中的分布也是主要方面。

3　目前基于元胞自动机的交通模型概况

研究表明,元胞自动机建模技术是研究交通流动态问题一种简单有效的方法。自从Wo lfram在1986年提出了关于元胞自动机模型的理论与应用以来[2],元胞自动机模型已经广泛应用于人工智能、动力系统、计算机图形学、生物学、复杂的物理过程、化学、地理、经济社会等行为的模拟。随着现代道路交通的发展,基于元胞自动机理论的建模技术对于复杂交通现象研究具有重要意义而受到了学术界的广泛关注。作为元胞自动机在交通行为仿真中的应用,Wo lfram提出的184号CA模型之后,Nagel和Sch reckenberg于1992年提出了把车辆当成基本研究单元处理的N S模型[3],其后, Fukui和Ishibashi于1996年提出了F I模型[4]。这两个模型成为最重要的一维交通流模型。

4　新建模型

在上述NS模型[3]、F I模型[4]两个模型的基础上,笔者将规则进行了拓展并讨论了如何将一维元胞自动机应用于多车道高速路,并详细描述了模型建立情况,对数据进行定义,同时给出了车辆跟驶模型和车道变换模型。

作者还讨论了跟车模型和超车模型,进行了相应的仿真。该模型使用Java进行编写。将高速公路离散化为大小相等的单元格,并将格子状态赋值为空或被占有。被占有的格子的另一个扩展特性为占有该格子车的特性。在每条道路有很多‘入口格’与‘出口格’,车辆将按照一种特定的概率分布通过这些网格进入或离开道路。在每个时间步长,模型应用算法更新车辆的速度和位置、格子的状态。模型定义了如下道路参数:路的长度、车道数、超车道的数量和位置、“出口格”和“入口格”的位置、路段的限制速度、单元格的大小、时间步长。当格子状态为被占有使,格子需要扩展上述相关的特性。同时定义占有格子车的跟驶参数:车辆的类型、车辆的长度、最大加速度、最大减速度、超车能力、当前速度、最大速度等。

4.1　基本规则

1)产生阶段:以按发车概率在空格点产生不同速度的车辆,相当于不同速度的车辆进入车道占据不同的空格子[5];

2)加速阶段[5]:如果当前车辆速度小于V max,则车速加ΔV,V′=V+ΔV;

3)减速阶段:如果一辆车到它前面最近邻的另一辆车的距离ΔX小于或等于V(ΔX≤V),则车子减速为V′=ΔX—1;

4)转出阶段:如果车辆的车速为零,则以一定的概率δ消失,它代表车辆的转出[5];

5)运动阶段:各车辆以自己的速度向前运动V i 个格子[5]。

同时有:

1)若该车辆前方(右方)为空,则该车辆可向前移动几格或静止不动;

2)若该格子有车辆占据,且其前方也有车辆占据,则不管前方车辆在下一时刻是否向前运动,该车辆均不能向前运动。

以上演化步骤作为一个周期反复进行下去,它实际上描述了较为接近实际的高速公路上车辆的运动状况。另外,关于车辆发生的规则在文献[7]中详细阐述。

4.2　跟车模型

在交通模型中,根据驾驶员在驾车过程中的心理状态,抽象出一般性心理学原理P IEV(Percep tion2 Intellection2Evaluation2Volition)模式[8]。P IEV模式有以下具体内容:1)Percep tion过程中需要引入驾驶员觉察环境的概念:交通流环境、交通控制环境、道路几何环境。2)Intellection过程依据Percep tion过程提供的信息进行深化加工得到对当前驾驶员判断决策操作有直接意义的一系列参数值,仍为信息不是结果。

3)Evaluation过程是对驾驶员自身收集并整理的信息被转化为对下一步操纵方式的决策,确定的驾驶行为。

4)Volition过程就是从本车的当前行驶状态达到下一

78

第28卷第5期 孙　跃等:基于元胞自动机原理的微观交通仿真模型

时刻的行驶状态,得到当前速度和加速度,确定下一时刻本车的位置和速度。并把这一模式合理地应用在跟车模型和超车模型中。采用时间扫描法,在每一个单位时间内,模拟驾驶员的P IEV 模式,然后更新车辆速度和位置。在每一个时间步里,首先获得每辆车的速度和位置,然后计算出该车辆的车头时距,再判断出该车辆的行驶目标是继续跟车还是变换车道准备超车,根据不同行驶目标采用不同的算法计算出车辆的加速度,最后更新车辆在下一个单位时间中的速度和位置。

驾驶员在行驶过程中主要依据本车与前车的距离决定驾驶动作。如果距离足够安全,就可以加速;否则,就要考虑减速。所要求的安全距离Gs 与当前车速有关,理论上安全距离的关系式为:

12

m v 2

=f ×(G S -G 0),f 为刹车时的摩擦力;G 0为车辆减速并停车时与前车之间应有的最小距离。

则:

G S =

m 2f

v 2

+G 01考虑正常车速低于200km /h,驾驶员心理接受距

离高于理论安全值,同时在大量数据进行仿真利于计算机的实现,

则将安全距离Gs 和当前车速V 近似于简化为正比例关系(见图1),如(1):

Gs =G 0+b V 1

(1)图1　安全距离与车速的关系

根据当前与前车的距离Gr 决定对车辆运动状态:

1)当Gr >Gs,车辆会尽量加速,达到路段的限制速度或车辆的最高速度;

2)当Gr

当G r

。具体实现时可以取随机变量R:

1)如果R

2)如果R >1-Pb,则车辆加速;3)其他的,则车辆维持速度不变。

图2　加速概率Pa 和减速概率Pb 与速度V 的关系

由此创建Variable Probability 规则(简称V P 规则):(其中第i 辆车的位置记为X i,而它的速度V i ∈1,2,…,V max ,其中i ∈1,2,…,N ,且假定所有车辆具有相同的最大速度V max ,司机反应时间为Ts,加速概率Pa 和减速概率Pb 是以速度V 为自变量的函数,且Pa +Pb ≤1)

1)自由行驶阶段:若X i-1-X i -1>Ts ×V i ,则:

V ′i =

m in (V m ax ,V i +1),以概率Pa;

m ax (0,V i -1),

以概率Pb ;

V i,

其他.

2)安全减速阶段:若X i-1-X i -1≤Ts ×V i,则:

V ′i =m ax (0,V i -1);

3)避免车辆碰撞:如果V i >X i-1-X i -1,则:

V ′i =X i-1-X i -1;

4)车辆位置更新:X ′i =X i +V ′i .

Pa 和Pb 的取值见表1。

表1　加速概率和减速概率随速度变化取值表

V /格?s

-1

012345Pa 10.80.70.50.30Pb

0.1

0.2

0.3

0.4

0.8

4.3　超车模型

当车辆超车时,必须变换车道,则可用车道变换模型来描述超车行为。当G r

Z A (t )=G A (t )-G A (V t ).

(2)G A (t )表示车辆A 当前的前车车距,G A (V t )表示车辆A 在速度V t 时的安全车距。当车辆A 前面没有车辆时,Z A (t )记为+∞。

车辆A 超车时必须要变换车道。如图3所示,设车辆A 换到2号车道,则必然使车辆A 插入到车辆C 与车辆D 之间。则车辆A 变换车道后的安全系数表示为Z 2

A (t +Δt ),即:

88重庆大学学报(自然科学版) 2005年

Z ′A (t +Δt )

=(Z 2

A (t +Δt )+Z C (t +Δt ))/2.(3)

当Z ′A (t +Δt )>|Z A (t +Δt )|时,车辆A 才能安全变换车道。这样,就可以用比较简单的规则,把高速公路上的车流情况比较准确描述出来

。

图3　车辆A 变换车道示意图

5　编程与时空图

程序使用Java 语言编写,在软件设计上,以车辆行

驶模型为主,建立一个在一条单向封闭的环形公路上仿真器。根据程序流程图(图4),程序中设计有元胞类、状态类、元胞自动机运行类、元胞自动机模型类、图形输出类、界面类。初始参数为:环形公路分为500个格子,每个格子长度为7.5m,速度为每秒0、1、2、3、4、5个格子,即最高速度135km /h 。状态更新时间为1s 。发车是基于泊

松分布原理的断面发车模型[7]

。流程图见图4

。

图4　程序流程图

仿真后时空图见图5。

在这个模型中,存在了加速概率和减速概率变量,使得不论是加速还是减速都是按照非固定的概率进行的,速度可发生突变,且在区域中的车辆以时走时停的向前运动。运动状态具有随机性,

这与现实交通状况很相似。

(车辆最大速度为5格/s,总密度设为30%,反应时间为2s )

图5　VP 模型的时空图

6　结　论

以往在元胞自动机上的研究集中于理论分析,主要是对仿真结果与从公式中推导的结论的比较,笔者建立了交通仿真系统,包括发车模型、车辆运动模型元胞自动机模型将道路划分为大量均匀的格子,离散时间,能用少量的参数和简单的规则来准确的描绘高速路的交通情况。

若将对模型所需要的参数值由固定在道路上的传感器实时测量,经过统计数据提供,并将神经网络模块加入车辆更新算法。根据神经网络的自学习性与预测性,交通仿真系统可以对预测到几分钟以后的交通流状态。这将是一个新兴的研究方向。参考文献:

[1]　丁永生,邵世煌,万庆萱.元胞自动机与软计算的集成及

其应用[J ].控制与决策,1996,11(6):617-622.[2]　WOLFRAM S .Theory and App licati on of Cellular Aut omata

[M ].World Scientific,Singapore,1986.

[3]　NAGE L K,S CHRECKE NBERG M.A Cellular Aut omat on

Model for Free way Traffic [J ].J Phys I,1992,15(2):

2221-2229.

[4]　F UK U IM ,LSH I B ASH I Y .Traffic Fl ow in 1D Cellular Au 2

t omat on Model I ncluding CarsMoving with H igh Speed [J ].

Phys Rev E,Soc,Japan,1996,65(7):1868-1870.[5]　吕晓阳,刘慕仁,孔令江.一维元胞自动机随机交通流模

型的理论分析与计算机实验[J ].物理学报,1998,47

(11):1761-1768.[6]　李华兵,陈若航,刘慕仁,等.车辆从车道进入与转出的一

维多速随机交通流模型的研究[J ].物理学报,1998,47(11):1769-1775.[7]　莫智锋,余嘉,孙跃.基于泊松分布的微观交通仿真断面

发车数学模型研究[J ].武汉理工大学学报(交通科学与工程版),2003,27(1):73-76.

[8]　段进宇.高速道路微观交通仿真[J ].公路交通科技.

1998,15(3):21-24.

(下转第94页)

9

8第28卷第5期 孙　跃等:基于元胞自动机原理的微观交通仿真模型

[6]　SE2Y OON OH,HY UN HA HONG,M I N HO K ANG.A Data

Burst A sse mbly A lgorith m in Op tical Burst S witching Net2 works[J].ET R I Journal,2002,24(4):16-21.

[7]　XU L,PERROS H,ROUSK AS G.Techniques for Op tical

Packet S witching and Op tical Burst S witching[J].I EEE

Comm Mag,2001,39(1):136-142.

[8]　DOLZER K,G AUGER C,SPTH J,et al.Evaluati on of Res2

ervati on Mechanis m s for Op tical Burst S witching[J].Jour2 nal of Electr onics,2001,55(1):82-89.

An Adapti ve Dat a Burst Asse mbly Algorith m i n OBS Networks

WAN G J i2fe ng,J I A N G Yu2li a n,X I A Ha n2zhu

(Aut o mati on I nstitute,Chongqing University of Posts and Teleco mmunicati ons,Chongqing,400065,China)

Abstract:Op tical Burst S witching(OBS)is a p r o m ising paradig m f or the next2generati on I nternet infrastructure.This paper p r oposes an adap tive dada burst asse mbly algorith m in OBS net w orks,which can adjust para meters of asse mbly al2 gorithm according t o the traffic arrival rate of the edge nodes in OBS net w orks.A ls o this paper p r oposes how t o realize the adap tive data burst asse mbly algorith m.

Key words:op tical burst s witching;data burst;burst head packet;edge node;asse mbly algorithm

(编辑　吕赛英)

(上接第89页)

M i croscopi c Traffi c Si m ul ati on Mathe mati c

M odel Based on Cellul ar Auto mat a

SUN Yue,Y U J i a,HU Yo u2q i a ng,MO Zh i2fe ng

(College of Aut omati on,Chongqing University,Chongqing400030,China)

Abstract:This paper p resents a model f or free way traffic fl ow si m ulati on and p redicti on.The model uses cellular aut oma2 ti on theory t o model comp lex traffic behavi or.The advantage of the cellular aut omata app r oach is that the r oadway t o be modeled is quantized int o si m p le homogeneous cells,ti m e is quanitzed int o discrete step s,and physical quantities take on a finite set of values.A ls o,the state of the cells is updated at each discrete ti m estep by using a vehicle update algo2 rithm that combines a fe w vehicle moti on models,g overned by a relatively s mall set of para meters.Then vehicles just move one or several cells at each discrete ti m estep according t o the self2defined rule.This app r oach makes the computer operati on feasible.A t last,the paper puts f or ward a suppose that if the si m ulati on syste m is equi ped with the self-study syste m of NN(neural net w ork)module according t o the statistical data fr om the transducer fixed on the free way,it can p redict the traffic status ahead of10m inutes.

Key words:cellular aut o mata;traffic si m ulati on;mathe matic model

(编辑　吕赛英) 49重庆大学学报(自然科学版) 2005年

元胞自动机(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之间。 图是程序的运行图，图中，白色表示有车，黑色是元胞。

元胞自动机简史

元胞自动机简史 元胞自动机的诞生是人类探索人的认识本质的结果，也是计算技术巨大进步推动的结果。自古以来，人类认识一般问题的根本方法就是，建模和计算（推演）。模型是人类智力能理解自然世界的唯一方式。而元胞自动机正是一种可以用来建模也非常容易进行计算的理论框架和模型工具。最早从计算的视角审视问题的是关心人的认识本质的哲学家。笛卡尔认为, 人的理解就是形成和操作恰当的表述方式。洛克认为, 我们对世界的认识都要经过观念这个中介, 思维事实上不过是人类大脑对这些观念进行组合或分解的过程。霍布斯更是明确提出, 推理的本质就是计算。莱布尼兹也认为, 一切思维都可以看作是符号的形式操作的过程。进入20 世纪, 弗雷格, 怀特海、罗素等人通过数理逻辑把人类的思维进一步形式化, 形成了所谓的命题逻辑及一阶和高阶逻辑。在他们看来, 逻辑和数学, 都是根据特定的纯句法规则运作的。在这里, 所有的意义都被清除出去而不予考虑。在弗雷格和罗素的基础上, 维特根斯坦在他的早期哲学中把哲学史上自笛卡尔以来的原子论的理性主义传统发展到了一个新的高度。在维特根斯坦看来, 世界是逻辑上独立的原子事实的总和, 而不是事物的总和; 原子事实是一些客体的结合, 这些事实和它们的逻辑关系都在心灵中得到表达: 我们在心灵中为自己建造了事实的形象。人工智能事实上就是试图在机器中实现这种理性主义理想的一门学科。 在计算理论发展过程中, 阿兰·图灵(A. Turing) 的思想可以说是最关键的。在1936 年发表的论文中, 图灵提出了著名的图灵机概念。图灵机的核心部分有三: 一条带子、一个读写头、一个控制装置。带子分成许多小格, 每小格存一位数; 读写头受制于控制装置, 以一小格为移动量相对于带子左右移动, 或读小格内的数, 或写符号于其上。可以把程序和数据都以数码的形式存储在带子上。这就是“通用图灵机”原理。图灵在不考虑硬件的前提下, 严格描述了计算机的逻辑构造。这个理论不仅解决了纯数学基础理论问题, 而且从理论上证明了研制通用数字计算机的可行性。 图灵认为, 人的大脑应当被看作是一台离散态机器。尽管大脑的物质组成与计算机的物质组成完全不同, 但它们的本质则是相同。。离散态机器的行为原则上能够被写在一张行为表上, 因此与思想有关的大脑的每个特征也可以被写在一张行为表上, 从而能被一台计算机所仿效。1950 年, 图灵发表了《计算机器和智能》的论文, 对智能问题从行为主义的角度给出了定义, 设计出著名的“图灵测验,论证了心灵的计算本质, 并反驳了反对机器能够思维的9 种可能的意见。 与图灵提出人的大脑是一台离散态的计算机的思想几乎同一时期, 计算机科学的另一个 开创者冯·诺伊曼(J . von Neumann) 则开始从计算的视角思考生命的本质问题。一个人工的机器能够繁殖它自己吗? 当年笛卡尔在声称动物是机器的时候, 就曾被这个问题所难住。但冯·诺伊曼要回答这个问题, 他要找到自动机产生后代的条件, 他要证明机器可以繁殖! 为此, 冯·诺伊曼作了一个思想实验。他想象一台机器漂浮在一个池塘的上面, 这个池塘里有许多机器的零部件。这台机器是一台通用的建造器: 只要给出任何一台机器的描述,这台机器就会在池塘中寻找合适的部件, 然后再制造出这台机器。如果能够给出它自身的描述, 它就可以创造出它本身。不过, 这还不是完全的自我繁殖, 因为后代机器还没有对自身的描述, 它们因此不能复制自己。所以, 冯·诺伊曼继续假定最初的机器还必须包含一个描述复制器, 一旦后代机器产生出来, 它也从亲代那里复制一份关于自身的描述, 这样, 后代机器就可以无穷无尽地繁殖下去。 冯·诺伊曼的试验揭示了一个深刻的问题：任何自我繁殖的系统的基因材料, 无论是自然的还是人工的, 都必须具有两个不同的基本功能: 一方面它必须起到计算机程序的作用, 是一种在繁殖下一代时能够运行的算法, 另一方面它必须起到被动数据的作用, 是一个能够复制和传给下一代的描述。1953 年沃森和克里克揭示的DNA 结构和自我复制的机理。DNA 的特性正好具备冯·诺伊曼所指出的两个要求。 然而, 冯·诺伊曼对他自己的动力学模型并不十分满意。他不能充分地获得最小的逻辑前提, 因为该模型仍然以具体的原材料的吸收为前提。冯·诺伊曼感到, 该模型没有很好地把过程的

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

文章编号: 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.wendangku.net/doc/974978346.html,.

_Doctor-城市微观交通仿真及其应用(理工大-商蕾)

城市微观交通仿真 及其应用 培养单位：能源与动力工程学院学科专业：轮机工程 研究生：商蕾 指导老师：高孝洪教授 2003年10月

摘要 80年代以来，世界各国虽然基本建成了现代化道路网，但随着经济的发展，路网通行能力已经满足不了交通量增长的需要，交通拥堵现象日趋严重。为了在现有道路条件下实施交通规划和控制，在路网出现拥挤的情况下进行交通诱导和事故处理，必须对交通流的特性有清楚的认识。因此，在过去的五十年里，出现了大量的交通流理论和模型。如按细节层次分，交通仿真模型可分为亚微观模型、微观模型、中观模型和宏观模型。 以前的研究主要集中于宏观模型，讨论交通流量及密度的变化。现在，由于高速运算计算机的发展以及交通仿真的需要，研究热点逐渐转移到微观仿真模型。微观交通模型在每一时刻均计算每一辆车的位置、车速、加速度等特性，可为交通管理和仿真提供详细的信息。 本文以微观交通仿真建模和城市微观交通仿真系统开发为研究重点，主要完成了如下工作： （1） 建立了车辆行为模型，其中包括跟驰模型、邻车影响模型和换道模型。模型中充分考虑了邻道车辆对驾驶行为的影响及驾驶员的 反应延迟，使模型更符合真实情况； （2） 开发了城市微观交通仿真系统：该系统包括车辆产生模型、路网模型、交通规则模型、信号灯控制模型、车辆行为模型、路径选 择模型、路口转向描述模型； （3） 在仿真应用中实现并研究了信号灯周期及其相位按交通需求动态分配的方案，提出该项仿真可用于确定在已知OD下，信号灯控 制路口的最大通行能力，并可作为现有控制方案的评估依据。 （4） 在图形工作站OCTANE上实现城市微观交通仿真系统的可视化，可从多角度实时观测交通状况。 （5） 通过对典型路段的交通调查，验证城市微观交通仿真系统的合理性。 关键词： 微观交通模型、仿真、可视化 I

元胞自动机简史

元胞自动机简史元胞自动机的诞生是人类探索人的认识本质的结果，也是计算技术巨大进步推动的结果。自古以来，人类认识一般问题的根本方法就是，建模和计算（推演）。模型是人类智力能理解自然世界的唯一方式。而元胞自动机正是一种可以用来建模也非常容易进行计算的理论框架和模型工具。最早从计算的视角审视问题的是关心人的认识本质的哲学家。笛卡尔认为, 人的理解就是形成 和操作恰当的表述方式。洛克认为, 我们对世界的认识都要经过观念这个中介, 思维事实上不过是 人类大脑对这些观念进行组合或分解的过程。霍布斯更是明确提出, 推理的本质就是计算。莱布尼兹也认为, 一切思维都可以看作是符号的形式操作的过程。进入20 世纪, 弗雷格, 怀特海、罗素等人通过数理逻辑把人类的思维进一步形式化, 形成了所谓的命题逻辑及一阶和高阶逻辑。在他们看来, 逻辑和数学, 都是根据特定的纯句法规则运作的。在这里, 所有的意义都被清除出去而不 予考虑。在弗雷格和罗素的基础上, 维特根斯坦在他的早期哲学中把哲学史上自笛卡尔以来的原 子论的理性主义传统发展到了一个新的高度。在维特根斯坦看来, 世界是逻辑上独立的原子事实 的总和, 而不是事物的总和; 原子事实是一些客体的结合, 这些事实和它们的逻辑关系都在心灵中得到表达: 我们在心灵中为自己建造了事实的形象。人工智能事实上就是试图在机器中实现这种理性主义理想的一门学科。 在计算理论发展过程中，阿兰图灵（A. Turing）的思想可以说是最关键的。在1936年发表的论 文中, 图灵提出了著名的图灵机概念。图灵机的核心部分有三: 一条带子、一个读写头、一个控制装置。带子分成许多小格, 每小格存一位数; 读写头受制于控制装置, 以一小格为移动量相对于带子左右移动, 或读小格内的数, 或写符号于其上。可以把程序和数据都以数码的形式存储在带子上。这就是“通用图灵机”原理。图灵在不考虑硬件的前提下, 严格描述了计算机的逻辑构造。这个理论不仅解决了纯数学基础理论问题, 而且从理论上证明了研制通用数字计算机的可行性。 图灵认为, 人的大脑应当被看作是一台离散态机器。尽管大脑的物质组成与计算机的物质组成完全不同, 但它们的本质则是相同。。离散态机器的行为原则上能够被写在一张行为表上, 因此与思想有关的大脑的每个特征也可以被写在一张行为表上, 从而能被一台计算机所仿效。1950 年, 图灵发表了《计算机器和智能》的论文, 对智能问题从行为主义的角度给出了定义, 设计出著名的“图灵测验,论证了心灵的计算本质, 并反驳了反对机器能够思维的9 种可能的意见。 与图灵提出人的大脑是一台离散态的计算机的思想几乎同一时期, 计算机科学的另一个 开创者冯诺伊曼J . von Neumann）则开始从计算的视角思考生命的本质问题。一个人工的机器能 够繁殖它自己吗？当年笛卡尔在声称动物是机器的时候，就曾被这个问题所难住。但冯诺伊曼要回答这个问题, 他要找到自动机产生后代的条件, 他要证明机器可以繁殖! 为此，冯诺伊曼作了一个思想实验。他想象一台机器漂浮在一个池塘的上面，这个池塘里有许多机器的零部件。这台机器是一台通用的建造器: 只要给出任何一台机器的描述,这台机器就会在 池塘中寻找合适的部件, 然后再制造出这台机器。如果能够给出它自身的描述, 它就可以创造出它本身。不过, 这还不是完全的自我繁殖, 因为后代机器还没有对自身的描述, 它们因此不能复制自己。所以，冯诺伊曼继续假定最初的机器还必须包含一个描述复制器，一旦后代机器产生岀来，它也从亲代那里复制一份关于自身的描述, 这样, 后代机器就可以无穷无尽地繁殖下去。 冯诺伊曼的试验揭示了一个深刻的问题：任何自我繁殖的系统的基因材料，无论是自然的还是人工的, 都必须具有两个不同的基本功能: 一方面它必须起到计算机程序的作用, 是一种在繁殖下一代时能够运行的算法, 另一方面它必须起到被动数据的作用, 是一个能够复制和传给下一代的描述。1953 年沃森和克里克揭示的DNA 结构和自我复制的机理。DNA 的特性正好具备冯诺伊曼所指岀的两个要求。 然而, 冯诺伊曼对他自己的动力学模型并不十分满意。他不能充分地获得最小的逻辑前提, 因为该模型仍然以具体的原材料的吸收为前提。冯诺伊曼感到, 该模型没有很好地把过程的 逻辑形式和过程的物质结构区分开。作为一个数学家，冯诺伊曼需要的是完全形式化的抽象理

元胞自动机与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); ●加入一个简单的图形用户界面是很容易的。在下面这个例子中，应用了三个 按钮和一个文本框。三个按钮，作用分别是运行，停止，程序退出按钮。文框是用来显示的仿真运算的次数。

道路微观交通仿真中换道行为模型的研究与实现

::道路与交通工程 Road&Traffic Engineering 道路微观交通仿真中换道行为模型的研究与实现 陈晶，孙旭飞，田东黎 （福州大学物理与信息工程学院，福建福州350108） 摘要：建立了描述车辆换道意图的产生、选择合适车道和实施换道行为的车道变换模型。运用车辆运动学理论，以换道车辆为目标，给岀了目标车辆与邻近车辆的最小安全距离间隙接受模型和车辆换道实施过程的运动模型，并应用到程序设计中，利用基于VC++上建立的交通仿真系统动态地显示非强制换道行为的效果。与VISSIM软件基于规则的换道模型相比，加入驾驶特性的影响和优化原来固定的安全距离,研究结果相对更优。 关键词：道路；微观交通仿真；换道行为；目标位置；最小安全距离 中图分类号：U412.1文献标志码：B文章编号:1009-7767（2019）01-0028-04 Research and Implementation of Simulated Lane Change Behavior Model of Road Micro Traffic Chen Jing,Sun Xufei,Tian Dongshen 智能交通系统（Intelligent Transport System,以下简称为ITS）在交通运输系统发展过程中占据重要地位。由于交通运输系统的不可复制性，交通仿真模型成为ITS中交通分析的重要方法之一，而作为交通仿真的核心部分，车辆行为模型也在ITS中发挥着重要作用m。车辆行为模型包括跟驰行为模型和换道行为模型，其中换道行为模型的质量优劣直接影响着交通仿真模型的效果与性能。与已趋于成熟的跟驰行为模型相比，换道行为模型研究则相对落后回。由于在换道过程中存在运动学过程较为复杂、驾驶员的驾驶特性难以量化、微观数据难以获取等问题，笔者拟从运动学角度对车辆换道行为模型进行分析，从驾驶员的决策过程分析最小安全距离和换道行为实施的运动模型。通过在微观仿真系统上动态显示换道行为的仿真效果，来验证换道行为模型的准确性，并提高微观仿真系统的精度。 1换道行为分类 道路上车辆换道行为是一种普遍且常见的交通现象。车辆换道是指当前道路不止1个车道时,车辆由于某种需求从当前车道变更到相邻车道的驾驶行为。换道行为是指根据驾驶员特性以及对周围交通状况的实时信息（车速、位置等）判断,调整驾驶目标策略的综合过程。换道行为根据换道产生的需求大致可以分为2类：强制换道、非强制换道。强制换道是指车辆为了到达目的地而采取的变道行为，具有确定的目标车道、在一定行驶区域内必须换道的特点；非强制换道又称为自由换道，是指目标车辆在遇到当前车道前车速较慢时，为了追求期望车速以及更大的驾驶空间或为了正常驾驶避开即将驶入安全距离的后车而产生的换道行为。笔者主要研究非强制换道行为。 2换道行为模型研究 换道行为通常被分为：产生换道意图、选择合适车道和换道行为实施2T。其中选择合适车道可以视为分析车辆换道行为可行性的过程，它将最终决定换道行为是否实施。 2.1产生换道意图 在不同的交通流密度下，由于每个驾驶员对当前车辆的期望车速要求不同，这个期望车速主要受车辆的机械特性、驾驶员的驾驶特性和交通规则的影响。车辆在道路行驶时，由于当前车道前车的速度过慢，导致车辆的行驶速度低于期望车速时,便会产生换道需求。但是这个需求不是必须的，而是为了获取更理想的行驶方式而采取的换道行为。只有当选择的目标车道确认换道行为可行时，换道才可实施，否则车辆会继续在原车道减速行驶冋。 28彳苯技水2019No.l(Jan.)Vol.37

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

第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)能够再现各种复杂的交通现象,反映交通流特性。在模拟过程中人们通过考察元胞状态的变化,不仅可以得到每一辆车在任意时刻的速度、位移以及车头时距等参数,描述交通流的微观特性,还可以得到平均速度、密度、流量等参数,呈现交通流的宏观特性。

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

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-),浙江温州人,重庆大学教授,博士,研究方向:微观交通仿真、电力电子技术、运动控制技术及系统。

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

关于元胞自动机在交通流理论方面的应用 一．概念阐述 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

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

姓名：张雪蕾学号：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为非确定性有限自动机。