（控制理论与控制工程专业论文）计算markov链性能势的算法研究.pdf

中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：盏丝蓥 年月 i e i 中国科学技术大学硕士学位论文摘要 摘要 基于性能势理论，对离散事件动态系统进行性能分析和性能优化时，需要 计算实现因子和性能势在这篇文章中，以遍历m a r k o v 链为模型，针对现有 计算方法的不足，提出了计算实现因子和性能势的三种迭代算法和一种仿真算 法三种迭代算法分别从l y a p u n 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 链；实现因子；性能势；迭代算法；耦合 中田科学技术大学硕士学位论文 a b s t r a c t i nd i s c r e t ee v e n td y n a m i cs y s t e m s ( i ) e o s s ) ，t h es t u d yo f p e r f o r m a n c es e n s i t i v i t y a n dp e r f o r m a n c eo p t i m i z a t i o nb a s e do nt h e o r yo fp e r f o r m a n c ep o t e n t i a lr e q u i r e s c o m p u t i n gt h er e a l i z a t i o nf a c t o r sa n dp e r f o r m a n c ep o t e n t i a l s i nt h i sp a p e r ，w es t u d y h o wt oc o m p u t et h er e a l i z a t i o nf a c t o r se n dp e r f o r m a n c ep o t e n t i a l so fa l le r g o d i c m a r k o vc h a i n t r e ei t e r a t i v ea l g o r i t h m sa r ep r o p o s e dh e r e t h ea d v a n t a g eo f t h e s e a l g o r i t h m s i st h a t e x p l i c i tk n o w l e d g eo ft h es t a t i o n a r yd i s t r i b u t i o ni sn o t r e q u i r e d t h e s ea l g o r i t h m sa r eo b t a i n e df r o md i f f e r e n tp o i n to f v i e w ，b u tt h e ya 坤t h e q u i t es a m ei nf a c t b e s i d e st h e s ei t e r a t i v ea l g o r i t h m s ，am e t h o di so v e nt oe s t i m a t e t h er e a l i z a t i o nf a c t o r sb ys i m u l a t i o nb a s e do nt h ec o u p l i n ga p p r o a c h i nt h ec o u p l i n g a p p r o a c h ，w ec a ng e ta r to p t i m i z e dt r a n s i t i o np r o b a b i l i t ym a t r i x u s i n gt h eo p t i m i z e d c o u p l e dm a t r i x ，t h es a m p l ep a t h sm e r g et o g e t h e rq u i c k l y ，t h er e a l i z a t i o nf a c t o r c a nb eo b t a i n e dr a p i d l yi ns i m u l a t i o n i nt h i sw a y , t h ep r o b l e mo fs o l v i n gt h e o p t h n i z e dc o u p l e dm a t r i xi sas t a n d a r dl i n e a rp r o g r a m m i n g ( l v ) p r o b l e m i n p a r t i c u l a r , as i m p l em e t h o di sa l s op r o p o s e dt os o l v et h e l pp r o b l e m k e y w o r d e ：m a r k o vc h a i n ；r e a l i z a t i o nf a c t o r ；p e r f o r m a n c ep o t e n t i a l ；i t e r a t i v e a l g o r i t h m ；c o u p l i n g - 3 中田科学技术大学硕士学位论文 第一章绪论 第一章绪论 随着计算机网络，通信网络和军事指挥系统等高新技术的发展，离散事件 动态系统( d i s c r e t ee v e n td y n a m i cs y s t e m s ，简称d e d s s ) 已经成为系统和控 制领域的一个前沿方向，并在一大批高科技领域得到广泛应用研究d e d s s 的主要目的是要在一定条件下优化系统的性能使之可以更有效的运行，并为 设计新系统或者改进现有的系统提供可靠的依据这就是d e d s s 的优化问 题同时因为d e d s s 应用领域的日益发展，出现了很多更为复杂的人造系统， 这些系统要求决策者根据系统的实时演化提出相应的策略，使系统的整体性能 达到最佳，这便是d e d s s 的控制问题研究d e d s s 控制问题的一个主要方向 就是m a r k o v 决策过程的性能优化问题 在d e d s s 的优化问题和m a r k o v 决策过程性能优化问题这两个研究领域中， 基于性能势理论的研究都取得了显著的成果性能势理论以m a r k o v 过程作为 系统模型，并引入了两个重要的概念：实现因子和性能势计算或者精确估计 系统模型的实现因子和性能势是性能势理论的一个重要前提然而系统越来越 复杂，系统的状态越来越多，实现因子和性能势随之也越来越难以计算因此， 研究计算性能势的算法特别是研究适用于大型状态空间条件下的算法具有十分 重要的意义 本章下面将介绍d e d s s 以及m a r k o v 决策过程，本文其他章节内容安排如 下：第二章讲述性能势理论，并以闭排队网络为对象，介绍基于性能势理论的 灵敏度分析和性能优化的一些主要方法和结果；第三章介绍现在常用的几种计 算实现因子和性能势的算法，分析这些算法的不足之处；第四章研究了三种不 依赖稳态分布的迭代算法计算实现因子和性能势，并给出了这三种算法之间的 关系；第五章研究基于耦合技术的仿真算法计算实现因子和性能势，通过使用 耦合技术来减小仿真中样本轨道的长度，以此来达到提升算法性能的目的，通 过仿真并与其他算法进行比较来验证该算法的性能 1 1 离散事件动态系统( d e d s s ) 离散事件动态系统( d e d s s ) 是系统和控制领域一门新的分支，它是由哈 佛大学y c h o 教授等人于1 9 8 0 年前后创立的【d e d s s 区别于通常的连续变 量动态系统( c v d s s ) ，是一类特殊的系统，大多是一些人造系统在d e d s s 中，决定系统状态的是一批离散事件，系统的状态在离散事件发生的瞬时改变， 系统所遵循的也都是些复杂的人为规则随着科学技术的发展，出现了越来越 中崮科学技术大学硕士学位论文 第一章绪论 多的反映科学技术发展方向的人造系统，比如通信网络，交通管理系统和军事 指挥系统等，这类系统通常都能被描述为d e d s s ，所以d e d s s 越来越受到重 视和关注1 2 - l n 在d e d s s 中，状态变量指用来研究特定性能所必需的描述该系统的最少变量 的组合所有状态构成的集合称为状态空间d e d s s 可以定义为由异步、突发的 事件驱动状态演化的动态系统系统的动态性体现在两个方面：一方面离散事件 发生驱动状态的演化，另一方面系统状态的演化触发新的离散事件的发生离散 事件动态系统的状态通常只取有限个离散值，对应于系统部件的好坏、忙闲及待 处理个数等可能的物理状况，或计划制定、作业调度等宏观管理的状况而这些 状态的变化则由于诸如某些环境条件的出现或消失、系统操作的启动或完成等各 种事件的发生而引起对d e d s s 的建模和分析有两个特点：一方面，实际d e d s s 的状态变化往往呈现出不确定性，因此在对d e d s s 的建模和分析中，随机因素不 可回避；另一方面，不同于连续变量动态系统，d e d s s 遵循的是人为规则而不是 物理学定律( 如牛顿运动定律，电路定律等) 及其衍生物，状态空间缺乏易操作 的运算结构，这就决定了难以用传统的差分方程或者微分方程方法来研究，其建 模和分析十分复杂 现实中，d e d s s 的实际背景有很多，其中作为先进制造系统重要组成鄯分 的柔性生产线或称为柔性制造系统( f l e 妇b l em 锄u f a c t u r i n gs y s t e m s ，简称f l v l s s ) ， 是最典型的一个重要例子【1 卯柔性制造系统是综合计算机数控技术，机器人技 术和计算机软硬件技术的一类先进制造系统柔性制造系统能够按所要求的工 件品种混合比来同时加工多种不同工件，能够适应小批量多品种加工任务，对 加工过程中的频繁切换具有高度灵活性在被称为2 1 世纪自动化工厂模式的计 算机集成制造系统中，柔性制造系统是不可缺少的底层单元 通常柔性制造系统的组成可以用图1 1 表示一个典型的柔性制造系统需 要包括以下4 个基本组成部分 ( 1 )加工中心加工中心由不同类型机床组成，配备多达几十种功能的 刀具，可对工件进行不同类型的加工在加工中心中，从刀具的选 择到加工工艺的确定全部都是由计算机程序控制的，并且程序的调 用和更改十分灵活方便，因而加工中心具有很好的柔性 ( 2 )物料自动传送系统物料自动传送系统是加工过程中不间断运行的 一个保障系统物料自动传送的常用方式是采用由计算机控制以一 定速度按照指定路径巡驶的物料小车待加工工件由自动小车送到 相应加工中心的缓冲区，加工完的工件由自动小车送到自动立体仓 库 中田科学技术大学硕士学位论文 第一章绪论 缓冲区缓冲区位于各个加工中心之前，其功能是存放暂时不能进 入加工中心的待加工工件设置缓冲区是为了改善由于各个加工中 心作业时间不同造成的物流不均衡性，避免可能出现的阻塞现象 计算机控制单元计算机控制单元是柔性制造系统加工过程的控制 中心，其功能包括：对工件流向的控制，对加工任务的调度，对运 行状态的监控，对自动小车的分配等 圈1 1 柔性制造系统示意图 柔性制造系统是一个典型的离散事件动态系统各个加工中心对各类工件的 加工活动构成系统的状态，由工件和加工中心组成系统的资源，资源的投入或释 放构成系统的离散事件表示系统加工活动的状态的跃变，由待加工工件的到达 ( 投入) 和机床的完成加工( 释放) 等事件所驱动显然，状态演化过程中，状态跃 变时刻将呈现出异步性，而系统演化则由离散事件错综复杂的相互作用所决 定当f m s s 的基本参数( 如加工中心对各种工件的作业时间、自动物料传送系统 的运行速度、工件的加上特性等) 为固定不变时，f m s s 中出现的事件可认为是确 定性的，整个f m s s 可表征为一个确定性d e d s s 如果f m s s 的基本参数( 如机床作 业时间自动物料传送系统的运行速度等) 受内部和外部因素影响而具有不确定 时，f m s s 中的事件在本质上是随机性的，f m s s 相应地需要采用随r l d e d s s 来描 述 基于f m s s 的d e d s s 模型，可用来确定对待加工工件的排序，分析加工过程 的加工节奏，避免f m s s 出现阻塞现象，优化配置各个缓冲区的容量，以及优化 系统的生产率等 中田科学技术大学硬士学位论文第一章绪论 1 2 离散事件动态系统的研究现状概述 现今，在d e d s s 的研究中，常把d e d s s 的模型和分析区分为三个基本层 次，即逻辑层次、代数层次和统计性能层次d e d s s 模型和分析的逻辑层次， 着眼于逻辑时同层次上研究d e d s s 中事件和状态的符号序列关系，关心的是系 统的逻辑行为，这可以用其演化过程的状态序列和事件序列来刻画，采用的主 要数学工具包括形式语言、有限自动机、p e l r i 网以及m a r k o v 链等d e d s s 模 型和分析的代数层次，着眼于物理时间层次上来研究d e d s s 的代数特性和运动 过程，目的是进一步研究各种操作和演化的时间关系以提高系统的效率，采用 的主要数学工具包括极大极小代数，赋时p e t r i 网等，并采用计划排序，实时调 度等技术进行优化和控制i l 犯“d e d s s 模型和分析的统计性能层次，着眼于在 性能层次上来研究随机情况下d e d s s 的各种平均性能及其优化，主要运用随机 过程，排队网络等模型和理论方法进行分析和研究 一般来说，d e d s s 中某个参变量的微小变化，都会导致系统以十分不同的 方式运行，因此需要考虑系统中许多参变量的随机交化，从而在性能分析中需 采用统计平均的方法实际上，从统计性能层次研究d e d s s ，是d e d s s 研究 的最初形式当初，y c h o 教授等人提出d e d s s 这个概念时，就是从该层次 出发的在这一层次下，采用的主要研究方法，最典型的就是摄动分析 ( p e r t u r b a t i o n a n a l y s i s ，简称p a ) 方法，它主要是由y c h o 教授等人提出的摄 动分析方法是一种将理论分析与计算机仿真技术相结合的方法，经过2 0 多年的 发展，从无穷小摄动分析( 丑p a ) 到非i p a 方法，已经建立了一套有用的技术， 并被成功的应用于各种不同的系统分析和优化中 随着d e d s s 的应用越来越广泛，研究的各种人造系统的结构和行为特性越 来越复杂，p a 方法表现出了较大的局限性，特别是缺乏作为理论的普遍性，故 曹希仁教授和陈翰馥院士于1 9 9 7 年在这个方向上提出了一种新的理论，我们称 之为性能势理论基于性能势理论，可以从系统的一条单一样本轨道上获得系 统稳态性能关于无穷小矩阵摄动的灵敏度公式，因此这种方法可以应用于i p a 方法失效系统的性能分析和优化目前，基于性能势理论，研究m m k o v 系统 和排队网络的性能灵敏度分析问题已经取得了一大批显著的成果 1 3 m a r k o v 决策过程 m a r k o v 决策过程( m a r k o vd e c i s i o np r o c e s s e s ，简称m d p s ) 又常称作m a r k o v 控制过程i a r k o v 决策过程是序贯决策的主要研究领域它是m 龇 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 型随机最优控制的 理论，其决策变量就是控制变量，它属于随机系统最优控制的范畴，更是和 d e d s s 理论密不可分，实际上，它是随机d e d s s 唯一的动态控制方法 上世纪5 0 年代r b e l l m a n 研究动态规划时和l s s h a p l e y 研究随机对策时已 出现m a r k o v 决策过程的基本思想r a h o w a r d ( 1 9 6 0 ) 和d b l a c k w c l l ( 1 9 6 2 ) 等人 的研究工作奠定了m a r k o v 决策过程的理论基础1 9 6 5 年，b l a c k w e l l 关于一般 状态空间的研究和e b d y n k m 关于非时齐( 非时间平稳性) 的研究，推动了这 一理论的发展1 9 6 0 年以来，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 ，【彳，f 明，q ，乃研，其中s 为系统的状态空间；a 为状态f ( f s ) 的可用策 略( 措施，控制) 集；g 为转移概率簇，簇的参数是可用的行动；，是决策得 到的报酬，值与系统所在状态以及选用的策略相关；若观察到的状态为f ，选用 策略口，则下一步转移到状态，的概率为q ( j f 口) ，而且获得报酬r ( j ，c i ) ，它们 均与系统的历史无关；v 是衡量策略优劣的指标( 准则) 策略是提供给决策者在各个时刻选取行动的规则，记作 撑= ( n o ，啊，他，+ l ，) ， 其中，k 是时刻栉选取行动的规则从理论上来说，为了在大范围内寻求最优策 中田科学技术大学硕士学位论文 第一章绪论 略，最好根据时刻n 以前的历史，甚至是随机地选择最优策略但为了便于 应用，常采用既不依赖于历史、又不依赖于时间的策略，甚至可以采用确定性 平稳策略衡量策略优劣的常用指标有折扣指标和平均指标折扣指标是指长 期折扣( 把f 时刻的单位收益折合成0 时刻的单位收益的雳6 0 o ，f o 设p = ( 1 ，l 矿为足维列向量由m a r k o v 过程理论可知 p p = 1 ，a e = 0 ，p ，i = 0 ( 2 1 1 ) 设：西_ r 为一个性能函数，= ( ，( 1 ) ，厂( 2 ) ，厂( x ) ) r ，定义稳态性能测度乃 为关于稳态分布p 的期望值，即 r 钐= 岛们= p ( i ) f ( o = p f ( 2 1 2 ) i - i 下面对稳态性能测度乃的定义做进一步说明考虑m a r k o v 过程y 的一条 样本轨道，记写，= o ，1 ，2 ，为m a r k o v 过程j ，的状态转移时刻，其中瓦= o ， 在任意的一个时间段【o ，瓦】，样本性能定义为 中目科学技术大学硕士学位论文第二章性能势理论 嘭2 专f 厂( 耳矽，工吐2 - ( 2 1 3 ) 如果m a 也o y 过程】，是遍历的，则样本性能磷当三- o o 时的极限，即稳态性能 r 巩2 k 彀耀2 善p ，( f ) 2 p f w p 1 ( 2 1 ， 2 2 实现矩阵和性能势 考虑两条相互独立的样本轨道y 和y ，两者具有相同的无穷小矩阵a 以及性 能函数，分别从状态f 和状态歹出发，即k = i ，- o = ，设两条样本轨道的相 遇时问为 丁= i n f t ：t o ，r = z ( 2 2 1 ) 定义2 1 办= 联f i f ( e ) 一u ) 坤 ，i , j 西， ( 2 2 2 ) 称为m m k o v 过程】，关于性能函数，摄动的实现因子，矩阵d = 【吃】称为m a r k o v 过程关于，摄动的实现矩阵 对于任意的t t v d ，我们有 r ，( - f ) 一f ( y i ) d t , , r l t j ) 一 一 一 = j il 厂( l ) 一厂晖) 】衍+ 厶。l 厂) 一f ( y t ) l d t 因为在时刻r ，琢。= 孙一，由强m 村k o v 性，可知 翌罂e ( 丘。i f ( l ) 一厂( 耳) 】办) = 所以 舰e l 【( 玎) 一f ( r j d t = 占 i l 厂( n ) 一，g ) 】西 ( 2 2 3 ) 一一4，jt 一 根据( 2 2 2 ) 和( 2 2 3 ) ，可以得到 吻= e ( f f ( y , ) c l t r 厂( r ) 】毋) ( 2 2 4 ) ( 2 2 。4 ) 表明了实现因子乃衡量了m a r k o v 过程l ，从状态f 到状态的变化对系 中田科学技术大学硕士学位论文 第二章性能势理论 统性能的影响，用摄动分析的术语说，就是在t = o 是系统从状态i 被摄动到状 态_ ，且在t f f it w 时摄动被系统实现 下面说明实现因子的两个性质从实现因子的定义( 2 2 2 ) 可知 d q = 一d i l i , j 国， 因此实现矩阵具有以下性质 d = 一上尸 ( 2 2 5 ) 由( 2 2 4 ) ，我们可以得到实现因子的另一个性质 d g = d t + d q ，i , j , k e 2 2 6 ) 这个性质类似于物理学中势能的性质因此，我们可以选择一个整数o 和 任意的实数c ，并对任意的f o ，f 矿，定义一个t g i 如下： g p = c ，g l = g c + d k j q 2 定义2 2g l ，i e o 称为 m , 盯k o v 过程l ，在状态i 时关于性能函数，的势 - - 能；列向量g = ( 岛，g z ，) 7 称为m a r k o v 过程y 关于性能函数厂的性能势向 量，简称性能势 由( 2 2 6 ) 式和( 2 2 7 ) 式，我们可以得到 d g = g 广g l ，i , j e m ， 如果写成矩阵形式就是 d f e 9 7 一舻7 ( 2 2 8 ) 引理2 3实现矩阵d 满足l y a p u v 方程 a d + d a 7 = - f ， ( 2 2 9 ) 这里，f = e f t 一力7 证p u ( t ) f f i p z , o = n 和户( f ) = 【助o ) 】p ( t ) 3 0m a r k o v 过程r 的转移概率 矩阵由于状态空间是有限的，那么p = 矿于是 r e 八r m ) = p k ( f ) 翮， 中田科学技术大学硕士学位论文第二章性能势理论 这是向量矿厂的第i 个分量置d ( n = l 氏( 3 1 ，其中 力( d = e f 厂( 矿) 讲卜e r 厂何m w t ， 由( 2 2 4 ) ，有d = ，h i n d ( r ) 又因为 力( r ) = r 【e f 八z ) - e ，( r m ) 】出 d 叮) = r 矿( p 4 ) r _ e 4 f i 7 毋 以及a e = 0 ，故我们有 印+ d ( r ) a 7 = r 旷( 矿) 7 一彳p 血弦 = 矿7 【r p 4 ) 一毋】r 一【r 加) 彳纠户7 = e f 7 。7 8 0 r 一【e 4 7 一e o l 詹7 注意到 触g ”= e p ，e o = j ，e f 7 唧) 7 = ( p f ) e e 7 = e p f e 7 ， n 在( 2 2 1 0 ) 中令r 斗，则有 彳d + d ，蔓7 ；斥7 一矿7 = l 引理2 4性能势g 是p o i s s o n 方程 a g = 一，+ ， f e 的一切解 证将( 2 2 8 ) 式代入( 2 2 9 ) 式，并且由于f = e ，一r e 7 ，我们有 e ( a g + ，) 7 = ( a g + f ) e 7 ， ( 2 2 1 0 ) ( 2 2 1 1 ) ( 2 2 t 2 ) 因为方程e z 7 = 韶7 的解是：= 廖，r ，故方程( 2 2 1 2 ) 等价于下面的方程 a g + f = p e t9 e r 注意到p h = 0 ，= 以一p e = l ，其中p 是稳态分布，则在上面的方程两边同 乘上p ，则有= 嘶，因此g 是方程( 2 2 1 2 ) 的一个解 如果g 是方程( 2 2 1 2 ) 的一个解，那么g + c e ，c r ，也是方程( 2 2 1 2 ) 的一 个解 中田科学技术大学硕士学位论文 第二章性能势理论 2 3 闭排队网络基于性能势的灵敏度分析 基于性能势理论，对离散事件动态系统性能分析与优化的研究取得了丰富 的成果在离散事件动态系统理论中，排队网络已被应用于模拟集成制造系统、 通信系统以及计算机网络等系统的动态特征，所以这类研究越来越受关注。这 一节我们以状态相关闭排队网络为对象，研究它的稳态性能灵敏度分析问题， 给出基于性能势的灵敏度公式删 首先介绍无穷小矩阵群逆的概念由于( 2 1 1 ) 式中的矩阵4 不是满秩的， 所以它的正则逆不存在对每一个满足( 2 1 1 ) 式的p ，相应的a 不是唯一的定 义 以= 4 ：= o ，4 e = o 易验证以关于矩阵乘法是一个具有单位元，一印的群，其中，j 是单位阵 定义2 5 彳在群彳。中的逆称为4 的群逆，记为a 。 设m a r k o v 过程y 的无穷小矩阵彳为区间j t - 且上变化的参数p 的可微函 数，即所有吻= 嘞( 力，i , j o 为口的可微函数且设厂也与口有关，即 厂= f ( i ，0 ) ，f o ，p ，并为口的可微函数由于p 是方程硝= o ，p e = l 的 唯一解，且p 一定存在，所以p 的所有分量都是嘞，f ，o 的有理函数根据 假设吩是目的可微函数，那么p 也是口的可微函数由乃的定义( 2 1 2 ) 可知，乃 也是0 的可微函数 定理2 6 鲁= 叩荔彳7 + p 荔 = 一p 历o a 掣“r t ，历o f 翻钟 邓历g + p 荔 证由( 2 2 1 1 ) 式，我们有 等g + 彳舅= 一荔+ 鲁e 中目科学技术大学硕士学位论文 第二章性能势理论 将上式两边同乘p ，由于倒= o ，p e = l ，所以 斋= p 万0 4 鲫荔，a 8a e 。a 9 由于九r = ，一e p ，所以g = 4 。厂是方程( 2 2 1 1 ) 的一个解，那么g = 一a 。厂+ 韶， c e r 是方程的( 2 2 1 1 ) 的通解又由于彳口= 0 ，所以 历a a g = 历a a ( - 彳，+ 卯) = 一荔彳。厂， ( 2 3 2 ) 历a a 矽= 等( 矿一) ，= 一等g ( 科= 一面a a g ，( 2 3 3 ) 将( 2 3 2 ) 式和( 2 3 3 ) 式代入到( 2 3 1 ) 式，则定理2 6 得证 考虑一个闭的状态相关排队网络，由n 个顾客和m 个服务台组成，每个服 务台都有无限容量的缓冲器，r = l 2 ，膨) 表示m 服务台的指标集。路径概 率矩阵q = 【如】是不可约的，网络的状态空间为 j ， 西= 厅= ( 鸭，如，) ：吩o ，吩= ) ， 其中表示在服务台i 的顾客数，总状态数为 置= ( 肌 每个服务台的服务时间均服从指数分布，且设服务率与系统状态疗相关，用鸬。 表示服务台f 在系统状态为r 时的服务率，腑f f i a r ，珂e 西，o m 。 o o 网络的状态过程为m a r k o v 过程】，= z ；，20 ) ，p = ( 1 ) ，p ( 2 ) ，p ( 芷) ) 是稳 态分布记 甜，= 艇尝 f ( 珂) = f ( 啊) “。 1 - i ( 2 3 4 ) 其中0 ) 称为网络在状态门是的平均服务率下面给出三种稳态性能侧度的定 谬= r l l = e p ( n ) f ( n ) = p f ， ( 2 3 5 ) 中国科学技术大学硬士学位论文 第二章性能势理论 r = p ( n ) l a ( n ) = p a ， ，7 0 9 ：妲， 叩 ( 2 3 6 ) ( 2 3 7 ) 彬称为稳态时间平均性能，矿”称为稳态顾客平均性能，7 称为稳态透过量 m a r k o v 过程l ，的无穷小矩阵4 的第，小) 个元素为 i 占( 伟) “，锄，辨= 飞，f ， 口= 占( 珥) h 吼一( ，1 ) ，朋= 刀， ( 2 ，3 8 ) lo ，其他， 又记为矩阵4 的第刀行元素组成的行向量，且 凡2 嘞薏盯一曲 定理2 7对所有的i ，j e r ，有 肼，筹叫功彬一份m ，) 】+ m 岳， 麒，薏叫功脚叫功一届r i g ( u ) + s ( 绣m ， ( 2 3 9 ) ( 2 3 1 0 ) 参筹刊眠嗍) ( g t r ) _ r c o g o o 巾( 帆) 】+ 伽薏( 2 | 3 1 1 ) _ p ( 硝吖( 砒力一俐氓( g ( ，) 舻蚋m ，p 老 ( 2 3 1 2 ) 这里，g 7 和g 一分别是网络的状态过程j r 关于厂和的性能势 证根据，7 妙的定义和定理2 6 ，可知 秘，警= 嗽。静g ( ，) 坞磋j 由( 2 3 8 ) 式，易知矩阵以，薏除了第 行为一屈，外j 其他元素都是零；由 中国科学技术大学硕士学位论文 第二章性螗势理论 引理2 4 可知= ，( 帕+ ，7 p ，将两式代入( 2 3 1 3 ) 式，得( 2 3 9 ) 式用代替 ( 2 3 9 ) 式中的f ，由于 p 毒塑= 占( 啊) p ( 栉) ， o a h s 可以得到( 2 3 1 0 ) 式( 2 3 1 1 ) 式和( 2 3 1 2 ) 式可以由( 2 3 7 ) 式，( 2 3 9 ) 式和( 2 3 i o ) 式 直接得到 由定理2 7 ，直接得到下面的定理： 定理2 8对所有的r ，有 警一a ag t ) + p 嘞o f ， 叫4 ) ho q i iq 娶：p 婺g ， 1 5 ) 叫c m o 方等2 磋国( f ) _ r t 尝， 6 ， 2 4 闭排队网络性能优化算法 基于性能势理论，对离散事件动态系统的性能优化研究取得了丰富的成 果本节内容以梯度算法为例介绍基于性能势理论的闭排队网络优化算法梯 度算法是性能优化常采用的方法，其基本思想是沿着系统的性能下降的方向更 新策略，一般形式为 l = 唯+ 儿， 其中儿是正步长，最是下降搜索方向，即 ( v s ) 7 峨 o 这里v y 、= 学i 唯是系统性能钡。度关于策略的梯度。由于系统的性能测度沿着负 洲 梯度方向下降最快，因此常取墨= 一w 唯，这种方法成为一阶梯度算法，或者称 为最速下降法、最陡下法、直接梯度法。在这里我们可以采用基于性能势理论的 方法来估计系统性能测度关于策略的梯度的无偏估计值。该算法基于以下的公 - 1 8 中田科学技术大学硕士学位论文第二章性能势理论 式： 触劳 瓦邓瓦g + p 毒。 考虑在上一节中描述的闭排队网络，在其中加入负荷相关的策略1 ，v 是。 个m n 维的向量 1 ，= ( 肚j ，肼，鸬j ，胁一，胁 ，i t u , , v ) 。， 其稳态性能测度j ( v ) 可以表示为性能函数时间平均期望值的极限 ，( v ) = 璺爨研吾r ( 】：，v ( z ) ) 奶 稳态性能代价函数又可表示成 m 以= p k v ) + j i j i ( 玎，v ) 】 = 系统在状态狞的代价由每个服务台的代价z ( ，v ) 之和组成z ( 啊v ) 由两部 分构成，分别是运作代价c a n ，v ) 和维持费用趣以v ) 其中，运作代价是服务率 - 的线性函数，维持费用是服务率的反比函数 f ( n ，1 ，( 厅) ) = q ( 开，v ) + | j i ( 疗，v ) 】，r i c o 对系统进行性能优化的目标是找到一个最优的策略，使其平均代价，达到最 小 对于给定的初始服务策略，当求出稳态性能指标对每个服务率参数的导数 后，就可以在导数构成的梯度方向上进行一维搜索，求得该方向上的最优服务 策略，并以此作为新的起点，按同样的方法不断搜索寻优，以求出最优策略 寻优的算法如下： 第1 步：给定任意的初始策略，计算相应的无穷小矩阵4 ，稳态分布风 以及相应的性能势g o 第2 步：由 a ，副 瓦2 胁瓦g o + p o 毒 中国科学技术大学硕士学位论文 第二章性能势理论 计算孚兰，i - 1 ，2 ，m ，玎o ，求梯度w ， 叭一 = 篇，薏，鼍，静-d 池lo h o | l “o p h 4 第3 步：对于第七步策略h ，计算其梯度w ，然后在梯度方向上进行一 维搜索，求得该方向上的最有策略。 3 1 ：令v o = 唯，给定初始步长 ，计算魄= 1 一力w ，令h = 1 ； 3 2 ：比较l 和，若l p 一，wl 0 ，若0 w o ：x t = i l x o = 力，也就是说五= f ，根据强m a r k o v l 生， 我们可知当上z ( ij d 时，( 3 3 4 ) 式中的第2 项和第3 项相等，又因为 l 憋n e f ( x ，) 】= ，7 ， 所以( 3 3 4 ) 式的第4 项为零那么，( 3 3 4 ) 式就能化简成以下形式： 中国科学技术大学硕士学位论文第三章性能势和实现因子的常用计算方法 d ( i ，力：以警。l 厂隅) - , 1 j i x o ；力 ( 3 3 5 ) ，l o ( 3 3 5 ) 式就是基于单样本轨道的实现因子公式，以上的推导可以用图3 1 来说 明； 0 b ) 一4 jii66 f o 率a 汀)( 订)( i i i ) l 己“h ) = 7 l 。1 1 丸一i 图3 1 图3 , 1 中的第( i ) 部分对应于( 3 3 4 ) 式中的第1 项，第( ) 部分对应于( 3 3 4 ) 式 中的第2 项和第3 项，第( 1 1 i ) 部分对应于( 3 3 4 ) 式中的第4 项 3 3 2 实现因子和性能势盼无偏估计 根据基于单样本轨道的实现因子和性能势公式，我们可以用计算机仿真出 一条m a r k o v 链的样本轨道，从这条样本轨道上获得实现因子和性能势的无偏 估计 我们假设已经用计算机仿真出了m a r k o v 链的一条样本轨道，m a r k o v 链为 z = j 瓦；疗，具有状态空间m = l ，2 ，m ) 以及转移矩阵p = 【p g 朋产生 样本轨道的方法如下； 第1 步：给定初始状态五； 第2 步：当前状态设为x - - - x o ； 第3 步：状态转移用计算机产生一个【o ，1 】区问上均匀分布的随机数f ， 如果f 满足金p ( x ，j ) s f l ，有d = t l i r a d ( k ( 4 1 1 ) 上面的迭代算法不用事先求解稳态分布万，但是每一步迭代都要作两次矩 阵乘法，计算量比较大 4 2 基于实现因子定义的迭代算法 在第三章中给出了实现因子的定义： 4 d ) - 1 d ( i ，歹) = 研u ( 聊n ) - f ( x y ) ) 】，i ，j = 1 ，2 ，m ，- o 如果两条m a r k o v 链只用了一步状态转移就相遇了，此时可以假设条件是转移 矩阵p 的每一行都是完全一样的，那么显然有d ( f ，力= d ，( f j ) = f ( j ) - f ( o 如 中置科学技术大学硕士学位论文 第四章不依赖稳态分布的迭代算法 果两条m a r k o v 链用了两步状态转移相遇，那么 ， d ( f ，力= ( 如一m ) 厂( 的+ d ，( i 力 k - i 由上面的两步假设，不妨设 丑， d o ( i ，力= ( 力一厂，d 2 i f , j ) - - ( 苏一m ) 厂( 七) + d ，( f ，力， i - i 其中两步相遇情况下的实现因子也可以写成： “ d ( 2 ) ( f ，) = 【p 业，( 的+ 加) 卜【p 墙f ( k ) + f ( o = f 2 q 3 - f 2 f f ) ， 正= 最，( _ | ) + m ，1 = i ，2 ，m k - i 如果两条m a r k o v 链用了三步状态转移相遇，那么由实现因子的定义 f d 0 ) ( f ，d = ( 如一m ) 正( 功+ d ，( 力 k - i f 埘 = 匹办丘+ 几，) 】一【如正( 七) + ，( i ) 】 k - ik l l 、 = 石( ，) 一石( 彳) 依次类推，下面给出迭代算法： d 1 ( _ ，) = 一用) ，d “( f ，力= 厶i 一厶l ( o ，j 2 1 ， 令，= 1 ，2 ，m ， ， 石= ，厶。= 厂u ) + m z ( k ) ，s = l ，二，2 “， k - 1 d ( i ，力= t i m d ( ) ( i ，力，f ，j = t ，2 ，m ( 4 2 1 ) 这个算法同样不需要计算稳态分布- ，而且每次迭代的计算量相当于次矩阵 乘法 4 3 基于耦合技术的迭代算法 回顾一下第三章所述的方法( 3 2 3 ) ，设r = p - e ：x ，则有 中田科学技术大学硕士学位论文 第四章不依赣穆态分布的迭代算法 g = ( j + 皿+ r 2 h ，+ 矗4 ，圹， ( 4 3 1 ) 如果稳态分布石和代价函数，正交，即，r ，= 0 ，则由( 4 3 1 ) 式和( 4 3 1 ) 式可知， 此时计算性能势g 时可以避免计算稳态分布，r 。我们将使用耦合技术来构造出 定义4 1 r q 。a 1 1f 岛。岛，1 设矩阵4 。= i ij l ，= l ； 一 ；l ，定义矩阵的k r o n e c k 髓 i 。jl j 叫誊= l 彳0 口= i ； 1 l i 曰嚣。 以= 眙o d 一( i 固e ) i g = p o g ) 一( g p 力， 办和噍都是长为m 2 的列向量 定理4 2如果非负矩阵满足下面的条件 c a ) ( ，9 力= ( j o 力p ， ( 6 ) 欲e o d = ( e o d p ， 则的稳态分布；与哆正交，r 满足( i