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

(1. 珠江水利科學研究院，廣州 510611；2. 水利部珠江河口動力學及伴生過程調控重點實驗室，廣州 510611； 3. 水利部珠江水利委員會技術咨詢中心，廣州 510611)

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

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

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

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

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

目標函數(shù)：

(1)

約束條件：

水量平衡方程

(2)

蓄水量約束

(3)

發(fā)電流量約束

(4)

出庫流量約束

(5)

出力約束

(6)

始末水位約束

(7)

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

(8)

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

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

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

(9)

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

2.2 方法并行性

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

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

kM+(T-2)k2M+kM

(10)

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

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

2.3 并行動態(tài)規(guī)劃方法設計

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

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

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

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

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

(5)將各子任務平均分配到子線程中，并調用Fork/Join多核并行框架計算各子任務的返回值。當計算結束時，合并各子任務的解集，返回主線程。

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

3 應用實例

3.1 基礎信息

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

圖2 流域水庫群拓撲結構Fig.2 Topological structure of the cascaded reservoirs

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

3.2 配置及指標

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

Sp=T1/Tp

(11)

Ep=Sp/p

(12)

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

3.3 方案設置

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

3.4 結果分析

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

圖3 各方案PDP方法計算耗時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 結 語

近年來，我國水電事業(yè)發(fā)展迅猛，各大流域逐步形成了大規(guī)模梯級水庫群聯(lián)合調度格局，精細化調度水平亟待提高，尤其是探索高效可行的優(yōu)化求解方法具有重要意義。本文結合當今流行的并行技術，提出了并行動態(tài)規(guī)劃方法的設計思路及實現(xiàn)方式，并以西江干流梯級水庫群優(yōu)化調度為例，驗證了該方法的并行效率，結果表明，該方法有效可行，能顯著提升算法求解效率，可為其他動態(tài)規(guī)劃方法并行化設計提供參考和借鑒。但是，由于動態(tài)規(guī)劃方法受“維數(shù)災”影響，應用范圍具有一定局限性，下一步工作將進一步開展動態(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)化調度研究進展與展望[J]. 水科學進展, 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] 莫則堯,張愛清,劉青凱,等. 并行算法與并行編程:從個性、共性到軟件復用[J]. 中國科學:信息科學, 2016,46(10):1 392-1 410.

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

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

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

[10] 蔣志強,紀昌明,孫 平,等. 多層嵌套動態(tài)規(guī)劃并行算法在梯級水庫優(yōu)化調度中的應用[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] 蔣志強,紀昌明,孫 平,等. 多維動態(tài)規(guī)劃三種并行模式的對比分析[J]. 中國農(nóng)村水利水電, 2015,34(3):168-173.