陳 佳,章漢軍,徐 囡

(1.諸暨市水利局,浙江 紹興 311800;2.紹興市柯橋區(qū)浙光中學(xué),浙江 紹興 312025)

動態(tài)規(guī)劃(DP)是解決多階段決策問題的經(jīng)典方法,在水庫調(diào)度領(lǐng)域獲得了廣泛應(yīng)用[1-3]。受“維數(shù)災(zāi)”[4]限制,在當(dāng)前計算能力下,DP難以直接應(yīng)用于3個水庫以上規(guī)模水庫群聯(lián)合優(yōu)化。為了緩解DP的“維數(shù)災(zāi)”效應(yīng),研究人員提出了一系列降維技術(shù),這些技術(shù)分為以提高計算效率為目的的并行計算技術(shù)[5-6]和以減少計算工作量為目的的改進型DP[7-10]2類。并行計算的優(yōu)勢在于能夠提高計算資源使用率,尤其是有助于發(fā)掘多核處理器的計算潛能。但是,并行計算的本質(zhì)是以空間資源換取時間,因計算工作量并未減少,隨著問題規(guī)模增大,DP的計算成本仍然難以承受。改進型DP主要從4個方面減少DP計算工作量。①利用實際問題的數(shù)學(xué)特性減少計算工作量。如趙銅鐵鋼等[1]基于水庫狀態(tài)變量與決策變量之間的單調(diào)關(guān)系,提出2種DP改進型,避免了冗余計算;ZENG等[11]利用時段初并聯(lián)水庫系統(tǒng)總可用水量與時段末水庫最優(yōu)蓄水量之間的單調(diào)關(guān)系,對DP進行改進,精簡了DP計算過程。②通過規(guī)避重復(fù)計算或者無效計算減少計算工作量。如紀(jì)昌明等[2]通過構(gòu)建水電站出力泛函模型,精簡了DP計算步驟,提高了計算效率;紀(jì)昌明等[12]通過構(gòu)建可行域搜索映射模型,規(guī)避了無效狀態(tài)組合計算,縮減了DP計算時間。③采用抽樣技術(shù)減少計算工作量。如馮仲愷等[13]使用試驗設(shè)計表在水庫狀態(tài)空間中進行抽樣,避免了水庫全狀態(tài)組合引起的“維數(shù)”問題;HE等[14]將重要性采樣技術(shù)應(yīng)用于梯級水庫蓄水調(diào)度,緩解了DP“維數(shù)災(zāi)”效應(yīng)。④對解空間進行分解,采用逐次逼近策略減少計算工作量。此類算法以離散微分動態(tài)規(guī)劃(DDDP)[7]、動態(tài)規(guī)劃逐次逼近(DPSA)[8]和逐步優(yōu)化算法(POA)[9]為代表。DDDP將大范圍的解空間分解為一連串重疊的小范圍子空間,每次在1個子空間內(nèi)應(yīng)用DP尋優(yōu),并利用子空間的重疊性不斷向相鄰子空間滲透,進而實現(xiàn)對整個解空間的探索。DPSA和POA采用變量解耦策略,將高維解空間分解為若干低維子空間,通過在不同子空間內(nèi)輪流搜索,逼近問題的解。

DPSA是一種“空間降維”方法。該方法首先通過對變量實施解耦,將水庫群優(yōu)化問題分解為一系列單庫優(yōu)化問題;然后自上而下進行逐庫優(yōu)化(每次僅對1座水庫的蓄水軌線進行優(yōu)化,同時固定其余水庫的蓄水軌線);最后通過迭代,收斂于問題的解。DPSA最大的優(yōu)勢在于其計算工作量隨水庫數(shù)量呈線性增長,有效緩解了DP的“維數(shù)”問題。但是,DPSA的變量解耦策略難以有效處理梯級水庫之間復(fù)雜的水力耦合關(guān)系。在梯級水庫系統(tǒng)中,上、下游水庫之間存在強水力耦合關(guān)系,這一關(guān)系增加了梯級水庫聯(lián)合優(yōu)化問題的復(fù)雜性,主要體現(xiàn)在:①上游水庫的放水構(gòu)成下游水庫入流的一部分,下游水庫最優(yōu)蓄泄方案由上游水庫的蓄泄方案確定;②下游水庫的蓄泄方案又反過來作用于上游水庫的決策空間,影響上游水庫的最優(yōu)蓄泄方案。由于上述耦合關(guān)系的存在,在梯級水庫聯(lián)合優(yōu)化中采用DPSA變量解耦策略,當(dāng)搜索至約束邊界上時容易出現(xiàn)“停滯不前”問題,影響解的質(zhì)量。有關(guān)該問題的詳細論證見下一節(jié)“1算法實證分析”。

POA是一種“時間降維”方法。該方法采用靜態(tài)變量解耦策略,將多階段問題分解為若干兩階段問題,通過連續(xù)、重復(fù)地求解兩階段問題,逼近多階段問題的解。已有文獻證明,對于凸問題,POA能夠收斂于全局最優(yōu)解。但是,實際水庫優(yōu)化問題往往具有“非凸”特征,對于“非凸”問題,POA的降維是以犧牲解的質(zhì)量作為代價?？偟膩碚f,POA有2個方面的局限性:①搜索的盲目性影響解的質(zhì)量,算法僅在少量固定的子空間中輪流搜索,不對變量進行比較、評價;②“維數(shù)”問題影響求解效率。POA兩階段問題計算工作量隨水庫數(shù)量呈指數(shù)增長,存在“維數(shù)障礙”[15]。為了提升POA的性能,研究人員提出了一系列POA改進型。這些改進主要圍繞上述2個方面展開。圍繞第1方面的改進主要有:廖勝利等[16]針對POA搜索至約束邊界上易陷入局部最優(yōu)解問題,提出了一種沿目標(biāo)函數(shù)等值線向可行域內(nèi)部移動的策略;CHENG等[17]設(shè)計了一種多步POA,通過多次應(yīng)用POA對4、8、16、96個時段的水庫群優(yōu)化問題進行求解(當(dāng)前問題的最優(yōu)解作為下一問題的初始解),提高了POA解的質(zhì)量;黃草等[18]引入“優(yōu)化窗口”和“滑動距離”概念,將POA兩階段優(yōu)化和單步移動擴展為多階段優(yōu)化和多步移動;肖勝賢等[19]針對坐標(biāo)輪換法求解POA兩階段問題搜索至約束邊界上“停滯不前”問題,提出了一種等約束滑行策略;張誠等[20]在文獻[18]的基礎(chǔ)上設(shè)計了一種變階段POA,將POA兩階段模式拓展到多階段模式;JI等[21]考慮河道水流傳播對梯級水庫短期調(diào)度的影響,對POA兩階段效益函數(shù)進行改進,設(shè)計了一種嵌套POA。圍繞第2方面的改進主要有:MA等[22]采用智能算法求解POA兩階段問題,避免了水庫全狀態(tài)組合引起的“維數(shù)”問題;李義等[23]采用坐標(biāo)輪換法求解POA兩階段問題,減少了POA一次尋優(yōu)的變量數(shù);胡挺等[24]將DDDP“廊道”技術(shù)引進POA兩階段問題求解,減少了POA一次尋優(yōu)的狀態(tài)數(shù);馮仲愷等[25]將試驗設(shè)計引進POA兩階段問題求解,緩解了POA“維數(shù)”問題;趙志鵬等[26]采用離散梯度下降法求解POA兩階段問題,減少了POA計算工作量;FENG等[15]采用Nelder-Mead單純形方法求解POA兩階段問題,減輕了POA計算負擔(dān)。此外,CHEN[27]針對POA相鄰時段水量分配機制的不足,對POA兩階段效益函數(shù)進行改進,設(shè)計了一種跨時段水量分配機制,并采用DP求解兩階段問題,提高了POA解的質(zhì)量和求解效率。雖然通過不同的改進措施,POA的性能得到了一定程度的提升,但是,現(xiàn)有改進措施均未能從根本上解決POA“盲目搜索”問題和“維數(shù)”問題。

為了進一步提高水庫群調(diào)度問題的求解質(zhì)量和效率,本文一方面綜合DPSA和POA的降維優(yōu)勢,另一方面針對2種算法的不足進行改進,設(shè)計一種時、空組合降維技術(shù),并將其命名為IPOA-CBSA(Improved POA with Chain-Based Successive Approximation)。IPOA-CBSA采用CBSA框架,將復(fù)雜水庫網(wǎng)絡(luò)分解為若干“梯級水庫鏈”子網(wǎng),然后輪流對各“梯級水庫鏈”子網(wǎng)進行優(yōu)化,直至收斂。其中,各“梯級水庫鏈”子網(wǎng)問題采用IPOA進行求解。CBSA是DPSA變量解耦策略的改進型,將DPSA“單庫輪流”優(yōu)化模式拓展至“梯級水庫鏈輪流”優(yōu)化模式,通過對各“梯級水庫鏈”子網(wǎng)進行整體優(yōu)化,更好地處理梯級系統(tǒng)內(nèi)部水力耦合關(guān)系。IPOA采用動態(tài)變量解耦策略(Dynamic Variable Decoupling Strategy,DVDS)進行降維,彌補POA靜態(tài)變量解耦策略搜索的盲目性,改善解的質(zhì)量;同時引進擾動機制,緩解POA兩階段問題求解的“維數(shù)”問題。本文試圖通過對2種經(jīng)典算法進行改進和綜合,提高大規(guī)模復(fù)雜水庫群優(yōu)化問題的求解效能。

1 算法實證分析

1.1 “兩水庫三階段”問題

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

調(diào)度對象為A(上)、B(下)2座梯級水庫。調(diào)度期為1年,劃分為3個時段。調(diào)度問題可以簡單描述為:在滿足A、B水庫各項物理、運行約束條件下,尋求2座水庫的最優(yōu)蓄泄方案,使得梯級系統(tǒng)調(diào)度期內(nèi)總效益最大化。假設(shè)目標(biāo)函數(shù)可以表示為max{2RA,1+4RA,2+3RA,3+3RB,1+4RB,2+2RB,3}。其中:RA,t、RB,t分別為A、B水庫第t個時段的下泄水量(t=1,2,3)。

1.1.2約束條件

水庫水量平衡方程:VA,t=VA,t-1+2-RA,t,VB,t=VB,t-1+RA,t-RB,t。

水庫蓄水量上、下限:0≤VA,t≤3,0≤VB,t≤3。

水庫下泄水量上、下限:0≤RA,t≤5,0≤RB,t≤5。

邊界條件:VA,0=1,VA,3=1;VB,0=1,VB,3=1。

式中VA,t、VB,t——A、B水庫第t個時段末的蓄水量。

對于上述問題,容易求得最優(yōu)解相應(yīng)的梯級系統(tǒng)蓄水軌線為:AV～(1,3,0,1),BV～(1,0,0,1),下泄軌線為:AR～(0,5,1),BR～(1,5,0),目標(biāo)函數(shù)值為46?，F(xiàn)給定初始解,分別采用DPSA和POA求解上述問題。初始解相應(yīng)的梯級系統(tǒng)蓄水軌線為:AV～(1,3,1,1),BV～(1,1,0,1),下泄軌線為:AR～(0,4,2),BR～(0,5,1),目標(biāo)函數(shù)值為44。

1.2 DPSA求解過程分析

采用DPSA進行求解,先考慮固定B水庫蓄水軌線,對A水庫蓄水軌線進行優(yōu)化的情況。比較A水庫初始下泄軌線AR～(0,4,2)和最優(yōu)下泄軌線AR～(0,5,1)可知,要想獲得最優(yōu)下泄軌線,只需在初始下泄軌線的基礎(chǔ)上,將1個單位的水量從第3個時段轉(zhuǎn)移至第2個時段即可。按此操作后,B水庫下泄軌線變?yōu)锽R～(0,6,0),可知B水庫第2個時段的下泄水量已突破上限約束。因此,可以判定上述操作不可行。再考慮固定A水庫蓄水軌線,對B水庫蓄水軌線進行優(yōu)化的情況。比較B水庫初始下泄軌線BR～(0,5,1)和最優(yōu)下泄軌線BR～(1,5,0)可知,要想獲得最優(yōu)下泄軌線,只需在初始下泄軌線的基礎(chǔ)上,將1個單位的水量從第3個時段轉(zhuǎn)移至第1個時段即可。按此操作后,B水庫蓄水軌線變?yōu)锽V～(1,0,-1,1),可知B水庫第2個時段末的蓄水量已突破下限約束。因此,可以判定上述操作亦不可行。由于2種情況下水庫蓄水軌線均得不到改善,DPSA收斂于初始解。

此例說明:采用DPSA變量解耦策略難以有效處理梯級水庫之間復(fù)雜的水力耦合關(guān)系。實際上,要想獲得最優(yōu)解,必須同時對A、B水庫的蓄水軌線進行優(yōu)化。

1.3 POA求解過程分析

采用POA進行求解,首先對初始解相應(yīng)的梯級系統(tǒng)第2個時段末的蓄水狀態(tài)進行優(yōu)化,優(yōu)化后梯級系統(tǒng)蓄水軌線變?yōu)锳V～(1,3,0,1),BV～(1,1,1,1),下泄軌線變?yōu)锳R～(0,5,1),BR～(0,5,1),目標(biāo)函數(shù)值變?yōu)?5。此后,在POA優(yōu)化機制下,梯級系統(tǒng)蓄水軌線再也得不到改善,算法收斂。比較POA收斂解與最優(yōu)解可知,要想獲得最優(yōu)解,只需在收斂解的基礎(chǔ)上,將B水庫1個單位的水量從第3個時段轉(zhuǎn)移至第1個時段即可,由于B水庫第2個時段的下泄水量已達上限值,可以判定,在POA優(yōu)化機制下,上述跨時段操作無法實現(xiàn)。

此例說明:POA僅在T-1個固定子空間中搜索,無法保證收斂于最優(yōu)解,其中,T為調(diào)度期時段總數(shù)。實際上,要想獲得最優(yōu)解,必須為POA提供更多的搜索空間。

2 IPOA-CBSA

2.1 CBSA

考慮M座水庫聯(lián)合優(yōu)化問題。DPSA采用變量解耦策略,將M座水庫聯(lián)合優(yōu)化問題分解為M個單庫優(yōu)化問題,緩解了DP的“維數(shù)災(zāi)”效應(yīng)。但是,這種緩解是以犧牲解的質(zhì)量作為代價的。DPSA最大的缺陷在于其“單庫輪流”優(yōu)化模式難以有效處理梯級水庫之間復(fù)雜的水力耦合關(guān)系。DPSA時間復(fù)雜度和空間復(fù)雜度分別為O(M·T·K2)和O(T·K),K為水庫狀態(tài)離散點數(shù)。更多DPSA詳情參見文獻[8]。

為了彌補上述缺陷,本文考慮以“梯級水庫鏈”為優(yōu)化單元,將DPSA“單庫輪流”優(yōu)化模式拓展至“梯級水庫鏈輪流”優(yōu)化模式。以圖1所示“十水庫”系統(tǒng)為例,闡述CBSA的優(yōu)化過程。首先,采用常規(guī)方法(如等流量法)獲得“十水庫”系統(tǒng)各水庫初始下泄軌線;然后,將“十水庫”系統(tǒng)分解為1-7-10、2-4-7-10、3-4-7-10、5-7-10、6-7-10和8-9-10共6個梯級水庫鏈;最后,輪流對6個梯級水庫鏈的下泄軌線進行優(yōu)化,直至收斂。具體步驟如下。

圖1 “十水庫”系統(tǒng)結(jié)構(gòu)

對于M座水庫T個時段的優(yōu)化問題,假設(shè)水庫群系統(tǒng)包含n個梯級水庫鏈,則CBSA優(yōu)化步驟如下。

步驟二固定第j個梯級水庫鏈以外各水庫的下泄軌線,采用IPOA對第j個梯級水庫鏈以內(nèi)各水庫的下泄軌線進行優(yōu)化。該過程按照j=1,2,…,n的順序執(zhí)行,直到n個梯級水庫鏈均已優(yōu)化完畢為止。

從CBSA尋優(yōu)過程可見,CBSA每次以梯級水庫鏈為整體進行優(yōu)化,可以有效地處理梯級系統(tǒng)內(nèi)部復(fù)雜的水力耦合關(guān)系。

2.2 IPOA

與DPSA類似,POA也采用變量解耦策略進行降維?？紤]N座水庫構(gòu)成的梯級水庫鏈T個時段的優(yōu)化問題,POA首先將問題的N·(T-1)個狀態(tài)變量按時段分成T-1個固定的組,每組由同一時刻的N個狀態(tài)變量組成;然后輪流對各組變量的值進行優(yōu)化,直到N·(T-1)個狀態(tài)變量的值穩(wěn)定為止。因各組成員在整個優(yōu)化過程中保持恒定,故稱POA變量解耦策略為靜態(tài)變量解耦策略。POA時間復(fù)雜度和空間復(fù)雜度分別為O(T·KN)和O(N·T)。更多POA詳情參見文獻[9]。POA良好的收斂性和魯棒性使之成為當(dāng)下最流行的水庫群優(yōu)化技術(shù)之一,然而,“盲目搜索”問題和“維數(shù)”問題嚴(yán)重限制了該算法在大規(guī)模水庫群優(yōu)化中的應(yīng)用。

為了彌補上述缺陷,本文采用DVDS和擾動機制對POA進行改進。為了清楚起見,接下來采用決策變量(水庫下泄)對相關(guān)問題進行描述。

2.2.1DVDS

DVDS基本思想為:①從問題的N·T個決策變量中抽取2N個(每座水庫2個)對目標(biāo)函數(shù)影響最顯著的決策變量構(gòu)建N維子空間;②在N維子空間中搜索,改善解的質(zhì)量;③重復(fù)①—②,直至收斂。

2.2.1.1偶極子對

DVDS降維的關(guān)鍵是合理選取2N個決策變量。為了便于闡述,定義“偶極子對”的概念。在水庫群聯(lián)合調(diào)度中,通常各水庫調(diào)度期初、末期的蓄水量給定,因此,對于某一天然來水過程,各水庫調(diào)度期內(nèi)的總下泄水量是確定的。根據(jù)水量平衡原理,水庫某時段下泄量增加必然引起其他時段下泄量減少,且總增加量等于總減少量。根據(jù)上述原理,對水庫i(i=1,…,N)的下泄軌線施加擾動,譬如令ji時段下泄增加ΔRi,ki時段下泄減少ΔRi。因作用于ji、ki時段的擾動大小相等方向相反,將此擾動定義為水庫i的一個偶極子對,表示為(ji,ki)ΔRi,或者更簡潔地表示為(ji,ki)。對于梯級水庫鏈中的其他水庫,可實施與水庫i類似的操作。由于擾動疊加在水庫下泄軌線上,一般而言,系統(tǒng)目標(biāo)函數(shù)將發(fā)生變化。

2.2.1.2偶極子優(yōu)化問題

對于水庫i而言,其偶極子對中的ji、ki可在整數(shù)集{1,2,…,T}中任意取值,因此,總共存在T·(T-1)+1種偶極子對(其中,所有ji=ki的情況對應(yīng)同1種偶極子對)。對于由N座水庫構(gòu)成的梯級水庫鏈而言,考慮N座水庫不同偶極子對的組合,總共有[T·(T-1)+1]N種偶極子對組合。在這些組合中,必然存在1種組合,作用于水庫群下泄軌線上將產(chǎn)生最大的效益,稱之為最優(yōu)偶極子對組合。從所有偶極子對組合中尋找最優(yōu)偶極子對組合的問題稱為偶極子優(yōu)化問題。DVDS正是通過求解偶極子優(yōu)化問題,選取最優(yōu)偶極子對組合對應(yīng)的2N個決策變量構(gòu)建N維子空間。以第m+1次迭代為例,偶極子優(yōu)化問題可以表示為式(1):

(1)

2.2.1.3偶極子優(yōu)化問題的DP模型

采用DP求解式(1)所示偶極子優(yōu)化問題,定義階段變量、狀態(tài)變量和遞推方程如下。

a)階段變量。水庫調(diào)度一般按時間順序做出決策,因此通常將調(diào)度期劃分為若干個時段,用1個時段表示1個階段?？紤]到偶極子優(yōu)化問題的解是由不同水庫的偶極子對構(gòu)成,與時間相關(guān)性不大,并且,在梯級水庫鏈中,水庫i的最優(yōu)下泄軌線必須在水庫i-1的下泄軌線確定之后才能計算。因此,偶極子優(yōu)化是按空間順序做出決策。鑒于此,偶極子優(yōu)化問題的階段變量取水庫索引i。對于由N座水庫構(gòu)成的梯級水庫鏈,偶極子優(yōu)化問題的階段數(shù)為N。

c)遞推方程。對偶極子優(yōu)化問題進行順序遞推計算,遞推方程表示為式(2):

(2)

圖2 DP求解偶極子優(yōu)化問題原理

從圖2可見,采用式(2),DP將N階段問題分解為N個單階段問題,避免了重復(fù)計算,提高了求解效率。因為每個階段有T·(T-1)+1種狀態(tài),每個階段須進行[T·(T-1)+1]2次目標(biāo)函數(shù)計算,因此,DP的時間復(fù)雜度和空間復(fù)雜度分別為O(N·T4)和O(N·T2)。

2.2.2擾動機制

(3)

式中k——施加擾動的次數(shù),在搜索開始時設(shè)置為0;kRi,t——施加第k次擾動后,水庫i時段t的下泄量。

一般而言,在搜索的前期階段,梯級系統(tǒng)效益會顯著增長;隨著搜索的發(fā)展(即k值增加),梯級系統(tǒng)效益的增長速度會逐漸降低;當(dāng)k增加至某一臨界值L時,梯級系統(tǒng)效益將停止增長;當(dāng)k值超過L時,梯級系統(tǒng)效益開始下降。因此,k的最大取值應(yīng)當(dāng)為L。通常,L值可以采用試算法確定。L值確定后,通過使用遞推式(3)(從k=0遞推至k=L),梯級系統(tǒng)的下泄軌線可以得到改善。

由于IPOA的主要計算和存儲需求來自偶極子優(yōu)化問題求解,因此,IPOA的時間復(fù)雜度和空間復(fù)雜度與DP相同,分別為O(N·T4)和O(N·T2)。

2.3 算法組合

本文綜合CBSA和IPOA 2種技術(shù)的優(yōu)勢對復(fù)雜水庫系統(tǒng)進行降維:首先,采用CBSA將水庫群優(yōu)化問題分解為若干簡單的“梯級水庫鏈”優(yōu)化子問題;然后采用IPOA輪流對各“梯級水庫鏈”優(yōu)化子問題進行求解,直至收斂。對于M座水庫T個時段的優(yōu)化問題,假設(shè)水庫群系統(tǒng)分解為n個梯級水庫鏈,則IPOA-CBSA求解流程見圖3。IPOA-CBSA時間復(fù)雜度和空間復(fù)雜度分別為O(M·T4)和O(M·T2)。

圖3 IPOA-CBSA算法流程

3 案例研究

3.1 “四水庫”問題

以湖南沅水流域三板溪、白市、托口、五強溪4座季調(diào)節(jié)以上水庫構(gòu)成的梯級系統(tǒng)長期發(fā)電調(diào)度為例,研究IPOA-CBSA算法的性能。水庫拓撲關(guān)系見圖4,各水庫特征參數(shù)見表1。

表1 水庫特征參數(shù)

圖4 “四水庫”系統(tǒng)結(jié)構(gòu)

該問題調(diào)度期為1 a,劃分為12個時段(月),目標(biāo)函數(shù)為水庫群調(diào)度期內(nèi)總發(fā)電量最大。為了方便公式化描述,按從上游到下游的順序?qū)?座水庫依次編號為1、2、3、4,目標(biāo)函數(shù)表示為式(4):

(4)

約束條件主要包括水庫水量平衡方程、水庫蓄水量上下限、水庫下泄水量上下限、水庫出力上下限、水庫群總出力上下限、水庫庫容特性曲線、水庫尾水位特性曲線和調(diào)度邊界條件等。

采用流域2000年4月至2001年3月的月徑流數(shù)據(jù)進行模擬計算。為了更好地展現(xiàn)IPOA-CBSA的性能,采用EPOA-DP[27]、DDDP、DPSA和POA進行對比分析。初始解按各時段水庫出、入庫平衡調(diào)節(jié)計算產(chǎn)生,初始解對應(yīng)的目標(biāo)函數(shù)值為17 222 945 MWh。采用EPOA-DP、DDDP、DPSA和POA進行求解時,各水庫庫容離散間隔為1.054×107m3,相應(yīng)的流量步長為4 m3/s。ΔRi=1.054×107m3。在聯(lián)想臺式機上測試(3.40 GHz CPU,8 GB RAM),各算法最優(yōu)指標(biāo)對比見表2,各算法收斂過程對比見圖5。

表2 不同算法求解“四水庫”問題最優(yōu)指標(biāo)對比

圖5 各算法求解“四水庫”問題收斂過程

由表2可知,5種算法的最優(yōu)發(fā)電量,IPOA-CBSA最大,POA最小,IPOA-CBSA略大于EPOA-DP和DDDP,比DPSA增加0.62億kWh(增幅為0.3%),比POA增加1.39億kWh(增幅為0.7%)。

5種算法的計算耗時,DPSA最短,DDDP次之,POA最長。其中,POA計算耗時已超過11 h。POA耗時長主要是由兩階段問題求解的“維數(shù)障礙”引起。由于POA計算工作量與KN成正比,隨著新的水庫不斷加入系統(tǒng)參與優(yōu)化,可以預(yù)見,POA耗時將難以承受。

IPOA-CBSA計算耗時與DDDP基本相當(dāng)。與DDDP相比,IPOA-CBSA最大的優(yōu)勢在于其計算工作量隨M呈線性增長,而DDDP計算工作量隨M呈指數(shù)增長(DDDP時間復(fù)雜度為O(T·32M))?？梢灶A(yù)見,隨著新的水庫不斷加入系統(tǒng)參與優(yōu)化,DDDP計算耗時將遠遠大于IPOA-CBSA。

盡管EPOA-DP的最優(yōu)發(fā)電量與IPOA-CBSA基本相當(dāng),但其計算耗時約為后者的2倍。與EPOA-DP相比,IPOA-CBSA最大的優(yōu)勢在于無需對水庫狀態(tài)進行離散(計算工作量與K無關(guān)),而EPOA-DP計算工作量正比于K2(EPOA-DP時間復(fù)雜度為O(M·T2·K2))?？梢?隨著精度要求不斷提高,EPOA-DP計算耗時將遠遠大于IPOA-CBSA。

3.2 “十水庫”問題

采用更復(fù)雜的“十水庫”問題進一步驗證IPOA-CBSA算法的性能。“十水庫”問題是由Murray和Yakowitz引進文獻,最先用于測試約束微分動態(tài)規(guī)劃的性能[28]。Wardlaw和Sharif使用該問題測試GA的性能[29]。肖勝賢等[19]使用該問題測試改進POA-SA的性能。最近,Ahmadianfar等[30]使用該問題測試差分進化與粒子群混合算法的性能。與“四水庫”問題相比,“十水庫”問題不僅規(guī)模更大、系統(tǒng)結(jié)構(gòu)更復(fù)雜,而且約束條件更多、更苛刻?！笆畮臁毕到y(tǒng)結(jié)構(gòu)見圖1。10座水庫功能均以發(fā)電為主,調(diào)度期為1 a,劃分為12個時段,目標(biāo)函數(shù)為水庫群調(diào)度期內(nèi)發(fā)電效益最大,見式(5)。

(5)

式中bi,t——水庫i時段t的效益系數(shù)。

“十水庫”問題的約束條件主要有:水庫水量平衡方程、水庫蓄水量上下限約束、水庫下泄水量上下限約束和調(diào)度邊界條件等。水庫1、2、3、5、6、8各時段均有天然來水注入,水庫之間區(qū)間來水忽略不計?！笆畮臁眴栴}相關(guān)參數(shù)的取值見文獻[28]。

“十水庫”問題的規(guī)模已經(jīng)超過DP、DDDP、POA等算法的最大計算規(guī)模,該問題最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值為1194.44(可采用單純形法求得)。為了更好地展現(xiàn)IPOA-CBSA算法的性能,采用EPOA-DP-SA[27]、改進POA-SA[19]、DPSA和GA[29]進行對比分析。IPOA-CBSA、EPOA-DP-SA和DPSA的初始解取自文獻[28],初始解對應(yīng)的目標(biāo)函數(shù)值為1 080.983 6。IPOA-CBSA、EPOA-DP-SA、改進POA-SA、DPSA和GA分別經(jīng)過22、151、5、3和2 500次迭代后返回各自最優(yōu)值。在聯(lián)想臺式機上測試(3.40 GHz CPU、8 GB RAM),各算法最優(yōu)指標(biāo)對比見表3。

表3 不同算法求解“十水庫”問題最優(yōu)指標(biāo)對比

由表3可見,5種算法中,IPOA-CBSA耗時最短,而最優(yōu)返回值最大。IPOA-CBSA最優(yōu)返回值略大于EPOA-DP-SA和改進POA-SA,較DPSA提高了1.5%,較GA提高了0.3%,達到“十水庫”問題最優(yōu)目標(biāo)函數(shù)值的99.98%。IPOA-CBSA耗時僅為1.4 s,與改進POA-SA和DPSA較為接近,但遠遠小于EPOA-DP-SA和GA。進一步測試發(fā)現(xiàn),當(dāng)ΔRi=1×10-6時,IPOA-CBSA經(jīng)過22次迭代后返回最優(yōu)值1 194.44,最優(yōu)返回值達到“十水庫”問題最優(yōu)目標(biāo)函數(shù)值的100%,而耗時僅114.2 s。ΔRi=1×10-6時,IPOA-CBSA收斂過程見圖6。

圖6 IPOA-CBSA求解“十水庫”問題收斂過程

4 結(jié)論

“盲目搜索”問題和“維數(shù)”問題限制了DPSA和POA在水庫群聯(lián)合優(yōu)化中的性能。為了提高水庫群優(yōu)化問題的求解效率和解的質(zhì)量,本文對DPSA和POA進行改進和綜合,設(shè)計了一種組合降維算法。根據(jù)“四水庫”問題和“十水庫”問題的測試結(jié)果,本文得出以下結(jié)論。

a)采用CBSA將DPSA“單庫輪流”優(yōu)化模式拓展至“梯級水庫鏈輪流”優(yōu)化模式,“四水庫”問題和“十水庫”問題的優(yōu)化效益分別提高了0.3%和1.5%,說明與DPSA相比,CBSA能夠更好地處理梯級水庫之間復(fù)雜的水力耦合關(guān)系,能夠提高解的質(zhì)量。

b)采用DVDS對POA靜態(tài)變量解耦策略進行改進,“四水庫”問題的發(fā)電量提高了0.7%,說明DVDS能夠有效地彌補POA搜索的盲目性,能夠提高解的質(zhì)量。

c)通過在子問題求解中引進擾動機制和對2種改進算法進行組合,算法耗時明顯縮短:對于“四水庫”問題,POA計算耗時縮短了99.96%;對于“十水庫”問題,IPOA-CBSA計算耗時不到2 s。說明IPOA-CBSA能夠有效地緩解水庫群調(diào)度的“維數(shù)災(zāi)”效應(yīng),能夠提高求解效率。

d)IPOA-CBSA獲得了“十水庫”問題的最優(yōu)解,在解的質(zhì)量和求解效率上優(yōu)于7種現(xiàn)有算法,說明IPOA-CBSA能夠在保障解的質(zhì)量的同時提高求解效率。與現(xiàn)有算法相比,IPOA-CBSA最大的優(yōu)勢在于,其計算工作量與水庫數(shù)量為線性關(guān)系,具有應(yīng)用于大規(guī)模復(fù)雜水庫系統(tǒng)優(yōu)化的潛力。

為了簡化計算,建模時未考慮徑流的隨機性?？紤]來水的不確定性,采用IPOA-CBSA對水庫群進行長系列模擬計算,在此基礎(chǔ)上挖掘水庫系統(tǒng)優(yōu)化調(diào)度規(guī)則,成為下一步研究重點。