基于改進(jìn)布谷鳥算法的梯級水庫長期優(yōu)化調(diào)度研究

明 波 黃 強(qiáng) 王義民(西安理工大學(xué) 西北旱區(qū)生態(tài)水利工程國家重點(diǎn)實(shí)驗(yàn)室培育基地，陜西 西安 710048)

基于改進(jìn)布谷鳥算法的梯級水庫長期優(yōu)化調(diào)度研究

明 波 黃 強(qiáng) 王義民(西安理工大學(xué) 西北旱區(qū)生態(tài)水利工程國家重點(diǎn)實(shí)驗(yàn)室培育基地，陜西 西安 710048)

梯級水庫優(yōu)化調(diào)度模型的求解一直是水利學(xué)科需要深入研究的基本問題。使用改進(jìn)布谷鳥算法求解梯級水庫優(yōu)化調(diào)度模型是一種新思路。布谷鳥算法是近年來提出的一種新穎的啟發(fā)式全局搜索算法，該算法參數(shù)少、魯棒性強(qiáng)、搜索效率高，已得到廣泛的研究和應(yīng)用。對標(biāo)準(zhǔn)布谷鳥算法的尋優(yōu)機(jī)制作了闡述，并嘗試在算法進(jìn)化過程中采用動態(tài)發(fā)現(xiàn)概率以及引入變異機(jī)制對標(biāo)準(zhǔn)算法進(jìn)行改進(jìn)，提出了改進(jìn)的布谷鳥算法，并將其應(yīng)用于某梯級水庫優(yōu)化調(diào)度中。以實(shí)例驗(yàn)證了布谷鳥算法在梯級水庫優(yōu)化調(diào)度中的可行性和有效性，提出的改進(jìn)策略可有效克服標(biāo)準(zhǔn)算法中的“早熟”現(xiàn)象，改進(jìn)算法搜索效率更高，尋優(yōu)結(jié)果更穩(wěn)定。

梯級水庫;水庫調(diào)度;優(yōu)化調(diào)度方法;布谷鳥算法

1 概 述

水庫優(yōu)化調(diào)度是一個(gè)強(qiáng)約束、非線性、多階段的組合優(yōu)化問題[1]，其核心在于建立合理的優(yōu)化調(diào)度模型以及選擇合適的求解方法[2]。隨著流域梯級水電站群規(guī)模的逐步擴(kuò)大，進(jìn)一步研究高效的調(diào)度方法具有重要的理論和實(shí)踐價(jià)值。水庫優(yōu)化調(diào)度的傳統(tǒng)方法主要包括線性規(guī)劃[3]、非線性規(guī)劃[4]、網(wǎng)絡(luò)流規(guī)劃[5]和動態(tài)規(guī)劃[6]等。傳統(tǒng)方法或多或少存在收斂結(jié)果不穩(wěn)定、算法復(fù)雜或者存在“維數(shù)災(zāi)”等問題[7]，難以適應(yīng)梯級水庫優(yōu)化調(diào)度的高維、非線性特點(diǎn)。智能算法具有原理簡單、易于實(shí)現(xiàn)、并行搜索以及全局尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)，為梯級水庫聯(lián)合優(yōu)化調(diào)度提供了一條新途徑。其中，具有代表性的有遺傳算法[8,9]、粒子群算法[7,10]、蟻群算法[11,12]以及差分進(jìn)化算法[13]等。

布谷鳥搜索算法 (CS)是由英國學(xué)者于2009年提出的一種新的群智能算法[14,15]。研究表明，CS算法的搜索性能高效，并且參數(shù)少、魯棒性強(qiáng)，其搜索效率不亞于傳統(tǒng)的GA和PSO[16～19]。作為一種新穎、高效的搜索算法，CS尚未被引入到梯級水庫優(yōu)化調(diào)度當(dāng)中。

本文對標(biāo)準(zhǔn)CS算法的尋優(yōu)機(jī)制作了闡述，并針對標(biāo)準(zhǔn)CS在進(jìn)化后期收斂速度慢、容易陷入局部最優(yōu)解的缺陷，嘗試采用動態(tài)發(fā)現(xiàn)概率以及引入種群變異機(jī)制對其進(jìn)行改進(jìn)，提出了改進(jìn)的布谷鳥算法(ICS)，并將其應(yīng)用于某梯級水庫中長期優(yōu)化調(diào)度問題當(dāng)中。

2 標(biāo)準(zhǔn)布谷鳥算法

布谷鳥最特殊的習(xí)性是寄生育雛。在繁殖期間，布谷鳥將卵產(chǎn)在宿主鳥窩里讓其孵化。卵一旦被發(fā)現(xiàn)，則會被宿主推出鳥窩或者宿主放棄原來的鳥窩，這也就意味著，布谷鳥須要重新尋窩，該過程可用一個(gè)概率Pa來表示，即新窩替換舊窩的概率為Pa。在尋窩過程，其飛行路徑呈現(xiàn)出萊維飛行 (Lévyflight)特征,屬于隨機(jī)游走的一種，其步長滿足一個(gè)重尾的穩(wěn)定分布，在行走過程中，短距離的探索與偶爾較長距離的行走相間。

同其他智能算法類似，CS算法首先是生成初始種群，并采用Lévyflight隨機(jī)游動算子和偏好隨機(jī)游動算子,對種群不斷地更新，經(jīng)過一定進(jìn)化代數(shù)，直到算法收斂于滿意解為止。

(1)Lévyflight更新方式

xi(t+1)=xi(t)+α⊕L(λ)

(1)

式中,xi(t+1)表示第t+1代中的個(gè)體i；α為步長控制量，用于控制隨機(jī)搜索的范圍； ⊕為點(diǎn)對點(diǎn)乘法；L(λ)為Lévy隨機(jī)搜索步長，服從Lévy分布。

L(λ)～u=t-λ, 1<λ≤3

(2)

(2) 偏好隨機(jī)游動更新方式

xi(t+1)=xi(t)+γ×H(Pa-ε)?[xj(t)-xk(t)]

(3)

式中,ε,γ∈[0,1],二者均服從均勻分布；xi(t)、xj(t)和xk(t)分別表示第t代中的3個(gè)隨機(jī)個(gè)體。H(Pa-ε)為赫維賽德函數(shù)，當(dāng)Pa-ε>0時(shí)，函數(shù)值為0；當(dāng)Pa-ε<0時(shí)，函數(shù)值為1；當(dāng)Pa-ε=0時(shí)，函數(shù)值為0.5。

綜上所述，可得到布谷鳥算法流程圖，如圖1所示。

3 改進(jìn)的布谷鳥算法(ICS)

本文主要從2個(gè)方面對標(biāo)準(zhǔn)的CS算法進(jìn)行了改進(jìn)。

(1) 采用動態(tài)發(fā)現(xiàn)概率替換原有的固定發(fā)現(xiàn)概率，使算法搜索后期更容易生成新的個(gè)體，避免算法“早熟”；

(2) 借鑒遺傳算法的思想，在算法進(jìn)化過程中引入變異機(jī)制，以進(jìn)一步增加種群的多樣性。

3.1 動態(tài)發(fā)現(xiàn)概率

在標(biāo)準(zhǔn)的CS算法中,采用一個(gè)隨機(jī)數(shù)ε與發(fā)現(xiàn)概率Pa作比較,根據(jù)比較結(jié)果，來確定是否產(chǎn)生新的個(gè)體：若ε >Pa，淘汰原有的個(gè)體，同時(shí)生成新的個(gè)體；若ε

因此，本文采用余弦遞減策略來實(shí)現(xiàn)Pa的動態(tài)變化,即

(4)

式中,Tmax為算法的最大進(jìn)化代數(shù)；Titer為當(dāng)前進(jìn)化代數(shù)；Pa,max與Pa,min分別為Pa的控制參數(shù)。

3.2 種群變異機(jī)制

在進(jìn)化算法中,初始解的質(zhì)量將影響算法的收斂速度以及最終的優(yōu)化結(jié)果。在標(biāo)準(zhǔn)的CS算法中,初始個(gè)體的生成方式為

xi=xmin+ξ(xmax-xmin),i∈[1,Npop]

(5)

式中,xi為初始種群中的個(gè)體i;xmin和xmax分別為個(gè)體生成的上、下限;ξ為[0,1]之間均勻分布的隨機(jī)數(shù);Npop為種群規(guī)模。

由式(5)可知，CS算法初始解的生成方式具有很大的隨機(jī)性。要獲得較高質(zhì)量的初始種群，必須加大種群的規(guī)模。而隨著種群規(guī)模的增加，計(jì)算機(jī)占用內(nèi)存也會隨之增加，不利于算法尋優(yōu)。

因此，本文對CS每代最佳個(gè)體進(jìn)行變異，以進(jìn)一步提高個(gè)體的質(zhì)量。變異機(jī)制如下：在CS算法迭代至第t代時(shí)，選擇當(dāng)前最佳的鳥窩xt,bt，不讓其直接遺傳到下一代，而是繼續(xù)進(jìn)行變異操作，并且變異步長會隨著進(jìn)化代數(shù)的增加而逐漸減小。變異機(jī)制可表示為

〗⊕ε

(6)

式中，xt,b2為變異后的鳥窩位置;ε為1×d向量，服從標(biāo)準(zhǔn)正態(tài)分布;d為優(yōu)化問題的維數(shù)。

進(jìn)行變異后可產(chǎn)生新的個(gè)體xt,b2。為保證變異沿著有利的方向進(jìn)行，比較變異后的個(gè)體xt,b2與變異之前的個(gè)體xt,b1的適應(yīng)度值，保留適應(yīng)度值較優(yōu)的個(gè)體xt,b,并將其遺傳到下一代，以此實(shí)現(xiàn)有效變異操作。

(7)

基于以上分析，通過采用動態(tài)發(fā)現(xiàn)概率以及引入種群變異機(jī)制,對標(biāo)準(zhǔn)CS算法進(jìn)行了改進(jìn)，從而建立改進(jìn)的布谷鳥算法。

4 梯級水庫優(yōu)化調(diào)度數(shù)學(xué)模型

本文建立了兼顧保證出力的梯級發(fā)電量最大模型。問題描述為：給定調(diào)度期內(nèi)各水電站及區(qū)間來水過程，綜合各種約束條件，確定梯級各水電站水庫的發(fā)電用水過程，在盡量滿足各水電站保證出力的前提下，使整個(gè)梯級的發(fā)電量最大。

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

(8)

4.2 約束條件

(1) 水量平衡約束

V(m,t+1)=V(m,t)+[Q1(m,t)-

Q0(m,t)-Qs(m,t)]×Δt

(9)

(2) 水位約束

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

(10)

(3) 下泄流量約束

Qomin(m,t)≤Qo(m,t)≤Qomax(m,t)

(11)

(4) 電站出力約束

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

(12)

(5) 邊界條件約束

Z(m,1)=Zm,b,Z(m,T+1)=Zm,e

(13)

式中，B為目標(biāo)函數(shù)值；t、T分別表示調(diào)度時(shí)期內(nèi)的時(shí)段編號以及總時(shí)段數(shù)；m、M分別表示水電站水庫的編號和總個(gè)數(shù)；N(m,t)表示m水電站第t時(shí)段的平均出力；Nm,f為m水庫的保證出力；H、δ和k均為模型的懲罰參數(shù)；V(m+1,t)、V(m,t)分別表示m水庫t時(shí)段的初、末庫容；QI(m,t)、Qo(m,t)、Qs(m,t)分別表示m水庫t時(shí)段入庫、出庫、棄水流量;q(i,t)為m水庫和m+1水庫在t時(shí)段的區(qū)間入流;Zmax(m,t)、Zmin(m,t)分別表示m水庫在t時(shí)段允許水位的上、下限;Qomax(m,t)、Qomin(m,t)表示m水庫允許下泄流量的上、下限;Nmax(m,t)、Nmin(m,t)分別表示m水庫在t時(shí)段允許出力的上、下限；Zm,b為m水庫調(diào)度初期的水位；Zm,e為m水庫調(diào)度末期的水位。

5 實(shí)例計(jì)算

為驗(yàn)證ICS算法的可行性和有效性，以某梯級水電站水庫的典型年資料為例進(jìn)行計(jì)算。該梯級水電站包含A、B兩座大型水庫，且均具有年調(diào)節(jié)庫容;A水庫位于B水庫的上游，調(diào)度期為5月～次年的4月;主汛期為7～8月。A、B水電站水庫各項(xiàng)參數(shù)見表1。

5.1 不同算法對比

采用ICS對調(diào)度模型進(jìn)行求解，同時(shí)將GA、CS以及ACS作為對比。算法參數(shù)設(shè)置如下：種群規(guī)模均為Npop=50；最大迭代次數(shù)為Tmax=300；在標(biāo)準(zhǔn)CS算法中，發(fā)現(xiàn)概率為Pa=0.25;在標(biāo)準(zhǔn)GA中,交叉、變異概率分別為Pc=0.2、Pm=0.08；在動態(tài)發(fā)現(xiàn)概率策略中，發(fā)現(xiàn)概率的控制參數(shù)為Pa,min=0.1，Pa,max=0.4。由于較大的變異步長容易使算法跳出可行搜索空間，導(dǎo)致變異效率很低，因此基于局部擾動思想，確定步長控制量為a1=0.5。

由于ICS、GA等均屬于隨機(jī)搜索算法，而且搜索結(jié)果不穩(wěn)定，因此,將程序獨(dú)立運(yùn)行10次，取其平均值作對比。

表2給出了上述4種算法的逐次運(yùn)行結(jié)果以及對應(yīng)的均值、標(biāo)準(zhǔn)差和每種算法的平均尋優(yōu)時(shí)間。此外，為了反映ICS算法優(yōu)化結(jié)果的合理性，挑選出了發(fā)電量最大對應(yīng)的調(diào)度結(jié)果作為代表進(jìn)行分析。

由表2可知：

(1) 從發(fā)電量來看，ICS的發(fā)電量最大值為82.77億kW·h，相對于標(biāo)準(zhǔn)的CS和GA，分別提高了1.28%和4.37%，但相對于ACS，則降低了0.13%。

(2) 從結(jié)果穩(wěn)定性來看，ICS優(yōu)化結(jié)果的標(biāo)準(zhǔn)差為0.57，均低于其余3種算法，表明優(yōu)化結(jié)果相對來說更穩(wěn)定。

(3) 從尋優(yōu)時(shí)間來看，CS以及其改進(jìn)型比GA的要長，不同改進(jìn)策略均會使算法的尋優(yōu)時(shí)間延長，但I(xiàn)CS與ACS尋優(yōu)時(shí)間相接近，說明本文所提出的改進(jìn)策略在確保一定精度的前提下,仍具有一定競爭力。

ICS既增加了發(fā)電量，又提高了結(jié)果的穩(wěn)定性，考慮到中長期水庫調(diào)度對時(shí)效性的要求不高，不同算法的尋優(yōu)時(shí)長并無本質(zhì)區(qū)別。總體而言，ICS優(yōu)于GA、CS及ACS，表明改進(jìn)策略有效。

同時(shí)，分析結(jié)果也表明，ICS調(diào)度結(jié)果均滿足各項(xiàng)約束條件，各水庫水位在蓄水期迅速上升，枯水期水位逐漸回落，體現(xiàn)了水庫“蓄豐補(bǔ)枯”的特點(diǎn)。調(diào)度結(jié)果合理、可靠，顯示出ICS算法應(yīng)用于梯級水庫調(diào)度中的可行性。

5.2 改進(jìn)策略作用分析

為區(qū)分2種改進(jìn)策略各自作用的大小，單獨(dú)采用變異策略以及動態(tài)發(fā)現(xiàn)概率策略，分別與傳統(tǒng)CS的收斂過程進(jìn)行對比,如圖2所示。

從優(yōu)化結(jié)果來看，2種策略均于使優(yōu)化結(jié)果得到改善，但變異策略的改善效果更為明顯；從收斂性來看，采用變異策略可明顯提升算法的收斂速度，而采用動態(tài)發(fā)現(xiàn)概率策略在收斂前期可使收斂速度下降，這可能與采用動態(tài)發(fā)現(xiàn)概率改變了算法進(jìn)化過程中全局與局部搜索之間的均衡性有關(guān)。從算法復(fù)雜度來看，采用變異策略增加了目標(biāo)函數(shù)的評價(jià)次數(shù)，使算法尋優(yōu)時(shí)間變長，而采用動態(tài)發(fā)現(xiàn)概率并無改變算法的復(fù)雜度，因而尋優(yōu)時(shí)間基本不受影響。

總體而言，采用2種改進(jìn)策略均能使優(yōu)化的主要目標(biāo)(梯級發(fā)電量)得到改善，但變異策略對于算法整體的改善效果更為明顯。

5.3 ICS算法搜索性能分析

在智能算法中，一般通過增大種群規(guī)模或者迭代次數(shù)可進(jìn)一步改善優(yōu)化結(jié)果，但同時(shí)也占用了更多的計(jì)算機(jī)內(nèi)存且延長了尋優(yōu)時(shí)間。因此，高效的算法應(yīng)該是在較小的種群規(guī)模下,經(jīng)過一定的迭代次數(shù),便可收斂至全局最優(yōu)或者準(zhǔn)全局最優(yōu)解。為進(jìn)一步反映ICS的搜索性能，通過設(shè)定不同的種群規(guī)模進(jìn)行優(yōu)化計(jì)算，優(yōu)化結(jié)果見表3。

由表3可知，種群規(guī)模越大，ICS算法的收斂速度就越快;當(dāng)進(jìn)化代數(shù)為500時(shí)，三者的收斂值相差較小，表明ICS在較小的種群規(guī)模下經(jīng)過一定的迭代次數(shù),仍然可以達(dá)到較滿意的精度，顯示出該算法的高效性。

結(jié)合表2，當(dāng)GA種群規(guī)模為50時(shí)，進(jìn)化代數(shù)為300次時(shí)最大的優(yōu)化值僅為79.35億kW·h，而在同等條件下,CS最大優(yōu)化值為81.93億kW·h，ICS的最大優(yōu)化值為82.77億kW·h，表明GA和CS均不同程度地陷入了局部最優(yōu)解，但CS在克服算法“早熟”方面的性能明顯更優(yōu)。這是由CS算法搜索機(jī)理所決定的，算法中，Lévyflight搜索步長長短相間以及偏好隨機(jī)游動,在每次迭代時(shí)都會產(chǎn)生新的個(gè)體，使算法在進(jìn)化后期仍能夠保持較好的種群多樣性，因而不容易陷入局部最優(yōu)解。相對于GA和CS而言，ICS的搜索性能也進(jìn)一步得到了提升，表明改進(jìn)策略的有效性。

6 結(jié) 語

作為一種新穎的群智能算法，布谷鳥算法參數(shù)少、搜索效率高、尋優(yōu)結(jié)果穩(wěn)定、魯棒性強(qiáng)，可為梯級水庫優(yōu)化調(diào)度提供一條有效途徑。標(biāo)準(zhǔn)的CS算法在進(jìn)化過程中同樣存在收斂速度慢、種群活力不足等缺陷，本文通過采用動態(tài)發(fā)現(xiàn)概率以及引入變異機(jī)制,對標(biāo)準(zhǔn)算法進(jìn)行了改進(jìn)，提出了改進(jìn)的布谷鳥算法，并將其應(yīng)用于求解梯級水庫優(yōu)化調(diào)度問題當(dāng)中。實(shí)例應(yīng)用結(jié)果驗(yàn)證了布谷鳥算法在梯級水庫優(yōu)化調(diào)度中的可行性和有效性。

此外，本文所提出的改進(jìn)策略,可以進(jìn)一步提高算法的搜索性能。總之，改進(jìn)的布谷鳥算法搜索性能更高，尋優(yōu)結(jié)果也更加穩(wěn)定。

[1] 趙明雁,程春田,李剛. 水庫群系統(tǒng)優(yōu)化調(diào)度新進(jìn)展[J]. 水文,2005,25(6):18-23.

[2] 陳立華,梅亞東,董雅潔,等. 改進(jìn)遺傳算法及其在水庫群優(yōu)化調(diào)度中的應(yīng)用[J]. 水利學(xué)報(bào),2008,39(5):550-556.

[3]ZiadK.Shawwash,ThomasK.Siu,S.O.DenisRussell.TheB.C.HydroShortTermHydroSchedulingOptimizationModel[J].IEEETransactionsonPowerSystems, 2000, 15(3): 1125-1131.

[4]GuanX,LuhPB,ZhangL.NonlinearApproximationinLagrangianRelaxation-basedforHydrothermalScheduling[J].IEEETransactionsonPowerSystems, 2000, 10(2): 772-778.

[5]P.E.C.Franco,M.F.Carvalho,S.Soares.ANetworkFlowModelforShorttermHydro-dominatedHydrothermalSchedulingProblems[J].IEEETransactionsonPowerSystems, 1994, 9(2): 1016-1022.

[6]TraversDL,KayeRJ.DynamicDispatchbyConstructiveDynamicProgramming[J].IEEETransactionsonPowerSystems, 1998, 13(1): 72-78.[7] 彭勇,梁國華,周惠成. 基于改進(jìn)微粒群算法的梯級水庫群優(yōu)化調(diào)度[J].水力發(fā)電學(xué)報(bào),2009,28(4):49-55.[8] 王少波,解建倉,孔珂. 自適應(yīng)遺傳算法在水庫優(yōu)化調(diào)度中的應(yīng)用[J].水利學(xué)報(bào),2006,37(4):480-485.

[9] 鄭姣,楊侃,倪福全,等. 水庫群發(fā)電優(yōu)化調(diào)度遺傳算法整體改進(jìn)策略研究[J].水利學(xué)報(bào),2013,44(2):205-211.

[10]張雙虎,黃強(qiáng),吳洪壽,等. 水電站水庫優(yōu)化調(diào)度的改進(jìn)粒子群算法[J].水力發(fā)電學(xué)報(bào),2007,26(1):1-5.

[11]徐剛,馬光文,梁武湖,等. 蟻群算法在水庫優(yōu)化調(diào)度中的應(yīng)用[J].水科學(xué)進(jìn)展,2005,16(3):397-400.

[12]徐剛,馬光文.基于蟻群算法的梯級水電站群優(yōu)化調(diào)度[J].水力發(fā)電學(xué)報(bào),2005,24(5):7-10.

[13]鄭慧濤,梅亞東,胡挺,等. 改進(jìn)差分進(jìn)化算法在梯級水庫優(yōu)化調(diào)度中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào)(工學(xué)版),2013,46(1)：57-61.

[14]Xin-sheYang,DebSuash.CuckoosearchviaLévyFlights[C].ProceedingsofWorldCongressonNature&BiologicallyInspiredComputing.Piscataway:IEEEPublications, 2009: 210-214.

[15]Xin-sheYang,DebSuash.Engineeringoptimizationbycuckoosearch[J].Int’lJournalofMathematicalModelingandNumericalOptimization, 2010, 1(4):330-343.

[16]G.Kanagaraj,S.G.Ponnambalam,N.Jawahar.Ahybridcuckoosearchandgeneticalgorithmforreliability-redundancyallocationproblems[J].Computers&IndustrialEngineering, 2013, 66(4):1115-1124.

[17]M.Dhivya,M.Sundarambal.CuckooSearchforDataGatheringinWirelessSensorNetworks[J].Int’lJournalofMobileComnunications, 2011, 9(6):642-654.

[18]AmirHosseinGandomi,Xin-SheYang,AmirHosseinAlavi.Cuckoosearchalgorithm:ametaheuristicapproachtosolvestructuraloptimizationproblems[J].EngineeringwithComputers,2013,29:17-35.

[19]ApoorvP.Patwardhan,RohanPatidar,NithinV.George.Onacuckoosearchoptimizationapproachtowardsfeedbacksystemidentification[J].DigitalSignalProcessing,2014,32(9):156-163.

[20]李煜,馬良. 新型元啟發(fā)布谷鳥搜索算法[J].系統(tǒng)工程,2012,30(8):64-69.

(編輯：趙秋云)

2015-04-09

明 波，男，西安理工大學(xué)水利水電學(xué)院，碩士研究生.

1006-0081(2015)04-0009-05

TV697.12

A