水库(群)发电优化调度计算的并行策略研究

吴 昊，纪昌明，张验科(华北电力大学可再生能源学院， 北京 102206)

0 引 言

模型构建和算法求解是关于水库(群)优化调度问题研究的两个主要方向[1]。水库群规模至今已逐渐发展成串联、并联以及由串并联组成的混联模式，构建的优化模型更加复杂与精细，相应优化算法随之更加计算繁重。随着并行技术的兴起与发展，学者们提出了针对多种优化方法的并行化策略，可进一步提高水库(群)优化调度计算效率，实现求得满意最优解和计算耗时较少的双重目标。

本文以单一水库、并联水库群、串联水库群以及混联水库群优化调度为背景，较全面综述了诸多学者在主要传统求解方法和智能优化方法计算中应用的并行策略及其原理。并行技术有效缩短了复杂的优化计算耗时，然而目前并行策略大都还是基于或改进于传统求解方法的并行动态规划和智能优化算法中分解后子群并行性特点。串联水库群发电优化调度算法一直是学者们致力研究的重点和难点，一般很难同时兼顾优化解的精度和计算耗时。郑慧涛[2]的博士论文中，基于水库群短期发电优化调度模型计算特点，拓展粗粒度并行思维，将混联水库群分解成独立计算的单库，使具有并联、串联关系的各个子水库优化计算实现并行，在水库群发电优化调度并行策略研究中有了质的飞越。然而在串联水库群中长期发电优化调度中，郑慧涛博士研究有关出入流关系水库的并行策略依据准则并不适用。因此是否可以像并联水库群一样，在中长期优化调度中将上下库具有出入流关系的串联水库群分解为独立计算的单库子系统，分配于不同的对应的计算单元，实现粗粒度并行计算模式，将是本文致力于研究串联水库群创新性并行策略的切入点，文中将此计算模式称为异步并行计算。

之后以我国西南地区李仙江流域上崖羊山、石门坎水库组成的串联水库群为例，在其中长期发电优化调度中，对分解协调异步并行计算展开了相关论证。本文针对水库(群)展开并行策略的研究，为复杂水库群系统在发电、防洪、灌溉等水资源优化调度领域提供了新的研究与应用方向，为人力、物力、财力等资源优化配置提供了一定的理论依据。

1 水库(群)发电优化调度计算的并行策略研究进展

1.1 并行策略的主要研究方向

在单库和水库群发电优化调度中，传统优化方法主要为动态规划、线性规划、非线性规划、逐次逼近法、逐步优化法等；智能优化方法主要是以遗传算法、蚁群算法、粒子群算法、模拟退火算法、人工鱼群算法、混沌算法以及人工鱼群算法等为典型代表。

万新宇[3]针对水库发电优化调度，分析了传统串行动态规划算法的计算特点，由此建立了主从模式的并行动态规划模型。李想[4]以经典四水库问题为例构建多维动态规划模型，也是基于主从模式的并行动态规划算法，并成功在高性能并行计算机上进行求解。二位学者的并行策略基本一致，都是基于状态点相互独立的并行动态规划思想，不同之处是前者应用于单库，后者以简单的混联水库群作为研究对象。

李想[5]针对水库优化调度采用的是并行遗传算法中的粗粒度模型，基本思想是将某种群分割成若干个子种群，各子种群在对应不同编号的处理单元上相互独立地并发执行进化操作，实现计算时间的重叠，经过数次迭代进化，各子种群间会交换部分个体，从而丰富各子种群的多样性，防止早熟发生，不断积累优秀基因。陈立华[6]对水库群优化调度中的粗粒度并行粒子群算法展开研究，其基本思想是参照处理单元的数目把对象粒子群分成数个子群体，并对应分配至每个处理单元，使各处理单元上的子群体能够独立搜索最优解，实现计算时间的重叠。可见两种智能优化算法并行思想的基本点都是将待计算群体分成不相关联的子群，再分配到不同的计算单元作为子任务处理，实现并行计算。

总之，目前有关发电优化调度的并行策略可归纳为两大类：在传统优化算法的并行策略中，最常用的是基于状态点相互独立和阶段重构的并行动态规划；而在各种智能优化算法中的并行策略，基本都是将待计算群体分解成不相关联的子群，分配到不同的计算单元处理，实现并行计算。

以上两类主要并行策略可适用于单一水库以及串联水库群的优化计算。

对于并联水库群优化计算，可以遵循两种并行思路：第一，对于其中的组成单库可以应用以上两类以分解算法计算过程为子任务的并行策略；第二，将各单库独立计算体作为不同子任务分配到各自对应的处理单元并行处理，即实现粗粒度并行计算，可将对应不同组成单库的数台计算机互联，作为该并联水库群发电优化调度的仿真系统。

若将数台互联的独立计算机对应串联水库群中前后毗邻的各单库，仿真该串联水库群系统，由此可产生是否能实现此串联水库群中各单库独立计算粗粒度并行化的思考。

针对混联水库群，初步思想是将其分解成并联和串联子水库群，再用相应的并行策略解决其优化计算问题。

1.2 串联水库群优化计算新型并行策略研究切入点

毛睿[7]根据上下库无出入流关系特征把混联水库群分解出可并联的数个串联子水库群，将各自优化计算作为子任务进行了并行处理。

目前有关串联水库群的并行策略大都是围绕着并行动态规划和智能算法中并行子群的计算模式，只是在此基础上改进或进行几种算法结合，较长时间没有在串联水库群优化调度中实现并行计算的实质性算法创新。直至郑慧涛在博士论文中对串联水库群短期发电优化调度设计出了独特的并行计算方法。郑慧涛博士在大规模混联水库群短期联合优化调度模型中并行策略的关键点是根据并联、串联水库群特点，遵循单库间分布特性、单库间水流传播特性以及水库调节性能三原则，对水库群有效分解成不相关联独立计算的单库子系统，实现优化计算粗粒度并行化。

三原则的详细内容陈述如下：

(1)依据单库地理位置分解，例如在不同流域上的单库之间属于并联关系，水流上不存在直接联系，其特性可体现并行性，因此可以在模拟计算时将隶属不同流域、河流的单库进行简化分解。

(2)依据水流传播特性分解，因在水库群短期优化调度问题中，水流传播时间具有时滞性的特点。若上库泄流传播到下库时间超过了调度期长度，可将预报入流作为下库的流量输入条件。由此，单库之间可进行简化分解。此分解方式适用于串联水库群短期优化调度，但由水流特性可知其明显不适用于串联水库群的中长期优化调度。

(3)依据电站调节性能分解，即上库具有日调节的特点或是径流式，而下库具有季以上中长期调节能力，则上库时段泄流量相对于下库的调节库容来说比较小，对于下库水位的变化影响也较小，可近似认为下库水位不会随上库的泄流变化而变化，因此下库可采用预报入流作为入库流量条件。当单库之间调节性能满足上述条件时，可将此水库群进行简化分解。根据其特点，此分解方法依旧不适合串联水库群中长期优化调度模型。

总结郑慧涛的博士论文可知，将分解后各单库计算作为独立子任务依次分配给不同计算机处理单元，各自可通过优化算法得到求解，可由并行计算提高求解速度。基于划分与分治思想对水库群进行并行计算，经模拟计算结果表明该方法可以提供在较短时间内大规模水库群计算出的短期调度方案，满足了短期调度的时效性要求。得到各子任务结果后，再归约合并得到整体水库群优化调度的最优解。

求串联水库群中长期发电优化调度可借鉴郑慧涛博士分解水库群实现粗粒度并行计算的基本思想，然而水库群分解三原则只适合并联水库群或是短期优化调度的串联水库群。如何分解中长期发电优化调度的串联水库群是本文新型并行策略——异步并行计算的切入点，为研究混联水库群中长期发电优化调度粗粒度并行计算做出了铺垫。

串联水库群可以被看成一个完整的大系统。李爱玲[8]提出了如何将大系统分解协调方法应用于串联水库群中长期发电优化调度模型最优解计算，水库群中各单库之间的关联统一由协调层处理，分解后的各单库优化计算可以不相关联独立进行。吴昊[9]、纪昌明等在此模型基础上，应用多线程技术实现分解后单库子系统的并行动态规划计算，但未实现各单库的粗粒度并行计算。

在毛睿的文献[7]中提到，对于并联水库群，不管是短期还是中长期优化调度，某个单库的入流情况不会受到其他单库出流的影响，因而各单库调度计算可以实现并行；而在串联水库群中长期发电优化调度中，上库调度方案的变化直接影响下库的入流，即下库的入流只有等到上库对应时段的泄流计算得出后方可计算，即串行计算。目前还没有在串联水库群中长期发电优化调度中，实现以各单库作为独立计算体的粗粒度并行计算，即实现各单库计算时间的重叠。

参照动态规划将调度期分成数个时间段，入流随之分成数段，按时间的先后顺序入流有先有后，由此考虑到后库在较早时间段是否可先计算先获得的入流值，使分解后各单库实现计算时间重叠，这是本文研究串联水库群中长期发电优化调度新型并行策略的关键点，为今后混联水库群中长期发电优化调度实现粗粒度并行计算模式奠定了研究基础。

2 串联水库群优化计算的新型并行策略

2.1 串联水库群中长期发电优化调度的大系统分解协调模型

假设某串联水库群由R个以季调节的水库组成，以整个调度期限内的发电量最大作为该水库群中长期发电优化调度准则，可建立基本模型为：

(1)

其中约束条件表达式如下：

Vit min≤Vit≤Vit max(蓄水量约束)

(2)

qit min≤qit≤qit max(放水量约束)

(3)

Nit min≤Nit=ηiqithit≤Nit max(出力约束)

(4)

Vi(t+1)=Vit+(Qit-qit)-Δt(水量平衡方程)

(5)

Q(i+1)t=qit+IBit(关联方程)

(6)

式中：Qit为第i单库第t时段的来水量，m3/s；IBit为第i和第(i+1)单库在第t时段区间来水量，m3/s；ηi为第i单库的出力系数；Δt为时段计算时间，s；T为时段数；R为串联库群系统中单库个数；hit为第i单库第t时段的水头；Nit min、Nit、Nit max为第i单库第t时段的最小容许出力、决策出力、最大容许出力，kW；qit min、qit、qit max为第i单库第t时段的最小容许放水量、决策放水量、最大容许放水量，m3/s；Vit min、Vit、Vit max为第i单库第t时段的最小容许蓄水量、决策蓄水量、最大容许蓄水量，m3。

串联水库群发电优化调度联合最优解并不是简单的各单库最优解相加，不能简单地将各单库计算分割，毗邻单库间不仅具有上下库的出入流关系，同时毗邻单库间的水力关系共同以合力的形式决定了整个水库群的最优解大小，是潜在的一种关联；郑慧涛博士论文中对串联水库群的分解方法也不适合中长期发电优化调度。

大系统分解协调方法以递阶控制形式将大系统分解成若干相对独立的子系统，作为分解级；并用协调器来处理各子系统间关联作用，作为协调级。通过上下级之间反复交换信息，经数次迭代求得各子系统极值，待收敛时可获得整个大系统的最优解[10]。可应用大系统分解协调方法将串联水库群发电优化调度中的单库分解成计算相互独立的子任务，而之间的关联统一由协调器来负责计算。

根据大系统分解协调方法，令μit、λit分别为式(5) 、式(6)的拉格朗日乘子，由式(1)的模型表达式可构造拉格朗日函数为:

(7)

由式(7)可把该串联水库群分解成如下R个单库子系统求解模型：

(8)

其约束条件表达式与串联水库群中长期优化调度模型的一致。

该分解级单库子系统模型以及之后提及的协调级表达式，其原理可参考李爱玲的文献[8]，其中协调级表达式如式(9)、式(10)。

Qk(i+1)t=qkit+IBit

(9)

(10)

大系统分解协调方法应用在串联库群中长期发电优化调度中，使计算耗时大幅度减少。为进一步减少计算耗时，提高计算性能，可以充分利用计算闲置资源。基于大系统分解协调方法，将分解后的单库子系统优化计算作为子任务分配于对应的计算处理单元，为实现粗粒度并行计算奠定了基础，如图1。

图1 串联水库群示意图Fig.1 Diagram of series-connected reservoirs

2.2 并行策略分析

并行计算的基本思想是把求解问题尽量分解成相互独立的子任务，并被分配到对应的计算机处理单元，各自独立计算的时间重叠实现了各子任务的并行处理，再将各子任务的处理结果汇总后得到整个问题解[11]。

分解后的各单库优化计算是相互独立的，可以被分配到各自对应的计算机进行仿真最优化计算，之间的关联由协调级处理。然而正如毛睿提及，由式(9)可知，上库对下库的入流关系是不容改变的，下库需等待上库整个调度周期内下泄流量计算得出后方可计算，每个时间点只有一台计算机处理对应的单库优化计算，各单库无计算时间重叠固然没有实现并行计算。

若将调度周期等分数个时段，下泄流量相对于每个时段都会有对应的值。为实现不同单库计算时间重叠，可以想到是否可以将上库各时段的下泄流量按计算先后顺序依次下传给下库对应时段，下库先得到入流数据的时段可先进行计算，依次直至该库群末库计算完毕。若此方法可行，各单库优化计算时间的重叠便可实现，并行计算模式自然而成。

单库优化调度计算应用动态规划算法[12]时，调度期被等分数个时段，并且每个相邻时段按逆时序依次花一定的时间寻优计算，因此上库各时段的下泄流量似乎可以逆时序先后传给下库，下库可以先计算先获得的下泄流量，最终可实现相邻单库的并行计算，直至末库计算完毕。然而在动态规划算法实际计算过程中，各时段决策变量需在逆推计算结束后再进行回代方可统一获得，那么对于下库仍需要等待上库计算得到整个调度期内的下泄流量后方可计算，各单库计算时间重叠实现又出现困难。有关单库动态规划算法原理可参考文献[12]。

设调度周期被均分成T个时段，在单库的动态规划逆推计算过程中，假设第t时段的初、末库容各有状态离散点M个，那么由此会产生M2个决策变量，而在这第t时段可得到M个较优决策变量并组成集合，占所有决策变量总数的1/M，可以看出M值越大，该集合中决策变量整体精度越高。可设定某规则选取该集合中的某个决策变量作为该时段的最优决策变量，并且所有时段决策变量的选取方法都遵循此规则，例如选定中间号为[M/2]的决策变量，其中[ ]表示取整。各时段决策变量计算时间基本一致，可设定为TN。按此规则在动态规划逆推计算过程中，第i单库各时段的决策变量qit值可以按时间顺序先后依次计算得出，即获得第(t+1)时段放水量qi(t+1)值比相邻的第t时段放水量qit值早TN时间，可将qi(t+1)值先下传于第(i+1)单库计算，不再需要通过回代过程求得各时段最优策略值，以及相应状态值Vit、hit等。毗邻下库的计算时间可不用等待上库TN×T时间，只需等待TN时间方可开始计算，以同等方式，直至末库计算。依此而来各单库最优决策变量计算实现了计算时间重叠，为并行计算模式奠定了坚实的基础，由于毗邻的后库比前库计算开始时间慢一个时段计算时间TN，可命名此新型计算模式为异步并行计算，原理如图2所示,表示为应用大系统分解协调方法下某次迭代过程中串联水库群各单库的并行策略。

3 实例计算与方法验证

3.1 计算模型建立

李仙江是云南省红河的一级支流，本文实例背景是以其具有调节性能的崖羊山、石门坎两座水库作为串联水库群系统，参考数据自1957年开始，调度期为43 a。

在本串联水库群系统中，崖羊山作为上库，来水量Q来自43 a统计的实际数据，石门坎作为下库，来水量Q来自崖羊山的放水量q与他们之间的区间来水量IB之和。每年按月化为12个时段，总共43 a则为43×12个时段。

3.2 异步并行计算方法设计

本实例计算基于多核计算机，开发环境为visio studio 2010，应用C#普通多线程技术控制参与工作的计算机内核数来实现异步并行计算。

将基于标准动态规划方法逆推计算的单库发电优化调度计算模块化，对于崖羊山、石门坎模块主要是输入与输出参数不同，代码构造基本一致，每一时段的最优出力计算时间基本相同，即上述的时间TN，离散点M取值越大计算结果越趋于最优值，但计算成本大幅增加，在本实例中取值为50。在主进程中开启两个子线程，将崖羊山、石门坎两模块分配于两核独立计算，在两模块外的主进程中设置一个43×12的数组，共有43×12个空位分别过渡存储崖羊山各对应时段的出水量qit。对于石门坎的43×12个时段的来水量Q2t时刻监听崖羊山模块中对应时段的q1t。在t时段一旦数组中的q1t由0值转为非空，石门坎由协调级函数Qk2t=qk1t+IB1t即刻取得值Q2t进行计算，实现此t时段与崖羊山(t-1)时段较优出力计算的并行，从而实现异步并行计算。

算出整个系统的解后，将石门坎子系统相关参数传给主进程的协调级函数λk+11t=η2hk2t，算出协调因子传于崖羊山用于第二次迭代计算，如此循环直至大系统目标值收敛。两库部分时段计算的程序流程图如图3所示。

3.3 实例计算结果

在本实例中，由于崖羊山、石门坎水库应用的是标准动态规划算法的逆推计算独立获得各时段的较优决策变量，在应用2.2节中异步并行计算方法的基础上，对于两单库的独立计算，可以将各个时段离散变量的所有组合进行并行处理，应用双重并行计算无疑可以更进一步节省本实例的计算时间。然而离散变量的组合并行计算方法在现今水库群调度研究中比较成熟广泛，且本文研究重点是创新型异步并行计算方法的可行性，因此在本实例的程序设计中，没有在各个时段离散变量的所有组合中应用并行计算方法。

图3 串联水库群发电优化调度分解协调异步并行计算程序流程图Fig.3 The program flow chart of decomposition-coordination asynchronous parallel calculating for optimal power-generation scheduling of series-connected reservoirs

在崖羊山、石门坎水库组成的串联水库群系统发电优化调度中，由表2可知，采用单一的标准动态规划算法求得水库群联合最优发电值所用的时间大致是采用大系统分解协调方法后计算时间的9.56倍。而采用大系统分解协调方法后的最优年平均发电量是采用单一标准动态规划算法的97.9%左右，是偏于理想值5%的可承受范围之内，因此，应用大系统分解协调方法高效求解串联水库群系统发电优化调度最优值是非常可取的。以大系统分解协调方法以及单库标准动态规划算法逆推计算为基础，结合异步并行计算求得系统发电最优解的计算时间约为并行处理之前的60%，最优年平均发电量基本与单一大系统分解协调方法一致，是单一标准动态规划算法的97.69%，亦是偏于理想值5%的可承受范围内，因此结果表明分解协调异步并行计算应用于串联水库群系统发电优化调度中，为明显减少耗时是可行的。在以后的研究中可以进一步证明串联水库数目越多，同时均匀分布于每个处理单元且应用分解协调异步并行计算方法进行计算，耗时减少的会越明显。

表1 不同算法年平均发电量最优值与计算时间Tab.2 The calculating time and optimal value of annual average generating capacity based on different algorithms

4 结 语

本文综述了学者们对水库(群)优化调度计算并行策略研究情况，并指出了在串联水库群中长期发电优化调度中并行策略可做进一步研究的方向。由此作为研究重点提出了基于大系统分解协调方法的异步并行计算。文中最后以李仙江流域部分水库组成串联水库群为例，对分解协调异步并行计算方法做出了相关验证。本文主要目的是提供学者们新型并行策略的基本思想，今后会在混联水库群中长期发电优化调度中[13]，通过实例进一步验证异步并行计算的高效性、实用性，为水库(群)优化调度的并行策略新方法提供一定参考。

□

[1] R Moeini, A Afshar, M H Afshar. Fuzzy rule-based model for hydropower reservoirs operation [J]. International Journal of Electrical Power and Energy Systems, 2011,33(2):171-178.

[2] 郑慧涛.水电站群发电优化调度的并行求解方法研究与应用[D]. 武汉：武汉大学,2013.

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

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

[5] 李 想,魏加华,傅旭东.粗粒度并行遗传算法在水库调度问题中的应用[J].水力发电学报,2012,31(4):28-33.

[6] 陈立华,朱海涛,梅亚东.并行粒子群算法及其在水库群优化调度中应用[J].广西大学学报(自然科学版),2011,36(4):677- 682.

[7] 毛 睿,黄刘生,徐大杰,等.淮河中上游群库联合优化调度算法及并行实现[J].小型微型计算机系统, 2000, 21(6):603- 607.

[8] 李爱玲.水电站水库群系统优化调度的大系统分解协调方法研究[J].水电能源科学,1997,15(4):58-63.

[9] 吴昊,纪昌明,蒋志强,等. 梯级水库群发电优化调度的大系统分解协调模型 [J]. 水力发电学报,2015,34(11):40-50.

[10] Qinghui Zhong, Kevin E. Lansey. Optimal multi-reservoir hydropower operations by decomposition [J]. Engineering Optimization, 1992,19 (2):131-151.

[11] Dias B H, Tomim M A, Marcato A L M, et al. Parallel computing applied to the stochastic dynamic programming for long term operation planning of hydrothermal power systems [J]. European Journal of Operational Research, 2013,229(1):212-222.

[12] 周茜,王丽萍,吴昊,张验科,张璞.基于管道并行动态规划算法的水库发电优化调度[J].中国农村水利水电,2013,(9):151-154.

[13] Omid Bozorg Haddad, Abbas Afshar, Miguel A Marino. Design-operation of multi-hydropower reservoirs: HBMO approach[J]. Water Resources Management, 2008,22(12):1 709-1 722.