离散事件动态系统--马尔科夫链PPT课件

课程基本情况 课程性质 非学位课学时数 学分 32 2周学时 4 后面有调整 授课形式 a 主讲面授 c 文献报告和自由讨论应用领域 网络系统分析 移动机器人 智能交通 生产自动化和供应链管理 Agent系统 网络控制优化 机器学习 排队网络 系统可靠性分析 以及其它有关决策优化 控制和智能学习等 前期课程内容 高等数学 概率论 线性代数考核方式 考查 含课程总结 文献汇报 课程内容 离散事件动态系统基本概念 分类 研究方法随机离散事件动态系统的基本仿真技术Markov决策过程 含Markov链 半Markov决策过程 基本知识动态规划 dynamicprogramming 和仿真优化 主要介绍Bellman最优方程 策略迭代和数值迭代 强化学习 reinforcementlearning 技术 主要介绍Monte Carlo方法 TD学习 Q学习和SARSA学习等 神经元 逼近动态规划 neuro dynamicprogramming 多Agent学习探讨实例分析 第一章离散事件动态系统基本概念 分类和研究方法 基本概念 随着高新技术的迅猛发展 现实世界中涌现了大量的复杂人造系统 如计算机网络 通信网络 柔性制造系统 CIMS 交通管理系统 军事指挥系统等 这些系统的共同特征是 系统的演化过程不能由通常的物理定律来描述 而是服从一些由人为规定的复杂规则 并由一系列相互作用的离散事件所决定 这样的一类人造系统常被描述为离散事件动态系统 Discreteeventdynamicsystem DEDS 事件 使DEDS状态发生变动的一个行动或事情 DEDS与一般动态系统的差别 通常的连续变量动态系统 CVDS 其动态特性满足一定的物理定律 可用微分方程或差分方程来描述 例如经典力学下的质点运动方程等可以描述为DEDS基本概念 由一些相互作用的离散事件构成 并且由它们触发而引起状态转移 演化 的一类动态系统 它所含的事件的发生在时间和空间上都是离散的 线性系统 例1柔性制造系统 待加工工件缓冲器 工作台1 已加工工件缓冲器 待加工工件缓冲器 工作台M 已加工工件缓冲器 Sn2 Sn1 智能仓库 自行小车 例2机器人自动装配线 roboticassemblyline 例3开排队网络 服务站1缓冲器 服务站2缓冲器 服务站3缓冲器 通信系统中的接入控制 基本分类和研究方法 DEDS的三个层次模型 逻辑层次模型 确定性 主要有形式语言 有限自动机 Markov链 Petri网等 不可时序化 模型不可赋时 只考虑表征系统行为的符号的顺序关系代数层次模型 确定性 主要有极大极小代数 有限递归过程等 可时序化 统计层次模型 随机性 主要有Markov过程 半Markov过程或广义半Markov过程 各种类型的排队网络等 可时序化 采用仿真方法 DEDS统计性能层次的研究情况 从九十年代开始 统计性能层次的研究已成为DEDS研究领域的一个重要方面 主要包括以下两个研究方向 系统的性能分析 主要是灵敏度分析优化理论和应用研究 Markov控制 决策 过程方法及优化问题已成为当前DEDS领域的一个令人注目的热点 也是本课程的主要介绍对象 拓展 SMDP POMDP HMM HDS 建模 第二章随机离散事件动态系统的基本仿真技术 随机变量 随机变量 粗略的说就是能取不同数值的量非随机的 确定性的数值 永不改变 太阳系中的太阳个数随机的 一个人一天接到的电话个数 每天都不一样 概率 实验 experiment 考试 掷骰子 打球比赛 扔硬币一次实验对应一个输出X 考虑实验的输出是随机变量 可取多个值 pass fail 1 2 3 4 5 6 win lose heads tails 事件 掷骰子 点数为2 或者为偶数事件的概率 事件发生的机会 chance 或可能性 likelihood m次实验中 事件A发生n次 则概率为P A limm n m 0 1 加数法则 additionlaw 互斥事件 mutuallyexclusive 复合事件 compound 由互斥事件构成 如多次掷骰子中 出现偶数的事件由分别出现2 4或6的互斥事件构成 若复合事件E由A1 An构成 则P E P A1 P An 复杂事件 complex 未必由互斥事件构成 如掷骰子 出现质数 2 3 5 或偶数 2 4 6 的事件P A B P A P B P A B A B 乘积法则 multiplicationlaw 独立事件 independent 两个事件中 一个事件的出现不依赖于另外一个 反之为相关事件 dependent 扔硬币 第一次为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 也可能是连续的 如区间 010 先考虑离散变量离散随机变量 掷骰子游戏中 输出X 1 2 3 4 5 6 其中X为1的概率记P X 1 1 6 一般地 P X k l 对应一个概率质量函数 Prob Massfunction PMF 即f x 表示概率P X x P X k l表示随机变量X不超过k的概率为l 该函数表示累积分布函数 Cumulativedistributionfunction CDF 有时简称分布函数 记为F X k 或F x 满足F X k kx af x 从X的最低可能值a到k的所有pmf值的和 PMFCDF 概率分布 连续变量 连续随机变量 例如连续两次所接电话之间的时间差概率密度函数 Prob densityfunction PDF对应离散情况的PMF 仍记为f x 分布函数满足 随机变量的期望值和标准偏差 离散随机变量的期望值 expected mean averagevalue 连续随机变量的期望值 均值不能说明一个随机变量任何特性 只有同标准偏差一起才能说明 随机性完全体现在PDF PMF或CDF 标准偏差 随机变量对其均值的平均偏离的估计 定义 标准偏差的平方称为方差 极限定理 LimitTheorems 中心极限定理 强大数定律 仿真中的基本概念 离散事件仿真主要涉及随机数产生和随机系统仿真模型动态系统 系统 行为 随时间变化状态 描述系统 行为 随时间变化的物理量 如排队系统的队长 库存量 带宽占用率等 支配 控制 变量 governingvariable 动态系统的行为受这些变量支配 控制 操纵 如排队系统中的服务时间和相邻顾客到达时间间隔 随机系统 控制变量是随机变量的系统 其行为受随机变量支配 模型 实体 模型 小型飞机模型 模拟仿真系统抽象 数学 模型 方程 函数 不等式 计算机程序等 帮助理解 分析 预测系统行为 建模一般基于一些假设 如系统结构 支配变量的分布 排队系统中的指数服务和到达间隔 为研究大规模复杂随机系统 可用计算机程序模拟系统行为 为支配随机变量产生随机数 这样的程序可称为仿真模型 仿真模型亦可用于优化 特别是无法或难以建立数学模型时 产生仿真优化 为什么研究随机系统 很多实际系统是随机系统 如通讯网络通过研究 可以改变这些系统 使其更有效运行 或降低其运行代价 随机系统的仿真模型 随机系统的建模第一步是要寻找支配随机变量的分布 分布的作用 数学模型中用于建立表达式 仿真模型中用于产生随机数 以便计算机来模拟系统的行为 即重构实际系统发生的事件 产生支配随机变量的值 随机变量分布的获取 从实际系统收集数据 然后进行分布函数拟合 随机数产生 均匀分布随机数的产生 人工产生 线性同余随机数产生 linearcongruentialgenerator Ij 1 aIjmodm aIj被m除的余数 a和m为正整数 I0小于等于m Ij 0 m 是随机序列 如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 若m 232 1 对应个数2147483646 随机数产生 实际中 若周期短 m小 则随机数会重复 导致结果变坏 随机数不独立 不再服从均匀分布 Ij 1 aIjmodm 中的aIj可能会超出计算机表达能力 Schrage逼近因数分解 Q a Ijmodq r Ij 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 1 19 4 9 1 1 可构造两种事件发生到达ta离开空闲 10 1 2 2ts使用率 utilization 1 12 3 22 79长时段仿真 longrun 10 1 2 3 0 1 第三章Markov决策过程基本知识 Examples Thedeterministicshortestpathproblem Transitionfromonecitytothenextoneisdeterministic Eachcontrol oraction atagivencityleadstoauniqueandcertainsuccessorcityTheobjectiveistofindapathamongallpossiblepaths whichhastheminimumcostThisproblemcanbesolvedeffectivelybydynamicprogramming Fig 2 Theshortestpathproblem Bellmanequation 反向递推 从K节点出发 Examples Stochasticshortestpath SSP problem Transitionfromonestatetothenextoneisstochastic thatisEachactionatagivenstatemayleadtoseveralpossiblesuccessorstates andeachtransition e g fromstateCtostateF willgenerateacost whichmaybedependentontheaction Terminationcity Terminationstate Initialcity initialstate Fig 3Pathprogrammingforasignalincommunicationsystems Examples TransitionforsignalsintheSSPproblems Transitionprobability P E C d Generatedcost 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 d d B C D E F G P F C d f C d F P G C d f C d G Theessenceoftheproblemishowtoreachtheterminationstatewithminimumexpectedcost P E C d f C d E MathematicmodelsforMarkovchains SystemEvolution Decisionepoch tDecisionepoch t 1 Action dt dt 1 Cost ft Xt dt ft 1 Xt 1 dt 1 Xt Xt 1 P Xt 1 Xt dt Markovproperty statetransitionisindependentofthehistory i e transitionfromXttoXt 1isonlydeterminedbycurrentstateXtandselectedactiondt 状态序列行动序列代价序列 MathematicmodelsforMarkovchains Basicmodelparameters MathematicmodelsforMarkovchains Classificationofpolicies MathematicmodelsforMarkovchains Performancecriteria MathematicmodelsforMarkovchains Optimizationproblem Semi Markovdecisionprocesses SMDPs FromMarkovchaintoSMDP basicconceptsforMDP 保守矩阵与策略v有关 Problemformulation 3 optimizationobjective Potential basedoptimizationvianumericalcomputation 1 performancepotential Reinforcementlearningofpotentials Semi Markovdecisionprocesses SMDPs Relationsofdifferentmodels Inmanycases thestudyofaSMDPisrealizedbytransformingtoacontrolledMarkovchain ifthemodelisknownE g suchasapreventiveproblemprovidedinthebook Simulation basedoptimization Fig 5Relationsofdifferentmodels Optimizationmethods difficultproblems Overviewofdifferentoptimizationmethods Numericalcomputation Valueiteration Policyiteration Non LinearprogrammingSimulationmethods Monte Carlomethods Reinforcementlearning Neuro dynamicprogramming Ismodelknown Yes TDlearning model based NO Q learning model free Disadvantages ModelneedtobeknownComputationofmatrixinverseisdifficultforlargescaleproblems Forfinitehorizonmodels backwardinduction dynamicprogramming Optimizationmethods difficultproblems Somevariantsonthebasicmodel Basicandsimplestmodels Markovchains Statespaceandactionsetarebothfinite StochasticprocessisergodicTherearemanyproblemsappearingnow Decisionsmaybemadeincontinuoustime SMDP Theremaybeacontinuumofstatesoractions pact Modelparametersmaynotbeknownoruncertain Robustdecision simulationmethods Systemstatemaybenotobservable POMDPorHMM 第三章动态规划 dynamicprogramming 动态规划是运筹学的一个分支 是求解多阶段决策过程的最优化数学方法 20世纪50年代初美国数学家R E Bellman等人在研究多阶段决策过程的优化问题时 提出了著名的最优化原理 把多阶段过程转化为一系列单阶段问题 逐个求解 创立了解决这类问题的新方法 动态规划 多阶段决策过程 multi stepdecisionprocess 指这样一类特殊的活动过程 过程可以按时间顺序分解成若干个相互联系的阶段 在每一个阶段都需要做出决策 全部过程的决策是一个决策序列 最优化原理作为整个过程的最优策略具有这样的性质 无论过去的状态和决策如何 相对于前面的决策所形成的状态而言 余下的决策序列必然构成最优子策略 也就是说 一个最优策略的子策略也是最优的 模型分类 以 时间 角度可分成 离散型和连续型 从信息确定与否可分成 确定型和随机型 从目标函数的个数可分成 单目标型和多目标型 确定性问题 Fig Theshortestpathproblem 3 2 7 9 4 13 8 13 14 Bellmanequation 反向递推 随机问题 Bellmanequati