動(dòng)態(tài)規(guī)劃—禁忌搜索算法在水庫(kù)群調(diào)度中的應(yīng)用

宋紫淳 郭瑱祎 張佩

【摘 要】針對(duì)水庫(kù)群調(diào)度這一多約束條件、動(dòng)態(tài)的、非線性的優(yōu)化問(wèn)題，引進(jìn)了動(dòng)態(tài)規(guī)劃-禁忌搜索（DP-TS）算法進(jìn)行求解。首先利用動(dòng)態(tài)規(guī)劃（DP）算法求出調(diào)度的一組發(fā)電流量?jī)?yōu)化解，其次將DP算法得出的解作為禁忌搜索（TS）算法的初始值，以降低TS算法運(yùn)行時(shí)間和增強(qiáng)其全局尋優(yōu)的能力。以錦屏一級(jí)二灘梯級(jí)水庫(kù)群為例，用上述提出的組合算法進(jìn)行優(yōu)化求解，結(jié)果表明該法效率高，優(yōu)化結(jié)果良好。

【關(guān)鍵詞】動(dòng)態(tài)規(guī)劃-禁忌搜索算法;水庫(kù)群調(diào)度;優(yōu)化

0 前言

水庫(kù)優(yōu)化調(diào)度需要考慮到眾多約束條件和實(shí)際情況，本文引進(jìn)了動(dòng)態(tài)規(guī)劃算法，構(gòu)成了DP-TS算法，以錦屏一級(jí)二灘水庫(kù)群調(diào)度實(shí)例模擬算法。

1 水庫(kù)群優(yōu)化調(diào)度模型

1.1 目標(biāo)函數(shù)

根據(jù)發(fā)電效益最大的原則，得到目標(biāo)函數(shù)如下式所示：

E=maxAQH△t（1）

注：E為總時(shí)間段的發(fā)電量;E為第t個(gè)時(shí)間段水庫(kù)群的發(fā)電量; A是第i個(gè)電站的出力系數(shù);Q是第i個(gè)電站在第t個(gè)時(shí)段的平均發(fā)電流量;H是第i電站在第t時(shí)段的平均發(fā)電水頭;△t是所計(jì)算的時(shí)間長(zhǎng)度。

1.2 約束條件

（1）庫(kù)容約束條件

（2）流量約束條件

（3）電站出力約束條件

（4）水量平衡約束條件

1.3 目標(biāo)函數(shù)處理

考慮到保證率的要求，我們加入懲罰項(xiàng)，最終目標(biāo)函數(shù)如下：

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

注：A為懲罰系數(shù);E為保證電量;σ為模型參數(shù)，取值規(guī)則為：當(dāng)E≥E時(shí)，σ=0;否則σ=1。

2 動(dòng)態(tài)-禁忌搜索算法

2.1 TS算法

TS算法是組合優(yōu)化算法的一種，以下為T(mén)S算法的主要步驟。

Step1：賦予一組初始值集合X（X={X，X，…，X}），計(jì)算當(dāng)下X的目標(biāo)函數(shù)值;

Step2：令當(dāng)前解集合X和最優(yōu)解集合X等于X，禁忌表長(zhǎng)度l為0;

Step3：構(gòu)造當(dāng)前解集合X的鄰域，將其作為候選集，在候選集中選一個(gè)最佳解X;

Step4：若X比最優(yōu)解集X更優(yōu)，令X=X，X=X;

Step5：若X比最優(yōu)解集X差，且X到X的變化不在禁忌表中，則令X=X;若在禁忌表中，則在候選解中尋找次優(yōu)解X，并令X=X ，返回Step5;

Step6：將X到X的變化記錄到禁忌表末尾， 若禁忌表長(zhǎng)度達(dá)到最大值， 去掉最頭的一個(gè)記錄;否則禁忌表長(zhǎng)度l=l+1;

Step7：滿(mǎn)足迭代收斂條件轉(zhuǎn)Step8，否則轉(zhuǎn)Step3;

Step8：滿(mǎn)足精度要求， 退出。

2.2 DP-TS 算法

TS算法的初值較為主觀，故我們利用DP算法來(lái)獲取TS算法的初值。我們利用DP算法得出一個(gè)優(yōu)化解X，將此解作為T(mén)S算法的初值X，這樣便可利用TS算法以利于求解全局最優(yōu)解的優(yōu)點(diǎn)，又避開(kāi)其初始值選取敏感的缺點(diǎn)，得到組合DP-TS算法。

3 實(shí)例應(yīng)用

3.1 錦屏一級(jí)二灘水庫(kù)群概況

錦屏一級(jí)水電站位于四川省，裝機(jī)容量3600MW，保證出力1086MW，多年平均174.1×10kwh，水庫(kù)正常蓄水位1880m，死水位1800m，正常蓄水位以下庫(kù)容77.6×10m，調(diào)節(jié)庫(kù)容49.1×10m，屬年調(diào)節(jié)水庫(kù)。二灘水電站水庫(kù)正常蓄水位1200m，發(fā)電最低運(yùn)行水位1155m，總庫(kù)容58×10m，調(diào)節(jié)庫(kù)容33.7×10m，死水位庫(kù)容24.2×10m，屬季調(diào)節(jié)水庫(kù)。電站裝機(jī)容量3300MW，多年平均發(fā)電量168.8×10kwh，保證出力1050MW

3.2 算法設(shè)計(jì)

DP算法求初始值：

根據(jù)上述給出的約束條件，通過(guò)獲取某典型年的逐月徑流情況以及庫(kù)水位與庫(kù)容的關(guān)系，可以得到用DP算法求出的一個(gè)解集串。在這里我們?nèi)∷浑x散點(diǎn)數(shù)為50和500，保證率懲罰系數(shù)A=5，DP算法主要相關(guān)變量設(shè)計(jì)如下：

（1）階段變量和狀態(tài)變量：階段變量取1月，整個(gè)調(diào)度期共12個(gè)時(shí)段，即階段變量k=1，2，...，12。狀態(tài)變量取各時(shí)段初系統(tǒng)的水位，水庫(kù)水位在死水位與各時(shí)段狀態(tài)允許最高水位之間連續(xù)變化，取水庫(kù)水位變化△z為一個(gè)間隔，相應(yīng)于該水位的一個(gè)狀態(tài)。狀態(tài)變量Z=（z， z），表示第k狀態(tài)初，錦屏一級(jí)水庫(kù)水位處于i狀態(tài)，二灘水庫(kù)水位處于j狀態(tài)。

（2）決策變量和狀態(tài)轉(zhuǎn)移方程：各階段，若初狀態(tài)為Z，末狀態(tài)為Z，則決策變量出庫(kù)流量為q=（q，q）。狀態(tài)轉(zhuǎn)移方程用水量平衡方程，第k階段，入流為Q=（Q，Q），狀態(tài)變量為Z，決策變量為q，狀態(tài)轉(zhuǎn)移方程為：v=v+（S-q）△tv=v+（S+q-q）△t（3）

其中：V、V為初狀態(tài)Z，末狀態(tài)Z所對(duì)應(yīng)的庫(kù)容;S為整個(gè)系統(tǒng)的入庫(kù)流量;Q為錦屏一級(jí)的入庫(kù)流量;Q為錦屏一級(jí)與二灘之間的區(qū)間流量;q為第k階段，此始末狀態(tài)下，錦屏一級(jí)水庫(kù)的出庫(kù)流量;q為第k階段，此始末狀態(tài)下，二灘水庫(kù)的出庫(kù)流量。

（3）根據(jù)上述變量選取可得到該法下最優(yōu)解所對(duì)應(yīng)的發(fā)電流量解集X={Q，Q，…，Q}。

3.3 DP-TS算法求全局最優(yōu)解

根據(jù)表1中利用DP算法得出的發(fā)電流量解集X={Q，Q，…，Q}作為T(mén)S算法的初始值X，然后利用上述所介紹的TS算法求出最后最優(yōu)解，見(jiàn)表1。

3.4 結(jié)果分析

在基于DP算法基礎(chǔ)上的TS算法由于初值選取較好，因而迭代的次數(shù)明顯減少，可迅速趨于全局最優(yōu)解，為便于比較，我們?cè)倮肈P算法在水位離散點(diǎn)數(shù)分別為500的情況下求解兩個(gè)水庫(kù)發(fā)電效益，并與在DP算法離散點(diǎn)為50的基礎(chǔ)上的DP-TS算法的結(jié)果進(jìn)行比較，結(jié)果見(jiàn)表2。

表2 動(dòng)態(tài)規(guī)劃與組合算法結(jié)果比較

從上表可以看出DP算法隨著離散點(diǎn)所取數(shù)量增多，發(fā)電量有著提升，但耗時(shí)多，而DP-TS算法只需在DP算法取50離散點(diǎn)的情況下便可與取500離散點(diǎn)時(shí)具有獲得幾乎相當(dāng)?shù)恼{(diào)度解，且時(shí)間消耗與離散點(diǎn)為500的DP算法相比較少。進(jìn)一步，容易知道當(dāng)水庫(kù)群的數(shù)量進(jìn)一步增多時(shí)，DP算法會(huì)陷入“時(shí)間災(zāi)”，而組合算法的優(yōu)點(diǎn)則會(huì)突出。

4 結(jié)論

分析結(jié)果表明， DP-TS算法能夠克服DP算法容易陷入局部最優(yōu)解的缺點(diǎn)， 使全局搜索優(yōu)化解的可靠性進(jìn)一步提高， 且收斂速度快，為水庫(kù)優(yōu)化調(diào)度問(wèn)題求解提供了一個(gè)新的方法與思路。

[責(zé)任編輯：楊玉潔]