（计算机软件与理论专业论文）基于markov决策过程的数据压缩研究.pdf

摘要 摘要 数据压缩是把输入数据流( 源流和原始数据) 转变为另一种较小数据流( 输 出流或者压缩流) 的过程。现有的大多数数据压缩算法是对某些特殊领域或者数 据冗余度比较大的文件进行处理，对于二进制文件或者数据冗余度不高的文件压 缩效果一般，甚至可能出现负压缩。 本文在d m c ( d y n a m i cm a r k o vc h a i n ) 算法和d e f l a t e 算法的基础上，提出 了一种新的压缩算法，目的是获得更高的数据压缩率。本算法由两个阶段组成， 首先使用l z 7 7 方法对整个输入流进行压缩，然后通过m a r k o v 决策过程和算术编 码，计算当前状态的转移概率获得最终的数据压缩编码。基本思想是在整体上使 用l z 7 7 方法，然后通过m a r k o v 决策过程对状态空间的控制，结合算术编码的方 法，计算当前状态的转移概率获得最终压缩编码。 本算法的核心处理过程是m a r k o v 决策过程对m a r k o v 状态集的控制、实时调 用寻优策略来获得最大报酬。根据每次数据处理长度的不同，决策过程的复杂度、 压缩效果也存在差异。 状态空间的结构多样化，给m a r k o v 决策过程提供了更广泛的应用空间，使压 缩效果得到提高，处理过程复杂度增加。为了平衡压缩率与算法处理复杂度之间 的关系，本算法选择了每次处理2b i t s 数据。这样m a r k o v 状态空间中每个状态 都可以输入o o 、0 1 、1 0 和1 1 四种符号，包含四个输出的转移概率，当前状念转 移到下一个状态的可选择的路径为四条。 算法的主体部分体现了m a k r o v 决策过程中的关键步骤。m a k r o v 决策过程包 括决策、寻优和获得最大报酬。在决策阶段，算法处理的是判定状态是否需要复 制以及复制方式的选择，重要的两个衡量指标分别是当前状态的转移概率( c o u n t 比率关系) 和当前状态内部入口与出口之间的映射关系( m a p p i n g ) 。在寻优阶段， 算法处理的是状态计数器的动态调整，动态调整的对象是决策过程中用于决策的 各个衡量指标。在取得最大报酬阶段，算法处理方法是调用自适应算术编码。 本文最后给出了测试结果数据及其分析，并对本文的研究工作出了总结。验 广东工业大学工学硕士学位论文 结果显示，对于芈j p g ，木m p 3 等数据冗余度比较小的文件算法比z i p 算法压缩效 果更加明显，获得了更高的数据压缩率。 关键词：数据压缩；m a r k o v 决策过程；状态空间；状态转移 n a b s t r a c t a bs t r a c t d a t a - c o m p r e s s i o n i sac h a n g i n g p r o c e s st h a tc h a n g ed a t a - s t r e a mf r o mi n p u t d a t a - s t r e a m ( s o u r c eo ri n i t i a ls t r e a m ) t oa n o t h e rk i n do fl e s sd a t a - s t r e a m ( e x p o r ts t r e a m o rc o m p r e s ss t r e a m ) ，t h es t r e a mi saf i l eo rab u f f e rm e m o r yi nt h em e m o r y a tp r e s e n t , m o s te x i s t i n gd a t a - c o m p r e s s i o na l g o r i t h m sa r eu s e dt od e a lw i t ht h ed a t ai ns p e c i a l f i e l do rt h ef i l eo fw i t c ht h er e d u n d a n td e g r e ei sb i g g e r t h e i rc o m p r e s s i o nr a t i o sa r e i n c o n s p i c u o u sw h e nt h ei n p u td a t a - s t r e a ma r et h eb i n a r yf i l e so rt h es m a l lr e d u n d a n t f i l e s i no r d e rt or a i s et h ed a t a c o m p r e s s i o nr a t i oo ft h es m a l lr e d u n d a n tf i l e s ，t h r o u g h s t u d y i n gt h ee x i s t i n gd a t a - c o m p r e s s i o na l g o r i t h m , ih a v ep r o p o s e dan e wk i n do f a l g o r i t h m , i tb a s e do nd m c ( d y n a m i cm a r k o vc h a i n ) a n dd e f l a t ea l g o r i t h m t h e a l g o r i t h mf a l l si n t ot w op a r t s a t 盘s t i ti st ou s el z 7 7a l g o r i t h m , t h e ni tg e tf i n a l c o m p r e s s i o nc o d eb ya r i t h m e t i ca l g o r i t h ma n dt h ec o n t r o lo ns t a t es p a c eo fm a r k o v d e c i s i o n p r o c e s s e s t l 硷f m a lc o m p r e s s i o nc o d e i s t h r o u g h c a l c u l a t i o nt h e t r a n s f o r m a t i o np r o b a b i l i t yo nt h ec u r r e n t l ys t a t e m a r k o vd e c i s i o np r o c e s s e sa r eu s e dt oc o n t r o lt h em a r k o vs t a t ea g g r e g a t ei nt h i s a l g o r i t h m , t h ep u r p o s ei s t oo b t a i nr e w a r da sm u c ha sp o s s i b l eb ys o m ek i n d so f o p t i m i z a t i o ns t r a t e g i e s a c c o r d i n gt ot h ed i f f e r e n tl e n g t ho fd a t a - c e l l ，m a r k o vd e c i s i o n p r o c e s s e sh a v ed i f f e r e n te f f e c t i ft h el e n g t h so fd a t a - c e l la r eb i g g e r ，t h ed e c i s i o n p r o c e s s e sa r em o r ec o m p l m a t e dt o o ，t h ec o m p r e s s i o n - r a t i oa r eh i g h e r w h a tic h o i c ei st od e a lw i t h2b i td a t ae a c ht i m ei nt h ep r o j e c t i nt h i sw a y ，e a c h s t a t ei n c l u d e sf o u rp i e c e so fo u t p u t t e dt r a n s f o r m a t i o np r o b a b i l i t yi nt h es t a t es p a c eo f m a r k o v ，s y m b o l st h a tc a l lb ei n p u ti nt h es t a t es p a c ea r e0 0 ，o1 ，10 ，1 1 ，t h es t a t ew i l l h a v ef o u rt r a n s f e r r i n go p t i o n a lr o u t eo ft h en e x ts t a t e t h es t r u c t u r ed i v e r s i f i c a t i o no f t h es t a t es p a c e s ，w i l lb r i n gb i g g e rp i e c e so fa p p l i c a t i o ns p a c e sf o rt h em a r k o vd e c i s i o n p r o c e s s e s , i m p r o v ec o m p r e s s i o nr a t i o ，a tt h es a m et i m ei tm a k et h ed e c i s i o np r o c e s s e s h i 广东工业大学- 丁学硕士学位论文 c h a n g e dc o m p l i c a t e d m a r k o vd e c i s i o np r o c e s s e si n c l u d e sd e c i d i n g 、s e e k i n go p t i m a ls t r a t e g i e sa n d o b t a i n i n gt h el a r g e s tr e w a r d s i nt h i sp r o j e c t ，t h em o s ti m p o r t a n td e c i s i o ni st oj u d g e w h e t h e rt h ec u r r e n ts t a t en e e d st oc l o n ea n dt oc h o i c et h ec l o n em e t h o d , t h e r ea r et w o p a r a m e t e r si nt h ed e c i s i o np r o c e s s e s ，o n ei st r a n s f o r m a t i o np r o b a b i l i t yo f t h ec u r r e n t s t a t e ( i nt h ep r o j e c t ，i ti sp a r a m e t e rc o u n t ) ，a n o t h e ri sm a p p i n gi nt h ei n n e ro f t h es t a t e ( i nt h ep r o j e c t ，i ti sp a r a m e t e rm a p p i n g ) ；o n ek i n do fs i m p l es e e k i n go p t i m a ls t r a t e g i e s i sd y n a m i ca d j u s ta l lk i n d so fc o u n t so ft h ec u r r e n ts t a t e ，w h a ti sd y n a m i ca d j u s t e da r e s o m ep a r a m e t e r st h a tb eu s e dt ob eak i n do fs t a n d a r da n dr a n kv a l u e st h a tb eu s e dt o r e c o r dt h es p a c ei na d a p t i v ea r i t h m e t i cc o d i n gp h a s e ；i no r d e rt oo b t a i nr e w a r da sm u c h a sp o s s i b l e ，t h i sp r o j e c tr e a l i z eb yc a l lt h ea d a p t i v ea r i t h m e t i ca l g o r i t h mp r o d u c ef i n a l c o m p r e s s i o n - c o d e i nt h el a s tp a r to ft h ep a p e r , id e s i g n e ds o m et e s t i n ge x a m p l ea n da n a l y z e dt h e t e s t i n gr e s u kf o rt h ep r o j e c t ，a n de d u c ec o n c l u s i o ni nt h es t u d y i n gp r o c e s s t h e c o m p r e s s i o nr a t i oo ft h en e wa l g o r i t h mh a v em o r ei m p r o v e dt h a nt h ez i pa l g o r i t h m w h e nt h es m a l lr e d u n d a n to b j e c t sw e r ec o m p r e s s e ds u c ha s 幸j p g 、m p 3 k e y w o r d s ：d a t ac o m p r e s s i o n ；m a r k o vd e c i s i o np r o c e s s e s ；s t a t es p a c e ；s t a t e t r a n s f e r i v 广东工业大学工学硕士学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 论文作者签字：印多乙多乙 指导教师签字： 6 2 二零零八年四月十八同 第一章绪论 第一章绪论 本章简要介绍了数据压缩的发展过程与现状，基于m a r k o v 决策过程的数据 压缩研究意义，以及开发工具的选择等。 1 1 数据压缩 现有的无损压缩本算法基本上都是在l z 算法的基础上发展起来的，不同的 领域l z 算法的侧重点不同，有l z 7 7 、l z 7 8 、l z w 、l z s s 、l z a 、l z h 等。l z 算法是在整体上对字符串数据进行压缩，在l z 方法处理结束后为了提高压缩率， 一般的算法都要在b y t e 或者b i t 单位上进行进一步的处理，现在流行的z i p 压缩 算法就是这样处理的，它是先用l z 7 7 处理，然后在用h u f f m a n 编码和动态自适 应h u f f m a n 编码处理。b y t e 或者b i t 单位上常用的处理方法有h u f f m a n 编码、算 术编码、前缀码、g o b m b 码、p p m 编码、n n p 编码等【1 圳。 数据压缩的目的就是要消除信息中的冗余。压缩以一种更紧凑的表达形式来 表示信息从而减少对它进行存储和传输的比特数，它最重要的三个作用： 1 对于需要存储的数据节约磁盘空间 2 对于需要通信的数据加快传输效率 3 对文件或者文件夹压缩存档 压缩技术根据其不同的压缩结果可以分成以下两类： 1 无损( l o s s l e s s ) 压缩：压缩过程没有数据丢失，所有原始数据可以精确重 现。 2 有损( l o s s y ) 压缩：在可以接受的前提下丢失一些细节，从而大大增加压 缩比。 严格意义上的数据压缩起源于人们对概率的认识。当人们对文字信息进行编 码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予 较长的编码，总的编码长度就能缩短不少。在计算机出现之前，著名的m o r s e 电 码就已经成功地实践了这准则。在m o r s e 码表中，每个字母都对应于一个唯 广东工业大学工学硕士学位论文 一的点划组合，出现概率最高的字母e 被编码为一个点“ ，而出现概率较 低的字母z 则被编码为“ 。显然，这可以有效缩短最终的电码长度。 1 1 1 数据压缩技术发展 数据压缩技术p 卅大致经历了三个发展阶段：1 9 4 8 年1 9 7 6 年算术编码基础 理论研究阶段，即第一阶段；1 9 7 7 年1 9 8 4 年为字典编码基础理论研究阶段， 即第二阶段；1 9 8 5 年至今为实用化阶段，即第三阶段。 1 s h a n n o n - f a n o 编码 1 9 4 8 年贝尔实验室的s h a n n o n 发表了am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n ( 通信的数学理论) 的论文，第一次用数学语言阐明了概率与信 息冗余度的关系。s h a n n o n 借鉴了热力学的概念，把信息中排除了冗余后的平均 信息量成为信息熵，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被 誉为信息论的开山之作，信息熵同时也奠定了所有数据压缩算法的理论基础，同 时他也给出了一种简单的编码方法一s h a n n o n 编码。1 9 5 2 年，麻省理工学院的 r m f a n o 又进一步提出了f a n o 编码。两者后来被称为s h a n n o n - f a n o 编码，这 种早期的编码方法揭示了变长的编码方法揭示了变长编码的基本规律。 2 h u f f m a n 编码 19 5 2 年，d a h u f f m a n 在其论文am e t h o df o rt h ec o n s t r u c t i o no f m i n i m u m r e d u n d a n c yc o d e s ( 最小冗余度代码的构造方法) 中提出了著名的h u f f m a n 编码。 h u f f m a n 编码是第一个真正实用的编码方法。它根据字符出现的概率来构造 平均长度最短的编码，是一种变长的编码。在编码中，若各码字长度严格按照码 字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。 h u f f m a n 编码效率高，运算速度快，实现方式灵活，从2 0 世纪6 0 年代直到 现在，在数据压缩领域得到了广泛的应用。 3 算术编码 1 9 6 8 年，ee l i a s 发展了s h a n n o n 和f a n o 的编码方法，构造出从数学角度 看来更为完美的s h a n n o n - f a n o e l i a s 编码；沿着这一编码方法的思路，1 9 7 6 年， j r i s s a n e n 提出了一种可以成功地逼近信息熵极限的编码方法一算术编码； 当符号概率等于2 的负整数次幂时，h u f f m a n 编码和s h a n n o n 编码才能产生 2 第一章绪论 最佳结果( 编码的平均长度等与熵) 。算术编码克服了这个问题，它通常是把一 个码字( 通常较长) 分配给整个输入流，而不是给各个符号分别分配码字。它逐 个符号读入输入流，每输入和处理一个符号，就在码字后面加几位。可以理解为 生成的码字是 o ，1 ) 之间的一个数。 4 l z 编码 l z 是其发明者j a c o bz i v 和a b r a h a ml e m p e l 两个犹太人姓氏的缩写。此二 人于1 9 7 7 年发表题为 au n i v e r s a la l o g r i t h e mf o rs e q u e n t i md a t ac o m p r e s s i o n ( 顺 序数据压缩的一个通用算法) 的论文，论文中描述的算法被后人称为l z 7 7 算法。 1 9 7 8 年，二人又发表了该论文的续篇( ( c o m p r e s s i o no fi n d i v i d u a ls e q u e n c e sv i a v a r i a b l e r a t ec o d i n g ( 通过可变比率编码的独立序列的压缩) ，描述了后来被命名 为l z 7 8 的压缩算法【5 1 。 19 8 4 年，t e r r yw e l c h 发表了名为at e c h n i q u ef o rh i g h - p e r f o r m a n c ed a t a c o m p r e s s i o n ( 高性能数据压缩技术) 的论文，描述了他在s p e r r yr e s e a r c hc e n t e r ( 现在是u n i s y s 的一部分) 的研究成果。他实现了l z 7 8 算法的一个变种 l z w 。l z w 继承了l z 7 7 和l z 7 8 压缩效果好、速度快的优点，而且在算法 描述上更容易被人们接受( 有的研究者认为是出于w e l c h 的论文_ 比z i v 和 l e m p e l 的更容易理解) ，实现也比较简单；曾经风靡一时的g i f 图像格式使用 的就是l z w 算法。今天，l z 7 7 、l z 7 8 、l z w 算法以及它们的各种变体 几乎垄断了整个通用数据压缩领域，人们熟悉的a r j ，p k z i p ，w i n z i p ，l h a r c ， r a r ，g z i p ，a c e ，z o o ，t u r b o z i p ，c o m p r e s s ，j a r 等压缩工具以及z i p 、 g i f 、p n g 等文件格式，许多硬件如网络设备中内置的压缩算法等，都是l z 系列算法的受益者，甚至连p g p 这样的加密文件格式也选择了l z 系列算法作 为其数据压缩的标准【6 】o 5 阴t 编码 19 9 4 年，m b u r r o w s 和d j w h e e l e r 在论文a b l o c k s o r t i n gl o s s l e s sd a t a c o m p r e s s i o n a l g o r i t h m ) ) 中提出了一种全新的通用数据压缩算法。这种算法的核 心思想是对字符串轮转后得到的字符矩阵进行排序和变换，类似的变换算法被称 为b u r r o w s w h e e l e rt r a n s f o r m a t i o n ，简称b w t ；该算法与以往所有通用压缩算 法的设计思路都迥然不同。现有比较著名的压缩算法都是处理数据流模型的，一 次读取一个或多个字节，b w t 使得处理成块的数据成为可能。这种算法的核心 广东_ t 业大学：f ：学硕士学位论文 思想是对字符串轮转后得到的字符矩阵进行排序和变换。考虑一般的文本应用比 如英语文本中t h e 这个字符串经常会被用到，经过b w 转换之后，所有的t 都被 移动到最后并且聚合在起，这样变换之后的字符串用通用的统计压缩模型 ( h u f f m a nc o d i n g 、l z 算法、p p m 算法) 等进行压缩就能得到更好的压缩比。 1 2 数据压缩技术分类 数据压缩算法按有损或无损进行的简单分类如下图1 1 所示。 压缩技术 广上1 通用无损数据压缩多媒体数据压缩( 大多为有损压缩) 广l _ 弋广j 弋 基于统计模型 基于字典模型的音频压缩 图像压缩视频压缩 的压缩技术 压缩技专 l l l i i m p 3 等一一1 a v i 11 二岳灰度彩色矢釜m p e g 2 等 窘s h n n 。n 。n 编- h 编u 码f f m a n 磊窖l z 7 7 l z 7 8 l z w 图像 图像图像_ 图像 ” i li -i 1- 。l ， - 蓑纛；饕罨第1 阱f 娶p o n s d t 。s w c r s l 删p t f 信息熵u n i x 下接近秀p k z i p 、l h a r c , 灌“ 簿 等 理论指的 损压缩 a r j 、u n i x 下 导。卜简 c o m p a c t 极限的 的 c o m p r e s s 单编码 程序等 高级应 程序等 方式 用 图1 - 1 数据压缩分类 f i g u r el 1d a t a - c o m p r e s s i o nc a t e g o r y 其中常用到的w i n z i p 、w i n r a r 都是属于通用无损数据压缩，他们的压缩 率与有损压缩比较要小的多。但是他们完整了保存了原有文件的数据信息，可以 完全对原来有的数据进行还原，有损压缩只是保存了数据的重要信息，对于一些 细节方面的数据就忽略掉了。比如视频数据人眼睛能够分辨的最高刷新率是2 5 祯秒，对于人的感官系统，1 0 0 祯秒和8 0 祯秒的效果是一样的，但是两中不同 频率下的数据量却有很大差别。 4 第一章绪论 1 2 随机过程 随机过程口咱1 是随机变量概念的推广，通常人们把取值具有不确定性的变量 称为随机变量。随机过程的定义中引入了空间的概念，即在空间中每个位置上它 都呈现为一个随机变量，如果空间取为时间域，那么它在每个时刻都呈现为一个 随机变量。 随机过程毛( t ) 具有以下特点： 1 ) 亏( t ) 在t = t o 时刻的单个样本值砸o ) 是一随机变量。 2 ) 毛( u 的数学期望s ( t o ) = e ( 芎m ) ) 是确定的，其中e ( ) 表示统计平均运算。 3 ) s ( t ) = e ( 熟) ) 是关于t 的函数，此时呈现了函数的特性，因此芎( t ) 可以看 作是一个随机函数。 随机过程具有二重性：( 1 ) 随机性：对任何耽搁样本值致t o ) 而言，它是一 随机变量。( 2 ) 函数特性：在整个时域空间上，亏( t ) 是一随机函数。 依据随机过程的单样本值为随机变量的特性，相应的研究内容包括连续型 随机过程和离散型随机过程，具体的研究对象包括：均值、方差、协方差、有限 维联合分布等；依据随机过程的函数特性，相应的研究内容应包括：时间上的相 关性、连续性与离散性、随机过程的导数、微分、积分、卷积、级数展开、微分 方程与积分方程等；依据随机过程的二重性的联合特征，相应的研究内容包括： 互相关函数、空间的遍历性、时域平均与集总平均的关系、随机抽样定理、滤波 理论、估计与预测方法等。 随机过程的数学定义是：设( q ，f ，p ) 是一个概率空间，其中q 是一个集合， f 是由q 的某些子集所组成的一个a 代数，p 是在可测空间( q ，f ) 上定义的一个 概率测度，t 是一个指标集，若对每一个t t ，亏( t ，) 是一个随机变量，则称号 ( t ，妨= 每( 呦为该概率空间上的随机过程，为方便其间，通常记为芎( t ) 。 随机过程是一簇与参数集合t 有关的随机变量 x tit t ) ，其中x 。定义在 同一个概率空间，取值于同一个集合s ，参数集合t 通常被看作是时间集合，s 称为状态空间。对于一个固定的t ，随机变量x t 代表了t 时刻状态空间s 上的一 个随机分布。随机过程的参数时间集合t 和状态空间都可以是离散或连续的，若 t 为离散的时间集合，称这样的随机过程为离散时间随机过程，若t 为连续施加 广东工业大学工学硕士学位论文 的集合，则称为连续施加随机过程。 一个随机过程的例子是某个地方，在一段时间内的温度x 的变化情况，这 个随机过程的状态空间s 是一个合理的温度变化范围。而每个随机变量x 。都给 出t 时刻该地任意可能的温度概率。如果考虑每天的平均温度的变化，则时问集 合t 就是离散的，由此就得到一个离散时间随机过程，其中) ( o 表示第一天的平 均温度的概率分布。x l 表示第二天的平均温度的概率分布，依此类推，类似的， 通过选择连续的时间参数集合，就能描述随机时间连续变化的随机过程。 1 2 1m a r k o v 随机过程 一个随机过程在随机时间变化的过程当中，其下一个变化时刻的取值可能 与当前时刻的取值和当前时刻以前的取值情况有关【9 1 。若一个随机过程的下一个 变化时刻的取值只与当前时刻的取值有关而与过去时刻的取值无关，就称这样的 随机过程具有马尔可夫性n 0 。( m a r k o vp r o p e r t y ) ，或无记忆性( m e m o r y l e s s ) ，用 数学的语言描述，马尔可夫性就是对任意的时间序列t n + l t 户t n 1 t o ，都有 下式成立 p x t , 一as x n + lix t n = x n ，x t n l = x n - i ，x t o = x o ) = p x t n + lsx n + lix t n = x n ) 一 ( 1 1 ) 对于离散时问随机过程来说，马尔可夫性可以表示的更加简洁，即对任意 的t n ，有 p x c + 1sx t + l jx t = x n ，x t 1 = x t - i ，x o = x o = p x 0 ls x t + l ix t = x t ( 1 2 ) 马尔可夫性反映了随机过程将来的行为与它过去的行为无关，仅仅与当前 所处的状态有关，但是马尔可夫性并不意味着随机过程将来的行为与当前时刻t 无关，如果x t 的取值与t 无关，这样的随机过程称为非齐次的( i n h o m o g e n e o u s ) ， 反之，如果x 的取值与t 无关，则称之为齐次的( h o m o g e n e o u s ) ，更精确地，齐 次性要求任意tj 三t ，下式成立f 1 2 】 p xtsxix t = x ) 2p x t - tsxix o = x )( 1 3 ) 满足齐次性的随机过程，其变化过程只与变化的时间间隔有关而与变化的 起始时间点无关，这使得人们可以任意选择时间的原点而不会影响观察的结果。 6 第一章绪论 满足马尔可夫性质的随机过程称为马尔可夫过程。如果马尔可夫过程的状 态空间是离散的，则称为马尔可夫链。 1 2 2m 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 ) 是序贯决策 的主要研究领域。它是马尔可夫过程与确定性的动态规划相结合的产物，故又称 马尔可夫型随机动态规划，属于运筹学中数学规划的一个分支1 1 0 1 。 序贯决策是用于随机性或不确定性动态系统最优化的决策方法。序贯决策 的特点是：l 、所研究的系统是动态的，即系统所处的状态与时间有关，可周期 ( 或连续) 地对它观察；2 、决策是序贯地进行的，即每个时刻根据所观察到的 状态和以前状态的记录，从一组可行方案中选用一个最优方案( 即作最优决策) ， 使取决于状态的某个目标函数取最优值( 极大或极小值) ；3 、系统下一步( 或未 来) 可能出现的状态是随机的或不确定的。序贯决策的过程是：从初始状态开始， 每个时刻作出最优决策后，接着观察下一步实际出现的状态，即收集新的信息， 然后再作出新的最优决策，反复进行直至最后。系统在每次作出决策后下一步可 能出现的状态是不能确切预知的，存在两种情况：l 、系统下一步可能出现的状 态的概率分布是已知的，可用客观概率的条件分布来描述。对于这类系统的序贯 决策研究得较完满的是状态转移律具有无后效性的系统，相应的序贯决策称为马 尔可夫决策过程，它是将马尔可夫过程理论与决定性动态规划相结合的产物。2 、 系统下一步可能出现的状态的概率分布不知道，只能用主观概率的条件分布来描 述。用于这类系统的序贯决策属于决策分析的内容1 1 3 - l5 1 。 马尔可夫决策过程就是指决策者周期地或连续地观察具有马尔可夫性的随 机动态系统，序贯地作出决策。即根据每个时刻观察到的状态，从可用的行动集 合中选用一个行动作出决策，系统下一步( 未来) 的状态是随机的，并且其状态 转移概率具有马尔可夫性。决策者根据新观察到的状态，再作新的决策，依此反 复地进行。马尔可夫性是指一个随机过程未来发展的概率规律与观察之前的历史 无关的性质。马尔可夫性又可简单叙述为状态转移概率的无后效性。状态转移概 率具有马尔可夫性的随机过程即为马尔可夫过程。马尔可夫决策过程又可看作随 机对策的特殊情形，在这种随机对策中对策的一方是无意志的。马尔可夫决策过 7 广东丁业大学工学硕士学位论文 程还可作为马尔可夫型随机最优控制，其决策变量就是控制变量。 1 m a r k o v 决策过程的发展 m a r k o v 决策过程的起源可以追溯到上世纪5 0 年代。r b e l l m a n 研究动态规 划时和l s s h a p l e y ( 1 9 5 3 ) 研究随机对策时已出现马尔可夫决策过程的基本思想。 1 9 5 3 年s h a p l e y 在一次讨论班上做的关于随机对策的报告中所讨论的问题其实就 可以看成是一种特殊的m a r k o v 决策模型，后来b e l l m a n 最早讨论了一般的序列 决策的问题。r a h o w a r d ( 1 9 6 0 ) 和d b l a c k w e l l ( 1 9 6 2 ) 等人的研究工作奠定了马 尔可夫决策过程的理论基础。h o w a r d 首先使用了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 i n 关于非时齐( 非时间平稳性) 的研究， 推动了这一理论的发展。1 9 6 0 年以来，马尔可夫决策过程理论得到迅速发展， 应用领域不断扩大。凡是以马尔可夫过程作为数学模型的问题，只要能引入决策 和效用结构，均可应用这种理论。 在m d p 发展的前3 0 年，即到1 9 8 0 年左右，主要的研究集中在最优方程及 其求解算法，也就是策略和值迭代的方法。值迭代还包括它的一些相关变化，例 如连续逼近，向后递归及动态规划等。基本上，那些原则仅使用于单一目标函数 的情况。例如，适用于有限阶段期望总报酬模型的动态规划算法，通常可以应用 于无限阶段模型，即期望总报酬折扣模型和平均模型。但是对于其他准则的优化 问题就不能直接应用动态规划的方法了，例如带约束条件的单目标准则模型。对 于这些具体问题，使用凸分析方法是比较自然的，这包括有限和无限维空问上的 线性规划和凸规划方法。近2 0 年来，大部分的研究集中在动态规划原则不直接 使用的困难问题上，特别是多准则问题等方面。 2 决策过程数学描述 周期地进行观察的m a r k o v 决策过程可用如下五元组来描述： t ，s ，a ( i ) ，p ( ii ，a ) ，“i ，a ) ( 1 4 ) 其中：t = o ，l ，2 ，n 1 ，0 n v n + ( i ) 对所有状态i s 成立，则称为n 阶段最优策略，简称为e 最优策略， 当= 0 时简称为最优策略。 人们总认为决策者希望在系统的每个可能的初始状态上都能选取最好的决 定，寻求向量最优。在实际问题中，可能只需要知道一些或者个特定的初始状 态是如何选优的就足够了。也就是说只需要极大化k g 万弦 艺= f ) ，即对 j e s u y o = i ) o 的那些i 极大化相应的v n ( i ，) ，其中u y o = i ) 为初试状态的概率 分布。 3 2 有限阶段的策略迭代和最优方程 有限阶段模型的理论的理论和计算方法是基于动态规划的期望报酬值后递 广东t 业大学工学硕士学位论文 归的过程2 睨7 1 。 令= ( o ，瓢l ，n 1 ) 为一个一般的策略。记函数 矿= 县_ r 为用策略从时刻t 到时刻n 的的期望报酬总和，其中h 。表示到t 时刻为止的历史集合，它是实数集合的一个子集。如果决策时刻t 的历史为h t = ( i o ，a o ，de h t 2 9 - 3 0 。 r r 11 衫( 忽) 兰e b 何) + 玳( 瓦) i 曩，z = ( t o 并假设彳( ts 是方程( 3 6 ) 的解，而且满足边界条件( 3 7 ) 如 果策略万。= ( 菇，砰，。) 确定性策略满足 ( ，口) + 善见( 小，口) “融，西( 忽) ，j f ) + 嘉 绦卜小萎p r ( j m 咖触 那么有 ( 1 ) 对一切t = 0 ，i ，n - 1 ， ( 曩) + ( 一f ) 号西( 啊) ， ( 2 ) 耳是最优策略，而且 ( i ，1 8 ) ( f ) ( 3 1 2 ) l l i h t( 3 1 3 ) i s ( 3 1 4 ) 广东工业大学工学硕十学位论文 定理1 和定理2 中的最优策略和最优策略是属于确定性策略类的，但是确 定性策略是与历史相关的策略，很不方便使用。下面的定理3 说明了如果最优方 程有解，则存在m a r k o v 策略是最优策略或者是e 最优策略是最优的。 定理3 假设假设茚( tsn ) 是方程( 3 6 ) 的解，而且满足边界条件( 3 7 ) 。那么： ( 1 ) 对t = 0 ，1 ，n ，彳( 忍) 对历史曩县的依赖只是与h t 的最后一个元 素i t es 有关系。 ( 2 ) 令 0 ，存在最优策略就是m a r k o v 策略。 ( 3 ) 对t = 0 ，1 ，n 和所有的i t s ，存在a a ( i t ) 满足式( 3 1 1 ) ，那么存 在最优策略而且它还是m a r k o v 策略。 由定理3 ，可以得出 戍( f ) =s u p( f j r ) =s u p( f 万) ，i s ( 3 1 5 ) 石e 最一般策略集合石确定性胁咖v 策略类 由定理3 可以比较容易的判断最优m a r k o v 策略的存在性，例如，当对一切 i s ，a ( i ) 是有限集合时：或者对一切t = 0 ，l ，n 和i s ，a ( i ) 是紧致的， ，；( 厶口) 关于a 上半连续且对各个参数一致有界，以及p t ( ji 厶a ) 关于a 下半连续 等。 最优策略具有如下性质，无论从哪一个初始状态出发和采取了哪个初始行 动，对下一个决策时刻来说剩余的决策规则组成的策略是最优策略，这就是最优 理论，最早出现在b e l l m a n 的书里。 3 4 单调策略的最优性 为了简化最优策略 1 0 , 3 5 1 的结构，给出进一步的条件限定保证存在确定性的单 调最优m a r k o v 决策，这不仅能够满足决策者的要求，而且具有易操作性和易计 算性。 令g ( x ，y ) 为实数集上的二言函数，如果对任意的x i x 2 和y l y 2 ，满足 g ( ，咒) + g ，y 2 ) g ( 屯，咒) + g ( x 2 ，咒)( 3 1 6 ) 就称g ( x ，y ) 为上可加的或者上模的，如果上式中不等号反过来，则称g ( x ，” 为下可加的或者下模的。 设状态空间s 是非负整数：对一切i s ，行动集合都是一样的，即 第三章m a r k o v 决策过程的应用 a ( i ) 三彳c 全体实数。 q , ( k l i , = p , ( j l i , 力 ( 3 1 7 ) j = k 对一切t = 0 ，1 ，