动态规划—禁忌搜索算法在水库群调度中的应用

宋紫淳 郭瑱祎 张佩

【摘 要】针对水库群调度这一多约束条件、动态的、非线性的优化问题，引进了动态规划-禁忌搜索（DP-TS）算法进行求解。首先利用动态规划（DP）算法求出调度的一组发电流量优化解，其次将DP算法得出的解作为禁忌搜索（TS）算法的初始值，以降低TS算法运行时间和增强其全局寻优的能力。以锦屏一级二滩梯级水库群为例，用上述提出的组合算法进行优化求解，结果表明该法效率高，优化结果良好。

【关键词】动态规划-禁忌搜索算法;水库群调度;优化

0 前言

水库优化调度需要考虑到众多约束条件和实际情况，本文引进了动态规划算法，构成了DP-TS算法，以锦屏一级二滩水库群调度实例模拟算法。

1 水库群优化调度模型

1.1 目标函数

根据发电效益最大的原则，得到目标函数如下式所示：

E=maxAQH△t（1）

注：E为总时间段的发电量;E为第t个时间段水库群的发电量; A是第i个电站的出力系数;Q是第i个电站在第t个时段的平均发电流量;H是第i电站在第t时段的平均发电水头;△t是所计算的时间长度。

1.2 约束条件

（1）库容约束条件

（2）流量约束条件

（3）电站出力约束条件

（4）水量平衡约束条件

1.3 目标函数处理

考虑到保证率的要求，我们加入惩罚项，最终目标函数如下：

F=max{E-Aσ（E-E）}（2）

注：A为惩罚系数;E为保证电量;σ为模型参数，取值规则为：当E≥E时，σ=0;否则σ=1。

2 动态-禁忌搜索算法

2.1 TS算法

TS算法是组合优化算法的一种，以下为TS算法的主要步骤。

Step1：赋予一组初始值集合X（X={X，X，…，X}），計算当下X的目标函数值;

Step2：令当前解集合X和最优解集合X等于X，禁忌表长度l为0;

Step3：构造当前解集合X的邻域，将其作为候选集，在候选集中选一个最佳解X;

Step4：若X比最优解集X更优，令X=X，X=X;

Step5：若X比最优解集X差，且X到X的变化不在禁忌表中，则令X=X;若在禁忌表中，则在候选解中寻找次优解X，并令X=X ，返回Step5;

Step6：将X到X的变化记录到禁忌表末尾， 若禁忌表长度达到最大值， 去掉最头的一个记录;否则禁忌表长度l=l+1;

Step7：满足迭代收敛条件转Step8，否则转Step3;

Step8：满足精度要求， 退出。

2.2 DP-TS 算法

TS算法的初值较为主观，故我们利用DP算法来获取TS算法的初值。我们利用DP算法得出一个优化解X，将此解作为TS算法的初值X，这样便可利用TS算法以利于求解全局最优解的优点，又避开其初始值选取敏感的缺点，得到组合DP-TS算法。

3 实例应用

3.1 锦屏一级二滩水库群概况

锦屏一级水电站位于四川省，装机容量3600MW，保证出力1086MW，多年平均174.1×10kwh，水库正常蓄水位1880m，死水位1800m，正常蓄水位以下库容77.6×10m，调节库容49.1×10m，属年调节水库。二滩水电站水库正常蓄水位1200m，发电最低运行水位1155m，总库容58×10m，调节库容33.7×10m，死水位库容24.2×10m，属季调节水库。电站装机容量3300MW，多年平均发电量168.8×10kwh，保证出力1050MW

3.2 算法设计

DP算法求初始值：

根据上述给出的约束条件，通过获取某典型年的逐月径流情况以及库水位与库容的关系，可以得到用DP算法求出的一个解集串。在这里我们取水位离散点数为50和500，保证率惩罚系数A=5，DP算法主要相关变量设计如下：

（1）阶段变量和状态变量：阶段变量取1月，整个调度期共12个时段，即阶段变量k=1，2，...，12。状态变量取各时段初系统的水位，水库水位在死水位与各时段状态允许最高水位之间连续变化，取水库水位变化△z为一个间隔，相应于该水位的一个状态。状态变量Z=（z， z），表示第k状态初，锦屏一级水库水位处于i状态，二滩水库水位处于j状态。

（2）决策变量和状态转移方程：各阶段，若初状态为Z，末状态为Z，则决策变量出库流量为q=（q，q）。状态转移方程用水量平衡方程，第k阶段，入流为Q=（Q，Q），状态变量为Z，决策变量为q，状态转移方程为：v=v+（S-q）△tv=v+（S+q-q）△t（3）

其中：V、V为初状态Z，末状态Z所对应的库容;S为整个系统的入库流量;Q为锦屏一级的入库流量;Q为锦屏一级与二滩之间的区间流量;q为第k阶段，此始末状态下，锦屏一级水库的出库流量;q为第k阶段，此始末状态下，二滩水库的出库流量。

（3）根据上述变量选取可得到该法下最优解所对应的发电流量解集X={Q，Q，…，Q}。

3.3 DP-TS算法求全局最优解

根据表1中利用DP算法得出的发电流量解集X={Q，Q，…，Q}作为TS算法的初始值X，然后利用上述所介绍的TS算法求出最后最优解，见表1。

3.4 结果分析

在基于DP算法基础上的TS算法由于初值选取较好，因而迭代的次数明显减少，可迅速趋于全局最优解，为便于比较，我们再利用DP算法在水位离散点数分别为500的情况下求解两个水库发电效益，并与在DP算法离散点为50的基础上的DP-TS算法的结果进行比较，结果见表2。

表2 动态规划与组合算法结果比较

从上表可以看出DP算法随着离散点所取数量增多，发电量有着提升，但耗时多，而DP-TS算法只需在DP算法取50离散点的情况下便可与取500离散点时具有获得几乎相当的调度解，且时间消耗与离散点为500的DP算法相比较少。进一步，容易知道当水库群的数量进一步增多时，DP算法会陷入“时间灾”，而组合算法的优点则会突出。

4 结论

分析结果表明， DP-TS算法能够克服DP算法容易陷入局部最优解的缺点， 使全局搜索优化解的可靠性进一步提高， 且收敛速度快，为水库优化调度问题求解提供了一个新的方法与思路。

[责任编辑：杨玉洁]