（计算机应用技术专业论文）smdp基于性能势的异步优化算法.pdf

s m d p 基于性能势的异步优化算法 摘要 随糟社会和科技的发展，离散事件动态系统( d e d s ) 的性能分析和 优纯应糟已经成为控秘与系统、管壤、计算撬等学群交叉领域蠢翡个藩 沿鹾究方肉。半岛絮霹夫决蓑过程( s m d p ) 乍为现实中类广泛的系统 模型，可以用来描述大部分的实际系统。由于实际应用的需要，s m d p 的 优化控制已经成为控制理论界的研究热点之一。性能势理论的完善为 s m d p 静优纯控籁提供了巾较为竞整懿理论捶絮。 本文主疆在性能势的基础上，磺究s m d p 在紧致行动集上的异步优化 算法，。鼠所有算法是折扣准则和平均准则统的。首先介绍了s m d p 在紧 致行动巢上罄于无穷小矩阵的标准数值迭代，给密算法，并证裙箕较敛 性，舅外讨论了嚣张性裁准则下媳异步数值迭 弋冀法，其中主要分缨 g a u s s s e i d e l 迭代和基于样本轨道仿真的异步数值迭代。然后旌于性能势 的思想对有关的算法进行改进。以上研究结果均可适用于连续时间马尔可 夫决策避程( c t m d p ) 。 毽统斡理论计算优化算法优化糙度巍，拢化速度快，但不能适用于大 规模系统，而基于仿真的优化算法，如t d 学习、n d p 优化等_ 西丁以解决理 论优化算法的问题，结合这两种方法的特点，本文讨论了昴步策略迭代的 尼释形式，魏醚步囱 ；萋繁珞悲 弋，基予t d 学霹的嫩步囱蓑策路迭代， 基予n d p 学习的m 步向前策略迭代算法。以上几静算法均是折扣准则与 平均准则统一的。 本文用个s m d p 的数值实翻来说裙相关德亿算法酶应甬，院较各耱 算法的傀缺点，该缝榘可以壹接运用到连续黠间马尔可夫决策过程中。 在异步优化算法的基础上，文章还介绍了优化仿真平台的构建问题， 该平台可根据实际系统的需要，设定参数值，为部分系统的性能优化提供 便利。 关键词：半m a r k o v 决策过程、性能势、异步遮代、优仡仿真平台 a s y n c h r o n o u so p t i m i z a t i o na l g o r i t h m sf o rs m d pb a s e do n p e r f o r m a n c ep o t e n t i a l a b s t r a c t w i t ht h ed e v e l o p i n go ft h es o c i e t ya n dt e c h n o l o g y ，t h ep o t e n t i a la n a l y s i s a n do p t i m i z a t i o no fd i s c r e t ee v e n td y n a m i cs y s t e m ( d e d s ) h a sb e c o m ea n a d v a n c e ds t u d ya s p e c ti nc r o s sf i e l do fc o n t r o la n ds y s t e m 、m a n a g e m e n ta n d c o m p u t e r t h es e m i m a r k o vd e c i s i o np r o c e s s ( s m d p ) c a na n a l y s i sm o s to f s y s t e mi ns o c i e t y m o t i v a t e db yt h en e e d so ft h ea p p l i c a t i o n ，t h eo p t i m i z a t i o n o fs m d p sh a sb e e no n eo fr e s e a r c hf o c u s e si nt h ec o n t r o f i e l d p e r f o r m a n c e p o t e n t i a l st h e o r yp r o v i d e sau n i f i e df r a m e w o r kf o rs m d p s ，o p t i m i z a t i o n t h i sp a p e ri sc o n c e r n e dw i t ht h ea s y n c h r o n o u so p t i m i z a t i o np r o b l e m so f s e m i - m a r k o vd e c i s i o np r o c e s s e s ( s m d p s ) w i t hc o m p a c ta c t i o ns e tb a s e do n t h ep e r f o r m a n c ep o t e n t i a l ，a n da l lt h ea l g o r i t h m sf o rb o t hd i s c o u n t e da n d a v e r a g ep e r f o r m a n c ec r i t e r i a f i r s t ，t h eu n i f i e ds t a n d a r dv a l u ei t e r a t i o n ( v r ) a l g o r i t h mb a s e dd i r e c t l yo nt h ee q u i v a l e n ti n f i n i t e s i m a lg e n e r a t o r i s c o n s i d e r e d ，a n dt h ec o n v e r g e n c ei se s t a b l i s h e d 。s e c o n d ，t h eu n i f i e d a s y n c h r o n o u sv ia l g o r i t h m si n c l u d i n gg a u s s s e i d e li t e r a t i o na l g o r i t h ma n d a s y n c h r o n o u sv ia l g o r i t h mb a s e do nt h es i m u l a t i o no fas a m p l ep a t h 。t h e n ， a c c o r d i n gt ot h ep e r f o r m a n c ep o t e n t i a lt h e o r y ，t h ec o r r e s p o n d i n gm o d i f i e dv i i sd i s c u s s e d 。t h ea b o v er e s u l t sw i t lb ea p p l i c a b l et oc o n t i n u o u s 。t i m em a r k o v d e c i s i o np r o c e s s e s t h et r a d i t i o n a lt h e o r e t i c a la l g o r i t h m sc a nc o m p u t eq u i c k l ya n dt h e o b t a i n e dr e s u l t sa r ep r e c i s i o n ，b u tc a nu s u a l l yn o tb eu s e dt o o p t i m i z e l a r g e s c a l es y s t e ma n dt h es y s t e mw i t hn o tm a n yi n f o r m a t i o n t h es i m u l a t i o n o p t i m i z a t i o na l g o r i t h m ss u c ha st e m p o r a ld i f f e r e n c e s ( t d ) l e a r n i n ga n d n e u r o - d y n a m i cp r o g r a m m i n g ( n d p ) o p t i m i z a t i o na l g o r i t h m sa n ds oo nc a n s o l v et h ea b o v ep r o b l e m b a s e do nt h e s ec h a r a c t e r i s t i c ，t h ep a p e ri n t r o d u c e d t h eu n i f i e da s y n c h r o n o u sp o l i c yi t e r a t i o n ( p 1 ) ，s u c ha sm u l t i s t a g el o o k a h e a d p o l i c yi t e r a t i o n ，m u l t i s t a g el o o k a h e a dp ib a s e dt dl e a r n i n ga n dn d p t h e s e a l g o r i t h m sa r eu n i f i e df o rb o t hd i s c o u n t e da n da v e r a g ep e r f o r m a n c ec r i t e r i a a tl a s to n en u m e r i c a le x a m p l ei su s e dt os h o wt h ed i f f e r e n tp r o p e r t i e so f t h ea l g o r i t h m s t h eo b t a i n e dr e s u l t sw i l lb ea p p l i c a b l et oc o n t i n u o u s t i m e 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 ) 。 b a s e do nt h e a s y n c h r o n o u sa l g o r i t h m ，t h ep a p e ri n t r o d u c t i o n t h e i i o p t i m i z a t i o ns i m u l a t i o np l a t f o r m ，t h ep l a t f o r mc a ni n p u ts u i t a b l ep a r a m e t e r b a s e do nt h e s y s t e m ，a n dp r o v i d ec o n v e n i e n c ef o r t h ep e r f o r m a n c e o p t i m i z a t i o no fm o s ts y s t e m s k e yw o r d s ： s e m i - m a r k o vd e c i s i o n p r o c e s s ，p e r f o r m a n c ep o t e n t i a l s ， a s y n c h r o n o u si t e r a t i o n ，o p t i m i z a t i o ns i m u l a t i o np l a t f o r m i i t 插图清单 爨1 一ld e d s 綦秀究豹范醛。，。2 阁3 - 1 标准数值迭代在折扣因子连续变化时折扣代价瞻( ) 的变化曲线2 7 潮3 2 改进数僮迭代在挺扣因予连续变化时折扣代价啦( i ) 的变化曲线。2 8 圈41c r i t i c 逼近结构黼3 0 阁4 - 2m 步向前异步策略迭代的优化性能3 8 豳4 - 3 慕于t d 学习的m 步向箭策略遮代的铙优性靛3 8 阁4 4 不同折扣因子下的折扣代价4 0 黼4 - 5 蕊子n d p 静m 步两前策貉迭 弋鹩饶讫过程。鹌 图5 一l 数值迭代算法选择界面4 3 鬻5 - 2 舞步数穰迭霞算法懿参数设置器嚣。4 4 圈5 3 策略迭代的算法选择界面4 5 瓣s 一4 姒步囊懿异步策骧迭代参数设置爨嚣。4 5 图5 - 5 慕于t d 学习的m 步向前策略遮代算法参数设窳4 6 阁5 - 6 基于n d p 的m 步囱翦蒙路迭代驰参数设定4 7 圈5 7 仿真平台的操作流程。4 9 v l 表格清单 表3 一l 标擦数值迭代在不阚手厅糖因子时靛伉化缝装。2 8 表3 2 改邋懿稼准数值迭钱在不嗣掰籀罐子时瓣饶纯缝票。，2 7 表3 3 昴步数值迭代的优化结采，2 7 表4 一lm 步向前异步策略悠代在m 取不同值时的优化结果3 7 表4 2 基于t d 学习的m 步向前策略迭代的优化结果3 7 表4 - 3 鏊予n d p 的m 步向前策略迭代在m = 3 时刁；同学习步数的优化结果3 8 表4 4 蒸予n d p 豹m 多淘 l 繁醢迭我在n = 5 0 0 0 辩不同m 篷豹饶纯缝莱，3 9 表4 - 5 务耱算法结采魄较。+ 3 9 v l i 独仓性声明 本人零臻鳆呈交弱学位论文廷本人在导瘘谨等等避褥瓣疆究王俦及取键滟臻燮或暴。摆我掰 知，除了文中特别抽以标志和致谢的地方外，论文中不包禽其他人已经发表戏撰写过的研究戒果， 也不包古为获得金魍王些鑫擞 或其他教育机构的学位或证书而使用过的材料。与我一同i = 作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：蓼、鱼笮签字日期：茹护年f 月罗日 学位论文舨较使雳授权书 本学位论文作者完全了解愈勰王业盍堂有若保留、使用学位论文的规定，有权保留井向 国家有荚部门或机构送交论文的鬣印件和磁盘，允许论文被查阅或借阅。本人授权盒日b 王些去堂 可以褥学经论文懿全部或部分谂文浅謇鳊入有关数爨露避嚣检索，可以粟瘸影印、缩印或扫拯等 复铡手毅傈存、汇编学植论文。 ( 保密的学位论文在解密厝通用本授权书) 学位论文者签名；孑t 玉牮 签字嗣期：趔6 年月孑日 学位论文作者毕业后去向 】二 誊攀爱： 邋讯地址 导师签 签字日 宅话： 邮编： l 致谢 本论文是在导师唐爨斟教授的精心指导下完成的。从论文的选题、研 究方案戆制定隧及论文的写作，唐老师一裹给予我耐心指鼯、热心帮助和 严辫要求。在硬究生攀浑酚段，1 | 蓦老麴严谨的治学终嚣、诲天不倦麓教学 态泼、爱岗敬业的精神让我终身受益。在此，衷心感谢唐老师在学业上的 悉心激诲以及生活上无微不至的关怀。 特别要对韩江洪教授及其领导下的分布式控制实验塞的老师们表示 最诚挚的谢意，他们为浅的研究和论文作创造了有利的科研环境和学术 氛黧，提出了多方嚣瓣宝奏建议。 震心感谢毫隽教授及箕领导下熬秘校剑叛群体的大力支持，铷耘群髂 为我们研究工作的顺利开展提供了多方糊的支持和资助。 感谢课题组的袁继彬、刘春两位师兄以及陈栋、周雷锋课题组中的同 学，感谢他们在课题研究中给予我的启示和帮助。 感谢计算枫学院和学校有关单位的领罨、老师的关一陌鄢支持。感谢所 麓聚韵避我熬尺翻。 最后特别感谢我的家人，感谢德们对我始终如一豹关怀和支持。 i v 作辫吴玉华 2 0 0 6 每5 秀l s 嚣 第一章绪论 本章中，简要介绍离散搿件动态系统f d e d s ：d i s c r e t ee v e n td y n a m i c s y s t e m ) 、马尔可夫决策过獠( ( m a r k o vd e c i s i o np r o c e s s ，简称m d p ) ) 及半 骂蠡可夫决黎过程( s m d p ) 静纂本羟识，分缨本文繇涉及静一墅基本壤念 稆基本的理论。最后，余缁本文的文章结襁。 1 1 离散零件动态系统 离敷豢传动态系统臻的怒幽离散事件触发褥弓| 起状态转移的类鑫 然兹或入逡豹动态系统，曼霾| 飧镶大学懿餐藏酶等学者在上签爨a 卡年饩 前后正式搬出的概念l l 。j 。d e d s 是系统和控铡毽论中的一个新兴分支与 前沿方向，有着广泛的应用领域。 d e d s 是复杂的人造大系统，需要系统理论、控制论、运筹学、人工 智能和计辫机科学等多学科嬲交叉研究。从原遐上说，d e d s 属予运筹学 ( o p e r a t i o nr e s e a r c h ) 豹范薅。然瑟，d e d s 笈袋至今已驭整裁谂器系统谂 中吸取了诲多有益静养分。睡l 于d e d s 貔人遮系统的特征，人工智能在 d e d s 的发展也起到了相当大的作用。目前，随机受控d e d s 的隧能分析 和优化应用，已成为控制与系统、管理、计算机和数学等学科交叉领域内 的一个前沿研究方向和研究热点。d e d s 模型的研究范畴如图l 。l 所示。 d e d s 是一类特殊、复杂瓣动态系统，英演德过程不能由通露浆徽分 方程 0 ，定义随机矩阵它= 三( 珥) 一1 ( p ”一残) 。再定义 c = 【正( 1 ，v ( 1 ) ) ，兀( 2 ，v ( 2 ) ) ，l ( k ，v ( 置) ) 】_ ( q 厂”) p ，这里运算符号“e ”表 示两个矩阵对应元素分别相乘。可以证明的定义同文献 5 0 中方程( 3 1 ) 的 定义等价“。记露= h 碘之，且片= ( 露q 厂”扣，根据( 2 3 ) 式有 d u + f ”= 嚣= l i 罂。根据文献 5 0 和 5 1 ，有l i m + a ( a l 一) = e ，则 十 8 4 u 硝= p 石。f = e r ”= 掰 这说明z 的平均代价问题可以看作是折扣问题的极限情况，是其特例，故可以 统一研究。对任意口0 ，优化目标就是在策略空间上寻找一个最优策略v + 满足 v + a r g r a 。i n 珑。为保证最优解的存在性，作下列假设。 假设1 对任意f ，o ，r 0 ，岛( v ( f ) ) ，f o ( t ，v ( f ) ) 和，( f ，v ( f ) ) 是定义在d ( f ) 上 的连续实值函数。 2 2 半m a r k o v 决策过程和口一一致化m a r k o v 链 s m d p 的优化问题比较复杂，近来，s m d p 性能势的定义为其优化框 架的建立奠定了很好的基础【5 0 1 。通过等价无穷小生成子的定义，以前关 于m d p 的基于性能势的一些优化理论和方法，在适当的情况下可以推广 到s m d p 中。为了研究s m d p 的优化问题，本节首先通过s m d p 等价无 穷小生成子的概念，定义s m d p 的a 一致化m a r k o v 链，口0 。 2 2 1 等价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 决策过程。 仍然考虑2 1 2 繁中的半m a r k o v 过程菇。蓄先根据文献f 5 l 碜出 s m d p 的等价无穷小生成予的定义，该定义岛文献f 5 0 】中的等价无穷小生 成子的定义形式不一样，假实质意义是一样的。先令 9 p ) = ( ”( 1 ，如，h 7 ( 2 ，吐，h ”( 量，) ) 。= ( 一q ”( ，) ) p ， ( 2 4 ) 这墼8 - - ( 1 ，l ，1 ) 7 是鬈缝列囱整。显然，矿瓴玲= l 一坌7 ( f ， ) 。 定义 鳞= 线( f ，) 】= 昏“q ”( 西) 且 霹任意群0 ( 2 5 ) = ( h j o ) ，壤( 耘，筏皤) ) 7 = 昏“h ( t ) d t ， 当瑾= o 孵，饼= ，蹦u ) 袭示盖在状态i 的平均逗留时间州：f ) 。翁证 让蟛= ( i 一碰) p ( 2 6 ) 定义娥= 搬( ( 1 ) ，( 2 ) ，( 秘) 。于是对经懑辞 - 0 ，定义矩降 2 ；螂蚶卜哆”霉 像，) = 【a 。v ) “( 搿以+ 线，) = ( 娥) “( g 一，) 这里彤= 搿磁+ 蛾。可以证明的这种定义网文献 s o 中的定义实际上 是等徐熬。由方程( 2 g ) 荔麴是“糅守”转，舔滚是 群e = 0 ，( 2 8 ) 且( f ，f ) o ；群( f ，) o ，i 棼 v f ，中。可见群具有同连续 f c q m d p 无 穷枣生成子撵豹性质，救拣秀s 酝d p 静镣徐无穷小生戏子，( | ，力为 等价转移速率。令= ( i t 1 。v ( 2 ) ，旧) ，篮满足 群= 0 ，8 ；1 。 ( 2 9 ) 由予x 遍历且零有限，荔_ i 芷是方程( 2 9 ) 的唯一解，且为囊 5 1 1 。另 努骞 罐l i m ，n - ：, ，= t i m ，a l ! ：, 硝即为x 的稳态分布疗f 5 “，且记a ”= 硝。相似于m d p ，方程( 2 9 ) 可 以看作是s m d p x 在口- 折扣准则下的等价平衡方程，口0 ，故称之为z 的 a 一平衡方程。 现在考虑- - + m a r k o v 过i l x = 置，r 0 ) ，其具有状态空间中，无穷小 矩阵为群，稳态分布为。因此，对同样的性能函数，m a r k o v 过程和 半m a r k o v 过程x 具有相同的稳态性能。于 s m d p ( 五，o ，d ，q ”( r ) ，”) 等价 于一个连续时i 司m d p ( x ( f ) ，中，d ，彤) 。 2 2 2s m d p 的口一一致化m a r k o v 链 s m d p 性能势首先是定义在随机过程的样本轨道上，其概念具有明确 的物理意义，并且s m d p 性能势的定义同s m d p 的p o i s s o n 方程的解具有 紧密的数学联系。 令 屯= ，船( 磋( f ) 卜 ( 2 1 0 ) 由于中有限且d 紧致，则根据蹦的定义易证 凡。磐以口 定义一个随机矩阵或= 【死( f ，v ( f ) ) 】 4 s l 为 弘击“， ( 21 1 ) 且记芦”= 刷。则或对应一个m a r k o v 链牙= ( 瓦，中，d ，f ：，石) ，称为s m d p x 的 一个口一一致化m a r k o v 链【4 5 1 ，对应任意口0 ，牙的折扣因子为 尾= l 。 牙的平均性能准则1 4 5 】定义为 弘l i m l e 酚舶c 剐 ， 折扣准则定义为 髭( f ) = ( 1 - 尾) e l 善雕正( 以v ( 瓦) ) i 五刮j ，o 尾“- 这里，算子符号科】表示关于转移矩阵只的期望。同珑表达式中的 因子a 的作用一样，符号“l i m ”前的因子1 - 尾也是为了保证畦( f ) 关于以 在成= 1 处的连续性。记鬣2 ( 鬣( 1 ) ，髭( 2 ) ，鬣伍) ) 7 ，且鬲。= 牌砝， 则有g l ”= p 虿” 4 9 o 由文献 4 5 得，对任意a o ，即0 o 时，上式即为丰斥扣 p o i s s o n 方程，= o 时为平均等价p o i s s o n 方程。易证l i r a 或= ，记”= 醮。, g og * ，v 对任意的a o ，即0 0 ，任选一初始策略岵和k 维向量g o 。 s t e p2 选择k 满足 心+ ，a r g 卿 尼+ g 。茂丸+ g ) ( 3 t ) s t e p3 计算 g “4 = ，”+ ( 4 “+ 丸j ) g ，( 气+ 髓) ( 3 5 ) s t e p4 如果s p ( g “1 - g ) 嚣，则记叱= u 算法停止。否员皤令k 津k + l ，转 s t e p 2 。 令弓= 旌，屯+ ，成= 五( l + 口) ，易证霹楚一个随梳矩阵，筐可戳看作 是s m d p 熬个一致链豹转移矩阵，值迭代方程( 3 5 ) 可写为 g “1 一露“+ 成蛩”9 4 方程( 3 4 ) 等价予k + l 毫a r 9 1 。t l l n ，( f ：+ a p t g 。 ，因此s m d p 基予静数 豢迭 弋 等价子其一致链夏= ( 五，零，d ，露，石) 韵数穰遗代，它与文献e 3 9 中的数德迭l 弋 不同之楚在于，首先这篓无需计簿玲阵弓，且性熊蠡数石不露转换，其次它 对s m d p 的折扣和平均准则是统一的。我们有下列收敛性定理。 定理3 。l在假设1 下，对任意的群0 ，上述标准数值迭代算法满足 ( 1 ) l i m ( g “5 一9 2 ) = j i m ( r “g 。一r 矿) = ( 反尹1 9 矿( 搿) ，这里扩是最伐繁 a t n 一 蝮。 2 ) 算法在裔双步内以一个# 一最傀( - o p t i m a l ) 燕略停止。 这里，如果一个策略v 满足统以黜，蒯称萁为楚占- 最优的。它对折箱和平 均褥种性能准则都适用。该定理涯明见3 1 。2 节。 l s 3 1 2 收敛性证明 证明：该定理的证明过程与文献 3 9 中的定理5 的证明类似，但此处我们 考虑的是直接基于的数值迭代算法，且对两种性能准则都适用。 首先，对任意的k ，g 和g “1 满足 g = f 2 + ( 爿0 + 丸，) g - 1 ( 以+ 口) - f j + + ( 4 j + z o z ) g 。一1 ( 丸+ 岱) ( 3 6 ) g 一= ，1 + ( 爿0 1 + 乃，) g 一2 ( l + 口) - f f + ( 4 i + 以，) g 一2 ( 屯+ 口) 根据递推关系有 g 岛+ 鼠g 。 ( 3 7 ) n = 0 这里，定义e = ( 群+ 以，) ( 丸+ 口) 】”，n 1 ，且鼠= ， 则 b e = ( 见) ”e 。 由文献 4 5 知 易证 再由( 3 1 ) 和( 3 2 ) 得 懿= ( 丸+ o o g ： g ：= p o ( 彤一，) 戢 珑2 彤+ 或= 口残+ 五e 戎或= ( ，一成) g ；o + 展疗 ) e 所以 2 珑一= ( ，一p o ) 豌+ 尾o ( a ) e 一或 = ( j p o ) ( 以+ 口) g ：+ 尾f l ( c t ) e 一占： = ( 口一) g ：+ p o f l ( c t ) e = _ ( + 九，) ( 九+ 口) 】或( 五十口) + ( 九+ d ) 或+ 反o ( a ) e 因此 f j = _ ( + 屯，) ( 九+ 口) 或( 以+ a ) + ( 屯+ 口) + 尾斫” ) 因为a ；e = 0 ，则把其带入( 3 7 ) 式得 g k k - 1 e 一旦( 厶+ 口) + ( 丸+ 口) g ：+ p o 研? ( 口) 】+ 毋g 。 = 【一b o + 彰( 丸+ 口) + 鼠( 以+ 口) 彰+ b p 0 8 0 ”+ ( 口) 】+ 壤矿 9 = ( 丸+ 口) g ：一b ( 以+ 口) 彰+ 最见研” ) + 且g 。 n = o ：( 丸+ 口) g ：一且( 九+ 口) g j + k - 1 ( 尾) n + l e ( 口) + 境g 。 k l = ( 以+ 口) g i + ( 尾) ”1 研+ ( 口) + 壤 g 。一( 丸+ 口) g ：】 h 一0 k 一1 ( 九+ 口) g j + ( 尾) 研”( a ) 慨m a x e g 。一( 丸+ 盘) g ： ( f ) ) p n = o i e 0 = ( 九+ 口) 彰+ 萎k1 ( 尾) 斫” ) + ( 尾) 。学 g 。一( 丸+ 口) g ： ( f ) ) e ( 3 8 ) 对应算法得迭代过程，定义一个确定性的m a r k o v 策略v = ( v l ，v 2 ，) ，由( 3 5 ) 式通过迭代得 g = z ? + ( 4 + 以，) g 。( 丸+ 口) = 口+ ( 臂+ 以眦口q ( 露一1 + x o s ) g “( 以+ 口) ( 五十口) 这里定义 = 群1 f 2 + b k g o ( 3 9 ) 硝= ，； 聊= ( 4 0 + 丸i ) ( 2 + 口) 】 ( 4 。1 + 以，) ( 屯+ 口) 】 ( 4 1 “+ x 0 1 ) ( , t o + 口) 】，1 - n 时，恒有 s p ( g 。“一g k 、 0 时，有 破= a ( a i 一露) 。口 。a ( a l a 2 ) _ 1 学+ ( 露+ 屯，) g “1i ( l + 口) 一g “3 + c t g 。一1 ( 五+ a ) = a ( a i 一4 ) - 1 【g 一g k - i + 口g 。1 ( 屯+ 口) 0 ，任选一初始策略v 0 和世维向量g o 。 s t e p 2 若栉k ，重受弹= 1e 选择更辨镣赡礁+ ，满足 v k + t ( f ) 芒a r g 姚饭( f ，v ( ) ) + a o ( i ，j , v ( 0 ) g ( ) 饥+ a ) ，i = n 唯“o ) - 心( f ) ，i 行 s t e p3 按下弼公式计冀g “ g k , i ( f ) = 正( f ，v k 。( f ) ) 十，( 以( f ，工唯( j ) ) + 屯州，：) ) 矿( j ) ( 五十口) ，i = n g “( f ) 矿( ) ，f 雄 s t e p4 若s p ( g “1 一g ) 0 ，任选一个初始策略和足维向量g o ，以及初始状态。 s t e p2 选择更新策略v 。满足 v k + l ( f ) a r g 舁恕 五( f ，v ( f ) ) + ，以( f ，v ( f ) ) 9 2 ( ) ( 九+ 口) ，f _ 噩 唯+ ( 叭= k ( f ) ，i 鼍 s t e p3 按下列公式计算g “1 g k + l ( f ) = 五( f ，u + ，( f ) ) + j ( 以( f ，_ ，咋+ - ( f ) ) + 九州，：) ) 矿( ) ( 乃+ d ) ，i _ 五 g k + l ( f ) = = g k ( f ) ，i x k s t e p 4 若s p ( g “1 一g k ) 0 ，即0 位l ，2 7 的折扣因 韵成2 去，夏p o i s s o n 旆为 ( i - 以露+ 尾e ) g 危= 片， 则有 酸= ( 九十口) 残 易证 或= 恁( 鬈一d 爵 博由( 3 1 ) 和( 3 2 ) 得 蹿：= d 或+ 玩辱。皎弦= ( i 一热) 酸十玩牙” 弦 ( 3 1 3 ) 瓣j 鞋： 片+ g ：一珂：= 片+ 成露残一兹一尾矿位) e 嚣最往性方程( 3 。3 ) 变为 o = r a 。i n 石+ 慝鬈蕺一弦一危矿 ) 8 可写为 或= ? 磐 + 见气一v g - - 疙v * 一致 ) 8 ( 3 。1 4 ) 已知对任意的策略v ，一致链的髋能势是有界酶，因此为保证迭代值 的有界，根据錾于性能势的最优性方程( 3 1 4 ) ，避用性能势的思想，我们 硼以构造改避豹数值迭代算法，例如在标准豹算法中，保持s t e p2 的公 式( 3 。4 ) 不变，僵s t e p3 懿毽遮代公式( 3 5 ) 交魏 g “= “+ ( a 2 “+ 屯j ) 9 4 ( 以+ o e ) - 屁疗( 口) e 这撑在每次迭我霹需要 中冀等徐m d p 熬乎均我价矿板) ；在各耪募步数蓬迭 弋 算法中，使这代公式变为 g k + j ( j ) = 工( 屯咋+ 。( f ) ) + ，( 以( f ，j ，v k + 1 ( f ) ) + 九州，：) ) 矿( j ) ( a o + 口) 一风牙( 口) 毅逶嚣鹣数毽迭伐墓蒸零瑟怒与糖准数蓬迭代豹愚想是一毁夔，只是 对性能势的迭代公式有所调整，以保证迭代值的谢界。 改进后邀代算法的性能势的迭代值不会随着步数的增加丽增大，而是 在定的数德范围内波动。该愚想在蠢些算法中怒必要豹，这在第四章介 绍静算法中簸可充分俸蕊。 3 4 数值例予 考虑文献 4 5 中给出的个s m d p ，令垂= l 2 ，3 1 ，d = o 5 ，3 5 】，在策略v 下随机过程嵌入链的转移概率满足 p 。( v ( f ) ) = ! 黧! 二型2 1 笠 j * n e x t 十 一v ( ) ) ) , m o e x p ( 1 一p o ( v ( f ) ) ，= n e x t ， i # 狴m 1 这里n e x t , 为状态f 的下个状态，当i = l ，2 ，3 0 时，n e x t ，= f + l ；当i = 3 1 时 n e x t , = 1 。牲戆溅数，( i ，v ) ) = k 瓣+ 1 ) v ( ) 】+ 、i ( 2 v ( i ) ) ；过程在状悫f 鹩逗黧时 间服从三阶e r l a n g 分布，即 毛也v ( 功= f a t ，v ( 秘= 1 - e e x p ( t u ”t ) e ， 一1 1 0 1 这里，t 州= 3 v ( i ) 10 - 1 l l ，口= 【l ，1 ，1 7 ，e t = f 1 ，0 ，0 】。 00 1 | 运用文中的算法，我们取丸= 3 6 + 得到以下实验绻果。 袭3 - 1 是稼准鼗蘧遮俄算法程占取t 0 正辩在不磷辑撩嚣予霹静蓊磐维 果，其中k + 1 袭示算法停止时总的迭代步数，f 7 。( 掰) 为停止策略对应的等 徐m d p 豹孚麓代徐。霹潋爱裂，搿= e 帮警均准弱馈嚣下，冀法求出鹣套 个折扣代价在密许计算误差范围内完全相簿，近似为平均代价最优值。在 g 增大时，运行步数逐濒变小，运行时间变短，而且g “1 一g 。和瘁。 ) 验 证了定理1 1 ) 。 袭3 - 1标准数值迭代在不同折扣因子时的优化结果 辩黼迭 弋多 卜 话( 1 )瞎( 1 6 )砖( 3 1 )g “一g 矿 ) ( 8 ) 数k + 1 i 群= 0 3 。7 1 7 5 6 3 23 7 1 7 5 6 3 23 。7 1 7 5 6 3 29 1 51 0 13 。7 1 7 5 6 3 23 7 1 7 5 6 3 2 l 口= 0 51 9 8 9 5 0 2 54 1 4 0 5 3 9 03 6 8 2 4 8 7 74 4 。26 0o o o l 6 5 9 73 6 1 2 2 4 5 8 a = 11 4 8 7 0 0 6 34 3 0 9 6 0 2 93 8 7 1 1 4 2 33 0 2 4 20 0 0 0 1 4 1 83 5 3 7 0 0 0 7 对应表3 - 1 ，表3 - 2 为改进的标准数值迭代的优化结果。在改进辫法 的计簿中，我们注意到，迭代值9 2 一般在一3 0 1 0 驰范围内停止，而标准 的数值迭代算法停止时，g 递增达到3 0 0 多。另外，改进簿法的优化结 果网秣准算法几乎完全鞠阉，但运行辩阈榴对较长，这是嚣为每次数谯迭 代时都需要计算尾f k 的值，相应地，算法停止时g “1 - g 。的值也非常 小。 表3 - 2改遥的檬维数值迭代在不同辑捆因子对豹挽纯结采 时间迭代步 口 姑( 1 )砖( 1 6 ) 砖( 3 1 )g 。一g 矿( 口) ( s )数+ 1 口= o3 7 1 7 5 6 3 23 7 1 7 5 6 3 23 7 1 7 5 6 3 22 0 0 51 4 12 2 e 一8 3 7 1 7 5 6 3 2 g = o 51 9 8 9 5 0 2 54 1 4 0 5 3 9 03 ，6 8 2 4 8 7 61 4 5 。48 02 。2 e - 53 6 1 2 2 4 5 8 l 盘= l1 4 8 7 0 0 6 34 + 3 0 9 6 0 2 93 8 7 1 1 4 2 39 4 65 7l 。5 e 一63 5 3 7 0 0 0 7 表3 - 3 礅示s 仍取1 0 4 且折扣因子口= 0 0 0 3 5 时，两种异步迭代算法的优 化结果，可以看到异步数饿迭代的优化效果接近于标准迭代的优化结果， 说明是步磐法也具有较高的优化糖度，故可以邂用多处理器或节点来实现 莠行数壤遮鼗，藏少运算辩凌，鞋勰捷大焱搂悉统匏魏纯润题。铁表孛可 敬酲显纛蹬异步算法魄标凇箨法的运行辩瀛袄，但优纯效暴穗麓不大；另 外，基于样本轨道仿真的异步数值迭代比g a u s s s e i d e l 异步迭代的整个运 行时间斑，但优化效果略麓。 表3 - 3 异步数值迭代的优化结果 薅阗逡袋步鼗 冀法 瞻( 1 )露f 1 6 )堙3 1 ) ( s ) k + l 标准v i 3 6 9 3 2 7 0 4 8 6 43 7 2 2 4 6 5 8 9 3 03 7 1 4 3 6 0 9 4 1 98 8 81 0 l g s 遮代 3 6 9 3 2 7 0 4 8 6 43 7 2 2 4 6 5 8 9 3 03 7 1 4 3 6 0 9 4 2 07 6 1 l3 4 7 1 2 3 基于样本轨造 豹巽步v l 3 。6 9 4 3 1 4 4 1 0 73 。7 2 3 5 2 4 8 2 4 l3 7 1 5 4 1 2 0 8 8 43 8 1 11 5 6 8 3 7 拳 誊 蠢 鏊 始 嚣 i t +t=： 釜：= = ：= = ：誊# = ：兰：= ：= ： 螂蹦：叠每 - 拶 宿鉴，j 一。，。j |婚 ： t 肆 、 一 ：。， 0o 氇i疆3a 40 s & 80r0 80g 折扣因子a 圈3 - 1 标准数值迭代在折扣因子连续变化时折扣代价话( i ) 的变化曲线 辑撩盈予a 图3 - 2 改进数值迭代在折扣因子连续变化时折扣代价结( f ) 的变化曲线 网3 - 1 和阁3 - 2 分别表示在搿连续变化时，标猴数值迭代算法和改进 的数德迭 弋算法在不网状态下的折扣代份瞻( f ) 静变化趣线，可见冬数值 都隧搿趋向零黼收敛予一点，即最侥平均代价值，这说明了平均代价弼以 看作憋折扣因子趋于零时的极限情况。 第四章s m d p 基于性髓势的异步策略迭代算法 本耄主要研究s m d p 慕于性能势的异步策略迭代。首先介绍t d 学习 和n d p 优化，然后主要介缨弊步策略迭代中的几静主要算法，半m a r k o v 凌篆过程( s m d p ) 基予淫筑势熬殛步囊懿( 1 0 0 k a h e a d ) 舅步滚疆迭饩 算法。该算法不仅对标准策略迭代算法帮一缎的异步策略迭代嚣法都适 用，而凰对s m d p 在折扣和平均准则下的优化也是统一的；另外，还给 出了两种性能准则下基于t d 学习的m 步向前异步策略迭代和撼于n d p 的m 步向前策略迭代。最聪遇过一个数值例予说明比较各种髯法韵优缺 点。 4 1t d 学习和n d p 优化 本节简单介绍t d 学习和神经元动态规划。s u t t o n 等指出t d 强化学 习方法的数学理论基础是动态规划。在文献 s 5 中，s u t t o n 给出了从动态 溪捌方法逐步遘渡垂t d 强豫学习方法瓣其傣j