第12讲 计算机仿真模型.

Presentation on theme: "第12讲 计算机仿真模型."— Presentation transcript:

1 第12讲 计算机仿真模型

2 数学建模 数学建模 【计算机仿真模型简介】 计算机仿真——利用计算机模拟现实情况或系统的演变过程，发现新的知识或规律的一种方法。本节简单介绍计算机仿真的几种基本方法，以及在数学建模过程中所发挥的重要作用。

3 数学建模 一、计算机仿真基本概念 数学建模 计算机仿真，是根据已知的信息和知识（如数学、物理规律），利用计算机模拟现实情况或系统的演变过程，发现新的知识或规律，从而解决问题的一种方法。 独立于理论研究与实验研究的认识世界的第三种方法。 特点：代价小、时间短、可重复、参数设置灵活。 得益于计算机的快速发展，计算机仿真的应用领域亦有飞速的扩展.

4 数学建模 数学建模 核禁试条件下，模拟核爆的必要性就更加凸显出来了。 核爆炸模拟

5 数学建模 数学建模 这是不可能做真实实验的，因此仿真成为重要手段，与理论计算一起共同达到安全保障的目的。 大坝安全性模拟

6 概括起来，适合于使用计算机仿真求解的问题通常具备以下两个特征之一：
数学建模 数学建模 　　什么问题适合于使用计算机仿真求解？ 　　概括起来，适合于使用计算机仿真求解的问题通常具备以下两个特征之一： 　　１、局部规律已知，全局表现未知； 　　２、具有随机因素。

7 我们根据以上两大特征把计算机仿真问题分为四大类： Ａ．物理规律仿真：只具备特征一，并且与时间无关（或关系不大），如喷泉问题，电路问题等。
数学建模 数学建模 我们根据以上两大特征把计算机仿真问题分为四大类： Ａ．物理规律仿真：只具备特征一，并且与时间无关（或关系不大），如喷泉问题，电路问题等。 从不同的角度，根据不同的标准，计算机仿真问题有多种不同的分类方法。 喷泉问题：在风向风速以及水滴质量已知的条件下，每一滴水滴的运动已知，但总体效果未知，故可作力学推导或仿真。 电路问题：单个元件的功能和作用是已知的（不考虑元件不稳定所引起的不确定性），那么多个元件组成电路后会产生什么效果。

8 Ｂ．系统演变仿真：只具备特征一，且与时间有关，如洪水漫延，生命游戏等。
数学建模 数学建模 　　　Ｂ．系统演变仿真：只具备特征一，且与时间有关，如洪水漫延，生命游戏等。 　　Ｃ．蒙特卡罗方法：只具备特征二，如高尔顿钉板实验，复杂图形面积计算等。 洪水漫延：如０５年美国数模竞赛题目：预测大坝溃堤后洪水的造成的后果。还有０８年研究生数模竞赛唐家山堰塞湖泄洪效果预测。 生命游戏：后面专门讲。 蒙特卡罗方法：又称统计模拟方法，用计算机仿真手段来模拟随机现象，预测结果。应用非常广泛。２０世纪十个最伟大的算法之一。 蒙特卡罗——摩纳哥著名赌城。２０世纪４０年代，美国曼哈顿计划。 复杂图形面积计算：边界过分复杂的图形，无法利用积分求面积。可以产生均匀分布的随机点，然后统计落入该复杂图形内的点的比例，即可估计出该复杂图形的面积。也可以求体积，如２０１０年大学生数模竞赛题“储油罐变位识别”，就有人用蒙特卡洛方法计算油罐内剩余油量的体积。

9 Ｄ．离散事件仿真：同时具备两个特征，如电梯调度，交通流模拟，飞机登机顺序等。
数学建模 数学建模 　 Ｄ．离散事件仿真：同时具备两个特征，如电梯调度，交通流模拟，飞机登机顺序等。 递推策略：时间步长法与事件步长法 “过道冲突”与“座位冲突”，对应策略：“由后向前”（back to front)与“由外向里”(outside in)

10 二、计算机仿真建模应用案例 案例一：不可召回的秘书招聘问题 设某企业招聘１名秘书，采用不可召回、当场拍板的录取方式，共有100人应聘。
数学建模 二、计算机仿真建模应用案例 数学建模 案例一：不可召回的秘书招聘问题 　　设某企业招聘１名秘书，采用不可召回、当场拍板的录取方式，共有100人应聘。 　　问题：如何使招到最优秀应聘者的概率最大？ 在第4讲“非诚勿扰女生的最佳选择”中已介绍一个最佳策略，先来回顾这个策略。

11 策略 总共面试100人，不选择前k人，从第k+1人起，一旦有比前面更优秀的人选，则选择。 k＝37——37%法则！
数学建模 数学建模 总共面试100人，不选择前k人，从第k+1人起，一旦有比前面更优秀的人选，则选择。 策略 　 　　　　　k＝37——37%法则！ 　按此策略，招到最优秀人选和空手而归的概率都是37%！ Ｋ值太小，则可能选到的人不够优秀；ｋ值太大，则可能错过最优秀人选。 前面介绍过概率解法，也可以应用蒙特卡洛方法。

12 数学建模 　蒙特卡罗方法模拟求解 数学建模 １００位应聘人选按优秀程度编号，每次出场顺序随机分布，统计招聘结果。此过程重复３百万次，然后统计招到最优秀人选的次数比例。 空手而归的概率偏大。如何改变？ 空手而归是由于最佳人选在前３７个中出场。从实际情形考虑，“选到最佳人选”的要求太高了一点，所以我们改变策略。

13 数学建模 数学建模 不选择前k人，从第k+1人起，一旦有比前面次优人选更优秀的人选，则选择。 策略 再看概率分布。

14 数学建模 数学建模 选到前三名概率是0.6311；　　而前一方法是 更关键的是改变策略后空手而归的概率由0.37降为了 可以就各种不同策略仿真，而不必计算概率，这是蒙特卡罗方法的优势。看下一情形。

15 两个条件相差较大的企业同时招聘，假定好企业仍采取３７％法则。问：差企业应如何应对？
数学建模 数学建模 两个条件相差较大的企业同时招聘，假定好企业仍采取３７％法则。问：差企业应如何应对？ 也有人称为“穷老板、富老板问题” 如果富老板知道穷老板的这个策略，也可以调整策略（ｋ值），保证自己利益最大化。穷老板相应也会再次调整策略，由此进入博弈论研究的范畴。这样一种博弈最终会得到什么结果？是一个有意思的话题。有兴趣的同学可以试试。

16 数学建模 案例二：车灯线光源优化设计 数学建模 安装在汽车头部的车灯的形状为一旋转抛物面，车灯的对称轴水平地指向正前方。经过车灯的焦点，在与对称轴相垂直的水平方向，对称地放置一定长度的均匀分布的线光源。 在焦点F正前方25米处的A点放置一测试屏，屏与FA垂直，用以测试车灯的反射光。… …

17 数学建模 数学建模 焦点处的点光源经抛物面反射出的是平行于对称轴的平行光线。

18 数学建模 数学建模 请解决下列问题： 1. 在满足该设计规范的条件下，计算线光源长度，使线光源的功率最小。 2. 对得到的线光源长度，在有标尺的坐标系中画出测试屏上反射光的亮区。 3. 讨论该设计规范的合理性。

19 数学建模 数学建模 【问题分析】 局部已知：线光源上任意一点所发出的任意一条光线，经过反射后到达测试屏上的具体位置 整体未知：整个线光源通过反射面在屏上形成的亮区。 【光线追踪法】对灯管及反射抛物面离散化，遍历光源“每一点”所发出的“所有”光线，统计测试屏上每一点接收到的光线“条数”，就可以确定亮区。

20 数学建模 数学建模 上图为反射面使用柱面坐标均匀离散化的结果。 测试屏反射光亮区

21 请同学们想象下列情况： 场景重现 假设你在美国波士顿马拉松赛现场，假设恐怖爆炸导致某一个区域现场全部被浓烟笼罩，你的手机信号、GPS、指南针等等设备都失灵或没有，你仅仅能够看到你周围两米范围内的人或物的情况，请问这时候你怎么处理？ 请同学们回答你的想法 引导同学们得到结论：你的行为不仅是由你个体决定，而且与周围邻居的行为有关，那么所有人最终展现出来的行为又是什么呢？ 这就是我们今天讲解的主要内容-元胞自动机模型

22 部分竞赛案例 （mcm1999B）场所疏散安全问题 （mcm2004B）快速通道问题 （mcm2005B）收费站设置问题 （mcm2007B）飞机登机问题 （mcm2009A）环岛交通管理问题 （mcm2013A）高速公路交通规则制定 （研赛2008A）唐家山堰塞湖泄洪问题

23 元胞自动机(Cellular Automata)一般描述：
元胞自动机是一种时间和空间都离散，空间各点（元胞）存在有限的离散状态并按给定的局部简单规则相互作用，当大量如此的元胞随时间作同步演化就可以描述复杂非线性系统的演化。元胞自动机可归结为一种仿真模型，其不是由严格的物理或函数定义，而是由一系列规则构成，用于描述局部规则明确，而全局或整体规律未知的系统变化，可以认为是一种确定性的仿真方法。 一旦给出了规则和初始状态其不同次运行的最终得行为结果将是完全一样的 关键问题： （1）元胞的状态； （2）局部的变化规则

24 基本认识： （1）元胞自动机是一个模型框架，只要满足时间、空间和状态离散且状态有限，局部规则明确但系统演化难以描述的大量个体的系统行为的仿真都可以称为元胞自动机； （2）元胞自动机的局部规则明确已知时，系统演化不含随机性； （3）系统演化结果与初始状态有关，与元胞局部邻域定义有关，与元胞系统边界条件有关，当然也与局部规则有关。

25 数 学：描述连续现象的偏微分方程的离散模型。 计算机：人工智能、人工生命的研究工具。 生 物：生命现象的一种抽象。
元胞自动机定义 物 理：离散的、无穷维的动力学系统。 数 学：描述连续现象的偏微分方程的离散模型。 计算机：人工智能、人工生命的研究工具。 生 物：生命现象的一种抽象。 元胞自动机并不仅仅是一个想法或一个算法，其蕴含深刻的理论基础和广泛的应用前景 我们知道计算机的计算时通过改变状态来进行的，其每一位存在两种状态0和1，通过这些状态的改变完成计算，理论证明元胞自动机可以完成计算机的功能，这就导致了基于元胞自动机的计算机设计 生命现象中，复制是最复杂的一项，元胞自动机可以描述个体的复制。 简单来讲，元胞自动机模型就是由元胞、元胞空间、元胞邻域和元胞规则定义。

26 （1）元胞同质性和齐性：作用规则相同和元胞分布相同；
经典元胞自动机具有以下特征： （1）元胞同质性和齐性：作用规则相同和元胞分布相同； （2）空间离散、时间离散、状态离散； （3）同步计算； （4）时空局部性； （5）维度高：元胞数量多 即状态集、邻域和变化规则都一样，同时对元胞的排列结构也做了规定 既然学习元胞自动机，我们就应该了解有哪些经典的元胞自动机模型，其特征是什么 所谓分布相同就是每个元胞完全一样，不论是分布、大小还是形状而且分布规整 下面我们就来看看一些经典的元胞自动机，这是学习过元宝自动机了应该清楚的经典模型

27 元胞：分布在一维、二维或欧氏空间的晶格点上； 状态：状态可以是{0,1}的二进制形式或是整数形式{s0,s1,…,sk}的离散集;
经典元胞自动机 元胞：分布在一维、二维或欧氏空间的晶格点上； 状态：状态可以是{0,1}的二进制形式或是整数形式{s0,s1,…,sk}的离散集; 元胞空间： 严格意义上，每个元胞在每个时刻都有自己的状态； 元胞空间的划分比较灵活，与问题有关，不同的划分导致的邻域结构不一样，同时也导致定义不同的边界条件 理论上元胞空间可以无限，但实际问题总是有限的，这就导致的当位于边界的元胞更新状态时的处理，因为边界的邻域与中间的元胞并不同，一般来说，边界可以采用周期处理或镜像处理

28 邻域：与元胞空间相关，一般有两种方式(Von. Neumann型和Moore型)：
局部规则：根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的状态转移函数。 局部规则的定义比较灵活，常用的，可以时以邻域中每个元胞的状态为自变量的函数，也可以是邻域元胞状态的某种处理或变换后的值为自变量的函数，另外一种是可以对邻域元胞的状态做统计，根据不同统计值来定义规则，甚至是邻域元胞状态的某种构型作为自变量的函数； 不同的局部规则定义就导致元胞的空间的发展产生不同的结果

29 二维元胞自动机：Game of life 和 Langton's ant
生命游戏（game of life）是由剑桥大学的数学家John Horton Conway在1970年提出来的。 元胞分布在规则划分的二维网格上； 元胞具有0，1两种状态，0代表“死”，1代表“生”； 元胞以相邻的8个元胞为邻居； 一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态决定（规则）。 生命游戏由基于一些简单数学规则的元胞组成，他能够模拟出元胞的生、死以及繁殖的过程。 总的原则是，当周围生的元胞过多，则当前元胞就由于资源限制的转为死的状态，当周围生的细胞过少，则由于孤独也将死去，而如果周围生的元胞合适，则当前元胞也将生存 下面我们来看一下其定义的规则

30 游戏规则： ＊一个死细胞恰好有3个活邻居的话，就成为一个活的细胞（诞生）； ＊一个活细胞有2个或3个活邻居的话，就继续活下去（生存）； ＊其他情况下，细胞死去或是保持死的状态（孤独或拥挤）。

31 规则的数学表达形式： 虽然如此简单的规则，但生命游戏是具有产生动态图案和动态结构能力的元胞自动机模型。它能产生丰富的、有趣的图案。给定任意的初始状态分布。经过若干步的运算，有的图案会很快消失。而有的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行。有的则保持图案定向移动

32 　　　不同初始状态可以产生非常复杂的模式，但有下面几种基本模式：
生者恒生（Stilllives） 砖块 　蜂窝 　面包 小船 大船

33 振　荡（Oscillators） 　　　眨眼者　　 灯塔　　 脉冲星

34 飞　船（Spaceships） 滑翔机 轻型飞船

35 寿 星（Methuselahs） ＊顽固者经过130代后消失。 ＊五格拼板需要1103代才能稳定下来。
数学建模 寿　星（Methuselahs） 数学建模 　　　顽固者　　　　　　五格拼板　　　　　橡树果 ＊顽固者经过130代后消失。 ＊五格拼板需要1103代才能稳定下来。 ＊橡树果需要5206代才能稳定下来，生成633个活细胞， 其中包括13个飞船。 我们想象一下五格拼版这样一个简单图形，会演变出怎样的图形？

36 最终的活细胞数是116个，包括8个砖块，4个蜂窝，1个面包，1个小船，1个大船，４个眨眼者，以及6个滑翔机。
　　五格拼板最终状态（6个滑翔机已被释放） 最终的活细胞数是116个，包括8个砖块，4个蜂窝，1个面包，1个小船，1个大船，４个眨眼者，以及6个滑翔机。

37 滑翔机发射器（ Glider Gun） 数学建模 数学建模
Conway曾经猜想，没有任何一种模式可以无限增长下去。1970年Conway在《科学美国人》杂志的数学游戏专栏第一次公开发表生命游戏时，同时提供50美元奖金，用于奖励在1970年底之前能够证明该猜想正确或错误的人。这里的“滑翔机发射器”就是一个反例。 生命游戏模型作为一类特殊的细胞自动机能够模拟生命活动中的生存、灭绝、竞争等等复杂现象，因而得名“生命游戏”。

38 Langton's ant 兰顿蚂蚁是元胞自动机另外一个经典的案例。其通过简单两条规则模拟蚂蚁的行为规律。
蚂蚁在方形网格上运动，网格分为黑色和白色两种，蚂蚁在网格上头可朝向上、下、左、右四个方向，头朝向哪个方向，下一步运动就向该方向，并且不改变头的方向，运动遵循两条规则： （1）若蚂蚁位于黑色网格，则头向左转90度，前进一步，并将原网格变成白色； （2）若蚂蚁位于白色网格，则头向右转90度，前进一步，并将原网格变成黑色； 说到二维元胞自动机，还有一个经典案例需要讲解，那就是langton蚂蚁

39 通过模拟可以发现，蚂蚁表现出了相当复杂的行为。初始状态为一只小蚂蚁位于网格中间，且头朝上。随着蚂蚁的行走演变，系统行为表现为三个阶段：
蚂蚁开始运动后会表现出一种对称图形状态并回到起点，然后进入相当复杂的行为，看不出其明确的规律，当运动到一定步数以后，蚂蚁开始进行一种规则的运动，形成一条笔直“高速公路”

40

41 自我复制的元胞自动机-Fredkin奇偶规则
Edward Fredkin 最早提出了演化规则为奇偶规则的元胞自动机模型。该自动机具有自我复制的能力。 二维网格空间中每一个网格为一个元胞，元胞的状态可以取值为0或1，元胞邻域取上、下、左、右四个邻居，局部规则根据奇偶规则决定的。若邻居状态和为偶数，则下一个时刻该元胞为0，否则为1，规则也可以表示为 前面说过元胞自动机在生物学中可以模拟生命现象，而生命现象中最典型的就是复制功能

42

43 基于元胞自动机的传播模型 模拟少数服从多数现象。 元胞空间采用2维正方形网格自动机，元胞包括2种状态：0和1，分别代表不同意见。初始状态由这2种情况以0.5概率随机填充，邻域取Moore型。每一步按下述规则更新状态： 当周围邻居为1的个数超过4时，即超过邻居的一半时，下一个时刻状态变为1，否则变为0。演化的结果是每个元胞倾向于其周围大多数的意见，并且具有相同状态值的元胞会聚集在一起，体现“物以类聚”，最终会达到一个稳定状态，不再变化。 基于元胞自动机可以研究某些现象的传播

44 前面我们讲解的都是局部规则确定性的元胞自动机，只要其初始状态、边界处理和局部规则确定，则系统演化就确定了，系统将表现出一些具有某种规律性的现象，事实上，同样可以在元胞自动机中加入随机性，让其具有一定随机变化规律，这就是概率元胞自动机

45 概率元胞自动机模型 元胞自动机中局部规则一般是确定的，不含随机性。其由局部规则决定系统演变。若在局部规则中加入随机性因素，使得规则由原来的单值映射变为多值映射，即一个规则以一定概率映射为某个值，这种元胞自动机称为概率元胞自动机。 概率元胞自动机可以描述粒子的随机运动，多用于随机扩散、多粒子运动等运动模型，在模拟非确定性自然现象中具有较好的效果。典型的概率元胞自动机模型为森林火灾模拟。

46 森林火灾模拟 元胞空间采用2维正方形网格自动机，元胞包括三种状态：正在生长的树（绿色），正在燃烧的树（红色）和空状态（黑色）。初始状态由这三种情况随机填充，邻域取Moore型。每一步按下述规则更新状态： （1）正在燃烧的树变为空状态； （2）如果正在生长的树格位最近的邻居中有不少于一棵树正在燃烧，则它将变为燃烧状态； （3）如果是空状态格位，则其以概率p生长出树； （4）考虑到闪电的作用，在最近邻居中没有正在燃烧的树（周围全是树且没有燃烧）的情况下，生长树在每个时间步以概率 p 变成燃烧的树。

47

48 各种状态的元胞的比例变化情况： 仿真并不是光好看，看热闹，重要的是从仿真结果中看出某种规律或统计出某种平均结果

49 基于元胞自动机的交通流模拟 将道路离散化为一维网格，车辆为元胞，匀速行驶，其在一维网格上的移动看成一维网格的状态变化，邻域取前后各一个位置，即邻域半径 r=1，初始状态为道路入口处有一辆车，随着时间的进行，道路入口处按均匀分布随机产生一辆车作为道路的输入（产生概率决定了车流密度），车辆在道路上的移动可使用元胞自动机模拟。 将某一个位置的车固定不移动，还可模拟红绿灯和交通堵塞等情况，如将道路最后一个位置车辆不移动或固定时长移动，则可模拟红绿灯；将道路中某一个位置车辆不移动一定时长可模拟偶然交通事故。 最后，我们用元胞自动机讨论一个稍微复杂一点的案例，交通流模拟

50 移动规则： （1）在当前时间，某一个位置若有车，则下一个时间该位置有无车取决于前后位置是否有车；
（2）若当前位置有车，下一个位置没有车，则当前位置下一个时刻有无车取决于上一个位置是否有车，如上一个位置有车，则下一个时刻当前位置有车，否则无车，若下一个位置有车，则还决定于下一个时刻此车是否会前进，若前进，则当前位置下一个时刻有无车又由上一个位置有无车决定，否则当前位置有车； （3）若当前时刻无车，则下一个时刻有无车取决于上一个位置是否有车，若有车，则当前位置下一个时刻有车，否则无车。

51 上述这条规则隐藏了一个潜在的前提（假设）：前进中的车辆应该有车距（一个车位），即若完全紧挨在一起的车辆在行进中要隔开一个车位。
移动规则可表示成: 上述这条规则隐藏了一个潜在的前提（假设）：前进中的车辆应该有车距（一个车位），即若完全紧挨在一起的车辆在行进中要隔开一个车位。 若 状态，下一个时刻则为 ,再下一个时刻即为

52

53 在这个模型基础上还可以加上红绿灯机制，如在路的最后设置红绿灯，给定红绿灯时间，只需在红灯时间内让道路口位置恒为1，在绿灯时间内让道路口位置恒为0即可。
红灯60个单位时间，绿灯120个单位时间

54 作业： 12.1 计算机仿真在数学建模中有哪些方面的应用？ 12.2 建立三号院俱乐部火灾疏散的元胞自动机模型，并编程实现，假定座位满员，通过仿真给出疏散最佳策略及疏散最短时间是多少？

55 谢 谢！