（控制理论与控制工程专业论文）迭代动态规划算法及并行化研究.pdf

摘要 动态规划是一种求解多级决策问题的基本工具，在社会经济、工程技术和最优控制等 领域有广泛的应用。但常规的动态规划实施存在一系列的困难，l u u s 提出了动态规划的 迭代实施算法，即迭代动态规划。迭代动态规划可以提高常规动态规划算法计算效率并 且容易实现。由于动态系统的强非线性和优化问题规模的增大，使得求解过程需要耗费 大量的计算时间，而且迭代动态规划算法本身计算量较大，因此研究迭代动态规划的并 行实现是必要且具有现实意义的。 本文主要研究内容概扩如下： 首先研究了迭代动态规划算法在最优控制上的正确性和效率。应用迭代动态规划求 解l q r 最优控制问题，并与解析解比较，获得了基本一致的最优控制曲线和最优状态 曲线。三个有控制约束或状态约束的文献化工最优控制实例的求解结果表明迭代动态规 划对非线性工业过程是有效的。本文还研究了算法参数的选取及算法效率的影响。 其次建立了并验证了一个并行计算平台。基于实验室p c 节点及1 0 0 m 局域网环境， 并以一台服务器为主节点建立了硬件机群环境。以w i n d o w s 系统为基础，结合m p i c h 消息传递并行编程平台，实现了简单的机群单一系统映象。通过矩阵相乘的例子说明了 通信及计算规模等对并行编程效率的影响并检验了机群的有效性。 再次实现了基于搭建的并行计算平台的迭代动态规划粗粒度主从式并行算法，并求 解了三个文献化工集总最优控制实例，以加速比和并行效率作为度量，验证了算法的有 效性。 最后将一类分布参数最优控制问题利用有限差分离散成动态规划模型，给出了迭代 动态规划求解该类问题的步骤。以一维热传导最优控制和一维聚合物驱最优控制策略问 题为例，分别运用串并行迭代动态规划算法进行了求解。结果验证了算法的正确性。 关键词：最优控制，迭代动态规划，p c 机群，并行计算 r e s e a r c ho ni t e r a t i v ed y n a m i cp r o g r a m m i n ga l g o r i t h ma n d p a r a l l e i i z a t i o n z h a n g y u b i n ( c o n t r o lt h e o r ya n d c o n t r o le n g i n e e r i n g ) d i r e c t e db yp r o f e s s o rl is h u r o n g a b s t r a c t d y n a m i cp r o g r a m m i n gi saf u n d a m e n t a lt o o l t os o l v em u l t i - s t a g ed e c i s i o n m a k i n g p r o b l e m sa n dh a se x t e n s i v ea p p l i c a t i o ni ns o c i e t ye c o n o m y , e n g i n e e rt e c h n i q u e ，o p t i m a l c o n t r o le t c h o w e v e r , t h e r ea r ean u m b e ro fd i f f i c u l t i e sa s s o c i a t e dw i t ht h eu s eo fd y n a m i c p r o g r a m m i n gi ni t so r i g i n a lf o r m l u u si n t r o d u c e dt h ei t e r a t i v ed y n a m i cp r o g r a m m i n g ( i d p ) w h i c hc a ni m p r o v et h ee f f i c i e n c yo fc o n v e n t i o n a lm e t h o do fd y n a m i cp r o g r a m m i n ga n di s e a s yt oi m p l e m e n t d u et oh i 曲n o n l i n e a r i t yi nt h ed y n a m i cp r o c e s ss y s t e ma n dl a r g es c a l eo f c o n t r o lp r o b l e m ，t og e tt h es o l u t i o nr e q u i r e sc o n s i d e r a b l ec o m p u t a t i o n a le f f o r t ，a n di d p a l g o r i t h mi t s e l fi st i m e c o n s u m i n g ，s o i t sn e c e s s a r yt o p r e c e d et h o r o u g hr e s e a r c ht o p a r a l l e l i z a t i o no ft h ei t e r a t i v ed y n a m i cp r o g r a m m i n g t h em a i nw o r k so ft h i st h e s i sa r ea s f o l l o w s ： f i r s t l y , w es t u d yt h ev a l i d i t ya n de f f i c i e n c yo fi t e r a t i v ed y n a m i cp r o g r a m m i n ga l g o r i t h m l q rp r o b l e ma n ds e v e r a ll i t e r a t u r ec h e m i c a lo p t i m a lc o n t r o lp r o b l e m s ( o c p s ) a r es o l v e d u s i n gi d pa l g o r i t h m c o m p a r i s o no fa n a l y t i c a ls o l u t i o no fl q rp r o b l e mt ot h es o l u t i o nu s i n g i d pi sm a d e a n o t h e rt h r e ec h e m i c a lo c p sw i t hc o n t r o lo rs t a t ec o n s t r a i n e ds y s t e ma r e s o l v e db yi d et h es i m u l a t i o ns t u d ys h o w st h a tt h ei d pi se f f e c t i v ea n da p p l i c a b l et om a n y n o n l i n e a ri n d u s t r i a ls y s t e m s t h ea l g o r i t h mp a r a m e t e r ss e l e c t i o nm e t h o d sw h i c hc a ni m p r o v e t h ee f f i c i e n c ya r ea l s os t u d i e d s e c o n d l y , ap a r a l l e lc o m p u t i n gp l a t f o r mw h i c hc o n s i s t sh a r d w a r ea n ds o f t w a r ei sb u i l t a n dv e r i f i e d l a bc l u s t e ri sb u i kb a s e do nt h e1 a bp c sa n d10 0 ml o c a ln e ta n das e r v e r m a c h i n ei su s e da st h em a s t e rn o d e c l u s t e rs i n g l es y s t e mi m a g e ( s s i ) i si m p l e m e n t e db a s e d o nw i n d o w so sa n dm p i c hm e s s a g e - p a s s i n gp r o g r a m m i n gl i b r a r y t h ee x a m p l eo fm a t r i x m u l t i p l yu s i n gc a n n o na l g o r i t h ms h o w st h ee f f i c i e n c yo fl a bc l u s t e r a l s o ，t h ee f f e c to fs c a l e o fc o m m u n i c a t i o na n dc o m p u t a t i o no nt h ep r o g r a m m i n ge f f i c i e n c yi sa n a l y z e d t h i r d l y , ap a r a l l e ls t r a t e g yo fi d pa l g o r i t h mi si m p l e m e n t e db a s e do nt h ep a r a l l e l c o m p u t i n gp l a t f o r m t h ep a r a l l e l i d pa l g o r i t h mi s a p p l i e dt ot h r e ec h e m i c a ll u m p e d o c p s t h er e s u l t ss h o wt h a tt h ep a r a l l e ls o l u t i o ni sc o n s i s t e n tw i t hs e q u e n t i a la l g o r i t h ma n d c o m p u t i n gt i m ei ss h o r t e nc o n s i d e r a b l y f i n a l l y , ac l a s so fd i s t r i b u t e dp a r a m e t e ro c pi sd i s c r e t i z e dt od y n a m i cp r o g r a m m i n g m o d e lu s i n gf i n i t ed i f f e r e n c ea n ds o l v i n gs t e p su s i n gi d pa r eg i v e n o p t i m i z a t i o np r o b l e mf o r l i n e a rh e a tc o n d u c t i o na n di n j e c t i o np o l i c e so p t i m i z a t i o np r o b l e mf o rp o l y m e rf l o o d i n ga r e s o l v e db ys e q u e n t i a la n dp a r a l l e li d pa l g o r i t h m s t h er e s u l t ss h o wt h ev a l i d i t y k e yw o r d s ：o p t i m a lc o n t r o l ，i t e r a t i v ed y n a m i cp r o g r a m m i n g ，p cc l u s t e r ，p a r a l l e l c o m p u t i n g 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均己在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 弛五拭 日期：劢7 湃月d - 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签 指导教师签名： 日期：z 册西年么月夕日 日期：枷侈年乡月厂日 中国石油人学( 华东) 硕士学位论文 1 1 研究意义 第一章前言 最优控制【l j ，又称为动态或过程最优化，是现代控制理论的一个最重要、最基本的 组成部分。它所研究的中心问题是：根据受控系统的动态特性，在满足一定约束条件下， 寻求最优控制规律( 控制策略) ，使其在规定的性能指标( 目标函数) 下具有最优值。最优 控制技术应用日益广泛，在运筹学、系统工程、经济管理等学科和实际的工程设计和控 制中都取得了卓有成效的成果。 工业过程是状态变量随时间的演进、空间的转移而发生改变的动态过程。工业过程 的动态模型通常公式化为代数一微分方程形式，其中微分方程描述系统的动态特性，如 质量和能量的守恒关系，而代数方程用来确保物理和热力学平衡关系。状态变量随时间 变化、或随空间( 一维) 变化的动态系统，这类系统用常微分方程描述，称为集中参数系 统。更为一般的情况是，状态变量随时间空间和其它参数变化的过程，需用偏微分方程 来表达，这类系统称为分布参数系统【2 3 1 。常微分方程较多地引入了一些特殊的假设， 因此集中参数系统的动态优化结果，与实际最优解相比，总存在一定的偏差。而偏微分 方程更深入更确切地描述了过程，因而分布参数系统的动态优化结果更加贴近实际。 在工业过程中，动态过程优化即最优控制问题相当普遍，如流程工业中化工反应过 程、优化设计、动态过程系统参数估计、生产过程工作点切换等命题，以及油气田开发 最优决策及三次注采过程中一定性能指标下的最优注入策略问题【4 10 1 。随着工业生产过 程的规模大型化，结构集成化，过程系统的控制结构形式越来越复杂，对控制系统和性 能要求也越来越高。如何优化生产条件与操作参数，提高产品的质量和数量，获得巨大 的经济和社会效益，成为目前工业过程优化控制中一个主要问题。 最优控制问题的核心之一就是求解方法的研究。求解最优控制问题的解析方法有两 种，一类是基于庞特里亚金极大值原理的方法，另一类是基于贝尔曼最优性原理的动态 规划方法1 1 1 1 。但稍微复杂的最优控制问题，一般不能得到解析解，需采用数值方法以分 段阶段函数逼近最优控制轨线。基于梯度信息的数值方法收敛速度快，但复杂的系统得 到梯度信息困难，且易陷入局部极小，适用范围较窄。而数值的动态规划方法及近年来 发展起来的仿生类算法不需要梯度信息，并能够求得系统全局最优解，应用日益广泛。 r e i nl u u s 在1 9 9 0 年前后提出了迭代动态规划算法，用迭代来补偿离散化所带来的 第一章前言 系统误差，用比较稀疏的控制变量离散数目，保证每次迭代时的计算量不会激增，然后 通过若干次迭代去寻找最优控制策略以逼近全局最优解。迭代动态规划不需要求解 h a m i l t o n j a e o b i b e l l m a n 方程，便于计算机实现，对控制变量的初值选取依赖性不大， 在一些非线性复杂化工过程中得到了应用1 2 d5 1 。但迭代动态规划方法计算量大，收敛速 度较慢，如何改进算法实施中参数的选取策略，提高算法的收敛速度，对该算法在工业 过程优化中的应用有一定的意义。 目前迭代动态规划应用一般应用在常微分方程描述的过程优化中，在偏微分方程描 述的分布参数动态过程优化中应用极少，而石油、化工工业中分布参数系统的优化命题 很多，如提高原油采收率的聚合物驱油过程本质上是一个分布参数的动态过程，聚合物 驱开发方案的科学设计应当采用动态的优化方法。由于迭代动态规划在全局优化和实现 简单的优势，研究迭代动态规划在聚合物驱油最优控制问题上的应用，既对油田开发有 一定的实际意义，对研究迭代动态规划在分布参数最优控制中的应用也有理论意义。 工业过程系统通常采用基于过程机理和严格物性计算的精确数学模型，这类模型往 往具有大规模、非线性的特点。一个典型的化工过程系统优化全联立方程包括了所有的 单元模型方程、物性计算方程、流程联接方程，维数巨大。随着石油工业的技术进步， 越来越多的地质模型和地质统计方法提供了石油开采区域上分布的数百乃至上千万网 格点的数据，使得石油工业油藏模拟成为典型的计算密集型问题；石油开采中的动态过 程也由分布参数系统描述，最优控制策略的求解需要耗费大量的时间，需要高性能的计 算机和高效率的优化算法进行求解计算【1 6 】。大规模优化中海量的数值计算及数据处理需 求迫切需要不断提高计算机的性能及计算能力，依靠并行处理技术提高计算机的运算速 度，则是近年来令人瞩目的一个发展方向。随着并行计算软硬件的发展，将大大推动科 学计算的发展，因为： 1 ) 它可以加快速度，即在更短的时间内解决相同的问题或在相同的时间内解决更多的问 题。 2 ) 节省投入，并行计算可以以较低的投入完成串行计算的任务。 3 ) 物理极限的约束，光速是不可逾越的速度极限，设备和材料也不可能做得无限小，c p u 的速度不可能无限度的提高。只有通过并行才能够不断提高速度。 依靠实验室p c 机搭建机群系统和免费的并行编程环境构建并行计算平台，使研究 优化算法的并行化成为可能。由于迭代动态规划算法天然的并行性，研究其并行化以提 高计算效率是对工业过程系统优化有一定的意义。由于聚合物驱最优控制问题是一组大 2 中国石油大学( 华东) 硕士学位论文 规模偏微分约束下的动态系统优化问题，因次在运用最优控制方法研究其最佳注采策略 时，研究并行的实现算法就显得格外重要。 1 2 研究现状 控制策略的优化在工业过程中有着越来越重要的作用，其中心任务就是研究求解动 态优化的算法。本节综述了目前国内外最优控制算法包括迭代动态规划的研究现状，并 介绍了并行计算技术及在优化算法并行化的发展。 1 2 1 最优控制问题求解方法 最优控制问题按照终端时间给定与否，终端状态有无约束可分为多种类型，本文以 最简单的终端时间给定、终端状态无约束的最优控制问题为例介绍其解法。该问题用式 ( 1 1 ) 作一般性的数学描述： 对连续系统： 讹妒嗍) ，毗，u ( o ，啦 ( 1 1 ) s i 5 c = f ( x ( t ) ，甜，力，x ( t o ) = ：c o 控制约束为：u ( t ) u ，t t 0f ，】，其中，x 是，2 维状态变量，纠是系统的m 维控 制变量。 该最优控制问题即为在到0 时间段内，求得容许控制“( f ) u ，t t 0t 】，使得 系统由给定初态出发，在f ， t o 时刻转移到目标，并使性能，最优。 对离散系统： ，i x ( o ) ，】2 沙( x ( ) ，) + k = o ( x ( 后) ，甜( 尼) ，七)( 1 2 ) s t x ( k + 1 ) = 厂( x ( 尼) ，“( 七) ，后) x ( 0 ) = x o 该最优控制问题即为在气到0 时间段内，求得容许控制序列u ( k ) u ，t 【t 0t f 】， 使得系统由给定初态出发，在f ， t o 时刻转移到目标，并使性能j 最优。 求解上述最优控制问题的解析解法一般有基于变分法的极大值原理和基于最优性 原理的动态规划方法。极大值原理是苏联数学家庞特里亚金受力学哈密顿原理启发，总 结了经典变分法研究成果，1 9 5 6 年至1 9 5 8 年创立的。它是解决最优控制问题的一种普 遍的有效方法，由于它放宽了求解问题的前提条件，使得许多古典变分法无法解决的工 程技术问题得到了解决。 第一章前言 动态规划是贝尔曼2 0 世纪5 0 年代中期为解决多阶段决策问题提出来的1 1 7 j 。它对研 究最优控制理论的重要性在于：动态规划的连续形式可以给出它与古典变分法得联系， 在一定条件下也可以给出与庞特里亚金极大值原理的联系，使得这两种解决最优控制问 题得基础方法在一定条件下得以沟通。 对于复杂的实际的最优控制问题，一般不能得到解析解，需要采用数值方法以分段 函数逼近最优控制曲线。最优控制问题的求解方法通常可分为两类：间接法、直接法 1 8 - 1 9 1 。间接法是先用经典的变分法、极大值原理或动态规划得到最优控制的必要条件( 如 两点边值问题，r i c c a t i 方程等) ，然后再考虑这些必要条件的数值解法，如打靶法、拟 线性化法以及r i c c a t i 方程度符号函数法等。直接法是将静态最优化技术直接应用于最 优控制这个动态优化问题的求解方法，如梯度法、共轭梯度法、牛顿法、变尺度法等， 或者是通过参数化方法将动态优化问题转化为静态优化问题进行求解，其中包括控制向 量参数化方法和数值动态规划等。 控制向量参数化方法是一种求解最优控制问题的直接方法，它将无穷维的最优控制 问题转化为有限维的优化问题进行求解。在早期的参数化方法当中，选取有限时间点将 最优控制问题离散化，控制变量和状态变量作为独立的求解变量，离散后的状态方程作 为静态优化问题的等式约束条件【2 0 1 。后来人们采用分段多项式函数来近似地表示控制变 量和状态变量，从而提高了算法的效率。这类方法是状态向量和控制向量同时被参数化 的方法。另外一种方法是只对控制向量参数化，状态变量通过系统的状态方程来计算， 这样做减少了参数和约束条件的个数。文献 2 1 】将控制变量近似地表示为一些待定参数 和关于时间的多项式函数的线性组合，最优控制问题只考虑了状态方程度约束，最终被 转化为一个无约束的优化问题，在求解无约束的优化问题时也没有采用基于梯度的方 法。在1 9 7 0 年以后，这一方法得到了改进，分段多项式函数被用来近似地表示控制变 量，并且可以计算出目标函数对参数的偏导数以及有效地处理约束条件。目标函数的梯 度可以通过前向差分方法【2 2 1 、灵敏度方程方法和伴随方程度方法【2 4 1 来计算。 常规的动态规划数值计算方法在实现时，往往存在令现有计算机难以承受的巨大的 内存空间及计算时间要求，即“维数灾”问题。尽管已提出了许多改进算法，如疏密网 格法、状态增量法( s i d p ) 、离散微分增量法( d d d p ) 、双状态法( b s d p ) ，逐次逼近法( d p s a ) 及二阶段滑动寻优法( p o a ) 等，其目的是为了提高计算效率并减少存贮量，然而，这些 算法大多以牺牲计算时问或计算精度为代价，来换取较小的高速内存需求。难以满足实 际工程问题对计算速度和计算精度愈来愈高的要求。 4 中国石油大学( 华东) 硕士学位论文 r e i nl u u s 在1 9 9 0 年前后提出了迭代动态规划算法，并在一些复杂对象中得到应用。 迭代动态规划是解决非线性系统全局最优控制问题的有效手段，是实际化工生产系统优 化控制问题的有效方法【2 5 粕】。过程系统的最优控制是实际化工生产中常见课题，多数情 况下涉及的连续系统是以复杂的非线性微分方程组表示的，一般的优化方法对求解这一 系列非线性方程组的全局最优解是很困难的。迭代动态规划能够避免求解系统h j b 方程 以及高维方程中可能出现的计算量激增的问题。迭代动态规划将连续系统从时间和空间 两个角度进行离散，使对应于离散后的不同时间段的所有状态变量被离散为一组网格， 在每一时间段应用不同的控制变量可行值进行计算，最终找到使得非线性系统的性能指 标最优的完整控制策略。 迭代动态规划具有易实现、强鲁棒性、不需要系统的微分方程、不涉及难以求解的 非线性规划等优点。正是因此迭代动态规划引起了大量学者的关注和研究，已经在很多 领域得到了应用，在一些时变动态非线性系统中解决了些实际的最优控制问题，扩展 了最优控制的应用领域但i d p 方法目前只应用到了常微分约束的最优控制问题中，在 偏微分约束的分布参数最优控制中应用极少。 1 2 2 并行计算的发展 随着计算在科学研究和实际应用中发挥着越来越大的作用，人们对计算已经产生了 依赖，将数值模拟优化作为许多决策的依据。现在人们已经将计算作为科学研究的第三 种手段，和传统的科学研究的理论方法和实验方法并列。但对大规模问题和强非线性系 统的求解，需要耗费大量的计算时间才能解决，单机性能已不能满足需求。解决的办法 就是利用并行计算技术，包括并行计算机硬件和并行算法两个方面。 近年来，由于机群系统【2 7 - 2 8 】的发展，使得越来越多的人研究并行算法成为可能。 因为基于p c 机群系统开发周期短，价格低廉，升级方便。机群系统上的开发平台如 m p i 、p v m 日趋成熟，这些软件平台往往是跨操作系统的，因此开发出来的应用程序， 可以方便的进行移植。而以往的传统的并行系统需要专门的语言和指令，缺乏统一的标 准，通用性很差。机群系统已经在各行各业得到了广泛应用。石油、气象等应用部门已 进行了实际的应用研究和开发，取得了良好的效果。在过程系统中，模型建立、过程模 拟、系统优化等方面的并行化也都有了大量的研究成果【2 9 - 3 0 1 。 自从并行机出现以来，并行算法的研究越来越活跃。并行算法的设计依赖一下的事 实，即独立的计算可以同时执行。如果一个算法包含大量的独立计算，则称这个算法具 第一章前言 有内在的并行性。并行算法的设计应该利用这种计算无关性，将各种无关计算单元分而 治之。并行优化的策略基本上分为一下几类【3 l 】。 1 ) 按变量分裂的并行计算 将一个大规模的优化问题分解成一系列规模较小的容易求解的子问题，设计优化并 行算法的基本方法之一。因为这些子问题的求解往往是独立的，所以可以利用多台处理 器容易组织成并行算法。 2 ) 目标函数、约束方程和梯度值的并行计算 3 ) 计算步骤的并行化 计算步骤的并行化不是指函数的计算的并行，并行的是优化算法本身，即不同迭代 步的工作可在同一时刻在不同的处理器上进行。如并行拟牛顿法的一种思路就是：在线 性搜索中当一台计算机在计算某点的函数值时，其他p 一1 台计算机就同时计算该点梯度 的p 一1 个分量。如果该点被线性搜索采纳，则已算出了梯度的p 一1 个分量。 数值优化算法基本分为两类，利用梯度信息和不利用梯度信息。仿生类算法和迭代 动态规划算法属于后者。仿生类算法已有大量的并行思路，用于实际应用中【3 2 - 3 4 1 。迭代 动态规划算法具有天然的并行性，基于p c 机群和平台并行编程环境m p i 研究其并行化， 可提高算法的计算效率，减少求解大规模问题的计算时间，提高其解决最优控制问题的 适用性。 1 。3 本文的主要内容 本文研究了迭代动态规划在工业过程优化中的应用，研究了其基本算法及对状态约 束优化问题的扩展求解。利用迭代动态规划算法对l q r 最优控制问题求解并与解析解 比较及对若干文献化工实例的求解，验证了迭代动态规划在最优控制问题上的有效性， 并研究了算法参数的选取对算法效率的影响。通过数值离散化将迭代动态规划应用到一 类分布参数系统的最优控制策略求解问题上。基于搭建的实验室并行计算平台，实现了 迭代动态规划的并行化，并通过若干例子的求解验证了算法的并行效率。本文章节安排 如下： 第一章综述了研究工业过程最优控制的意义及利用并行技术提高优化求解的需求， 介绍了最优控制算法和并行计算软硬件的现状与发展。 第二章研究了迭代动态规划的基本算法及对状态约束优化问题的扩展求解。利用迭 6 中国石油大学( 华东) 硕士学位论文 代动态规划算法对l q r 最优控制问题求解并与解析解比较，并求解了三个文献化工最 优控制实例，验证了迭代动态规划在最优控制问题上的有效性，并研究了算法参数的选 取对算法效率的影响。 第三章构建了基于w i n d o w s 的并行计算平台。首先介绍了并行计算软硬件的发展。 基于实验室p c 节点及1 0 0 m 局域网环境，并以一台服务器为主节点建立了机群。以 w i n d o w s 系统为基础，结合m p i c h 消息传递并行编程平台，实现了简单的机群单一系 统映象，并对该机群系统进行了性能测试。介绍了m p i 并行编程技术，并结合矩阵相乘 的例子说明了通信及计算规模等对并行编程效率的影响。 第四章分析了动态优化算法的几种基于粒度的并行思路，实现了基于m p i 消息传递 和p c 机群的迭代动态规划粗粒度主从式并行算法。 第五章并行求解了两个文献化工实例，与串行求解结果进行比较，验证了并行迭代 动态规划算法的有效性，分析了求解中任务划分、通信等对并行效率的影响。通过将一 类一维分布参数的最优控制问题基于有限差分法将其转化为适于动态规划求解的形式， 并实施迭代动态规划算法，通过一维热传导问题和一维聚合物驱最优注入策略问题实例 验证了有效性。 7 第二章迭代动态规划算法 第二章迭代动态规划算法 基于对多级决策过程的研究，美国学者贝尔曼在本世纪5 0 年代提出了动态规划方 法。目前，动态规划在许多技术领域中的优化方法处理方面获得了广泛的应用。动态规 划的核心是贝尔曼最优性原理，它首先将一个多级决策问题转化为一系列单级决策问 题，然后从最后一级状态开始逆向推向初始级状态为止，即在求解多级决策问题时，要 从末端开始到始端为止，逆向递推。最优性原理表述为： 若一个级决策是最优的，则以第k 级( k n ) 决策形成的状态作为初始的任何一 个n k 级的子决策也必然是最优的，即：将最优决策的任何一级作为初始级，这一级 的状态作为初始，由此以后一直到最终级为止的余下的决策，对于由这一级开始往后的 多级过程是一个最优决策。 考虑如下一组微分方程描述的最优控制问题： 性能指标取为： 3 i x ( t o ) ，o 】_ 嗍) ，d + j ，触 ( 2 - 1 ) 状态方程为： 戈= 厂( x o ) ，材( f ) ，r ) ，x ( t o ) = x o( 2 - 2 ) 控制约束为： 吩u j 色，j = 1 ，2 ，。，m 其中，x 是n 维状态变量，u 是系统的m 维控制变量。 该最优控制问题即为在t o 到7 ，时间段内，求得容许控制u ( t ) u ，f 【t o ，t ，】，使得 系统由给定初态出发，在f ， t o 时刻转移到目标，并使性能，最优。 2 1 连续系统动态规划基本原理 对上述连续系统最优控制问题，性能指标改写为： y ( f ，x ，“) 2 沙( x ( o ) ) + j 。研x ( f ) ，材( ，) ，f 】旃 若t = 0 ，则v ( t ，x ，u ) 就是原系统的性能指标 矿( o ，掰) = 歹h ( ) ，o 】= ( x ( o ) ) + f 7 x ) ，材p ) ，t d t 若系统在区间p ，】上由最优控制策略“作用，则v ( t ，x ，甜) 达到最小，记为矿( f ，x ，“) ， 中国石油大学( 华东) 硕士学位论文 简写为v ( t ，x ) 。根据最优性原理，有下式成立 a v ( t , x ) ：m i 。nv ( ，x ，“ f ，0 】) o t u t1 ，f ， 。j “ 终态为v ( t i ，x ) = y x ( 0 ) 】。对于连续系统，推导有如下h a m i l t o n - j a c o b i b e l l m a n 方程成 立： o v _ ( _ t 一, x ) ：一m i n v 。v ( t , x ) f ( x , u , 1 ) + 驴( x ，“，) ( 2 - 3 ) o t “ 终态为v ( t i ，z ) = y 【x ( 0 ) 】。 2 2 数值动态规划算法 2 , 2 1 数值动态规划算法步骤 式( 2 3 ) 是一个偏微分方程，只有在较为简单的情形下可以得到解析解。为此贝尔曼 提出了动态规划的数值求解方法。 考虑离散型的动态系统，设其向量差分方程为： x ( k + 1 ) = 厂 x ( 尼) ，“( 七) ，k 】x ( o ) = x o ( 2 - 4 ) 要找出个控制向量“( o ) ，u 0 ) ，“( 2 ) ，u ( n 一1 ) ，使得目标函数 一l g a x ( k ) ，甜( 后) 】+ g h ( ) 】 k = o 达到最小。对于连续动态优化问题，应首先实施时间区问的离散化。 _ 一l 如果存在最优解，则目标函数g x ( 后) ，“( 七) 】+ g h ( ) 】的最小值必为初始值x ( o ) ，- 1 与控制步数的函数，设为旺( o ) 】，同理，从k = i 至_ l jn l 上的q x ( 尼) ，甜( 尼) 】+ g 瞳( ) 】 的最小值必为x ( f ) 与控制步数n - i 的函数，设为h n 一。b ( f ) 】。 据此，动态规划方法实施步骤为： 1 ) 令 x ( ) 】= 6 f 【z ( ) 】； 2 ) 对于任一x ( 一1 ) ，有啊防( 一1 ) 】_ 删m i - ”n g 一- ( ) + b ( ) 】) 其中x ( ) = f i x ( n - 1 ) ，u ( n - 1 ) ，n 一1 】求出使得式右边最小的“+ ( 一1 ) ，它是x ( 一1 ) 的函数，于是得 9 第二章迭代动态规划算法 h l x ( n - 1 ) 】= g 一l b ( 一1 ) ，u ( 一1 ) 】+ x ( 一1 ) ，u ( n - 1 ) ，n - 1 3 ) 对于任一x ( n 一2 ) ，有吃h ( 一2 ) 】_ 。m ( i - 2 ) n g 一z ( ) + 鲋x ( 一1 ) 】 其中x ( n 一1 ) = f x ( n 一2 ) ，u ( n 一2 ) ，n 一2 】。求出使得式右边最小的“( n 一2 ) ，它是 x ( n 一2 ) 的函数，于是得： l h x ( n 一2 ) 】= g n 一：i x ( n - 2 ) ，“+ ( 一2 ) 】+ 磊 厂【x ( 一2 ) ，u ( n - 2 ) ，n - 2 ) 4 ) 一般的，令i = n 一3 ，一4 ，等，对于任- - x ( i ) ，有 一，阢( - i ) 】- 啦p g j ( ) + 小。口( f + 1 ) ) 其中x ( i + 1 ) = 九x ( 耽u ( o ，i 】。求出使得式右边最小的甜( f ) ，它是x ( f ) 的函数，于是得 一，i x ( i ) 】= g i x ( i ) ，u ( 明+ 斗， f i x ( i ) ，“( f ) ，小 5 ) 重复步骤4 至i = o ，便得到最优的控制策略u ( 0 ) ，u ( 1 ) ，u ( 一1 ) 和目标函数的最小 值h n 【x ( 0 ) 】。 2 2 2 动态规划方法与其他方法比较 动态规划方法、最小值原理是解决系统优化问题的有效的计算方法。这些方法各有 特点。各自适用于不同特性的系统。目前为止，没有哪一种方法可以解决各种不同特性 的系统优化问题。本节比较动态规划方法与最小值原理的特点【1 7 】。 1 ) 系统状态参数的维数与计算量的关系 动态规划法要逐级计算所有可能情况下的最优值，计算工作量或计算机内存量与 状态参数的维数的指数有关。如一维参数在可能范围内计算1 0 个可能状态，对二维参 数，每一个参数有1 0 个可能状态，就有种1 0 2 可能的状态。因此动态规划方法对状态 参数的维数很敏感，当状态参数超过三维，用数值法求解时，很难用内插法求得中间 数据。这种情况称为维数灾难。这是动态规划获得广泛应用得主要障碍。最小值原理 的计算工作量或信息储存量与参数得维数成线性关系。 2 ) 参数受有界约束时对计算的影响 动态规划方法是要计算各种可能情况下的最优解，当变量受有界约束时，只需在界 域内给出可能状态，对计算并不增加任何困难。 l o 中国石油大学( 华东) 硕士学位论文 3 ) 系统的目标函数为多峰函数对计算结果的影响 因为动态规划计算了所有可能的情况，可从多个极值点中选取最优值，与目标函数 是否为多峰函数无关，数值计算时如忽略内插引起的误差，可以求得最优解。最大值原 理给出的必要条件求的是目标函数为极值的解，不能保证得到的是全局最优解。 4 ) 提供的信息量及计算速度的比较 动态规划的计算方法决定了此法可提供的信息量大，当外界条件发生变化时，可以 利用原来的计算结果，很快得到新的最优策略，而最大值原理只能得到与外界条件相应 的一组解，当条件稍有变动就需要重新计算。 计算速度方面，用数值计算方法来比较，当两种方法所要求的精度相等时，动态规 划方法所需的计算时间长，且随着级数的增加，两者差别更大，时间可长几倍到十几倍。 2 3 迭代动态规划基本算法及若干参数的选取 针对常规动态规划算法计算时间长，容易出现维数灾难的缺点，r e i nl u u s 在1 9 9 0 年前后提出了迭代动态规划算法【2 5 1 。迭代动态规划能够避免求解系统 h a m i l t o n j a c o b i b e l l m a n 方程以及缓解高维方程中可能出现的计算量激增的问题。迭 代动态规划具有易实现、强鲁棒性、不需要系统的微分方程、不涉及难以求解的非线性 规划等优点。 2 3 1 迭代动态规划基本算法 迭代动态规划可以描述为下面的步骤： s t e p l ：将时间初始化为p 个等分阶段，每个时间段为l ； s t e p 2 ：选择控制变量的离散个数，表示为r ，在初始控制区域r i 内选择初始控制策略， 同时确定初始的收缩因子r ，以及还原因子召；选取循环次数n 以及每次循环的迭 代次数m ； s t e p 3 ：用g 表示当前循环的次数，置g = 1 ；用表示当前迭代次数，置= 1 ； s t e p 4 ：设置当前控制区域，= r q - l r i ； s t e p 5 ：j 羽当前的控制策略以及气时刻的状态，计算得到当前各个时间段的系统状态值 x ( 露) ，k = 1 ，p ； s t e p 6 ：从第p 个时问段开始求解每个时间段内的最优控制策略，置当前时间段k = p - 1 ； 1 1 第二章迭代动态规划算法 当前时间段内，每个控制变量在控制区域r 内均匀选择r 个值，组成当前控制策略 集，用当前段的各个控制策略、当前段的初始状态x ( k ) 以及以后时间段的最优控 制策略，计算以后各个时间段的状态并得到性能指标，比较各个性能指标，选 择最小的，对应的控制策略作为当前时间段的最优控制策略u ( k ) ；时间段前移 k = k 一1 ；当k = o 时完成本次迭代； s t e p 7 ：收缩控制变量的控制区域，= y r ；增加迭代次数，歹= j + l ；迭代m 次之后完成本次 循环并重置= 1 ； s t e p 8 ：循环次数加一，q = q + l ；循环n 次之后完成计算。 从上述步骤可以看出，迭代动态规划的计算方法和常规动态规划一样是从所有阶段 的最后一个阶段开始，先计算最后阶段的最优控制策略，然后向前逐个阶段求解。每一 阶段的求解都以已经得到的后面的各个阶段的控制策略为基础。 2 3 2 状态存在约束时最优控制问题的迭代动态规划求解 迭代动态规划的基本算法只能解决没有状态约束的控制问题，为了求解状态存在约 束的最优控制问题，l u u s 提出迭代动态规划算法结合罚函数法的方法。 2 3 2 1 终端状态约束优化问题的i d p 求解 对( 2 。1 ) ( 2 。2 ) 式描述的最优控制问题，在终端时刻f ，若干个状态存在约束，或者 为等式约束 薯o 厂) = 薯i = 1 ，2 ，m 或者为不等式约束 誓q ，) s f i = l ，2 ，搬 应用迭代动态规划方法解决上述问题，为了满足终端时刻状态约束，构造增广的性 能指标 ，= ，b ( o ) ，0 】+ p o 竹) ) 其中p ( f 瑚是引入的惩罚函数项以满足状态约束。应用迭代动态规划时，有广泛 的惩罚函数可以选择，因为并不要求惩罚函数是可微的。 一般对等式约束可选取如下函数： 1 2 中国石油大学( 华东) 硕士学位论文 罗( x ( 0 ”- - z 谚( t ( 0 ) 一) 2 f 之1 i f x ，( 0 ) 墨 f i x , q r 、) s p ( x ( 0 ) ) = 仍o ( 0 ) ) i = 1 显而易见，惩罚因子2 必须为正值。算法的收敛速度收到惩罚因子大小的影响，因 此对具体的问题而言，少量的初始测试运行是比要的。一般而言，惩罚项很大则收敛较 慢，且需要大量的容许控制策略集合；合理的选取惩罚项会加速收敛过程，且仅需要少 量的容许控制策略集合。 2 3 2 2 不等式状态约束的最优控制问题的i d p 求解 对( 2 1 ) - ( 2 2 ) 式描述的问题，除了控制约束外，存在g 个不等式状态约束 ( x ) 0i = 1 ，2 ，q 应用迭代动态规划方法解决上述问题，为处理上式