计算机仿真原理及应用第三讲 离散事件系统仿真方法课件

1、单位：物理电子学院演讲人：王刚电子邮箱： buncan_，计算机模拟原理与应用，3离散事件系统模拟方法，离散事件系统示例：单一理发店系统，上午9336000开门，下午5336000关门。顾客的到达时间通常是随机的，每个顾客的服务时间也是随机的。系统状态：服务台的状态(忙或闲)，排队等候的顾客的队列长度。状态量的变化只能发生在离散的随机时间点。系统：由一些具有特定功能的物体组成的整体，并按照一定的规则相互联系。系统边界：为了限制研究问题的范围，系统边界被用来区分被研究的系统和影响系统的环境。实体：系统的对象和组件可以称为实体，可以在仿真系统中单独识别和描述。属性(Attribute):属性反映了

2、实体的某些属性，是对实体特征的描述，由特征参数或变量来表示。它可以是文字、数字或逻辑。活动：一个实体在一段时间内的连续运作或过程。通常用于表示两个可区分的事件之间的过程。它标志着系统状态的转变。状态：系统的状态是指某一时刻实体及其属性值的集合。事件：事件是导致离散事件系统状态改变的动作。过程：它由若干有序的事件和活动组成，描述了其中包含的事件和活动之间的逻辑关系和时序关系。为了将系统模型转化为计算机模型，必须首先确定仿真模型的控制逻辑和整个仿真时钟推进机制，即确定仿真策略。仿真策略是仿真模型的核心，它反映了仿真模型的本质，从根本上决定了仿真模型的结构。到目前为止，离散事件系统已经形成了三种基本

3、的仿真策略：事件调度、活动扫描和过程交互，这是兰德公司在1963年提出的。在美国广泛使用，在欧洲不太流行。基本思想：事件例程被视为仿真模型的基本模型单元，相应的事件例程按照事件的顺序连续执行。每个事件都有一个事件例程，用于处理事件对实体状态的影响，并安排后续事件。事件调度方法从事件的角度分析真实系统。通过定义事件和每个事件的发生，它引起系统状态的变化，并在每个事件发生时按时间顺序确定和执行相关的逻辑关系。当按照这种策略建立模型时，所有事件都被放置在事件表中，并且在模型中设置时间控制器，该时间控制器从事件表中选择最早的事件，将模拟时钟改变到事件发生的时间，然后调用对应于该事件的事件处理模块。以这

4、种方式，事件的选择和处理继续进行，直到仿真终止或程序事件生成。事件调度法的仿真策略，(1)初始化仿真的开始时间t0和结束时间tf。设置实体的初始状态。设置初始事件及其发生时间ts。(2)模拟时钟时间表(3)在当前时钟时间发生的事件类型Ei，I=1，2和n根据规则被确定和排序。(4)如果是时间表，执行E1的案例Ei:执行E1的事件例程，生成后续的事件类型和发生时间；En:执行en的evEnt例程，并生成后续的事件类型和发生时间。否则，转至(6)。(5)将模拟时钟时间提前到下一个最早的事件发生时间。这一步反映了模拟时钟的提前机制，即将模拟时钟提前到下一个最早的事件。它不同于固定时间增量法，固定时间

5、增量法是连续系统仿真中的一种时间推进方法，它反映了离散事件系统的状态只在离散时间点发生变化的特点。这种时间推进方法广泛应用于离散事件系统仿真，被称为下一个事件增量法。(6)模拟结束。1系统建模随机变量的分布和参数由观测数据决定。一般来说，它可以用流程图或网格图的形式来描述，它反映了系统中临时实体的过程、永久实体在临时实体中的作用以及它们之间的逻辑关系。2.确定模拟算法的两个方面：如何生成所需的随机变量；用什么方法来模拟离散事件系统。确定模拟策略。3.建立仿真模型，模拟时钟在各种算法中的推进方式。根据仿真算法，建立了仿真系统的计算机模型(变量定义和程序流程)。4.设计仿真程序，实现仿真模型。5模

6、拟结果分析每个模拟结果只是随机变量的一个样本。模拟结果有多可靠？离散事件系统模拟步骤，已知基本信息：等待区域足够大；队列规则先进先出；到达间隔服从11/10(单位/天)的负指数分布；维修时间服从21/15(单位/天)的负指数分布；模拟时间为365天。编程解决方案：机器的平均等待时间；机器的平均停留时间；维修站利用率。例：机器维修车间仿真，这是一个典型的单服务器单队列排队系统仿真模型。这种排队系统主要包括两个要素：顾客(即服务对象)和服务员(即服务设备)。该系统由到达模式、服务模式、并行服务器数量、系统容量和排队规则来表示。根据这个命题，修好的机器是“顾客”，修理台是“服务员”。排队系统的到达方

7、式用机器到达间隔时间的负指数分布来表示。维修模式由维修时间的负指数分布表示。系统中并行等待者的数量是1；系统容量足够大；排队规则采用先进先出模式。系统描述、系统建模，采用事件调度方法，具体仿真步骤如下：1)初始化：给出当前仿真时钟、系统状态和统计的初始值；2)扫描事件表，将当前模拟时钟增加到下一个最早的事件时间；3)处理事件并相应地改变系统状态；4)收集统计数据；5)如果模拟时间没有结束，返回2，否则，执行下一步；6)分析收集的统计数据并生成报告。通过分析可以看出，仿真模型中只有两种事件：第一种事件是“到达事件”；第二类事件是“出发事件”。下一个事件的类型由变量EVTFLAG给出。仿真模型的总

8、体结构图如下页所示，其中INIT为系统初始化子程序；是一个时间推进子程序；到达是到达事件处理子程序；是一个出发事件处理子程序；报告为报告生成子程序。仿真模型的总体结构图、建模变量的描述、到达事件的处理流程、出发事件的处理流程以及计算机仿真结果。由已知条件可知，到达间隔时间服从11/10(单位/天)的负指数分布；维修时间服从21/15(单位/天)的负指数分布；模拟时间为365天。因此，平均到达间隔时间1/1=10(天)；平均维修时间ERT1/215(天)；模拟的结束时间是365天。给定随机数发生器种子SEED113，模拟结果机器在系统中的平均停留时间为33天。机器在队列中的平均等待时间为40天。

9、维修站利用率为78.9%。基本思想：根据物理现象的统计规律，或人工构造一个合适的依赖于随机变量的概率模型，使某些随机变量的统计量成为待解决问题的解，进行大规模测量(n)的统计实验方法或计算机随机模拟方法。理论基础：大数定理：算术平均的均匀分布收敛到真值中心极限定理：置信水平下的统计误差，两个例子：布丰投针实验解决射击问题(射击游戏)，蒙特卡罗方法概述-基本思想，布丰投针实验(1777年)解决：N大数定理，蒙特卡罗方法概述-基本思想，那么交集概率是：有人进行了实验，结果列于下表：1。让R代表射手撞击点到靶心的距离，(R)代表击中R时的相应分数(环数)，而f(r)是射手撞击点的分布密度函数，它反映

10、了射手的射击水平。这位运动员的射击成绩是：在概率语言中，它是随机变量(r)的数学期望，即。假设运动员多次射击，每次射击的落点依次为r1、r2和rN，子分数g(r1)、g(r2)和g(rN)的算术平均值代表运动员的成绩和射击问题。例如，假设射击运动员的命中点分布为，用计算机进行随机测试(射击)的方法是选择一个随机数，并根据右边列出的方法判断结果。这样，进行了随机测试(拍摄)并获得了结果(r)。经过检验，得到了运动员射击成绩的近似值和：个大数的收敛定理作为待解的近似值。根据大数定律，如果X1、X2、XN独立同分布，并且具有有限的期望值(E(X)，那么当子样本的数量足够大时，随机变量X的简单子样本的

11、算术平均值以概率1收敛到其期望值E(X)。根据上面的介绍，蒙特卡罗方法是简单子样本X1的算术平均值，X2，XN的随机变量x: f(x)是x的分布密度函数。然后，当n足够大时，有下面的近似公式，蒙特卡罗方法的近似值和真值之间的误差，以及概率论的中心极限定理给出了答案。该定理指出，如果随机变量序列X1，X2，XN是独立且同分布的，并且具有有限的非零方差2，即称为置信水平，1称为置信水平。这表明该不等式以概率1近似成立，误差收敛速度的阶数为0(N-1/2)。蒙特卡罗方法中的误差中心极限定理，与上述公式一一对应的置信水平。根据问题的要求确定置信水平后，可以通过查标准正态分布表来确定。一般来说，蒙特卡罗

12、方法的误差定义为给出几种常用的和的值，有两种解释：(1)蒙特卡罗方法的误差是概率误差，它不同于其他数值计算方法。(2)误差中的均方误差是未知的，必须使用其估计值来代替。估计值可以与计算值同时计算。(2)减少估计的均方误差，例如，减少一半，那么误差将减少一半，这相当于n增加四倍的效果。减少方差的各种技巧：(1)增加试验次数n。在一个固定的条件下，要把精度提高一个数量级，试验次数n需要增加两个数量级。因此，简单地增加n不是一个有效的方法。显然，当给定置信度()时，误差由和n决定。为了降低：的效率，一般来说，减少方差的技术通常会增加观察子样本的时间。在固定时间内，减少观察样本的数量。因此，一种方法的

13、优缺点需要通过观察子样本的方差和成本(使用计算机的时间)来衡量。这就是大规模定制方法中的效率概念。它被定义为2c，其中c是观察子样本的平均成本。显然，2c越小，该方法越有效。(1)它能逼真地描述随机事物的特征和物理实验的过程，以及蒙特卡罗方法的优点。从这个意义上说，蒙特卡罗方法可以部分代替物理实验，甚至得到物理实验中难以得到的结果。用蒙特卡罗方法解决实际问题，我们可以直接从实际问题出发，而不是从方程出发，(2)由于有限的几何条件，在S维空间中计算任意面积Ds上的积分：无论面积Ds的形状有多特殊，只要能给出描述Ds几何特征的条件，就能从Ds上均匀地生成N个点：因此，在具有随机性质的问题中，如复杂

14、的系统形状，用一般的数值方法很难求解，而用蒙特卡罗方法，原则上没有困难。其中Ds是面积Ds的体积。这很难用数值方法来实现。得到了积分的近似值：(3)收敛速度与问题的维数无关。根据误差的定义，蒙特卡罗方法的误差为0(N-1/2)，与问题本身的维数无关。维数的变化只引起采样时间和估计计算时间的变化，不影响误差。这一特点决定了蒙特卡罗方法对多维问题的适应性。在一般的数值方法中，例如，当计算定积分时，计算时间随着维数的幂而增加，并且因为点数与维数的幂成正比，所以它占用了相当大的计算机内存，这在用一般的数值方法计算高维积分时是难以克服的。(4)具有同时计算多个方案和未知量的能力，(2)通过蒙特卡罗方法可

15、以同时得到多个量。(1)对于那些需要计算多个方案的问题，蒙特卡罗方法有时不需要像常规方法那样逐个计算，而是可以同时计算所有方案，其总计算量几乎等于一个方案的计算量。例如，对于具有均匀屏蔽层的几何平板，要计算几种厚度的穿透概率，只需要计算最厚的情况，而在计算最厚的情况时，只需稍加处理，就可以同时得到其他厚度的穿透概率。例如，在模拟粒子的过程中，可以同时获得不同区域中的通量、能谱和角分布，而不是像传统方法那样逐个计算量。(5)误差易于确定，根据蒙特卡罗方法的误差公式，误差可以同时计算；(6)程序结构简单，易于实现，在计算机上使用蒙特卡罗方法时，程序结构简单，块性强，易于实现。(1)收敛速度慢，(2

16、)误差是概率性的，蒙特卡罗方法的收敛速度是0(N-1/2)，因此不容易得到高精度的近似结果。对于维数较小(小于三维)的问题，它不如其他方法好。由于蒙特卡罗方法的误差是在一定的置信水平下估计的，所以它的误差是概率性的，而不是一般意义上的误差。1蒙特卡罗方法概述MC的缺点，(3)计算结果与系统的大小有关，例如，在粒子输运问题中，经验表明，蒙特卡罗方法的计算结果只有在系统的大小可以与粒子的平均自由程(一般约为十个平均自由程)相比较时才是令人满意的。然而，对于大系统或小概率事件，计算结果往往低于真实值。在使用蒙特卡罗方法时，我们可以考虑将蒙特卡罗方法与解析(或数值)方法相结合，取长补短，既可以解决解析

17、(或数值)方法难以解决的问题，也可以解决单独使用蒙特卡罗方法难以解决的问题。真随机数：不可重复，通过物理方法生成。随机数是实现已知分布抽样的基本量。在已知分布的抽样过程中，以随机数为已知量，利用适当的数学方法可以生成任意已知分布的简单子样本。在蒙特卡罗方法中，从已知分布的总体中提取简单的子样本是非常重要的。总体与子样本的关系属于共性与个性的关系。蒙特卡罗模拟是一种在生成随机数时进行随机模拟的方法。准随机数不是随机的，只要通过处理问题可以得到正确的结果。如放射性衰变、电子设备的热噪声、触发时间伪随机数：可重复，通过数学方法生成，必须通过统计检验来区分：序列的随机性和随机数分布。一个完美的随机数序列可能有一定的分布(如均匀分布、高斯分布等)。)，但是具有某种分布的序列可能根本不是随机的。分布函数是：最简单、最基本、最重要的随机数是在单个区间0，1内均匀分布的随机数，它的分布密度函数是：由于随机数在蒙特卡罗方法中占有极其重要的位置，我们用特殊的符号来表示它们。1和2代表相互独立的随机