水庫(群)發電優化調度計算的并行策略研究

吳 昊，紀昌明，張驗科(華北電力大學可再生能源學院， 北京 102206)

0 引 言

模型構建和算法求解是關于水庫(群)優化調度問題研究的兩個主要方向[1]。水庫群規模至今已逐漸發展成串聯、并聯以及由串并聯組成的混聯模式，構建的優化模型更加復雜與精細，相應優化算法隨之更加計算繁重。隨著并行技術的興起與發展，學者們提出了針對多種優化方法的并行化策略，可進一步提高水庫(群)優化調度計算效率，實現求得滿意最優解和計算耗時較少的雙重目標。

本文以單一水庫、并聯水庫群、串聯水庫群以及混聯水庫群優化調度為背景，較全面綜述了諸多學者在主要傳統求解方法和智能優化方法計算中應用的并行策略及其原理。并行技術有效縮短了復雜的優化計算耗時，然而目前并行策略大都還是基于或改進于傳統求解方法的并行動態規劃和智能優化算法中分解后子群并行性特點。串聯水庫群發電優化調度算法一直是學者們致力研究的重點和難點，一般很難同時兼顧優化解的精度和計算耗時。鄭慧濤[2]的博士論文中，基于水庫群短期發電優化調度模型計算特點，拓展粗粒度并行思維，將混聯水庫群分解成獨立計算的單庫，使具有并聯、串聯關系的各個子水庫優化計算實現并行，在水庫群發電優化調度并行策略研究中有了質的飛越。然而在串聯水庫群中長期發電優化調度中，鄭慧濤博士研究有關出入流關系水庫的并行策略依據準則并不適用。因此是否可以像并聯水庫群一樣，在中長期優化調度中將上下庫具有出入流關系的串聯水庫群分解為獨立計算的單庫子系統，分配于不同的對應的計算單元，實現粗粒度并行計算模式，將是本文致力于研究串聯水庫群創新性并行策略的切入點，文中將此計算模式稱為異步并行計算。

之后以我國西南地區李仙江流域上崖羊山、石門坎水庫組成的串聯水庫群為例，在其中長期發電優化調度中，對分解協調異步并行計算展開了相關論證。本文針對水庫(群)展開并行策略的研究，為復雜水庫群系統在發電、防洪、灌溉等水資源優化調度領域提供了新的研究與應用方向，為人力、物力、財力等資源優化配置提供了一定的理論依據。

1 水庫(群)發電優化調度計算的并行策略研究進展

1.1 并行策略的主要研究方向

在單庫和水庫群發電優化調度中，傳統優化方法主要為動態規劃、線性規劃、非線性規劃、逐次逼近法、逐步優化法等；智能優化方法主要是以遺傳算法、蟻群算法、粒子群算法、模擬退火算法、人工魚群算法、混沌算法以及人工魚群算法等為典型代表。

萬新宇[3]針對水庫發電優化調度，分析了傳統串行動態規劃算法的計算特點，由此建立了主從模式的并行動態規劃模型。李想[4]以經典四水庫問題為例構建多維動態規劃模型，也是基于主從模式的并行動態規劃算法，并成功在高性能并行計算機上進行求解。二位學者的并行策略基本一致，都是基于狀態點相互獨立的并行動態規劃思想，不同之處是前者應用于單庫，后者以簡單的混聯水庫群作為研究對象。

李想[5]針對水庫優化調度采用的是并行遺傳算法中的粗粒度模型，基本思想是將某種群分割成若干個子種群，各子種群在對應不同編號的處理單元上相互獨立地并發執行進化操作，實現計算時間的重疊，經過數次迭代進化，各子種群間會交換部分個體，從而豐富各子種群的多樣性，防止早熟發生，不斷積累優秀基因。陳立華[6]對水庫群優化調度中的粗粒度并行粒子群算法展開研究，其基本思想是參照處理單元的數目把對象粒子群分成數個子群體，并對應分配至每個處理單元，使各處理單元上的子群體能夠獨立搜索最優解，實現計算時間的重疊。可見兩種智能優化算法并行思想的基本點都是將待計算群體分成不相關聯的子群，再分配到不同的計算單元作為子任務處理，實現并行計算。

總之，目前有關發電優化調度的并行策略可歸納為兩大類：在傳統優化算法的并行策略中，最常用的是基于狀態點相互獨立和階段重構的并行動態規劃；而在各種智能優化算法中的并行策略，基本都是將待計算群體分解成不相關聯的子群，分配到不同的計算單元處理，實現并行計算。

以上兩類主要并行策略可適用于單一水庫以及串聯水庫群的優化計算。

對于并聯水庫群優化計算，可以遵循兩種并行思路：第一，對于其中的組成單庫可以應用以上兩類以分解算法計算過程為子任務的并行策略；第二，將各單庫獨立計算體作為不同子任務分配到各自對應的處理單元并行處理，即實現粗粒度并行計算，可將對應不同組成單庫的數臺計算機互聯，作為該并聯水庫群發電優化調度的仿真系統。

若將數臺互聯的獨立計算機對應串聯水庫群中前后毗鄰的各單庫，仿真該串聯水庫群系統，由此可產生是否能實現此串聯水庫群中各單庫獨立計算粗粒度并行化的思考。

針對混聯水庫群，初步思想是將其分解成并聯和串聯子水庫群，再用相應的并行策略解決其優化計算問題。

1.2 串聯水庫群優化計算新型并行策略研究切入點

毛睿[7]根據上下庫無出入流關系特征把混聯水庫群分解出可并聯的數個串聯子水庫群，將各自優化計算作為子任務進行了并行處理。

目前有關串聯水庫群的并行策略大都是圍繞著并行動態規劃和智能算法中并行子群的計算模式，只是在此基礎上改進或進行幾種算法結合，較長時間沒有在串聯水庫群優化調度中實現并行計算的實質性算法創新。直至鄭慧濤在博士論文中對串聯水庫群短期發電優化調度設計出了獨特的并行計算方法。鄭慧濤博士在大規模混聯水庫群短期聯合優化調度模型中并行策略的關鍵點是根據并聯、串聯水庫群特點，遵循單庫間分布特性、單庫間水流傳播特性以及水庫調節性能三原則，對水庫群有效分解成不相關聯獨立計算的單庫子系統，實現優化計算粗粒度并行化。

三原則的詳細內容陳述如下：

(1)依據單庫地理位置分解，例如在不同流域上的單庫之間屬于并聯關系，水流上不存在直接聯系，其特性可體現并行性，因此可以在模擬計算時將隸屬不同流域、河流的單庫進行簡化分解。

(2)依據水流傳播特性分解，因在水庫群短期優化調度問題中，水流傳播時間具有時滯性的特點。若上庫泄流傳播到下庫時間超過了調度期長度，可將預報入流作為下庫的流量輸入條件。由此，單庫之間可進行簡化分解。此分解方式適用于串聯水庫群短期優化調度，但由水流特性可知其明顯不適用于串聯水庫群的中長期優化調度。

(3)依據電站調節性能分解，即上庫具有日調節的特點或是徑流式，而下庫具有季以上中長期調節能力，則上庫時段泄流量相對于下庫的調節庫容來說比較小，對于下庫水位的變化影響也較小，可近似認為下庫水位不會隨上庫的泄流變化而變化，因此下庫可采用預報入流作為入庫流量條件。當單庫之間調節性能滿足上述條件時，可將此水庫群進行簡化分解。根據其特點，此分解方法依舊不適合串聯水庫群中長期優化調度模型。

總結鄭慧濤的博士論文可知，將分解后各單庫計算作為獨立子任務依次分配給不同計算機處理單元，各自可通過優化算法得到求解，可由并行計算提高求解速度。基于劃分與分治思想對水庫群進行并行計算，經模擬計算結果表明該方法可以提供在較短時間內大規模水庫群計算出的短期調度方案，滿足了短期調度的時效性要求。得到各子任務結果后，再歸約合并得到整體水庫群優化調度的最優解。

求串聯水庫群中長期發電優化調度可借鑒鄭慧濤博士分解水庫群實現粗粒度并行計算的基本思想，然而水庫群分解三原則只適合并聯水庫群或是短期優化調度的串聯水庫群。如何分解中長期發電優化調度的串聯水庫群是本文新型并行策略——異步并行計算的切入點，為研究混聯水庫群中長期發電優化調度粗粒度并行計算做出了鋪墊。

串聯水庫群可以被看成一個完整的大系統。李愛玲[8]提出了如何將大系統分解協調方法應用于串聯水庫群中長期發電優化調度模型最優解計算，水庫群中各單庫之間的關聯統一由協調層處理，分解后的各單庫優化計算可以不相關聯獨立進行。吳昊[9]、紀昌明等在此模型基礎上，應用多線程技術實現分解后單庫子系統的并行動態規劃計算，但未實現各單庫的粗粒度并行計算。

在毛睿的文獻[7]中提到，對于并聯水庫群，不管是短期還是中長期優化調度，某個單庫的入流情況不會受到其他單庫出流的影響，因而各單庫調度計算可以實現并行；而在串聯水庫群中長期發電優化調度中，上庫調度方案的變化直接影響下庫的入流，即下庫的入流只有等到上庫對應時段的泄流計算得出后方可計算，即串行計算。目前還沒有在串聯水庫群中長期發電優化調度中，實現以各單庫作為獨立計算體的粗粒度并行計算，即實現各單庫計算時間的重疊。

參照動態規劃將調度期分成數個時間段，入流隨之分成數段，按時間的先后順序入流有先有后，由此考慮到后庫在較早時間段是否可先計算先獲得的入流值，使分解后各單庫實現計算時間重疊，這是本文研究串聯水庫群中長期發電優化調度新型并行策略的關鍵點，為今后混聯水庫群中長期發電優化調度實現粗粒度并行計算模式奠定了研究基礎。

2 串聯水庫群優化計算的新型并行策略

2.1 串聯水庫群中長期發電優化調度的大系統分解協調模型

假設某串聯水庫群由R個以季調節的水庫組成，以整個調度期限內的發電量最大作為該水庫群中長期發電優化調度準則，可建立基本模型為：

(1)

其中約束條件表達式如下：

Vit min≤Vit≤Vit max(蓄水量約束)

(2)

qit min≤qit≤qit max(放水量約束)

(3)

Nit min≤Nit=ηiqithit≤Nit max(出力約束)

(4)

Vi(t+1)=Vit+(Qit-qit)-Δt(水量平衡方程)

(5)

Q(i+1)t=qit+IBit(關聯方程)

(6)

式中：Qit為第i單庫第t時段的來水量，m3/s；IBit為第i和第(i+1)單庫在第t時段區間來水量，m3/s；ηi為第i單庫的出力系數；Δt為時段計算時間，s；T為時段數；R為串聯庫群系統中單庫個數；hit為第i單庫第t時段的水頭；Nit min、Nit、Nit max為第i單庫第t時段的最小容許出力、決策出力、最大容許出力，kW；qit min、qit、qit max為第i單庫第t時段的最小容許放水量、決策放水量、最大容許放水量，m3/s；Vit min、Vit、Vit max為第i單庫第t時段的最小容許蓄水量、決策蓄水量、最大容許蓄水量，m3。

串聯水庫群發電優化調度聯合最優解并不是簡單的各單庫最優解相加，不能簡單地將各單庫計算分割，毗鄰單庫間不僅具有上下庫的出入流關系，同時毗鄰單庫間的水力關系共同以合力的形式決定了整個水庫群的最優解大小，是潛在的一種關聯；鄭慧濤博士論文中對串聯水庫群的分解方法也不適合中長期發電優化調度。

大系統分解協調方法以遞階控制形式將大系統分解成若干相對獨立的子系統，作為分解級；并用協調器來處理各子系統間關聯作用，作為協調級。通過上下級之間反復交換信息，經數次迭代求得各子系統極值，待收斂時可獲得整個大系統的最優解[10]。可應用大系統分解協調方法將串聯水庫群發電優化調度中的單庫分解成計算相互獨立的子任務，而之間的關聯統一由協調器來負責計算。

根據大系統分解協調方法，令μit、λit分別為式(5) 、式(6)的拉格朗日乘子，由式(1)的模型表達式可構造拉格朗日函數為:

(7)

由式(7)可把該串聯水庫群分解成如下R個單庫子系統求解模型：

(8)

其約束條件表達式與串聯水庫群中長期優化調度模型的一致。

該分解級單庫子系統模型以及之后提及的協調級表達式，其原理可參考李愛玲的文獻[8]，其中協調級表達式如式(9)、式(10)。

Qk(i+1)t=qkit+IBit

(9)

(10)

大系統分解協調方法應用在串聯庫群中長期發電優化調度中，使計算耗時大幅度減少。為進一步減少計算耗時，提高計算性能，可以充分利用計算閑置資源。基于大系統分解協調方法，將分解后的單庫子系統優化計算作為子任務分配于對應的計算處理單元，為實現粗粒度并行計算奠定了基礎，如圖1。

圖1 串聯水庫群示意圖Fig.1 Diagram of series-connected reservoirs

2.2 并行策略分析

并行計算的基本思想是把求解問題盡量分解成相互獨立的子任務，并被分配到對應的計算機處理單元，各自獨立計算的時間重疊實現了各子任務的并行處理，再將各子任務的處理結果匯總后得到整個問題解[11]。

分解后的各單庫優化計算是相互獨立的，可以被分配到各自對應的計算機進行仿真最優化計算，之間的關聯由協調級處理。然而正如毛睿提及，由式(9)可知，上庫對下庫的入流關系是不容改變的，下庫需等待上庫整個調度周期內下泄流量計算得出后方可計算，每個時間點只有一臺計算機處理對應的單庫優化計算，各單庫無計算時間重疊固然沒有實現并行計算。

若將調度周期等分數個時段，下泄流量相對于每個時段都會有對應的值。為實現不同單庫計算時間重疊，可以想到是否可以將上庫各時段的下泄流量按計算先后順序依次下傳給下庫對應時段，下庫先得到入流數據的時段可先進行計算，依次直至該庫群末庫計算完畢。若此方法可行，各單庫優化計算時間的重疊便可實現，并行計算模式自然而成。

單庫優化調度計算應用動態規劃算法[12]時，調度期被等分數個時段，并且每個相鄰時段按逆時序依次花一定的時間尋優計算，因此上庫各時段的下泄流量似乎可以逆時序先后傳給下庫，下庫可以先計算先獲得的下泄流量，最終可實現相鄰單庫的并行計算，直至末庫計算完畢。然而在動態規劃算法實際計算過程中，各時段決策變量需在逆推計算結束后再進行回代方可統一獲得，那么對于下庫仍需要等待上庫計算得到整個調度期內的下泄流量后方可計算，各單庫計算時間重疊實現又出現困難。有關單庫動態規劃算法原理可參考文獻[12]。

設調度周期被均分成T個時段，在單庫的動態規劃逆推計算過程中，假設第t時段的初、末庫容各有狀態離散點M個，那么由此會產生M2個決策變量，而在這第t時段可得到M個較優決策變量并組成集合，占所有決策變量總數的1/M，可以看出M值越大，該集合中決策變量整體精度越高。可設定某規則選取該集合中的某個決策變量作為該時段的最優決策變量，并且所有時段決策變量的選取方法都遵循此規則，例如選定中間號為[M/2]的決策變量，其中[ ]表示取整。各時段決策變量計算時間基本一致，可設定為TN。按此規則在動態規劃逆推計算過程中，第i單庫各時段的決策變量qit值可以按時間順序先后依次計算得出，即獲得第(t+1)時段放水量qi(t+1)值比相鄰的第t時段放水量qit值早TN時間，可將qi(t+1)值先下傳于第(i+1)單庫計算，不再需要通過回代過程求得各時段最優策略值，以及相應狀態值Vit、hit等。毗鄰下庫的計算時間可不用等待上庫TN×T時間，只需等待TN時間方可開始計算，以同等方式，直至末庫計算。依此而來各單庫最優決策變量計算實現了計算時間重疊，為并行計算模式奠定了堅實的基礎，由于毗鄰的后庫比前庫計算開始時間慢一個時段計算時間TN，可命名此新型計算模式為異步并行計算，原理如圖2所示,表示為應用大系統分解協調方法下某次迭代過程中串聯水庫群各單庫的并行策略。

3 實例計算與方法驗證

3.1 計算模型建立

李仙江是云南省紅河的一級支流，本文實例背景是以其具有調節性能的崖羊山、石門坎兩座水庫作為串聯水庫群系統，參考數據自1957年開始，調度期為43 a。

在本串聯水庫群系統中，崖羊山作為上庫，來水量Q來自43 a統計的實際數據，石門坎作為下庫，來水量Q來自崖羊山的放水量q與他們之間的區間來水量IB之和。每年按月化為12個時段，總共43 a則為43×12個時段。

3.2 異步并行計算方法設計

本實例計算基于多核計算機，開發環境為visio studio 2010，應用C#普通多線程技術控制參與工作的計算機內核數來實現異步并行計算。

將基于標準動態規劃方法逆推計算的單庫發電優化調度計算模塊化，對于崖羊山、石門坎模塊主要是輸入與輸出參數不同，代碼構造基本一致，每一時段的最優出力計算時間基本相同，即上述的時間TN，離散點M取值越大計算結果越趨于最優值，但計算成本大幅增加，在本實例中取值為50。在主進程中開啟兩個子線程，將崖羊山、石門坎兩模塊分配于兩核獨立計算，在兩模塊外的主進程中設置一個43×12的數組，共有43×12個空位分別過渡存儲崖羊山各對應時段的出水量qit。對于石門坎的43×12個時段的來水量Q2t時刻監聽崖羊山模塊中對應時段的q1t。在t時段一旦數組中的q1t由0值轉為非空，石門坎由協調級函數Qk2t=qk1t+IB1t即刻取得值Q2t進行計算，實現此t時段與崖羊山(t-1)時段較優出力計算的并行，從而實現異步并行計算。

算出整個系統的解后，將石門坎子系統相關參數傳給主進程的協調級函數λk+11t=η2hk2t，算出協調因子傳于崖羊山用于第二次迭代計算，如此循環直至大系統目標值收斂。兩庫部分時段計算的程序流程圖如圖3所示。

3.3 實例計算結果

在本實例中，由于崖羊山、石門坎水庫應用的是標準動態規劃算法的逆推計算獨立獲得各時段的較優決策變量，在應用2.2節中異步并行計算方法的基礎上，對于兩單庫的獨立計算，可以將各個時段離散變量的所有組合進行并行處理，應用雙重并行計算無疑可以更進一步節省本實例的計算時間。然而離散變量的組合并行計算方法在現今水庫群調度研究中比較成熟廣泛，且本文研究重點是創新型異步并行計算方法的可行性，因此在本實例的程序設計中，沒有在各個時段離散變量的所有組合中應用并行計算方法。

圖3 串聯水庫群發電優化調度分解協調異步并行計算程序流程圖Fig.3 The program flow chart of decomposition-coordination asynchronous parallel calculating for optimal power-generation scheduling of series-connected reservoirs

在崖羊山、石門坎水庫組成的串聯水庫群系統發電優化調度中，由表2可知，采用單一的標準動態規劃算法求得水庫群聯合最優發電值所用的時間大致是采用大系統分解協調方法后計算時間的9.56倍。而采用大系統分解協調方法后的最優年平均發電量是采用單一標準動態規劃算法的97.9%左右，是偏于理想值5%的可承受范圍之內，因此，應用大系統分解協調方法高效求解串聯水庫群系統發電優化調度最優值是非常可取的。以大系統分解協調方法以及單庫標準動態規劃算法逆推計算為基礎，結合異步并行計算求得系統發電最優解的計算時間約為并行處理之前的60%，最優年平均發電量基本與單一大系統分解協調方法一致，是單一標準動態規劃算法的97.69%，亦是偏于理想值5%的可承受范圍內，因此結果表明分解協調異步并行計算應用于串聯水庫群系統發電優化調度中，為明顯減少耗時是可行的。在以后的研究中可以進一步證明串聯水庫數目越多，同時均勻分布于每個處理單元且應用分解協調異步并行計算方法進行計算，耗時減少的會越明顯。

表1 不同算法年平均發電量最優值與計算時間Tab.2 The calculating time and optimal value of annual average generating capacity based on different algorithms

4 結 語

本文綜述了學者們對水庫(群)優化調度計算并行策略研究情況，并指出了在串聯水庫群中長期發電優化調度中并行策略可做進一步研究的方向。由此作為研究重點提出了基于大系統分解協調方法的異步并行計算。文中最后以李仙江流域部分水庫組成串聯水庫群為例，對分解協調異步并行計算方法做出了相關驗證。本文主要目的是提供學者們新型并行策略的基本思想，今后會在混聯水庫群中長期發電優化調度中[13]，通過實例進一步驗證異步并行計算的高效性、實用性，為水庫(群)優化調度的并行策略新方法提供一定參考。

□

[1] R Moeini, A Afshar, M H Afshar. Fuzzy rule-based model for hydropower reservoirs operation [J]. International Journal of Electrical Power and Energy Systems, 2011,33(2):171-178.

[2] 鄭慧濤.水電站群發電優化調度的并行求解方法研究與應用[D]. 武漢：武漢大學,2013.

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

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

[5] 李 想,魏加華,傅旭東.粗粒度并行遺傳算法在水庫調度問題中的應用[J].水力發電學報,2012,31(4):28-33.

[6] 陳立華,朱海濤,梅亞東.并行粒子群算法及其在水庫群優化調度中應用[J].廣西大學學報(自然科學版),2011,36(4):677- 682.

[7] 毛 睿,黃劉生,徐大杰,等.淮河中上游群庫聯合優化調度算法及并行實現[J].小型微型計算機系統, 2000, 21(6):603- 607.

[8] 李愛玲.水電站水庫群系統優化調度的大系統分解協調方法研究[J].水電能源科學,1997,15(4):58-63.

[9] 吳昊,紀昌明,蔣志強,等. 梯級水庫群發電優化調度的大系統分解協調模型 [J]. 水力發電學報,2015,34(11):40-50.

[10] Qinghui Zhong, Kevin E. Lansey. Optimal multi-reservoir hydropower operations by decomposition [J]. Engineering Optimization, 1992,19 (2):131-151.

[11] Dias B H, Tomim M A, Marcato A L M, et al. Parallel computing applied to the stochastic dynamic programming for long term operation planning of hydrothermal power systems [J]. European Journal of Operational Research, 2013,229(1):212-222.

[12] 周茜,王麗萍,吳昊,張驗科,張璞.基于管道并行動態規劃算法的水庫發電優化調度[J].中國農村水利水電,2013,(9):151-154.

[13] Omid Bozorg Haddad, Abbas Afshar, Miguel A Marino. Design-operation of multi-hydropower reservoirs: HBMO approach[J]. Water Resources Management, 2008,22(12):1 709-1 722.