基于改進(jìn)遺傳算法的梯級橡膠壩調(diào)度優(yōu)化

鄧浩　郝瑞霞

摘 要：為解決城市河道中梯級橡膠壩的優(yōu)化調(diào)度問題，求解出較為合理的塌壩泄流方案，保障河道行洪安全，根據(jù)橡膠壩塌壩泄流計(jì)算原理，以限定時(shí)間范圍內(nèi)最小泄流量為目標(biāo)函數(shù)，建立梯級橡膠壩調(diào)度優(yōu)化模型，并采用線性加速選擇函數(shù)與改進(jìn)的自適應(yīng)交叉、變異函數(shù)，改進(jìn)傳統(tǒng)遺傳算法（GA），進(jìn)行模擬運(yùn)算，求解最優(yōu)塌壩方案。改進(jìn)的遺傳算法（IGA）收斂速度快、穩(wěn)定性強(qiáng)、程序運(yùn)算時(shí)間短，能高效精確地計(jì)算出符合客觀實(shí)際要求的梯級橡膠壩優(yōu)化調(diào)度方案，具有一定的工程應(yīng)用價(jià)值。

關(guān)鍵詞：梯級橡膠壩;最優(yōu)塌壩方案;調(diào)度優(yōu)化;改進(jìn)的遺傳算法;改進(jìn)自適應(yīng)度

中圖分類號：TV644?? 文獻(xiàn)標(biāo)志碼：A

doi：10.3969/j.issn.1000-1379.2020.03.030

Scheduling Optimization of Cascade Rubber Dam Based on Improved Genetic Algorithm

DENG Hao， HAO Ruixia

（College of Water Resources Science and Engineering， Taiyuan University of Technology， Taiyuan 030024， China）

Abstract： In order to solve the issue of optimal scheduling of cascade rubber dams in urban rivers， a reasonable dam discharge plan was solved to ensure the safety of river flood discharge. According to the calculation principle of rubber dam collapse discharge， the minimum discharge flow within a limited time range was obtained. For the objective function， cascade rubber dams scheduling optimization model was established， and the linear acceleration selection function， the improved adaptive crossover function and variation function were used to improve the traditional genetic algorithm （GA） and simulated to solve the optimal dam collapse scheme. The improved genetic algorithm （IGA） has fast convergence speed， strong stability and short program operation time. It can efficiently and accurately calculate the optimal scheduling scheme of cascade rubber dams that can meet objective practical requirements and has certain engineering application value.

Key words： cascade rubber dams; optimal scheme of dam collapse; scheduling optimization; improved genetic algorithm; improved self adaptation

近年來，隨著橡膠壩在生態(tài)水利、景觀水利和水資源開發(fā)中的廣泛應(yīng)用，同一河道上會修建多級橡膠壩形成梯級橡膠壩群。汛期洪水來臨之前梯級橡膠壩群的泄流調(diào)度非常重要，不合理的泄流方案會造成人造洪峰或洪水疊加，如何在不危及下游河道行洪安全的前提下按限定時(shí)間完成泄流迎汛任務(wù)，是一個(gè)調(diào)度策略優(yōu)化問題。目前，對于梯級橡膠壩運(yùn)行調(diào)度方案優(yōu)化，主要有非線性規(guī)劃法、動態(tài)規(guī)化法（DP）[1]和POA法[2]等，隨著梯級橡膠壩級數(shù)的增加，其優(yōu)化時(shí)間變長、收斂速度變慢，易陷入“維數(shù)災(zāi)”[3]，并且全局搜索性能較差。遺傳算法（GA）是一種模擬遺傳進(jìn)化機(jī)制的全局優(yōu)化智能算法[4]，操作簡單、運(yùn)行時(shí)間短，在水庫調(diào)度與水資源優(yōu)化配置中得到廣泛運(yùn)用[5]。筆者根據(jù)橡膠壩泄流運(yùn)算原理，建立調(diào)度方案優(yōu)化模型，并對傳統(tǒng)遺傳算法（GA）進(jìn)行改進(jìn)，采用改進(jìn)的自適應(yīng)函數(shù)[6]，確定優(yōu)化調(diào)度準(zhǔn)則和目標(biāo)函數(shù)，加入適應(yīng)度放縮機(jī)制，克服算法的早熟性和不穩(wěn)定性[7]，以期迅速、穩(wěn)定地得到符合約束條件的最優(yōu)方案。

1 梯級橡膠壩優(yōu)化調(diào)度模型

1.1 優(yōu)化調(diào)度準(zhǔn)則與目標(biāo)函數(shù)

根據(jù)梯級橡膠壩汛期調(diào)度運(yùn)行原則，塌壩泄流應(yīng)自下而上逆序進(jìn)行[8]。各級橡膠壩從上游到下游標(biāo)記為D1、D2、…、Dn，各級橡膠壩自身塌壩時(shí)間分別為T1、T2、…、Tn，各級橡膠壩的塌壩開始時(shí)間分別為Tb1、Tb2、…、Tbn，在橡膠壩塌壩泄流過程中各壩段最大泄流量分別為Q1max、Q2max、…、Qnmax，完成泄流任務(wù)的總時(shí)間為TM。根據(jù)保護(hù)下游河道、不產(chǎn)生洪水疊加的要求，應(yīng)最大限度減小塌壩泄流量Qmax。梯級橡膠壩的塌壩泄流調(diào)度在滿足不大于限定泄流時(shí)間TL的情況下，以降低最下游橡膠壩斷面的泄流量為目標(biāo)，其目標(biāo)函數(shù)為

式中：Qnmax為最下游橡膠壩斷面最大下泄流量。

1.2 約束條件

為了求得滿足目標(biāo)函數(shù)的最優(yōu)解，對模型的求解條件進(jìn)行約束。根據(jù)橡膠壩塌壩泄流計(jì)算的基本要求和原則[9]，確定如下約束條件。

（1）水量平衡約束，表達(dá)式為

式中：Vt為t時(shí)刻的橡膠壩蓄水量;Vt-1為t-1時(shí)刻的蓄水量;Qd為t時(shí)刻的泄流量;Qt為t時(shí)刻的入流量;Δt為時(shí)段長，取值為1 min。

（2）水位與蓄水量約束，表達(dá)式為

式中：Himax為橡膠壩塌壩過程中壩前最高水位，其中i為橡膠壩編號;Hil表示壩前最高限定水位;Vimax為最大蓄水量;Vil為最大限制蓄水量。

（3）時(shí)間約束，表達(dá)式為

式中：Tbi為第i級橡膠壩開始泄流時(shí)間;Tbi+1為第i+1級橡膠壩開始泄流時(shí)間;Ti為第i級橡膠壩完全塌壩的時(shí)間;TKi為第i級橡膠壩最短塌壩時(shí)間;TM為完成塌壩泄流任務(wù)的總時(shí)間;TL為限制泄流時(shí)間，即保證在上游洪水來臨之前完成橡膠壩塌壩的限制總時(shí)間。

（4）流量約束，表達(dá)式為

式中：Qmax為最大泄流量;Q河為河道行洪能力。

（5）非負(fù)約束條件，所設(shè)定參數(shù)全部不得小于0。

2 改進(jìn)遺傳算法

2.1 遺傳算法

遺傳算法（GA）是當(dāng)前應(yīng)用較為廣泛的智能優(yōu)化算法，其操作簡便、全局搜索性強(qiáng)，通過模擬生物進(jìn)化和遺傳的過程，把需處理問題的控制變量編譯為二進(jìn)制型或浮點(diǎn)型編碼，形成基因，若干基因排序組合形成一個(gè)染色體（個(gè)體），代表一種優(yōu)化方案。多個(gè)染色體組成一個(gè)種群P（t），根據(jù)適者生存的進(jìn)化規(guī)律，種群中適應(yīng)度高的染色體基因有較大概率遺傳至子代，并通過交叉、變異等操作生成新的個(gè)體，組成新的群體P（t+1）。經(jīng)過反復(fù)迭代，逐步使群體進(jìn)化至最優(yōu)解狀態(tài)，從而求出問題最優(yōu)解。

GA算法用于梯級橡膠壩調(diào)度優(yōu)化的求解步驟：以梯級橡膠壩各壩塌壩開始時(shí)間Tb1、Tb2、…、Tbn為控制條件，采用浮點(diǎn)型編碼形成基因組;隨機(jī)生成M個(gè)基因組，每組基因代表一種調(diào)度決策方案，進(jìn)而形成種群規(guī)模為M的初始群體;在約束條件下進(jìn)行選擇、交叉和變異等操作，經(jīng)過迭代不斷產(chǎn)生新的個(gè)體和種群，直至達(dá)到收斂條件，輸出最優(yōu)解和非劣解。

2.2 改進(jìn)遺傳算法（IGA）

在基本遺傳算法（GA）的運(yùn)算過程中，常因算法本身的缺陷和數(shù)據(jù)誤差而出現(xiàn)算法早熟、局部收斂、后期穩(wěn)定性差等問題，為此，在GA算法的基礎(chǔ)上，結(jié)合模型實(shí)例對遺傳算法運(yùn)行中的選擇算子進(jìn)行改進(jìn)，并引入改進(jìn)自適應(yīng)度和懲罰因子，使算法收斂速度更快、穩(wěn)定性更好。

2.2.1 改進(jìn)選擇算子

在 GA算法中，輪盤賭法是較為常用的遺傳算子選擇方法。輪盤賭法存在的問題是，進(jìn)化前期適應(yīng)度較為分散時(shí)，易產(chǎn)生超級個(gè)體，導(dǎo)致算法的早熟;進(jìn)化后期適應(yīng)度比較集中時(shí)，不易選出適應(yīng)度高的基因，導(dǎo)致算法收斂不穩(wěn)定。因此，引入線性加速選擇函數(shù)式（6）、式（7），轉(zhuǎn)換所求適應(yīng)度值域映射尺度，改變遺傳算子選擇方式。

式中：f′（x）為轉(zhuǎn)換后的適應(yīng)度;f（x）為原適應(yīng)度;a、b為系數(shù)和常數(shù);favg為原適應(yīng)度平均值;fmax為原群體最大適應(yīng)度值;C為轉(zhuǎn)化系數(shù)，取值范圍為[1.2，2]，本文取值1.2。

2.2.2 改進(jìn)自適應(yīng)度交叉、變異算子

在GA算法中，由于交叉率Pc和變異率Pm是初始設(shè)定固定值，導(dǎo)致運(yùn)行時(shí)適應(yīng)度高的個(gè)體基因可能被交叉和變異操作破壞，從而降低其收斂速率，因此在群體進(jìn)化過程中，引入改進(jìn)的自適應(yīng)度函數(shù)，使交叉率Pc和變異率Pm隨著個(gè)體適應(yīng)度大小進(jìn)行非線性調(diào)整，進(jìn)而提升算法收斂速率和穩(wěn)定性。當(dāng)個(gè)體自身適應(yīng)度大于平均值時(shí)，通過縮小個(gè)體的變異與交叉率，來保持優(yōu)良基因組的穩(wěn)定性;當(dāng)個(gè)體自身適應(yīng)度小于平均值時(shí)，通過擴(kuò)大個(gè)體的交叉率與變異率，增強(qiáng)群體基因的多樣性。交叉率Pc和變異率Pm的改進(jìn)自適應(yīng)度調(diào)整公式為

式中：A為變換常數(shù)值9.903 438 [10];Pcmax、Pcmin分別為交叉率的最大和最小值;Pmmax、Pmmin分別為變異率的最大和最小值;f′為兩個(gè)交叉?zhèn)€體適應(yīng)度中的較大值;f為變異個(gè)體適應(yīng)度值。

2.3 基于IGA算法的橡膠壩調(diào)度優(yōu)化運(yùn)算步驟

結(jié)合優(yōu)化調(diào)度模型，以各級橡膠壩塌壩開始時(shí)間Tb1、Tb2、…、Tbn為基因，隨機(jī)生成擁有M個(gè)個(gè)體的初始種群，在適應(yīng)度函數(shù)和各約束條件的限制下，通過選擇、交叉和變異等操作，不斷向適應(yīng)度高的目標(biāo)進(jìn)化，直至達(dá)到收斂條件，輸出優(yōu)化調(diào)度運(yùn)行方案， 算法流程見圖1。

圖1 IGA算法流程

（1）編碼及初始化種群。在梯級橡膠壩優(yōu)化調(diào)度運(yùn)行中，結(jié)合實(shí)際需要，采用浮點(diǎn)型編碼，在約束條件中上一級橡膠壩塌壩開始時(shí)間Tbi不早于下一級橡膠壩塌壩開始時(shí)間Tbi+1，所以編碼時(shí)Tbi在區(qū)間[Tbi+1，Tbi+1+N]內(nèi)隨機(jī)生成（其中N為區(qū)間范圍值），并以此規(guī)則隨機(jī)生成M組方案，生成初始調(diào)度方案種群。

（2）計(jì)算適應(yīng)度。利用差值法將已知最小值問題轉(zhuǎn)化成計(jì)算個(gè)體最大適應(yīng)度值問題，其中適應(yīng)度函數(shù)為

式中：g（x）為目標(biāo)函數(shù)值;Cmax為目標(biāo)函數(shù)能取得的最大值。

在計(jì)算適應(yīng)度時(shí)，并不是所有方案都能滿足約束條件，故引入線性懲罰函數(shù)τ（x），對超出限制的個(gè)體適應(yīng)度進(jìn)行處理，即f′（x）=τ（x）f（x），在保持基因多樣性的同時(shí)，對超過約束條件的適應(yīng)度進(jìn)行調(diào)整。懲罰函數(shù)τ（x）公式為

式中：K為最大超限值，取值為主要目標(biāo)函數(shù)值的5%;L為超出約束條件限度值。

（3）選擇。依據(jù)初始計(jì)算的各個(gè)體適應(yīng)度，通過改進(jìn)的輪盤賭法，利用線性加速函數(shù)計(jì)算選擇個(gè)體的概率。在算法早期，降低超級個(gè)體適應(yīng)度值，以防止出現(xiàn)早熟。在選擇操作過程中，采取保留精英策略，避免最優(yōu)個(gè)體在選擇過程中因概率事件未被選入下一代種群，克服樣本的隨機(jī)誤差。

（4）交叉與變異。在進(jìn)行交叉操作時(shí)，采用錯(cuò)位交叉原則，對隨機(jī)選擇產(chǎn)生的兩個(gè)父代進(jìn)行配對，取父代Jti的偶數(shù)位基因與父代Jtk的奇數(shù)位基因，組合形成新的基因組Jt+1i和子代群體。在進(jìn)行變異操作時(shí)，考慮到編碼類型為浮點(diǎn)型，對變異的基因范圍進(jìn)行控制，即各有50%的概率，在原浮點(diǎn)型基因基礎(chǔ)上形成新的個(gè)體。其中交叉率Pc與變異率Pm通過改進(jìn)的自適應(yīng)度函數(shù)來確定。

（5）終止條件。以種群平均適應(yīng)度和最大適應(yīng)度的差值小于0.01且持續(xù)超過10代為收斂的判斷標(biāo)準(zhǔn)，以子代平均適應(yīng)度與父代平均適應(yīng)度差值小于0.01且持續(xù)超過10代為輔助判斷標(biāo)準(zhǔn)，直至達(dá)到收斂條件，終止算法，輸出最優(yōu)調(diào)度運(yùn)行方案。

3 應(yīng)用實(shí)例

以汾河太原段已建多級橡膠壩為例進(jìn)行調(diào)度方案優(yōu)化。汾河太原段已建成7座橡膠壩，北起柴村橋、南到祥云橋下游500 m處，總長度約15.6 km，蓄水量達(dá)1 000萬m3，一期治理河段設(shè)計(jì)河道比降為0.078 3%，二期治理河段設(shè)計(jì)河道比降為0.1%，梯級橡膠壩示意見圖2。汾河太原城區(qū)段河道限制流量Q河為2 250 m3/s。

汾河二庫距太原市中心約30 km，是以防洪、供水為主的大（2）型水利樞紐工程，設(shè)計(jì)洪水（100 a一遇）最大泄流量為3 450 m3/s，選取汾河二庫2016年7月19日6—24時(shí)實(shí)測下泄流量過程（見圖3）進(jìn)行梯級橡膠壩運(yùn)行調(diào)度方案優(yōu)化。

根據(jù)處于上游的汾河寨上站和蘭村站水文資料分析，兩站之間洪水平均流速為3.11 m/s。汾河二庫到1#橡膠壩約33 km，洪水傳播時(shí)間即限定泄流時(shí)間TL為2.95 h，梯級橡膠壩須在洪水來臨之前完成塌壩泄流任務(wù)。根據(jù)現(xiàn)有資料查得各壩的自身塌壩時(shí)間T1、T2、…、T7及相關(guān)信息，見表1。

以各級橡膠壩的塌壩開始時(shí)間為基因，隨機(jī)生成100個(gè)初始個(gè)體，組成初始種群，進(jìn)化代數(shù)設(shè)為300代，交叉率Pc的取值范圍為0.2～0.9，變異率Pm的取值范圍為0.01～0.1，即Pcmin=0.2，Pcmax=0.9，Pmmin=0.01，Pmmax=0.1。

根據(jù)收集的資料和相關(guān)水力學(xué)計(jì)算原理，在壩袋充脹時(shí)按曲線型實(shí)用堰計(jì)算泄流過程，在壩袋塌平時(shí)按寬頂堰計(jì)算泄流過程，在此基礎(chǔ)上以單個(gè)橡膠壩的塌壩泄流計(jì)算過程為參照，綜合分析梯級橡膠壩的塌壩泄流過程。利用改進(jìn)的遺傳算法（IGA），在C/C++平臺上進(jìn)行編譯運(yùn)算，通過多次試算，均能快速收斂，并求得5組近似最優(yōu)方案（見表2），并畫出5種方案最下游梯級橡膠壩泄流過程線（見圖4）。5種方案雖然控制條件不同，但模擬計(jì)算結(jié)果卻十分接近，其最下游梯級橡膠壩泄流量過程線相似，都是滿足限制條件的優(yōu)化調(diào)度方案，都能在上游洪水來臨之前完成塌壩泄流任務(wù)、保證河道安全。

假設(shè)汾河二庫保持流量為700 m3/s下泄，選取調(diào)度方案1進(jìn)行模擬計(jì)算，分析是否會產(chǎn)生洪水疊加、危及河道安全，結(jié)果顯示，優(yōu)化調(diào)度方案1完成塌壩泄流任務(wù)需200 min，而汾河二庫泄流洪水抵達(dá)最下游橡膠壩的時(shí)間為250 min左右，此時(shí)橡膠壩已基本排空蓄水量，因而不會產(chǎn)生洪水疊加，最下游橡膠壩流量過程線見圖5。

為了便于比較分析，在相同的目標(biāo)函數(shù)和約束條件下，也采用傳統(tǒng)遺傳算法（GA）對本算例進(jìn)行了模擬計(jì)算，兩種方法的每代目標(biāo)函數(shù)值、平均適應(yīng)度見圖6、圖7，可以看出：IGA算法每代平均目標(biāo)函數(shù)值跌落顯明，在模擬過程中有較快的收斂速度，表明IGA算法在加入改進(jìn)的自適應(yīng)度函數(shù)后能更快地收斂至目標(biāo)解，引入選擇算子調(diào)整函數(shù)能增強(qiáng)算法的穩(wěn)定性;適應(yīng)度值相同時(shí)，IGA算法優(yōu)化代數(shù)明顯少于GA算法的，表明IGA算法收斂性好，可以迅速求得最佳調(diào)度優(yōu)化方案。

4 結(jié) 語

引入自適應(yīng)選擇函數(shù)和改進(jìn)自適應(yīng)度函數(shù)對遺傳算法進(jìn)行改進(jìn)，改進(jìn)的遺傳算法（IGA）收斂速度加快，穩(wěn)定性增強(qiáng)，程序運(yùn)算時(shí)間縮短，不易陷入“維數(shù)災(zāi)”。在優(yōu)化調(diào)度模型基礎(chǔ)上，采用IGA算法得到的梯級橡膠壩優(yōu)化調(diào)度方案符合客觀實(shí)際，能保證在限定的時(shí)間內(nèi)以較小的下泄流量完成橡膠壩塌壩泄流任務(wù)，具有一定的工程應(yīng)用價(jià)值。本文提出的IGA算法只能解決梯級橡膠壩優(yōu)化的單目標(biāo)函數(shù)問題，對多目標(biāo)函數(shù)問題還需進(jìn)一步研究。

參考文獻(xiàn)：

[1] 暢建霞，黃強(qiáng)，王義民.水電站水庫優(yōu)化調(diào)度幾種方法的探討[J].水電能源科學(xué)，2000，18（3）：19-22.

[2] 宗航，李承軍，周建中，等. POA算法在梯級水電站短期優(yōu)化調(diào)度中的應(yīng)用[J].水電能源科學(xué)，2003， 21（1）：46-48.

[3] 馬靜.梯級橡膠壩塌壩泄流計(jì)算與塌壩方案優(yōu)化方法研究[D].泰安：山東農(nóng)業(yè)大學(xué)，2012：18-21.

[4] 王小平，曹立明.遺傳算法：理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002：25-28.

[5] 黃偉.基于自適應(yīng)遺傳算法的水資源優(yōu)化配置研究[J].人民黃河，2010，32（8）：63-64.

[6] WANG Guangmin，WAN Zhongping. An Adaptive Genetic Algorithm for Solving Bilevel Linear Programming Problem[J]. Applied Mathematics and Mechanics（English Edition），2007（12）：1605-1612.

[7] 葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2008，25（10）：2911-2916.

[8] 徐智廷，孫廷璽，張世功，等.沂河梯級橡膠壩汛期調(diào)度運(yùn)用原則探討[J].中國水利，2008（19）：61-62.

[9] 張慶華，刁艷芳，程傳民，等.梯級橡膠壩塌壩泄流計(jì)算仿真系統(tǒng)[J].水利水電科技進(jìn)展，2014，34（4）：53-56.

[10] 金晶，蘇勇.一種改進(jìn)的自適應(yīng)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2005，41（18）：64-69.

【責(zé)任編輯 張智民】

收稿日期：2017-09-21

作者簡介：鄧浩（1989—），男，山東菏澤人，碩士研究生，研究方向?yàn)樗W(xué)及河流動力學(xué)

通信作者：郝瑞霞（1965—），女，山西太原人，教授，博士，碩士研究生導(dǎo)師，研究方向?yàn)樗W(xué)及河流動力學(xué)

E-mail：366557098@qq.com