1、第7讲 仿真模型与Matlab实现,王 丹理学院数学与系统科学系 2016年夏季,例1：生命游戏,生命游戏（game of life）是由剑桥大学的数学家John Horton Conway在1970年提出来的。,元胞分布在规则划分的二维网格上； 元胞具有0，1两种状态，0代表“死”，1代表“生”； 元胞以相邻的8个元胞为邻居； 一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态决定。,生命游戏的规则：,生存：对一个活的元胞，如果它的邻居中有两个或三个元胞是活的，那么该元胞将继续生存下去。,死亡: 对一个活的元胞 (a)如果它的邻居中有四个或四个以上的元胞是活的，那么该元胞将死去；(
2、b)如果它的邻居中只有一个或没有活的元胞，那么该元胞也将死去。,繁殖: 对一个死的元胞，如果它的邻居中有3个（不能多也不能少）活的，那么该元胞将成为一个活的元胞。,生命游戏的规则(数学形式)：,规则的不断演化所形成的规律性与初始状态有关，不同的初始状态可能导致不同的演化结果。,生命游戏的一些演化过程和形态演示,（1）完全生成初始状态 （2）脉冲星（Explore） （3）滑翔机（Glider） （4）小脉冲星（Small Explore） （5）10元胞行（10 Cells row） （6）轻型飞船（Lightweight Spaceship） （7）图姆勒（Tumler） （8）滑翔机发射器
3、（Gosper Glider Gun ）,完全生成初始状态,脉冲星（Explore）,滑翔机（Glider）,10元胞行（10 Cells row）,轻型飞船（Lightweight Spaceship）,图姆勒（Tumler）,滑翔机发射器（Gosper Glider Gun ）,滑翔机发射器（Gosper Glider Gun ）,程序实现,几个核心问题： （1）棋盘状态如何表示？ （2）邻域活细胞总数如何统计？ （3）元胞自动机的状态改变规则在程序中如何体现？ （4）动画如何生成？ （5）初始状态如何给定？,（1）棋盘状态如何表示？用一个0-1矩阵表示元胞自动机的棋盘，即：,（2）邻域活
4、细胞总数如何统计？,（3）元胞自动机的状态改变规则在程序中如何体现？,换一种写法：,程序效率差异显著,（4）动画如何生成？,初始化：,每次更新：,（5）初始状态如何给定？直接赋值，如,省略了赋初值语句,例2：Langtons ant,兰顿蚂蚁是元胞自动机另外一个经典的案例。其通过简单两条规则模拟蚂蚁的行为规律。,蚂蚁在方形网格上运动，网格分为黑色和白色两种，蚂蚁在网格上头可朝向上、下、左、右四个方向，头朝向哪个方向，下一步运动就向该方向，并且不改变头的方向，运动遵循两条规则：,（1）若蚂蚁位于黑色网格，则头向右转90度，前进一步，并将原网格变成白色； （2）若蚂蚁位于白色网格，则头向左转90度
5、，前进一步，并将原网格变成黑色；,通过模拟可以发现，蚂蚁表现出了相当复杂的行为。初始状态为一只小蚂蚁位于网格中间，且头朝上。随着蚂蚁的行走演变，系统行为表现为三个阶段：,程序实现,核心变量： （1）棋盘的状态改变 （2）蚂蚁的当前位置和头的朝向,用一个二维数组表示棋盘的状态，假设棋盘大小为200*200，蚂蚁位于棋盘中心(100,100)位置，初始蚂蚁头朝上。 棋盘：cells(1:200,1:200) = 1; %白色棋盘posx = 100; posy = 100; %蚂蚁当前位置direct = 1; %1,2,3,4代表从上开始顺时针四个方向,棋盘大小,全为白色棋盘,设定图像显示,蚂蚁
6、初始位置和方向,当前位置为黑格,头朝上,头朝右,头朝下,头朝左,当前位置为白格,头朝上,头朝右,头朝下,头朝左,例3：森林火灾模拟,元胞空间采用2维正方形网格自动机，元胞包括三种状态：正在生长的树（绿色），正在燃烧的树（红色）和空状态（黑色）。初始状态由这三种情况随机填充，邻域取Moore型。每一步按下述规则更新状态：,（1）正在燃烧的树变为空状态； （2）如果正在生长的树格位最近的邻居中有不少于一棵树正在燃烧，则它将变为燃烧状态； （3）如果是空状态格位，则其以概率p生长出树； （4）考虑到闪电的作用，在最近邻居中没有正在燃烧的树（周围全是树且没有燃烧）的情况下，生长树在每个时间步以概率 f
7、 变成燃烧的树。,程序实现,核心变量：规则（1）规则（4）的实现！,用一个二维数组表示棋盘的状态，假设棋盘大小为100*100，初始根据概率随机确定是否有树。 棋盘：S=rand(100); %随机生成0,1间的棋盘矩阵S(S0.5) = 1;Sk=zeros(102); Sk(2:N+1,2:N+1) = S;,例4：基于元胞自动机的交通流模拟,将道路离散化为一维网格，车辆为元胞，匀速行驶，其在一维网格上的移动看成一维网格的状态变化，邻域取前后各一个位置，即邻域半径 r=1，初始状态为道路入口处有一辆车，随着时间的进行，道路入口处按均匀分布随机产生一辆车作为道路的输入（产生概率决定了车流密度
8、），车辆在道路上的移动可使用元胞自动机模拟。将某一个位置的车固定不移动，还可模拟红绿灯和交通堵塞等情况，如将道路最后一个位置车辆不移动或固定时长移动，则可模拟红绿灯；将道路中某一个位置车辆不移动一定时长可模拟偶然交通事故。,（1）在当前时间，某一个位置若有车，则下一个时间该位置有无车取决于前后位置是否有车； （2）若当前位置有车，下一个位置没有车，则当前位置下一个时刻有无车取决于上一个位置是否有车，如上一个位置有车，则下一个时刻当前位置有车，否则无车，若下一个位置有车，则还决定于下一个时刻此车是否会前进，若前进，则当前位置下一个时刻有无车又由上一个位置有无车决定，否则当前位置有车； （3）若当
9、前时刻无车，则下一个时刻有无车取决于上一个位置是否有车，若有车，则当前位置下一个时刻有车，否则无车。,移动规则：,移动规则可表示成:,上述这条规则隐藏了一个潜在的前提（假设）：前进中的车辆应该有车距（一个车位），即若完全紧挨在一起的车辆在行进中要隔开一个车位。,在这个模型基础上还可以加上红绿灯机制，如在路的最后设置红绿灯，给定红绿灯时间，只需在红灯时间内让道路口位置恒为1，在绿灯时间内让道路口位置恒为0即可。,红灯60个单位时间，绿灯120个单位时间,增加偶然交通事故。在每个时刻，产生服从均匀分布的随机数，若随机数大于0.5%则发生一次交通事故，在有车的位置随机产生一个交通事故点，堵塞交通固定
10、时间，如60个时间单位。具体实现上让这个位置在堵塞时间内恒为1即可。,程序实现,系统参数设置：,S=100; %道路长度 First(1:s+1) = 0； %一维数组表示道路 Passtime = 120; %绿灯时间 Stoptime = 60; %红灯时间 Ispass=1, curpass=0, curstop =0; %记录当前车辆已通过或停止的时间 Accident = 0; %路面是否发生随机事故 Acpoint = -1; %发生随机事故的位置 Actime = 60; curactime = -1; %随机事故的阻塞时间,记录更新的道路状态,阻塞道路末端,打开道路末端,红绿灯
11、规则实现,随机交通事故处理,以0.5%的概率产生随机事故,车辆移动仿真,从道路末端到起点,道路口进入车辆,以0.4的概率按均匀分布在道路起点处产生1辆车，更符合实际的是应该按照泊松分布或指数分布产生车辆，如：,进一步考虑车辆加减速，设每辆汽车（元胞）有一个行驶速度，速度最小值为0，最大值为vmax，在当前时刻到下一时刻演化中，汽车遵循以下原则：,（1）加速：现实中司机总是期望以最大速度行驶，所以在每一步当可以加速时(前后车辆距离大于当前车速)，司机进行加速，新的速度为,（2）减速：当前后车距过近，用当前速度前进会碰撞时司机进行减速，新的速度为,dn为前后车距。,（3）随机慢化：由于各种不确定因
12、素（如路况，司机分心等）造成车辆减速，以概率p进行随机慢化，新的速度为,（4）移动：车辆按照调整后速度向前移动,这个模型称为NaSch(Nagel和Schreckenberg提出)模型。,仿真场景1：设在道路口处按均匀分布以40%的概率产生车辆，假设随机慢化概率很低，不超过5%，最大速度为2，则仿真结果显示：,仿真场景2：设在道路口处按均匀分布以40%的概率产生车辆，假设随机慢化概率很低，不超过5%，最大速度为5，则仿真结果显示：,仿真场景3：设在道路口处按均匀分布以80%的概率产生车辆，假设随机慢化概率40%，最大速度为4，则仿真结果显示：,仿真场景4：设在道路口处按均匀分布以60%的概率产生车辆，假设随机慢化概率40%，最大速度为2，则仿真结果显示：,程序实现,系统参数设置：,S=200; %道路长度 First(1:s+1) = 0； %一维数组表示道路，其值记录车辆的速度 vmax = 4; %最大车速 Rnd_car= 0.4; %车辆产生概率 rndp=0.6; %随机慢化概率,车辆移动仿真,（1）最后一个位置的车辆处理：,（2）寻找当前车辆前面的车辆位置，计算两车间距离：,车辆移动仿真,（3）车辆加速处理：,车辆移动仿真,（4）车辆减速处理：,谢 谢！,
