（控制科学与工程专业论文）奇异摄动markov决策过程的优化算法.pdf

摘要 m & r k o v 决策过程作为离散事件系统优化理论的一个重要的分支，并且广泛的应用于 诸如，排队网络，计算机和通信网络中在实际的问题中，系统一般具有大规模状态空间 对于具有大规模状态空间的m a r k o v 决策过程的优化算法也日益成为m a r k o v 决策过程研 究的一个重要课题在对于此类问题的研究中，早期提出的一般的值迭代的方法和策略 迭代的方法会伴随着状态数量的增加而产生计算量和存储量的快速增长实至今日，”状 态灾“问题仍然是m a r k o v 决策过程研究中的一个具有挑战性的问题、而且现在对于”状态 灾：的问题也没有有效的通用的算法 在本文中，介绍了一类基于样本轨道的优化算法，而且该算法的最大的特点是针对 于一类具有特殊结构的m a r k o v 决策过程即，奇异摄动m a r k o v 过程该过程的状态空间 可以分解成为若干个互不相交的子空间的并，这些子状态空间之间的相互转移的概率远 远低于每个子空间内的元素之间的转移概率奇异摄动m a r k o v 过程的特点在于它的层次 性的结构，第一层次是子状态空间的状态转移，第二层次是子状态子空间之间的转移 m a r k o v 决策过程的优化算法中有一类基于仿真的梯度算法在这一类算法中，首 先通过己知的概率转移矩阵，生成一条样本轨道，这里，样本轨道也可以通过实际系统 的在线运行得到：这条样本轨道可以看作是摄动过程的状态序n s 。，5 ，s 。，s 。一其 中s 。为摄动m a r k o v 过程的状态之一；通过随着时间演化的状态，这一类算法可以得到一 系列相对于报酬的梯度的逼近值，经过证明可以知道，这些不断更新的梯度估计值将收 敛到理论值通过最终得到的梯度值，可以用它对参数进行优化、即，通过梯度的方向对 参数进行寻优在这篇文章中，将给出一个基于摄动m a r k o v 过程生成的样本轨道的优化 算法，在这个优化算法中，不同于以往的算法，并不是在每个状态或是设定的常返状态出 进行梯度的更新，而是将每一个子状态空间占据的样本轨道的一段作为一个整体，在子 空间转移的时候对梯度进行更新，并且根据更新后的梯度对于参数进行寻优这样依赖 于聚集后的状态空间，可以得到一个更加节省计算量的优化算法 其后，在近一步的讨论中将给出m a r k o v 决策过程中称为可聚集的性质、在这个性质 下，可以判定一类可聚集的m a r k o v 决策过程，即，可以通过一系列的变换得到一个具有 较小状态状态空间的m a r k o v 决策过程，和一个聚集后的报酬函数，状态转移矩阵，等 该类过程和奇异摄动m a r k o v 过程之间的相互联系也将在后面给出同时，一些奇异摄 动m a r k o v 决策过程的实际应用，例如，其在混合系统中的应用，包括l q g 问题的最优控 制，还有些稳定性问题；还有奇异摄动m a r k o v 决策过程在h a m i l t o n 环问题中应用 关键词：奇异摄动m a r k o v 过程，基于仿真的优化，梯度更新，状态聚集，可聚 集性，多程序处理系统，混合系统 a b s t r a c t m a r k o vd e c i s i o np r o c e s s e s a sak i n do fo p t i m i z a t i o nm e t h o d su s e di nd i s c r e t ee v e n t s y s t e m s ，h a v eb e e nw e t ld i s c u s s e di ns o m ep r a c t i c a la r e & 8 ，s u c ha s ，q u e u e i n gn e t w o r ka n d c o m p u t e ra n dt e l e c o m m u h i e a t i o nn e t w o r k si nm o s to ft h ep r a c t i c a lp r o b l e m ，t h es y s t e m s c a nn o td e s c r i b e db yas i m p l es t a t es p a c e ，b u tag r e a ts t a t es p a c e s om a r k o vd e c i s i o n p r o c e s s e sw i t hag r e a ts t a t es p a c eb e c o m i n gai m p o r t a n tr e s e a r c ha r e a i nt h i sc a s e ， s o m ef r o r mm e t h o d sw i l lc a u s eai n c r e m e n to fc o m p u t a t i o n a la m o u n tw h e nt h en u m b e ro f s t a t e si n c r e a s e st i l ln o w t h e ”c u r s eo fd i m e n s i o n ”i ss t i l l8k e yr e s e a r c ht o p i ci nm a r k o v d e c i s i o np r o b l e m a n dt h e r ei sn os u e hag e n e r a lm e t h o dc a nb eu s e da sap a n a c e a i nt h i st h e s i s ac l a s so fs a m p l ep a t hb a s e do p t i m i z a t i o na l g o r i t h m si si n t r o d u c e d t h em o s tl m p o r t a n tp r o p e r t yo ft h e s ea l g o r i t h m si st h e i rh i e r a r c h i c a ls t r u c t u r e w h i c h c a nl c a dt oad e c o m p o s a b i l i t yo fs t a t es p a c e s t h es t a t es p a c e sc a nb ed i v i d e dt oas e r i e so f s u b s e t sa n dt h et r a n s i t i o n sa m o n gt h e s es u b s e t sa r em u c hl e s st h a nt h et r a n s i t i o n sa m o n g s t a t e si nt h e s es u b s e t s m o s to ff o r ms t u d i e sa r ef o c u s e do nt h et o p i co ft h e o r e t i cr e s u l t a n ds t b c h a s t i cp r o p e r t i e so fs i n g u l a r l yp e r t u r b e dm a r k o vp r o c e s s e s f u r t h e r m o r e ，s o m e a s y m p t o t i cp r o p e r t i e sa l s oh a v eb e e nt h o r o u 【g hi n v e s t i g a t e dh o w e v e r ，t h e s er e s e a r c h e s a r es t i l lf a ra w a yf r o mt h es t u d yo fd e c i s i o no rr e w a r dp r o c e s s e sa n do p t i m i z a t i o nt h e o r y s ot h a tt h e yc a r lb eu s e di nt h ea r e ao fm a r k o vd e c i s i o np r o c e s s e s i nt h ea l g o r i t h m so fm a r k o vd e c i s i o np r o c e s s e s t h e r ei sak i n do fa l g o r i t h m sc a l l e d s i m u l a t i o n b a s e do p t i m i z a t i o na l g o r i t h m i nt h e s ea l g o r i t h m s ，f i r s t l y ，as a m p l ep a t h i s g e n e r a t e db ys t a t e t r a n s i t i o nm a t r i x w h e r et h es a m p l ep a t h i sa l s oc a nb ea c q u i r e db yt h ee v o l u t i o no fr e a ls y s t e m s 、a n di tc a nb es e e na sas e q u e n c eo fs t a t e sa s s o ，s l ：一，s n ，c d o t s ，i nw h i c he v e r y 鼠i sas t a t eo fs i n g u l a r l yp e r t u r b e dm a r k o vc h a i n w i t ht h et i m eg o i n go n 、t h ea l g o r i t h mc a na p p r o a c has e r i e so fa p p r o x i m a t i o n so ft h eg r a d i e n ti tc a nb ep r o v e dt h a tt h e s ea p p r o x i m a t i o n sc a nb ec o n v e r g e n tt oat h e o r e t i cv a l u e t h e nw i t ht h ef i n a lg r a d i e n t a no p t i m i z a t i o no fp a r a m e t e r sc a nb ed e r i v e d ，eg w i t ht h e d i r e c t i o no ft h eg r a d i e n t ，t h eb e s tv a l u ec a nb es e a r c h e df o r i nt h i st h e s i s ，as a m p l ep a t h b a s e do p t i m i z a t i o na l g o r i t h mw i l lb ep r o p o s e d ，a n dt h es a m p l ep a t hi sg e n e r a t e db ya s i n g u l a r l yp e r t u r b e dm a r k o vc h a i nd i f f e r i n gf r o mo t h e ra l g o r i t h m s ，g r a d i e n tu p d a t i n g w i l ln o tp e r f o r m e di de v e r ys t a t e so rf i x e dr e c u r r e n ts t a t e 、b u tt a k ee v e r ys e g m e n to ft h e s a m p l ep a t hd o m i n a t e db ys t a t e sf r o mac e r t a i ns u b s p a c ea sa ne n t i t y ) a n dt h et r a n s i t i o na m o n gt h e s ee n t i t i e sw i l lc a u s eag r a d i e n tu p d a t i n ga c c o r d i n gt ot h eu p d a t i n g ：t h e o p t i m i z e dv a l u ei sa p p r o a c h e d a n dal e s sc o m p u t a t i o n a la m o u n tw i l lb ec o s t f i n a l l yl,thel u m p a b i l i t yo fm a r k o vd e c i s i o np r o c e s s e s w i lb ed i s c u s s e d t h e d e f i n i t i o no fl u m p a b i l i t yc a nb e u s e da saj u d g e m e n tw h e t h e ram a r k o vd e c i s i o n p r o c e s sc a nb ea g g r e g a t e do rn o t ，eg a f t e rat r a n s f o r m ，am a r k o vd e c i s i o np r o c e s s c a nb ec h a n g e dt oa n o t h e rp r o b l e mw i t has m a l l e rs t a t e s p a c e c o n s e q u e n t l y i t s r e w a r dm e t r i c ，t r a n s i t i o nm a t r i xw i l lb et r a n s f o r m e d ，t o o m e a n w h i l e ，t h e r ew i l lb e f o l l o w d ds o m ep r a c t i c a lv a l u eo fs i n g u l a r l yp e r t u r b e dm a r k o vc h a i n f o re x a m p l e ， t h eo p t i m a lc o n t r o lf o rt h el q gp r o b l e mo fh y b r i ds y s t e m s ；s o m es t a b i l i z a t i o np r o b l e mi nh y b r i ds y s t e m s ；a n ds i n g u l a r l yp e r t u r b e dm a r k o vc h a i ni nh a m i l t o nc y c l ep r o b l e m k e yw o r d s ：s i n g u l a r l yp e r t u r b e dm a r k o vd e c i s i o np r o c e s s e s ( s p m r p ) ，s i m u l a t i o n b a s e d o p t i m i z a t i o n ，g r a d i e n tu p d a t i o n ，s t a t ea g g r e g a t i o n ，l u m p a b i l i t y ，m u l t i p r o g r a m m i n gp r o c e s s i n gs y s t e m s ，h y b r i ds y s t e m s 插图目录 插图目录 1 - 1 两系统串联图示一 2 - 1 具有参数和代价函数的多程序系统 3 - 1 状态聚集算法 3 2 原算法的结果 4 1 具有可聚集性的排队系统示意图 4 - 2 仿真的性能结果比较 4 - 3 具仿真的性能结果的局部比较 加 缸s ； 如姐 第一章m a r k e r 决策过程豹简介与数学基础 第一章m a r k o v 决策过程的简介与数学基础 1 1m a r k o v 决策过程的介绍 作为研究随机序列决策模型的一种重要的数学手段：m a r k o v 决策过程f m a r k o vd e c i s i o np r o c e s s e s ，简i p n m d p ) 越来越受到优化理论研究工作者的重视对于m d p 的研究 可以追溯到上世纪六十年代之前，当时，伴随着随机过程理论：规划理论和它们在实际 工程中的应用，m d p 的一系列的基本概念以及最优解的存在性陆续的被提出和得以证 明 1 】六十年代之后，随着对于排队系统，柔性制造模型等相关领域研究的深入m d p 成 为随机运筹学和应用概率的一门重要的分支时至今曰，m d p 已经广泛的应用于人工智 能和通信网络等相关领域 而m d p 作为描述和解决此类问题的一个重要手段得到了足够的重视与发展这种发 展的表现之一就是：不仅大量的理论结果得以推广，而且大量可以应用到离散事件系统 中的算法和针对这些算法的速度和稳定性的改进结果也相继得到 在众多的实际系统，如计算机网络，通信网络，柔性生产和制造系统，和管理系统中，存 在着大量的人造性质，都需要运用离散事件动态系统( d i s c r e t ee v e n td y n a m i cs y s t e r n s 简记为d e d s ) 来分析系统的行为【2 ，以达到控制和优化系统的目标同时，由于作为研 究d e d s 的重要的数学基础，m d p 的优化和控制算法本身的及其实用性也成为此类研究 不可避免的问题 11 1m a r k o v 过程的定义 首先，简要的给出m a r k o v 过程的定义3 1 假设 x 。( u ) ，n = 0 ，1 ，2 ，) 是定义在概率空间( q ，p ) 上，取值为非负整数集s 的 随机序列用五；= i 表示在时刻n 过程位于状态i 的这一事件i 己p q ( n ) = p ( 咒”i = j l x , 。= i ) ，通常称为过程的一步转移概率如果对于v 。l ，i 2 ，一i l ，i ，j s ，n o 均有： p ( 又j + 1 = j 1 ) ( = i ，x i = i k ，女= 1 ，2 ，-，n 一1 ) = p 玎( 佗) 此处要求v ( x 。= j ，一i ，k = 1 ，2 ，一，n 一1 ) ，则称过程 x 。) ，n = 0 ，l ，2 ，) 是 一个离散时问的m a r k o v 链当( n ) 与起始时刻无关时，称 ) ，n = 0 ，1 ，2 ，) 为齐 次m a r k o v 链，并且简记p 。，( s j j p q - 又称p = ( p 。，) 为该过程的一步转移矩阵或转移概率矩 阵 考虑一个如文献【4 】描述的正常返的，不可约的m a r k o v 过程x = x t ；t o ) ，它具有 一个有限空间s = 1 ，2 ，礼) ，状态间的转移概率矩阵q p i b ；，】。一厶。由 文献h 中定理5 2 3 可知，s 存在唯一的稳态分布用 = ( ”l ，7 r 2 ，”。) 表示过程s 的稳态 概率向量后文中用 表示n 维欧氏空间且简记爬1 = 豫设e 。= ( 1 ，1 ，1 ) 为一个分量 1 1m a j k o v 决策过程的介绍 全为l 的n 维向量由m a r k o v 过程理论可知 7 r e 。= 1 ，q e 。= 0 ，q = 0 ( 1 1 ) 考察取值在非负整数集s 上的随机过程 x c ，t t ：一【0 ，+ 。) ) ，如果对一切t 中 的t l t 2 o 时，可以定义 p i j ( s ，t ) = p ( 溉= j i 咒= i ) ，s t 并称它为系统在状态i 的条件下，t 时刻转移到状态j 的转移概率若上式只与t s 相关，则 称它为齐次转移概率矩阵 112m a r k o v 决策过程的数学模型 在这介绍性的章内，插入了这样充满公式的一节是为了给m d p 做一个准 确的定义只有充分了解这里的定义后，基于数学的研究才能展开，下一章中对于摄 动m d p 的介绍才能更加流畅这里介绍最为基本的离散时间m a r k o v 决策过程的数学模 型为了描述的简单，假定在时刻点n = 0 ，1 ，2 ，处观测系统，这里n 可以是个有限 值n = 0 1 ， ，n + 。或依次取遍所有的非负整数，eg 时间可以到达无穷远的未来 使用文章i s l 中相同的符号，考虑一个离散时i 司m a r k o v 链 h ) 。，o ，其状态空间可以为 一个有限的状态集合s = 0 ) b 该m a r k o v 链的参数，用于对系统的 结构的描述；该m a r k o v 链的状态空间为s = 1 ，2 ，j v ) 假设在时刻t o ，其中= 0 ，l ，t e ，系统的状态转移概率矩阵为： p ( ) 一p ( k ) + q ( k )( 2 - 1 ) 其中p ( ) 为一个状态转移概率矩阵，q ( ) 为一个转移率矩阵生成- 子( g e n e r a t o r ) ，即q ( ) e 爵= 0 ，这里o = ( 0 ，- ，0 ) r ”在文中，对于每个时刻k 的生成子q ( k ) = ( q i ：( a ) ) v 。n 以下条件： q 。，( k ) 0 ，i j ，q 。( k ) ；o i = 1 对每个状态i = l ，2 ，成立 首先，使用概率向量 z ( 七) = ( p ( x ；一1 ) ，- - ，p ( x l = ) ) 1 。 ( 2 - 2 ) 来进一步说明各种渐近性质，并且满足下面这个向量值差分方程( v e c t o r v a l u e dd i f f e r e n c e e q u a t i o n ) ： z ( + 1 ) = x e ( ) p e ( ) ，= 0 ，1 ，t e ， ( k ) = 。o = ( z o ，1 ，- ，z o ，)( 2 - 3 ) 使得