王 森，馬志鵬，李善綜，熊 靜

(1. 珠江水利科學(xué)研究院，廣州 510611；2. 水利部珠江河口動(dòng)力學(xué)及伴生過程調(diào)控重點(diǎn)實(shí)驗(yàn)室，廣州 510611； 3. 水利部珠江水利委員會(huì)技術(shù)咨詢中心，廣州 510611)

梯級水庫群優(yōu)化調(diào)度具有顯著的高維數(shù)、非線性、多階段、約束強(qiáng)耦合等特點(diǎn)，且梯級水庫之間存在復(fù)雜的水力和電力聯(lián)系，優(yōu)化求解非常困難[1]。動(dòng)態(tài)規(guī)劃方法是求解梯級水庫群優(yōu)化調(diào)度問題的經(jīng)典算法之一，能夠有效地克服非線性、非凸性等求解困難。但是，隨著計(jì)算電站數(shù)目的增多，動(dòng)態(tài)規(guī)劃方法的優(yōu)化計(jì)算規(guī)模、占用內(nèi)存及耗時(shí)呈指數(shù)增長，易造成“維數(shù)災(zāi)”問題[2]，甚至可能導(dǎo)致無法求解。為了緩解“維數(shù)災(zāi)”問題，衍生出了多種經(jīng)典的改進(jìn)動(dòng)態(tài)規(guī)劃方法，常用的有離散微分動(dòng)態(tài)規(guī)劃[3]、逐步優(yōu)化[4]、逐次逼近動(dòng)態(tài)規(guī)劃[5]等方法。盡管這些改進(jìn)方法提高了優(yōu)化求解效率，但是求解精度及質(zhì)量相比動(dòng)態(tài)規(guī)劃方法有所下降，更適用于求解規(guī)模較大的梯級水庫群優(yōu)化調(diào)度問題。當(dāng)梯級水庫群的計(jì)算規(guī)模在可計(jì)算范圍內(nèi)時(shí)，動(dòng)態(tài)規(guī)劃仍然是優(yōu)先選擇的計(jì)算方法。因此，如何保證動(dòng)態(tài)規(guī)劃在滿足求解質(zhì)量要求的基礎(chǔ)上提高求解效率，是非常有價(jià)值的研究內(nèi)容。

近年來，隨著計(jì)算機(jī)科學(xué)的高速發(fā)展以及多核硬件配置的廣泛流行，并行技術(shù)已成為提高算法計(jì)算效率的高效手段，并且在許多研究領(lǐng)域中得到成功應(yīng)用[6,7]。同時(shí)，在水庫優(yōu)化調(diào)度領(lǐng)域，并行計(jì)算在動(dòng)態(tài)規(guī)劃方法中的應(yīng)用也已有相關(guān)成果。萬新宇[8]等建立基于主從模式的并行動(dòng)態(tài)規(guī)劃模型，將其運(yùn)用到水布婭水庫的發(fā)電優(yōu)化調(diào)度。李想[9]等構(gòu)建了多維動(dòng)態(tài)規(guī)劃模型，采用主從模式策略對方法進(jìn)行并行化，在高性能計(jì)算機(jī)上測試了四水庫優(yōu)化調(diào)度問題。蔣志強(qiáng)[10]等構(gòu)建了多層嵌套多維動(dòng)態(tài)規(guī)劃并行算法，應(yīng)用于李仙江流域三庫梯級優(yōu)化調(diào)度求解。這些研究成果普遍采用了兼容C++、Python、C#編碼語言的并行框架或工具包，但是目前對動(dòng)態(tài)規(guī)劃并行化研究的成果中，能夠有效兼容Java編碼的并行化方法研究較少。而且，由于開發(fā)人員對不同編程語言的熟悉程度是影響方法并行化實(shí)現(xiàn)方式的關(guān)鍵因素之一，因此，研究Java編碼實(shí)現(xiàn)的動(dòng)態(tài)規(guī)劃并行化方法具有重要的現(xiàn)實(shí)意義。

Fork/Join框架[11]是Java7提供的一種用于并行執(zhí)行任務(wù)的框架，能夠把大任務(wù)分割成若干個(gè)小任務(wù)，最終匯總每個(gè)小任務(wù)結(jié)果后得到大任務(wù)結(jié)果，具有并行效率高、編程易實(shí)現(xiàn)等優(yōu)點(diǎn)，能無縫銜接Java編碼方法的并行化實(shí)現(xiàn)。因此，為了實(shí)現(xiàn)Java編碼的動(dòng)態(tài)規(guī)劃并行化，考慮到動(dòng)態(tài)規(guī)劃通過離散變量尋優(yōu)而具有的天然并行性，本文提出了梯級水庫優(yōu)化調(diào)度并行動(dòng)態(tài)規(guī)劃方法(Parallel Dynamic Programming, PDP)。該方法以調(diào)度期內(nèi)所有離散變量組合的求解計(jì)算作為父任務(wù)，利用Fork/Join多核并行框架將其分解為多個(gè)規(guī)模更小的子任務(wù)進(jìn)行并行化求解。西江干流梯級水庫群長期發(fā)電優(yōu)化調(diào)度應(yīng)用實(shí)例結(jié)果表明，該方法能夠大幅度縮短計(jì)算耗時(shí)，顯著提高計(jì)算效率，是求解梯級水庫群優(yōu)化調(diào)度非常高效的實(shí)用性方法。

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

本文以水庫群發(fā)電量最大為優(yōu)化目標(biāo)，模型描述為：入庫流量過程條件下，考慮水量平衡、水位、泄量等各種約束，兼顧防洪、灌溉、航運(yùn)等綜合要求，制定最優(yōu)調(diào)度決策過程，使調(diào)度期內(nèi)水庫群發(fā)電量最大。模型目標(biāo)函數(shù)及其約束條件如下所示：

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

(1)

約束條件：

水量平衡方程

(2)

蓄水量約束

(3)

發(fā)電流量約束

(4)

出庫流量約束

(5)

出力約束

(6)

始末水位約束

(7)

水電系統(tǒng)總出力約束

(8)

2 并行動(dòng)態(tài)規(guī)劃方法

2.1 動(dòng)態(tài)規(guī)劃方法

動(dòng)態(tài)規(guī)劃方法最早由數(shù)學(xué)家貝爾曼提出，適用于求解多階段序貫決策優(yōu)化問題。該方法將多階段問題轉(zhuǎn)化為多個(gè)單階段問題，逐個(gè)求解并最終返回全局優(yōu)化解，在水庫群優(yōu)化調(diào)度領(lǐng)域得到廣泛應(yīng)用。算法的核心思想可通過遞推公式進(jìn)行描述，見公式(9)。

(9)

式中：t、T分別為時(shí)段序號和時(shí)段數(shù)；St、It、Nt分別為M維(電站個(gè)數(shù))水庫庫容、入庫流量、出力，均為矢量；f*t(St)為時(shí)段t狀態(tài)為St時(shí)，從時(shí)段t到末時(shí)段的系統(tǒng)最大發(fā)電量，億kWh；Bt(St,It,Nt)為時(shí)段t初始蓄水狀態(tài)為St，入庫流量為It，決策出力為Nt時(shí)的本時(shí)段系統(tǒng)發(fā)電量，億kWh；Tt+1(St+1,It,Nt)為時(shí)段t+1到t的狀態(tài)轉(zhuǎn)移方程，通常為水量平衡方程。

2.2 方法并行性

算法的計(jì)算任務(wù)是否能夠分解為多個(gè)規(guī)模更小且獨(dú)立的子任務(wù)是判斷該算法是否具有并行性的必要條件。以計(jì)算時(shí)段為月、調(diào)度周期為1年的2庫梯級水庫群優(yōu)化調(diào)度為例，假設(shè)調(diào)度周期內(nèi)始末水位固定，蓄水狀態(tài)離散個(gè)數(shù)為k，則迭代搜索計(jì)算任務(wù)規(guī)模為k2+10k4+k2，見圖1。

結(jié)合圖1以及式(9)，Bt(St,It,Nt)是遞推公式的主要計(jì)算任務(wù)，其中，在確定性徑流優(yōu)化調(diào)度過程中，僅St為狀態(tài)變量，It為已知條件，Nt通過St狀態(tài)遞推采用以水定電方法可推求，而且St由時(shí)段內(nèi)不同蓄水狀態(tài)離散值構(gòu)成，不同的離散值在Bt(St,It,Nt)中的反饋計(jì)算是相互獨(dú)立的。因此，Bt(St,It,Nt)的計(jì)算任務(wù)具有天然并行性，而且任務(wù)規(guī)模由St變量的離散數(shù)目決定。對于任意一個(gè)M庫梯級水庫群優(yōu)化調(diào)度系統(tǒng)，在調(diào)度周期T內(nèi)的計(jì)算規(guī)?？杀硎緸楣?10)，如下所示：

kM+(T-2)k2M+kM

(10)

通過算法并行化設(shè)計(jì)，DP方法的計(jì)算任務(wù)可平均分配到不同核心同時(shí)計(jì)算，降低算法計(jì)算復(fù)雜度。在p核服務(wù)器中，DP方法復(fù)雜度從O(k2M)縮減到O(k2M/p)。

圖1 DP方法優(yōu)化計(jì)算規(guī)模示意圖Fig.1 Schematic diagram of computational scale of DP

2.3 并行動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)

通過方法并行性分析，DP在迭代優(yōu)化過程中所有離散變量組合在Bt(St,It,Nt)中的求解計(jì)算是相互獨(dú)立可并行的。因此，根據(jù)DP方法迭代特點(diǎn)，可將迭代周期內(nèi)所有變量組合在Bt(St,It,Nt)中的求解計(jì)算作為父任務(wù)，采用細(xì)粒度并行模式實(shí)現(xiàn)DP方法的并行化計(jì)算。本文采用Fork/Join多核并行框架進(jìn)行并行化設(shè)計(jì)，PDP方法詳細(xì)求解步驟如下：

(1)數(shù)據(jù)準(zhǔn)備。獲取計(jì)算所需的電站基礎(chǔ)屬性特征值及特征曲線，包括電站特征水位、出力系數(shù)、水位-庫容曲線、泄流-尾水位曲線等，并根據(jù)水庫各時(shí)段蓄水上下限、離散個(gè)數(shù)確定離散狀態(tài)變量St。

(2)創(chuàng)建線程池，設(shè)置線程池線程數(shù)與CPU配置邏輯線程數(shù)一致。

(3)構(gòu)建并行計(jì)算的父任務(wù)。將迭代周期內(nèi)所有蓄水狀態(tài)變量組合在Bt(St,It,Nt)中的求解計(jì)算作為父任務(wù)，并為計(jì)算過程中水位、出力、發(fā)電量等指標(biāo)創(chuàng)建存儲空間。

(4)設(shè)置Fork/Join計(jì)算閾值，使子任務(wù)分割數(shù)與線程池線程數(shù)一致。

(5)將各子任務(wù)平均分配到子線程中，并調(diào)用Fork/Join多核并行框架計(jì)算各子任務(wù)的返回值。當(dāng)計(jì)算結(jié)束時(shí)，合并各子任務(wù)的解集，返回主線程。

(6)確定最優(yōu)路徑。通過返回的結(jié)果集以及遞推公式，輸出優(yōu)化計(jì)算的最優(yōu)解。

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

3.1 基礎(chǔ)信息

本文以西江干流梯級水庫群優(yōu)化調(diào)度長期發(fā)電量最大模型為測試實(shí)例，測試PDP方法在不同并行環(huán)境下的計(jì)算性能，驗(yàn)證算法的可靠性及效率。目前，西江干流已建電站共7座，其中龍灘、巖灘具有長期調(diào)節(jié)能力，大化、百龍灘、樂灘、橋鞏、長洲電站為日調(diào)節(jié)或徑流式電站。因此，根據(jù)梯級水庫群優(yōu)化調(diào)度特點(diǎn)，參與優(yōu)化搜索的電站為龍灘和巖灘兩座水庫。流域水庫群拓?fù)浣Y(jié)構(gòu)及電站特性參數(shù)分別見圖2和表1。

圖2 流域水庫群拓?fù)浣Y(jié)構(gòu)Fig.2 Topological structure of the cascaded reservoirs

電站/屬性調(diào)節(jié)性能正常高水位/m死水位/m裝機(jī)容量/MW最大過機(jī)流量/(m3·s-1)龍灘年調(diào)節(jié)375．00330．004900．04970巖灘不完全年調(diào)節(jié)223．00212．001210．02600大化日調(diào)節(jié)155．00153．00456．02712百龍灘徑流式126．00125．00192．02580樂灘日調(diào)節(jié)112．00110．00600．03432橋鞏日調(diào)節(jié)84．0082．00456．04920長洲日調(diào)節(jié)20．6018．60630．07428

3.2 配置及指標(biāo)

本次測試采用的配置為Dell Precision WorkStation T1600，CPU類型為Intel(R) Xeon(R) E3-1245@3.30 GHz，核心數(shù)目為4核。另外，測試并行性能的主要指標(biāo)為加速比和效率[12]，其數(shù)學(xué)表達(dá)式見公式(11)和式(12)，如下所示：

Sp=T1/Tp

(11)

Ep=Sp/p

(12)

式中：T1為串行執(zhí)行時(shí)間；Tp為p核環(huán)境下的執(zhí)行時(shí)間。

3.3 方案設(shè)置

本次測試采用庫群平水年入庫徑流作為輸入條件。按蓄水狀態(tài)離散點(diǎn)不同設(shè)置兩個(gè)測試方案，方案1為離散點(diǎn)20，方案2為離散點(diǎn)25，并分別在2核、4核并行環(huán)境下測試算法計(jì)算耗時(shí)、加速比以及效率等指標(biāo)。

3.4 結(jié)果分析

本次測試案例采用的庫群發(fā)電量最大模型以及動(dòng)態(tài)規(guī)劃方法為水庫群優(yōu)化調(diào)度的基礎(chǔ)模型和方法，庫群調(diào)度結(jié)果不再詳細(xì)分析和闡述，重點(diǎn)對方法的并行性能進(jìn)行分析。圖3、圖4、圖5分別為不同仿真方案在不同并行環(huán)境下測試得到的計(jì)算耗時(shí)、加速比及效率。從圖3中可看到，PDP方法計(jì)算耗時(shí)比串行方法有明顯縮減。DP方法(串行計(jì)算)在方案1和方案2中的計(jì)算耗時(shí)分別為343.2、719.6 s，主要原因是由于DP方法的計(jì)算規(guī)模主要由離散點(diǎn)數(shù)決定，方案2計(jì)算規(guī)模大于方案1。PDP方法在4核環(huán)境下方案1和方案2的最大縮減計(jì)算耗時(shí)分別為251.7、532.2 s，并行計(jì)算優(yōu)勢在規(guī)模更大的計(jì)算任務(wù)中更好地得到體現(xiàn)。從圖4中可看到，PDP方法在2核環(huán)境下方案1和方案2的加速比分別為1.91、1.95，在4核環(huán)境下分別為3.75、3.84，在相同并行環(huán)境下，隨著計(jì)算任務(wù)規(guī)模的增加，并行計(jì)算的最優(yōu)加速比逐步提高，且越接近理想加速比，更好地發(fā)揮并行計(jì)算的優(yōu)勢，原因在于相對規(guī)模更大的計(jì)算任務(wù)，線程管理消耗及通信等額外時(shí)間消耗占計(jì)算總耗時(shí)的比例相對較小，線程處于工作運(yùn)行狀態(tài)的時(shí)間更長。從圖5中可看到，PDP方法在2核環(huán)境下方案1和方案2的效率分別為95.5%、97.5%，在4核環(huán)境下分別為93.8%、96.0%，隨著測試環(huán)境核數(shù)的增加，效率逐漸下降，主要原因在于管理消耗以及通信時(shí)間的影響，而且，為了避免數(shù)據(jù)同步錯(cuò)誤的發(fā)生，在各工作線程中消耗了更多緩存來單獨(dú)定義計(jì)算所需要的變量，勢必影響算法總體的并行性能，降低計(jì)算效率。

圖3 各方案PDP方法計(jì)算耗時(shí)Fig.3 Computing time of PDP in diverse cases

圖4 各方案PDP方法加速比Fig.4 Speedup of PDP in diverse cases

圖5 各方案PDP方法效率Fig.5 Efficiency of PDP in diverse cases

4 結(jié) 語

近年來，我國水電事業(yè)發(fā)展迅猛，各大流域逐步形成了大規(guī)模梯級水庫群聯(lián)合調(diào)度格局，精細(xì)化調(diào)度水平亟待提高，尤其是探索高效可行的優(yōu)化求解方法具有重要意義。本文結(jié)合當(dāng)今流行的并行技術(shù)，提出了并行動(dòng)態(tài)規(guī)劃方法的設(shè)計(jì)思路及實(shí)現(xiàn)方式，并以西江干流梯級水庫群優(yōu)化調(diào)度為例，驗(yàn)證了該方法的并行效率，結(jié)果表明，該方法有效可行，能顯著提升算法求解效率，可為其他動(dòng)態(tài)規(guī)劃方法并行化設(shè)計(jì)提供參考和借鑒。但是，由于動(dòng)態(tài)規(guī)劃方法受“維數(shù)災(zāi)”影響，應(yīng)用范圍具有一定局限性，下一步工作將進(jìn)一步開展動(dòng)態(tài)規(guī)劃降維方法及其并行化研究。

□

[1] Labadie J W.Optimal operation of multireservoir systems:State-of-the-art review[J].Journal of Water Resources Planning and Management,2004,130(2):93-111.

[2] 郭生練,陳炯宏,劉 攀,等. 水庫群聯(lián)合優(yōu)化調(diào)度研究進(jìn)展與展望[J]. 水科學(xué)進(jìn)展, 2010,21(4):496-503.

[4] Howson H R, Sancho N G F. New algorithm for solution of multistate dynamic programming problems[J]. Mathematical programming, 1975,8(1):104-116.

[5] Yeh W W, Trott M. Optimization of water resources development: Optimization of capacity specification for components of regional, complex, integrated, multi-purpose water resources systems[M]. Los Angeles: Engineering Rep. No. 7245, Univ. of California, 1972.

[6] 莫?jiǎng)t堯,張愛清,劉青凱,等. 并行算法與并行編程:從個(gè)性、共性到軟件復(fù)用[J]. 中國科學(xué):信息科學(xué), 2016,46(10):1 392-1 410.

[7] 李 娜,王 杰. 大型泵站裝置系統(tǒng)的CFD并行計(jì)算及分析[J]. 中國農(nóng)村水利水電, 2016,35(10):179-181.

[8] 萬新宇,王光謙. 基于并行動(dòng)態(tài)規(guī)劃的水庫發(fā)電優(yōu)化[J]. 水力發(fā)電學(xué)報(bào), 2011,30(6):166-170.

[9] 李 想,魏加華,姚晨晨,等. 基于并行動(dòng)態(tài)規(guī)劃的水庫群優(yōu)化[J]. 清華大學(xué)學(xué)報(bào)自然科學(xué)版, 2013,53(9):1 235-1 240.

[10] 蔣志強(qiáng),紀(jì)昌明,孫 平,等. 多層嵌套動(dòng)態(tài)規(guī)劃并行算法在梯級水庫優(yōu)化調(diào)度中的應(yīng)用[J]. 中國農(nóng)村水利水電, 2014,33(9):70-75.

[11] Lea D. A Java fork/join framework[C]∥ In Proceedings of the ACM 2000 conference on Java Grande. 2000:36-43.

[12] 蔣志強(qiáng),紀(jì)昌明,孫 平,等. 多維動(dòng)態(tài)規(guī)劃三種并行模式的對比分析[J]. 中國農(nóng)村水利水電, 2015,34(3):168-173.