梯級水庫群優化調度并行動態規劃方法

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

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

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

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

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

1 庫群優化調度模型

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

目標函數：

(1)

約束條件：

水量平衡方程

(2)

蓄水量約束

(3)

發電流量約束

(4)

出庫流量約束

(5)

出力約束

(6)

始末水位約束

(7)

水電系統總出力約束

(8)

2 并行動態規劃方法

2.1 動態規劃方法

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

(9)

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

2.2 方法并行性

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

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

kM+(T-2)k2M+kM

(10)

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

圖1 DP方法優化計算規模示意圖Fig.1 Schematic diagram of computational scale of DP

2.3 并行動態規劃方法設計

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

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

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

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

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

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

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

3 應用實例

3.1 基礎信息

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

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

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

3.2 配置及指標

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

Sp=T1/Tp

(11)

Ep=Sp/p

(12)

式中：T1為串行執行時間；Tp為p核環境下的執行時間。

3.3 方案設置

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

3.4 結果分析

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

圖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 結 語

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

□

[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] 郭生練,陳炯宏,劉 攀,等. 水庫群聯合優化調度研究進展與展望[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] 李 娜,王 杰. 大型泵站裝置系統的CFD并行計算及分析[J]. 中國農村水利水電, 2016,35(10):179-181.

[8] 萬新宇,王光謙. 基于并行動態規劃的水庫發電優化[J]. 水力發電學報, 2011,30(6):166-170.

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

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