遺傳算法在水庫(kù)調(diào)度中的應(yīng)用綜述

1、第26卷第4期水利水電科技進(jìn)展2006年8月Vol.26No.4A dvances in Science and Technology o f Water Reso ur ces Au g.2006基金項(xiàng)目:國(guó)家重大基礎(chǔ)研究前期研究資助項(xiàng)目(2003C C A00200;湖北省自然科學(xué)基金資助項(xiàng)目(2005AB A315作者簡(jiǎn)介:劉攀(1978,男,湖南湘潭人,講師,博士,從事水文及水資源開發(fā)利用研究。E 2mail:liupan遺傳算法在水庫(kù)調(diào)度中的應(yīng)用綜述劉 攀,郭生練,李 瑋,易松松(武漢大學(xué)水資源與水電工程科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430072摘要:簡(jiǎn)要回顧了遺傳算法在水庫(kù)調(diào)度中的

2、應(yīng)用概況,對(duì)遺傳算法用于水庫(kù)調(diào)度優(yōu)化時(shí)的編碼、約束條件處理、早熟與全局收斂性、參數(shù)設(shè)置、混合遺傳算法、多目標(biāo)遺傳算法以及效率評(píng)定準(zhǔn)則等問題進(jìn)行了綜述。分析遺傳算法耗時(shí)與全局收斂之間的矛盾后認(rèn)為,遺傳算法適用于傳統(tǒng)方法難以求解的優(yōu)化問題,以及對(duì)計(jì)算時(shí)效性要求不高或者目標(biāo)函數(shù)計(jì)算復(fù)雜度不高的實(shí)時(shí)水庫(kù)調(diào)度問題,特別是水庫(kù)中長(zhǎng)期調(diào)度以及水資源規(guī)劃問題。關(guān)鍵詞:水庫(kù)調(diào)度;遺傳算法;綜述中圖分類號(hào):TV697.1+1 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1006O 7647(200604O 0078O 06A r eview of application of genetic algor ithm to r ese

3、r voir oper ation/LIU Pan,G U O Sheng 2lian,LI W ei,YI Song 2song (State Key L a b orato ry o f W ater Resou rces an d Hydro po wer Enginee rin g Science,W uhan U nivers ity,W uhan 430072,ChinaAbstr act :W ith regard to some problems in applicatio n o f the genetic algo rith m to opti mal operation

4、of reserv oirs,including coding,treatment of restraint conditi ons,prematurity and global convergence,parameter setting,hy brid genetic al gorithm,multi 2objective genetic algori thm,and criterion for efficiency evaluation,some special methods were review ed and discussed.Based on an analysis of the

5、 contradiction between time consumptio n and global co nvergence,i t is considered that the genetic alg orithm is much more suitable for the opti mization problem difficult to be solved by the co nv enti onal method,and the real 2time reservoir operatio n problem wi th lo w requirement fo r time 2ef

6、fectiveness o f calculation and lo w co mplexity in o bjecti ve function calculation.Mo reov er ,the genetic algori thm is especially sui table fo r middle 2and long 2term reservoir operatio n and planning fo r water resources.Key wor ds :reserv oir operation;genetic algori thm;review水庫(kù)調(diào)度技術(shù)傳統(tǒng)而復(fù)雜,20世

7、紀(jì)50年代以來(lái),以線性規(guī)劃、動(dòng)態(tài)規(guī)劃等為代表的優(yōu)化方法在水庫(kù)調(diào)度中得到了廣泛的應(yīng)用,幾十年的應(yīng)用表明,這些傳統(tǒng)的優(yōu)化方法都存在一定的局限性1O 2。遺傳算法(genetic algorithm是一種基于模擬自然基因和自然選擇機(jī)制的尋優(yōu)方法,該方法按照/擇優(yōu)汰劣0的法則,將適者生存與自然界基因變異、繁衍等規(guī)律相結(jié)合,采用隨機(jī)搜索,以種群為單位,根據(jù)個(gè)體的適應(yīng)度進(jìn)行選擇、交叉及變異等操作,最終可達(dá)到收斂于全局最優(yōu)解的目的3。遺傳算法主要特點(diǎn)有4:¹適應(yīng)性強(qiáng);º全局優(yōu)化;»編碼特征;¼概率搜索;½隱含并行性;¾自適應(yīng)性;¿算法簡(jiǎn)單

8、,通用性好;À應(yīng)用廣泛等。鑒于這些特點(diǎn),遺傳算法在水庫(kù)(群優(yōu)化調(diào)度(尋求最優(yōu)調(diào)度軌跡5O 29、水電廠經(jīng)濟(jì)運(yùn)行30O 35、水火電混合系統(tǒng)經(jīng)濟(jì)調(diào)度36O 37、水庫(kù)調(diào)度規(guī)則38O 51等領(lǐng)域中得到了廣泛的應(yīng)用,給現(xiàn)代水庫(kù)調(diào)度技術(shù)注入了活力與生機(jī)。1 用于水庫(kù)調(diào)度的遺傳算法設(shè)計(jì)問題111 編碼策略在設(shè)計(jì)遺傳算法時(shí),可通過編碼實(shí)現(xiàn)從優(yōu)化變量到染色體個(gè)體的映射。編碼策略直接影響到計(jì)算精度與所需時(shí)間,需結(jié)合具體問題進(jìn)行編碼。一般地,編碼可遵循以下原則:a.在優(yōu)化實(shí)數(shù)變量時(shí),盡量采用浮點(diǎn)編碼。遺傳算法的編碼一般可以分為二進(jìn)制編碼、格雷編碼、整數(shù)編碼、浮點(diǎn)編碼以及混合編碼等。其中二進(jìn)制編碼概念清

9、晰,但離散數(shù)目一定是2n -1個(gè),即離散數(shù)目呈倍數(shù)增長(zhǎng),因而難于選擇恰當(dāng)?shù)碾x散數(shù)目:離散數(shù)目太多則搜索空間太大,太少則達(dá)不到精度要求39,因此往往存在編碼冗余問題10;整數(shù)編碼無(wú)需轉(zhuǎn)化成二進(jìn)制,但與二進(jìn)制編碼一樣,仍需將優(yōu)化變量按一定步長(zhǎng)進(jìn)行離散;浮點(diǎn)編碼可直接表征優(yōu)化變量,計(jì)算精度高。在預(yù)設(shè)調(diào)度規(guī)則的水庫(kù)防洪優(yōu)化調(diào)度中,為了優(yōu)化調(diào)度規(guī)則中的4個(gè)參數(shù),分別采用浮點(diǎn)編碼和二進(jìn)制編碼設(shè)計(jì)遺傳算法,經(jīng)比較防洪效益均值和方差,得出了浮點(diǎn)編碼優(yōu)于二進(jìn)制編碼的結(jié)論,其原因在于:¹浮點(diǎn)編碼可直接反映變量,映射實(shí)數(shù)空間的任意實(shí)數(shù),而二進(jìn)制編碼等則受編碼長(zhǎng)度限制,計(jì)算精度往往不及浮點(diǎn)編碼高;º

10、;基于浮點(diǎn)編碼的遺傳算法實(shí)際上利用了目標(biāo)的梯度信息,因而收斂速度快39。在四水庫(kù)群的優(yōu)化調(diào)度計(jì)算中,通過比較分析,得出了浮點(diǎn)編碼優(yōu)于二進(jìn)制編碼和格雷編碼的結(jié)論8。類似的研究表明,在水庫(kù)優(yōu)化調(diào)度計(jì)算中,整數(shù)編碼要優(yōu)于二進(jìn)制編碼,主要原因是:¹二進(jìn)制編碼容易擴(kuò)大搜索空間;º將二進(jìn)制轉(zhuǎn)換成整數(shù)時(shí)浪費(fèi)了計(jì)算時(shí)間12。對(duì)于優(yōu)化變量是實(shí)數(shù)的問題,一般可選擇浮點(diǎn)編碼;如果采用二進(jìn)制編碼或整數(shù)編碼,則需要權(quán)衡計(jì)算精度和計(jì)算復(fù)雜度(時(shí)間之間的關(guān)系,選擇合適的染色體長(zhǎng)度。對(duì)于0O 1規(guī)劃或者整數(shù)規(guī)劃,仍需采用二進(jìn)制編碼或整數(shù)編碼。此外,借助于基因顯性機(jī)制的二倍體遺傳算法,可利用二倍體基因結(jié)構(gòu)具

11、有內(nèi)在的保護(hù)群體基因多樣性的能力,提高算法的全局尋優(yōu)能力7。b.優(yōu)化變量最少原則。優(yōu)化變量越少,則計(jì)算搜索空間越小,算法也就越容易收斂。遺傳算法的優(yōu)化變量既可是整數(shù),也可是非整數(shù)實(shí)數(shù),還可兩者皆有(混合規(guī)劃。實(shí)際應(yīng)用中編碼有較大的技巧性,可根據(jù)具體問題的特點(diǎn),選擇合適的編碼方式來(lái)簡(jiǎn)化問題,即通過減少優(yōu)化變量數(shù)來(lái)降低問題的復(fù) 雜程度。圖1 每旬一個(gè)變量表示調(diào)度線在水庫(kù)調(diào)度線優(yōu)化中,可采用兩種方法進(jìn)行編碼:¹每個(gè)時(shí)段(旬采用一個(gè)實(shí)數(shù)來(lái)代表該時(shí)段的調(diào)度線特征值(圖1;º預(yù)設(shè)調(diào)度線的形狀,通過遺傳算法確定關(guān)鍵點(diǎn)的參數(shù)(圖247。在實(shí)例研究中,時(shí)段長(zhǎng)度為旬,方法¹的優(yōu)化變量

12、多達(dá)36個(gè),而方法º中,如果汛期只有一個(gè)分段,則僅需確定A D 點(diǎn)的坐標(biāo),因此僅有8個(gè)優(yōu)化變量,其中還有4 個(gè)圖2 采用關(guān)鍵點(diǎn)表示調(diào)度線是整數(shù)。此外,方法º避免了水位的波動(dòng),較為符合實(shí)際情況,也便于實(shí)際操作。計(jì)算結(jié)果表明,按照方法º進(jìn)行編碼明顯優(yōu)于方法¹。Chen43在水庫(kù)長(zhǎng)期調(diào)度中,雖然采用圖2的形式預(yù)定義調(diào)度線形狀,但A D 點(diǎn)的橫坐標(biāo)均采用浮點(diǎn)編碼而不是整數(shù)編碼,增大了搜索空間,可能造成編碼冗余。Huang 等51在水庫(kù)干旱預(yù)警系統(tǒng)中采用方法º得到了較好的計(jì)算結(jié)果。在三峽水庫(kù)圍堰發(fā)電期泄洪閘門優(yōu)化調(diào)度問題中,由于相同類型的閘門有很多,因此

13、對(duì)各泄洪閘門(全開或全關(guān)不是采用0O 1變量編碼,而是將各相同類型的閘門開啟臺(tái)數(shù)進(jìn)行編碼20。這樣可反映同種泄流設(shè)備啟閉時(shí),是開啟的總臺(tái)數(shù)決定調(diào)度方式,而與具體哪一個(gè)泄流設(shè)備以及其組合方式無(wú)關(guān)。對(duì)于23孔深孔,如果采用0O 1編碼,則搜索空間達(dá)223個(gè);而按照開啟的總臺(tái)數(shù)編碼,則搜索空間僅為24(023個(gè)。因此,這種編碼方法可減少冗余編碼,提高算法效率。c.盡量考慮問題的約束條件。在采用遺傳算法求解優(yōu)化問題時(shí),如果在編碼中就考慮到某些約束條件,可使父代經(jīng)過交叉、變異等操作,生成的新個(gè)體仍然滿足這些約束條件,因而無(wú)需進(jìn)行多余、不可行的計(jì)算,可提高算法的計(jì)算效率。對(duì)于圖2的A 點(diǎn)和D 點(diǎn),它們的水

14、位值應(yīng)該相等,這樣方可保證水位的連續(xù)性;同樣B,C 兩點(diǎn)的水位值也應(yīng)相等。在此約束條件下,優(yōu)化變量進(jìn)一步簡(jiǎn)化為6個(gè)47。在泄洪閘門控制問題中,導(dǎo)流底孔為22個(gè),為了滿足對(duì)稱啟閉條件,它在編碼時(shí)取值為011,在解碼時(shí)乘2得到實(shí)際的開啟孔數(shù)20。這樣不僅滿足了對(duì)稱啟閉的約束,還減小了問題的搜索空間。d.利用先驗(yàn)知識(shí)。遺傳算法初始編碼一般隨機(jī)確定,往往造成尋優(yōu)過程復(fù)雜耗時(shí)。在考慮電網(wǎng)分時(shí)電價(jià)時(shí),各時(shí)段機(jī)組的運(yùn)行方式具有一定的規(guī)律性,在效益大的時(shí)段多發(fā)電,引用流量也越大,因此可利用這一先驗(yàn)知識(shí),根據(jù)各個(gè)時(shí)段的發(fā)電效益不同引入各時(shí)段的權(quán)重系數(shù)構(gòu)造初始遺傳編碼25。112約束條件處理水庫(kù)調(diào)度中存在較多的約

15、束條件,雖然在編碼中可對(duì)其中的部分約束條件給予考慮,但這種方法不具有通用性。常用的約束條件與處理方法有:a.懲罰函數(shù)法。懲罰函數(shù)法是較通用的約束處理方法,可通過適當(dāng)修改目標(biāo)函數(shù)實(shí)現(xiàn)。但懲罰函數(shù)法的效率一般較低,懲罰系數(shù)難于確定:當(dāng)懲罰系數(shù)太小時(shí),算法可能收斂于不可行解;而懲罰系數(shù)太大時(shí),又會(huì)使算法較早地收斂于某個(gè)局部最優(yōu)解。為解決這一矛盾,可采用變量懲罰法,使懲罰系數(shù)隨著進(jìn)化代數(shù)的增加而動(dòng)態(tài)增大12,18。b.出庫(kù)流量上下界、水庫(kù)庫(kù)容上下界約束處理。在水庫(kù)優(yōu)化調(diào)度問題中,約束條件一般包括出庫(kù)流量上下界、水庫(kù)庫(kù)容上下界等,而這兩者又通過水量平衡方程相互關(guān)聯(lián),因此在處理此類條件時(shí),需要綜合這三方面

16、的因素,對(duì)出庫(kù)(發(fā)電流量上下界進(jìn)行標(biāo)定,然后從中隨機(jī)產(chǎn)生個(gè)體,使之易于滿足出庫(kù)(發(fā)電流量的上下界約束以及水庫(kù)庫(kù)容的上下界約束5,21。c.總水量限制約束。水庫(kù)優(yōu)化調(diào)度問題一般給定始末狀態(tài),這樣就限制了總出庫(kù)水量,若選擇各時(shí)段出庫(kù)流量作為優(yōu)化變量,給定調(diào)度末水位(狀態(tài)作為邊界條件時(shí),采用遺傳算法優(yōu)化往往難于找到滿足該邊界條件(調(diào)度末水位指定的可行解?？刹捎脙煞N方法處理該約束:¹將嚴(yán)格等式約束松弛為不等式約束21。發(fā)電調(diào)度末水位越高,則越有利于以后時(shí)段的發(fā)電,將嚴(yán)格等式要求松弛為不低于指定的調(diào)度末水位這一不等式,便于找到問題的可行解,提高算法效率;º如果計(jì)算周期內(nèi)總水量超過限制

17、水量,可將超出的水量通過等比例法來(lái)修正各優(yōu)化變量25。113早熟與全局收斂性標(biāo)準(zhǔn)遺傳算法容易早熟,理論上也不能保證算法的全局收斂性。防止早熟的主要方法是保持群體的多樣性,目前對(duì)種群的多樣性評(píng)價(jià)指標(biāo)包括方差、熵、種群個(gè)體最優(yōu)適應(yīng)度與平均適應(yīng)度的差值以及高于平均適應(yīng)度的個(gè)體均值與最優(yōu)個(gè)體的差值等17。保持群體多樣性的方法主要有:¹引入共享函數(shù)限制相似個(gè)體在群體中的生長(zhǎng)3,48;º將父代和子代合并,一起進(jìn)行選擇以增加群體的多樣性18;»在進(jìn)化過程中引入混沌序列,充分利用其對(duì)初值的敏感性、遍歷性和隨機(jī)性,抑制/早熟0收斂13;¼采用兩個(gè)種群的偽并行遺傳算法35。

18、為了保證遺傳算法的全局收斂性,可采用如下方法進(jìn)行改進(jìn):¹進(jìn)化過程中保留最優(yōu)個(gè)體18,36;º采用倍體遺傳算法7。同時(shí),可針對(duì)具體問題,改進(jìn)適應(yīng)度函數(shù)、選擇策略、交叉策略以及變異策略等,構(gòu)造加速遺傳算法。114參數(shù)設(shè)置由于遺傳算法中大的群體規(guī)模與少的計(jì)算量要求之間、高的變異概率與算法的收斂性要求之間存在固有的矛盾,導(dǎo)致了遺傳算法的控制參數(shù)設(shè)置復(fù)雜,尚無(wú)簡(jiǎn)明統(tǒng)一的指導(dǎo)原則3?？刂茀?shù)的設(shè)置主要依靠試算,即通過多次計(jì)算得到相對(duì)合理的參數(shù)值。為解決靜態(tài)參數(shù)的缺陷,可根據(jù)進(jìn)化次數(shù),動(dòng)態(tài)地調(diào)整交叉或變異概率:¹根據(jù)與最優(yōu)個(gè)體的差異24,36,或者種群的多樣性指標(biāo)17,實(shí)現(xiàn)交叉

19、概率、變異概率的自適應(yīng)變化,即種群的差異越大,則交叉概率越大,變異概率越小;º在同一代種群中,設(shè)置不同個(gè)體的交叉、變異概率與適應(yīng)度呈線性關(guān)系,以此進(jìn)行交叉、變異概率的自適應(yīng)調(diào)整22。115混合遺傳算法a.增加局部搜索的混合遺傳算法。遺傳算法長(zhǎng)于全局尋優(yōu),但局部搜索能力不足;而基于梯度的搜索方法可彌補(bǔ)這一缺陷。因此,在遺傳算法中嵌入局部搜索,可大大提高算法的效率,主要方法有:¹利用每一代群體中的最劣個(gè)體的信息,計(jì)算梯度值,將傳統(tǒng)的下降搜索算子嵌入遺傳算法中21;º根據(jù)進(jìn)化代數(shù),動(dòng)態(tài)地進(jìn)行非均勻變異,使得算法在后期進(jìn)行局部搜索26;»在進(jìn)化中引入擬梯度以加速

20、進(jìn)化過程,同時(shí)在擬梯度的基礎(chǔ)上對(duì)高斯變異加以改進(jìn)構(gòu)成新的遺傳變異算子,構(gòu)造出擬梯度遺傳算法31;¼在進(jìn)化過程中引入混沌序列,同時(shí)對(duì)變異算子加以改進(jìn),構(gòu)造出一種自適應(yīng)誤差反向傳播變異算子,形成混沌雜交進(jìn)化算法13;½采用模擬退火算法改進(jìn)局部搜索能力27,或者將模擬退火算法和遺傳算法相結(jié)合,構(gòu)成并行組合模擬退火算法28。此種混合遺傳算法具有較強(qiáng)的通用性,容易移植處理其他優(yōu)化問題。b.優(yōu)化部分關(guān)鍵參數(shù)的遺傳算法。遺傳算法具有全局收斂能力,但需要較長(zhǎng)的計(jì)算時(shí)間。在處理大規(guī)模問題中,折中的辦法是采用遺傳算法優(yōu)化一部分參數(shù)。例如:¹對(duì)于水庫(kù)群隨機(jī)動(dòng)態(tài)規(guī)劃問題,在確定了各水庫(kù)的

21、分配系數(shù)之后,可計(jì)算每個(gè)水庫(kù)的需水量,由此將水庫(kù)群分解為單個(gè)水庫(kù)的隨機(jī)動(dòng)態(tài)規(guī)劃問題,此時(shí)采用遺傳算法優(yōu)化水庫(kù)的分配系數(shù),使得整個(gè)庫(kù)群的缺水量最小19;º在基于神經(jīng)模糊網(wǎng)絡(luò)的水庫(kù)調(diào)度規(guī)則中,通過擬合最優(yōu)調(diào)度過程的方法得到了神經(jīng)網(wǎng)絡(luò)調(diào)度規(guī)則,然后采用遺傳算法優(yōu)化一部分調(diào)度規(guī)則參數(shù),進(jìn)一步優(yōu)化神經(jīng)網(wǎng)絡(luò),使得輸出的方差(不確定性變小46;»在復(fù)雜的非線性水庫(kù)群管理問題中,通過分析抽取復(fù)雜變量,余下的問題可簡(jiǎn)化為一線性規(guī)劃問題,遺傳算法則用于對(duì)復(fù)雜變量的優(yōu)化14;¼在水電廠內(nèi)經(jīng)濟(jì)運(yùn)行問題中,采用動(dòng)態(tài)規(guī)劃在空間分配機(jī)組負(fù)荷,而遺傳算法在時(shí)間上分配機(jī)組組合32。此種混合遺傳算法

22、針對(duì)具體問題,可大大簡(jiǎn)化優(yōu)化計(jì)算的復(fù)雜度,但一般不具通用性,難于移植。116多目標(biāo)遺傳算法水庫(kù)調(diào)度問題有多目標(biāo)特征,遺傳算法是以種群為進(jìn)化單位的一種尋優(yōu)算法,因此最終計(jì)算結(jié)果既可以是一個(gè)最優(yōu)值,也可以是一個(gè)解集,這恰好合乎非劣解集的特點(diǎn)。在設(shè)定了多目標(biāo)的排序規(guī)則后,可計(jì)算多目標(biāo)問題的適應(yīng)度函數(shù)值,從而構(gòu)造多目標(biāo)遺傳算法,優(yōu)化計(jì)算可一次性獲得問題的非劣解集22,29?？梢?多目標(biāo)遺傳算法在尋求水庫(kù)優(yōu)化調(diào)度問題的非劣解集方面具有獨(dú)特的優(yōu)勢(shì)。117遺傳算法效率評(píng)定準(zhǔn)則在遺傳算法優(yōu)化計(jì)算中,由于其隨機(jī)搜索的特點(diǎn),初始化得到的解就有可能已經(jīng)非常接近最優(yōu)解,因此,僅僅依靠某特定條件下遺傳算法得到了較優(yōu)的計(jì)

23、算結(jié)果,就認(rèn)為該方法具有強(qiáng)的全局搜索能力或者很快的收斂速度,往往不能客觀、真實(shí)地評(píng)價(jià)算法效率?？刹捎脙煞矫娴闹笜?biāo)評(píng)價(jià)遺傳算法的性能:a.最優(yōu)性。對(duì)于很多實(shí)際問題,往往無(wú)法獲知理論全局最優(yōu)解,論證最優(yōu)性可通過比較遺傳算法和其他算法結(jié)果的優(yōu)劣來(lái)評(píng)價(jià)。尋求理論上的最優(yōu)解對(duì)于很多問題并沒有太大的實(shí)際意義,只要保證得到的解較傳統(tǒng)方法(如動(dòng)態(tài)規(guī)劃法有所改進(jìn),就可以接受,或者認(rèn)為遺傳算法具有最優(yōu)性。b.穩(wěn)健性。評(píng)價(jià)遺傳算法的效率時(shí),不僅僅需要考究多次計(jì)算值的均值,還需要評(píng)價(jià)它們的離散程度:如果對(duì)于同一問題,可能出現(xiàn)很好的結(jié)果,也可能出現(xiàn)很差的結(jié)果,則該算法能否在實(shí)際中應(yīng)用,需進(jìn)一步分析?？山o定迭代次數(shù),分析

24、多次計(jì)算結(jié)果的離散程度,用以評(píng)價(jià)算法的穩(wěn)健性17,21,24。2宜用遺傳算法處理的水庫(kù)調(diào)度問題211耗時(shí)與最優(yōu)解雖然理論上大部分遺傳算法能收斂于全局最優(yōu)解,但一般需耗用相當(dāng)長(zhǎng)的計(jì)算時(shí)間,因此,計(jì)算時(shí)間是遺傳算法應(yīng)用中的關(guān)鍵問題42。在中小規(guī)模的優(yōu)化計(jì)算中(優(yōu)化變量在100個(gè)以內(nèi),如果目標(biāo)函數(shù)不太復(fù)雜,遺傳算法的優(yōu)化結(jié)果往往優(yōu)于傳統(tǒng)方法,計(jì)算時(shí)間也可以接受。如采用1年的資料進(jìn)行水庫(kù)優(yōu)化調(diào)度,計(jì)算時(shí)段長(zhǎng)度為月,則優(yōu)化變量為12個(gè),在這些問題中,遺傳算法的計(jì)算時(shí)間基本與動(dòng)態(tài)規(guī)劃法相當(dāng):在馬光文等5的研究中,遺傳算法所用時(shí)間稍高于動(dòng)態(tài)規(guī)劃法;在暢建霞等10的研究中,相對(duì)于動(dòng)態(tài)規(guī)劃、逐步優(yōu)化方法,遺傳算

25、法耗時(shí)最少;在鐘登華等18的研究中,遺傳算法和動(dòng)態(tài)規(guī)劃法計(jì)算所需時(shí)間相差不大。但是對(duì)于大規(guī)模的水庫(kù)優(yōu)化調(diào)度問題,遺傳算法不一定能在有限的時(shí)間內(nèi)尋求到滿意的解,例如在馮平等23的研究中,計(jì)算時(shí)段長(zhǎng)度仍為月,優(yōu)化的資料長(zhǎng)度為10年,需要優(yōu)化的變量為120個(gè),此時(shí)動(dòng)態(tài)規(guī)劃法的優(yōu)化結(jié)果高出遺傳算法約319%?？梢?雖然理論上遺傳算法可收斂至全局最優(yōu)解,但在有限的計(jì)算時(shí)間內(nèi)往往不能達(dá)到。視計(jì)算規(guī)模不同,遺傳算法所需時(shí)間差別很大:單一水庫(kù)的優(yōu)化調(diào)度(12個(gè)優(yōu)化變量一般僅需幾十秒10,在Ahmed等50的研究中,優(yōu)化需要計(jì)算時(shí)間為13h;而在Cui等44的研究中,計(jì)算時(shí)間長(zhǎng)達(dá)416d。因此,耗時(shí)與最優(yōu)解之間

26、存在的矛盾,制約了遺傳算法在一些問題中的應(yīng)用,需尋求某些方面的改進(jìn)(改進(jìn)或者混合遺傳算法。212適宜于采用遺傳算法的條件和領(lǐng)域a.傳統(tǒng)方法難以解決的問題。傳統(tǒng)的線性規(guī)劃、非線性規(guī)劃以及動(dòng)態(tài)規(guī)劃技術(shù)在理論上可尋求到最優(yōu)解或者近似最優(yōu)解,但存在一定的適應(yīng)范圍和條件。如果傳統(tǒng)方法可以較完美地解決問題,則無(wú)需采用遺傳算法這一隨機(jī)搜索方法,如總長(zhǎng)度為10年的單一水庫(kù)優(yōu)化調(diào)度問題23。但某些問題采用傳統(tǒng)方法難以解決,主要包括:¹存在一些約束條件難于處理,如模型的半結(jié)構(gòu)化11;º不滿足狀態(tài)變量的無(wú)后效性、目標(biāo)的可分離性、決策與狀態(tài)的可逆性等條件,如決策變量為水庫(kù)汛限水位48;»

27、目標(biāo)函數(shù)復(fù)雜,如強(qiáng)調(diào)水電機(jī)組啟停成本、避開空蝕振動(dòng)限制運(yùn)行區(qū)間和考慮強(qiáng)制性開停機(jī)要求以及最小開停機(jī)時(shí)間約束的水電站廠內(nèi)經(jīng)濟(jì)運(yùn)行的數(shù)學(xué)模型33O34,其實(shí)質(zhì)上是一整數(shù)混合規(guī)劃問題,傳統(tǒng)方法難于尋找全局最優(yōu)解;又如考慮沖沙調(diào)度后目標(biāo)函數(shù)相當(dāng)復(fù)雜,必須采用基于模擬的優(yōu)化方法26,41;在水量水質(zhì)聯(lián)合調(diào)度中也存在類似的問題42。b.時(shí)效性(實(shí)時(shí)性能要求不高的問題。遺傳算法作為一種隨機(jī)搜索方法,在有限的計(jì)算時(shí)間內(nèi),最終計(jì)算結(jié)果具有一定的不確定性。使用遺傳算法時(shí),需要根據(jù)問題的特點(diǎn)進(jìn)行算法設(shè)計(jì),在計(jì)算時(shí)間與計(jì)算精度之間進(jìn)行均衡。在時(shí)效性要求較高的實(shí)時(shí)調(diào)度中(如計(jì)算時(shí)段長(zhǎng)為15min的水庫(kù)優(yōu)化調(diào)度,如果問題

28、規(guī)模較大或者目標(biāo)函數(shù)復(fù)雜,則選用遺傳算法需慎重;一旦選擇了遺傳算法,需根據(jù)問題特點(diǎn)精心設(shè)計(jì)算法,以改進(jìn)計(jì)算的收斂速度與穩(wěn)健性,確保在規(guī)定時(shí)間內(nèi)可得到較優(yōu)的計(jì)算結(jié)果。而在中小規(guī)模的優(yōu)化問題中,目標(biāo)函數(shù)也不復(fù)雜;或者在水庫(kù)中長(zhǎng)期調(diào)度、水庫(kù)優(yōu)化調(diào)度規(guī)則等屬于規(guī)劃階段的問題中,對(duì)計(jì)算的時(shí)效性要求不高,因此只要能保證算法具有全局收斂能力即可。模擬與優(yōu)化相結(jié)合的水庫(kù)調(diào)度技術(shù),越來(lái)越為學(xué)者所推崇45。遺傳算法不依賴于問題本身,為求解此類復(fù)雜問題提供了一種通用的框架。如圖3所示,給定調(diào)度規(guī)則、水庫(kù)特征數(shù)據(jù)等待定參數(shù),以歷史水文資料作為輸入,采用模擬技術(shù)可以計(jì)算方案的發(fā)電量、防洪風(fēng)險(xiǎn)等目標(biāo)值;以此為基礎(chǔ),采用遺

29、傳算法進(jìn)行優(yōu)化求解,建立以模擬為基礎(chǔ)的優(yōu)化模型,不僅可以減小水庫(kù)調(diào)度理論與實(shí)踐的差距,還可以大大減少優(yōu)化變量數(shù)45。但基于模擬的優(yōu)化方法需要相當(dāng)長(zhǎng)的計(jì)算時(shí)間,由于規(guī)劃設(shè)計(jì)問題對(duì)計(jì)算時(shí)間沒有太大的限制,且大都可以采用模擬優(yōu)化的方法解決,因此特別適宜于采用遺傳算法求解。此外,遺傳算法具有天然的并行性,可大大提高計(jì)算速度,提高大規(guī)模、復(fù)雜水庫(kù)群調(diào)度問題的處理能力44。因此,以遺傳算法作為優(yōu)化手段的模擬優(yōu)化方法在水庫(kù)調(diào)度規(guī)則38O 40,43O 47,49O 51、水沙聯(lián)合調(diào)度26,41、水量水質(zhì)聯(lián)合調(diào)度42以及水庫(kù)特征水位優(yōu)化48等方面得到了廣泛的應(yīng)用,具有廣闊的應(yīng)用前景。 圖3 基于模擬的優(yōu)化調(diào)度

30、框架3 結(jié) 語(yǔ)本文對(duì)遺傳算法用于水庫(kù)調(diào)度中的若干問題進(jìn)行了探討,可得到以下結(jié)論:a.遺傳算法的變種很多,參數(shù)確定也無(wú)明確規(guī)律可循,大大豐富了研究?jī)?nèi)容。遺傳算法的編碼、約束條件的處理非常重要,直接影響算法效率與精度。b.遺傳算法不依賴于問題的具體形式,可有效地解決傳統(tǒng)優(yōu)化方法難以解決的整數(shù)規(guī)劃或0O 1規(guī)劃問題。在水庫(kù)調(diào)度中,遺傳算法適宜于傳統(tǒng)方法難以求解的問題,以及時(shí)效性要求不高的實(shí)時(shí)調(diào)度問題,尤其是水庫(kù)規(guī)劃設(shè)計(jì)問題。遺傳算法作為一門新興的優(yōu)化技術(shù),自身也在不斷發(fā)展,可與神經(jīng)網(wǎng)絡(luò)、模糊理論以及小波技術(shù)等新興技術(shù)相結(jié)合,為解決很多傳統(tǒng)方法難以解決的問題提供新的思路;遺傳算法具有天然的并行性,發(fā)展

31、整體并行、粗粒度并行等并行遺傳算法,可大大提高計(jì)算速度,提高大規(guī)模、復(fù)雜水庫(kù)群調(diào)度問題的處理能力?？梢灶A(yù)見,在水庫(kù)調(diào)度中具有廣闊的應(yīng)用前景。參考文獻(xiàn):1郭生練.水庫(kù)調(diào)度綜合自動(dòng)化系統(tǒng)M.武漢:武漢水利電力大學(xué)出版社,2000.2Y EH W W 2G.Reservoir management and operations models:astate 2o f 2the 2art reviewJ.Water Resources Research,1985,21(12:1797O 1818.3金菊良,丁晶.水資源系統(tǒng)工程M.成都:四川科學(xué)技術(shù)出版社,2002.4丁晶,金菊良,楊曉華,等.基因算法在

32、水科學(xué)中的應(yīng)用J.人民長(zhǎng)江,1999,30(增刊:13O 15.5馬光文,王黎,WA L TERS G A.水電站優(yōu)化調(diào)度的FP 遺傳算法J.系統(tǒng)工程理論與實(shí)踐,1996(11:77O 81.6馬光文,王黎,WA L TERS G A.水電站群優(yōu)化調(diào)度的FP 遺傳算法J.水力發(fā)電學(xué)報(bào),1996,15(4:21O 28.7伍永剛,王定一.二倍體遺傳算法求解梯級(jí)水電站日優(yōu)化調(diào)度問題J.水電能源科學(xué),1999,17(3:31O 34.8W ARD LA W R,SHA RIF M.Evaluation o f genetic algo rith ms forop timal reserv oir r

33、esources J.Jo urnal of Water Resource Planni ng and Management,1999,125(1:25O 33.9S HA RIF M,W A RD LA W R.Multireserv oir sy stems op timizatio nusing genetic algo rith ms:case studyJ.Journal o f Computi ng in Civil Engineering,2000,14(4:255O 263.10暢建霞,黃強(qiáng),王義民.基于改進(jìn)遺傳算法的水電站水庫(kù)優(yōu)化調(diào)度J.水力發(fā)電學(xué)報(bào),2001,20(3:85

34、O 90.11方紅遠(yuǎn),鄧玉梅,董增川.多目標(biāo)水資源系統(tǒng)運(yùn)行決策優(yōu)化的遺傳算法J.水利學(xué)報(bào),2001,32(9:22O 27.12王大剛,程春田,李敏.基于遺傳算法的水電站優(yōu)化調(diào)度研究J.華北水利水電學(xué)院學(xué)報(bào),2001,22(1:5O 10.13袁曉輝,袁艷斌,權(quán)先璋,等.基于混沌進(jìn)化算法的梯級(jí)水電系統(tǒng)短期發(fā)電計(jì)劃J.電力系統(tǒng)自動(dòng)化,2001,25(16:34O 38.14CA I X,MCKINN EY D C,LA SDO N L S.So lving nonlinearwater management models using a co mbined genetic alg orithm

35、and linear pro gramming approach J.A dvances in Water Resources,2001,24(24:667O 676.15CHA NG Li 2chiu,C HAN G Fi 2jo hn.Intelligent co ntrol formodelling of real 2time reservoir operatio n J .Hy drological Processes,2001,15(9:1621O 1634.16馬光文,王黎,過夏明.分時(shí)電價(jià)下多用途水庫(kù)的運(yùn)用方式研究J.水科學(xué)進(jìn)展,2002,13(5:583O 587.17徐琦,張

36、勇傳,孔力,等.改進(jìn)遺傳算法在梯級(jí)電站日優(yōu)化運(yùn)行中的應(yīng)用J.水電能源科學(xué),2002,20(4:51O 53.18鐘登華,熊開智,成立芹.遺傳算法的改進(jìn)及其在水庫(kù)優(yōu)化調(diào)度中的應(yīng)用研究J.中國(guó)工程科學(xué),2003,5(9:22O 26.19HUA NG W en 2cheng,Y UAN Lun 2chin,CHI Ming.Linkin ggenetic algori thms w ith stochastic dynamic programming to the long 2term o peration of a multireservoir sy stem J.WaterResources

37、Research, 2002, 38 ( 12 , 1304, doi: 1011029/ 2001WR001122. 20 劉攀, 王才君, 張洪剛, 等. 三峽水 庫(kù)圍堰 發(fā)電期泄 洪閘 門優(yōu)化調(diào)度研究 C / / 郭 生練. 水 問 題研 究與 進(jìn)展: 全 國(guó)首屆水問題研究學(xué)術(shù)研討會(huì) 論文集. 武漢: 湖北 科學(xué) 技術(shù)出版社, 2003: 373 O377. 21 宋朝紅, 羅 強(qiáng), 紀(jì)昌明. 基 于混 合遺 傳算 法的 水庫(kù) 群優(yōu) 化調(diào)度研究 J . 武漢大學(xué)學(xué)報(bào): 工學(xué)版, 2003, 36( 4 : 28 O 31. 22 游進(jìn)軍, 紀(jì) 昌明, 付湘. 基 于遺 傳算 法的 多目

38、標(biāo)問 題求 解方法 J . 水利學(xué)報(bào), 2003, 34( 7 : 64 O69. 23 馮平, 李紹飛, 安偉哲, 等. 三門峽 水庫(kù)電 站運(yùn)行調(diào) 度的 優(yōu)化研究 J . 天津大學(xué)學(xué)報(bào) , 2004, 37( 4 : 294O 297. 24 付永鋒, 沈冰, 李智錄, 等. 基于自 適應(yīng)遺 傳算法的 金盆 水庫(kù)優(yōu)化調(diào)度研究 J . 水電 能源 科學(xué), 2004, 22( 3 : 47O 50. 25 胡明罡, 練繼建. 基于改進(jìn)遺傳算 法的水 電站日優(yōu) 化調(diào) 度方法研究 J . 水力發(fā)電學(xué) 報(bào), 2004, 23( 2 : 17O 21. 26 練繼建, 胡 明罡, 劉媛 媛. 多沙 河流

39、 水庫(kù) 水沙 聯(lián)調(diào) 多目 標(biāo)規(guī)劃研究 J . 水力發(fā)電學(xué) 報(bào), 2004, 23( 2 : 12O 16. 27 羅云霞, 周 慕遜, 王萬(wàn) 良. 基于 遺傳 模擬 退火 算法 的水 庫(kù)優(yōu)化調(diào)度 J . 華 北水 利水 電學(xué) 院學(xué) 報(bào), 2004, 25( 3 : 20O 22. 28 張雙虎, 黃 強(qiáng), 孫廷容. 基 于并 行組 合模 擬退 火算 法的 水電站優(yōu)化調(diào) 度研 究 J . 水 力發(fā) 電學(xué) 報(bào), 2004, 23( 4 : 16O 19. 29 朱仲元, 朝倫巴根, 杜丹, 等. 多目 標(biāo)遺傳 算法在確 定串 聯(lián)水庫(kù)系統(tǒng)優(yōu)化運(yùn)行策略中的應(yīng)用 J . 灌溉排水學(xué)報(bào), 2004, 23

40、( 6 : 71 O74. 30 姜鐵兵, 梁年生, 康玲, 等. 用遺傳 法確定 水電站自 動(dòng)發(fā) 電計(jì)劃 J . 水力發(fā)電學(xué)報(bào), 1995, 14( 4 : 7 O14. 31 袁曉輝, 張雙全, 王金文, 等. 擬梯 度遺傳 算法在水 電廠 廠內(nèi)經(jīng) 濟(jì) 運(yùn) 行 中 的 應(yīng) 用 研 究 J . 電 網(wǎng) 技 術(shù), 2000, 24 ( 12 : 66 O69. 32 劉博, 周建 中, 楊敬濤. 基 于動(dòng) 態(tài)規(guī) 劃和 遺傳 算法 的混 合算法研究 J . 計(jì)算機(jī)仿真 , 2004, 21( 12 : 87O 89. 33 孫昌佑, 馬震岳. 基于遺傳算法的 水電站 廠內(nèi)經(jīng)濟(jì) 運(yùn)行 模型研究 J

41、 . 水電能源科學(xué) , 2004, 22( 1 : 48O 50. 34 王立明, 馬 光文, 張永 麗. 權(quán)衡 電能 損失 和啟 停成 本的 水電站機(jī)組最佳運(yùn)行計(jì)劃 J . 四川大學(xué)學(xué)報(bào): 工程科學(xué) 版, 2004, 36( 2 : 29O 32. 35 楊敬濤, 周建中, 向凌, 等. 偽并行 遺傳算 法及其在 水電 站經(jīng)濟(jì)運(yùn)行中的 應(yīng) 用 J . 電網(wǎng) 技術(shù), 2004, 28( 14 : 53O 56. 36 王亞娟, 熊信艮. 基于遺傳算法的 水火電 混合電力 系統(tǒng) 短期發(fā)電計(jì)劃優(yōu)化 J . 繼電 器, 2000, 28( 10 : 21O 24. 37 ZOUMAS C E, B

42、AKIRTZIS A G, THEOCHARIS J B, et al. Genetic algorithm solution approach to the hydrothermal coordination problem J . IEEE Transactions on Power Systems, 2004, 19( 2 : 1356O 1364. 38 OLIVEIRA R, LOUCKS D P. Operating rules for multireservoir 水利水電科技進(jìn)展, 2006, 26( 4 Tel : 025O83786335 systems J . Water

43、 Resources Research, 1997, 33 ( 4 : 839O 852. 39 CHANG Fi2john, C HEN Li. Real2coded genetic algorithm for rule 2based flood control reservoir management J . Water Resources Management, 1998, 12( 3 : 185 O198. 40 MERABTENE T, KAWAMURA A, JINNO K, et al. Risk assessment for optimal drought management

44、 of an integrated water resources system using a genetic algorithm J . Hydrological Processes, 2002, 16( 11 : 2189 O2208. 41 C HANG Fi2john, LAI Jihn2sung, KAO Li2shan. Optimization of operation rule curves and flushing schedule in a reservoir J . Hydrological Processes, 2003, 17( 8 : 1623 O1640. 42

45、 C HAVES P, KOJIRI T, YAMAS HIKI Y. Optimization of storage reservoir considering water quantity and quality J . Hydrological Processes, 2003, 17( 14 : 2769 O2793. 43 CHEN L. Real coded genetic algorithm optimization of long2 term reservoir operation J . Journal of the American Water Resources Association, 2003, 39( 5 , 1157 O1165. 44 CUI L J, KUCZER