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

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

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

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

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

5、(n/m) 0,1加數(shù)法則（addition law）互斥事件（mutually exclusive）復合事件（compound）：由互斥事件構(gòu)成，如多次擲骰子中，出現(xiàn)偶數(shù)的事件由分別出現(xiàn)2，4或6的互斥事件構(gòu)成。若復合事件E由A1，,An構(gòu)成，則P(E)=P( A1)+ P(An)復雜事件（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）獨立事件（independent）：兩個事件中，一個事件的出現(xiàn)不依賴于另外一個。反之為相關事件（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，也可能是連續(xù)的，如區(qū)間0 10。先考慮離散變量離散隨機變量：擲骰子游戲中，輸出X 1,2,3,

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

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

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

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

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

12、數(shù)分解：Q= a(Ij mod q)-rIj /q，q和r是正整數(shù)隨機數(shù)產(chǎn)生機制無需計算aIj 對(a, b)間的任何均勻分布，其隨機數(shù)x都可由(0, 1)之間的隨機數(shù)y產(chǎn)生: x=a+(b-a)y. （映射！）隨機數(shù)產(chǎn)生-其它分布逆函數(shù)方法指數(shù)分布的累積分布函數(shù)為產(chǎn)生一個隨機數(shù)y，服從（0，1）之間的均勻分布，令其為指數(shù)分布的CDF的值，即F(x)=y反解x，即使用隨機數(shù)的事件重構(gòu)以單個服務臺排隊為例，兩個支配變量：相繼到達時間間隔ta。服務者為一個顧客的服務時間ts。根據(jù)各自分布產(chǎn)生兩個隨機序列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ā)生到達 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節(jié)點出發(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)序列行動序列代價序列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第三章動態(tài)規(guī)劃（dynamic programming） 動態(tài)規(guī)劃是運籌學的一個分支，是求解多階段決策過程的最優(yōu)化數(shù)學方法。20世紀50年代初美國數(shù)學家 等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，把多階段過

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