5.2.2　水库（群）中长期发电优化调度模型的求解方法

5.2.2　水库（群）中长期发电优化调度模型的求解方法

5.2.2.1　动态规划法

水电站水库群中长期发电优化调度是一种与时间过程有关的典型动态多阶段决策过程，且一般不考虑水库之间水流时滞的影响，决策具有无后效性。而动态规划法是解决多阶段决策过程最优化问题的一种数学方法，故常用动态规划法求解水库群优化调度问题。用动态规划法求解水库优化调度问题，具有以下优点。

（1）易于确定最优解。

（2）能得到子过程的每一组解，有利于结果分析。

（3）能利用经验，提高求解的效率。

但动态规划法也存在不足之处，在进行数值求解时，随着所求解水库数目的增多，所需的内存成指数增长，进而造成“维数灾”。

1.确定性动态规划法

（1）阶段变量。将调度期分成若干时段，以计算时段作为阶段，时段变量t作为阶段变量。

（2）状态变量。水库调度中，常以时段初的水库水位Zt或蓄水量Vt作为状态变量。在确定性模型中，假定水库的入流过程是已知的，因此用该状态变量描述水库运行过程具有无后效性。

（3）决策变量。取第t时段的电站出力Nt或引用流量Qt为决策变量。

（4）状态转移方程。状态转移方程为水量平衡方程。即：

式中：qt为第t阶段的入库流量，即该时刻的天然来水流量。

（5）目标函数及递推方程。以发电量最大为目标，目标函数为：

递推方程（逆时序递推）：

式中：为从第t时段初水库蓄水量Vt出发，到第T时段的最优总发电量；Et（Vt，Qt）为面临时段t在时段初水库蓄水量为Vt和该时段发电引用流量为Qt时的发电量；为余留时期（从第t+1时段到T时段）的最优总发电量。

（6）边界条件。调度期始末水库库容为死库容，即：

式中：Vd为水库死库容。

（7）单一水库发电优化调度求解步骤。动态规划问题常采用网格法求解，在以纵坐标为水库蓄水量、横坐标为时间的图上，将调节库容分为m等份，时间分为T段，从格点上取值求解递推方程，从中选优，就能得到目标函数的最优解。如图5-6所示。

图5-6　网格图

3）采用上述方法确定（T-2）时段直到第2时段的各时段最大累计发电量。

4）同样方法计算最后时段即第1时段的最大累计发电量。由于本时段初状态只有一个，且已知V1=Vd，故所求的最大累计发电量即为目标函数最优值。

5）根据最优值，进行顺向决策，即可找到最优的调度线及最优出力过程。

由于网格法分格点越多，精度越高，计算工作量也就越大，在应用动态规划法求解优化模型时，常常会产生“维数灾”，因此该方法常用于求解单库的优化调度模型。

2.增量动态规划法

增量动态规划（Incremental Dynamic Planning，I.D.P）是一种改进的动态规划法，由于在不发生弃水的情况下，水头的最优利用反映为水库水位越高越好，随之出力越大。因此可以大致估出最优调度线的近似位置，然后在此近似线上下各取2～3个水位增量（向上算正增量+Δ，向下算负增量-Δ），形成一个策略廊道，并在此廊道中，用动态规划法求得最优调度线。求解步骤如下。

（1）首先根据入库流量过程在水库容许变化范围内，拟定一条初始调度线。

（2）在初始调度线上下，根据索取步长Δl规定某一变化区间±kΔl，k=2～3。

（3）在规定区间内，从调度期末开始，对每一时刻限定的m个状态，逆时序按动态规划法向前递推求水库最优调度线。

（4）若所求最优调度线与初始调度线不完全重合，则不需要改变步长，应以所求调度线作为初始调度线，再按上述步骤重新进行计算；如果所求最优调度线与初始调度线处处重合，说明对于所选步长已不能增优，应以所求调度线作为初始调度线，缩小步长继续进行优化计算。

（5）直至步长已缩小为规定的最小步长Δl时，如果调度线不能再增优，此时的最优调度线即为所求。

相对于动态规划法，增量动态规划法能够更好地拟和水库的初始调度线，用于求解发电量最大模型。

3.逐次逼近动态规划法

逐次逼近算法（Succesive Approximation-Methods of Dynamic Programming，DPSA）的基本思想是把带有若干个决策变量的问题分解成仅仅带有一个决策变量的若干子问题，使这些子问题的优化序列收敛于原问题的解。每个子问题比原来的总问题具有较少的状态变量，从而节省了计算工作量，便于计算机求解。

具有n个水库的梯级水库群发电量最大优化模型的求解步骤如下。

（1）假定各库的初始策略和状态序列。

（2）先对第一个水库进行优化，其余n-1个水库的运行策略和状态变量序列暂时保持不变，相当于对n维决策向量加n-1个约束条件。这样，该子问题只含有一个状态变量和一个决策变量，就可以用一维的优化算法（如POA）求解，从而可得第一个水库的运行策略。

（3）再对第二个水库进行优化，除第一个水库保持新的运行策略外，其余水库仍保持初始策略，用优化算法求解第二个水库的最优运行策略。

（4）用同样的方法对剩下的水库分别进行优化，得到各个水库的新的运行策略。

（5）再从第一个水库开始，重复上述步骤，进行第二轮、第三轮……的迭代计算，直到目标函数不再有改善或前后两轮迭代目标函数值满足收敛要求为止。

DPSA的优点是将n维动态规划问题转化成n个一维子问题，因而其计算工作量只是随维数n成线性增长而不是成指数增长。由此可见，问题的维数越高，该方法所节省的计算工作量越显著。在解决工程实际问题时常将该方法与其他单库优化算法相结合，首先用DPSA将n维问题分解成只有一维的n个子问题，然后用优化算法实现每个子问题的最优化。

4.离散微分动态规划法

离散微分动态规划（Discrete Differential Dynamic Programming，DDDP）法，是用迭代程序求解贝尔曼递推方程的方法。它是由一个满足一系列特定的初始和最终条件的初始试验轨迹开始，并在这个试验轨迹的邻域内（称为“廊道”）将状态离散化，然后在该邻域内用动态规划递推方程，在各离散状态间寻找一个改善轨迹，并以此作为下次迭代的试验轨迹，重复上述计算，逐步缩小“廊道”尺寸。当“廊道”缩小到一定程度，且水电站收益不再增加或运行轨迹的变动范围满足了某收敛准则，则认为得到了满足约束条件的最优轨迹（最优解）。该方法实质上是通过试验状态与决策的迭代以寻求系统的最优目标。

DDDP法将动态规划递推计算限制在一个特定的“廊道”内进行。这个“廊道”比水库状态变量的可行域要小得多，其状态变量离散点一般取3～5个。若将水库群状态变量分为N等份，那么DDDP法迭代计算一次工作量仅相当于直接引用动态规划法计算工作量的[（3～5）/（N+1）]2m。当水库个数较多时，DDDP法将比动态规划法大大节约工作量和存储容量。

在DDDP法中，一般是先假定“试验策略”，即各阶段决策向量的试验序列，它必须是可行的决策向量，然后由试验策略用状态转移方程确定各阶段的状态向量，该状态向量序列称为“试验轨迹”。

在可逆系统中，可以先假设一个可行的试验轨迹，然后根据该轨迹计算出试验策略。为了寻求最优轨迹和最优策略，还须在试验轨迹的周围，按照一定的增量建立一个“状态域”，即“廊道”。该状态域必须满足约束条件，即在各阶段状态空间的可行域内。

在DDDP法中，把“廊道”作为一个可行状态空间，并用递推方程式，按一般动态规划法在这些离散状态域中实施寻优，再反演求得一个相应改善了的轨迹和策略，作为下一次迭代的试验轨迹和试验策略。通过若干次迭代计算，求得一个最大的总效益及其相应的最优轨迹和最优策略。求解步骤如下。

（1）假设一个可行的初始试验轨迹，再由状态转移方程推算出相应的初始试验策略）。与此同时可得相应的目标函数初始值。值得注意的是初始策略和试验轨迹首先必须是可行的，其次是假定得好坏将影响收敛速度。

（2）在状态和决策的可行域内，选取增量ΔVi，t（t=2，…，T，i=1，2，…NM），并按在初始试验轨迹周围形成“廊道”。每次递推计算，就在该次形成的“廊道”区域内进行。例如当M=1和N=3时，就在试验轨迹上、下各取增量ΔVi，t，若只取1个增量时，即形成1个有3个离散值的“廊道”；若各取2个增量时，即形成1个有5个离散值的“廊道”。如果初始和最终时刻的边界条件给定，其增量即等于零（即和在计算过程中保持不变）。一般初始增量选得大些，在迭代过程中逐步减小增量值，直到达到收敛为止。根据经验，每个状态变量选取3～7个增量即可，并宜用奇数。

（3）在“廊道”中，用一般动态规划寻求最大效益Ek（k表示迭代次数），且反演确定相应轨迹{Vk，t}和策略{Qk，t}，称其为改善轨迹和改善策略。

（4）以本次（第k次）迭代所得的改善轨迹替代假设的试验轨迹，并作为下次（第k+1次）迭代的试验轨迹和试验策略。进行重复计算，并对本次迭代和前次迭代所得的试验轨迹进行比较。当其绝对误差小于某一规定值时，则减小增量，在新的试验轨迹周围建立较小的“廊道”。否则，仍采用原来的增量在新的试验轨迹周围建立廊道，重复上述（2）～（4）。

在迭代计算过程中，经第k次迭代后，若出现各时段试验轨迹值变化很小或不再改善时，应由k+1次迭代开始减小增量，然后在新廊道内继续迭代，直到另一次迭代产生如第k次迭代那样的情况，进行同样的处理。增量的递减率采用1/2。

（5）如此不断地迭代计算，直到增量ΔVi，t减小到小于规定值，且前后2次迭代所得的试验轨迹之绝对误差也小于规定值，则结束初始试验策略和初始试验轨迹的迭代，即求得最优策略和最优轨迹，以及最优目标函数值。

DDDP法由于每次迭代计算都局限在所得轨迹为中心的一个邻域内，这样大大减少了参加计算的状态点和可能决策数，减少了内存量并节省了机时。由于动态规划问题中的函数不一定都是凸函数，只从一个初始试验轨迹出发求得的最优解不一定保证是全局最优解，一般需要假定若干个不同的初始试验策略和相应的初始试验轨迹，重复（2）～（5），求得若干相应的最大效益、最优轨迹和最优策略，并选取其中效益最大者为采用值，即为满足约束条件的最优策略和最优轨迹。

5.2.2.2　遗传算法

水库优化调度的遗传算法可表示为在水库水位的允许变化范围内，随机选取POP组可行水位变化序列（Z11，Z12，…，Z1n），（Z21，Z22，…，Z2n），…（ZPOP1，ZPOP2，…，ZPOPn），其中POP为群体规模，n为时段数，再通过一定的编码将其表示为个体的数字串，在满足给定的约束条件下，按预定的适应度评价标准评价水位变化序列的优劣，通过一定的遗传操作（选择、交叉和变异），使适应度低的个体被淘汰，适应度高的个体遗传至下一代，如此反复，直至满足给定的终止规则。遗传算法的终止规则通常有3种：①是否到了预定的进化代数；②是否找到了某个优秀个体；③连续几代的最优目标值是否变化等。对于水库优化调度，第①种规则最为常用。

（1）个体编码。可采用实数编码，把水库在时段t允许的水位变化区间分为m等份，并按从小到大的次序用整数1，2，3，…，m，m+1表示，个体的每一向量（基因）即为水库水位的真值。表示为：

式中：Zt，max、Zt，min分别为时段t水库水位的最大值和最小值；m为控制精度的整数；Nrand为小于m的随机数。

（2）适应度函数。由于水库的优化调度为约束极大值优化问题，因此采用保守估计界限构造法来构造适应度函数。适应值函数表达式为：

式中：f（Z）为目标函数值；c为目标函数界值的保守估计，并且c≥0，cf（Z）≥0。

水库优化调度中约束优化问题的处理，通常采用惩罚函数法。惩罚函数法又分为定量惩罚法、变量罚函法。在定量惩罚法中，解的质量严重地依赖惩罚系数的值。当惩罚系数太小时，算法可能收敛于不可行解；另一方面，惩罚系数太大时，会使算法较早地收敛于某个局部最优解。因此，可采用变量惩罚函数法，公式为：

式中：F（Z）为原优化问题的目标函数值；M为与进化代数有关的惩罚因子；Wi为与第i个约束有关的违约值；p为违约数目。

（3）遗传操作。

1）选择算子。采用GA中最常用的轮盘赌法（又称适应度比例法）对个体进行选择。设群体大小为POP，个体i的适应度为fi，则个体被选中的概率因此个体的适应度越大，被选中的概率越高。2）交叉运算。交叉是把两个父代个体的部分结构加以替换重组而生成新个体的操作，目的是寻找父代双亲已有的但未能合理利用的基因信息。若采用中间交叉策略，设x和y是两父代个体，则交叉产生的后代为x=ax+（1-a）y和y=ay+（1-a）x，a为[0～1]内均匀分布的一个随机数。

3）变异运算。通过变异可引入新的基因以保持种群的多样性，它在一定程度上可以防止成熟前收敛的发生。具体方法为：个体Z的每一个分量Zi（i=0，1，…，n），以概率1/n被选择进行变异。设对变量Zk进行变异，其定义区间为（Zk，min，Zk，max），变异后

式中：Rand为0～1之间的随机数；rand（u）函数表示产生最大值为u的正整数。

4）参数的自适应调整。遗传控制参数中Pc和Pm的选择是影响GA行为和性能的关键所在。构造如下自适应调整函数，使遗传控制参数Pc和Pm随个体适应度大小和群体的分散程度自动调整：

式中：fmax为群体中的最大适应度值；favg为每代群体的平均适应度值；f′为要交叉的两个体中较大的适应度值；f为要变异个体的适应度值；k1、k2、k3、k4均为自适应控制参数，在（0，1）区间取固定值。

由式（5-59）和式（5-60）可以看出，适应度大于群体平均适应度的个体，其Pc和Pm的变化范围分别是[0，k1）和[0，k3）；而适应度低于群体平均适应度的个体，其Pc和Pm分别是k2和k4。同时还可以看出，对于每代种群中的最大个体，其Pc和Pm均为零，保证了当前代中最优个体的模式可以成功进入下一代。

按照式（5-59）和式（5-60）对遗传控制参数Pc和Pm进行自适应调整。另外，为了保证每一代的优良个体不被破坏，采用最优保存策略，使它们直接复制到下一代：

综上所述，算法的步骤如下。

（1）初始化，设置控制参数，产生初始群体。

（2）计算各个体的目标函数，并进行适应度变换。

（3）按轮盘赌选择法对母体进行选择。

（4）按照式（5-61）和式（5-62）计算的Pc和Pm对群体进行交叉、变异和精英选择策略操作，得到新一代群体。

（5）检验是否达到进化代数，若达到，输出最优解，否则转向（2）。

作为一种基于自然选择和群体遗传机理的全局优化搜索方法，遗传算法提供了一条处理复杂优化问题的有效途径。标准遗传算法由于在进化过程中采用恒定的交叉概率和变异概率，使得算法收敛性差并且容易出现早熟现象，因此能否提高算法的收敛速度并且避免早熟是遗传算法在应用中遇到的最大困难。与标准遗传算法相比，自适应遗传算法能够有效地根据个体适应度大小和群体的分散程度自动调整遗传控制参数，从而能够在保持群体多样性的同时，加快收敛速度，提高算法全局收敛的稳定性。

5.2.2.3　模拟退火算法

1982年，Kirkpatrick等将退火思想引入组合优化问题领域，提出一种解大规模组合问题，特别是非线性组合优化问题的有效近似算法——模拟退火算法（Simulated Annealing Algorithms，SAA）。其源于对固体退火过程的模拟，用一组称为冷却进度的参数控制算法的进程，使算法在控制参数T徐徐“降温”并趋于零时，最终求得优化问题的全局或准全局最优解。该算法使用基于概率的双方向随机搜索技术，当基于邻域的一次操作使当前解的质量提高时，模拟退火算法接收这个被改进的解作为新的当前解；在相反的情况下，该算法以一定的概率exp（-ΔC/Te）接收质量较差的解作为当前解。其中，ΔC为邻域操作前后解的质量差，Te为退火过程的控制参数。模拟退火算法已经在理论上证明是一种以概率“1”收敛于全局最优解的全局优化算法，具有较强的局部搜索能力，它能够以随机搜索技术从概率意义上找出目标函数的全局最小点。模拟退火算法的一个重要特征是扰动选择。首先对第k代群体P（k）中的每一个个体Pi进行扰动后，生成新个体：

式中：η为控制扰动大小的比例常数；λ为随机扰动值，服从Cauchy分布；V0为与初始值及取值范围有关的步长值。

然后以概率P接受Pnewi为群体P（k）中第i个个体：

式中：f（i）为个体i的适应度函数值；T为当前模拟退火温度，T（k）=Te/（1+k）。

式（5-64）表明，若是Pi的质量提高，则完全接受其为新个体，否则以一定的概率接受。利用扰动算法对群体进行选择的范围要比基本遗传算法大。模拟退火以一定的概率接受较差的个体，具有优良的选择机制及摆脱局部最优解的能力。

但是，SAA把握搜索过程的总体能力较差，运行效率低。而遗传算法（GA）求解时，容易产生“早熟”、局部寻优能力差的问题。将SAA与GA结合起来，取长补短构成新的优化算法——并行组合模拟退火算法（Parallel Recombination Simulated Annealing Algorithms，PRSAA）。其基本思想是：将模拟退火算法与遗传算法相结合，在模拟退火算法中融入遗传算法群体、交叉、变异操作的概念。

PRSAA在SAA中融入GA的思想，与GA一样，它在求解问题时也是从多个解开始的，然后通过一定的法则，经过多次迭代，最终达到全局或准全局最优解。在水电站优化调度中，水电站运行策略一般用发电引水流量序列（Q1，Q2，…，Qn）来表示，而发电引水流量序列又可以转化为水位变化序列（Z1，Z2，…，Zn）。为方便起见，以水库水位Zt（t=1，2，3，…，T）作为优化变量。对于水电站优化调度的PASAA可理解为：在水库运行水位允许的范围内，随机选取m组水位变化序列（Z11，Z12，…，Z1n），…，（Zm1，Zm2，…，Zmn），受约束条件限制，根据预定的法则，逐步迭代，最终达到最优解。

1.编码与解码

对优化变量Zt采用实数编码。设Zt的取值区间为（Zt，min，Zt，max），Zt，min、Zt，max分别为t时段水库水位允许最大和最小值，欲使变量的精度为δ，则把水库的时段允许水位划分为m等份：

则染色体的基因可用整数n（n=1，2，…，m+1）来表示，它代表水库某一时刻的水位Zt：若优化计算时段为月，那么染色体包含的基因数为12。

2.交叉和变异运算

交叉运算可采用部分离散交叉，变异运算采用非均匀变异。

3.具体算法步骤

（1）随机生成含有M个个体的初始群体P（0），迭代次数k=0。

（2）设置初始温度参数：T←Tmax。

（3）对P（k）中的各个个体进行随机配对，对其中的每一对个体组做如下处理：

1）进行交叉和变异运算，由两个父代个体p1、p2生成两个子代个体c1和c2。

2）对由父代个体和子代个体组成的两个个体组p1和c1、p2和c1，以概率P接受父代个体为下一代群体中的个体，以概率（1-P）接受子代个体为下一代群体中的个体。其中：

式中：Δf为子代个体与父代个体所对应的目标函数之差（在最小化问题中）或父代个体与子代个体所对应的目标函数之差（在最大化问题中），如果有约束条件，上述接受准则中还必须加上对新解的可行性判定。

（4）终止条件判断。若不满足终止条件，则降温，更新温度参数T，k←k+1转向（3）；若满足终止条件，则输出当前最优点，算法结束。

从上述步骤可以看出模拟退火遗传算法依据式（5-67）所描述的Metropolis准则接受子代个体为新的个体，除了接受优化解外，还在一定限度内接受恶化解。随着T的不断减小，接受恶化解的概率不断减小，最后在T趋于零时，就不再接受恶化解。从而使模拟退火遗传算法能从局部最优的“陷阱”中跳出，最后得到最优解。

PRSAA具有以下优点：

（1）由于模拟退火算法具有很强的局部搜索能力，而遗传算法具有把握全局搜索的能力，与其他优化算法相比，该算法能在较短的时间内得到全局近似最优解。

（2）该算法用的是一个相对增量，不需要对目标函数进行变换。

（3）模拟退火算法可应用于多种优化问题，为一个问题编制的程序可以有效地用于其他问题。

（4）PRSAA仅以目标函数搜索为依据，不要求目标函数、约束条件满足连续单调、可微等条件，可用于离散问题和函数关系不明确或难以描述的问题。

5.2.2.4　混沌优化算法

随着混沌优化算法的不断发展，将混沌优化算法运用到水库优化调度中，具有计算简单、计算精度高等优点。

1.混沌优化算法的思路

混沌是非线性系统所独有且广泛存在的一种非周期的运动形式，表现出介于规则和随机之间的一种行为，其现象几乎覆盖了自然科学和社会科学的每一个分支。其具有精致的内在结构，能把系统的运动吸引并束缚在特定的范围内，按其自身规律不重复地遍历所有状态，因此利用混沌变量进行优化搜索无疑能跳出局部最优的羁绊，取得满意的结果。

混沌现象是指由确定方程所描述的系统中的随机现象，有时也称为确定性随机现象，不是杂乱无章、错综复杂的混乱，而是具有精致内在结构的一类现象。混沌性规律的特征有：解对初始值的高度敏感性；相空间的遍历性；系统的内在随机性等。混沌的迭代不重复性和遍历性确定了其快速寻优的可能性。

非线性规划处理的问题是在等式或不等式约束下的某个目标函数，求出最优解。一般表示为：

式中：X∈En，f（x）为目标函数；gi（X）、hj（X）为约束函数，这些函数中至少有一个为非线性函数。约束条件有时用集合形式表示，令S={X|gi（X）≥0，i=1，2，…，m；hj（X）=0，j=1，2，…，l}，称S为可行集或可行域，S中的点称为可行点。

Logistic模型是混沌研究中的最典型模型之一，其方程为：

式中：λ为控制参数，取值0～4，Logistic的映射是[0，1]上的不可逆映射。当λ取值为4时，系统处于混沌状态，任意取初始点，可以得到[0，1]上的遍历的点列。用Logistic方程来生成混沌序列，此序列也叫混沌变量，将其转化成在优化问题解空间中做混沌遍历的变量，通过搜索寻优寻找问题的最优解。

2.混沌优化算法的求解步骤

设式（5-68）中X的维数为M，X=[x1，x2，…，xM′]，xi∈[di，ei]。混沌优化方法求解该问题的基本步骤如下。

（1）算法初始化。置k=1，随机生成M个初值xi，k，令：当其构成的向量X′k∈S时，令X*=X′k，f*=f（X*）否则重复（1）直到获得满足条件的Xk。

（2）置最大迭代步数N，将X1代入式（5-69）迭代生成混沌向量序列{Xk}k=2，3，…，N，将混沌序列按照式（5-70）进行载波，对得到的X′k进行可行性检验，如果通过检验f（X′k）<f（X*），那么X*=Xk1，f*=f（X′k），否则令k=k+1，对X′k+1进行检验，重复（2），直到f（X*）的值只有微小变化或者满足最大迭代次数。

（3）设定循环次数，按照Zk+1=Zk+aZk+1进行二次载波，令Zk=X*，Zk+1为由Logistic映射生成的混沌序列。令α=0.0001×（e′-d′），此问题可以根据具体问题进行设定。

对Zk+1进行检验，如果通过检验f（Zk+1）<f（Zk），那么Zk=Zk+1，f（Zk）=f（Zk+1），否则令k=k+1，重复（3）直到f（Zk）的值满足精度要求，或者满足最大迭代次数。最终的Zk即为所求解，f（Zk）为最优值。

混沌优化算法直接采用混沌变量在允许解空间进行搜索，搜索过程按混沌运动自身规律进行，更容易跳出局部最优解，且搜索效率高。混沌优化算法是一种非常有效的寻优方法，其与遗传算法及其他方法相比具有以下优点。

（1）混沌算法原理明了，计算过程简单，且有很高的精度。

（2）遗传算法在计算过程中存在“早熟现象”，且交叉概率和变异概率的选择对问题的解有很大的影响，而混沌优化算法可以避免这个不足。

（3）通过实例计算，混沌优化算法运行时间优于其他方法，精度较高。将混沌优化算法运用到水库优化调度中可以避免其他方法的不足，提高优化结果的精度，减少运算时间。

5.2.2.5　动态搜索法

5.2.2.6　快速分配法