水庫(群)發(fā)電優(yōu)化調(diào)度計(jì)算的并行策略研究

吳 昊，紀(jì)昌明，張驗(yàn)科(華北電力大學(xué)可再生能源學(xué)院， 北京 102206)

0 引 言

模型構(gòu)建和算法求解是關(guān)于水庫(群)優(yōu)化調(diào)度問題研究的兩個(gè)主要方向[1]。水庫群規(guī)模至今已逐漸發(fā)展成串聯(lián)、并聯(lián)以及由串并聯(lián)組成的混聯(lián)模式，構(gòu)建的優(yōu)化模型更加復(fù)雜與精細(xì)，相應(yīng)優(yōu)化算法隨之更加計(jì)算繁重。隨著并行技術(shù)的興起與發(fā)展，學(xué)者們提出了針對(duì)多種優(yōu)化方法的并行化策略，可進(jìn)一步提高水庫(群)優(yōu)化調(diào)度計(jì)算效率，實(shí)現(xiàn)求得滿意最優(yōu)解和計(jì)算耗時(shí)較少的雙重目標(biāo)。

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

之后以我國西南地區(qū)李仙江流域上崖羊山、石門坎水庫組成的串聯(lián)水庫群為例，在其中長(zhǎng)期發(fā)電優(yōu)化調(diào)度中，對(duì)分解協(xié)調(diào)異步并行計(jì)算展開了相關(guān)論證。本文針對(duì)水庫(群)展開并行策略的研究，為復(fù)雜水庫群系統(tǒng)在發(fā)電、防洪、灌溉等水資源優(yōu)化調(diào)度領(lǐng)域提供了新的研究與應(yīng)用方向，為人力、物力、財(cái)力等資源優(yōu)化配置提供了一定的理論依據(jù)。

1 水庫(群)發(fā)電優(yōu)化調(diào)度計(jì)算的并行策略研究進(jìn)展

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

在單庫和水庫群發(fā)電優(yōu)化調(diào)度中，傳統(tǒng)優(yōu)化方法主要為動(dòng)態(tài)規(guī)劃、線性規(guī)劃、非線性規(guī)劃、逐次逼近法、逐步優(yōu)化法等；智能優(yōu)化方法主要是以遺傳算法、蟻群算法、粒子群算法、模擬退火算法、人工魚群算法、混沌算法以及人工魚群算法等為典型代表。

萬新宇[3]針對(duì)水庫發(fā)電優(yōu)化調(diào)度，分析了傳統(tǒng)串行動(dòng)態(tài)規(guī)劃算法的計(jì)算特點(diǎn)，由此建立了主從模式的并行動(dòng)態(tài)規(guī)劃模型。李想[4]以經(jīng)典四水庫問題為例構(gòu)建多維動(dòng)態(tài)規(guī)劃模型，也是基于主從模式的并行動(dòng)態(tài)規(guī)劃算法，并成功在高性能并行計(jì)算機(jī)上進(jìn)行求解。二位學(xué)者的并行策略基本一致，都是基于狀態(tài)點(diǎn)相互獨(dú)立的并行動(dòng)態(tài)規(guī)劃思想，不同之處是前者應(yīng)用于單庫，后者以簡(jiǎn)單的混聯(lián)水庫群作為研究對(duì)象。

李想[5]針對(duì)水庫優(yōu)化調(diào)度采用的是并行遺傳算法中的粗粒度模型，基本思想是將某種群分割成若干個(gè)子種群，各子種群在對(duì)應(yīng)不同編號(hào)的處理單元上相互獨(dú)立地并發(fā)執(zhí)行進(jìn)化操作，實(shí)現(xiàn)計(jì)算時(shí)間的重疊，經(jīng)過數(shù)次迭代進(jìn)化，各子種群間會(huì)交換部分個(gè)體，從而豐富各子種群的多樣性，防止早熟發(fā)生，不斷積累優(yōu)秀基因。陳立華[6]對(duì)水庫群優(yōu)化調(diào)度中的粗粒度并行粒子群算法展開研究，其基本思想是參照處理單元的數(shù)目把對(duì)象粒子群分成數(shù)個(gè)子群體，并對(duì)應(yīng)分配至每個(gè)處理單元，使各處理單元上的子群體能夠獨(dú)立搜索最優(yōu)解，實(shí)現(xiàn)計(jì)算時(shí)間的重疊?？梢妰煞N智能優(yōu)化算法并行思想的基本點(diǎn)都是將待計(jì)算群體分成不相關(guān)聯(lián)的子群，再分配到不同的計(jì)算單元作為子任務(wù)處理，實(shí)現(xiàn)并行計(jì)算。

總之，目前有關(guān)發(fā)電優(yōu)化調(diào)度的并行策略可歸納為兩大類：在傳統(tǒng)優(yōu)化算法的并行策略中，最常用的是基于狀態(tài)點(diǎn)相互獨(dú)立和階段重構(gòu)的并行動(dòng)態(tài)規(guī)劃；而在各種智能優(yōu)化算法中的并行策略，基本都是將待計(jì)算群體分解成不相關(guān)聯(lián)的子群，分配到不同的計(jì)算單元處理，實(shí)現(xiàn)并行計(jì)算。

以上兩類主要并行策略可適用于單一水庫以及串聯(lián)水庫群的優(yōu)化計(jì)算。

對(duì)于并聯(lián)水庫群優(yōu)化計(jì)算，可以遵循兩種并行思路：第一，對(duì)于其中的組成單庫可以應(yīng)用以上兩類以分解算法計(jì)算過程為子任務(wù)的并行策略；第二，將各單庫獨(dú)立計(jì)算體作為不同子任務(wù)分配到各自對(duì)應(yīng)的處理單元并行處理，即實(shí)現(xiàn)粗粒度并行計(jì)算，可將對(duì)應(yīng)不同組成單庫的數(shù)臺(tái)計(jì)算機(jī)互聯(lián)，作為該并聯(lián)水庫群發(fā)電優(yōu)化調(diào)度的仿真系統(tǒng)。

若將數(shù)臺(tái)互聯(lián)的獨(dú)立計(jì)算機(jī)對(duì)應(yīng)串聯(lián)水庫群中前后毗鄰的各單庫，仿真該串聯(lián)水庫群系統(tǒng)，由此可產(chǎn)生是否能實(shí)現(xiàn)此串聯(lián)水庫群中各單庫獨(dú)立計(jì)算粗粒度并行化的思考。

針對(duì)混聯(lián)水庫群，初步思想是將其分解成并聯(lián)和串聯(lián)子水庫群，再用相應(yīng)的并行策略解決其優(yōu)化計(jì)算問題。

1.2 串聯(lián)水庫群優(yōu)化計(jì)算新型并行策略研究切入點(diǎn)

毛睿[7]根據(jù)上下庫無出入流關(guān)系特征把混聯(lián)水庫群分解出可并聯(lián)的數(shù)個(gè)串聯(lián)子水庫群，將各自優(yōu)化計(jì)算作為子任務(wù)進(jìn)行了并行處理。

目前有關(guān)串聯(lián)水庫群的并行策略大都是圍繞著并行動(dòng)態(tài)規(guī)劃和智能算法中并行子群的計(jì)算模式，只是在此基礎(chǔ)上改進(jìn)或進(jìn)行幾種算法結(jié)合，較長(zhǎng)時(shí)間沒有在串聯(lián)水庫群優(yōu)化調(diào)度中實(shí)現(xiàn)并行計(jì)算的實(shí)質(zhì)性算法創(chuàng)新。直至鄭慧濤在博士論文中對(duì)串聯(lián)水庫群短期發(fā)電優(yōu)化調(diào)度設(shè)計(jì)出了獨(dú)特的并行計(jì)算方法。鄭慧濤博士在大規(guī)?；炻?lián)水庫群短期聯(lián)合優(yōu)化調(diào)度模型中并行策略的關(guān)鍵點(diǎn)是根據(jù)并聯(lián)、串聯(lián)水庫群特點(diǎn)，遵循單庫間分布特性、單庫間水流傳播特性以及水庫調(diào)節(jié)性能三原則，對(duì)水庫群有效分解成不相關(guān)聯(lián)獨(dú)立計(jì)算的單庫子系統(tǒng)，實(shí)現(xiàn)優(yōu)化計(jì)算粗粒度并行化。

三原則的詳細(xì)內(nèi)容陳述如下：

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

(2)依據(jù)水流傳播特性分解，因在水庫群短期優(yōu)化調(diào)度問題中，水流傳播時(shí)間具有時(shí)滯性的特點(diǎn)。若上庫泄流傳播到下庫時(shí)間超過了調(diào)度期長(zhǎng)度，可將預(yù)報(bào)入流作為下庫的流量輸入條件。由此，單庫之間可進(jìn)行簡(jiǎn)化分解。此分解方式適用于串聯(lián)水庫群短期優(yōu)化調(diào)度，但由水流特性可知其明顯不適用于串聯(lián)水庫群的中長(zhǎng)期優(yōu)化調(diào)度。

(3)依據(jù)電站調(diào)節(jié)性能分解，即上庫具有日調(diào)節(jié)的特點(diǎn)或是徑流式，而下庫具有季以上中長(zhǎng)期調(diào)節(jié)能力，則上庫時(shí)段泄流量相對(duì)于下庫的調(diào)節(jié)庫容來說比較小，對(duì)于下庫水位的變化影響也較小，可近似認(rèn)為下庫水位不會(huì)隨上庫的泄流變化而變化，因此下庫可采用預(yù)報(bào)入流作為入庫流量條件。當(dāng)單庫之間調(diào)節(jié)性能滿足上述條件時(shí)，可將此水庫群進(jìn)行簡(jiǎn)化分解。根據(jù)其特點(diǎn)，此分解方法依舊不適合串聯(lián)水庫群中長(zhǎng)期優(yōu)化調(diào)度模型。

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

求串聯(lián)水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度可借鑒鄭慧濤博士分解水庫群實(shí)現(xiàn)粗粒度并行計(jì)算的基本思想，然而水庫群分解三原則只適合并聯(lián)水庫群或是短期優(yōu)化調(diào)度的串聯(lián)水庫群。如何分解中長(zhǎng)期發(fā)電優(yōu)化調(diào)度的串聯(lián)水庫群是本文新型并行策略——異步并行計(jì)算的切入點(diǎn)，為研究混聯(lián)水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度粗粒度并行計(jì)算做出了鋪墊。

串聯(lián)水庫群可以被看成一個(gè)完整的大系統(tǒng)。李愛玲[8]提出了如何將大系統(tǒng)分解協(xié)調(diào)方法應(yīng)用于串聯(lián)水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度模型最優(yōu)解計(jì)算，水庫群中各單庫之間的關(guān)聯(lián)統(tǒng)一由協(xié)調(diào)層處理，分解后的各單庫優(yōu)化計(jì)算可以不相關(guān)聯(lián)獨(dú)立進(jìn)行。吳昊[9]、紀(jì)昌明等在此模型基礎(chǔ)上，應(yīng)用多線程技術(shù)實(shí)現(xiàn)分解后單庫子系統(tǒng)的并行動(dòng)態(tài)規(guī)劃計(jì)算，但未實(shí)現(xiàn)各單庫的粗粒度并行計(jì)算。

在毛睿的文獻(xiàn)[7]中提到，對(duì)于并聯(lián)水庫群，不管是短期還是中長(zhǎng)期優(yōu)化調(diào)度，某個(gè)單庫的入流情況不會(huì)受到其他單庫出流的影響，因而各單庫調(diào)度計(jì)算可以實(shí)現(xiàn)并行；而在串聯(lián)水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度中，上庫調(diào)度方案的變化直接影響下庫的入流，即下庫的入流只有等到上庫對(duì)應(yīng)時(shí)段的泄流計(jì)算得出后方可計(jì)算，即串行計(jì)算。目前還沒有在串聯(lián)水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度中，實(shí)現(xiàn)以各單庫作為獨(dú)立計(jì)算體的粗粒度并行計(jì)算，即實(shí)現(xiàn)各單庫計(jì)算時(shí)間的重疊。

參照動(dòng)態(tài)規(guī)劃將調(diào)度期分成數(shù)個(gè)時(shí)間段，入流隨之分成數(shù)段，按時(shí)間的先后順序入流有先有后，由此考慮到后庫在較早時(shí)間段是否可先計(jì)算先獲得的入流值，使分解后各單庫實(shí)現(xiàn)計(jì)算時(shí)間重疊，這是本文研究串聯(lián)水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度新型并行策略的關(guān)鍵點(diǎn)，為今后混聯(lián)水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度實(shí)現(xiàn)粗粒度并行計(jì)算模式奠定了研究基礎(chǔ)。

2 串聯(lián)水庫群優(yōu)化計(jì)算的新型并行策略

2.1 串聯(lián)水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度的大系統(tǒng)分解協(xié)調(diào)模型

假設(shè)某串聯(lián)水庫群由R個(gè)以季調(diào)節(jié)的水庫組成，以整個(gè)調(diào)度期限內(nèi)的發(fā)電量最大作為該水庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度準(zhǔn)則，可建立基本模型為：

(1)

其中約束條件表達(dá)式如下：

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(關(guān)聯(lián)方程)

(6)

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

串聯(lián)水庫群發(fā)電優(yōu)化調(diào)度聯(lián)合最優(yōu)解并不是簡(jiǎn)單的各單庫最優(yōu)解相加，不能簡(jiǎn)單地將各單庫計(jì)算分割，毗鄰單庫間不僅具有上下庫的出入流關(guān)系，同時(shí)毗鄰單庫間的水力關(guān)系共同以合力的形式?jīng)Q定了整個(gè)水庫群的最優(yōu)解大小，是潛在的一種關(guān)聯(lián)；鄭慧濤博士論文中對(duì)串聯(lián)水庫群的分解方法也不適合中長(zhǎng)期發(fā)電優(yōu)化調(diào)度。

大系統(tǒng)分解協(xié)調(diào)方法以遞階控制形式將大系統(tǒng)分解成若干相對(duì)獨(dú)立的子系統(tǒng)，作為分解級(jí)；并用協(xié)調(diào)器來處理各子系統(tǒng)間關(guān)聯(lián)作用，作為協(xié)調(diào)級(jí)。通過上下級(jí)之間反復(fù)交換信息，經(jīng)數(shù)次迭代求得各子系統(tǒng)極值，待收斂時(shí)可獲得整個(gè)大系統(tǒng)的最優(yōu)解[10]。可應(yīng)用大系統(tǒng)分解協(xié)調(diào)方法將串聯(lián)水庫群發(fā)電優(yōu)化調(diào)度中的單庫分解成計(jì)算相互獨(dú)立的子任務(wù)，而之間的關(guān)聯(lián)統(tǒng)一由協(xié)調(diào)器來負(fù)責(zé)計(jì)算。

根據(jù)大系統(tǒng)分解協(xié)調(diào)方法，令μit、λit分別為式(5) 、式(6)的拉格朗日乘子，由式(1)的模型表達(dá)式可構(gòu)造拉格朗日函數(shù)為:

(7)

由式(7)可把該串聯(lián)水庫群分解成如下R個(gè)單庫子系統(tǒng)求解模型：

(8)

其約束條件表達(dá)式與串聯(lián)水庫群中長(zhǎng)期優(yōu)化調(diào)度模型的一致。

該分解級(jí)單庫子系統(tǒng)模型以及之后提及的協(xié)調(diào)級(jí)表達(dá)式，其原理可參考李愛玲的文獻(xiàn)[8]，其中協(xié)調(diào)級(jí)表達(dá)式如式(9)、式(10)。

Qk(i+1)t=qkit+IBit

(9)

(10)

大系統(tǒng)分解協(xié)調(diào)方法應(yīng)用在串聯(lián)庫群中長(zhǎng)期發(fā)電優(yōu)化調(diào)度中，使計(jì)算耗時(shí)大幅度減少。為進(jìn)一步減少計(jì)算耗時(shí)，提高計(jì)算性能，可以充分利用計(jì)算閑置資源。基于大系統(tǒng)分解協(xié)調(diào)方法，將分解后的單庫子系統(tǒng)優(yōu)化計(jì)算作為子任務(wù)分配于對(duì)應(yīng)的計(jì)算處理單元，為實(shí)現(xiàn)粗粒度并行計(jì)算奠定了基礎(chǔ)，如圖1。

圖1 串聯(lián)水庫群示意圖Fig.1 Diagram of series-connected reservoirs

2.2 并行策略分析

并行計(jì)算的基本思想是把求解問題盡量分解成相互獨(dú)立的子任務(wù)，并被分配到對(duì)應(yīng)的計(jì)算機(jī)處理單元，各自獨(dú)立計(jì)算的時(shí)間重疊實(shí)現(xiàn)了各子任務(wù)的并行處理，再將各子任務(wù)的處理結(jié)果匯總后得到整個(gè)問題解[11]。

分解后的各單庫優(yōu)化計(jì)算是相互獨(dú)立的，可以被分配到各自對(duì)應(yīng)的計(jì)算機(jī)進(jìn)行仿真最優(yōu)化計(jì)算，之間的關(guān)聯(lián)由協(xié)調(diào)級(jí)處理。然而正如毛睿提及，由式(9)可知，上庫對(duì)下庫的入流關(guān)系是不容改變的，下庫需等待上庫整個(gè)調(diào)度周期內(nèi)下泄流量計(jì)算得出后方可計(jì)算，每個(gè)時(shí)間點(diǎn)只有一臺(tái)計(jì)算機(jī)處理對(duì)應(yīng)的單庫優(yōu)化計(jì)算，各單庫無計(jì)算時(shí)間重疊固然沒有實(shí)現(xiàn)并行計(jì)算。

若將調(diào)度周期等分?jǐn)?shù)個(gè)時(shí)段，下泄流量相對(duì)于每個(gè)時(shí)段都會(huì)有對(duì)應(yīng)的值。為實(shí)現(xiàn)不同單庫計(jì)算時(shí)間重疊，可以想到是否可以將上庫各時(shí)段的下泄流量按計(jì)算先后順序依次下傳給下庫對(duì)應(yīng)時(shí)段，下庫先得到入流數(shù)據(jù)的時(shí)段可先進(jìn)行計(jì)算，依次直至該庫群末庫計(jì)算完畢。若此方法可行，各單庫優(yōu)化計(jì)算時(shí)間的重疊便可實(shí)現(xiàn)，并行計(jì)算模式自然而成。

單庫優(yōu)化調(diào)度計(jì)算應(yīng)用動(dòng)態(tài)規(guī)劃算法[12]時(shí)，調(diào)度期被等分?jǐn)?shù)個(gè)時(shí)段，并且每個(gè)相鄰時(shí)段按逆時(shí)序依次花一定的時(shí)間尋優(yōu)計(jì)算，因此上庫各時(shí)段的下泄流量似乎可以逆時(shí)序先后傳給下庫，下庫可以先計(jì)算先獲得的下泄流量，最終可實(shí)現(xiàn)相鄰單庫的并行計(jì)算，直至末庫計(jì)算完畢。然而在動(dòng)態(tài)規(guī)劃算法實(shí)際計(jì)算過程中，各時(shí)段決策變量需在逆推計(jì)算結(jié)束后再進(jìn)行回代方可統(tǒng)一獲得，那么對(duì)于下庫仍需要等待上庫計(jì)算得到整個(gè)調(diào)度期內(nèi)的下泄流量后方可計(jì)算，各單庫計(jì)算時(shí)間重疊實(shí)現(xiàn)又出現(xiàn)困難。有關(guān)單庫動(dòng)態(tài)規(guī)劃算法原理可參考文獻(xiàn)[12]。

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

3 實(shí)例計(jì)算與方法驗(yàn)證

3.1 計(jì)算模型建立

李仙江是云南省紅河的一級(jí)支流，本文實(shí)例背景是以其具有調(diào)節(jié)性能的崖羊山、石門坎兩座水庫作為串聯(lián)水庫群系統(tǒng)，參考數(shù)據(jù)自1957年開始，調(diào)度期為43 a。

在本串聯(lián)水庫群系統(tǒng)中，崖羊山作為上庫，來水量Q來自43 a統(tǒng)計(jì)的實(shí)際數(shù)據(jù)，石門坎作為下庫，來水量Q來自崖羊山的放水量q與他們之間的區(qū)間來水量IB之和。每年按月化為12個(gè)時(shí)段，總共43 a則為43×12個(gè)時(shí)段。

3.2 異步并行計(jì)算方法設(shè)計(jì)

本實(shí)例計(jì)算基于多核計(jì)算機(jī)，開發(fā)環(huán)境為visio studio 2010，應(yīng)用C#普通多線程技術(shù)控制參與工作的計(jì)算機(jī)內(nèi)核數(shù)來實(shí)現(xiàn)異步并行計(jì)算。

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

算出整個(gè)系統(tǒng)的解后，將石門坎子系統(tǒng)相關(guān)參數(shù)傳給主進(jìn)程的協(xié)調(diào)級(jí)函數(shù)λk+11t=η2hk2t，算出協(xié)調(diào)因子傳于崖羊山用于第二次迭代計(jì)算，如此循環(huán)直至大系統(tǒng)目標(biāo)值收斂。兩庫部分時(shí)段計(jì)算的程序流程圖如圖3所示。

3.3 實(shí)例計(jì)算結(jié)果

在本實(shí)例中，由于崖羊山、石門坎水庫應(yīng)用的是標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法的逆推計(jì)算獨(dú)立獲得各時(shí)段的較優(yōu)決策變量，在應(yīng)用2.2節(jié)中異步并行計(jì)算方法的基礎(chǔ)上，對(duì)于兩單庫的獨(dú)立計(jì)算，可以將各個(gè)時(shí)段離散變量的所有組合進(jìn)行并行處理，應(yīng)用雙重并行計(jì)算無疑可以更進(jìn)一步節(jié)省本實(shí)例的計(jì)算時(shí)間。然而離散變量的組合并行計(jì)算方法在現(xiàn)今水庫群調(diào)度研究中比較成熟廣泛，且本文研究重點(diǎn)是創(chuàng)新型異步并行計(jì)算方法的可行性，因此在本實(shí)例的程序設(shè)計(jì)中，沒有在各個(gè)時(shí)段離散變量的所有組合中應(yīng)用并行計(jì)算方法。

圖3 串聯(lián)水庫群發(fā)電優(yōu)化調(diào)度分解協(xié)調(diào)異步并行計(jì)算程序流程圖Fig.3 The program flow chart of decomposition-coordination asynchronous parallel calculating for optimal power-generation scheduling of series-connected reservoirs

在崖羊山、石門坎水庫組成的串聯(lián)水庫群系統(tǒng)發(fā)電優(yōu)化調(diào)度中，由表2可知，采用單一的標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法求得水庫群聯(lián)合最優(yōu)發(fā)電值所用的時(shí)間大致是采用大系統(tǒng)分解協(xié)調(diào)方法后計(jì)算時(shí)間的9.56倍。而采用大系統(tǒng)分解協(xié)調(diào)方法后的最優(yōu)年平均發(fā)電量是采用單一標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法的97.9%左右，是偏于理想值5%的可承受范圍之內(nèi)，因此，應(yīng)用大系統(tǒng)分解協(xié)調(diào)方法高效求解串聯(lián)水庫群系統(tǒng)發(fā)電優(yōu)化調(diào)度最優(yōu)值是非?？扇〉摹Ｒ源笙到y(tǒng)分解協(xié)調(diào)方法以及單庫標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法逆推計(jì)算為基礎(chǔ)，結(jié)合異步并行計(jì)算求得系統(tǒng)發(fā)電最優(yōu)解的計(jì)算時(shí)間約為并行處理之前的60%，最優(yōu)年平均發(fā)電量基本與單一大系統(tǒng)分解協(xié)調(diào)方法一致，是單一標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法的97.69%，亦是偏于理想值5%的可承受范圍內(nèi)，因此結(jié)果表明分解協(xié)調(diào)異步并行計(jì)算應(yīng)用于串聯(lián)水庫群系統(tǒng)發(fā)電優(yōu)化調(diào)度中，為明顯減少耗時(shí)是可行的。在以后的研究中可以進(jìn)一步證明串聯(lián)水庫數(shù)目越多，同時(shí)均勻分布于每個(gè)處理單元且應(yīng)用分解協(xié)調(diào)異步并行計(jì)算方法進(jìn)行計(jì)算，耗時(shí)減少的會(huì)越明顯。

表1 不同算法年平均發(fā)電量最優(yōu)值與計(jì)算時(shí)間Tab.2 The calculating time and optimal value of annual average generating capacity based on different algorithms

4 結(jié) 語

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

□

[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] 鄭慧濤.水電站群發(fā)電優(yōu)化調(diào)度的并行求解方法研究與應(yīng)用[D]. 武漢：武漢大學(xué),2013.

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

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

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

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

[7] 毛 睿,黃劉生,徐大杰,等.淮河中上游群庫聯(lián)合優(yōu)化調(diào)度算法及并行實(shí)現(xiàn)[J].小型微型計(jì)算機(jī)系統(tǒng), 2000, 21(6):603- 607.

[8] 李愛玲.水電站水庫群系統(tǒng)優(yōu)化調(diào)度的大系統(tǒng)分解協(xié)調(diào)方法研究[J].水電能源科學(xué),1997,15(4):58-63.

[9] 吳昊,紀(jì)昌明,蔣志強(qiáng),等. 梯級(jí)水庫群發(fā)電優(yōu)化調(diào)度的大系統(tǒng)分解協(xié)調(diào)模型 [J]. 水力發(fā)電學(xué)報(bào),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] 周茜,王麗萍,吳昊,張驗(yàn)科,張璞.基于管道并行動(dòng)態(tài)規(guī)劃算法的水庫發(fā)電優(yōu)化調(diào)度[J].中國農(nóng)村水利水電,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.