基于逐次逼近遺傳算法的梯級水庫優(yōu)化調(diào)度

鄒 進

(昆明理工大學 電力工程學院，云南 昆明 650051)

遺傳算法是一種模擬自然基因和自然選擇機制的尋優(yōu)方法，自J.H.Holland于1975年首次提出以來［1］，已取得豐富的研究成果［2］，在水資源領(lǐng)域研究中的應用也相當廣泛［3］.在水庫運行管理中，遺傳算法主要應用于水庫(群)優(yōu)化調(diào)度［4－11］、水電站經(jīng)濟運行［12－14］、水火電混合系統(tǒng)經(jīng)濟調(diào)度［15－16］、水庫調(diào)度規(guī)則等方面［17－18］.與線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃、POA法等傳統(tǒng)優(yōu)化方法相比較，遺傳算法的優(yōu)點主要有:(1)全局搜索能力強，可以快速搜索出解空間中的全部解，而不會陷入局部最優(yōu)解的快速下降陷阱;(2)具有潛在并行性，可以方便地進行分布式計算，加快求解速度;(3)收斂性好，魯棒性高.但是，遺傳算法的局部搜索能力較差，在進化后期搜索效率較低;實際應用中，還容易產(chǎn)生“早熟”現(xiàn)象;并且尋優(yōu)效果受到許多可變參數(shù)的影響，如交叉率、變異率、種群大小等，而目前這些參數(shù)的選擇大部分仍依靠經(jīng)驗.針對這些缺點，產(chǎn)生了許多遺傳算法的改進方法，對編碼方式、控制參數(shù)的確定、選擇方式、交叉機理等方面都進行了改進.例如，使用自適應遺傳算子對交叉率、變異率等參數(shù)進行改進［8－9］;采用混合算法改善其搜索特性［10－12］;與混沌相結(jié)合來優(yōu)化初始解，改進變異算子［19］，等等.

總的來看，這些文獻中的遺傳算法都是在可行域中尋優(yōu)的，即初始解為可行解，經(jīng)過遺傳操作后產(chǎn)生的新個體若為不可行解，則對其進行修正;然而，在梯級調(diào)度中，由于梯級水庫間存在的水力電力聯(lián)系，使這種修正變得繁瑣，且容易陷入局部最優(yōu).因此，本文提出了逐次逼近遺傳算法，以一種漸近搜索的方式，使遺傳算法能夠在包括不可行解的空間中進行尋優(yōu)，并逐步找到全局最優(yōu)解.

1 逐次逼近遺傳算法

水庫調(diào)度實際上是一種過程優(yōu)化，需要使調(diào)度期內(nèi)的整體目標最大化，而不是某個時段的目標值最優(yōu).在用遺傳算法來求解單庫調(diào)度時，通常用浮點數(shù)編碼，其染色體長度即為調(diào)度期內(nèi)的時段數(shù);由于前后時段間存在水量平衡約束，前一時段泄水量的改變將影響后繼時段的用水策略，因此在經(jīng)過遺傳操作后，若新的個體不滿足約束條件，則需要對其進行修正.而在梯級水庫調(diào)度中，由于上下游水庫間具有密切的水力聯(lián)系，若某一級水庫的下泄流量發(fā)生了變化，可能使其下游所有水庫的調(diào)度方案發(fā)生變化.因此，利用遺傳算法進行優(yōu)化的時候，若代表上游水庫發(fā)電策略的染色體中的某一個(或某一段)基因產(chǎn)生了變化，則很可能使整個染色體所表示的解為不可行解，于是需要對該水庫的后續(xù)基因及下游水庫的相應基因進行調(diào)整，這種修正在庫群調(diào)度中是繁瑣困難的，且很容易陷入局部最優(yōu).因此，本文利用逐次逼近方法，使搜索空間不局限于可行解空間，而采用罰函數(shù)來淘汰不可行解，并通過逐次循環(huán)，使搜索空間不斷縮小，從而逐漸逼近全局最優(yōu)解.

如圖1(a)所示，初始循環(huán)時，其搜索空間為整個決策變量的可行域(即Xmax與Xmin之間的空間)，初始種群即為圖中的水平虛線;第2次及以后循環(huán)的搜索空間如圖1(b)所示，它由前一次循環(huán)的最優(yōu)解(圖中實線)加(減)1個變量所組成的廊道構(gòu)成(也即為修改后的Xmax與Xmin之間的空間)，其初始種群亦為圖中虛線所示.

圖1 初次循環(huán)及逐次循環(huán)的解空間與初始種群Fig.1 The space and initial population for the first time and successive cycle

逐次逼近遺傳算法的整體程序框圖如圖2所示.可以看出，相對于傳統(tǒng)遺傳算法，主要是增加了1個大循環(huán)及1個可變搜索空間.下面對一些主要參數(shù)的設(shè)置進行詳細討論.

(1)種群的初始化 由于遺傳算法是一種隨機搜索算法，因此種群的大小、結(jié)構(gòu)及其遍歷性對優(yōu)化結(jié)果均會產(chǎn)生影響.這里對初始解按下式賦值:

式中:i為時段編號;j為方案編號;Ininpop［i］［j］是種群中第j個染色體第i位基因的初始值，代表第i個時段(長期調(diào)度中一般指月或旬)決策變量(一般為庫水位或下泄流量)在第j個方案中的初始值;Xmin［i］為第i個時段決策變量的下限值;step［i］為第 i個時段的步長;Xmax［i］為第 i個時段決策變量的上限值;popsize為種群的大小.

(2)廊道大小的確定 如圖1(b)所示，決策變量上、下限 Xmax［i］與 Xmin［i］隨循環(huán)次數(shù)的改變而改變，其值為:

圖2 逐次逼近遺傳算法流程Fig.2 The flow chart of GASA

式中:Xbest［i］為前一輪遺傳算法所得i時段的最優(yōu)值;Width為廊道寬度，隨循環(huán)次數(shù)k而改變;Xmax［i］(1)與Xmin［i］(1)分別指第1次循環(huán)中決策變量的上、下限，例如，以庫水位為決策變量，則它們分別指正常蓄水位(汛期時為汛限水位)與死水位.

(3)最大循環(huán)次數(shù)與種群大小 最大循環(huán)次數(shù)maxrun的設(shè)定與問題復雜程度有關(guān)，在梯級調(diào)度中，可能設(shè)至上百次.種群大小對優(yōu)化結(jié)果的影響較大，設(shè)置過小搜索不到最優(yōu)解，過大則計算時間較長，具體值亦視問題的復雜程度而定，在梯級調(diào)度中，可能取到上千次.為了在保證一定精度的條件下減小運行時間，可用下式對種群大小進行更新:

式中:popsize(k)指第k次循環(huán)時種群的大小;maxpop指最大種群數(shù)，即為第一次循環(huán)時的種群數(shù);minpop指最小種群數(shù)，即為最后一次循環(huán)時的種群數(shù).

還需說明的是，maxrun與maxpop不宜設(shè)置過大，否則不僅影響計算速度，超過一定值后，它們對最優(yōu)解的貢獻也將很小.此外還有其他一些參數(shù)，如交叉率、變異率、一次循環(huán)的最大迭代次數(shù)等，均與常規(guī)遺傳算法無異，在此從略.

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

梯級水庫優(yōu)化調(diào)度模型的目標函數(shù)為:

式中:E為梯級總發(fā)電量;kj為電站j的綜合出力系數(shù);qfj，i為第j個水庫第i個月的發(fā)電流量(m3/s);Hj，i為第j個水庫第i個月的平均水頭(m);Δt為時段長，本文取1個月;T為年內(nèi)時段數(shù)，取T=12;n為梯級中所有水庫的個數(shù).

由于時段長度均為1個月，故式(5)可轉(zhuǎn)變?yōu)?

式中:N為出力.約束條件如下:

3 逐次逼近遺傳算法的求解步驟

現(xiàn)采用逐次逼近遺傳算法求解以上梯級水庫的優(yōu)化調(diào)度問題.參照圖2，主要步驟有:

(1)確定調(diào)度方案的基因編碼方式:一般使用浮點數(shù)編碼，則染色體形式為(x1，x2，…，xT×n)，其長度為T×n，T為時段數(shù);

(2)遺傳算法參數(shù)賦值，包括初始種群規(guī)模、交叉率、變異率、收斂精度、最大遺傳代數(shù)及最大循環(huán)次數(shù)等;

(3)按式(1)生成初始種群;

(4)計算當代種群中個體的適應度值:若以庫容為決策變量，則約束條件式(10)可以自然滿足;式(7)，(9)和(11)可合并為一個約束條件，以確定下泄流量qj，i;此時約束條件(8)就不一定可以滿足，采用罰函數(shù)法進行處理，即目標函數(shù)式(6)變?yōu)?

式中:α為罰系數(shù);

(5)進行遺傳操作:選擇、交叉、變異，生成新的種群;

(6)重復步驟(4)和(5)，直到滿足收斂條件或達到最大遺傳代數(shù)，產(chǎn)生一次循環(huán)的最優(yōu)調(diào)度方案;

(7)在前一次最優(yōu)方案的基礎(chǔ)上，由式(3)生成下一次尋優(yōu)的搜索空間，由式(4)更新種群大小;

(8)由式(1)生成下一次尋優(yōu)的初始種群;

(9)回到第(4)步，直到滿足收斂條件或達到最大循環(huán)次數(shù).

4 算例

某三級梯級水庫，水庫特征參數(shù)及年初庫水位如表1所示，由于有航運和灌溉任務(wù)，要求下泄流量不小于20 m3/s.表2為1個水文年的預報來水，要求調(diào)度期末水位為初始水位，試求出梯級水庫在該年的最優(yōu)調(diào)度方案.

表1 水電站的特征參數(shù)及初始條件Tab.1 The characteristic parameters of cascaded hydropower plants and the initial conditions

表2 某水文年月平均流量Tab.2 Monthly inflows of one hydrologic year m3·s－1

按上述的求解步驟進行優(yōu)化，取交叉率0.9，變異率0.1，收斂精度0.01，最大遺傳代數(shù)100，最大循環(huán)次數(shù)300，最大種群數(shù)1 500，最小種群數(shù)10，種群大小按式(5)進行更新.

計算結(jié)果見表3，作為比較，表中還列出了DDDP法與POA法的優(yōu)化結(jié)果.3種算法求得的水位變化過程線見圖3.

表3 3種優(yōu)化算法的結(jié)果比較Tab.3 Results comparison among GASA，DDDP and POA

圖3 3種算法所得的水位變化過程線Fig.3 The water level hydrographs by GASA，DDDP and POA

由表3可以看出，就梯級總發(fā)電量而言，GASA的結(jié)果較其他算法略高;而從圖3來看，由GASA所得的水位過程線變化較均勻，無大的跳躍;因此整體來看，GASA的優(yōu)化結(jié)果要好于其他兩種算法.這是因為遺傳算法理論上是一種全局尋優(yōu)的方法;并在遺傳算法每一次尋優(yōu)的基礎(chǔ)上增減一個廊道，以擴展尋優(yōu)空間，重構(gòu)初始解的結(jié)構(gòu)，這實際上打破了遺傳算法后期種群的單一性，避免了遺傳算法因種群單一性而陷入局部最優(yōu)解，從而有利于獲得全局最優(yōu)解.

通過以上算例，將GASA與其他傳統(tǒng)優(yōu)化算法進行對比，也說明了該算法在實際應用中的可行性與有效性，為梯級水庫的優(yōu)化調(diào)度提供了一條新的途徑.然而，從計算效率來看，GASA的運行時間遠多于其他算法，這雖然在離線計算的水庫長期優(yōu)化調(diào)度中尚可容許，但也是該算法需要改進的地方.

5 結(jié)語

本文在離散微分動態(tài)規(guī)劃(DDDP)中逐次逼近的思想下，結(jié)合遺傳算法的基本原理，提出了逐次逼近遺傳算法，其特點是可以在包含不可行解的空間中尋優(yōu);并通過算例驗證了該方法在梯級水庫調(diào)度中的有效性.同時由于逐次逼近遺傳算法不受目標函數(shù)性質(zhì)與約束條件的限制，也可通用于其他領(lǐng)域的優(yōu)化問題.但是該算法運行時間較長，這也是它需要進一步改進的地方.

［1］HOLLAND J H.Adaptation in natural and artificial systems［M］.MIT Press，1975.

［2］王小平，曹立明.遺傳算法——理論、應用與軟件實現(xiàn)［M］.西安:西安交通大學出版社，2002.(WANG Xiao-ping，CAO Li-ming.Genetic algorithm——theory，application and software realization［M］.Xi'an:Xi'an Jiaotong University Press，2002.(in Chinese))

［3］楊薇，南軍，孫德智，等.遺傳算法在水資源與水環(huán)境研究中的應用綜述［J］.水資源保護，2007，23(1):13-16.(YANG Wei，NAN Jun，SUN De-zhi，et al.Application of genetic algorithm in the fields of water resources and water environment［J］.Water Resources Protection，2007，23(1):13-16.(in Chinese))

［4］HAKIMI-ASIABAR M，GHODSYPOUR S H，KERACHIAN R.Deriving operating policies for multi-objective reservoir systems:application of self-learning genetic algorithm［J］.Appl Soft Comput J，2010，10(4):1151-1163.

［5］王萬良，周慕遜，管秋，等.基于遺傳算法的小水電站優(yōu)化調(diào)度方法的研究與實踐［J］.水力發(fā)電學報，2005，24(3):6-11.(WANG Wan-liang，ZHOU Mu-xun，GUAN Qiu，et al.Research and practice of optimum algorithm for small operation method based on genetic hydropower stations［J］.Journal of Hydroelectric Engineering，2005，24(3):6-11.(in Chinese))

［6］暢建霞，黃強，王義民.基于改進遺傳算法的水電站水庫優(yōu)化調(diào)度［J］.水力發(fā)電學報，2001(3):85-90.(CHANG Jianxia，HUANG Qiang，WANG Yi-min.Optimal operation of hydropower station reservoir by using an improved genetic algorithm［J］.Journal of Hydroelectric Engineering，2001(3):85-90.(in Chinese))

［7］陳立華，梅亞東，董雅潔，等.改進遺傳算法及其在水庫群優(yōu)化調(diào)度中的應用［J］.水利學報，2008，39(5):550-556.(CHEN Li-hua，MEI Ya-dong，DONG Ya-jie，et al.Improved genetic algorithm and its application in optimal dispatch of cascade reservoir［J］.Journal of Hydraulic Engineering，2008，39(5):550-556.(in Chinese))

［8］萬星，周建中.自適應對稱調(diào)和遺傳算法在水庫中長期發(fā)電調(diào)度中的應用［J］.水科學進展，2007，18(4):598-603.(WAN Xing，ZHOU Jian-zhong.Application of genetic algorithm for self adaptation，symmetry and congruity in reservoir midlong hydraulic power operation［J］.Advances in Water Science，2007，18(4):598-603.(in Chinese))

［9］王少波，解建倉，孔珂.自適應遺傳算法在水庫優(yōu)化調(diào)度中的應用［J］.水利學報，2006，37(4):480-485.(WANG Shao-bo，XIE Jian-cang，KONG Ke.Application of adaptive genetic algorithm in optimization of reservoir operation［J］.Journal of Hydraulic Engineering，2006，37(4):480-485.(in Chinese))

［10］劉衛(wèi)林，董增川，王德智.混合智能算法及其在供水水庫群優(yōu)化調(diào)度中的應用［J］.水利學報，2007，38(12):1437-1443.(LIU Wei-lin，DONG Zeng-chuan，WANG De-zhi.Hybrid intelligent algorithm and its application in dispatch optimization for water supply reservoir group［J］.Journal of Hydraulic Engineering，2007，38(12):1437-1443.(in Chinese))

［11］劉攀，郭生練，雒征，等.求解水庫優(yōu)化調(diào)度問題的動態(tài)規(guī)劃——遺傳算法［J］.武漢大學學報:工學版，2007，40(5):1-6.(LIU Pan，GUO Sheng-lian，LUO Zheng，et al.Optimization of reservoir operation by using dynamic programming——genetic algorithm［J］.Engineering Journal of Wuhan University，2007，40(5):1-6.(in Chinese))

［12］晉健，馬光文，陶春華.基于退火遺傳算法的水電站短期優(yōu)化調(diào)度［J］.水力發(fā)電學報，2008，27(6):18-21.(JIN Jian，MA Guang-wen，TAO Chun-hua.Short-term optimal operation of hydropower station based on annealing genetic algorithm［J］.Journal of Hydroelectric Engineering，2008，27(6):18-21.(in Chinese))

［13］周慕遜，王萬良，羅云霞.遺傳算法在水電站機組優(yōu)化組合中的研究與應用［J］.水力發(fā)電學報，2008，27(5):5-9.(ZHOU Mu-xun，WANG Wan-liang，LUO Yun-xiao.Research on application of genetic algorithm for unit optimized combination［J］.Journal of Hydroelectric Engineering，2008，27(5):5-9.(in Chinese))

［14］姜鐵兵，梁年生，康玲，等.用遺傳法確定水電站自動發(fā)電計劃［J］.水力發(fā)電學報，1995(4):7-14.(JIANG Tie-bing，LIANG Nian-sheng，KANG Ling，et al.Automatic generation schedules control by using genetic algorithm［J］.Journal of Hydroelectric Engineering，1995(4):7-14.(in Chinese))

［15］LAKSHMINARASIMMAN L，SUBRAMANIAN S.A modified hybrid differential evolution for short-term scheduling of hydrothermal power systems with cascaded reservoirs［J］.Energy Conversion and Management，2008，49:2513-2521.

［16］WONG S Y W.Hybrid simulated annealing/genetic algorithm approach to short-term hydro-thermal scheduling with multiple thermal plants［J］.Electrical Power and Energy Systems，2001，23(7):565-575.

［17］尹正杰，胡鐵松，崔遠來，等.水庫多目標供水調(diào)度規(guī)則研究［J］.水科學進展，2005，16(6):875-880.(YIN Zhengjie，HU Tie-song，CUI Yuan-lai，et al.Reservoir operation rule for multipurpose water supply［J］.Advances in Water Science，2005，16(6):875-880.(in Chinese))

［18］王東全，李承軍，張銘.基于遺傳算法的水庫中長期調(diào)度函數(shù)研究［J］.水力發(fā)電，2006，32(10):92-94.(WANG Dong-quan，LI Cheng-jun，ZHANG Min.Research on the function of reservoir long-term operation based on genetic algorithms［J］.Water Power，2006，32(10):92-94.(in Chinese))

［19］王文川，程春田，徐冬梅.基于混沌遺傳算法的水電站優(yōu)化調(diào)度模型及應用.水力發(fā)電學報，2007，26(6):7-11.(WANG Wen-chuan，CHENG Chun-tian，XU Dong-mei.The optimal operation model based on chaos genetic algorithm for hydropower station and its application［J］.Journal of Hydroelectric Engineering，2007，26(6):7-11.(in Chinese))