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

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

作业要求

根据前面的介绍，对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）加速：),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=0.3，Vmax=5，用matlab 软件进行编程，扔掉前11000个时间步，统计了之后500个时间步数据，得到如下基本图和时空图。

3.1程序简介

初始化：在路段上，随机分配200个车辆，且随机速度为1-5之间。

图3.1.1是程序的运行图，图3.1.2中，白色表示有车，黑色是元胞。

图3.1.1 NaSch模型运行图

图3.1.2 NaSch模型

3.2流量密度分析

图3.2描述了交通流量与密度的关系，从图中可知，该模型中，当密度为0——0.185时，流量随密度的增加而增加；当密度超过0.185时，流量开始随密度的增加而下降。

图3.2基于NaSch模型的流量密度图

3.3 NaSch模型时空图分析

图3.3.1和图3.3.2描述了，时间步从11001开始到11500结束，共500个时间步的空间和时间的关系，从图中可以模拟出自发产生的堵塞现象。

图3.3.1基于NaSch模型的时空图

图3.3.2基于NaSch模型的时空图

4 模型评价

优点：该程序基本实现了NaSch模型的基本功能，并且最大速度、元胞数量、车辆数量以及运行间隔时间都可以修改，程序很灵活，并且可以清晰的看出每一次运行过程。

缺点：当时间步超过20000步时，内存占用量大。

附件

% 主程序：NaSch_3.m程序代码

% 单车道最大速度3个元胞开口边界条件加速减速随机慢化clf

clear all

%build the GUI

%define the plot button

plotbutton=uicontrol('style','pushbutton',...

'string','Run', ...

'fontsize',12, ...

'position',[100,400,50,20], ...

'callback', 'run=1;');

%define the stop button

erasebutton=uicontrol('style','pushbutton',...

'string','Stop', ...

'fontsize',12, ...

'position',[100,500,50,20], ...

'callback','freeze=1;');

%define the Quit button

quitbutton=uicontrol('style','pushbutton',...

'string','Quit', ...

'fontsize',12, ...

'position',[100,600,50,20], ...

'callback','stop=1;close;');

number = uicontrol('style','text', ...

'string','1', ...

'fontsize',12, ...

'position',[20,400,50,20]);

%CA setup

n=1000; %数据初始化

z=zeros(1,n); %元胞个数

z=roadstart(z,200); %道路状态初始化，路段上随机分布200辆cells=z;

vmax=5; %最大速度

v=speedstart(cells,vmax); %速度初始化

x=1; %记录速度和车辆位置

memor_cells=zeros(3600,n);

memor_v=zeros(3600,n);

imh=imshow(cells); %初始化图像白色有车，黑色空元胞

set(imh, 'erasemode', 'none')

axis equal

axis tight

stop=0; %wait for a quit button push

run=0; %wait for a draw

freeze=0; %wait for a freeze（冻结）

while (stop==0 & x<11502)

if(run==1)

%边界条件处理，搜素首末车，控制进出，使用开口条件

a=searchleadcar(cells);

b=searchlastcar(cells);

[cells,v]=border_control(cells,a,b,v,vmax);

i=searchleadcar(cells); %搜索首车位置

for j=1:i

if i-j+1==n

[z,v]=leadcarupdate(z,v);

continue;

else

%======================================加速、减速、随机慢化

if cells(i-j+1)==0; %判断当前位置是否非空

continue;

else v(i-j+1)=min(v(i-j+1)+1,vmax); %加速

%=================================减速

k=searchfrontcar((i-j+1),cells); %搜素前方首个非空元胞位置

if k==0; %确定于前车之间的元胞数

d=n-(i-j+1);

else d=k-(i-j+1)-1;

end

v(i-j+1)=min(v(i-j+1),d);

%==============================%减速

%随机慢化

v(i-j+1)=randslow(v(i-j+1));

new_v=v(i-j+1);

%======================================加速、减速、随机慢化

%更新车辆位置

z(i-j+1)=0;

z(i-j+1+new_v)=1;

%更新速度

v(i-j+1)=0;

v(i-j+1+new_v)=new_v;

end

end

end

cells=z;

memor_cells(x,:)=cells; %记录速度和车辆位置

memor_v(x,:)=v;

x=x+1;

set(imh,'cdata',cells) %更新图像

%update the step number diaplay

pause(0.0001);

stepnumber = 1+str2num(get(number,'string'));

set(number,'string',num2str(stepnumber))

end

if (freeze==1)

run = 0;

freeze = 0;

end

drawnow

end

figure(1)

for l=11001:1:11500

for k=1:1:1000

ifmemor_cells(l,k)>0

plot(k,l,'k.');

hold on;

end

end

end

xlabel('空间位置')

ylabel('时间（s）')

title('时空图')

fori=1:1:500

density(i)=sum(memor_cells(i,:)>0)/1000;

flow(i)=sum(memor_v(i,:))/1000;

end

figure(2)

plot(density,flow,'k.');

title('流量密度图')

xlabel('density')

ylabel('flow')

%

% /////////////////////////////////////////////////////////////////////// %

%

% 函数：searchlastcar.m程序代码

function [location_lastcar]=searchlastcar(matrix_cells)

%搜索尾车位置

fori=1:length(matrix_cells)

ifmatrix_cells(i)~=0

location_lastcar=i;

break;

else %如果路上无车，则空元胞数设定为道路长度

location_lastcar=length(matrix_cells);

end

end

% 函数：searchfrontcar.m程序代码

function [location_frontcar]=searchfrontcar(current_location,matrix_cells)

i=length(matrix_cells);

ifcurrent_location==i

location_frontcar=0;

else

for j=current_location+1:i

ifmatrix_cells(j)~=0

location_frontcar=j;

break;

else

location_frontcar=0;

end

end

end

% 函数：roadstart.m程序代码

function [matrix_cells_start]=roadstart(matrix_cells,n)

%道路上的车辆初始化状态，元胞矩阵随机为0或1，matrix_cells初始矩阵，n初始车辆数k=length(matrix_cells);

z=round(k*rand(1,n));

fori=1:n

j=z(i);

if j==0

matrix_cells(j)=0;

else

matrix_cells(j)=1;

end

end

matrix_cells_start=matrix_cells;

% 函数：randslow.m程序代码

function [new_v]=randslow(v)

p=0.3; %慢化概率

rand('state',sum(100*clock)*rand(1));%?¨?????ú??×?

p_rand=rand; %产生随机概率

ifp_rand<=p

v=max(v-1,0);

end

new_v=v;

% 函数：leadcarrupdate.m程序代码

function [new_matrix_cells,new_=leadcarupdate(matrix_cells,v) %第一辆车更新规则

n=length(matrix_cells);

if v(n)~=0

matrix_cells(n)=0;

v(n)=0;

end

new_matrix_cells=matrix_cells;

new_v=v;

% 函数：searchleadcar.m程序代码

function [location_leadcar]=searchleadcar(matrix_cells)

i=length(matrix_cells);

for j=1:i

ifmatrix_cells(i-j+1)~=0

location_leadcar=i-j+1;

break;

else

location_leadcar=0;

end

end

% 函数：speadstart.m程序代码

function [v_matixcells]=speedstart(matrix_cells,vmax)

%道路初始状态车辆速度初始化

v_matixcells=zeros(1,length(matrix_cells));

fori=1:length(matrix_cells)

ifmatrix_cells(i)~=0

v_matixcells(i)=round(vmax*rand(1));

end

end

元胞自动机(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',...

图论算法及其MATLAB程序代码

图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)

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

元胞自动机-森林火灾模型MATLAB代码

% 元胞自动机：森林火灾模型 % 规则： % (1)正在燃烧的树变成空格位； % (2)如果绿树格位的最近邻居中有一个树在燃烧，则它变成正在燃烧的树；% (3)在空格位，树以概率p生长； % (4)在最近的邻居中没有正在燃烧的树的情况下树在每一时步以概率f(闪%? 电)变为正在燃烧的树。 % 参考文献: % 祝玉学，赵学龙译，<<物理系统的元胞自动机模拟>>, p23 close all; clc; clear; figure; p=0.3;% 概率p f=6e-5;% 概率f axes; rand('state',0); set(gcf,'DoubleBuffer','on'); % S=round((rand(300)/2+0.5)*2); S=round(rand(300)*2); Sk=zeros(302);

Sk(2:301,2:301)=S;%%加边开始的森林初值% 红色表示正在燃烧(S中等于2的位置) % 绿色表示绿树(S中等于1的位置) % 黑色表示空格位(S中等于0的位置) C=zeros(302,302,3); R=zeros(300); G=zeros(300); R(S==2)=1; G(S==1)=1; C(2:301,2:301,1)=R; C(2:301,2:301,2)=G; Ci=imshow(C); ti=0; tp=title(['T = ',num2str(ti)]);%%时间记录while 1; ti=ti+1; St=Sk; %%St表示t时刻的森林情况 St(Sk==2)=0; % for rule (1) Su=zeros(302); Sf=Sk;%%Sf表示模拟着火的过程 Sf(Sf<1.5)=0;%%只留下着火点

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

(图论)matlab模板程序

(图论)matlab模板程序

第一讲：图论模型 程序一：可达矩阵算法 %根据邻接矩阵A（有向图）求可达矩阵P（有向图） function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; %将不为0的元素变为1 P; 程序二：无向图关联矩阵和邻接矩阵互换算法F表示所给出的图的相应矩阵 W表示程序运行结束后的结果 f=0表示把邻接矩阵转换为关联矩阵 f=1表示把关联矩阵转换为邻接矩阵 %无向图的关联矩阵和邻接矩阵的相互转换 function W=incandadf(F,f) if f==0 %邻接矩阵转换为关联矩阵 m=sum(sum(F))/2; %计算图的边数 n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; %给边的始点赋值为1 W(j,k)=1; %给边的终点赋值为1 k=k+1; end end end elseif f==1 %关联矩阵转换为邻接矩阵 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; %存在边，则邻接矩阵的对应值为1 W(a(2),a(1))=1;

end else fprint('Please imput the right value of f'); end W; 程序三：有向图关联矩阵和邻接矩阵互换算法 %有向图的关联矩阵和邻接矩阵的转换 function W=mattransf(F,f) if f==0 %邻接矩阵转换为关联矩阵 m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 %由i发出的边，有向边的始点 W(i,k)=1; %关联矩阵始点值为1 W(j,k)=-1; %关联矩阵终点值为-1 k=k+1; end end end elseif f==1 %关联矩阵转换为邻接矩阵 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); %有向边的两个顶点 if F(a(1),i)==1 W(a(1),a(2))=1; %有向边由a(1)指向a(2) else W(a(2),a(1))=1; %有向边由a(2)指向a(1) end end else fprint('Please imput the right value of f'); end W;

图论算法及matlab程序的三个案例

图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma)

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

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

图论与网络优化课程设计_Matlab实现

图论与网络优化课程设计 四种基本网络（NCN、ER、WS、BA） 的构造及其性质比较 摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。

四种基本网络（NCN、ER、WS、BA） 的构造及其性质比较 1.概述 1.网络科学的概述 网络科学（Network Science）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而丰富。网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 2.最近邻耦合网络的概述 如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。这是一个得到大量研究的稀疏的规则网络模型。 常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每K个邻居节点相连，这里K是一个偶数。这类网络的一个重要特征个节点都与它左右各/2 就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。 NCN的Matlab实现： %function b = ncn(N,K) %此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络 %返回结果b为该最近邻耦合网络对应的邻接矩阵 function b = ncn(N,K) b=zeros(N); for i = 1:N for j = (i+1):(i+K/2) if j<=N b(i,j)=1; b(j,i)=1; else b(i,j-N)=1;

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

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

元胞自动机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模型实例

多目标优化实例和matlab程序

NSGA-II 算法实例 目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ，该函数是基于NSGA-II 改进的一种多目标优化算法。 一、 数值例子 多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1． 适应值函数m 文件： function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2． 调用gamultiobj 函数，及参数设置： clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',0.3,'populationsize',100,'generations',200,'stallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto); % 最优个体系数paretoFraction 为0.3；种群大小populationsize 为100，最大进化代数generations 为200， % 停止代数stallGenLimit 为200， 适应度函数偏差TolFun 设为1e-100，函数gaplotpareto ：绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)

matlab图论程序算法大全

精心整理 图论算法matlab实现 求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 for while for for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路

for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end ;end;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 while if elseif if if pd=0; 值 t=n; if elseif if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end%如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用

传染病模型的元胞自动机实现(附程序)

传染病模型的元胞自动机实现 clc;clear all;close all; TT0=[];TT1=[];TT2=[];TT3=[];TT4=[];TT5=[];TT6=[]; %========构建元胞网络============ n=100; %网格规模 L=73; %仿真天数，365/5=73 %=============参数设定=========== p1=0.001; %0-1（易感者-潜伏者） yita=0.001; %5-0（治愈着-易感者） Step=10; %迁移步长 m=0.1; %迁移比例 popu=round(m*n); %每次迁移的人数round(X)朝最近的方向取整，对X中的每个元素朝最近的方向取整 T1=1.4; %1-3（潜伏者-隔离者时间步长）? T2=2; %2-3(染病着-隔离者时间步长) ? T3=3; %隔离时间步长 T4=73; %免疫时间步长 T5=15; %接种疫苗时间步长(10-14天表现出症状) ?

q1=0.3; %潜伏者强制隔离阀值? q2=0.5; %染病着强制隔离阀值? q3=0.6; %隔离者强制治愈阀值 q4=0.9; %接种疫苗力度? q5=0.9; %6-5（接疫苗者-治愈者） q6=0.5; %1-2 q7=0.8; %5-0 lambda1=0.01075; %患者的死亡概率 lambda2=0.00525; %隔离者的死亡概率 %% 初始化元胞 people=zeros(n); %初始化人群 people(rand(n)

图论算法及matlab程序的三个案例

图论实验三个案例 单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到 j v 的权 ij w =∞ 。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在1i v +，使1()min{()}i l v l v +=，v S ∈； ⑤ 1{}i S S v += ，1{}i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果121n n v v v v - 是从1v 到n v 的最短路径，则121n v v v - 也必然是从1v 到1n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元素表示顶点i v 到 j v 的权 ij w ，若i v 到 j v 无边，则 realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma)

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

元胞自动机N a S c h模型及其M A T L A B代码 标准化管理部编码-[99968T-6889628-J68568-1689N]

元胞自动机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模型实例

图论举例MATLAB

例1 某公司在六个城市621,,,c c c 中有分公司，从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。 ? ? ??? ? ? ? ? ?????????∞∞∞∞∞∞ 055252510550102025251001020402010015252015050102540500 用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量pb 、1index 、2index 、 d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ?? ?=顶点未标号 当第顶点已标号 当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； )(i d 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab 程序如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a'; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)=2

城市规划-元胞自动机

元胞自动机-城市规划 城市规模设计 雄安新区占地总面积约为2000平方公里，涉及河北省雄县、容城、安新3个县及周边部分区域，地处北京、天津、保定腹地，通过ArcGIS地图软件搜索该区域并从中提取出来，区域图如下所示。 图5 雄安新区区域图 为对雄安新区进行更好的仿真模拟，首先先在地图中截取雄安新区地图，然后进行边缘轮廓提取和白洋淀等不可开发地区的剔除，获得预处理图像。最后用MATlAB进行图像灰度化、二值化处理如下图所示。为后续元胞自动机提供演变地图。 图6 Matlab识别图 城市规划CA模型总步骤： 1: Step首先确定其组成的主要元素：元胞、元胞空间、元胞状态、元胞邻域及转变规则 2: Step分析模拟城市空间结构；

3:Step 确定模型的参数：繁殖参数、扩散参数、传播参数及受规划约束参数 4:Step 确定模型所需元胞转换规则的定义 5:Step 进行城市发展模拟。 ①本文提取的雄安新区地图像素为135109m m ?，元胞空间定义为11m m ?；元胞状态对应的是该地的四种状态：未城市化（即对应能开发还未开发的区域），城市化，扩展中心城市，不能被开发（如白洋淀等区域）。土地状态用编码表示。 ②元胞邻域选取为on V Neumann 邻居，在CA 系统中一个元胞1t +时刻的状态取决于它t 时刻与它邻域内其他元胞状态，考虑到地区之间发展限制因素较多，所以选取邻域较少的Neumann V on 邻居型[7]。 on V Neumann 邻居型数学定义为： ()(){} 20,,1|||||,Z v v v v v v v v v N iy ix oy iy x ix iy ix i ∈≤-+-== （4.18） 式（18）中i v 、y v 为中心元胞邻居元胞的行列坐标值，ax v 、oy v 为中心元胞的行列坐标值。 ③模型参数 借鉴参考文献[7]中的CA 模型设置了以下几个主要参数来描述城市发展[7]。 1.扩散参数diffusion ：在自然增长规则下，扩散参数可以表示一个城市化单元格元胞可能转换成另一个城市化单元格元胞的次数 2.繁殖参数breed ：在新中心传播增长规则中，繁殖参数用于一个城市化元胞可能转变成为一个新的中心传播城市化元胞 3.传播参数spread ：在边界增长的规则下，用于一个扩散中心的已城市化的邻居元胞转变为城市化的可能性 4.规划系数参数onst int C ra ：城市规划是城市工程建设和城市管理中基本依据之一，规划系数的变化对规划区最终达成的效果有约束作用[7] 模型转换规则： ④元胞的转换规则是指元胞状态的演化过程的法则，当前中心元胞和邻居元胞所处的状态决定下一个时刻贵中心状态的动力学函数，即一个状态转移函数[7]。 ()11 :,t t t i i n f s f s s ++= （4.19） 式（4.19）中t i s 表示中心元胞i 在t 时刻的状态，t n s 为t 时刻的邻居状态的组 合，1t i s +为中心元胞i 在1t +时刻所处的状态，f 为映射函数，即为元胞局部运动规则[7]。 ⑤在传统的CA 模型转换规则上进行扩展，规则为：边界增长规则、自然增长规则、新扩展中心型增长规则及受规划系数影响增长规则[7]。 1.边界增长规则：原有城市元胞边缘一定区域内，随着城市化发展，城市向外扩展，生成一个新的城市化元胞，体现了城市发展的集聚效应[7]。规定对于