動態規劃—禁忌搜索算法在水庫群調度中的應用

宋紫淳 郭瑱祎 張佩

【摘 要】針對水庫群調度這一多約束條件、動態的、非線性的優化問題，引進了動態規劃-禁忌搜索（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算法容易陷入局部最優解的缺點， 使全局搜索優化解的可靠性進一步提高， 且收斂速度快，為水庫優化調度問題求解提供了一個新的方法與思路。

[責任編輯：楊玉潔]