（模式识别与智能系统专业论文）半markov控制过程的性能灵敏度分析、优化及其算法研究.pdf

摘要 本文的主要工作是，将m a r k o v 性能势理论推广到了半m a r k o v 过程，在 此基础上，讨论了一类具有可数状态空间的半m a r k o v 控制过程的稳态性能灵 敏度分析和优化问题，并给出了优化算法。 首先利用等价无穷小矩阵，定义了半m a r l c o v 过程的p o i s s o n 方程，并由 p o i s s o n 方程的解定义了半m a r l ( 0 v 过程的性能势：在此基础上，利用等价 m a r k o v 过程平嵌入m a r k o v 链的方法，讨论了半m a r l 【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 控制过程在无限水平平均代价准则下的最优平稳策略问 题。通过平衡方程和p o i s s o n 方程，给出了基于性能势的比较原理和平均代价 最优性方程，并在较弱的假设条件下证明了最优性方程在紧致行动集上解的 存在性定理。给出了求解最优( 次最优) 平稳策略的理论优化算法，包括梯 度算法，策略迭代算法和数值迭代算法并证明了算法的收敛性。 这些基于直接计算的优化方法，依赖于系统的精确模型，并且涉及到大 量矩阵求逆运算，对状态空间很大、存在“维数灾”的实际系统，矩阵求逆 运算将占用较多的内存空间和计算时间：而且有的实际系统，其模型参数可 能h i 完全可知，即存在所谓的“模型灾”问题。对这样的系统，基丁直接计 算的优化方法不再适用，需要考虑仿真方法利用仿真或观测实际系统得到 的样本轨道的信息来估计有关参数。 为了发展基丁仿真的优化方法，我们从样本轨道上利用实现因子定义了 半m a r k o v 过程的性能势，证明了其满足p o i s 9 0 n 方程即与利用等价m a r k o v 过程的方法定义的性能势是一致的，并给出了基于样本轨道的估计公式，由 此讨论了基于样本轨道的仿真优化算法，这些算法可用于解决大规模实际系 统q j 存在的“维数灾”或“模型灾”问题。 另外，我们注意到，半m a r k o v 控制过程的优化算法中，大部分的运算涉 及到矩阵和向量的运算，这些运算具有很好的并行性，并且性能势也可以根 据样本轨道并行估计。因此我们建立了相应的并行算法，用来解决计算机的 内存容量限制问题和运算时间问题，加快了寻优速度。 文巾给出了大量数值例子，另外我们给出了个半m a r k o v 过程的实际应 用的例子，讨论了m g ，1 排队系统的性能灵敏度分析和优化问题。 a b s t r a c t l nt h i st h e s i s ，t h e p e r f 0 丌n 强c ep o t e n t i a lt h e o r yw a se s t a b l i s h e df o r s e m i m a r k o vp r o c e s s e s b a s e do nt h ep e r f o m a n c ep o t e n t i a l s ，m ep m b l e m so ft h e s t e a d y - s t a t ep e r f o n l l a n c es e n s i t i v i t ya n a l y s i sa n dc h eo p t i m i z a t i o nf o rac l a s so f s e m i m a r k o vc o n 仃d 1p r o c e s s e sw i t hc o u n t a b l es t a t es p a c e sa n di n 6 n i t eh o r i z o n a v e r a g e c o s tp e r f b 珊a n c em e a s u r ew e r ed i s c u s s e d ，如ds o m eo d t i m i z a t j o n a i g o f j t h m sw e r ep r o v i d e d b ya ne q u j v a l e n tm a r k o vp r o c e s s ，t h ep o i s s o ne q u a t i o df o rs e m i m a r k o v p r o c e s sw a se s t a b l i s h e d ，a n dt h es o l u t i 伽st ot h ep o i s s o ne q u a t i o nw a sd e 6 n e da s m ep e r f o r m a n c ep o t e n t i a i so fs e m i m a r k o vp m c e s s e s t h ep r o b l e m so ft 1 1 e s t e a d y - s t a t ep e r f o 册a n c es e n s i t i v i t yw a sd j s c u s s e dt l l r o u g hm em e m o do f e q u i v a l e n tm a r k o vp m c e s s 锄de m b e d d e dm a r k o vc h a i n ，飙dt 圭i es e n s i t i v i t v f o m u 】a so ft h es t e a d y s 诅t ep e r f 咖姐c e e x p r e s s e db y t 1 1 ep 毗蚰t i a l so ft h e e q u i v a l e n tm a 订( o vp r o c e s sa n dm ee m b e d d e dm a r k o vc h a i na f e 茹v e l l c o m b i n i n gt h ep o t e n t i a lf h e o r yw i 也s e m i - m a d ，o vc o n 打o lp r o c e s s e s ，w e o b t a i nap e r f o 册a l 】c ep o t e n t i a 】s _ b a s e do p t i m a “t yt b e 甜鲫t h ep r o b 】e mo fm e o p t i m a ls t a t i o n a r yp o l j c yf o rs e m i m a r k o vp r o c e s s e sw i 也c o u n t a b l cs t a t es p a c e 柚dc o m p a c ta c 6 0 ns e tw a s 小s c u s s e db yt l l em e t l l o do fe q u i v a e n tm a r k o vp r o c e s s a n de m b e d d e dm a r k o vc h a i n 锄d 盯h ei n 蠡n i t eh o z o na v e f a g c - c o s tp e r f b 册a n c e m e a s u r e t h m u 曲t l l eb a l a 王l c ee q u a t i o na i l dp o i s s o ne q u a t i o n ，w eo b t a i na p e r f 0 兀n a n c e p o t e n t j a l s b a s e d o p t i m a l i t yt l i e o r e m ， 柚da p e r f o r m a n c e p o t e n t i a l s - b a s e da v e r a g e c o s to p t i m a l i t ye q u a t i o n f o rs e m i m a r k o vc o n t r o l p r o c e s s e s u n d e rs o m ew e a ka s s u m p 6 0 n s ，a ne x i s t e n c et h e o e mo f t i es o l u t i o n s o t l l eo p t i m a l j t ye q u a t i o nf o rs e m i - m a r k o vc o n t r dp m c e s s e sw i t l lc o m p a c ta c t i o ns e t i sd r i v e n i no r d e rt oc a l c u l a t eo p t i m a la v e r a g e c o s tp o l i c i e s ，w ep r o p o s es o m e a l g o r i t h m si n c 】u d i n ga 伊a d i e n t b a s e da l g 嘶t h m ，ap o l i c yi t e m t i o na l g o r i t l ma i l da v a u ei t e r a t i o na l g o r i t h m f u r 出e 订n o r e ，t l l ec o n v e 唱e n c eo f t h el a s tt w oa l g o t h m s i se s t a b l i s h e d ，w h i c hs h o w st h a tt l l ea l g o r i t l l m sw i l ls t o pi naf i n i t en u m b e ro fs t e p s w i t he p s i l o n p o l i c i e s t h ea b o v ec o m p u t a t j o n b a s e d 叩t j m i z a t i o na l g o r i t l l m sa s s u m em ea v a i l a b i l j t y o fa 1 1e x a c tm o d e l ，a n dr e q u i r em 锄yc a l c u l a t i o n so nm a 砸x 访v e r s i o n h o w e v e r m a n yi n t e r e s t j n gp m c t i c a is y s t e m si n v o l v ei a 培es 诅t es p a c e s ，i e ，t h e r ee x i s t st h e c u r s eo fd i m e n s i o n a l i t yt h ec o n l p u t a t i o no fm a 啊x 缸v e r s i o nw i l ln e e dl a 唱e s t o r a g es p a c ea n db em u c bt i m e c o n s u m i n g ，ka d d i t i o n ，f o rs o m ep r a c t i c a l s y s t e m s ，h ef u l li n f o r m a t i o do ft h es y s 锄p a r a m e t e r si sn o ta v a j l a b l e ，n a m e l y ， t h e r ei s 血ec u r s eo fm o d e i i n g f o rs u c hs y s t e m s ，t l l ec o m p u t a t i o n - b a s e d o p t i m i z a t i o na l g o r i m m sm a y b e i n a p p i i c a b l e ， 柚dw en e e d r e s o r t t o s i m u l a t i o n 七a s e da p p r o a c h e st oo v e r c o m et l ed i 硒c u l t i e s t h r o u g ht h ei n f o n n a t i o n “as i n 9 1 es 劬p l ep a t h ，w h i c hc 卸b eo b 翻n e db ys i m u l a t i n gar e a ls y s t e mo r o b s e r v i n g 山eo p e r a t i o no f a na c t i l a ls y s t e m ，s o m ev a l u ec a i lb ee s t i m a t e d i no r d e rt od e v e l o pm es i m u l a t i o n - b a s e da l g o r i t h m s ，w eg i v et l l ed e f i n i t i o no f s e m i m a r k o vp e r f b 玎n a n c ep o t e n t i a l sb y 廿l er e a l i z a 石o nf a c t o r st l l r o u g has i n 9 1 e s a m p i ep a t h ，a n dp m v et h a tt i i ed e f i n i t i o ni se q u i v a l e n tt oc h a td e f i n e db yt h e p o i s s o ne q u a t i o no f t h ee q u i v a l e n tm a r k o vp m c e s s t h ee s t i i n a t i o ne q ua 【i o no fi h e s e m i m a r k o vp e r f o 册a n c ep o t e n t i a l si s 垂v e n ，a n ds o m eo p t i m i 功t i o na l g o r i t h m s b a s e do na s i n g l es a m p l ep a 山w e r ed i s c u s s e d n l e s cs i m u l a t i o n - b a s c da 培o r i t i i m s w i l i 印p l i c a b i ef o rs o l v i n gt h e 叩t i m i z a t i 彻p r o b l e m so fl a 喧e s c a l ea c m a is y s t e m s w h e t h e rt h em o d e 】sa r ek n o w no ru n k n o w n i na d d i t j o n ，w en o t i c e l a tm o s to ft i l ew o r ki no p t i m i z a t i o np r o c e s s e si st h e c o m p u t a t i 仰r e l a t e dt om a n ym a t r i c e sa n dv e c t o r ，w h j c hc 锄b ee a s i 】yd e a l tb y p a r a l l e lm e t h o d s ，卸dt l l ee s t i m a t i o no ft l l ep e r f b m 锄c ep o t e n t i a l sc a i ib ed e a h s y n c h m n o u s ly t h e r e f o r e ，w eh a v ea l s od i s c u s s e dc o m p u 洲帆b a s e dp a r a l i e l a l g o r i t h m s 锄ds i m u l a t i o n b a s e dp a r a e la l 鲥m m s ，w h j c hc a ni m p r o v et l l e c o m p u t i n gs p e e da n dc 鲫b eu s c dt ov o i dt l l ec u r s eo fd i m e n s i o n a l i t ya 1 1 dl h ec u r s e o fm o d e l i n g w ep r o v i d em a n yn u m e r i c a 】e x 锄p l e st oi l l u s t r a t et 1 e 印p l i c a t i o no fa l lt h e a l g o t l i m sp r o p o s e di n t l l i st h e s i s 柚dg i v ear c a le x 锄p l eo fs e m j m a r k o v p r o c e s s e si nq u e u i n gs y s t e m ，i e w ed i s c u s s e dt l l ep r o b l e m so ft h es e n s i t i v i t y a n a l y s i sa n do p t i m i z a t i o nf o rm g lq u e u i n gs y s t e m s 致谢 本论文是在导师奚宏生教授的精心指导下完成的。奚老师为我选择了功 在这一前沿研究方向，并在课题研究与论文撰写工作中给予了充分的指导和 多方丽的支持。奚老师宽阔的学术视野，严谨的科研作风使我受益匪浅。他 的敬业精神将永远激励我向前。在此谨向奚老师表示深深的敬意和诚挚的感 谢! 在本课题的研究工作及论文成稿过程中，我还一直得到了硕士期间的导 师殷保群副教授的热心帮助和悉心指导。奚老师和殷老师作为研究项目的负 责人，始终身体力行，使我们的课题研究得以深入进行。本论文的每一部分， 都是在两位老师的精心指导下完成的。在论文定稿阶段。两位老师仔细阅读 了本文原稿，提出了许多宝贵的意见。同时，奚老师和殷老师扎实的理论基 础，广博的学识和高尚的品质永远是我学习的榜样。另外，五年来他们在生 活上也给予了我较多的关心和帮助。 在本论文的进行过程中始终得到了实验室成员周亚平老师和季海波老 师的热情帮助在与他们的讨论中我总能得到有益的启示。另外本实验室 所有老师和同学也一直给了我多方面的关心和帮助，特别是李衍杰博士，唐 吴博士等。在此对他们表示感谢! 另外，感谢自动化系和研究生院给予我多方面关心和帮助的所有老师和 工作人员。 最后，特别感谢我的父母姐妹和我的爱人，感谢他们长期以来给予我的 关怀，支持和鼓励。特别要感谢我的母亲，从小到大母亲都是我坚强的后盾， 她给予我巨大的精神动力和无私的关爱，感谢她为我默默奉献的一切。 衷心感谢所有帮助我的人。 中国科技大学博。l 。学位论文第一章绪论 第一章绪论 本文所进行的上作是半m a r k o v 控制过程的性能灵敏度分析、优化及其算 法研究。半m a r k o v 控制过程是比m a ik o v 控制过程更一般化的一种随机过程 系统在每个状态的逗留时间是一个服从一般分布的随机变量。半m a r k o v 控制 过程是离散事件动态系统在统计层次下的重要模型之一。在这一章坐，我们 将对离散事件动态系统的产生、发展以及研究成果作一下简单同顾，并介绍 半m a r k o v 控制过程基丁i 忭能势的优化问题以及一些相关工作。 1 1 离散事件动态系统简介 离散事件动态系统( d e d s ) 的概念是由哈佛大学的y c h o ( 何毓琦) 教 授等在二十世纪八十年代提出的l ，指的是由一些相互作用的离散事件构 成，并由这些离散事件触发而引起状态转移的一类系统。如交通管理，牛产 自动线，计算机网络，通信系统等都可由d e d s 来描述。 在d e d s 中，系统的状态定义为在特定时间内与研究目的有关的描述系统 所需变量的集合。例如，在制造系统中，机器的忙、闲或故障为可能的状态。 在银行系统中，正在工作的出纳员人数，在排队或正在接受服务的顾客数为 可能的状态。所有状态构成的集合，称为状态空间。 d e d s 的状态仅仅在可数的。些时问点上才有变化，我们定义可能改变系 统状态的瞬间事变为事件。d e d s 所包含的事件的发生在时问上和空叫上都是 离散的。在制造系统中，零件到来等待加工或加工完毕等是事件；而在银行 系统中。顾客的到达和离去等是事件【4 】。一个事件的发生往往引起系统的状态 在状态空间里变化。不同于通常的时间驱动的连续变量动态系统，d e d s 的状 态变化过程不能由通常的物理定理来描述，而是服从一些人为规定的复杂规 则，并由一系列相继发牛和相互作用的离散事件驱动。 d e d s 在近十年中得到了快速的发展【2 2 。它的根本推动力来自于十 世纪八 年代初期在一批高技术领域( 如计算机通信，制造系统，空中交通 中国科技大学博 + 学位论文 第一章 绪论 管理及军事指挥系统等) 中所大量出现的人造系统，由于这些高技术领域的 迅速发展，d e d s 从诞牛以来很快就成为控制与系统科学的一个前沿方向受 到了越来越多的重视和关注。据考证近几年国际控制界重要的学术会议，女 i f c 大会i e e e 控制与决策大会等d e d s 的研究论文均占有相当的比例。 研究d e d s 的主要目的是在一定的条件下优化该系统的性能指标，使之 能更有效地提供服务，为设计新系统或改进现有系统提供依据，这就是d e d s 的优化问题。随着d e d s 应用领域的日益发展，出现了许多更为复杂的系统， 它要求决策者根据系统的实时演化提出相应的策略使系统的整体指标达到最 佳，这可视为d e d s 的控制问题。 根据所采用的模型和工具的4 i 同，对d e d s 的研究目前在三个层次进行。 第一是从逻辑层次研究d e d s 中事件和状态序列的建模方法，主要采用形式语 言，有限自动机m a r k o v 链，p e t r i 网等i 2 i ”l 。在该层次下，一般利用离散 的符号来描述系统的状态特征，运用人们规定的某种机制来驱使事件的产生 或灭亡从而导致系统状态的演化。在逻辑层次下研究d e d s ，对系统的控 制及控制作用下的系统行为有较深刻的研究，但由于没有考虑系统的物理时 间所以难以用丁i 系统的动态分析。 第二是从时间层次研究d e d s 的运行轨道及其特性，主要采用的建模方法 包括通讯序贯过程，极大极小代数，有限递归过程等【3 “”。这一层次的特点 是将d e d s 类同于通常意义下的连续时间系统，将现代控制理论引进d e d s ，可 定量的研究系统的稳定性及结构特征等系统行为。在这一层次下，不仅考虑 事件和状态的逻辑顺序关系，而且也涉及到系统真实的物理时间，从而町用 于系统的动态分析。特别是，基于线性化的动态方程，可定量地研究系统的 稳定性及结构特征等系统行为。但其适用的范围较窄，并且通常的连续变量 线性系统中一系列的行之有效的分析控错b 和优化技术，难以用到这样的线 性系统模型中。 第三是从统计层次研究d e d s 的过程性能，主要采用的模型有m a r k o v 过 程，半m a r k o v 过程，广义半m a r k o v 过程以及各种类型的排队系统。统计层 次是d e d s 最初的研究形式，d e d s 的基本概念就是从这一层次提出来的。一般 来说，d e d s 中某个参变量的微小变化，都会导致系统以十分不同的方式运行， 因此需要考虑系统中许多参变量的随机变化，从而在性能分析中需采用统计 平均的方法。其中早期代表性的研究方法是摄动分析( p a ) 【4 舢5 9 1 方法，该方 中国科技人学博i 学位论文第一章 绪论 法是由哈怫大学的何毓奇教授提出来的【4 ，它是种将计算机仿真与理论分 析相结合的方法，可以通过分析随机过程的一条样本轨道来获得系统性能指 标关于参数的导数。近十多年来，经过众多学者的努力，从无穷小摄动分析 ( i p a ) 方法到改进的p a 方法，已经建立了一整套有用的技术，并被成功地用 于各种不同的系统分析中i “”】。但是由于d e d s 适用的范围越来越广，研究的 问题也越来越复杂，而摄动分析方法的理论要求很高，很多实际问题无法满 足或者根本无法验证是否满足要求，从而导致摄动分析方法失效。 木文的主要工作是在统计层次下做的。目前，该领域的两个主要研究方 向是性能灵敏度分析和优化问题，尤其半m a r k o v 控制过程己成为当前d e d s 领域的一个研究热点。本论文主要就是研究半m a r k o v 控制过程基于性能势的 灵敏度分析和优化问题。在下一廿，我们将介绍一个重要概念性能势， 并简单介绍一下半m a r k o v 控制过程。 1 2 性能势理论和半m a r k o v 控制过程 由于i p a 方法和改进的p a 方法，存在着一些缺陷和不足，特别是缺乏作 为理论的普适性，二十世纪九十年代，曹希仁( x r c ) 教授和陈翰馥教授 提出了一个新的理论：性能势理论，并揭示了m a r k o v 性能势、无穷小摄 动分析( i p a ) 与m a r k o v 控制过程( m c p ) 三者之间的联系【7 l j 。性能势理论 以m a r k o v 过程作为系统模型，并引入两个重要的概念：实现因子和性能势， 前者类似于摄动分析方法巾的实现因子，后者是对m a r k o v 过程理论的重要贡 献，通过这两个量中的任何一个，给出了系统稳态性能的灵敏度公式。南于 实现因子和性能势可从系统的一条单一样本轨道上获得它们的精确估计，故 性能势理论可应用于p a 方法失效的系统的灵敏度分析；而p a 方法有效的系 统，它同样町以提供精确的导数估计性能势理论为p a 方法和非p a 方法提 供了。个一。致的框架。 性能势理论被广泛应用到一般m a r k o v 系统和m a r k o v 型排队网络的灵敏 度分析中，并取得了显著成果1 7 “7 9 】：另外，曹希仁运用m a r k o v 性能势理论。 给出了m a r k o v 控制过程( m c p ) 在有限行动集下基于性能势的优化理论和算 法7 ”。在此基础上，有关m a r l ( o v 控制过程和受控排队网络在紧致行动集上 中国科技大学博匕学位论义 第一帝绪论 基于性能势的优化理论和算法的到了进步的研究f ”9 2 】。本文在曹教授和陈 教授工作的基础上，将性能势理论推广到了半m a r l v 过程，在此基础上，建 立了半m a r k o v 控制过程的优化理论。下面介绍简单一下半m a r k o v 控制过程。 在统训层次下，d e d s 领域目前的一个主要的研究热点是半m a r k o v 控制 过程( s m c p ) 。半m a r k o v 控制过程，又称为半m a r k o v 决策过程、受控半 m a r k o v 过程等，是指南一系列控制决策驱动的半m a r k o v 过程，在这一过程 中状态转移概率、状态的逗留时间序列与所选用的控制决策相互作用决定 了过程的演化。s m c p 是比m a d ：o v 控制过程( m c p ) 更广泛的一类随机过程， 它与m c p 的区别是s m c p 在每个状态的逗留时间服从一般分布，该分布与 当前状态和即将转移到的状态有关；若这个分布是指数分布，则其为m c p ， 即s m c p 包含m c p 。 s m c p 可以用来描述更一般化的实际人造系统其应用领域非常广泛， 这些领域有：生产存贮系统、质量控制、序惯搜索、水资源管理、森林管理、 航空订票、高速公路管理、计算机，通信网络系统控制、机器人控制等。 s m c p 是研究一类随机序贯决策问题的理论，即在一系列相继的或连续 的时刻( 称之为决策时刻) 点上做出决策。在每个决策时刻点，决策者根据 观察到的状态从可用的若干个决策中选择一个；将决策付诸实施后，系统将 获得与所处状态和所采取决策有关的一项报酬( 或费用等) 并影响系统在下 一决策时刻点所处的状态。系统在下一决策时刻点处的状态是随机的。在这 一薪的决策时刻点卜，决策者要重新观察系统所处的新的状态( 即收集新的 信息) 并采取新的决策，如此循环进行下去。在每一决策时刻采取的决策不 仪影响当前决策周期的运行和性能( 状态的逗留时问、获得的报酬或代价等) ， 而且会直接或间接影响下一决策时刻系统的运行和性能，并以此影响将来。 决策的目的足选择一种控制决策方案，使系统的运行在某种意义下( 称为性 能准则) 达到最优例如在期望平均报酬( 或期望平均代价) 准则卜，使系 统的期望平均总报酬( 或期望平均代价) 最大( 或最小) 。这样，在每一个决 策时刻所选择的控制决策，不但要使当前决策周期获褥的报酬( 代价) 尽可 能大( 小) ，而且要使系统在将来的后续周期所获得的报酬( 代价) 尽可能大 ( 小) 。这需要决策者从全局的观点做出权衡，因而这也是s m c p 优化控制问 题的难点所存。 我们在m a r k o v 性能势理论的基础上建立了s m c p 的性能势理论，利 中国科技大学博i 。学位论文第一章绪论 _ j 等价m a r l ( o v 和嵌入m a r k o v 链的方法，给出了半m a r k o v 过程的稳态性能 灵敏度公式，并建立了平均代价准则下基于性能势的优化理论，讨论了在紧 致行动集上的优化算法f 9 3 - 9 ”。 s m c p 的优化方法通常有数值计算求解、直接搜索法、线性规划方法 ( l p ) 、梯度方法、以及策略迭代( p i ) 和数值迭代( v i ) 方法等。目前后三 种方法是主要的优化手段。本文在s m c p 基于性能势的比较原理和壤优性方 程的基础上考虑一些优化算法如梯度算法、策略迭代算法以及数值迭代算 法。 在实际的优化问题中，系统模型可以是已知的，也可以是未知或者不完 伞可知的。在系统模型已知时，可以根据模型参数直接进行优化计算。然而 在状态空间很大的优化计算问题中，存在两个问题。一是赢接优化算法的计 算量常常相当大，尤其是矩阵求逆运算等，需要耗费大量的运算时间，往往 导致计算机负担过熏，甚至使得内存溢出而不可行：二是在一定的策略下。 部分状态出现的概率很小或者几乎不出现，对优化问题的贞献很小，从而耗 费了不必要的计算时间。为了降低优化问题的成本，我们可以考虑基于仿真 的算法，通过仿真随机产生出具有代表性的状态，然后对这些状态进行计算 这样避免了每次都要对那些很少出现的状态进行计算，因而节省了计算时间。 另外由于性能势的一个特点就是可以在一条单样本轨道上得到其无偏估计 值，并用于进一步的优化，因此在基于性能势的优化问题中考虑摹于仿真的 优化方法，可以避免矩阵求逆运算，克服“维数灾”问题。 在系统模型未知或者不完全可知时，基于理论计算的优化方法，由于需 要转移矩阵或无穷小矩阵的完全信息，也不再适用，必须求助十仿真的方法。 对于大规模实际s m c p 系统，由于其状态空间存在“维数灾”( c u r s eo f d i m e n s i o n a l j t y ) 问题，在对此类系统进行性能优化时，性能势的计算开销非 常大，对计算机处理器速度和内存容量的要求非常商，并且常常因此而受到 限制。在这种情况下我们考虑发展并行算法。在基于性能势的并行优化算法 中要考虑的是两个部分：一是性能势估计的并行算法：二是优化过程中迭代 子优化问题的并行化。 可见性能势理论为s m c p 的优化提供了一个统一的理论框架。运用性 能势理论，从p o i s s o n 方程着手，在较少的假设条件下，很容易建立起s m c p 中国科技大学博 学位论文第一章绪论 基于性能势的比较原理和最优性方程，并且容易证明其最优解的存在性定理。 在此皋础上可给出一些收敛的优化算法，如摹于计算的梯度类算法和策略迭 代以及数值迭代算法。另一方面，性能势的一个重要特点足可以通过仿真或 观测一个实际系统的运行得到单个样本轨道来进行无偏估计f “，在此基础 上可以发展基于单条样本轨道的仿真优化算法和在线优化算法。这种算法将 适片j 于大规模实际系统在模型已知或未知情况下的优化求解。 性能势的这些性质为实际半m a r k o v 系统的分析和优化提供了一个强有 力的工具，它在实际系统中的应用突m 体现在排队系统中。实际系统中的许 多排队系统都叫。以用半m a r k o v 控制过程来描述，我们称这样的排队系统为半 m a r k o v 型排队系统。本文中关于半m a r k o v 控制过程的研究结果可以直接推 j 到半m a r k o v 型排队系统的研究中，因此本文把一类半m a r l 【o v 型排队系统 m g l 排队系统的研究作为重要内容9 “。 1 3 相关工作 s m c p 是由文献 1 0 1 和 1 0 2 各自独立地将m c p 推广到半m a r k o v 过程而建 立的，之后，文献( 1 0 3 和 1 0 4 等分别作了相当多的讨论，但是这些方法都 是采用转换为离散时间m a r k o v 链的方法，有关半m a r k o v 性能势的研究目前 国内外的成果还很少。 在d e d s 理论中，j a c k s o n 等m a r k o v 型的排队网络己被应用于模拟计算机 系统，通信网络以及集成制造系统的动态特征，所以这类研究得到了越来越 多的关注。近期涉及网络优化方法研究的有：y a o 和s c h e c h n e rl 5 j 考虑了 一类特定的代价函数，它是每个服务节点上服务率的线性函数，应用线性规 划方法，他们得到了由一类阑值所指定的最优策略。m a 和c a 0i l 叫采用了一 种直接方法解决这一类型的优化问题，它基于乘积形式解的直观性质。c h o n g 和r a m a d g e m 蝌对t - 类再生过程，采用p a 方法估计性能指标的梯度，并且给 出了直接梯度寻优方法的收敛证明。然而最近的一些研究结果表明，对于一 些系统p a 方法能提供无偏或强相容的梯度估计，但是也已证实对于许多实 际系统，这类条件的验证是非常困难的，有的甚至根本不成立。 性能势理论的提出，开创了d e d s 研究的新局面基于性能势的直接计算 中国科技人学博i 学位论立笫一帝绪论 方法和仿真方法已被广泛的运朋到m a r k o v 型排队网络系统和m a r k o v 过程的 灵敏度分析与性能优化中，出现了大量的研究成果盼7 9 b 7 。8 。文献 8 9 将 m a r k o v 性能势理论移植到了m a r k o v 型排队网络中，建立了m a r k o v 型排队网 络的性能势理论，给出了网络稳态性能基丁- 性能势的灵敏度公式。这一成果 又被拓展到了一类位相型( p h a s e t y p e ) 分布的排队网络( 包括c o x ，e r l a n g 和超指数分布) 。文献 8 7 完成了性能势估计基于样本轨道的并行仿真算法和 网络稳态性能灵敏度估计的并行仿真算法。文献 8 6 采用m a r k o v 性能势理论 建立了离散时间和连续时间m a r k o v 控制过程在紧致行动集上的比较定理和最 优性方程，给出了解的存在性定理的证明和策略迭代算法的收敛性i f 明，同 时这些结果也被推广应用到了一类m a r k o v 型受控排队网络中。 半m a r k o v 性能势是曹希仁和陈翰馥教授继m a r k o v 性能势理论后提出的 一个新的研究方向”“j ，目前幽内外的研究成果还很少。我幽学者胡奇英教授 】和美同学者p u t e r m a n l 1 分别先后在他们的著作中提h 了，在一定的假设 条件下，可将依赖于决策的状态转移时间中的变化部分转换到过程的状态转 移概率一h 从而使半m a r k o v 控制过程转化为+ 个离散时间m a r k o v 控制过程 问题。然而这些相关的模型转换条件对大量实际人造系统的适用性迄今还未 获得论证。本论文首次采用半m a r k o v 性能势来研究半m a r k o v 控制过程，并 r 导出一个无需进行模型转换的直接优化方法。 1 4 文章结构安排 本文主要研究具有口j 擞状态空间的半m a r k o v 控制过程在无穷水平平均代 价准则下的性能灵敏度分析和优化问题。给出了以等价m a r k o v 过程和嵌入 m a r k o v 链的性能势表示的灵敏度公式，建立了优化理论，给出了最优性方程 行证明了解的存在性定理：研究了优化算法，给出了基r 单个样本轨道的仿 真优化算法及其并行算法。并给h ： 了大量的数值例子，来说明相应算法的应 用。文章的结构安排如下： 第二章中建立了半m a r k o v 过程的性能势理论，并在性能势的基础上讨论 了稳态性能势灵敏度分析问题。酋先利用等价无穷小矩阵，定义了半m a r k o v 过程的p o i s s o n 方程，将该p o i s s o n 方程的解定义为半r k o v 过程的性能势： 然后利川等价m a r k o v 过程和嵌入m a r k o v 链的方法，讨论了半m a r k o v 过程的 中国科技丈学博i ：学位论文第一章绪论 性能灵敏度分析问题，导出了基于等价m a r k o v 过程和嵌入m a r k o v 链的性能 势的灵敏度公式。 第三章讨论了一类可数状态空间的半r k o v 控制过程的性能优化问题。 首先讨论了一类可数m a r k o v 控制过程在平均代价性能准则下的性能优化问 题，然后分别运用等价m a r l 【o v 过程和嵌入m a r k o v 链方法研究了一类半 m a r k o v 控制过程在平均代价性能准则下的性能优化问题，给出了基于性能势 的最优性方程。并在较弱的条件下证明了解的存在性定理。 第四章主要研究半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 g l 排队系统的性能灵敏度分析和优化问题。针对g 1 排队系统的特点。 利用其嵌入m a r k o v 链来讨论了系统的灵敏度分析和优化问题，并给出了几种 特殊的吖g l 排队系统的灵敏度公式。 最后对本文工作做了一个总结，指出了迸一步的研究方向。 本论文的贡献和创新之处在于以下几个方面。 1 利用拟无穷小矩阵，定义了半m a r k o v 过程的p o i s s o n 方程，通过该 p o i s s o n 方程建立了半m a r k o v 过程的性能势理论； 2 利用等价m a r k o v 过程和嵌入m a r k o v 链的方法，讨论了具有可数状 态空闻的半m a r k o v 过程的稳态性能灵敏度分析问题，给出了基于性能势的灵 敏度公式； 3 将性能势理论和半m a r k o v 控制过程的基本原理相结合，建立了半 r k o v 控制过程的优化理论框架，给出了基于性能势的比较原理和平均代价 8 中国科技大学博士学位论文第一章鳍论 最优性方程，并证明了最优性方程在紧致行动集上解的存在性定理； 4 讨论了求解最优平稳策略的理论优化算法。并证明了算法的收敛性； 5 针对大规模状态空间的实际人造系统存在的“维数灾”和“模型灾” 问题，提出了基于样本轨道的仿真优化算法；另外，考虑到优化算法中的大 部分的运算涉及到矩阵和向量的运算，这些运算具有很好的并行性，并且性 能势也可以根据样本轨道并行估计，因此建立了相应的并行算法，用来解决 计算机的内存容量限制问题和运算时间问题，加快了寻优速度。 事实上，许多实际人造系统，例如柔性制造系统中自动车的移动策略， 物流系统中的最小代价路径问题，大规模计算机和通信网络中的多媒体信流 的接收和发送，系统的最优维护代价和安全可靠性等问题，最终均可归结为 个半m a r k o v 控制过程问题。本论文的研究能够为大量实际复杂人造系统的 性能优化提供个直接的、行之有效的方法，这对进一步改进系统的设计， 提高系统的运行效率和管理水平具有极其重要的意义。 中国科技大学博+ l 学位论立第二章半m a r k o v 过程的性能灵敏度分析 第二章半m a r k o v 过程的性畿灵敏度分析 在这一章里，我们将分别运用等价m a r k o v 过程和嵌入 l a r k o v 链的方法， 来研究半m a k o v 过程的稳态性能灵敏度分析问题。利用等价m a r k