离散事件动态系统--马尔科夫链.ppt

2024/5/21 周二计算机学院计算机学院/电气学院电气学院1/51合肥工业大学合肥工业大学课程基本情况n课程性质：非学位课n学时数/学分：32/2 n周学时：4（后面有调整）n授课形式：(a)主讲面授；(c)文献报告和自由讨论n应用领域：网络系统分析、移动机器人、智能交通、生产自动化和供应链管理、Agent系统、网络控制优化、机器学习、排队网络、系统可靠性分析，以及其它有关决策优化、控制和智能学习等。n前期课程内容：高等数学、概率论、线性代数n考核方式：考查（含课程总结、文献汇报）2024/5/21 周二计算机学院计算机学院/电气学院电气学院2/51合肥工业大学合肥工业大学课程内容 1.离散事件动态系统基本概念、分类、研究方法2.随机离散事件动态系统的基本仿真技术3.Markov决策过程（含Markov链，半Markov决策过程）基本知识4.动态规划（dynamic programming）和仿真优化：主要介绍Bellman最优方程，策略迭代和数值迭代。5.强化学习（reinforcement learning）技术：主要介绍Monte-Carlo方法、TD学习、Q学习和SARSA学习等。6.神经元/逼近动态规划（neuro-dynamic programming）7.多Agent学习探讨8.实例分析 2024/5/21 周二计算机学院计算机学院/电气学院电气学院3/51合肥工业大学合肥工业大学第一章离散事件动态系统基本概念、分类和研究方法2024/5/21 周二计算机学院计算机学院/电气学院电气学院4/51合肥工业大学合肥工业大学基本概念n随着高新技术的迅猛发展，现实世界中涌现了大量的复杂人造系统（如计算机网络、通信网络、柔性制造系统、CIMS、交通管理系统、军事指挥系统等）。这些系统的共同特征是：系统的演化过程不能由通常的物理定律来描述，而是服从一些由人为规定的复杂规则，并由一系列相互作用的离散事件所决定。n 这样的一类人造系统常被描述为离散事件动态系统（Discrete event dynamic system，DEDS）。n事件：使DEDS状态发生变动的一个行动或事情。2024/5/21 周二计算机学院计算机学院/电气学院电气学院5/51合肥工业大学合肥工业大学nDEDSDEDS与一般与一般动态系系统的差的差别：通常的连续变量动态系统(CVDS)，其动态特性满足一定的物理定律，可用微分方程或差分方程来描述。例如经典力学下的质点运动方程等可以描述为nDEDSDEDS基本概念基本概念:由一些相互作用的离散事件构成，并且由它们触发而引起状态转移（演化）的一类动态系统,它所含的事件的发生在时间和空间上都是离散的。线性系统2024/5/21 周二计算机学院计算机学院/电气学院电气学院6/51合肥工业大学合肥工业大学例1 柔性制造系统 待加工工件缓冲器工作台1已加工工件缓冲器待加工工件缓冲器工作台M已加工工件缓冲器Sn2Sn1智能仓库自行小车2024/5/21 周二计算机学院计算机学院/电气学院电气学院7/51合肥工业大学合肥工业大学例2 机器人自动装配线（robotic assembly line）2024/5/21 周二计算机学院计算机学院/电气学院电气学院8/51合肥工业大学合肥工业大学例3 开排队网络服务站1缓冲器服务站2缓冲器服务站3缓冲器2024/5/21 周二计算机学院计算机学院/电气学院电气学院9/51合肥工业大学合肥工业大学通信系统中的接入控制2024/5/21 周二计算机学院计算机学院/电气学院电气学院10/51合肥工业大学合肥工业大学基本分类和研究方法DEDS的三个层次模型：n 逻辑层次模型（确定性）主要有形式语言，有限自动机，Markov链，Petri网等(不可时序化）：模型不可赋时，只考虑表征系统行为的符号的顺序关系n 代数层次模型（确定性）主要有极大极小代数，有限递归过程等（可可时序化序化）n 统计层次模型（随机性）主要有Markov过程，半Markov过程或广义半Markov过程，各种类型的排队网络等（可可时序化序化、采用仿真方法）2024/5/21 周二计算机学院计算机学院/电气学院电气学院11/51合肥工业大学合肥工业大学DEDS统计性能层次的研究情况从九十年代开始，统计性能层次的研究已成为DEDS研究领域的一个重要方面，主要包括以下两个研究方向：u系统的性能分析：主要是灵敏度分析u优化理论和应用研究：Markov控制（决策）过程方法及优化问题已成为当前DEDS领域的一个令人注目的热点，也是本课程的主要介绍对象。拓展：SMDP、POMDP、HMM、HDS建模2024/5/21 周二计算机学院计算机学院/电气学院电气学院12/51合肥工业大学合肥工业大学第二章随机离散事件动态系统的基本仿真技术2024/5/21 周二计算机学院计算机学院/电气学院电气学院13/51合肥工业大学合肥工业大学随机变量n随机变量：粗略的说就是能取不同数值的量n非随机的（确定性的数值，永不改变）：太阳系中的太阳个数n随机的：一个人一天接到的电话个数，每天都不一样2024/5/21 周二计算机学院计算机学院/电气学院电气学院14/51合肥工业大学合肥工业大学概率n实验（experiment）：考试，掷骰子，打球比赛，扔硬币n一次实验对应一个输出X，考虑实验的输出是随机变量，可取多个值。n（pass，fail），（1，2，3，4，5，6），（win，lose），（heads，tails）n事件：掷骰子，点数为2，或者为偶数n事件的概率：事件发生的机会（chance）或可能性（likelihood），m次实验中，事件A发生n次，则概率为 P(A)=lim m(n/m)0,12024/5/21 周二计算机学院计算机学院/电气学院电气学院15/51合肥工业大学合肥工业大学加数法则（addition law）n互斥事件（mutually exclusive）n复合事件（compound）：由互斥事件构成，如多次掷骰子中，出现偶数的事件由分别出现2，4或6的互斥事件构成。若复合事件E由A1，,An构成，则P(E)=P(A1)+P(An)n复杂事件（complex）：未必由互斥事件构成，如掷骰子，出现质数（2，3，5）或偶数（2，4，6）的事件P(AB)=P(A)+P(B)-P(AB)AB2024/5/21 周二计算机学院计算机学院/电气学院电气学院16/51合肥工业大学合肥工业大学乘积法则（multiplication law）n独立事件（independent）：两个事件中，一个事件的出现不依赖于另外一个。反之为相关事件（dependent）。扔硬币，第一次为heads的事件A与第二次为tails的事件B相互独立。定义事件E表示第一次为heads且第二次为tails的事件，则P(E)P(A B)=P(A).P(B)n互斥的就无所谓相关不相关；非互斥的，则有可能独立，则P(A B)=P(A).P(B)。n既不互斥又不独立，则P(A B)=P(A).P(B|A)=P(B).P(A|B)，其中，P(B|A)和P(A|B)为条件概率。（若A、B独立，则？）2024/5/21 周二计算机学院计算机学院/电气学院电气学院17/51合肥工业大学合肥工业大学概率分布离散变量随机变量取值可能是离散的，如1,4.5,18,1969，也可能是连续的，如区间0 10。先考虑离散变量n离散随机变量：掷骰子游戏中，输出X 1,2,3,4,5,6，其中X为1的概率记P(X=1)=1/6，一般地，P(X=k)=l，对应一个概率质量函数（Prob.Mass function,PMF），即f(x)，表示概率P(X=x)。nP(Xk)=l表示随机变量X不超过k的概率为l，该函数表示累积分布函数（Cumulative distribution function,CDF，有时简称分布函数），记为F(X=k)或F(x)，满足nF(X=k)kx=af(x)（从X的最低可能值a到k的所有pmf值的和）nPMF CDF2024/5/21 周二计算机学院计算机学院/电气学院电气学院18/51合肥工业大学合肥工业大学概率分布连续变量连续随机变量：例如连续两次所接电话之间的时间差n概率密度函数（Prob.density function,PDF对应离散情况的PMF），仍记为f(x).分布函数满足2024/5/21 周二计算机学院计算机学院/电气学院电气学院19/51合肥工业大学合肥工业大学随机变量的期望值和标准偏差n离散随机变量的期望值（expected/mean/average value）n连续随机变量的期望值n均值不能说明一个随机变量任何特性，只有同标准偏差一起才能说明。随机性完全体现在PDF、PMF或CDF。n标准偏差：随机变量对其均值的平均偏离的估计，定义n标准偏差的平方称为方差2024/5/21 周二计算机学院计算机学院/电气学院电气学院20/51合肥工业大学合肥工业大学极限定理（Limit Theorems）n中心极限定理：n强大数定律：2024/5/21 周二计算机学院计算机学院/电气学院电气学院21/51合肥工业大学合肥工业大学仿真中的基本概念n离散事件仿真仿真主要涉及随机数产生和随机系统仿真模型n动态系系统：系统（行为）随时间变化n状状态：描述系统（行为）随时间变化的物理量。如排队系统的队长，库存量，带宽占用率等。n支配（控制）支配（控制）变量量（governing variable）：动态系统的行为受这些变量支配、控制（操纵），如排队系统中的服务时间和相邻顾客到达时间间隔。n随机系随机系统：控制变量是随机变量的系统，其行为受随机变量支配。2024/5/21 周二计算机学院计算机学院/电气学院电气学院22/51合肥工业大学合肥工业大学模型n实体（模型）体（模型）：小型飞机模型，模拟仿真系统n抽象（数学）模型抽象（数学）模型：方程，函数，不等式，计算机程序等。帮助理解，分析，预测系统行为.n建模建模一般基于一些假设，如系统结构，支配变量的分布。排队系统中的指数服务和到达间隔。n为研究大规模复杂随机系统，可用计算机程序模拟系统行为（为支配随机变量产生随机数），这样的程序可称为仿真模型。n仿真模型亦可用于优化，特别是无法或难以建立数学模型时。产生仿真优化。2024/5/21 周二计算机学院计算机学院/电气学院电气学院23/51合肥工业大学合肥工业大学为什么研究随机系统n很多实际系统是随机系统，如通讯网络n通过研究，可以改变这些系统，使其更有效运行（或降低其运行代价）2024/5/21 周二计算机学院计算机学院/电气学院电气学院24/51合肥工业大学合肥工业大学随机系统的仿真模型n随机系统的建模第一步是要寻找支配随机变量的分布。n分布的作用：数学模型中用于建立表达式；仿真模型中用于产生随机数，以便计算机来模拟系统的行为，即重构实际系统发生的事件（产生支配随机变量的值）。n随机变量分布的获取：从实际系统收集数据，然后进行分布函数拟合2024/5/21 周二计算机学院计算机学院/电气学院电气学院25/51合肥工业大学合肥工业大学随机数产生-均匀分布随机数的产生（人工产生！）线性同余随机数性同余随机数产生生（linear congruential generator）nIj+1(aIj mod m):aIj 被m除的余数，a和m为正整数，I0小于等于m，Ij0,m是随机序列。如a=2,m=20,I0=12,则有12,4,8,16,12,4,8,16,12,.n适当选择a和m，则得到0和m之间的所有整数序列（m-1个），第i个整数xi代表（决定了）第i个随机数yi=xi/m，每个yi的可能性相同（xi 在原来的序列集里出现一次）。m越大，yi越接近于服从0,1之间均匀分布的自然随机数。nI0是种子，能产生的最大随机数个数是m-1。若m2321，对应个数21474836462024/5/21 周二计算机学院计算机学院/电气学院电气学院26/51合肥工业大学合肥工业大学随机数产生n实际中，若周期短（m小），则随机数会重复，导致结果变坏（随机数不独立，不再服从均匀分布）。nIj+1(aIj mod m)中的aIj可能会超出计算机表达能力。nSchrage逼近因数分解：Q=a(Ij mod q)-rIj/q，q和r是正整数n随机数产生机制无需计算aIj n对(a,b)间的任何均匀分布，其随机数x都可由(0,1)之间的随机数y产生:x=a+(b-a)y.（映射！）2024/5/21 周二计算机学院计算机学院/电气学院电气学院27/51合肥工业大学合肥工业大学随机数产生-其它分布逆函数方法n指数分布的累积分布函数为1.产生一个随机数y，服从（0，1）之间的均匀分布，令其为指数分布的CDF的值，即F(x)=y2.反解x，即2024/5/21 周二计算机学院计算机学院/电气学院电气学院28/51合肥工业大学合肥工业大学使用随机数的事件重构n以单个服务台排队为例，两个支配变量：n相继到达时间间隔ta。n服务者为一个顾客的服务时间ts。n根据各自分布产生两个随机序列ta,ts，例如ta=10.1,2.3,1,0.9,3.5;ts=0.1,3.2,1.19,4.9,1.1.n可构造两种事件发生n到达 tan离开n空闲：10.1+2.2 tsn使用率（utilization）：1-12.3/22.79n长时段仿真（long run）10.12.3-0.12024/5/21 周二计算机学院计算机学院/电气学院电气学院29/51合肥工业大学合肥工业大学2024/5/21 周二计算机学院计算机学院/电气学院电气学院30/51合肥工业大学合肥工业大学第三章Markov决策过程基本知识2024/5/21 周二计算机学院计算机学院/电气学院电气学院31/51合肥工业大学合肥工业大学Examples The deterministic shortest path problem nTransition from one city to the next one is deterministic:Each control(or action)at a given city leads to a unique and certain successor citynThe objective is to find a path among all possible paths,which has the minimum costnThis problem can be solved effectively by dynamic programmingTermination cityInitial cityFig.1Path programming for a traveling sales man 2024/5/21 周二计算机学院计算机学院/电气学院电气学院32/51合肥工业大学合肥工业大学Fig.2:The shortest path problem 327941381314Bellman equation(反向递推，从K节点出发)：2024/5/21 周二计算机学院计算机学院/电气学院电气学院33/51合肥工业大学合肥工业大学Examples Stochastic shortest path(SSP)problem nTransition 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(Termination state)Initial city(initial state)Fig.3 Path programming for a signal in communication systems 2024/5/21 周二计算机学院计算机学院/电气学院电气学院34/51合肥工业大学合肥工业大学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(C,d,F)P(G|C,d);f(C,d,G)nThe essence of the problem is how to reach the termination state with minimum expected costP(E|C,d);f(C,d,E)2024/5/21 周二计算机学院计算机学院/电气学院电气学院35/51合肥工业大学合肥工业大学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,dt)nMarkov 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状态序列行动序列代价序列2024/5/21 周二计算机学院计算机学院/电气学院电气学院36/51合肥工业大学合肥工业大学Mathematic models for Markov chainsBasic model parameters2024/5/21 周二计算机学院计算机学院/电气学院电气学院37/51合肥工业大学合肥工业大学Mathematic models for Markov chains Classification of policies 2024/5/21 周二计算机学院计算机学院/电气学院电气学院38/51合肥工业大学合肥工业大学Mathematic models for Markov chains Performance criteria 2024/5/21 周二计算机学院计算机学院/电气学院电气学院39/51合肥工业大学合肥工业大学Mathematic models for Markov chainsOptimization problem 2024/5/21 周二计算机学院计算机学院/电气学院电气学院40/51合肥工业大学合肥工业大学Semi-Markov decision processes(SMDPs)From Markov chain to SMDP 一次仿真：2024/5/21 周二计算机学院计算机学院/电气学院电气学院41/51合肥工业大学合肥工业大学basic concepts for MDP保守矩阵与策略v有关2024/5/21 周二计算机学院计算机学院/电气学院电气学院42/51合肥工业大学合肥工业大学Problem formulation(3)optimization objective2024/5/21 周二计算机学院计算机学院/电气学院电气学院43/51合肥工业大学合肥工业大学Potential-based optimization via numerical computation(1)performance potential2024/5/21 周二计算机学院计算机学院/电气学院电气学院44/51合肥工业大学合肥工业大学Reinforcement learning of potentials2024/5/21 周二计算机学院计算机学院/电气学院电气学院45/51合肥工业大学合肥工业大学Semi-Markov decision processes(SMDPs)Relations of different models MDPContinuous-time MDPDiscrete-time MDP(Markov chain)SMDPnIn many cases,the study of a SMDP is realized by transforming to a controlled Markov chain,if the model is knownE.g.,such as a preventive problem provided in the book Simulation-based optimizationFig.5 Relations of different models 2024/5/21 周二计算机学院计算机学院/电气学院电气学院46/51合肥工业大学合肥工业大学Optimization methods&difficult problems Overview of different optimization methodsnNumerical computation Value iteration Policy iteration (Non)Linear programming nSimulation 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 induction(dynamic programming)2024/5/21 周二计算机学院计算机学院/电气学院电气学院47/51合肥工业大学合肥工业大学Optimization methods&difficult problems Some variants on the basic modelnBasic and simplest models:Markov chains State space and action set are both finite Stochastic process is ergodicnThere are many problems appearing now!Decisions may be made in continuous time SMDP There may be a continuum of states or actions pact Model parameters may not be known or uncertain Robust decision/simulation methods System state may be not observable POMDP or HMM2024/5/21 周二计算机学院计算机学院/电气学院电气学院48/51合肥工业大学合肥工业大学第三章动态规划（dynamic programming）2024/5/21 周二计算机学院计算机学院/电气学院电气学院49/51合肥工业大学合肥工业大学 动态规划是运筹学的一个分支，是求解多阶段决策过程的最优化数学方法。20世纪50年代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类问题的新方法动态规划。2024/5/21 周二计算机学院计算机学院/电气学院电气学院50/51合肥工业大学合肥工业大学n多多阶段决策段决策过程程(multi-step decision process)指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。n最最优化原理化原理 作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。2024/5/21 周二计算机学院计算机学院/电气学院电气学院51/51合肥工业大学合肥工业大学模型分类以以“时间”角度可分成角度可分成：离散型和连续型。从信息确定与否可分成从信息确定与否可分成：确定型和随机型。从目从目标函数的个数可分成函数的个数可分成：单目标型和多目标型。2024/5/21 周二计算机学院计算机学院/电气学院电气学院52/51合肥工业大学合肥工业大学确定性问题Fig.:The shortest path problem 327941381314Bellman equation(反向递推)：2024/5/21 周二计算机学院计算机学院/电气学院电气学院53/51合肥工业大学合肥工业大学随机问题Bellman equation(反向递推)：2024/5/21 周二计算机学院计算机学院/电气学院电气学院54/51合肥工业大学合肥工业大学My previous work Potential-based policy iterationBy solving Poisson equationor by estimate/learning via simulationPolicy evaluationPolicy improvementFig.6 Illustration of policy iteration 2024/5/21 周二计算机学院计算机学院/电气学院电气学院55/51合肥工业大学合肥工业大学My previous work Potential-based learning optimizationReal/simulation environmentPolicy updatingPolicy evaluation(potential learning)Feedback of stateand costActionLearning value ofpotentialsEnvironmentAgentFig.7 PI based on learning2024/5/21 周二计算机学院计算机学院/电气学院电气学院56/51合肥工业大学合肥工业大学样本轨道学习2024/5/21 周二计算机学院计算机学院/电气学院电气学院57/51合肥工业大学合肥工业大学Neuro-dynamic programming(NDP)函数值逼近 Neural network/Approximation mapParameter vector rApproximate cost-to-goof state j State j2024/5/21 周二计算机学院计算机学院/电气学院电气学院58/51合肥工业大学合肥工业大学Neuro-dynamic programming(NDP)分类和逼近结构critic-NDPactor-NDPstateFig.4 approximation of potential and policy2024/5/21 周二计算机学院计算机学院/电气学院电气学院59/51合肥工业大学合肥工业大学Potential-based optimization via simulation parameterized learning of potentials and policy2024/5/21 周二计算机学院计算机学院/电气学院电气学院60/51合肥工业大学合肥工业大学Potential-based optimization via simulation illustration of NDP methodsFig.5 Actor-critic NDP methods2024/5/21 周二计算机学院计算机学院/电气学院电气学院61/51合肥工业大学合肥工业大学Numerical example robust problems (a)(b)Fig.6 Optimal robust performance for different discount factor (a)dependent case;(b)independent case Consider uncertain SMDPs(3-order hyperexponential distribution)