离散事件系统仿真介绍

声明:封面与正文无关,纯粹好玩

离散事件系统仿真介绍

离散系统

在控制领域,我们通常把研究对象称之为“系统”。根据系统状态是否随时间连续变化,可以分为两类:

  • 离散系统
  • 连续系统

离散系统,是指系统状态在时间的离散点突变,通过离散的事件驱动运行变化的系统,例如系统的开关、不同指令的切换等。

离散系统的状态由于随机事件的驱动而发生变化,在两个相邻的离散事件之间,系统状态是保持不变的,因此离散系统的变化难以采用微分或者差分方程的形式描述,而且这些变化一般会具有随机性。

针对离散系统的这些特性,一方面可以基于概率论、随机过程等在理论上进行分析,但是随着系统复杂程度的增加,计算机仿真成为了研究离散系统的重要手段。

M/M/1常常出现在计算机仿真当中
![animal_coffee_shop_queue](https://gitlab.com/ztsblog/picbed/uploads/c0081eb65e9b13bae720839c1a85fcbc/animal_coffee_shop_queue.jpg)

离散事件系统仿真

离散事件系统仿真,或者叫离散事件仿真(Discrete Event Simulation,DES),就是针对离散系统建立数学模型,在计算机上进行试验的仿真技术。

DES常用概念

  1. 实体,用于描述系统中的对象。对象又可以分为“临时实体”和“永久实体”两大类。
  2. 事件,引起系统状态变化的行为。离散系统由事件驱动,在仿真模型中建立“事件表”管理系统中的各类事件。
  3. 活动,表示相邻两个事件之间的持续过程,其开始和结束都是由事件引起的。
  4. 进程。进程由若干个有序事件及若干个有序活动组成,一个进程描述了它所包括的事件及活动之间的逻辑关系及时序关系。
  5. 仿真钟。用于模拟实际系统的时间属性,一般是仿真的主要自变量。仿真过程中,仿真钟的取值成为仿真钟
  6. 统计计数器。离散事件动态系统的状态随着事件的不断发生呈现出动态变化,这种变化是随机的,某一次仿真运行得到的状态变化过程只不过是随机过程中的一次取样,只有经过多次统计得到的仿真输出统计结果才有意义。

此外,还有随机变量模型、伪随机数/变量等概念。

离散事件系统仿真一般步骤

  1. 系统建模,一般用流程图的形式描述临时实体产生规律(例如随机变量模型采用的分布、参数等)、系统运行的过程、永久实体对临时实体的规则、条件等;
  2. 确定仿真算法,除了产生随机变量外,还要确定建模的方法策略;
  3. 建立仿真模型;
  4. 设计和运行仿真程序;
  5. 分析仿真结果,需要注意的是,由于随机性的存在,一次仿真结果实质上只是一次抽样。

离散事件系统仿真建模方法

离散事件系统仿真的核心在于如何建立描述系统行为的仿真模型,如何推进仿真钟,建立起各个实体之间的逻辑关系。目前,比较成熟的仿真建模方法主要有以下4种:

  1. 事件调度法,其基本思想是通过定义事件以及每一事件发生对系统状态的影响,并按事件发生的时间顺序确定事件发生时系统中各个实体之间的逻辑关系及状态;
  2. 活动扫描法,通过定义活动以及每一活动发生对系统状态的影响来建立模型,适用于活动持续时间存在较强不确定性的系统,如前所述,可以认为事件与活动是彼此穿插的,有种“对偶”的感觉;
  3. 进程交互法,将实体历经系统时所发生的的事件及活动按事件逻辑顺序组合,形成各种进程,用于描述实体活动较为规则的系统,用类似“深度优先”的做法推进进程;
  4. 三阶段法,结合了事件调度法和活动扫描法的特点,可以粗略理解为时间推进->事件调度->活动扫描的三个阶段。

当然在实际使用中,并不一定严格要用某种策略。

安德的游戏也算是某种仿真

enders_game

Python中的仿真库

从前面略为冗长无聊的介绍中可以看出,离散事件系统仿真其实非常复杂。由于这种复杂性和专业性,市面上也有许多专用的或者通用的商业仿真软件,而在Python环境下(我个人觉得Python在性能等方面可能并无优势),也有一些用于离散系统仿真的库,在这里主要介绍SimpyCiw两个比较成熟的库。

SimPy介绍

SimPy(https://simpy.readthedocs.io/en/latest/) 是基于进程交互法的离散事件系统仿真框架。SimpPy的历史已经相当“悠久”,最早可以追溯到2002年,中间经过了许多次迭代,目前是SimPy 3。

SimPy采用Python的生成器(Generators)来描述进程,进程创建并且yield事件。根据生成器的特点我们知道,一个进程yield事件之后,该进程就会被挂起。当这个事件被触发以后,Simpy就恢复进程。在SimPy 3中进程也是事件,因此可以用一个进程继续生成另一个进程。

从网上搜索了一下,发现SimPy已经在业界得到了一定的应用,有公司利用SimPy针对特定业务场景开发一套更加完整和专业的系统仿真解决方案。

Ciw介绍

SimPy相比,Ciwhttps://ciw.readthedocs.io/en/latest/index.html )则要年轻得多——从2015年开始,到目前也不过5年的时间。

Ciw的主要功能是模拟开放式受限排队网络,基于事件调度法实现其仿真框架,采用类似三阶段的方式将事件分为三类;

  • A类事件推进仿真钟;
  • B类事件为预先安排好的事件;
  • C类事件则是在B类事件触发产生的事件。

Ciw借鉴了许多其他仿真库和Python库的设计经验,尤其是采用了面向对象的思想,虽然性能有一定的牺牲,但是具有更好的可读性。

下面附上Ciw论文中对几种仿真框架的比较,有兴趣的可以去查看原文:

SimulationFrameworkComparison

SimulationSpectrum

一点浅见

计算机仿真是我读本科大三时候上的一门课,那好像是我为数不多的成绩最好的专业课之一。不过当时只是按部就班的学习,自己深入想的并不多,隔了这么久重新拿起来,反而又有一些新的想法。

离散与连续的界限

前面已经讲过了离散系统与连续系统的区别,也提到了两者在仿真时的差异,但是在什么样的情况下我们可以用连续的方法来分析离散事件系统呢?之所以想到这一点,如果从量子的角度来看,那连续系统本质上也是离散的,例如化工过程中的化学反应,在微观层面也是一个个原子相互作用。那么,如果一个离散系统,如果事件的发生频率非常之高,同时我们对系统的观测频率又相对较慢,那么在一个较大的尺度上看,是不是可以尝试用连续系统的分析方法来分析离散事件系统的宏观特性呢?

数字孪生与离散仿真的出路

近年来,在西门子、通用、IBM等大厂的推波助澜下,数字孪生也成为了一个“网红”概念。数字孪生的概念固然是众说纷纭,但是其核心就在于对真实系统的精准(这样才称得上孪生)建模,此外数字孪生还强调数字模型与物理系统之间的实时交互。显然,数字孪生与离散系统仿真有着密切的关系——针对单个物理设备或者逻辑关系明确的离散制造过程,数字孪生应该具有较高的可行性和应用价值。那么,抛开技术的发展方向不谈,离散系统仿真在应用方面还可以有哪些突破呢?

Cosplay算是反向数字孪生,或者叫物理孪生?

dota_cosplay

参考文献

  1. 肖田元, 范文慧. 系统仿真导论. 清华大学出版社; 2010.
  2. 张效祥. 计算机科学技术百科全书. 清华大学出版社; 2005.
  3. Geraint I. Palmer, Vincent A. Knight, Paul R. Harper & Asyl L. Hawa (2019) Ciw: An open-source discrete event simulation library, Journal of Simulation, 13:1, 68-82, DOI: 10.1080/17477778.2018.1473909