离散事件动态系统基本概念、分类以及研究方法

1、离散事件动态系统基本概念、分类以及研究方法基本概念随着高新技术的迅猛发展，现实世界中涌现了大量的复杂人造系统（如计算机网络、通信网络、柔性制造系统、CIMS、交通管理系统、军事指挥系统等）。这些系统的共同特征是：系统的演化过程不能由通常的物理定律来描述，而是服从一些由人为规定的复杂规则，并由一系列相互作用的离散事件所决定。 这样的一类人造系统常被描述为离散事件动态系统（Discrete event dynamic system，DEDS）。事件：使DEDS状态发生变动的一个行动或事情。DEDS与一般动态系统的差别：通常的连续变量动态系统(CVDS)，其动态特性满足一定的物理定律，可用微分方程或

2、差分方程来描述。 例如经典力学下的质点运动方程等可以描述为DEDS基本概念: 由一些相互作用的离散事件构成，并且由它们触发而引起状态转移（演化）的一类动态系统,它所含的事件的发生在时间和空间上都是离散的。线性系统例1 柔性制造系统 待加工工件缓冲器工作台1已加工工件缓冲器待加工工件缓冲器工作台M已加工工件缓冲器Sn2Sn1智能仓库自行小车例2 机器人自动装配线（robotic assembly line）例3 开排队网络服务站1缓冲器服务站2缓冲器服务站3缓冲器通信系统中的接入控制基本分类和研究方法DEDS的三个层次模型： 逻辑层次模型（确定性）主要有形式语言，有限自动机，Markov链，Pe

3、tri网等(不可时序化）：模型不可赋时，只考虑表征系统行为的符号的顺序关系 代数层次模型（确定性）主要有极大极小代数，有限递归过程等（可时序化） 统计层次模型（随机性）主要有Markov过程，半Markov过程或广义半Markov过程，各种类型的排队网络等（可时序化、采用仿真方法）DEDS统计性能层次的研究情况从九十年代开始，统计性能层次的研究已成为DEDS研究领域的一个重要方面，主要包括以下两个研究方向：系统的性能分析：主要是灵敏度分析优化理论和应用研究：Markov控制（决策）过程方法及优化问题已成为当前DEDS领域的一个令人注目的热点，也是本课程的主要介绍对象。拓展：SMDP、POMDP

4、、HMM、HDS建模第二章随机离散事件动态系统的基本仿真技术随机变量随机变量：粗略的说就是能取不同数值的量非随机的（确定性的数值，永不改变） ：太阳系中的太阳个数随机的：一个人一天接到的 个数，每天都不一样概率实验（experiment）：考试，掷骰子，打球比赛，扔硬币一次实验对应一个输出X，考虑实验的输出是随机变量，可取多个值。（pass，fail），（1，2，3，4，5，6），（win，lose），（heads，tails）事件：掷骰子，点数为2，或者为偶数事件的概率：事件发生的机会（chance）或可能性（likelihood），m次实验中，事件A发生n次，则概率为 P(A)=lim m

5、(n/m) 0,1加数法则（addition law）互斥事件（mutually exclusive）复合事件（compound）：由互斥事件构成，如多次掷骰子中，出现偶数的事件由分别出现2，4或6的互斥事件构成。若复合事件E由A1，,An构成，则P(E)=P( A1)+ P(An)复杂事件（complex）：未必由互斥事件构成，如掷骰子，出现质数（2，3，5）或偶数（2，4，6）的事件P(AB)=P( A)+ P(B)-P(AB)AB乘积法则（multiplication law）独立事件（independent）：两个事件中，一个事件的出现不依赖于另外一个。反之为相关事件（dependen

6、t）。扔硬币，第一次为heads的事件A与第二次为tails的事件B相互独立。定义事件E表示第一次为heads且第二次为tails的事件，则P(E)P(A B)=P( A) .P(B)互斥的就无所谓相关不相关；非互斥的，则有可能独立，则P(A B)=P( A) .P(B)。既不互斥又不独立，则P(A B)=P( A) .P(B|A)= P( B) .P(A|B)， 其中，P(B|A)和P(A|B)为条件概率。（若A、B独立，则？）概率分布离散变量随机变量取值可能是离散的，如1,4.5,18,1969，也可能是连续的，如区间0 10。先考虑离散变量离散随机变量：掷骰子游戏中，输出X 1,2,3,

7、4,5,6，其中X为1的概率记P(X=1)=1/6，一般地， P(X=k)=l，对应一个概率质量函数（Prob. Mass function, PMF），即f(x)，表示概率P(X=x)。P(Xk)=l表示随机变量X不超过k的概率为l，该函数表示累积分布函数 （Cumulative distribution function, CDF，有时简称分布函数），记为F(X=k)或F(x)，满足F(X=k)kx=af(x)（从X的最低可能值a到k的所有pmf值的和）PMF CDF概率分布连续变量连续随机变量：例如连续两次所接 之间的时间差概率密度函数（Prob. density function, P

8、DF对应离散情况的PMF），仍记为f(x). 分布函数满足随机变量的期望值和标准偏差离散随机变量的期望值（expected/mean/average value）连续随机变量的期望值均值不能说明一个随机变量任何特性，只有同标准偏差一起才能说明。随机性完全体现在PDF、PMF或CDF。标准偏差：随机变量对其均值的平均偏离的估计，定义标准偏差的平方称为方差极限定理（Limit Theorems）中心极限定理：强大数定律：仿真中的基本概念离散事件仿真主要涉及随机数产生和随机系统仿真模型动态系统：系统（行为）随时间变化状态：描述系统（行为）随时间变化的物理量。如排队系统的队长，库存量，带宽占用率等。支

9、配（控制）变量（governing variable）：动态系统的行为受这些变量支配、控制（操纵），如排队系统中的服务时间和相邻顾客到达时间间隔。随机系统：控制变量是随机变量的系统，其行为受随机变量支配。模型实体（模型）：小型飞机模型，模拟仿真系统抽象（数学）模型：方程，函数，不等式，计算机程序等。帮助理解，分析，预测系统行为.建模一般基于一些假设，如系统结构，支配变量的分布。排队系统中的指数服务和到达间隔。为研究大规模复杂随机系统，可用计算机程序模拟系统行为（为支配随机变量产生随机数），这样的程序可称为仿真模型。仿真模型亦可用于优化，特别是无法或难以建立数学模型时。产生仿真优化。为什么研究随

10、机系统很多实际系统是随机系统，如通讯网络通过研究，可以改变这些系统，使其更有效运行（或降低其运行代价）随机系统的仿真模型随机系统的建模第一步是要寻找支配随机变量的分布。分布的作用：数学模型中用于建立表达式；仿真模型中用于产生随机数，以便计算机来模拟系统的行为，即重构实际系统发生的事件（产生支配随机变量的值）。随机变量分布的获取：从实际系统收集数据，然后进行分布函数拟合随机数产生-均匀分布随机数的产生（人工产生！）线性同余随机数产生（linear congruential generator）Ij+1(aIj mod m): aIj 被m除的余数， a和m为正整数，I0小于等于m，Ij0,m是随

11、机序列。如a=2, m=20, I0 =12,则有12,4,8,16,12,4,8,16,12,.适当选择a和m，则得到0和m之间的所有整数序列（m-1个），第i个整数xi代表（决定了）第i个随机数yi=xi/m，每个yi的可能性相同（ xi 在原来的序列集里出现一次）。m越大，yi越接近于服从0,1之间均匀分布的自然随机数。I0是种子，能产生的最大随机数个数是m-1。若m2321，对应个数2147483646随机数产生实际中，若周期短（m小），则随机数会重复，导致结果变坏（随机数不独立，不再服从均匀分布）。Ij+1(aIj mod m)中的aIj可能会超出计算机表达能力。Schrage逼近因

12、数分解：Q= a(Ij mod q)-rIj /q，q和r是正整数随机数产生机制无需计算aIj 对(a, b)间的任何均匀分布，其随机数x都可由(0, 1)之间的随机数y产生: x=a+(b-a)y. （映射！）随机数产生-其它分布逆函数方法指数分布的累积分布函数为产生一个随机数y，服从（0，1）之间的均匀分布，令其为指数分布的CDF的值，即F(x)=y反解x，即使用随机数的事件重构以单个服务台排队为例，两个支配变量：相继到达时间间隔ta。服务者为一个顾客的服务时间ts。根据各自分布产生两个随机序列ta,ts，例如ta=10.1, 2.3, 1, 0.9, 3.5; ts=0.1, 3.2,

13、1.19, 4.9, 1.1.可构造两种事件发生到达 ta离开空闲：10.1+2.2 ts使用率（utilization）：长时段仿真（long run）第三章Markov决策过程基本知识Examples The deterministic shortest path problem Transition from one city to the next one is deterministic:Each control (or action) at a given city leads to a unique and certain successor cityThe objective

14、is to find a path among all possible paths, which has the minimum costThis problem can be solved effectively by dynamic programmingTermination cityInitial cityFig.1Path programming for a traveling sales man Fig.2 : The shortest path problem 327941381314Bellman equation(反向递推，从K节点出发)：Examples Stochast

15、ic shortest path (SSP) problem Transition from one state to the next one is stochastic, that isEach action at a given state may lead to several possible successor states, and each transition, e.g. from state C to state F, will generate a cost, which may be dependent on the actionTermination city(Ter

16、mination state)Initial city (initial state)Fig.3 Path programming for a signal in communication systems Examples Transition for signals in the SSP problemsTransition probability: P(E| C, d); Generated cost: f (C, d, E)P(E| C, d)+P(F| C, d)+P(G| C, d )=1;P(G| C, d); f (C, d, G)ddBCDEFGP(F| C, d); f (

17、C, d, F)P(G| C, d ); f (C, d, G)The essence of the problem is how to reach the termination state with minimum expected costP(E| C, d); f (C, d, E)Mathematic models for Markov chains System EvolutionDecision epoch: t Decision epoch: t +1 Action: dtdt+1Cost: ft(Xt,dt)ft+1(Xt+1,dt+1)XtXt+1P(Xt+1| Xt, d

18、t)Markov property: state transition is independent of the history, i.e., transition from Xt to Xt+1 is only determined by current state Xt and selected action dt状态序列行动序列代价序列Mathematic models for Markov chainsBasic model parametersMathematic models for Markov chains Classification of policies Mathema

19、tic models for Markov chains Performance criteria Mathematic models for Markov chainsOptimization problem Semi-Markov decision processes (SMDPs) From Markov chain to SMDP 一次仿真：basic concepts for MDP保守矩阵与策略v有关Problem formulation (3) optimization objectivePotential-based optimization via numerical com

20、putation (1) performance potentialReinforcement learning of potentialsSemi-Markov decision processes (SMDPs) Relations of different models MDPContinuous-time MDPDiscrete-time MDP(Markov chain)SMDPIn many cases, the study of a SMDP is realized by transforming to a controlled Markov chain, if the mode

21、l is knownE.g., such as a preventive problem provided in the book Simulation-based optimizationFig. 5 Relations of different models Optimization methods & difficult problems Overview of different optimization methodsNumerical computation Value iteration Policy iteration (Non) Linear programmingSimul

22、ation methods Monte-Carlo methods Reinforcement learning Neuro-dynamic programmingIs model known?Yes: TD learning (model-based)NO: Q-learning (model-free)Disadvantages: Model need to be known Computation of matrix inverse is difficult for large scale problems! For finite horizon models backward indu

23、ction (dynamic programming)Optimization methods & difficult problems Some variants on the basic modelBasic and simplest models: Markov chains State space and action set are both finite Stochastic process is ergodicThere are many problems appearing now! Decisions may be made in continuous time SMDP T

24、here may be a continuum of states or actions e.g. compact Model parameters may not be known or uncertain Robust decision/simulation methods System state may be not observable POMDP or HMM第三章动态规划（dynamic programming） 动态规划是运筹学的一个分支，是求解多阶段决策过程的最优化数学方法。20世纪50年代初美国数学家 等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过

25、程转化为一系列单阶段问题，逐个求解，创立了解决这类问题的新方法动态规划。 多阶段决策过程( multi-step decision process ) 指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。最优化原理 作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。模型分类以“时间”角度可分成： 离散型和连续型。从信息确定与否可分成： 确定型和随机型。从目标函数的个数可分成： 单目标型和多目标型。确定性问题Fig. : The shortest path problem 327941381314Bellman equation(反向递推)：随机问题Bellman equation(反向递推)： My previous