两种多维动态规划算法在梯级水库优化调度中的应用

Application of two multi-dimensional dynamic programming algorithms in optimization of cascade reservoirs operation

针对目前大多数改进动态规划算法和智能优化算法应用于梯级水库联合优化调度模型求解时的非全局收敛问题,给出了状态组合遍历和多层嵌套两种多维动态规划算法的求解模式,并从程序复杂度、内存占用以及运行时间等方面对两种方法进行了对比分析,以李仙江流域三库梯级系统为研究背景进行实例计算,得出嵌套结构多维动态规划算法在程序复杂度和内存占用量方面要优于组合遍历多维动态规划算法,但在运行时间方面有所不足的结论。为提高嵌套结构多维动态规划算法的计算效率,将其与并行计算相结合,实例计算表明,并行计算能在一定程度上缓解其运行时间长的缺陷。

In view of the no global convergence problem to most of the improved dynamic programming al？gorithm and intelligent optimization algorithm in the application of cascade reservoirs joint operation optimiza？tion at present, two calculating modes of the multi-dimensional dynamic programming algorithm have been proposed in this paper based on the idea of group traversal and multilayer nested structure. Comparison and analysis of the two methods were carried out in terms of memory usage, computation complexity and run time. Taking cascade reservoirs distributed in the Lixianjiang River basin as the research background for practical calculation,it is concluded that the multilayer nested dynamic programming algorithm is superi？or to the group traversal dynamic programming algorithm in the aspects of programming complexity and memory usage,but inferior in terms of run-time. In order to improve the computation efficiency of multilay？er nested dynamic programming algorithm, combination of this method with the parallel computation is shown in this paper, and case study shows that the parallel computing can ease the defect of long run-time to a certain extent.