離散事件動(dòng)態(tài)系統(tǒng)基本概念、分類以及研究方法

1、離散事件動(dòng)態(tài)系統(tǒng)基本概念、分類以及研究方法基本概念隨著高新技術(shù)的迅猛發(fā)展，現(xiàn)實(shí)世界中涌現(xiàn)了大量的復(fù)雜人造系統(tǒng)（如計(jì)算機(jī)網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、柔性制造系統(tǒng)、CIMS、交通管理系統(tǒng)、軍事指揮系統(tǒng)等）。這些系統(tǒng)的共同特征是：系統(tǒng)的演化過程不能由通常的物理定律來描述，而是服從一些由人為規(guī)定的復(fù)雜規(guī)則，并由一系列相互作用的離散事件所決定。 這樣的一類人造系統(tǒng)常被描述為離散事件動(dòng)態(tài)系統(tǒng)（Discrete event dynamic system，DEDS）。事件：使DEDS狀態(tài)發(fā)生變動(dòng)的一個(gè)行動(dòng)或事情。DEDS與一般動(dòng)態(tài)系統(tǒng)的差別：通常的連續(xù)變量動(dòng)態(tài)系統(tǒng)(CVDS)，其動(dòng)態(tài)特性滿足一定的物理定律，可用微分方程或

2、差分方程來描述。 例如經(jīng)典力學(xué)下的質(zhì)點(diǎn)運(yùn)動(dòng)方程等可以描述為DEDS基本概念: 由一些相互作用的離散事件構(gòu)成，并且由它們觸發(fā)而引起狀態(tài)轉(zhuǎn)移（演化）的一類動(dòng)態(tài)系統(tǒng),它所含的事件的發(fā)生在時(shí)間和空間上都是離散的。線性系統(tǒng)例1 柔性制造系統(tǒng) 待加工工件緩沖器工作臺(tái)1已加工工件緩沖器待加工工件緩沖器工作臺(tái)M已加工工件緩沖器Sn2Sn1智能倉(cāng)庫(kù)自行小車?yán)? 機(jī)器人自動(dòng)裝配線（robotic assembly line）例3 開排隊(duì)網(wǎng)絡(luò)服務(wù)站1緩沖器服務(wù)站2緩沖器服務(wù)站3緩沖器通信系統(tǒng)中的接入控制基本分類和研究方法DEDS的三個(gè)層次模型： 邏輯層次模型（確定性）主要有形式語言，有限自動(dòng)機(jī)，Markov鏈，Pe

3、tri網(wǎng)等(不可時(shí)序化）：模型不可賦時(shí)，只考慮表征系統(tǒng)行為的符號(hào)的順序關(guān)系 代數(shù)層次模型（確定性）主要有極大極小代數(shù)，有限遞歸過程等（可時(shí)序化） 統(tǒng)計(jì)層次模型（隨機(jī)性）主要有Markov過程，半Markov過程或廣義半Markov過程，各種類型的排隊(duì)網(wǎng)絡(luò)等（可時(shí)序化、采用仿真方法）DEDS統(tǒng)計(jì)性能層次的研究情況從九十年代開始，統(tǒng)計(jì)性能層次的研究已成為DEDS研究領(lǐng)域的一個(gè)重要方面，主要包括以下兩個(gè)研究方向：系統(tǒng)的性能分析：主要是靈敏度分析優(yōu)化理論和應(yīng)用研究：Markov控制（決策）過程方法及優(yōu)化問題已成為當(dāng)前DEDS領(lǐng)域的一個(gè)令人注目的熱點(diǎn)，也是本課程的主要介紹對(duì)象。拓展：SMDP、POMDP

4、、HMM、HDS建模第二章隨機(jī)離散事件動(dòng)態(tài)系統(tǒng)的基本仿真技術(shù)隨機(jī)變量隨機(jī)變量：粗略的說就是能取不同數(shù)值的量非隨機(jī)的（確定性的數(shù)值，永不改變） ：太陽系中的太陽個(gè)數(shù)隨機(jī)的：一個(gè)人一天接到的 個(gè)數(shù)，每天都不一樣概率實(shí)驗(yàn)（experiment）：考試，擲骰子，打球比賽，扔硬幣一次實(shí)驗(yàn)對(duì)應(yīng)一個(gè)輸出X，考慮實(shí)驗(yàn)的輸出是隨機(jī)變量，可取多個(gè)值。（pass，fail），（1，2，3，4，5，6），（win，lose），（heads，tails）事件：擲骰子，點(diǎn)數(shù)為2，或者為偶數(shù)事件的概率：事件發(fā)生的機(jī)會(huì)（chance）或可能性（likelihood），m次實(shí)驗(yàn)中，事件A發(fā)生n次，則概率為 P(A)=lim m

5、(n/m) 0,1加數(shù)法則（addition law）互斥事件（mutually exclusive）復(fù)合事件（compound）：由互斥事件構(gòu)成，如多次擲骰子中，出現(xiàn)偶數(shù)的事件由分別出現(xiàn)2，4或6的互斥事件構(gòu)成。若復(fù)合事件E由A1，,An構(gòu)成，則P(E)=P( A1)+ P(An)復(fù)雜事件（complex）：未必由互斥事件構(gòu)成，如擲骰子，出現(xiàn)質(zhì)數(shù)（2，3，5）或偶數(shù)（2，4，6）的事件P(AB)=P( A)+ P(B)-P(AB)AB乘積法則（multiplication law）獨(dú)立事件（independent）：兩個(gè)事件中，一個(gè)事件的出現(xiàn)不依賴于另外一個(gè)。反之為相關(guān)事件（dependen

6、t）。扔硬幣，第一次為heads的事件A與第二次為tails的事件B相互獨(dú)立。定義事件E表示第一次為heads且第二次為tails的事件，則P(E)P(A B)=P( A) .P(B)互斥的就無所謂相關(guān)不相關(guān)；非互斥的，則有可能獨(dú)立，則P(A B)=P( A) .P(B)。既不互斥又不獨(dú)立，則P(A B)=P( A) .P(B|A)= P( B) .P(A|B)， 其中，P(B|A)和P(A|B)為條件概率。（若A、B獨(dú)立，則？）概率分布離散變量隨機(jī)變量取值可能是離散的，如1,4.5,18,1969，也可能是連續(xù)的，如區(qū)間0 10。先考慮離散變量離散隨機(jī)變量：擲骰子游戲中，輸出X 1,2,3,

7、4,5,6，其中X為1的概率記P(X=1)=1/6，一般地， P(X=k)=l，對(duì)應(yīng)一個(gè)概率質(zhì)量函數(shù)（Prob. Mass function, PMF），即f(x)，表示概率P(X=x)。P(Xk)=l表示隨機(jī)變量X不超過k的概率為l，該函數(shù)表示累積分布函數(shù) （Cumulative distribution function, CDF，有時(shí)簡(jiǎn)稱分布函數(shù)），記為F(X=k)或F(x)，滿足F(X=k)kx=af(x)（從X的最低可能值a到k的所有pmf值的和）PMF CDF概率分布連續(xù)變量連續(xù)隨機(jī)變量：例如連續(xù)兩次所接 之間的時(shí)間差概率密度函數(shù)（Prob. density function, P

8、DF對(duì)應(yīng)離散情況的PMF），仍記為f(x). 分布函數(shù)滿足隨機(jī)變量的期望值和標(biāo)準(zhǔn)偏差離散隨機(jī)變量的期望值（expected/mean/average value）連續(xù)隨機(jī)變量的期望值均值不能說明一個(gè)隨機(jī)變量任何特性，只有同標(biāo)準(zhǔn)偏差一起才能說明。隨機(jī)性完全體現(xiàn)在PDF、PMF或CDF。標(biāo)準(zhǔn)偏差：隨機(jī)變量對(duì)其均值的平均偏離的估計(jì)，定義標(biāo)準(zhǔn)偏差的平方稱為方差極限定理（Limit Theorems）中心極限定理：強(qiáng)大數(shù)定律：仿真中的基本概念離散事件仿真主要涉及隨機(jī)數(shù)產(chǎn)生和隨機(jī)系統(tǒng)仿真模型動(dòng)態(tài)系統(tǒng)：系統(tǒng)（行為）隨時(shí)間變化狀態(tài)：描述系統(tǒng)（行為）隨時(shí)間變化的物理量。如排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)，庫(kù)存量，帶寬占用率等。支

9、配（控制）變量（governing variable）：動(dòng)態(tài)系統(tǒng)的行為受這些變量支配、控制（操縱），如排隊(duì)系統(tǒng)中的服務(wù)時(shí)間和相鄰顧客到達(dá)時(shí)間間隔。隨機(jī)系統(tǒng)：控制變量是隨機(jī)變量的系統(tǒng)，其行為受隨機(jī)變量支配。模型實(shí)體（模型）：小型飛機(jī)模型，模擬仿真系統(tǒng)抽象（數(shù)學(xué)）模型：方程，函數(shù)，不等式，計(jì)算機(jī)程序等。幫助理解，分析，預(yù)測(cè)系統(tǒng)行為.建模一般基于一些假設(shè)，如系統(tǒng)結(jié)構(gòu)，支配變量的分布。排隊(duì)系統(tǒng)中的指數(shù)服務(wù)和到達(dá)間隔。為研究大規(guī)模復(fù)雜隨機(jī)系統(tǒng)，可用計(jì)算機(jī)程序模擬系統(tǒng)行為（為支配隨機(jī)變量產(chǎn)生隨機(jī)數(shù)），這樣的程序可稱為仿真模型。仿真模型亦可用于優(yōu)化，特別是無法或難以建立數(shù)學(xué)模型時(shí)。產(chǎn)生仿真優(yōu)化。為什么研究隨

10、機(jī)系統(tǒng)很多實(shí)際系統(tǒng)是隨機(jī)系統(tǒng)，如通訊網(wǎng)絡(luò)通過研究，可以改變這些系統(tǒng)，使其更有效運(yùn)行（或降低其運(yùn)行代價(jià)）隨機(jī)系統(tǒng)的仿真模型隨機(jī)系統(tǒng)的建模第一步是要尋找支配隨機(jī)變量的分布。分布的作用：數(shù)學(xué)模型中用于建立表達(dá)式；仿真模型中用于產(chǎn)生隨機(jī)數(shù)，以便計(jì)算機(jī)來模擬系統(tǒng)的行為，即重構(gòu)實(shí)際系統(tǒng)發(fā)生的事件（產(chǎn)生支配隨機(jī)變量的值）。隨機(jī)變量分布的獲?。簭膶?shí)際系統(tǒng)收集數(shù)據(jù)，然后進(jìn)行分布函數(shù)擬合隨機(jī)數(shù)產(chǎn)生-均勻分布隨機(jī)數(shù)的產(chǎn)生（人工產(chǎn)生?。┚€性同余隨機(jī)數(shù)產(chǎn)生（linear congruential generator）Ij+1(aIj mod m): aIj 被m除的余數(shù)， a和m為正整數(shù)，I0小于等于m，Ij0,m是隨

11、機(jī)序列。如a=2, m=20, I0 =12,則有12,4,8,16,12,4,8,16,12,.適當(dāng)選擇a和m，則得到0和m之間的所有整數(shù)序列（m-1個(gè)），第i個(gè)整數(shù)xi代表（決定了）第i個(gè)隨機(jī)數(shù)yi=xi/m，每個(gè)yi的可能性相同（ xi 在原來的序列集里出現(xiàn)一次）。m越大，yi越接近于服從0,1之間均勻分布的自然隨機(jī)數(shù)。I0是種子，能產(chǎn)生的最大隨機(jī)數(shù)個(gè)數(shù)是m-1。若m2321，對(duì)應(yīng)個(gè)數(shù)2147483646隨機(jī)數(shù)產(chǎn)生實(shí)際中，若周期短（m?。瑒t隨機(jī)數(shù)會(huì)重復(fù)，導(dǎo)致結(jié)果變壞（隨機(jī)數(shù)不獨(dú)立，不再服從均勻分布）。Ij+1(aIj mod m)中的aIj可能會(huì)超出計(jì)算機(jī)表達(dá)能力。Schrage逼近因

12、數(shù)分解：Q= a(Ij mod q)-rIj /q，q和r是正整數(shù)隨機(jī)數(shù)產(chǎn)生機(jī)制無需計(jì)算aIj 對(duì)(a, b)間的任何均勻分布，其隨機(jī)數(shù)x都可由(0, 1)之間的隨機(jī)數(shù)y產(chǎn)生: x=a+(b-a)y. （映射！）隨機(jī)數(shù)產(chǎn)生-其它分布逆函數(shù)方法指數(shù)分布的累積分布函數(shù)為產(chǎn)生一個(gè)隨機(jī)數(shù)y，服從（0，1）之間的均勻分布，令其為指數(shù)分布的CDF的值，即F(x)=y反解x，即使用隨機(jī)數(shù)的事件重構(gòu)以單個(gè)服務(wù)臺(tái)排隊(duì)為例，兩個(gè)支配變量：相繼到達(dá)時(shí)間間隔ta。服務(wù)者為一個(gè)顧客的服務(wù)時(shí)間ts。根據(jù)各自分布產(chǎn)生兩個(gè)隨機(jī)序列ta,ts，例如ta=10.1, 2.3, 1, 0.9, 3.5; ts=0.1, 3.2,

13、1.19, 4.9, 1.1.可構(gòu)造兩種事件發(fā)生到達(dá) ta離開空閑：10.1+2.2 ts使用率（utilization）：長(zhǎng)時(shí)段仿真（long run）第三章Markov決策過程基本知識(shí)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節(jié)點(diǎn)出發(fā))：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狀態(tài)序列行動(dòng)序列代價(jià)序列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有關(guān)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第三章動(dòng)態(tài)規(guī)劃（dynamic programming） 動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解多階段決策過程的最優(yōu)化數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家 等人在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理，把多階段過

25、程轉(zhuǎn)化為一系列單階段問題，逐個(gè)求解，創(chuàng)立了解決這類問題的新方法動(dòng)態(tài)規(guī)劃。 多階段決策過程( multi-step decision process ) 指這樣一類特殊的活動(dòng)過程，過程可以按時(shí)間順序分解成若干個(gè)相互聯(lián)系的階段，在每一個(gè)階段都需要做出決策，全部過程的決策是一個(gè)決策序列。最優(yōu)化原理 作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。也就是說，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。模型分類以“時(shí)間”角度可分成： 離散型和連續(xù)型。從信息確定與否可分成： 確定型和隨機(jī)型。從目標(biāo)函數(shù)的個(gè)數(shù)可分成： 單目標(biāo)型和多目標(biāo)型。確定性問題Fig. : The shortest path problem 327941381314Bellman equation(反向遞推)：隨機(jī)問題Bellman equation(反向遞推)： My previous