梯级水库群优化调度并行动态规划方法

王 森，马志鹏，李善综，熊 静

(1. 珠江水利科学研究院，广州 510611；2. 水利部珠江河口动力学及伴生过程调控重点实验室，广州 510611； 3. 水利部珠江水利委员会技术咨询中心，广州 510611)

梯级水库群优化调度具有显著的高维数、非线性、多阶段、约束强耦合等特点，且梯级水库之间存在复杂的水力和电力联系，优化求解非常困难[1]。动态规划方法是求解梯级水库群优化调度问题的经典算法之一，能够有效地克服非线性、非凸性等求解困难。但是，随着计算电站数目的增多，动态规划方法的优化计算规模、占用内存及耗时呈指数增长，易造成“维数灾”问题[2]，甚至可能导致无法求解。为了缓解“维数灾”问题，衍生出了多种经典的改进动态规划方法，常用的有离散微分动态规划[3]、逐步优化[4]、逐次逼近动态规划[5]等方法。尽管这些改进方法提高了优化求解效率，但是求解精度及质量相比动态规划方法有所下降，更适用于求解规模较大的梯级水库群优化调度问题。当梯级水库群的计算规模在可计算范围内时，动态规划仍然是优先选择的计算方法。因此，如何保证动态规划在满足求解质量要求的基础上提高求解效率，是非常有价值的研究内容。

近年来，随着计算机科学的高速发展以及多核硬件配置的广泛流行，并行技术已成为提高算法计算效率的高效手段，并且在许多研究领域中得到成功应用[6,7]。同时，在水库优化调度领域，并行计算在动态规划方法中的应用也已有相关成果。万新宇[8]等建立基于主从模式的并行动态规划模型，将其运用到水布娅水库的发电优化调度。李想[9]等构建了多维动态规划模型，采用主从模式策略对方法进行并行化，在高性能计算机上测试了四水库优化调度问题。蒋志强[10]等构建了多层嵌套多维动态规划并行算法，应用于李仙江流域三库梯级优化调度求解。这些研究成果普遍采用了兼容C++、Python、C#编码语言的并行框架或工具包，但是目前对动态规划并行化研究的成果中，能够有效兼容Java编码的并行化方法研究较少。而且，由于开发人员对不同编程语言的熟悉程度是影响方法并行化实现方式的关键因素之一，因此，研究Java编码实现的动态规划并行化方法具有重要的现实意义。

Fork/Join框架[11]是Java7提供的一种用于并行执行任务的框架，能够把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果，具有并行效率高、编程易实现等优点，能无缝衔接Java编码方法的并行化实现。因此，为了实现Java编码的动态规划并行化，考虑到动态规划通过离散变量寻优而具有的天然并行性，本文提出了梯级水库优化调度并行动态规划方法(Parallel Dynamic Programming, PDP)。该方法以调度期内所有离散变量组合的求解计算作为父任务，利用Fork/Join多核并行框架将其分解为多个规模更小的子任务进行并行化求解。西江干流梯级水库群长期发电优化调度应用实例结果表明，该方法能够大幅度缩短计算耗时，显著提高计算效率，是求解梯级水库群优化调度非常高效的实用性方法。

1 库群优化调度模型

本文以水库群发电量最大为优化目标，模型描述为：入库流量过程条件下，考虑水量平衡、水位、泄量等各种约束，兼顾防洪、灌溉、航运等综合要求，制定最优调度决策过程，使调度期内水库群发电量最大。模型目标函数及其约束条件如下所示：

目标函数：

(1)

约束条件：

水量平衡方程

(2)

蓄水量约束

(3)

发电流量约束

(4)

出库流量约束

(5)

出力约束

(6)

始末水位约束

(7)

水电系统总出力约束

(8)

2 并行动态规划方法

2.1 动态规划方法

动态规划方法最早由数学家贝尔曼提出，适用于求解多阶段序贯决策优化问题。该方法将多阶段问题转化为多个单阶段问题，逐个求解并最终返回全局优化解，在水库群优化调度领域得到广泛应用。算法的核心思想可通过递推公式进行描述，见公式(9)。

(9)

式中：t、T分别为时段序号和时段数；St、It、Nt分别为M维(电站个数)水库库容、入库流量、出力，均为矢量；f*t(St)为时段t状态为St时，从时段t到末时段的系统最大发电量，亿kWh；Bt(St,It,Nt)为时段t初始蓄水状态为St，入库流量为It，决策出力为Nt时的本时段系统发电量，亿kWh；Tt+1(St+1,It,Nt)为时段t+1到t的状态转移方程，通常为水量平衡方程。

2.2 方法并行性

算法的计算任务是否能够分解为多个规模更小且独立的子任务是判断该算法是否具有并行性的必要条件。以计算时段为月、调度周期为1年的2库梯级水库群优化调度为例，假设调度周期内始末水位固定，蓄水状态离散个数为k，则迭代搜索计算任务规模为k2+10k4+k2，见图1。

结合图1以及式(9)，Bt(St,It,Nt)是递推公式的主要计算任务，其中，在确定性径流优化调度过程中，仅St为状态变量，It为已知条件，Nt通过St状态递推采用以水定电方法可推求，而且St由时段内不同蓄水状态离散值构成，不同的离散值在Bt(St,It,Nt)中的反馈计算是相互独立的。因此，Bt(St,It,Nt)的计算任务具有天然并行性，而且任务规模由St变量的离散数目决定。对于任意一个M库梯级水库群优化调度系统，在调度周期T内的计算规模可表示为公式(10)，如下所示：

kM+(T-2)k2M+kM

(10)

通过算法并行化设计，DP方法的计算任务可平均分配到不同核心同时计算，降低算法计算复杂度。在p核服务器中，DP方法复杂度从O(k2M)缩减到O(k2M/p)。

图1 DP方法优化计算规模示意图Fig.1 Schematic diagram of computational scale of DP

2.3 并行动态规划方法设计

通过方法并行性分析，DP在迭代优化过程中所有离散变量组合在Bt(St,It,Nt)中的求解计算是相互独立可并行的。因此，根据DP方法迭代特点，可将迭代周期内所有变量组合在Bt(St,It,Nt)中的求解计算作为父任务，采用细粒度并行模式实现DP方法的并行化计算。本文采用Fork/Join多核并行框架进行并行化设计，PDP方法详细求解步骤如下：

(1)数据准备。获取计算所需的电站基础属性特征值及特征曲线，包括电站特征水位、出力系数、水位-库容曲线、泄流-尾水位曲线等，并根据水库各时段蓄水上下限、离散个数确定离散状态变量St。

(2)创建线程池，设置线程池线程数与CPU配置逻辑线程数一致。

(3)构建并行计算的父任务。将迭代周期内所有蓄水状态变量组合在Bt(St,It,Nt)中的求解计算作为父任务，并为计算过程中水位、出力、发电量等指标创建存储空间。

(4)设置Fork/Join计算阈值，使子任务分割数与线程池线程数一致。

(5)将各子任务平均分配到子线程中，并调用Fork/Join多核并行框架计算各子任务的返回值。当计算结束时，合并各子任务的解集，返回主线程。

(6)确定最优路径。通过返回的结果集以及递推公式，输出优化计算的最优解。

3 应用实例

3.1 基础信息

本文以西江干流梯级水库群优化调度长期发电量最大模型为测试实例，测试PDP方法在不同并行环境下的计算性能，验证算法的可靠性及效率。目前，西江干流已建电站共7座，其中龙滩、岩滩具有长期调节能力，大化、百龙滩、乐滩、桥巩、长洲电站为日调节或径流式电站。因此，根据梯级水库群优化调度特点，参与优化搜索的电站为龙滩和岩滩两座水库。流域水库群拓扑结构及电站特性参数分别见图2和表1。

图2 流域水库群拓扑结构Fig.2 Topological structure of the cascaded reservoirs

电站/属性调节性能正常高水位/m死水位/m装机容量/MW最大过机流量/(m3·s-1)龙滩年调节375．00330．004900．04970岩滩不完全年调节223．00212．001210．02600大化日调节155．00153．00456．02712百龙滩径流式126．00125．00192．02580乐滩日调节112．00110．00600．03432桥巩日调节84．0082．00456．04920长洲日调节20．6018．60630．07428

3.2 配置及指标

本次测试采用的配置为Dell Precision WorkStation T1600，CPU类型为Intel(R) Xeon(R) E3-1245@3.30 GHz，核心数目为4核。另外，测试并行性能的主要指标为加速比和效率[12]，其数学表达式见公式(11)和式(12)，如下所示：

Sp=T1/Tp

(11)

Ep=Sp/p

(12)

式中：T1为串行执行时间；Tp为p核环境下的执行时间。

3.3 方案设置

本次测试采用库群平水年入库径流作为输入条件。按蓄水状态离散点不同设置两个测试方案，方案1为离散点20，方案2为离散点25，并分别在2核、4核并行环境下测试算法计算耗时、加速比以及效率等指标。

3.4 结果分析

本次测试案例采用的库群发电量最大模型以及动态规划方法为水库群优化调度的基础模型和方法，库群调度结果不再详细分析和阐述，重点对方法的并行性能进行分析。图3、图4、图5分别为不同仿真方案在不同并行环境下测试得到的计算耗时、加速比及效率。从图3中可看到，PDP方法计算耗时比串行方法有明显缩减。DP方法(串行计算)在方案1和方案2中的计算耗时分别为343.2、719.6 s，主要原因是由于DP方法的计算规模主要由离散点数决定，方案2计算规模大于方案1。PDP方法在4核环境下方案1和方案2的最大缩减计算耗时分别为251.7、532.2 s，并行计算优势在规模更大的计算任务中更好地得到体现。从图4中可看到，PDP方法在2核环境下方案1和方案2的加速比分别为1.91、1.95，在4核环境下分别为3.75、3.84，在相同并行环境下，随着计算任务规模的增加，并行计算的最优加速比逐步提高，且越接近理想加速比，更好地发挥并行计算的优势，原因在于相对规模更大的计算任务，线程管理消耗及通信等额外时间消耗占计算总耗时的比例相对较小，线程处于工作运行状态的时间更长。从图5中可看到，PDP方法在2核环境下方案1和方案2的效率分别为95.5%、97.5%，在4核环境下分别为93.8%、96.0%，随着测试环境核数的增加，效率逐渐下降，主要原因在于管理消耗以及通信时间的影响，而且，为了避免数据同步错误的发生，在各工作线程中消耗了更多缓存来单独定义计算所需要的变量，势必影响算法总体的并行性能，降低计算效率。

图3 各方案PDP方法计算耗时Fig.3 Computing time of PDP in diverse cases

图4 各方案PDP方法加速比Fig.4 Speedup of PDP in diverse cases

图5 各方案PDP方法效率Fig.5 Efficiency of PDP in diverse cases

4 结 语

近年来，我国水电事业发展迅猛，各大流域逐步形成了大规模梯级水库群联合调度格局，精细化调度水平亟待提高，尤其是探索高效可行的优化求解方法具有重要意义。本文结合当今流行的并行技术，提出了并行动态规划方法的设计思路及实现方式，并以西江干流梯级水库群优化调度为例，验证了该方法的并行效率，结果表明，该方法有效可行，能显著提升算法求解效率，可为其他动态规划方法并行化设计提供参考和借鉴。但是，由于动态规划方法受“维数灾”影响，应用范围具有一定局限性，下一步工作将进一步开展动态规划降维方法及其并行化研究。

□

[1] Labadie J W.Optimal operation of multireservoir systems:State-of-the-art review[J].Journal of Water Resources Planning and Management,2004,130(2):93-111.

[2] 郭生练,陈炯宏,刘 攀,等. 水库群联合优化调度研究进展与展望[J]. 水科学进展, 2010,21(4):496-503.

[4] Howson H R, Sancho N G F. New algorithm for solution of multistate dynamic programming problems[J]. Mathematical programming, 1975,8(1):104-116.

[5] Yeh W W, Trott M. Optimization of water resources development: Optimization of capacity specification for components of regional, complex, integrated, multi-purpose water resources systems[M]. Los Angeles: Engineering Rep. No. 7245, Univ. of California, 1972.

[6] 莫则尧,张爱清,刘青凯,等. 并行算法与并行编程:从个性、共性到软件复用[J]. 中国科学:信息科学, 2016,46(10):1 392-1 410.

[7] 李 娜,王 杰. 大型泵站装置系统的CFD并行计算及分析[J]. 中国农村水利水电, 2016,35(10):179-181.

[8] 万新宇,王光谦. 基于并行动态规划的水库发电优化[J]. 水力发电学报, 2011,30(6):166-170.

[9] 李 想,魏加华,姚晨晨,等. 基于并行动态规划的水库群优化[J]. 清华大学学报自然科学版, 2013,53(9):1 235-1 240.

[10] 蒋志强,纪昌明,孙 平,等. 多层嵌套动态规划并行算法在梯级水库优化调度中的应用[J]. 中国农村水利水电, 2014,33(9):70-75.

[11] Lea D. A Java fork/join framework[C]∥ In Proceedings of the ACM 2000 conference on Java Grande. 2000:36-43.

[12] 蒋志强,纪昌明,孙 平,等. 多维动态规划三种并行模式的对比分析[J]. 中国农村水利水电, 2015,34(3):168-173.