迭代动态规划算法及并行化研究

论文摘要

动态规划是一种求解多级决策问题的基本工具,在社会经济、工程技术和最优控制等领域有广泛的应用。但常规的动态规划实施存在一系列的困难,Luus提出了动态规划的迭代实施算法,即迭代动态规划。迭代动态规划可以提高常规动态规划算法计算效率并且容易实现。由于动态系统的强非线性和优化问题规模的增大,使得求解过程需要耗费大量的计算时间,而且迭代动态规划算法本身计算量较大,因此研究迭代动态规划的并行实现是必要且具有现实意义的。本文主要研究内容概扩如下:首先研究了迭代动态规划算法在最优控制上的正确性和效率。应用迭代动态规划求解LQR最优控制问题,并与解析解比较,获得了基本一致的最优控制曲线和最优状态曲线。三个有控制约束或状态约束的文献化工最优控制实例的求解结果表明迭代动态规划对非线性工业过程是有效的。本文还研究了算法参数的选取及算法效率的影响。其次建立了并验证了一个并行计算平台。基于实验室PC节点及100M局域网环境,并以一台服务器为主节点建立了硬件机群环境。以Windows系统为基础,结合MPICH消息传递并行编程平台,实现了简单的机群单一系统映象。通过矩阵相乘的例子说明了通信及计算规模等对并行编程效率的影响并检验了机群的有效性。再次实现了基于搭建的并行计算平台的迭代动态规划粗粒度主从式并行算法,并求解了三个文献化工集总最优控制实例,以加速比和并行效率作为度量,验证了算法的有效性。最后将一类分布参数最优控制问题利用有限差分离散成动态规划模型,给出了迭代动态规划求解该类问题的步骤。以一维热传导最优控制和一维聚合物驱最优控制策略问题为例,分别运用串并行迭代动态规划算法进行了求解。结果验证了算法的正确性。

论文目录

• 摘要
• Abstract
• 第一章 前言
• 1.1 研究意义
• 1.2 研究现状
• 1.2.1 最优控制问题求解方法
• 1.2.2 并行计算的发展
• 1.3 本文的主要内容
• 第二章 迭代动态规划算法
• 2.1 连续系统动态规划基本原理
• 2.2 数值动态规划算法
• 2.2.1 数值动态规划算法步骤
• 2.2.2 动态规划方法与其他方法比较
• 2.3 迭代动态规划基本算法及若干参数的选取
• 2.3.1 迭代动态规划基本算法
• 2.3.2 状态存在约束时最优控制问题的迭代动态规划求解
• 2.3.3 迭代动态规划算法若干参数的选取方法
• 2.4 最优控制问题的迭代动态规划求解实例
• 2.4.1 LQR 优化问题的迭代动态规划求解
• 2.4.2 集总非线性最优控制迭代动态规划求解实例
• 第三章 基于WINDOWS 的并行计算平台的构建
• 3.1 并行计算概述
• 3.1.1 发展并行计算的需求
• 3.1.2 并行计算机的发展历程及当代并行机体系结构
• 3.1.3 并行程序的编程语言与环境
• 3.2 并行计算平台的构建
• 3.2.1 并行平台硬件构建
• 3.2.2 并行编程平台的构建
• 3.3 MPI 编程技术
• 3.3.1 MPI 并行编程概述
• 3.3.2 MPI 六个基本函数
• 3.3.3 MPI 编程模式
• 3.3.4 MPI 程序性能测试
• 3.4 矩阵相乘的并行编程应用及分析
• 3.4.1 矩阵相乘算法概述
• 3.4.2 Cannon 算法扩展性分析
• 3.4.3 Cannon 算法并行程序设计及测试
• 第四章 迭代动态规划的并行化
• 4.1 动态优化算法基于粒度选择的并行策略概述
• 4.2 并行算法性能度量
• 4.3 迭代动态规划的并行实现
• 第五章 基于WINDOWS 并行计算平台的迭代动态规划应用
• 5.1 集总非线性最优控制并行迭代动态规划应用
• 5.2 迭代动态规划在一维分布参数系统优化过程中的应用
• 5.2.1 一维分布参数最优控制问题描述及迭代动态规划求解
• 5.2.2 一维热传导模型的最优控制求解
• 5.2.3 迭代动态规划在一维聚合物驱实验模型中的应用
• 5.2.4 一维聚合物驱最优控制策略的迭代动态规划并行求解
• 总结
• 参考文献
• 攻读硕士学位期间取的的学术成果
• 致谢