Memetic 算法在水電站負荷優(yōu)化分配中的應用

鄧麗麗,楊 侃,周佳佳

(河海大學水文水資源學院,江蘇南京 210098)

Memetic 算法在水電站負荷優(yōu)化分配中的應用

鄧麗麗,楊 侃,周佳佳

(河海大學水文水資源學院,江蘇南京 210098)

針對求解水電站廠內經濟運行中負荷優(yōu)化分配問題時常出現(xiàn)的收斂性差、易早熟等問題,將基于全局搜索和局部啟發(fā)式搜索相結合的Memetic算法應用于水電站廠內經濟運行負荷優(yōu)化分配模型,用有限制的初始種群生成法來克服水電站機組不穩(wěn)定運行問題,采用育種算法作為局部搜索策略。三峽水電站廠內經濟運行實例計算結果表明,有限制的初始種群生成法能夠避開空蝕振動區(qū)的影響,保證機組的穩(wěn)定安全運行;Memetic算法的全局搜索和局部啟發(fā)式搜索策略能夠擴大尋優(yōu)范圍,優(yōu)化群體結構,提高算法的收斂能力。

水電站;負荷優(yōu)化分配;廠內經濟運行;Memetic算法;全局搜索;局部搜索

水電站廠內經濟運行是在滿足一系列約束條件的情況下,制定機組的啟停次序,選擇最優(yōu)的工作機組臺數(shù)和組合以及各運行機組間的負荷,以期獲得電站運行的最大經濟效益[1]。負荷優(yōu)化分配是水電站廠內經濟運行的關鍵子問題,該問題是指當給定了機組組合后,在滿足各種約束條件的前提下,將系統(tǒng)負荷合理分配給各運行機組,使水電站機組的總耗水量最小[2]。最優(yōu)的負荷分配可減小機組的運作損耗以提高機組運行的穩(wěn)定性和安全性,減少發(fā)電耗水量以提高水資源的利用效率。因此,負荷優(yōu)化分配不僅要考慮水電站發(fā)電機組最小、最大預想出力的限制條件,還不能忽略實際負荷分配中存在的機組空蝕振動區(qū)等嚴重影響水輪機穩(wěn)定和安全運行的限制問題。負荷優(yōu)化分配是一個復雜的多約束非線性優(yōu)化問題,在以往的研究中,其主要的求解方法包括等微增率法[1]、動態(tài)規(guī)劃法[3-4]、遺傳算法[5-7]和微粒群算法[8]等。周冉等[3]在用動態(tài)規(guī)劃法求解負荷最優(yōu)分配方案的過程中,為了避開機組的空蝕振動區(qū),對機組流量特性曲線出力落在空蝕振動區(qū)的部分進行懲罰處理;但當水電站機組數(shù)和解空間維數(shù)增多時,動態(tài)規(guī)劃法會出現(xiàn)“維數(shù)災”問題。張仁貢等[6]將遺傳算法(genetic algorithm,GA)應用于水電站廠內經濟運行,對機組的空蝕振動區(qū)在評價函數(shù)中用罰函數(shù)進行處理;但遺傳算法不能有效地處理非線性約束,且當維數(shù)較高時,會影響算法的搜索效率,很容易使算法陷入局部最優(yōu),不便于水電站負荷分配問題的求解。李崇浩等[8]通過確定微粒群在多維空間中的最優(yōu)位置來實現(xiàn)機組間的負荷優(yōu)化分配,對飛入振動區(qū)的微粒進行懲罰來避開空蝕振動區(qū),并引入遺傳算法的交叉算子克服局部收斂問題;小范圍的交叉雖可產生新個體,但具有局限性。

Memetic算法[9-10]是一種不同于遺傳算法的全局優(yōu)化算法,它不僅吸取了遺傳算法全局搜索能力的優(yōu)點,同時通過局部搜索策略來提高算法的局部搜索能力,為解決水電站廠內經濟運行中的負荷優(yōu)化分配問題提供了一種有效的方法。本文探討一種以育種算法為局部搜索策略的Memetic算法在水電站負荷優(yōu)化分配問題中的應用,并通過實例計算驗證該算法求解水電站負荷優(yōu)化分配問題的可行性和收斂性。

1 水電站廠內經濟運行負荷優(yōu)化分配模型

水電站廠內經濟運行負荷優(yōu)化分配的目的是當給定系統(tǒng)負荷和水電站水頭時,使整個水電站耗流量最小。最佳的負荷分配需要使機組運行效率最高且保證機組穩(wěn)定安全運行,故必須避開機組的空蝕振動區(qū)。水電站廠內經濟運行負荷優(yōu)化分配數(shù)學模型為

式中:Q為水電站運行機組的發(fā)電總耗水量;n為機組數(shù);j為機組編號;cj為j號機組的開停機狀態(tài),取值0或1分別為機組關或開;Nj為j號機組的出力,即負荷;H為電站水頭;qj(Nj,H)為j號機組在水頭H、出力為Nj時的發(fā)電引用水量,通過由擬合得到的機組流量特性函數(shù)計算得到;P為系統(tǒng)對電廠的負荷要求;N1,maxj、N1,minj分別為水頭H下j號機組預想出力的上、下限;N2,maxj、N2,minj分別為水頭H下j號機組穩(wěn)定運行區(qū)的上、下限;Zs為水庫水位; Zs,min、Zs,max分別為水庫允許的最低水位和最高水位;Qmin、Qmax分別為水庫的最小和最大下泄流量;Zw為水庫尾水位,根據(jù)下泄流量與尾水位的關系曲線線性插值得到。

上述模型中機組運行工況約束不僅考慮了機組預想出力的限制,還考慮了避開空蝕振動區(qū)的需要。機組運行區(qū)一般劃分為空蝕振動區(qū)(包括禁止運行區(qū)和限制運行區(qū)兩部分)和穩(wěn)定運行區(qū),劃分需要依據(jù)機組機架振動、軸承擺度標準來確定。機組在禁止運行區(qū)運行時極易造成嚴重破壞;在限制運行區(qū)運行時存在一定程度的振動,長期運行可能會造成疲勞破壞;只有在穩(wěn)定運行區(qū)中機組才能長期連續(xù)穩(wěn)定安全運行。因此進行水電站廠內經濟運行研究時,為了保證機組的穩(wěn)定安全運行,必須避開機組的空蝕振動區(qū),使機組一直運行在穩(wěn)定運行區(qū)中。穩(wěn)定運行區(qū)的上、下限是一個與水頭H相關的區(qū)間,水頭不同,機組對應的穩(wěn)定運行區(qū)是不同的;而機組預想出力定義域也是一個與水頭H相關的區(qū)間,故可通過求交集的方式將式(3)和式(4)轉化為機組運行工況約束:

式中:Nmaxj、Nminj分別為水頭H下j號機組的可行區(qū)域上、下限,可行區(qū)域是水頭H下j號機組按照運行區(qū)劃分避開了空蝕振動區(qū)的區(qū)域。

2 Memetic算法

Memetic算法是Moscato等在1992年提出的,該算法是一種基于人類文化遺傳策略的群體智能優(yōu)化算法,其局部搜索對象并不是種群空間內的普通個體,而是在各局部區(qū)域選出的優(yōu)秀代表,但個體與個體之間的相互操作和遺傳算法的遺傳操作是相似的,因此,Memetic算法實質上是一種基于種群的全局搜索和基于個體的局部啟發(fā)式搜索的結合體[9-10]。圖1為Memetic算法的計算流程,Memetic算法采用的計算框架和操作流程與遺傳算法相似,但它不局限于單純的遺傳算法,該算法在每次交叉和變異后均進行局部搜索,通過及早剔除不良個體,優(yōu)化種群結構,加快了算法的收斂能力。

圖1 Memetic算法的計算流程

2.1 初始種群的生成

Memetic算法中,初始種群的分布性質對算法的收斂性能有一定的影響。考慮到水電站水輪機運行區(qū)劃分的特殊性,本文運用了一種有限制的初始種群生成法(以下簡稱有限制方法),在種群生成的過程中就將水輪機的出力直接限制在機組運行工況約束的最小、最大范圍內,如某機組的運行工況約束出力范圍為45～70 MW,那么其對應的出力取值范圍為45～70 MW。因此,初始種群中的個體滿足機組預想出力約束及避開空蝕振動區(qū)的要求。

機組出力編碼和機組出力計算公式分別為

式中:kij為第i個個體j號機組出力編碼;dt為控制精度即出力離散的步長;R為一個[0,1]的均勻隨機數(shù);int為取整函數(shù);Nij為第i個個體j號機組出力編碼對應的出力值。

2.2 適應度函數(shù)

水電站負荷優(yōu)化分配模型中的約束條件主要包含負荷平衡約束(等式約束)和運行工況約束(不等式約束)兩種。決策變量的運行工況約束即不等式約束采用有限制的方法處理。由于運行機組的總負荷不一定等于給定的負荷,因此負荷平衡約束包含在適應度函數(shù)中采用罰函數(shù)的方法來處理。適應度函數(shù)Fi表達式為

式中:W是一個較大的常數(shù);M為種群的個體數(shù);Ui為第i個母體所對應的式(1)和式(2)的增廣目標函數(shù)值,見式(12)。

當運行機組的總負荷大于系統(tǒng)給定的負荷時,由于罰函數(shù)的作用,增廣目標函數(shù)值Ui會增大;但當運行機組的總負荷小于系統(tǒng)給定的負荷時,由機組的流量特性曲線可知運行機組的總耗流量也會減小,這時適應度的大小難以判定,可能出現(xiàn)不滿足約束條件的非可行個體適應度高的現(xiàn)象,無法保證種群的收斂。因此,在運行機組的總負荷小于系統(tǒng)負荷時,在增廣目標函數(shù)中采用雙重懲罰的方法以保證種群收斂:

而對于約束條件中的水庫下泄流量約束、水庫下泄流量與尾水位關系約束及水庫水位約束等其他約束條件在編程計算的過程中進行了驗證,對不滿足約束的個體進行適當?shù)膽土P,讓其在迭代過程中被淘汰。

2.3 選擇策略

Memetic算法采用比例替換的選擇策略:①根據(jù)個體適應度高低對種群中的個體進行排序;②選出種群中排名靠后的PsM(Ps為選擇概率)個個體,再把排名靠前的PsM個個體復制一份;③用復制的排名靠前的PsM個個體替換排名靠后的PsM個個體。

比例替換的選擇策略一定程度上使算法在進化初期保持種群的多樣性且在進化的后期仍然具有對優(yōu)良個體的選擇能力,提高了算法的全局收斂性能。

2.4 交叉策略

在Memetic算法中,把經過選擇后的M個個體隨機地進行兩兩配對,配對的個體以交叉概率Pc按照算術交叉的方式進行交叉運算,從而得到新個體。交叉公式為

式中:kij、k(i+1)j分別為配對的兩個個體j號基因的編碼值;k′ij、k′(i+1)j分別為對應的交叉后得到的新個體j號基因的編碼值;α為(0,1)上的隨機數(shù)。

2.5 變異策略

Memetic算法采用非均勻的變異策略:對種群中的個體以變異概率Pm進行變異,在可以變異的個體染色體編碼串中隨機選取一個基因位,按下式對該基因位上的基因進行變異:

式中:kis、k′is為變異前后個體染色體編碼串基因位上的編碼值,s表示個體染色體編碼串中基因位的位置;mis,max、mis,min分別為參數(shù)取值的上、下限; rand(2)指隨機產生整數(shù)1或2;r為一個[0,1]的均勻隨機數(shù);t、g分別為當前進化代數(shù)和最大進化代數(shù);B是一個系統(tǒng)參數(shù),決定了隨機擾動對進化代數(shù)g的依賴程度。

2.6 局部搜索策略

局部搜索是指采用一定的操作策略,對染色體某些基因位進行部分改變,以優(yōu)化種群的分布結構,及早剔除不良個體。常用的局部搜索方法有爬山法、貪婪法、模擬退火法等,本文采用育種算法。該方法是一種局部搜索算法,其核心思想是模仿生物繁殖優(yōu)良品種,通過選種→繁殖→再選種→再繁殖,不斷選擇品質優(yōu)秀的種子,不斷繁殖,直到種子對應的函數(shù)值達到全局最大[12-13]。

3 實例應用

三峽水利樞紐工程是一個具有防洪、發(fā)電、航運等多項綜合效益的大型水利水電工程。三峽水電站裝配單機容量為70萬kW的混流式水輪發(fā)電機32臺,其中左岸電站裝配14臺,右岸電站裝配12臺,地下電站裝配6臺,另電源電站裝配單機容量為5萬kW的電源發(fā)電機組2臺,總裝機容量2250萬kW。本文僅對左岸和右岸的26臺單機容量為70萬kW的混流式水輪發(fā)電機組進行分析,從左岸到右岸,依次對其排序編號。

分別采用Memetic算法和遺傳算法優(yōu)化79 m水頭下三峽水電站的負荷分配,考慮空載耗流量,并以出力5 000 kW作為控制精度。79 m水頭下左岸VGS機組的穩(wěn)定運行區(qū)為43萬～69.5萬kW,左岸ALSTOM機組為46.5萬～68.5萬kW,右岸東電機組為41.5萬 ～66萬kW,右岸ALSTOM機組為45萬～70萬kW,右岸哈電機組為41萬～63.5萬kW。由于模擬運算的隨機性,對Memetic算法和遺傳算法優(yōu)化負荷分配的過程進行10次模擬,并取最好的一次作為最終優(yōu)化結果。對于算法中的參數(shù)交叉概率Pc和變異概率Pm,為了不影響算法的收斂性能,均采用參數(shù)自適應的思想進行調整[14]。為了便于比較,兩種算法中的選擇概率Ps均為0.3,種群規(guī)模均為200。

3.1 育種規(guī)模分析

對于育種規(guī)模,以三峽水電站79 m水頭下1720萬kW負荷為例,用Memetic算法分別優(yōu)化了相同計算工況下育種規(guī)模為種群規(guī)模10%～100%的情況。每種情況下搜索到的最小耗流量及搜索過程所需的時間隨育種規(guī)模的變化見圖2。由圖2可知,育種規(guī)模越大,搜索到的解越好,而所需的計算時間也越長?？紤]到算法實時性的要求,認為育種規(guī)模為種群規(guī)模的0.5時效果最好,因此,本文育種規(guī)模為100。

圖2 最小耗流量隨育種規(guī)模的變化曲線

3.2 終止迭代次數(shù)分析

同樣以三峽水電站79 m水頭下1720萬kW負荷為例,用Memetic算法分別以迭代100次、200次、300次、400次、500次、600次、700次及800次作為終止條件進行模擬,每個終止迭代次數(shù)下模擬得到的最小耗流量隨迭代次數(shù)的變化見圖3。由圖3可以看出,模擬得到的最小耗流量隨終止迭代次數(shù)的增加而減小,并最終趨于穩(wěn)定,以500次為界,小于500次時最小耗流量隨迭代次數(shù)的變化較大,而大于500次時最小耗流量幾乎沒有改變?？紤]到三峽水電站負荷優(yōu)化分配的復雜程度,并結合計算機的性能和程序計算時間,本文選擇500次作為終止迭代次數(shù)。

圖3 最小耗流量隨迭代次數(shù)的變化曲線

3.3 優(yōu)化結果及分析

為了比較算法的收斂性能,采用兩種算法在相同計算工況下優(yōu)化了三峽水電站79 m水頭下的不同負荷。表1為兩種算法優(yōu)化不同負荷的最小耗流量對比,最小耗流量為兩種算法10次模擬最好的一次尋優(yōu)結果。為了更直觀地體現(xiàn)Memetic算法的搜索性能,選擇兩種算法10次模擬結果中最好的一次,對比了其搜索100次、200次、300次、400次及500次的最優(yōu)適應度,結果見表2,并比較了其中兩種負荷(1350萬kW和1550萬kW)的優(yōu)化過程,如圖4和圖5所示,其他負荷的優(yōu)化過程類似。

表1 79 m水頭下兩種算法優(yōu)化不同負荷的最小耗流量對比

從表1可知,在相同的種群規(guī)模和迭代次數(shù)下,相比于遺傳算法,Memetic算法在不同負荷下模擬的最小耗流量均有不同程度的減小;由表2可看出,隨著迭代過程的推進,Memetic算法在不同負荷下模擬的最優(yōu)適應度基本呈增加的趨勢,而遺傳算法的最優(yōu)適應度大部分在進化到100代就不再增加了,在相同迭代次數(shù)下兩種算法的最優(yōu)適應度相差也越來越大;由圖4、圖5的關系曲線對比可以看出,遺傳算法在優(yōu)化負荷分配問題時,其目標函數(shù)值在進化到一定代數(shù)后就不再減小,相應的最優(yōu)適應度也不再增加,而Memetic算法的目標函數(shù)值隨迭代次數(shù)一直在減小,最優(yōu)適應度也一直在增加,直到進化后期慢慢逼近最優(yōu)解的過程中目標函數(shù)和最優(yōu)適應度的變化幅度越來越小,最后不再變化?？梢? Memetic算法模擬的結果明顯優(yōu)于遺傳算法,說明Memetic算法能以較快速度收斂至全局最優(yōu),而遺傳算法容易陷入局部最優(yōu)。這是由于遺傳算法在迭代過程中由于種群多樣性下降,最優(yōu)個體解比較早地出現(xiàn)收斂現(xiàn)象,易陷入局部最優(yōu),然而Memetic算法通過在最優(yōu)個體附近進行局部搜索,總能找到更好的個體,跳出局部最優(yōu),其最優(yōu)個體不易出現(xiàn)過早收斂現(xiàn)象,因此Memetic算法具有更強的收斂能力。

為了驗證本文有限制方法能夠保證所有運行機組的安全與穩(wěn)定,相同計算工況下,用基于傳統(tǒng)方法[6]考慮空蝕振動區(qū)的Memetic算法進行負荷優(yōu)化分配,其中1350萬kW和1550萬kW兩種負荷的最優(yōu)分配方案見圖6,負荷上、下限為機組運行工況約束的上、下限。其他負荷的最優(yōu)分配方案基本一致。

從圖6可看出,有限制方法得到的最優(yōu)分配方案中所有機組均在穩(wěn)定運行區(qū)中運行,而傳統(tǒng)方法求得的最優(yōu)分配方案中有少數(shù)機組運行在空蝕振動區(qū),這說明有限制方法能夠保證運行機組的穩(wěn)定與安全。

表2 兩種算法在不同迭代次數(shù)時的最優(yōu)適應度

圖4 目標函數(shù)值隨迭代次數(shù)的變化曲線

圖5 最優(yōu)適應度與迭代次數(shù)關系曲線

4 結 論

a.有限制方法能夠保證所有運行機組運行在穩(wěn)定運行區(qū)。

b.Memetic算法的交叉和變異策略繼承了遺傳算法的強全局搜索能力,能擴大尋優(yōu)范圍,提高算法的尋優(yōu)質量。

c.Memetic算法的局部搜索策略可以優(yōu)化種群分布,及早剔除不良個體,增強算法的局部尋優(yōu)能力。

d.育種的局部搜索法依靠種子隨機繁殖若干子代,且子代個體分散分布在可行空間的任意位置,能搜索到更好的解,使算法跳出局部最優(yōu),提高了算法的收斂性能。

[1]張勇傳.水電站經濟運行原理[M].北京:中國水利水電出版社,1998.

[2]何蘭蘭.水電站機組組合與負荷分配的短期經濟調度[D].武漢:華中科技大學,2006.

[3]周冉,楊侃,郝永懷,等.考慮空蝕振動區(qū)的水電站廠內經濟運行方法[J].中國農村水利水電,2011(6):153-155.(ZHOU Ran,YANG Kan,HAO Yonghuai,et al. Researchontheeconomicoperationmethodfor hydropower stations taking account of cavitation and vibration areas[J].China Rural Water and Hydropower, 2011(6):153-155.(in Chinese))

[4]薛鵬,曾季弟,林家洋,等.基于遺傳算法和運行區(qū)劃分的水電站廠內經濟安全運行分析[J].水力發(fā)電學報, 2010,29(6):13-18.(XIE Peng,ZENG Jidi,LIN Jiayang,et al.Study of internal economic operation based on GA and operation region partition[J].Journal of Hydroelectric Engineering,2010,29(6):13-18.(in Chinese))

[5]王黎,馬光文.基于遺傳算法的水電站廠內經濟運行新算法[J].中國電機工程學報,1998,18(1):64-66. (WANG Li,MA Guangwen.Genetic algorithm in hydro station economic dispatch[J].Proceeding of the CSEE, 1998,18(1):64-66.(in Chinese))

[6]張仁貢,韓桂芳,白家驄,等.遺傳算法在水電站廠內經濟運行中的應用[J].華北水利水電學院學報,2006,27 (1):61-64.(ZHANG Rengong,HAN Guifang,BAI Jiacong,et al.The application of genetic algorithm in inner-plant economical operation of hydropower station [J].JournalofNorthChinaInstituteofWater Conservancy and Hydroelectric Power,2006,27(1):61-64.(in Chinese))

圖6 機組負荷最優(yōu)分配方案

[7]劉國帥,楊侃,郝永懷,等.水庫短期優(yōu)化調度改進選擇算子的遺傳算法應用研究[J].中國農村水利水電, 2011(10):44-46.(LIU Guoshuai,YANG Kan,HAO Yonghuai,et al.Application of genetic algorithm based on advanced selection operator for short-term optimization operation of reservoir[J].China Rural Water and Hydropower,2011(10):44-46.(in Chinese))

[8]李崇浩,紀昌明,李文.微粒群算法在水電站廠內經濟運行中的應用研究[J].水利水電技術,2006,37(1): 88-91.(LI Chonghao,JI Changming,LI Wen.Study on application of particle swarm optimization to in-plant economic operation of hydropower station[J].Water Resources and Hydropower Engineering,2006,37(1):88-91.(in Chinese))

[9]劉文君.Memetic算法研究與工程應用[D].武漢:華中科技大學,2007.

[10]李智歡.基于新型Memetic算法的電力系統(tǒng)無功優(yōu)化研究[D].武漢:華中科技大學,2007.

[11]張慧.遺傳算法在水電站群經濟運行中的應用[D].南京:河海大學,2007.

[12]許必熙.育種算法簡介[J].大眾科技,2005(9):66-67.(XU Bixi.Breeding algorithms instruction[J]. Popular Science&Technology,2005(9):66-67.(in Chinese))

[13]田凱,許必熙.育種算法在組合優(yōu)化計算中的應用[J].安徽農業(yè)科學,2012,40(20):10361-10362.(TIAN Kai,XU Bixi.Breeding algorithm and its application to combinatorial optimization calculation[J].Journal of Anhui Agricultural Sciences,2012,40(20):10361-10362.(in Chinese))

[14]SRINIVAS M,PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems,Man and Cybernetics,1994,24 (4):656-667.

Application of Memetic algorithm to optimal load dispatch of hydropower station//

DENG Lili,YANG Kan,ZHOU Jiajia
(College of Hydrology and Water Resources,Hohai University,Nanjing 210098,China)

In this paper,we apply the Memetic algorithm,based on global search and local heuristic search,to the model of load distribution of hydropower station aiming to overcome problems such as the bad convergence and easy premature emerged frequently when dealing with optimal load dispatch of inner-plant economical operation of hydropower station.To do that,a method to overcome the problem of instable operation of hydropower station units is used to generate the initial population.Additionally,the local search strategy is based on breeding algorithm.Taking the inner-plant economical operation of Three Gorges Hydropower Station as a case study,the Memetic algorithm is compared with genetic algorithm. The results show that with the limited method to generate initial population,stable and safe operations of units are ensured by avoiding the influence of cavitation-vibration region.The global search and local search strategy are able to enlarge the searching range of the algorithm and optimize the population structure as well as improve the ability of convergence.

hydropower station;optimal load dispatch;inner-plant economical operation;Memetic algorithm;global search;local search

TV737;TV697.1

:A

:1006-7647(2014)05-0050-06

10.3880/j.issn.1006-7647.2014.05.010

2013-0722 編輯:熊水斌)

國家重點基礎研究發(fā)展計劃(973計劃)(2012CB417006);“十一五”國家科技支撐計劃(2009BAC56B03)

鄧麗麗(1990—),女,江西宜春人,碩士研究生,主要從事水庫(群)優(yōu)化調度與經濟運行研究。E-mail:denglili0312@126.com