基于改進(jìn)混合蛙跳算法的梯級水庫優(yōu)化調(diào)度

，， ， ， ,(.華北電力大學(xué) 可再生能源學(xué)院， 北京 02206； 2.長江勘測規(guī)劃設(shè)計研究有限公司，武漢 000；.中國電建集團(tuán) 北京勘測設(shè)計研究院有限公司， 北京 0002；.中國水利水電科學(xué)研究院， 北京 0008)

1 研究背景

目前，我國各大江河干流及其主要支流等已經(jīng)或正在形成各自的水庫群，為水資源高效利用發(fā)揮著越來越重要的作用[1]，并有力地服務(wù)于全面建設(shè)小康社會。梯級水庫間具有十分復(fù)雜的水力聯(lián)系和電力聯(lián)系，其聯(lián)合優(yōu)化調(diào)度是一個多約束、高維、非線性的系統(tǒng)優(yōu)化問題，一直備受關(guān)注[2]。目前，大量尋優(yōu)算法已被用于水庫調(diào)度領(lǐng)域，其中動態(tài)規(guī)劃法具有全局收斂性，是求解梯級水庫聯(lián)合優(yōu)化調(diào)度模型的經(jīng)典算法，但其面臨“維數(shù)災(zāi)”問題[3]；近年來，隨著人工智能學(xué)科的發(fā)展，粒子群算法[4]、遺傳算法[5]、人工魚群算法[6]等智能方法已被廣泛引入，表現(xiàn)出強(qiáng)勁的生命力，但也存在早熟收斂等不足。因此，研究新方法并嘗試解決梯級水庫優(yōu)化調(diào)度問題仍然具有極為重要的現(xiàn)實(shí)意義。

受青蛙群體的協(xié)同機(jī)制啟發(fā)，Eusuff和Lansey[7]提出了一種新型高效的啟發(fā)式智能算法——混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)。該算法能夠搜索分析復(fù)雜空間中的最優(yōu)值，具有參數(shù)少、性能高、魯棒性強(qiáng)等特點(diǎn)，可用于求解具有不可微、多約束、多變量、多目標(biāo)等特點(diǎn)的非線性最優(yōu)控制問題。但是，SFLA存在著易早熟收斂等缺陷，已有學(xué)者對其進(jìn)行了一些改進(jìn)，提出了擴(kuò)張蛙跳算法[8]、粒子群蛙跳算法[9]、云變異蛙跳算法[10]等改進(jìn)算法，取得了良好效果。

對SFLA及其改進(jìn)的算法作進(jìn)一步分析，發(fā)現(xiàn)研究多是針對算法中的局部信息交流或者全局信息交換2種策略中的一種進(jìn)行改進(jìn)，算法的尋優(yōu)性能仍有待進(jìn)一步提高?；诖?，本文利用混沌技術(shù)對子群最優(yōu)解進(jìn)行精細(xì)搜索，結(jié)合蛙群最優(yōu)值擾動的處理方式對算法收斂進(jìn)行有目的的指導(dǎo)，構(gòu)建了“局部精細(xì)搜索”與“全局激勵調(diào)節(jié)”協(xié)同作用的改進(jìn)機(jī)制，并將其融入SFLA中，提出了一種改進(jìn)混合蛙跳算法(An Improved Shuffled Frog Leaping Algorithm，AISFLA)，以統(tǒng)籌算法的局部勘探和全局搜索。以李仙江流域梯級水庫為研究實(shí)例，驗(yàn)證了AISFLA的可行性和有效性。

2 混合蛙跳算法機(jī)理

SFLA是一種基于群體的協(xié)同搜索方法[11]，模擬青蛙覓食過程進(jìn)行尋優(yōu)。首先，按既定規(guī)則將青蛙種群分成多個子群，并在子群中開展搜索，通過信息的內(nèi)部交流來優(yōu)化內(nèi)部個體；然后，融合所有子群并按優(yōu)劣順序?qū)η嗤軅€體進(jìn)行排序，再次按既定規(guī)則劃分青蛙種群，通過這種方式實(shí)現(xiàn)全局性的信息交換?？梢钥闯?，混合蛙跳算法主要依靠局部信息交流和全局信息交換的結(jié)合搜索機(jī)制來尋優(yōu)，可在一定程度上避免過早陷入局部極值點(diǎn)。幾個重要概念見表1。

表1 SFLA重要概念Table 1 Important concepts in Shuffled Frog LeapingAlgorithm(SFLA)

SFLA計算流程如圖1所示，關(guān)鍵步驟包含蛙群初始化、蛙群劃分、局部搜索以及全局信息交換等。設(shè)f(x)為適應(yīng)度函數(shù);Ω為可行域;每一次迭代中，Xg為蛙群最優(yōu)青蛙;Xb為各子群最好青蛙;Xw為各子群最差青蛙。算法采用如下更新策略在各子群中進(jìn)行局部搜索：

(1)

式中：Dj為蛙跳步長更新值；rand()為[0,1]之間的隨機(jī)數(shù)；Xw,new為更新后的子群最差青蛙。

圖1 SFLA計算流程Fig.1 Computation flow of SFLA

3 改進(jìn)混合蛙跳算法

SFLA提出的時間不長，在理論方法及其應(yīng)用研究方面尚有待探索完善。與多數(shù)智能算法類似，SFLA在尋優(yōu)過程中不斷向蛙群最優(yōu)位置靠攏，蛙群多樣性逐漸降低，易出現(xiàn)早熟收斂。針對SFLA存在的問題，對局部搜索和早熟收斂進(jìn)行改進(jìn)，提出一種改進(jìn)混合蛙跳算法(AISFLA)。

3.1 局部精細(xì)搜索策略

混沌運(yùn)動普遍存在于非線性系統(tǒng)中，具有隨機(jī)性、遍歷性和規(guī)律性等特點(diǎn)。鑒于此，混沌技術(shù)具有易實(shí)現(xiàn)和避免局部陷阱的特殊能力[12]，已與多種智能算法融合來提高其性能。本文選用一種簡潔高效的一維非線性映射模型，即

Cr(t+1)=aCr(t)(1-Cr(t)) 。

(2)

式中：Cr(t)是算法每次運(yùn)行時隨機(jī)產(chǎn)生的常數(shù);a為控制參數(shù)，一般取4，此時系統(tǒng)處于混沌狀態(tài)[6]。

運(yùn)用混沌技術(shù)，在每次子群最好青蛙Xb周圍進(jìn)行精細(xì)搜索，策略如下：

newxb=xb+αs;

(3)

(4)

s=Cr(U-L)/β。

(5)

式中：α是搜索方向因子；s是搜索尺度；β是縮放因子，為不錯過各子群最好青蛙附近可能存在的更優(yōu)個體，其值可取20[13]；U，L分別為搜索空間的上下限。

3.2 全局激勵調(diào)節(jié)

針對算法尋優(yōu)過程中易出現(xiàn)早熟的問題，提出一種全局激勵調(diào)節(jié)策略，以改善蛙群多樣性，提高全局信息交流的能力。

3.2.1 蛙群相對多樣性判斷

(6)

(7)

式中：f為歸一化因子；F為蛙群規(guī)模。

設(shè)μk為當(dāng)前蛙群相對多樣性表征參數(shù)，可表示為

μk=σk/σ0。

(8)

若μk小于預(yù)定閾值μ*，則說明此時蛙群的多樣性較差，蛙群因受限在某一超平面中而過早收斂[15]，此時需要對蛙群最優(yōu)青蛙個體Xg進(jìn)行擾動來改善蛙群多樣性，進(jìn)而提高全局尋優(yōu)能力。

3.2.2 蛙群最優(yōu)個體處理

文獻(xiàn)[16]在處理PSO算法的早熟收斂問題時，采用了對當(dāng)前全局最優(yōu)粒子進(jìn)行微擾的方式進(jìn)行處理，效果顯著。借助這種思想，本文對蛙群最優(yōu)個體進(jìn)行擾動，促使算法跳出局部最優(yōu)。擾動公式為

(9)

4 AISFLA在梯級水庫優(yōu)化調(diào)度中的應(yīng)用

4.1 梯級水庫優(yōu)化調(diào)度模型

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

以發(fā)電量最大為目標(biāo)，建立梯級水庫中長期優(yōu)化調(diào)度模型，其目標(biāo)函數(shù)為

(10)

式中：E為調(diào)度期內(nèi)總發(fā)電量；i，n分別為水電站的編號和總數(shù)；t，T分別為調(diào)度期內(nèi)的時段編號和總時段數(shù)；Ai為水電站i的出力系數(shù)；Qi,t為水電站i在時段t的發(fā)電流量；Hi,t為水電站i在時段t的平均發(fā)電水頭；Δt為時段長。

4.1.2 約束條件

(1)水量平衡約束

Vi,t+1=Vi,t+(Ii,t-Qi,t-Si,t)Δt。

(11)

式中：Vi,t，Vi,t+1分別為水電站i在時段t的初、末庫容；Ii,t，Si,t分別為水電站i在時段t的入庫流量、棄水流量。

(2)上下庫流量聯(lián)系

Ii,t=Qi-1,t+Si-1,t+Ri,t。

(12)

式中Ri,t為水電站i在時段t的區(qū)間入庫流量。

(3)水位約束

Zi,tmin≤Zi,t≤Zi,tmax。

(13)

式中：Zi,t為水電站i在時段t的水位；Zi,t min，Zi,t max分別為水電站i在時段t允許的最低、最高水位。

(4)出力約束

Ni,tmin≤Ni,t≤Ni,tmax。

(14)

式中：Ni,t為水電站i在時段t的出力；Ni,t min，Ni,t max分別為水電站i在時段t的出力下限、上限。

(5)下泄流量約束

qi,tmin≤Qi,t+Si,t≤qi,tmax。

(15)

式中qi,t min，qi,t max分別為水電站i在時段t的下泄流量下限、上限。

(6)始末水位約束

(16)

4.2 基于AISFLA的模型求解步驟

運(yùn)用AISFLA求解梯級水庫中長期優(yōu)化調(diào)度模型，每只青蛙表示一種調(diào)度策略，具體求解步驟如下所述。

步驟1：參數(shù)初始化設(shè)置，包括蛙群規(guī)模F，子群中青蛙數(shù)h(F=M×h)，子群迭代次數(shù)Num_local，蛙群迭代次數(shù)Num_general?？尚杏颚阜秶鷥?nèi)隨機(jī)產(chǎn)生F只青蛙，第j只青蛙Xj編碼為

(17)

式中xit(i=1,2,…,n；t=1,2,…,T) 表示水電站i在時段t的出力。

步驟2：以式(10)為適應(yīng)度函數(shù)，計算當(dāng)前所有青蛙個體的適應(yīng)度值，然后按優(yōu)劣順序進(jìn)行排序，并對蛙群進(jìn)行重新劃分。

步驟3：利用式(3)—式(5)在當(dāng)前子群最好個體Xb基礎(chǔ)上進(jìn)行精細(xì)搜索，更新并取代Xb；確定當(dāng)前蛙群最優(yōu)個體Xg，然后依據(jù)式(1)的搜索策略更新子群最差個體Xw，重復(fù)步驟3直至滿足子群迭代次數(shù)Num_local；計算當(dāng)前蛙群適應(yīng)度方差。

步驟4：計算蛙群相對多樣性參數(shù)μk，檢驗(yàn)當(dāng)前蛙群多樣性是否滿足預(yù)定閾值。如果μk<μ*，利用式(9)進(jìn)行擾動，轉(zhuǎn)入步驟2；否則，轉(zhuǎn)入步驟5。

步驟5：判斷算法是否達(dá)到最大迭代次數(shù)Num_general。如果滿足，則停止尋優(yōu)過程，輸出結(jié)果；否則，轉(zhuǎn)入步驟2繼續(xù)迭代。

算法流程見圖2。

圖2 AISFLA計算流程Fig.2 Computation flow of AISFLA

表2 李仙江梯級水庫基本參數(shù)Table 2 Basic parameters of Lixianjiang cascade reservoirs

5 實(shí)例研究

5.1 工程概況

李仙江位于云南省境內(nèi)，是紅河的一級支流，控制流域面積約19 309 km2，中國境內(nèi)干流全長473 km，天然落差約1 790 m。干流上依次修建崖羊山、石門坎、新平寨、龍馬、居甫渡、戈蘭灘、土卡河7座水庫，本文選取具有調(diào)節(jié)性能的3座水庫(崖羊山、石門坎、龍馬)進(jìn)行計算，基本參數(shù)見表2。

5.2 結(jié)果分析

以某一枯水年實(shí)測徑流過程為輸入項(xiàng)，分別采用理論較為成熟的PSO算法、逐次逼近動態(tài)規(guī)劃算法(DPSA)、標(biāo)準(zhǔn)SFLA算法以及本文所提AISFLA算法，在同等條件下對李仙江梯級水庫進(jìn)行仿真計算。參照文獻(xiàn)[10]和文獻(xiàn)[15]中的參數(shù)設(shè)置建議，設(shè)置如下的算法參數(shù)：AISFLA中，蛙群規(guī)模F=200，子群中青蛙數(shù)h=20，子群總數(shù)M=10，子群迭代次數(shù)Num_local=10，蛙群迭代次數(shù)Num_general=500，蛙群相對多樣性閾值μ*=0.4，激勵因子Mf=1.5；標(biāo)準(zhǔn)SFLA中，參照AISFLA進(jìn)行參數(shù)設(shè)置；PSO中，學(xué)習(xí)因子c1，c2分別取1.5，2.0，慣性權(quán)重w=0.5，迭代次數(shù)取500；DPSA水位離散點(diǎn)取100。各智能算法獨(dú)立運(yùn)行10次，統(tǒng)計10次運(yùn)算中各種方法的最大發(fā)電量、平均發(fā)電量和標(biāo)準(zhǔn)差等指標(biāo)，結(jié)果如表3所示?？梢钥闯觯c表中列舉的2種智能優(yōu)化算法相比，AISFLA的計算結(jié)果有明顯提高(且最接近DPSA優(yōu)化結(jié)果)，與此同時，尋優(yōu)結(jié)果的穩(wěn)定性得到了有效提升，如相比于SFLA和PSO，AISFLA的標(biāo)準(zhǔn)差分別降低了70.17%和72.22%。

表3 不同方法計算結(jié)果Table 3 Results computed by different methods

進(jìn)一步對AISFLA和SFLA尋優(yōu)結(jié)果進(jìn)行分析。圖3為2種算法獨(dú)立運(yùn)行10次的計算結(jié)果(按降序排列)，可以看出，AISFLA相比于SFLA具有更好的尋優(yōu)性能，其各次模擬結(jié)果均優(yōu)于SFLA，且均值(平均發(fā)電量)比SFLA增加了1.74億kW·h，增幅為10.08%。

圖3 AISFLA算法與SFLA算法10次模擬結(jié)果對比Fig.3 Comparison of result between AISFLA and SFLA after 10 times of simulation

從收斂性方面分析AISFLA的優(yōu)越性。圖4為3種智能算法最大發(fā)電量方案對應(yīng)的收斂過程，可以看出，SFLA結(jié)果較優(yōu)于PSO，其收斂速度卻相對較慢，SFLA和PSO兩種算法在尋優(yōu)過程中容易陷入到局部最優(yōu)中，二者收斂過程呈現(xiàn)明顯的階梯狀；AISFLA在SFLA基礎(chǔ)上，利用混沌技術(shù)對局部最優(yōu)解進(jìn)行變異，加之結(jié)合全局激勵調(diào)節(jié)作用對收斂進(jìn)行有目的指導(dǎo)，“局部”與“全局”耦合作用的改進(jìn)機(jī)制，保證了算法求得的最終結(jié)果更接近全局最優(yōu)解；同時，AISFLA較SFLA和PSO算法的收斂速度更快。

圖4 3種算法收斂性比較Fig.4 Comparison of convergence among different methods

5.3 AISFLA性能進(jìn)一步測試

選取李仙江流域1957—2000年徑流資料進(jìn)行長系列計算，進(jìn)一步測試AISFLA在求解梯級水庫中長期優(yōu)化調(diào)度模型時的性能，計算結(jié)果如表4所示?？梢钥闯?，與SFLA和PSO相比，AISFLA求得多年平均發(fā)電量的增幅分別為6.74%和7.51%，所得結(jié)果更好，算法繼續(xù)保持著較好的尋優(yōu)性能。

表4 長系列計算結(jié)果Table 4 Computation results of AISFLA forlong-term series

注：電量差=AISFLA-SFLA(或者PSO)；百分比=電量差/SFLA(或者PSO)×100%

綜上，在水庫調(diào)度仿真計算中，本文所提AISFLA明顯改善了SFLA尋優(yōu)目標(biāo)和收斂速度2方面特性，是一種有效的改進(jìn)算法。

6 結(jié) 語

混合蛙跳算法(SFLA)是一種基于群體的協(xié)同搜索方法，本文提出了利用“局部精細(xì)搜索”和“全局激勵調(diào)節(jié)”耦合改進(jìn)策略對SFLA進(jìn)行改進(jìn)。一方面利用混沌技術(shù)對子群最優(yōu)值進(jìn)行變異操作，另一方面通過對蛙群最優(yōu)值進(jìn)行擾動來維持種群多樣性。對李仙江流域的計算結(jié)果表明，改進(jìn)算法具有很好的尋優(yōu)能力，可有效地增加已建成水庫群的發(fā)電效益，為提高梯級水庫中長期調(diào)度水平提供了技術(shù)支持。擴(kuò)展算法應(yīng)用領(lǐng)域是下一步研究的重點(diǎn)。

參考文獻(xiàn)：

[1] 王本德, 周惠成, 盧 迪. 我國水庫(群)調(diào)度理論方法研究應(yīng)用現(xiàn)狀與展望[J]. 水利學(xué)報, 2016, 47(3): 337-345.

[2] JI Chang-ming, JIANG Zhi-qiang, SUN Ping,etal. Research and Application of Multidimensional Dynamic Programming in Cascade Reservoirs Based on Multilayer Nested Structure[J]. Journal of Water Resource Planning and Management, 2015, 141(7): 1-13.

[3] 王 成, 曹慶磊. 水庫運(yùn)行管理中優(yōu)化調(diào)度的計算機(jī)算法研究[J]. 長江科學(xué)院院報, 2011, 28(1): 66-70.

[4] 王 森,馬志鵬,李善綜,等.粗粒度并行自適應(yīng)混合粒子群算法及其在梯級水庫群優(yōu)化調(diào)度中的應(yīng)用[J]. 長江科學(xué)院院報, 2017, 34(7): 149-154.

[5] 陳 端, 陳求穩(wěn), 陳 進(jìn). 基于改進(jìn)遺傳算法的生態(tài)友好型水庫調(diào)度[J]. 長江科學(xué)院院報, 2012, 29(3): 1-6,12.

[6] 黃 鋒, 王麗萍, 向騰飛, 等.基于混沌人工魚群算法的水庫發(fā)電優(yōu)化調(diào)度研究[J]. 中國農(nóng)村水利水電, 2014, (10): 149-153.

[7] EUSUFF M, LANSEY K, PASHA F. Shuffled Frog-leaping Algorithm: A Memetic Meta-heuristic for Discrete Optimization[J]. Engineering Optimization, 2006, 38(2): 129-154.

[8] KAUR P, MEHTA S. Resource Provisioning and Work Flow Scheduling in Clouds Using Augmented Shuffled Frog Leaping Algorithm[J]. Journal of Parallel and Distributed Computing, 2017, 101: 41-50.

[9] SAMUEL G G, ASIR RAJAN C C. Hybrid: Particle Swarm Optimization-Genetic Algorithm and Particle Swarm Optimization-Shuffled Frog Leaping Algorithm for Long-term Generator Maintenance Scheduling[J]. International Journal of Electrical Power & Energy Systems, 2015, 65: 432-442.

[10] 王麗萍, 孫 平, 蔣志強(qiáng), 等. 基于并行云變異蛙跳算法的梯級水庫優(yōu)化調(diào)度研究[J]. 系統(tǒng)工程理論與實(shí)踐, 2015, 35(3): 790-798.

[11] 羅雪暉, 楊 燁, 李 霞. 改進(jìn)混合蛙跳算法求解旅行商問題[J]. 通信學(xué)報, 2009, 30(7): 130-135.

[12] 陽春華, 錢曉山, 桂衛(wèi)華. 一種混沌差分進(jìn)化和粒子群優(yōu)化混合算法[J]. 計算機(jī)應(yīng)用研究, 2011, 28(2): 439-441.

[13] 易文周, 田立偉. 一種基于混沌搜索和鯰魚效應(yīng)策略的粒子群算法[J]. 計算機(jī)應(yīng)用與軟件, 2013, 30(5): 311-315.

[14] 姜 偉, 王宏力, 何 星, 等. 并行免疫離散粒子群優(yōu)化算法求解背包問題[J]. 系統(tǒng)仿真學(xué)報, 2014, 26(1): 56-61.

[15] 紀(jì)昌明, 劉 方, 彭 楊, 等. 基于鯰魚效應(yīng)粒子群算法的水庫水沙調(diào)度模型研究[J]. 水力發(fā)電學(xué)報, 2013, 32(1):70-76.

[16] 金榮洪, 袁智皓, 耿軍平, 等. 基于改進(jìn)粒子群算法的天線方向圖綜合技術(shù)[J]. 電波科學(xué)學(xué)報,2006, 21(6): 873-878.