張佳丹 顧圣平 鄭斯水 唐鳳珍
摘?要:針對梯級水庫優(yōu)化調(diào)度高維度、多約束以及非線性優(yōu)化的特點,將自適應(yīng)權(quán)重以及連續(xù)禁忌搜索算法引入標(biāo)準(zhǔn)蝙蝠算法,改善標(biāo)準(zhǔn)蝙蝠算法在水庫優(yōu)化調(diào)度應(yīng)用中出現(xiàn)的早熟收斂且陷入局部最優(yōu)的問題:一方面利用自適應(yīng)權(quán)重避免因更新步長機制導(dǎo)致尋優(yōu)能力不足的問題;另一方面利用連續(xù)禁忌搜索算法避免因種群多樣性差導(dǎo)致陷入局部最優(yōu)的問題。案例分析結(jié)果表明,改進蝙蝠算法能有效運用于水庫發(fā)電優(yōu)化調(diào)度中,并且與標(biāo)準(zhǔn)蝙蝠算法相比,具有更強全局尋優(yōu)能力、更高的運行效率,得到的運行調(diào)度結(jié)果更優(yōu)。
關(guān)鍵詞:水庫優(yōu)化調(diào)度;蝙蝠算法;自適應(yīng)權(quán)重;連續(xù)禁忌搜索算法
中圖分類號:TV697.1文獻標(biāo)志碼:A
doi:10.3969/j.issn.1000-1379.2020.06.011
Optimal Operation of Cascade Hydropower Station Reservoirs Based on the Improved Bat Algorithm
ZHANG Jiadan, GU Shengping, ZHENG Sishui, TANG Fengzhen
(College of Water Conservancy and Hydropower Engineering, Hohai University, Nanjing 210098, China)
Abstract:For the optimal operation of cascade reservoirs having the characteristics of high-dimension, multi-constraint and nonlinear optimization, the adaptive weight and continuous tabu search were introduced into the basic bat algorithm to solve the issue of premature convergence and getting the local optimal result easily in the optimal operation: On the one hand, the adaptive weight was used for avoiding the lack of optimizing ability caused by the step update mechanism; on the other hand, continuous tabu search was used for avoiding getting the local optimal result caused by the decline in population diversity. The case analysis shows that the improved bat algorithm can be effectively applied to the optimal operation of reservoir power generation and compared with the basic bat algorithm, it has stronger global optimization ability, higher operation performance and better operation scheduling scheme.
Key words: optimal operation; bat algorithm; adaptive weight; continuous tabu search
水庫優(yōu)化調(diào)度作為一個典型的非線性優(yōu)化問題,能根據(jù)徑流資料以及綜合利用要求,運用優(yōu)化方法尋求最優(yōu)的水庫調(diào)度方案,使水庫在調(diào)度周期內(nèi)經(jīng)濟效益最高,提高水能資源利用效率。然而,決策過程的多階段性以及徑流的不確定性使得水庫優(yōu)化調(diào)度求解難度較高且求解精度較低。傳統(tǒng)的水庫優(yōu)化調(diào)度方法主要有動態(tài)規(guī)劃算法[1]、逐步尋優(yōu)算法[2]等,然而隨著水庫調(diào)度計算時段的細(xì)分,容易出現(xiàn)“維數(shù)災(zāi)”、耗時長的問題。近年來,粒子群算法[3]、遺傳算法[4]等智能算法的出現(xiàn)使水庫優(yōu)化調(diào)度進入一個新階段,但這些算法不可避免地出現(xiàn)魯棒性差、尋優(yōu)精度不高等問題。蝙蝠算法[5]是Xin-She Yang基于微型蝙蝠的回聲定位行為于2010年提出的一種啟發(fā)式算法,該算法結(jié)合了粒子群算法的學(xué)習(xí)機制以及模擬退火算法的冷卻原理等,在計算精度、穩(wěn)定性上優(yōu)于其他算法,具有很好的發(fā)展?jié)摿?與此同時,蝙蝠算法仍然會出現(xiàn)早熟收斂、陷入局部最優(yōu)的問題。自適應(yīng)權(quán)重[6]能夠根據(jù)蝙蝠當(dāng)前的離散程度與種群進化程度,動態(tài)地調(diào)整位置,從而保證最優(yōu)解不易丟失;連續(xù)禁忌搜索算法[7]作為一種亞啟發(fā)式算法,具有很強的局部搜索能力,能通過對一個初始可行解展開鄰域搜索,并利用一種靈活的記憶結(jié)構(gòu)以及相應(yīng)的規(guī)則指導(dǎo)算法進行,避免出現(xiàn)迂回搜索從而陷入局部最優(yōu)的情況。筆者嘗試在種群更新機制中引入自適應(yīng)慣性權(quán)重,并根據(jù)種群多樣性的優(yōu)劣[8]結(jié)合連續(xù)禁忌搜索策略對蝙蝠算法進行改進,以提高算法在水庫優(yōu)化調(diào)度中的全局尋優(yōu)能力。
1?水庫發(fā)電優(yōu)化調(diào)度模型
電站運行效益的提高主要依靠發(fā)電量,因此可以在滿足水電站的水位、水量以及出力等約束條件下,根據(jù)水庫初始運行條件和入庫徑流,合理控制各個時段的發(fā)電流量,使得梯級電站在調(diào)度周期內(nèi)發(fā)電量最大。
1.1?目標(biāo)函數(shù)
以各個時段初的水位作為決策變量,建立發(fā)電量最大的目標(biāo)函數(shù)。
F=max∑nk=1∑Tt=1KkQk,tHk,tΔt(1)
式中:n為梯級水庫的個數(shù);T為調(diào)度時段總數(shù);Kk為水庫k電站綜合出力系數(shù);Qk,t為水庫k在t時段發(fā)電流量,m3/s;Hk,t為水庫k在t時段發(fā)電水頭,m;Δt為時段長度,h。
1.2?約束條件
(1)水量平衡約束:
Vk,t+1=Vk,t+(Ik,t-Qk,t-Sk,t)Δt(2)
(2)水位約束:
Zk,tmin≤Zk,t≤Zk,tmax(3)
(3)水庫下泄流量約束:
Qk,tmin≤Qk,t+Sk,t≤Qk,tmax(4)
(4)水電站出力約束:
Nk,tmin≤Nk,t≤Nk,tmax(5)
式中:Vk,t為水庫k在t時段初水庫庫容,m3;Ik,t為水庫k在t時段入庫流量,m3/s;Sk,t為水庫k在t時段棄水流量,m3/s;Zk,t為水庫k在t時段初的水位,m;Nk,t為水庫k在t段電站出力,kW;Zk,tmin、Zk,tmax分別為水庫k在t時段允許水位上、下限,m;Qk,tmin、Qk,tmax分別為水庫k在t時段允許下泄流量上、下限,m3/s;Nk,tmin、Nk,tmax分別為水庫k在t時段允許電站出力上、下限,kW。
2?改進蝙蝠算法
2.1?標(biāo)準(zhǔn)蝙蝠算法
蝙蝠算法是模擬蝙蝠利用回聲定位原理來捕獲獵物行為的一種啟發(fā)式算法。假定優(yōu)化問題為max F(X),蝙蝠隨機分布在d維搜索空間中,每只蝙蝠的位置代表函數(shù)F(X)的一個解,對應(yīng)的函數(shù)值即為蝙蝠的適應(yīng)度值,適應(yīng)度值越大則表示蝙蝠的位置越優(yōu)。同時,蝙蝠飛行的過程代表解朝著更優(yōu)方向更新的過程,每只蝙蝠可利用自己所發(fā)出的脈沖頻率以及自身與當(dāng)前最優(yōu)位置的距離來調(diào)整飛行速度;蝙蝠的脈沖頻率通過在[fmin,fmax]中隨機分配獲得,這個范圍可根據(jù)所研究問題的具體情況進行設(shè)定,一般取[0,2]。那么,第i只蝙蝠發(fā)出的脈沖頻率為fi,在g時刻的位置為Xgi并以速度vgi飛行,根據(jù)式(6)~式(8)在g+1時刻獲得新的位置Xg+1i和速度vg+1i。
fi=fmin+(fmax-fmin)β(6)
vg+1i=vgi+(Xgi-X*)fi(7)
Xg+1i=Xgi+vg+1i(8)
式中:fmin、fmax分別為蝙蝠所發(fā)出聲波的最大頻率、最小頻率;β為區(qū)間[0,1]內(nèi)的一個隨機數(shù);X*為當(dāng)前最優(yōu)位置。
一旦蝙蝠的最優(yōu)位置被選中,蝙蝠就按照式(9)在原先最優(yōu)位置Xold附近以隨機游走的方式生成一個新位置Xnew。
Xnew=Xold+εAg(9)
式中:ε為區(qū)間(-1,1)內(nèi)的一個隨機數(shù);Ag為g時刻所有的蝙蝠發(fā)出脈沖響度Agi的平均值。
蝙蝠最初會以較小的脈沖發(fā)射速率和較大的脈沖響度來搜尋獵物,以保證有足夠的搜索范圍;在靠近獵物的過程中為能對獵物進行更精細(xì)地搜索,會降低發(fā)出的脈沖響度和提高脈沖發(fā)射速率。每只蝙蝠的初始脈沖響度A0i與初始脈沖發(fā)射速率r0i可以根據(jù)具體問題進行設(shè)定,一般取A0i=1表示蝙蝠發(fā)出的響度最大,r0i取接近于0的常數(shù)。若第i只蝙蝠在g時刻隨機游走后最優(yōu)蝙蝠位置得到改善并且發(fā)出的響度大于隨機響度,則將蝙蝠當(dāng)前最優(yōu)位置更新為Xnew,其脈沖響度以及脈沖發(fā)射速率分別按照式(10)、式(11)進行更新;否則保持最優(yōu)位置、脈沖響度以及脈沖發(fā)射速率不變。
Ag+1i=αAgi(10)
rg+1i=r0i[1-exp(-γg)](11)
式中:Ag+1i為第i只蝙蝠在g+1時刻的脈沖響度;rg+1i為第i只蝙蝠在g+1時刻的脈沖發(fā)射速率;α為聲波衰減系數(shù),一般取0.9;γ為脈沖速率增強系數(shù),一般取0.9。
當(dāng)?shù)螖?shù)達(dá)到最大值G時,蝙蝠位置停止更新,并輸出蝙蝠的最優(yōu)位置作為本次計算的最優(yōu)解。
2.2?算法的改進
2.2.1?自適應(yīng)權(quán)重
在標(biāo)準(zhǔn)蝙蝠算法中,一旦蝙蝠以某種頻率發(fā)出超聲波后,其速度的更新主要依靠當(dāng)前全局最優(yōu)位置,步長變化過于單一,容易丟失最優(yōu)解,從而影響蝙蝠算法的搜索性能。在速度更新公式中引入自適應(yīng)慣性權(quán)重,可以根據(jù)蝙蝠當(dāng)前進化程度以及離散程度,動態(tài)改變蝙蝠的更新速度,平衡算法的全局搜索與局部開發(fā)能力。對于整個種群來說:進化初期應(yīng)分配較大的慣性權(quán)重以保證全局搜索性能,在進化后期應(yīng)分配較小的慣性權(quán)重以保證算法的收斂性能。對于蝙蝠個體來說:個體適應(yīng)度差于整個種群的平均適應(yīng)度時,應(yīng)提高尋優(yōu)速度,分配其較大的慣性權(quán)重;個體適應(yīng)度優(yōu)于整個種群的平均適應(yīng)度時,應(yīng)提高局部開發(fā)能力,分配其較小的慣性權(quán)重。改進的速度更新公式如下:
vgi=wgivg-1i+(xgi-x*)fi(12)
wgi=wmax-(wmax-wmin)[g2G+Fgmax-Fgi2(Fgmax-Fgavg)],
Fgi≥Fgavgwmax,F(xiàn)gi 式中:wgi為第i只蝙蝠在g時刻的慣性權(quán)重;wmax、wmin分別為慣性權(quán)重的最大值、最小值;Fgi為第i只蝙蝠在g時刻的適應(yīng)度值;Fgmax為種群內(nèi)所有蝙蝠在g時刻的最優(yōu)適應(yīng)度;Fgavg為種群內(nèi)所有蝙蝠在g時刻的平均適應(yīng)度值。 2.2.2?連續(xù)禁忌搜索算法 隨著迭代次數(shù)的增加,蝙蝠個體會不斷靠近當(dāng)前最優(yōu)位置而導(dǎo)致種群多樣性急速下降,使得尋優(yōu)能力變差。連續(xù)禁忌搜索算法是禁忌搜索算法在連續(xù)優(yōu)化問題上的一種拓展,是通過模仿人類尋找東西行為的亞啟發(fā)式算法:在一段時間內(nèi)不會對已經(jīng)搜尋過的地方進行重復(fù)搜索;若沒有找到,則回到原來的地方繼續(xù)尋找。在蝙蝠算法后期已經(jīng)得到相對較優(yōu)解的情況下,可引入連續(xù)禁忌搜索算法來進一步提高尋優(yōu)精度:從蝙蝠搜索到的最優(yōu)解為中心點(即X*)出發(fā)展開鄰域搜索,對于已搜索到的局部解進行標(biāo)記和篩選,并在接下來的若干次迭代中避開這些解,從而能保證對解的不同區(qū)域的有效搜索。 連續(xù)禁忌搜索算法有以下幾個重要因素: (1)鄰域。假定當(dāng)前的鄰域中心點為d維變量X,分別以各個分量xj為中心繪制w個同心超矩形,并在每個同心矩形He(e=1,2,…,w)內(nèi)隨機選取1個點以及在中心矩形H0內(nèi)隨機選取s個點,由這w+s個點共同組成X的鄰域;一般情況下,取w=5,s=3。同心超矩形數(shù)學(xué)定義如下: H0(x,h0)={x′||xj′-xj| xj′ (14) He(x,he-1,he)={x′|he-1<|xj′-xj| xjmin he=2he-1(16) h0=0.001(xjmax-xjmin)(17) 式中:xjmax、xjmin分別為分量xj的最大值、最小值;he為同心矩形He領(lǐng)域半徑;h0為中心矩形H0的領(lǐng)域半徑。 (2)禁忌表和禁忌規(guī)則。在連續(xù)禁忌搜索算法中,將需要避開的解稱為禁忌對象,換句話說,這些解處于被禁忌的狀態(tài);禁忌表則是用來存儲禁忌對象的結(jié)構(gòu),禁忌表能存放禁忌對象的最大個數(shù)稱為禁忌長度。算法運行初始,建立一個空的禁忌表,禁忌長度為L,第一個鄰域中心點X*直接放進禁忌表中。 每次迭代都采用兩重禁忌規(guī)則來判定鄰域中的點X′在本次迭代中是否被禁忌。首先判斷適應(yīng)度值F(X):若X′與任意禁忌對象Xl(l=1,2,…,L)的關(guān)系均滿足式(18),則X′沒有被禁忌;否則表示X′的適應(yīng)度值接近于某個禁忌對象X′l,判斷這兩個點是否接近,若此時對于任意的分量xj(j=1,2,…,d),均滿足式(19),則點X′被禁忌,否則沒有被禁忌。 |F(X)-F(X′l)|≥εf1(18) |xj-xj′l|≤εf2(19) 式中:εf1、εf2均為常數(shù),一般取0.001;L為禁忌長度,一般取常數(shù)。 如果X′沒有被禁忌,則按照“先進先出”原則放置在禁忌表中,并將下一次迭代的鄰域中心點Xnow更新為X′;當(dāng)禁忌個數(shù)超過禁忌長度時,將最早進入的禁忌對象剔除。如果X′被禁忌,則不把X′放進禁忌表中,并將X′從鄰域中剔除,從剩余鄰域中選取一個最優(yōu)解,再次進行禁忌判斷,直到找到一個解X″沒有被禁忌。 (3)特赦規(guī)則。為保證算法的優(yōu)化效果,避免因禁忌規(guī)則而導(dǎo)致算法出錯,還需要設(shè)置特赦規(guī)則:當(dāng)解X′優(yōu)于當(dāng)前最優(yōu)解Xbest時,為保證解X′不會因禁忌規(guī)則而被漏掉,更新當(dāng)前最優(yōu)解Xbest后,無視禁忌規(guī)則直接判定X′沒有被禁忌;當(dāng)鄰域內(nèi)所有解都沒有優(yōu)于當(dāng)前最優(yōu)解Xbest且都被禁忌,為防止算法出現(xiàn)死循環(huán),將禁忌表內(nèi)的所有禁忌對象取線性平均值,直接判定沒有被禁忌。 (4)終止規(guī)則。迭代步數(shù)達(dá)到最大值,則終止迭代,輸出最優(yōu)解。 除上述幾個因素外,還要考慮進行禁忌搜索的合適時機:若過早進行禁忌搜索則干擾到蝙蝠的尋優(yōu)過程;若太晚進行禁忌搜索,則會影響最終的尋優(yōu)效果。因此,可以設(shè)定一個閥值ξ,對蝙蝠的種群多樣性進行判斷。種群在第g時刻的相對多樣性公式如下: ξ(g)=div(g)div(0) div(g)=?1md∑dj=1∑mi=1[xji(g)-x*j(g)UBji-LBji]2(20) 式中:xji(g)為第i只蝙蝠在g時刻的第j個分量;x*j(g)為最優(yōu)位置X*蝙蝠在g時刻的第j個分量;UBji、LBji分別為分量xji(g)的最大值和最小值。 當(dāng)ξ(g)小于ξ時,表明蝙蝠的種群多樣性比較差,此時,選取最優(yōu)蝙蝠個體作為進行禁忌搜索的初始點展開進一步尋優(yōu)。 2.3?改進蝙蝠算法計算流程 在處理水庫優(yōu)化調(diào)度中的約束條件時,水庫各時段的運行水位約束通過限制蝙蝠的位置范圍來實現(xiàn),而其他約束則引用罰函數(shù)概念處理。改進的蝙蝠算法求解水庫優(yōu)化調(diào)度問題的主要步驟如下: 第一步:確定參數(shù)。蝙蝠的種群規(guī)模m,脈沖頻率范圍[fmin,fmax],初始脈沖響度A0,初始脈沖發(fā)射速率r0,最大迭代次數(shù)G,種群多樣性閾值ξ,禁忌搜索的禁忌長度L。 第二步:種群初始化。生成m個可行解作為每只蝙蝠的初始位置X0,計算每只蝙蝠適應(yīng)度F(Xi),選擇當(dāng)前的最優(yōu)位置X*。 第三步:種群迭代。按照式(6)、式(8)、式(12)和式(13)對蝙蝠的位置和飛行速度進行自適應(yīng)更新,并更新當(dāng)前最優(yōu)位置X*。 第四步:局部搜索。選擇最優(yōu)的蝙蝠位置并生成一個隨機數(shù)β1。如果ri小于β1,則按照式(9)在附近進行擾動形成一個局部解,并進行下一步判斷;否則,跳到第六步。 第五步:更新最優(yōu)位置。生成另一個隨機數(shù)β2,如果最優(yōu)位置得到改善并且Ai大于β2,則更新蝙蝠的最優(yōu)位置,并按照式(10)、式(11)調(diào)整蝙蝠的脈沖響度和脈沖發(fā)射速率;否則,保持不變。 第六步:種群多樣性判斷。當(dāng)前蝙蝠多樣性若滿足閾值要求,則進行第七步;否則,跳到第八步。 第七步:如果迭代次數(shù)達(dá)到最大,則輸出最優(yōu)結(jié)果;否則,回到第三步。 第八步:禁忌搜索。從當(dāng)前最優(yōu)解X*出發(fā)進行連續(xù)禁忌搜索,根據(jù)禁忌規(guī)則以及特赦規(guī)則,更新禁忌表、鄰域以及當(dāng)前最優(yōu)解。 第九步:如果迭代次數(shù)達(dá)到最大,則輸出最優(yōu)結(jié)果;否則,回到第八步。 改進后的蝙蝠算法流程圖見圖1。 3?實例應(yīng)用 我國某梯級系統(tǒng)上游至下游包含2個水電站A、B,兩個電站均以發(fā)電為主要任務(wù),電站間有區(qū)間入流匯入。電站的基本參數(shù)見表1。 由于2個電站在汛期基本保持在汛限水位運行,因此針對供水期進行優(yōu)化調(diào)度分析。選用梯級電站系統(tǒng)3個典型年供水期(12月至次年5月,共6個月)的徑流資料,以旬為計算時段,分析梯級水庫的發(fā)電優(yōu)化調(diào)度結(jié)果。 設(shè)置蝙蝠種群大小m=100,蝙蝠發(fā)出的脈沖頻率范圍[fmin,fmax]為[0,2],初始脈沖響度A0=1,初始脈沖速率r0=0.001,聲波衰減系數(shù)α=0.9,脈沖速率增強系數(shù)γ=0.9;在改進蝙蝠算法中最大慣性權(quán)重wmax=1,最小慣性權(quán)重wmin=0.4,種群相對多樣性閾值ξ取0.001,禁忌搜索的禁忌長度L=6。標(biāo)準(zhǔn)蝙蝠算法和改進蝙蝠算法計算得到的梯級總發(fā)電量優(yōu)化結(jié)果見表2,相應(yīng)的3個典型年供水期的水庫A、B優(yōu)化調(diào)度水位過程如圖2~圖4所示。 由以上結(jié)果可知,改進蝙蝠算法比標(biāo)準(zhǔn)蝙蝠算法計算得到的梯級發(fā)電量有所增加,枯水年增加1.90×106 kW·h,平水年增加9.57×105 kW·h,豐水年增加1.15×105 kW·h。表明從梯級發(fā)電量考慮,改進蝙蝠算法的優(yōu)化效果更好。 為了進一步比較這兩種優(yōu)化算法的收斂速度,這里以枯水年供水期計算為例,給出兩種算法的迭代過程,如圖5所示。 由圖5可知,標(biāo)準(zhǔn)蝙蝠算法達(dá)到收斂所需迭代次數(shù)大于改進蝙蝠算法所需迭代次數(shù),表明改進蝙蝠算法在獲得更優(yōu)解的前提下,收斂速度明顯提高。 4?結(jié)?論 在標(biāo)準(zhǔn)蝙蝠算法中引入自適應(yīng)權(quán)重,改善蝙蝠種群的更新機制,使蝙蝠位置能夠根據(jù)實際情況進行自適應(yīng)動態(tài)調(diào)整,提高蝙蝠的搜索性能;同時,在算法后期種群多樣性變差時,引入連續(xù)禁忌搜索算法,避免出現(xiàn)迂回搜索而無法跳出局部最優(yōu)的情況。案例分析表明,改進蝙蝠算法與標(biāo)準(zhǔn)蝙蝠算法相比,能以較快的運行效率獲得更優(yōu)的水庫運行方案,為水庫發(fā)電優(yōu)化調(diào)度提供了一個新的途徑。 參考文獻: [1]?楊峰,黃懷禮,張強.用動態(tài)規(guī)劃法對水庫進行優(yōu)化調(diào)度[J].河南科學(xué),2005,23(1):17-19. [2]?羅紅兵.POA算法在水庫優(yōu)化調(diào)度中的應(yīng)用[J].陜西水利,2018(6):127-129. [3]?鄧顯羽,彭勇,葉碎高,等.粒子群算法在水庫(群)優(yōu)化調(diào)度研究中的應(yīng)用綜述[J].水利水電科技進展,2010,30(5):90-94. [4]?馮迅,王金文,權(quán)先璋,等.遺傳算法在水電站優(yōu)化調(diào)度中的實用研究[J].華中電力,2005(3):12-15. [5]?YANG X S. A New Metaheuristic Bat-inspired Algorithm[J].Computer Knowledge &Technology,2010,284:65-74. [6]?劉列.自適應(yīng)粒子群算法在水庫優(yōu)化調(diào)度中的應(yīng)用研究[J].大眾科技,2017,19(1):11-13. [7]?王明興.連續(xù)禁忌搜索算法改進及應(yīng)用研究[D].杭州:浙江大學(xué),2005:15-27. [8]?紀(jì)昌明,劉方,喻杉,等.基于鯰魚效應(yīng)粒子群算法的梯級水庫群優(yōu)化調(diào)度[J].電力系統(tǒng)保護與控制,2011,39(19):63-68. 【責(zé)任編輯?崔瀟菡】