基于状态组合遍历的多维动态规划算法研究

基于状态组合遍历的多维动态规划算法研究

1基于多维动态规划的层级调度优化调度算法随着我国流域梯度开发的加快，分类水库的优化配置研究越来越受到重视。流域梯级水库联合优化运行是一个多变量耦合的复杂非线性规划问题,不仅需要考虑上下游水库之间的水力、电力联系,还需要处理大量的约束问题,具有维度高、耦合性强、不确定性多等特征。目前已有的优化调度方法在求解此类问题时,不仅各种约束条件难以处理,还存在着“维数灾”、早熟收敛等问题。因此,传统的优化调度模型需要进一步寻求更高效的解决方法,以增强算法对梯级水库联合优化调度问题的求解能力。目前,常用的梯级水库优化调度模型求解方法主要有动态规划及其改进方法和智能优化算法两类。动态规划算法是一种多阶段优化算法,具有全局收敛性,目前在单一水库优化调度计算中的应用较为成熟,但“维数灾”问题使其在大型梯级水库优化调度计算中的应用受到很大限制,因此众多学者都致力于降维方法的研究,但研究主要集中在各种动态规划的改进算法上,如离散微分动态规划(DDDP)、逐次逼近法(DPSA)和逐步优化法(POA)以及这些改进方法的组合等,而多维动态规划算法在梯级水库优化调度中的研究应用甚少。动态规划的改进方法虽然在一定程度上有效缓解了梯级水库优化调度中的“维数灾”问题,但作为代价也在一定程度上丧失了动态规划算法所具有的全局收敛性,因此决定了该类算法只能得到模型的近似理论最优值。而对于粒子群算法(PSO)、遗传算法(GA)、差分进化算法(DE)和蚁群算法(ACO)等智能优化算法,虽其可直接应用于处理非线性、非连续、不可导和多维等复杂问题的求解,但这类算法受随机性的影响,其所得的解也往往不是全局最优解。因此,开展多维动态规划方法在梯级水库优化调度问题中的应用研究,以获得该问题的全局最优解对于梯级水库中长期最优调度方案和最优调度规则的制定以及对于其它优化调度方法的最优性检验或优化能力评价有着非常重要的现实意义。本文以李仙江流域三库梯级为研究背景,基于单库动态规划原理,针对梯级水库优化调度模型给出了组合遍历多维动态规划(GroupTraversalDynamicProgramming,GTDP)和多层嵌套多维动态规划(MultilayerNestedDynamicProgramming,MNDP)两种计算模式,并从程序设计复杂度、运行时间和计算机内存占用量等方面对两种多维动态算法进行了对比性分析。2级水库优化配置模型2.1内时段号码及总时段数式中:E为调度期内梯级总发电量;t、T分别为调度时期内时段编号和总时段数;i、n分别为水电站编号和梯级水电站总数,梯级水电站从上游向下游依次编号为1,2,…,n;Nti为第t时段第i个水电站的出力。2.2主要限制条件(1)水量平衡约束(2)其它约束,包括蓄水量约束、下泄流量约束以及出力约束等3多时段蓄水量平衡方程水库调度运行可以看成是一多阶段决策问题,对于一个水库的优化调度问题,用动态规划求解时,可先按照调度期划分为T个离散的时段,因每一个时段末的水库蓄水量是下一时段初的蓄水量,说明各时段初的蓄水量仅与上一个时段末的蓄水量有关,而与其它时段的蓄水量无关,故满足无后效性原则,同时水量平衡方程式:Qt=(Vt-1-Vt)Δt+It,反应了相邻两时段间的蓄水量转换关系,而各时段的效益(出力)只与该时段的来水量It、用水量Qt及初蓄水量Vt-1有关,与其它时段的量无关,且整个调度期的效益是各时段的效益之和,故单库确定性离散动态规划的逆时序计算递归方程可表述如下:对于一个三库梯级系统,若每个水库的状态离散点数均为M,则可知在每个时段初系统有M3个蓄水量组合,仿照单库确定性离散动态规划的逆时序递归思路,可把系统时段初的每一个蓄水量组合作为一个状态,从后向前逐个时段遍历所有蓄水量组合进行逆时序递归计算,最终可得到全调度期效益最优的各时段蓄水量组合。组合遍历多维动态规划算法的逆时序递归方程可表述为:4多层嵌入式结构的多因素动态规划算法4.1库层级系统动态规划求解算法对一个三库梯级系统,上库的每一个下泄流量组合,中下两库动态规划模型都有一个对应的最优解;同样,对于中库的每一个下泄流量组合,下库动态规划模型也都有一个对应的最优解。因此在求解三库梯级动态规划时,可根据多层嵌套的思想,将三库梯级大系统看成是由一个上库单库和一个中下两库子系统组成,而将中下两库子系统又看成是由一个中库单库和一个下库单库组成。经过如此处理,求解三库梯级动态规划就可理解为:对应上库的每一个下泄流量组合嵌套求解一个由中下两库组成的两库梯级动态规划。而求解这个中下两库梯级动态规划又可理解为:对应中库的每一个下泄流量组合嵌套求解一个下库单库动态规划。这样三库梯级动态规划的求解最终也就变成了三个单库动态规划的求解。同理,对于其它多个水库组成的梯级系统,也可以采用相同的方法进行处理。如此,可大大减轻梯级水库动态规划计算中的状态组合数,进而减轻算法设计的复杂度。以三库梯级系统为例,基于多层嵌套结构的梯级水库动态规划算法计算原理可用图1表示。其中TN表示下游子系统对应上游水库一个确定下泄流量组合下的最优总出力。该方法在三库梯级系统的求解过程中,其逆时序递归计算过程与单库动态规划类似,所不同的是上库的最优余留期效益代表的不是上库,而是三库系统的最优余留期效益,中库的最优余留期效益代表的不是中库,而是中下两库系统的最优余留期效益,下库的最优余留期效益则单指下库。各库的逆时序递归方程可表示如下:上库:由式(8)—式(10)最终求出的g1*(V01)即为三库梯级系统在调度期内的最优出力之和。三库梯级动态规划的逆时序递归计算过程可用图2表示。4.2动态规划算法及计算过程(1)对任意时段,例如T-2时段,对于上库蓄水量组合m5-n3,对应时段末蓄水量离散点n3的最优余留期蓄水量过程已知,设为图2中上库的细点虚线所示,其对应有一组下泄流量,由此下泄流量组合加上上库蓄水量组合m5-n3所对应的时段下泄流量对中、下两库系统进行动态规划计算,可得中、下两库对应的最优水位过程,如图2中的中、下库的细点虚线所示,3条虚线所对应的出力加上上库蓄水量组合m5-n3的时段出力即为组合m5-n3所对应的最优梯级余留效益。(2)对于m5所对应的所有时段末蓄水量离散点(n1,n2,…,nM),都以步骤(1)进行计算,从中找出本时段梯级总余留期效益最大的末蓄水量离散点n*,并以此作为本时段初上库蓄水量离散点m5的最优梯级余留期效益所对应的时段末蓄水量点。(3)对于当前时段所有的时段初蓄水量离散点(m1,m2,…,mM),重复步骤(1)、步骤(2),以计算当前时段初所有上库蓄水量离散点mi(i=1,2,…,M)的最优梯级余留期效益值和所对应的时段末蓄水量点,并保存。(4)重复步骤(1)、步骤(2)、步骤(3),对上库所有时段进行逆时序计算,得出所有蓄水量离散点的最优余留期效益信息(余留期效益值、蓄水量点号等)。(5)利用与单库动态规划相似的方法对上库进行顺时序递归计算,得出整个调度期的梯级最优效益、上库最优蓄水量过程、以及上库最优蓄水量过程所对应的下泄流量等信息。(6)以上库最优蓄水量过程所对应的下泄流量加上区间入流作为中库的入流,对中、下两库系统进行两库动态规划计算,计算出各库的出力、出流过程。对于步骤(1)和步骤(6)所提到的两库系统动态规划算法,其计算过程可仿照三库系统动态规划算法的步骤进行。从上述两种动态规划方法对三库梯级系统的优化调度计算过程可以看出,对于GTDP,每个时段3个水库的所有状态点同时进行组合计算,因此计算中每个时段将有6层循环,变量的内存占用量为M3的函数,即随着水库数目的增加其值以指数形式增加。而MNDP是将三库系统分解为3个单库进行嵌套计算,每个水库每个时段只有2层循环,计算程序在各时刻也只执行2层循环,虽然系统总的计算次数因部分计算重复而有所增加,但变量的内存占用量随着水库数目的增加基本保持不变。由此可见,在计算复杂度和内存占用方面,MNDP与GTDP相比具有一定的优势。5使用实例5.1李仙江级数水库水质现状李仙江位于我国云南省境内,属红河水系,为红河一级支流,其干流在中国境内河道长473km,天然落差约1790m,出境处多年平均流量约460m3/s,控制流域面积约19309km2。李仙江干流7座水电站,依次为崖羊山、石门坎、新平寨、龙马、居甫渡、戈兰滩、土卡河。总装机容量148.5万kW。具有调节性能水库的水电站为崖羊山、石门坎和龙马3座水电站,其它均为径流式电站,且位于石门坎和龙马之间的新平寨水电站还未建成,因而李仙江梯级水库的调度方式以崖羊山、石门坎和龙马3座水库的联合调度方式为主体,故本文选取崖羊山、石门坎、龙马3座水库水电站作为研究对象。各电站基本参数见表1。流域长系列径流资料时间为1957—2000年,共43年,其中崖羊山水库多年平均年径流量为121.7m3/s,石门坎水库多年平均年区间径流量为5.5m3/s,龙马水库多年平均年区间径流量为63.2m3/s。分别选取43年径流资料中的1966、1990和1988作为丰水年、平水年和枯水年以用于优化调度计算。5.2模型求解过程以丰、平、枯3个典型年的径流数据为基础,在不同的状态离散数下,分别利用组合遍历多维动态规划算法(GTDP)和多层嵌套多维动态规划算法(MNDP)进行三库梯级系统调度期总发电量最大模型(无梯级保证出力约束)的求解计算,所得结果见表2所示。以枯水年径流数据为例,在三库梯级优化调度模型的求解过程中,随着水库状态离散点数的增加,两种方法的程序进程所占内存变化情况如图3所示,运行时间变化情况如图4所示。表3给出了MNDP、GTDP及POA在5、10、15、20四种离散数情况下的发电量和计算时间,其中POA的初始解通过常规联合调度获得,其最大迭代次数为500,收敛精度为0.0001。同时表3还给出了遗传算法(GA)在初始种群数为100、最大迭代次数为500、交叉率为0.8、变异率为0.05、收敛精度为0.0001时的计算结果。5.3mtndp和gtdp的比较由表2可以看出,对于丰、平、枯3个典型年,两种方法在不同离散数下的计算结果完全一致,说明了算法设计的正确合理性。同时由表2还可以看出,有的典型年部分离散点数小的发电量反而比离散点数大的发电量要高,例如平水年离散点数为10的发电量为22.6734亿kW·h,但离散点数为15的发电量为22.6723亿kW·h,减少0.0011亿kW·h;同样对于枯水年离散点数为15的发电量为18.9243亿kW·h,但离散点数为20的发电量为18.9203亿kW·h,减少0.004亿kW·h。该现象是由于状态离散点的非倍数增加而引起的。由平水年四种离散情况下的结果可以看出,其发电量最优的离散点取值是10倍数,因此离散点数为15时是不能获得最优点的;同样,对于枯水年,发电量最优的离散点是15倍数,因此离散点数为20时也是不能获得最优点的;而对于丰水年,年发电量最优的离散点是5倍数,因此4种离散情况下发电量均相同。由图3可以看出,对于一个三库梯级系统优化调度模型,在状态离散点数较小时(小于50),GT-DP和MNDP两种方法的内存占用量都基本保持不变,且两者相差很小。但随着水库状态离散点数的继续增加(大于50),GTDP方法的内存占用量则迅速上升,当离散点数达到190时,其计算内存占用量已经超过了13000M,而MNDP方法则仍保持不变。只有当状态离散点数非常大(十万、百万)时,MNDP方法的内存占用量才有所增加,但其递增速度也远远不及GTDP。由此可见MNDP方法在较少内存占用方面与GTDP方法相比具有极其显著的优势,特别是对于水库个数多、状态离散点数大的情况。可以说在任何一台能够实现单库动态规划的普通电脑上都能够通过MNDP而实现任何水库个数的梯级系统优化调度计算。MNDP方法通过嵌套结构求解模式使其在较少内存占用方面具有显著的优势,但其运行时间却因部分计算的重复而有很大程度的增加,这点可以从图4看出。在状态离散点数很小时(等于5),GTDP和MNDP两种方法的运行时间基本一样,且两者的值都很小。但随着水库状态离散点数的增加,MNDP方法的运行时间则迅速增加,当离散点数为20时,其运行时间已经达到了1200min;而GTDP方法随着水库状态离散点数的增加其运行时间虽然也以较快的速度增加,但其递增速度要比MNDP方法小很多,当离散点数为20时,其运行时间仅为200min左右。由此可见,在运行时间上GTDP方法是优于MNDP方法的,而且对于水库规模小、离散点数不大的情况,GTDP和MNDP两种方法的内存占用量基本一样,因此此时采取GTDP方法更为合适。由表3可以看出在不同的离散数下,虽然POA的计算时间优于MNDP和GTDP的计算时间,但其发电量与MNDP和GTDP的结果相比均偏小。而与GA相比,MNDP和GTDP在不同离散数情况下的发电量均优于GA,且在离散数较小时,GTDP的计算时间也有一定的优势,但MNDP以及离散数较大时的GTDP其计算时间均比GA的计算时间要长,这说明了MNDP和GTDP算法在全局收敛方面所具有的优势和在离散数较大时计算时间上的不足。通过前面的分析可以看出,MNDP方法在减少内存占用方面有很大优势,但其实质是以运行时间的延长为代价换取内存空间占用量的缩减,运行时间长的缺陷会在很大程度上限制其推广应用。若是能在内存空间占用量减少的同时也缩短其运行时间,那么MNDP方法就可以在程序复杂度、内存占用以及运行时间3个方面来缓解多维动态规划算法的维数灾问题,从而实现其在梯级水库优化调度中的有效运用。而现行的并行计算为解决该问题提供