均匀动态规划方法及其在水电系统优化调度中的应用-水利学报.pdf

水 利 学 报 2015年12月 SHUILI XUEBAO 第46卷 第12期 文章编号：0559-9350（2015）12-1487-10 均匀动态规划方法及其在水电系统优化调度中的应用 冯仲恺，程春田，牛文静，廖胜利，申建建 （大连理工大学 水电与水信息研究所，辽宁 大连 116023） 摘要：动态规划（DynamicProgramming，DP）是求解多维多阶段复杂决策问题的有效方法，然而维数灾问题极大 地限制了它的应用。为缓解这一问题，结合均匀试验设计提出均匀动态规划（UniformDynamicProgramming， UDP）。UDP以DP为基础框架，将各阶段不同维度离散状态的组合视为多因素多水平试验，利用均匀设计表从全 部状态变量中优选少数极具代表性、在可行域内均匀散布的状态变量进行计算，大幅降低各阶段状态变量集合基 数。分析表明，UDP空间复杂度和时间复杂度由DP指数增长分别降至线性和平方增长，存储量和运算量显著减 少，同时澜沧江梯级水电站群仿真测试结果验证了UDP的高效性和实用性。 关键词：多维；多阶段；复杂决策问题；动态规划；均匀试验；降维；维数灾；优化调度 中图分类号：TV697 文献标识码：A doi ：10.13243/ki.slxb 1 研究背景 大规模水利、电力和交通等系统的最优控制与调度运行通常涉及到非常复杂的目标函数和约束 ［1-2］ 条件，是典型的多维多阶段决策问题，一般很难对目标和约束进行分解与简化 ，难以采用传统 ［3-5］ 的线性优化、非线性优化等方法直接进行求解 。在这样的情况下，对目标函数和约束条件无严 ［6-8］ 格要求的动态规划（DP）在工程实际中得到了广泛重视 。DP将复杂高维决策问题通过分段降维转 化为一系列结构相似的简单低维子问题，利用各阶段之间的关联关系递归求解，可获取全局最优 解及各子过程最优解。然而DP方法的求解规模与计算效率受控于阶段数目、状态变量和决策变 量，特别是当系统规模增加时，DP计算量与存储量皆呈指数增长，“维数灾”问题不可避免［9-11］。 以水电优化调度为例，国内外研究与实践均表明：DP求解2座电站时已面临严重维数障碍，必须 有高超的优化求解技术和策略方可处理3座及以上电站。为此提出很多缓解这一问题的方法，代表 性的有POA［12-13］、DDDP［14-16］和DPSA［17-18］等方法，上述方法分别从减少优化阶段、离散状态、计算 维度等途径实现降维，但在求解大规模复杂问题时仍存在维数灾、局部收敛等不足［19-21］。而我国特 大流域梯级水电站群动辄十数级，如澜沧江和金沙江流域分别规划建设水电站14座和3库25级，如 何对常规方法进一步改进以在合理占用内存下快速获取高质量优化结果，对类似大规模复杂实际工 程问题具有尤为重要的理论价值和现实意义。 本文首先对DP时间和空间复杂度展开了理论分析，研究发现：各个计算阶段不同维度离散状态 间的全面组合是DP维数灾问题的产生根源。这与作者对POA与DDDP维数灾问题的研究成果相一 ［13］ ［14］ 致，所提出的OPOA 和ODDDP 方法均采用正交试验设计减少单阶段状态组合数目，能够在大幅 提高计算效率的同时有效降低所需存储规模。不同于正交试验设计选择具备“均匀分散”和“整齐可 收稿日期：2015-04-03 基金项目：国家自然科学基金重大国际合作项目；国家重点基础研究发展计划（973计划）项目（2013CB035906） 作者简介：冯仲恺（1988-），男，山东荷泽人，博士生，主要从事水电系统优化运行研究。E-mail：myfellow@163.com 通讯作者：程春田（1965-），男，教授，博士生导师，长江学者特聘教授，主要从事大规模复杂水电系统研究。