基于Spark的水庫(kù)群多目標(biāo)調(diào)度粒子群并行化算法

馬川惠,李 瑛,黃 強(qiáng),李 鳳

(1.西安理工大學(xué)省部共建西北旱區(qū)生態(tài)水利國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710048;2.西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,陜西西安 710048)

傳統(tǒng)的水庫(kù)多目標(biāo)調(diào)度模型求解是以單目標(biāo)優(yōu)化模型為基礎(chǔ),多采用目標(biāo)約束法、主次目標(biāo)法、目標(biāo)加權(quán)法、理想點(diǎn)法等為主要求解方法。1985年,Yeh[1]在水庫(kù)多目標(biāo)分析過(guò)程中,采用ε-約束法得到了兼顧發(fā)電和供水兩個(gè)目標(biāo)的折中解。1987年,董子敖和閻建生[2]提出了一種把多水庫(kù)多目標(biāo)的復(fù)雜優(yōu)化問(wèn)題經(jīng)過(guò)多次分層后,轉(zhuǎn)化為相對(duì)簡(jiǎn)單的子問(wèn)題來(lái)求解的多目標(biāo)多層次優(yōu)化方法,為解決大規(guī)模水庫(kù)群優(yōu)化調(diào)度的“維數(shù)災(zāi)”難題提供了新途徑。1997年,黃強(qiáng)和沈晉[3]提出了水庫(kù)群多目標(biāo)調(diào)度模型的求解方法,對(duì)解決復(fù)雜水庫(kù)群聯(lián)合優(yōu)化調(diào)度問(wèn)題具有實(shí)際參考價(jià)值。上述方法其本質(zhì)上還是單目標(biāo)優(yōu)化方法,不足之處是計(jì)算工作量大、計(jì)算速度慢、存在“維數(shù)災(zāi)”等,不利于工程實(shí)際應(yīng)用。

目前,智能優(yōu)化算法在水庫(kù)群多目標(biāo)調(diào)度模型求解中正處于快速發(fā)展階段,如遺傳算法、蟻群算法、粒子群算法等已經(jīng)取得了顯著成果,具有并行計(jì)算特性,對(duì)解決復(fù)雜水庫(kù)群多目標(biāo)調(diào)度模型具有很大優(yōu)勢(shì)。1985年,Schaffer[4]提出第一個(gè)設(shè)計(jì)多目標(biāo)進(jìn)化算法——向量評(píng)價(jià)遺傳算法。2000年,由Deb等[5]對(duì)非支配排序遺傳算法(NSGA)進(jìn)行了針對(duì)性改進(jìn),提出了基于快速分類的非支配排序遺傳算法(NSGA-Ⅱ)。2006年,Kim等[6]針對(duì)Han River流域的4座水庫(kù)2個(gè)目標(biāo)調(diào)度問(wèn)題,利用NSGA-Ⅱ算法進(jìn)行求解,獲得了令人滿意的效果。2007年,Reddy和Kumar[7]提出一種用于求解水庫(kù)群多目標(biāo)調(diào)度問(wèn)題的多目標(biāo)差分進(jìn)化算法,取得了比NSGA-Ⅱ更好的優(yōu)化效果。2007年,Li Chen等[8]提出了一種用于確定以用水和發(fā)電為目標(biāo)的綜合利用水庫(kù)調(diào)度圖的基于宏進(jìn)化的多目標(biāo)遺傳算法。2016年,楊延偉[9]針對(duì)基于實(shí)數(shù)編碼的遺傳算法(RAGA)在實(shí)際水庫(kù)調(diào)度應(yīng)用中易于早熟的缺點(diǎn),提出一種改進(jìn)的RAGA。2017年,張翔宇等[10]針對(duì)NSGA-Ⅱ算法在進(jìn)化過(guò)程中存在的不足,利用擬隨機(jī)Halton序列及自適應(yīng)調(diào)整的方法加以改進(jìn)。

2006年,馬細(xì)霞等[11]以某綜合利用水庫(kù)優(yōu)化調(diào)度為實(shí)例進(jìn)行研究,表明基于粒子群優(yōu)化算法的調(diào)度模型適用于年內(nèi)水庫(kù)優(yōu)化調(diào)度規(guī)則的確定。2007年,楊俊杰等[12]提出一種新的基于自適應(yīng)網(wǎng)格技術(shù)的多目標(biāo)粒子群優(yōu)化算法,為求解大規(guī)模多目標(biāo)優(yōu)化問(wèn)題提供了一種有效手段。2008年,Alexandre和Darrell[13]建立了基于多目標(biāo)粒子群算法的水庫(kù)群優(yōu)化調(diào)度模型,并指出該模型的缺點(diǎn),如對(duì)算法參數(shù)的選擇較為敏感等。2017年,張忠波等[14]把下山搜索策略引入到粒子群智能算法中,函數(shù)測(cè)試證明該方法改進(jìn)了算法的魯棒性,提高了算法求解效率。

但是,隨著水庫(kù)群優(yōu)化調(diào)度的規(guī)模和數(shù)據(jù)急劇增大,各智能算法存在搜索時(shí)間長(zhǎng)、易陷入局部最優(yōu)解等問(wèn)題。為了提高智能算法的運(yùn)行效率,本文建立了水庫(kù)群多目標(biāo)優(yōu)化模型,提出了基于Spark框架的粒子群并行化算法,旨在彌補(bǔ)智能算法的缺陷,提高求解模型的速度,對(duì)更好地解決水庫(kù)群多目標(biāo)調(diào)度問(wèn)題具有重要的理論意義和應(yīng)用價(jià)值。

1 水庫(kù)群多目標(biāo)優(yōu)化模型建立及求解

1.1 模型建立

本文以發(fā)源于祁連山的黑河為研究對(duì)象,黑河流域水資源短缺,綜合利用矛盾突出,為了充分開(kāi)發(fā)利用水資源,已修建了眾多水庫(kù),如何科學(xué)、合理調(diào)度水庫(kù)群,發(fā)揮水資源綜合利用效益,已成為亟待解決的問(wèn)題。黑河流域水庫(kù)群調(diào)度具有多目標(biāo)的特點(diǎn),既要兼顧上游發(fā)電目標(biāo)、又要滿足中游農(nóng)業(yè)灌溉目標(biāo),同時(shí)還要考慮下游生態(tài)用水目標(biāo)。因此,本文以灌溉缺水量最小、生態(tài)缺水量最小、發(fā)電量最大為目標(biāo),建立目標(biāo)函數(shù):

minf(f1,f2,-f3)

(1)

式中,f1、f2、f3分別為灌溉缺水量、生態(tài)缺水量、發(fā)電量。

目標(biāo)1 灌溉缺水量最小

(2)

(3)

式中,T為總時(shí)段數(shù);I為總?cè)∷跀?shù);α(t,i)為第t個(gè)時(shí)段第i個(gè)取水口的灌溉系數(shù);QW(t,i)和QS(t,i)分別為第t個(gè)時(shí)段第i個(gè)取水口的灌溉需水量和供水量。

目標(biāo)2 生態(tài)缺水量最小

(4)

(5)

式中,β(t)為第t時(shí)段的生態(tài)系數(shù);QD(t)和QP(t)分別為第t時(shí)段的生態(tài)需水量和供水量。

目標(biāo)3 發(fā)電量最大

(6)

N(t,m)=k(m)Q(t,m)H(t,m)

(7)

式中,M為電站個(gè)數(shù);N(t,m)為第t個(gè)時(shí)段第m電站的出力;Δt為最小計(jì)算時(shí)段;k(m)為第m電站出力系數(shù);Q(t,m)為第t個(gè)時(shí)段第m電站的發(fā)電流量;H(t,m)為第t個(gè)時(shí)段第m站的發(fā)電水頭。

上述目標(biāo)函數(shù)應(yīng)滿足的約束條件為:

約束1 水量平衡約束

V(t+1,m)=V(t,m)+(QO(t,m)-QI(t,m))Δt

(8)

約束2 流量連續(xù)約束

QI(t,m+1)=QO(t,m)+q(t,m+1)

(9)

約束3 蓄水位約束

Zmin(t,m)≤Z(t,m)≤Zmax(t,m)

(10)

約束4 庫(kù)容約束

Vmin(t,m)≤V(t,m)≤Vmax(t,m)

(11)

約束5 下泄流量約束

QOmin(t,m)≤QO(t,m)≤QOmax(t,m)

(12)

約束6 出力約束

Nmin(m)≤N(t,m)≤Nmax(m)

(13)

約束7 邊界條件約束

Z(1,m)=Zc,Z(T+1,m)=Ze

(14)

約束8 控制斷面流量約束

QS(t,i)≥QW(t,i),QP(t)≥QD(t)

(15)

式中,V(t+1,m)、V(t,m)分別為第t+1時(shí)段初(第t時(shí)段末)、第t個(gè)時(shí)段初第m電站的庫(kù)容;QO(t,m)、QI(t,m)分別為第t個(gè)時(shí)段第m電站的出庫(kù)流量、入庫(kù)流量;q(t,m+1)為第t個(gè)時(shí)段第m電站與第m+1電站之間的區(qū)間入流;Zmin(t,m)、Zmax(t,m)分別為第t個(gè)時(shí)段第m電站的最低、最高水位;Z(t,m)為第t個(gè)時(shí)段第m電站的水位;Vmin(t,m)、Vmax(t,m)分別為第t個(gè)時(shí)段第m電站的最小、最大庫(kù)容;V(t,m)為第t個(gè)時(shí)段第m電站的庫(kù)容;QOmin(t,m)、QOmax(t,m)分別為第t個(gè)時(shí)段第m電站的最小、最大出庫(kù)流量;QO(t,m)為第t個(gè)時(shí)段第m電站的出庫(kù)流量;Nmin(m)、Nmax(m)分別為第m電站的最小出力、裝機(jī)容量;Zc、Ze分別為起調(diào)水位和調(diào)度期末蓄水位。

式(1)～(15)是本文建立的水庫(kù)群多目標(biāo)優(yōu)化調(diào)度模型,該模型具有多目標(biāo)、多維、非線性、動(dòng)態(tài)等特點(diǎn),模型輸入資料涉及社會(huì)、經(jīng)濟(jì)、水文、氣象、生態(tài)、水利工程、水資源綜合利用等方面,數(shù)據(jù)量龐大、關(guān)系復(fù)雜。因此,尋求求解模型的算法、處理龐大的數(shù)據(jù)量與保證計(jì)算速度成為難點(diǎn)。本文采用基于Spark框架的粒子群并行化算法求解該模型,旨在克服“維數(shù)災(zāi)”,提高計(jì)算速度。

1.2 模型求解

水庫(kù)群多目標(biāo)優(yōu)化調(diào)度模型的求解可用主次目標(biāo)、目標(biāo)加權(quán)、理想點(diǎn)等方法,把多目標(biāo)模型轉(zhuǎn)化為單目標(biāo)模型,對(duì)單目標(biāo)優(yōu)化模型采用動(dòng)態(tài)規(guī)劃、遺傳算法、蟻群算法等進(jìn)行求解。但這些方法計(jì)算工作量大、速度慢,存在“維數(shù)災(zāi)”。本文利用粒子群算法(PSO)對(duì)多目標(biāo)優(yōu)化模型進(jìn)行整體一次求解。該算法是從隨機(jī)解出發(fā),通過(guò)迭代尋找最優(yōu)解,它通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì),通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。粒子群算法是一種成熟的算法,其具體步驟見(jiàn)文獻(xiàn)[15]。

2 基于Spark平臺(tái)的粒子群算法并行化

2.1 Spark平臺(tái)

Spark支持的大規(guī)模并行分布處理算法實(shí)現(xiàn)了基于內(nèi)存的分布式計(jì)算,基于彈性分布式數(shù)據(jù)集(RDD)成功構(gòu)建起了一體化、多元化的大數(shù)據(jù)處理體系。使用Spark SQL、Spark Streaming、MLlib、GraphX等工具,可以解決大數(shù)據(jù)批處理、流處理、圖處理、機(jī)器學(xué)習(xí)、即席查詢與關(guān)系查詢等關(guān)鍵技術(shù)問(wèn)題,只需一個(gè)框架就可滿足各種使用場(chǎng)景的需求。2003年以來(lái),Spark逐漸獲得了學(xué)術(shù)界與工業(yè)界的認(rèn)可,成為大數(shù)據(jù)處理技術(shù)的研究熱點(diǎn)、新一代大數(shù)據(jù)處理平臺(tái)的首選。RDD是Spark并行處理的基礎(chǔ),所有Spark的操作都圍繞RDD進(jìn)行。應(yīng)用RDD可以進(jìn)行并行數(shù)據(jù)集之間的互相轉(zhuǎn)換、緩存等操作?；赟park進(jìn)行并行化編程時(shí),要將輸入數(shù)據(jù)分解成一個(gè)個(gè)批處理片段,然后再將這些數(shù)據(jù)段都轉(zhuǎn)換成Spark中的RDD,即將數(shù)據(jù)封裝在RDD中,通過(guò)進(jìn)行RDD的并行操作,實(shí)現(xiàn)數(shù)據(jù)處理的并行執(zhí)行。因此,基于Spark平臺(tái)并行計(jì)算模型編程實(shí)現(xiàn)粒子群算法的基本步驟為:把粒子群封裝為RDD,并將其初始化為大小規(guī)模均等的多個(gè)小種群;再對(duì)這些小種群粒子群進(jìn)行并行處理,構(gòu)建可行解[16-20]。

2.2 基于Scala語(yǔ)言的粒子群并行編程方法

Scala語(yǔ)言是具有面向?qū)ο蠛秃瘮?shù)式編程特性的多范式編程語(yǔ)言,是Spark主要支持的高級(jí)計(jì)算機(jī)語(yǔ)言,面向分布式并行程序設(shè)計(jì);Spark中大多數(shù)代碼都是通過(guò)Scala語(yǔ)言編寫的。

本文運(yùn)用Scala并行編程方法實(shí)現(xiàn)了并行PSO算法在水庫(kù)群優(yōu)化調(diào)度中的應(yīng)用,具體流程圖見(jiàn)圖1。

圖1 并行PSO算法流程圖Fig.1 Parallel PSO algorithm process

3 應(yīng)用實(shí)例

3.1 黑河水庫(kù)群多目標(biāo)調(diào)度實(shí)例

黑河是我國(guó)西部地區(qū)較大的一條內(nèi)陸河,發(fā)源于祁連山與大通山之間,流經(jīng)青海、甘肅、內(nèi)蒙三省區(qū),流域面積約為14.29萬(wàn)km2,干流河長(zhǎng)821 km[21]。鶯落峽以上為干流上游,地處山區(qū),分東西兩岔,河道比降大,水量較為充沛,不僅是黑河流域的主要產(chǎn)流區(qū),也是該流域的梯級(jí)水電開(kāi)發(fā)基地。鶯落峽至正義峽之間為中游,地勢(shì)相對(duì)平坦,光熱資源豐富,沿岸分布多個(gè)灌區(qū),是該流域的主要用水區(qū)。正義峽以下為下游,降水稀少,蒸發(fā)強(qiáng)烈,生態(tài)系統(tǒng)脆弱,是該流域的主要生態(tài)耗水區(qū)。黑河干流上游主要有8座梯級(jí)水電站水庫(kù),分別是黃藏寺(在建)、寶瓶河、三道灣、二龍山、大孤山、小孤山、龍首二級(jí)和龍首一級(jí)。本研究采用資料包括氣象、水文、水利樞紐、河渠機(jī)井、中游灌區(qū)、生態(tài)需水、分水方案及相關(guān)社會(huì)經(jīng)濟(jì)等方面的海量數(shù)據(jù)。

采用基于Spark并行計(jì)算框架的粒子群算法,求解水庫(kù)群多目標(biāo)優(yōu)化調(diào)度模型,獲得了較滿意的結(jié)果:中游灌區(qū)灌溉保證率為50.5%,居民生活和工業(yè)生產(chǎn)供水保證率為95.1%;狼心山斷面多年平均下泄生態(tài)水量滿足多年平均應(yīng)下泄水量的要求;黑河上游8座梯級(jí)水電站多年平均發(fā)電總量為21.85億kW·h,比設(shè)計(jì)值減少3.8%。說(shuō)明黑河流域水庫(kù)群多目標(biāo)調(diào)度犧牲了發(fā)電效益,滿足了供水和生態(tài)效益,符合“以水定電”的調(diào)度策略和黑河流域的實(shí)際狀況。

3.2 計(jì)算性能比較

系統(tǒng)性能測(cè)試在64位單機(jī)Windows 7操作系統(tǒng)、8 GB內(nèi)存的環(huán)境下運(yùn)行。為了對(duì)比分析,本文分別采用基于串行和并行化的粒子群算法求解水庫(kù)群多目標(biāo)優(yōu)化模型,且逐步增加了輸入的數(shù)據(jù)條數(shù)來(lái)測(cè)試這個(gè)程序的性能,測(cè)試結(jié)果如圖2所示。其中,串行粒子群算法應(yīng)用Visual Basic語(yǔ)言編程,并行化粒子群算法用Scala語(yǔ)言編程。

數(shù)據(jù)條數(shù)從2 052增加至20 520,增至原來(lái)的10倍,在單機(jī)條件下,串行運(yùn)行時(shí)間從26.90 min增加至364.60 min,并行運(yùn)行時(shí)間從3.08 min增加至53.20 min,并行比串行運(yùn)行速度有了很大提升,提升速度約6～8倍。

為了測(cè)試單機(jī)與多機(jī)的運(yùn)行速度,本文分別在Ubuntu Linux操作系統(tǒng)環(huán)境下,采用單機(jī)和10臺(tái)聯(lián)想服務(wù)器并行計(jì)算,且逐步增加程序運(yùn)行的數(shù)據(jù)條數(shù)(從2 052增加至20 520),得到了更加理想的結(jié)果,如圖3所示。

圖2 單機(jī)串行與單機(jī)并行程序運(yùn)行時(shí)間比較圖Fig.2 Run time comparison between single machine serial and single machine parallel program

圖3 單機(jī)與多機(jī)并行程序運(yùn)行時(shí)間比較圖Fig.3 Run time comparison between single machine and multi-machine parallel program

與上一步所得的單機(jī)并行運(yùn)行時(shí)間進(jìn)行比較,多機(jī)并行運(yùn)行時(shí)間在數(shù)據(jù)條數(shù)增加的過(guò)程中,從0.80 min增加至8.27 min,多機(jī)并行比單機(jī)并行計(jì)算速度有了大幅提升,約提升了4～7倍,且隨著輸入數(shù)據(jù)條數(shù)的增加,速度提升優(yōu)勢(shì)明顯,體現(xiàn)出Spark平臺(tái)處理大量數(shù)據(jù)的優(yōu)勢(shì)。

4 結(jié) 語(yǔ)

隨著社會(huì)經(jīng)濟(jì)的發(fā)展,在江河修建的水庫(kù)數(shù)量和規(guī)模越來(lái)越大,水庫(kù)群調(diào)度所需資料、數(shù)據(jù)量龐大,關(guān)系復(fù)雜。由于水庫(kù)群之間的水力聯(lián)系更加復(fù)雜化和調(diào)度規(guī)模更加龐大,進(jìn)一步加劇了水庫(kù)調(diào)度問(wèn)題求解的復(fù)雜性,應(yīng)用常規(guī)技術(shù)進(jìn)行優(yōu)化調(diào)度計(jì)算難度較大、速度慢,且存在“維數(shù)災(zāi)”等。此外,水庫(kù)運(yùn)行積累的數(shù)據(jù)也呈現(xiàn)出指數(shù)增長(zhǎng)的趨勢(shì),形成了海量數(shù)據(jù)源。因此,水庫(kù)群多目標(biāo)調(diào)度對(duì)海量數(shù)據(jù)處理有著強(qiáng)烈的需求;同時(shí),需要并行計(jì)算技術(shù)為水庫(kù)群調(diào)度及其優(yōu)化計(jì)算提供強(qiáng)大的計(jì)算能力。

本文以黑河流域的水資源調(diào)度問(wèn)題為背景,建立了水庫(kù)群多目標(biāo)優(yōu)化模型,提出了基于Spark框架求解模型的粒子群并行化算法。實(shí)例表明,將粒子群算法與Spark并行計(jì)算框架結(jié)合使用,滿足了當(dāng)前水庫(kù)群調(diào)度多目標(biāo)的需求,提高了程序的運(yùn)行速度,說(shuō)明基于Spark框架求解模型的粒子群并行化算法具有很好的性能。研究旨在彌補(bǔ)智能算法的缺陷,提高求解模型的速度,對(duì)水庫(kù)群多目標(biāo)優(yōu)化調(diào)度的并行編程發(fā)展與應(yīng)用具有重要的參考價(jià)值。