优化算法在调度与控制问题中的应用研究

论文摘要

近年来,最优化算法在调度与控制领域的应用研究因其在生产、经济与社会中的重要影响而受到广泛关注。本文围绕几类优化算法在调度与控制问题上的应用,针对不同的优化问题,设计并实现了不同的优化算法,并且通过测试与仿真验证了各算法的有效性:首先,对于近年来日益受到关注的体育联赛赛程调度问题,本文提出一种新的基于禁忌搜索与VND算法的混合搜索算法。该算法首先采用一种改进的构造性的思路,快速生成高质量的初始可行解;然后在此初始可行解的基础上,结合禁忌搜索与VND算法思想,通过3种有效的邻域移动,深入遍历庞大的邻域结构;并且通过迭代次数的调整,算法能够在合理的时间内对于标准问题得出非常具有竞争力的结果。对于缺乏模型而直接从数据出发的控制问题,本文提出了一种基于线性系统凸组合与摄动优化的数据驱动控制算法。该算法分为三个环节,第一步从一个状态初始点的稳定控制序列离线数据出发,构造一个范围的控制序列;第二步通过定义控制性能指标函数,根据从状态边界点出发的不同控制序列的线性组合求解范围内的最优控制序列;第三步通过摄动方法寻找边界点控制序列的优化梯度方向,跳出局部最优,完成控制策略优化。算法的有效性通过仿真得到了验证。最后,对于预测控制中十分关键的凸二次规划问题,本文根据目前主流的求解二次规划的算法,设计并开发了专门的凸二次规划求解软件。该软件使用C++编写,采用统一的接口,包含有效集法,内点法和Wolfe单纯形法三种可选算法,能够处理规模在500维以上的大规模二次规划问题。通过对标准问题集的测试,以及与主流商业软件的对比,证明了该软件能够快速精确地求解预测控制中的凸二次规划问题。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 引言
• 1.2 数学规划算法
• 1.2.1 线性规划（Linear Programming）问题简介
• 1.2.2 二次规划（Quadratic Programming）问题简介
• 1.3 最速下降法
• 1.4 基于局部搜索的半启发式优化算法
• 1.4.1 禁忌搜索（Tabu Search）算法简介
• 1.4.2 变邻域下降（VND）算法简介
• 1.5 本文的主要内容与章节安排
• 第二章 求解体育联赛调度问题的混合局部搜索算法
• 2.1 研究意义和背景
• 2.2 体育联赛调度问题描述
• 2.3 构造化初始可行解
• 2.3.1 抽象赛程生成
• 2.3.2 真实队分配
• 2.3.3 分配主客场
• 2.4 邻域结构定义
• 2.4.1 主客场交换（HAS）
• 2.4.2 队伍交换（TS）
• 2.4.3 回合交换（RS）
• 2.5 混合局部搜索算法及其改进
• 2.6 计算结果与讨论
• 2.7 本章小结
• 第三章 基于凸组合的数据驱动控制算法设计
• 3.1 数据驱动控制算法简介
• 3.2 基本引理
• 3.3 离线构造范围控制序列
• 3.4 基于凸组合的范围控制优化策略
• 3.5 状态边界点控制策略的摄动优化
• 3.6 算法仿真验证
• 3.7 本章小结
• 第四章 预测控制的二次规划求解软件设计与应用
• 4.1 求解问题描述
• 4.1.1 模型预测控制中的优化问题
• 4.1.2 二次规划问题描述
• 4.2 算法介绍
• 4.2.1 有效集法
• 4.2.1.1 求解初始可行解
• 4.2.1.2 有效集法计算步骤
• 4.2.2 内点法
• 4.2.3 改进的Wolfe 单纯形法
• 4.3 软件结构及接口定义
• 4.3.1 软件结构
• 4.3.2 接口定义
• 4.4 测试结果及分析
• 4.4.1 有效集法测试
• 4.4.2 内点法测试
• 4.4.3 单纯形法测试
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 本文研究内容
• 5.2 未来研究展望
• 参考文献
• 致谢
• 攻读硕士学位期间已发表或录用的论文专利