三角函數(shù)選擇算子的遺傳算法在梯級水庫優(yōu)化調(diào)度中的應(yīng)用

楊 侃，鄭 姣，郝永懷，周 冉，劉國帥

(河海大學水文水資源學院，南京 210098)

遺傳算法(genetic algorithm，GA)產(chǎn)生于20世紀60年代末到70年代初，該法不依賴于問題的具體領(lǐng)域，有很強的魯棒性[1]．近年來，隨著數(shù)學與計算機技術(shù)的發(fā)展，GA被引入到水庫優(yōu)化調(diào)度領(lǐng)域．馬光文等[2]將采用二進制編碼的標準遺傳算法(simple genetic algorithm，SGA)應(yīng)用于水電站優(yōu)化調(diào)度，實現(xiàn)了較有效地在整個解空間尋優(yōu)，更有把握達到全局最優(yōu)或準全局最優(yōu)．王大剛等[3]提出了基于十進制編碼的 SGA，避免了由于二進制編碼串很長而造成的算法搜索效率低的缺陷．針對 SGA存在收斂性及個體適應(yīng)度求解方面的困難，王少波等[4]在 SGA 的基礎(chǔ)上采用隨個體適應(yīng)度大小和群體分散程度自動調(diào)整的交叉概率 Pc和變異概率 Pm，提出了一種自適應(yīng)遺傳算法(adaptive genetic algorithm，AGA)，并通過實例證明：與 SGA相比，AGA能夠加快收斂速度提高算法全局穩(wěn)定性．而對于水庫優(yōu)化調(diào)度中GA在選擇過程中可能造成的早熟所做的改進，目前為止鮮見報道．選擇算子直接關(guān)系到下一代種群的質(zhì)量，對GA的整個過程有著至關(guān)重要的影響，通過改進選擇算子，有利于避免算法過早收斂．

梯級水庫優(yōu)化調(diào)度模型建立上，傳統(tǒng)研究在處理水庫間復(fù)雜水力聯(lián)系問題上，或未考慮或采用簡化處理方式，所建模型只做流量時間上的推移計算，未考慮流量傳播過程引起的坦化變形問題[5-6]．基于此，筆者深入研究了在 GA中如何處理梯級水庫間復(fù)雜的水力聯(lián)系．

1 自適應(yīng)遺傳算法及其選擇原理

以決策變量編碼作為運算對象，根據(jù)種群中個體適應(yīng)度進行遺傳操作，在進化過程中對各代群體中的個體進行優(yōu)勝劣汰，以找尋目標函數(shù)的最優(yōu)解[3]．AGA采用隨個體適應(yīng)度大小和群體分散程度自動調(diào)整的交叉和變異概率，提高算法的優(yōu)化能力．

1.1 常用選擇方法及存在的問題

GA中常用的個體選擇方式主要有輪盤賭選擇法、錦標賽選擇法、排序選擇法．其中輪盤賭選擇法是最常用的，該法基于比例適應(yīng)度選擇，利用各個體適應(yīng)度所占比例的大小決定其子孫保留的可能性，要求適應(yīng)度大于零．對于水庫優(yōu)化調(diào)度問題，由于考慮流量約束和出力約束后，常常建立施以流量和出力懲罰的適應(yīng)度函數(shù)，這樣就很難保證適應(yīng)度非負．錦標賽選擇法雖然對適應(yīng)度取正負無要求，但不同的聯(lián)賽規(guī)?？赡軒聿煌男Ч?，而聯(lián)賽規(guī)模的選擇目前仍沒有理論依據(jù)，因此該法也存在其局限性．排序選擇法通過設(shè)置個體被選中的概率來處理包含負適應(yīng)值的情況，但是由于被選中的概率常常是常數(shù)值，不會隨進化狀態(tài)變化，因此也有其局限性[7]．因此怎樣對遺傳算法的選擇算子做改進，使其能夠克服適應(yīng)度非負的要求，是值得深入研究的一項工作．

1.2 基于三角函數(shù)的選擇算子

三角函數(shù)選擇算子實際上是一種對適應(yīng)值進行非線性變換的方法，將適應(yīng)度函數(shù)轉(zhuǎn)化為三角函數(shù)值pi映射到[0，1]．文獻[7]提出如下4種選擇算子．

正弦選擇算子

余弦選擇算子

正切選擇算子

余切選擇算子

文獻[7]分析了三角函數(shù)選擇算子的可行性，指出它能夠保證適應(yīng)值較優(yōu)的個體具有較高的被選擇概率．以正弦函數(shù)選擇算子為例：對于同一種群內(nèi)任意進化的 2個個體 xi和 xj，其適應(yīng)度滿足 fi＜fj，正弦函數(shù)顯然，而正弦函數(shù)在[0，]上單調(diào)增，故．三角函數(shù)選擇算子的概率是依據(jù)個體的適應(yīng)能力設(shè)置的，能夠很好地處理適應(yīng)值為負值的情況．可以結(jié)合輪盤賭等進行傳統(tǒng)選擇算子的改進，因此很適合處理水庫優(yōu)化調(diào)度問題，具有很好的實用價值．

2 基于三角函數(shù)選擇的梯級水庫優(yōu)化調(diào)度自適應(yīng)遺傳算法構(gòu)建

梯級水庫優(yōu)化調(diào)度模型中每個水庫每個時段都有最高最低水位約束，因此梯級水庫調(diào)度的遺傳算法在水庫水位允許范圍內(nèi)，將單庫調(diào)度期內(nèi)水位前后連接，組成pop組可行水位變化序列，其中pop為種群數(shù)量．將水位進行一定的編碼運算之后通過編碼按照個體適應(yīng)度進行“優(yōu)勝劣汰”的進化過程．如此反復(fù)，最后按照一定的終止規(guī)則終止．對于水庫優(yōu)化調(diào)度問題，一般采用是否達到預(yù)定進化代數(shù)的方式終止運算．

2.1 初始種群設(shè)計及梯級水庫間水力處理

初始種群的分布性質(zhì)嚴重影響算法的收斂性能，初始群體性能差可能導(dǎo)致算法收斂速度慢，甚至不收斂[8-9]．考慮到庫群編碼是單庫編碼的數(shù)倍，采用隨機生成初始種群的方式很難搜索到可行解，本研究采用文獻[10]提出的解空間生成法．

梯級水庫之間的水力聯(lián)系使得其短期優(yōu)化調(diào)度比單庫優(yōu)化調(diào)度復(fù)雜得多，傳統(tǒng)研究處理水庫間復(fù)雜水力聯(lián)系問題時，或未考慮或采用簡化處理方式．在下游水庫入庫流量的計算上，或簡單地處理成上游水庫出庫流量和區(qū)間來水的總和，或只將上游水庫出庫流量做時間上的推移，實際上這樣處理是非常不合理的，原因是上下游水庫流量傳播的過程中不僅存在時滯問題，還存在流量傳播過程中帶來的坦化變形．為此，筆者采用一種處理梯級水庫間水力聯(lián)系的新思路：以水庫壩間實測的上游水庫出庫流量與下游水庫相應(yīng)入庫流量資料來尋求其相關(guān)關(guān)系．這樣可以很好地避免水流時滯和坦化變形處理，能夠進一步提高模型的精度．

改進后模型中第i時段下游水庫入庫流量為

式中：d,iI為下游水庫 i時段入庫流量；u,iQ 為上游水庫i時段出庫流量；參數(shù)a、b由大量實測資料率定．

2.2 個體編碼設(shè)計

避免二進制編碼串很長造成搜索效率低的缺陷，采用實數(shù)編碼．編碼Kt，水位Zt，則

式中：tK為 t時段水位編碼為t時段水位編碼的上限；,maxtZ 、,mintZ 分別為t時段允許水位的最大和最小值；popdt為控制的水位精度．因為“以水定電”梯級水庫調(diào)度模型中對每一水庫都有初始和期末水位的限制，因此以第 1個水庫為例(有初始水位 Z0和期末水位 Ze的控制)，對該水庫初始和期末的水位編碼為K0和Ke，即

為避免因取整操作導(dǎo)致解碼后 Z0、Ze的改變，遺傳操作結(jié)束只按照式(7)進行中間時段的解碼操作，而初始和期末水位按照Z0和Ze保持不變．

2.3 適應(yīng)度函數(shù)設(shè)計

本研究為約束極大值優(yōu)化問題，其中初始和期末水位約束、最高最低水位約束已經(jīng)通過編碼設(shè)計實現(xiàn)，對于其他約束，在下面適應(yīng)度函數(shù)的設(shè)計中體現(xiàn)．單庫的適應(yīng)度函數(shù)為

式中：Qi和 Ni為 i時段的下泄流量和出力；Qi,min和Qi,max為i時段允許下泄的最小和最大流量；Ni,min為i時段水庫在電網(wǎng)要求下的最小出力．

對于出力的上限和下限，出力小于最小出力要求下的解為不可行解，已通過出力罰函數(shù)(式(11))進行懲罰處理．出力大于裝機容量的解為可行解，大于裝機容量則按照裝機容量發(fā)電(即水電站機組處于滿發(fā)狀態(tài))．

2.4 遺傳操作設(shè)計

2.4.1 基于輪盤賭選擇的正弦函數(shù)選擇算子(正弦輪盤賭)設(shè)計

選擇是建立在個體適應(yīng)度計算基礎(chǔ)上進行的．根據(jù)輪盤賭選擇算子求解水庫優(yōu)化調(diào)度問題時無法克服適應(yīng)度函數(shù)非負的情況，本研究將文獻[8]提出的三角函數(shù)選擇算子與輪盤賭選擇算子結(jié)合使用，以正弦函數(shù)為例，建立正弦輪盤賭選擇算子，以解決水庫調(diào)度中適應(yīng)度函數(shù)為負值的情況．其他 3種三角函數(shù)選擇算子可類似使用．

以ip代替適應(yīng)度函數(shù)if進行累積正弦函數(shù)值和累積正弦函數(shù)值比例的計算，在進行輪盤賭的選擇過程中每一輪產(chǎn)生一個[0，1]的均勻隨機數(shù)，對累積正弦函數(shù)值比例進行選擇．適應(yīng)度高的個體，正弦函數(shù)值大，在輪盤賭的選擇中容易被保留，而適應(yīng)度低的個體則易被淘汰．其中個體正弦函數(shù)值表示見式(1).

2.4.2 交叉和變異運算設(shè)計及參數(shù)自適應(yīng)調(diào)整

采用以水庫為單位進行的多點交叉和多點變異方式．考慮到設(shè)計的交叉算子需要有效地產(chǎn)生新個體以及水庫調(diào)度中初始和期末水位編碼固定的特殊性，采用文獻[10]提出的有限制單點交叉方式．單庫交叉斷點在個體編碼中的位置 s＝Rnd[1，n-2]；采用非均勻變異，以避免均勻變異不利于對某一重點區(qū)域進行局部搜索的問題．

式中：Ks和 Ks'為個體編碼串中 s位變異前后的編碼；B為系統(tǒng)參數(shù)，決定隨機擾動對進化代數(shù)的依賴程度．

文獻[4]已經(jīng)證明了 AGA 優(yōu)于 SGA，本研究采用文獻[1]提出的參數(shù)的自適應(yīng)調(diào)整公式．按照下列式子對交叉概率 Pc和變異概率 Pm進行自適應(yīng)調(diào)整．另外為了保證每一代的優(yōu)良個體不被破壞，在交叉和變異的過程中引入最優(yōu)保存策略．

式中：c1P ＝0.9；c2P ＝0.6；m1P ＝0.1；m2P ＝0.001；fmax、favg、f′、f分別為群體中最大適應(yīng)度值、平均適應(yīng)度值、要交叉兩個個體中較大適應(yīng)度值和要變異個體適應(yīng)度值．

3 三峽梯級實例分析

在處理三峽梯級水庫間水力聯(lián)系上，文獻[11]提出常系數(shù)線性回歸方程處理河段間水量傳播的影響，并應(yīng)用于三門峽小浪底水庫聯(lián)合優(yōu)化調(diào)度．筆者在此基礎(chǔ)上根據(jù)三峽梯級間河道水流傳播特征，提出變系數(shù)流量傳播回歸方程，用以處理梯級流量傳播中時滯與坦化變形 2個方面對優(yōu)化調(diào)度的影響．考慮到三峽梯級兩壩間河道特征，根據(jù)給定的實測相關(guān)資料對三峽水電站出庫流量 Qsx與葛洲壩水電站相應(yīng)入庫流量 Qgzb進行率定．實測資料表明：當 Qsx＜16000m3/s時，Qgzb＜Qsx；當Qsx≥ 1 6000m3/s 時，Qgzb＞Qsx．因此，筆者探討以Qsx＝16,000,m3/s為分界，以 Qsx為自變量，Qgzb為因變量，以觀測點與配合的直線在縱軸方向的離差平方和最小(OLS)為準則，建立不同三峽出庫流量下的線性回歸方程，即

三峽梯級優(yōu)化調(diào)度模型的目標函數(shù)為總出力最大，調(diào)度期T為1 d，劃分為24個時段優(yōu)化調(diào)度模型描述如下．

目標函數(shù)

式中：siN 和giN 分別為三峽和葛洲壩的階段出力；N為總的出力和．

主要約束條件如下．

水量平衡約束

水位約束

下泄流量約束

出力約束

式中：Vi,j、Vi,j+1為 j時段 i水庫初、末庫容；Ii,j、QLi,j和 Q Si,j分別為j時段i水庫入庫流量、發(fā)電引用流量和棄水流量；Zi,min、Zi,t和 Zi,max分別為 i水庫的死水位、t時段水位、正常蓄水位，假定“以水定電”模式中三峽水庫初始和期末調(diào)度水位要求均為 175 m，葛洲壩水庫均為66 m；Qi,min、Qi,t和 Qi,max分別為i水庫的最小下泄流量、t時段下泄流量和時段最大下泄流量；Ni,min、Ni,t和 Ni,max分別為 i水庫的保證出力、t時段出力和裝機容量．在水量平衡約束中，三峽入庫徑流是已知的，葛洲壩的入庫徑流按照變系數(shù)線性回歸方程(16)求得．

針對上述模型，分別采用本文提出的正弦輪盤賭選擇算子和單純輪盤賭選擇算子進行 AGA求解，對三峽水庫入庫流量為中洪水時，以小時為計算單位進行調(diào)度模擬．計算中取種群數(shù) pop為 100，水位精度popdt取 0.01 m．為了更好地比較二者的性能，分別以進化 10代、50代、100代、150代、200代、250代和300代作為終止條件進行模擬．考慮到GA是一種以隨機理論模仿生物進化的搜索方法，本研究對2種方法每個進化代數(shù)下分別進行 10次演算，取其平均值對比如圖1所示．由圖1可以看出，改進后的選擇算子在進化代數(shù)相同的情況下體現(xiàn)了較高的性能，說明改進后的選擇算子使AGA能以較快速度收斂．

圖1 兩種選擇方式在不同進化代數(shù)下的出力對比Fig.1 Comparison of output between two selection modes in different evolutionary generation

單獨選取進化代數(shù)為300作為終止條件下，將2種算法求得的最優(yōu)解進行對比分析．正弦輪盤賭選擇算子最好的一次調(diào)度出力分配見圖2和圖3，單純輪盤賭選擇算子最好的一次調(diào)度出力分配見圖 4和圖 5．

圖2 正弦輪盤賭三峽出力分配Fig.2 Sine-roulette Three Gorges output distribution

圖3 正弦輪盤賭葛洲壩出力分配Fig.3 Sine-roulette Gezhouba output distribution

在進化300代的條件下，采用正弦輪盤賭計算出的24,h梯級水庫最大出力和為36,990.0萬kW，其中三峽出力 30,855.3萬 kW，葛洲壩出力 6,134.7萬kW；而單純輪盤賭計算的 24,h最大出力和為36,970.1萬kW，其中三峽出力30,854.8萬kW，葛洲壩出力6,115.3萬kW．從優(yōu)化調(diào)度的過程可以看出，改進后的選擇算子計算結(jié)果相對較好，能夠以較快速度收斂．

圖4 單純輪盤賭三峽出力分配Fig.4 Simple roulette Three Gorges output distribution

圖5 單純輪盤賭葛洲壩出力分配Fig.5 Simple roulette Gezhouba output distribution

文獻[7]中曾提到基于三角函數(shù)輪盤賭選擇在進化初期不如單純輪盤賭算法．原因可能是由于三角函數(shù)在對適應(yīng)值進行非線性變換的時候相當于加入了噪聲，且這種處理方法可能在進化初期產(chǎn)生影響．但在進化后期，改進后選擇明顯優(yōu)于單純輪盤賭選擇，這一點在圖 1中得到了很好的證明．因此三角函數(shù)這種對適應(yīng)值加入噪聲的處理方式并沒有改變?nèi)肿顑?yōu)解．文獻[7]中提到的初期進化效果不好，是在進化代數(shù)相當小的情況下出現(xiàn)的．本研究特意在進化 10代的前提下模擬調(diào)度，證明了該進化代數(shù)下選用三角函數(shù)選擇算子進行水庫群優(yōu)化調(diào)度的結(jié)果好于單純輪盤賭．對于水庫群優(yōu)化調(diào)度問題，相當小進化代數(shù)下，只能得到局部最優(yōu)解，因此研究相當小進化代數(shù)下的調(diào)度沒有實際意義．因此，對求解水庫群優(yōu)化調(diào)度問題，正如文獻[7]提到的當個體有重復(fù)情況出現(xiàn)的時候，三角函數(shù)選擇算子能夠更好地保持種群多樣性，從而增大收斂速度，在進化后期容易找到全局最優(yōu)解；當遇到個體無重復(fù)的情況，三角函數(shù)選擇算子可避免單純輪盤賭選擇算子在消除重復(fù)個體上消耗的時間，可提高算法的效率，因此該選擇算子在求解水庫群優(yōu)化調(diào)度問題上有很好的實用性．

4 結(jié) 語

作為優(yōu)化搜索方法，GA為水庫優(yōu)化調(diào)度帶來了新的思路．但是由于選擇機制對適應(yīng)度函數(shù)依賴較高，而水庫優(yōu)化調(diào)度問題的很多約束往往不能保證適應(yīng)值非負，因此傳統(tǒng)的選擇算子均有其局限性，導(dǎo)致GA早熟．而本文提出的改進算法，在AGA的基礎(chǔ)上進行，由于采用三角函數(shù)對適應(yīng)值進行了非線性轉(zhuǎn)化，且這種加入噪聲的做法并沒有改變?nèi)肿顑?yōu)解，故能夠在選擇過程中有效地保持種群的多樣性，很好地避免GA的早熟，為遺傳算法的改進提供新的思路．

本研究在模型的建立上，以庫群調(diào)度為實例，更具有說服力．梯級間水力聯(lián)系的計算，尤其是非恒定流的計算，涉及到梯級中各水電站水頭、流量和水量平衡等，是十分復(fù)雜的問題，還沒有系統(tǒng)成熟完善的處理方法．對于上游水電站出流與下游水電站相應(yīng)入流具有密切相關(guān)關(guān)系的水電站群間流量傳播的計算問題，本文提出的流量時空演變相關(guān)分析法，為梯級間水力計算提供一個可行方向．

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

Wang Xiaoping，Cao Liming. Genetic Algorithms：Theory，Application and Implementation[M]. Xi’an：Xi'an Jiaotong University Press，2002(in Chinese).

［2］ 馬光文，王 黎. 遺傳算法在水電站優(yōu)化調(diào)度中的應(yīng)用[J]. 水科學進展，1997，8(3)：275-280.

Ma Guangwen，Wang Li. Application of genetic algorithm to optimal operation of hydropower station[J]. Advances in Water Science，1997，8(3)：275-280(in Chinese).

［3］ 王大剛，程春田，李 敏. 基于遺傳算法的水電站優(yōu)化調(diào)度研究[J]. 華北水利水電學院學報，2001，22(1)：5-10.

Wang Dagang，Cheng Chuntian，Li Min. Study on the optimal operation of hydropower station based on genetic algorithms[J]. Journal of North China Institute of Water Conservancy and Hydroelectric Power，2001，22(1)：5-10(in Chinese).

［4］ 王少波，解建倉，孔 珂. 自適應(yīng)遺傳算法在水庫優(yōu)化調(diào)度中的應(yīng)用[J]. 水利學報，2006，37(4)：480-485.

Wang Shaobo，Xie Jiancang，Kong Ke. Application of adaptive genetic algorithm in optimization of reservoir operation[J]. Journal of Hydraulic Engineering，2006，37(4)：480-485(in Chinese).

［5］ 梅亞東，朱教新. 黃河上游梯級水電站短期優(yōu)化調(diào)度模型及迭代解法[J]. 水力發(fā)電學報，2002(2)：1-7.

Mei Yadong，Zhu Jiaoxin. Short-term optimal operation model for the cascade hydroelectric stations on the upper yellow river and its solution[J]. Journal of Hydroelectric Engineering，2002(2)：1-7(in Chinese).

［6］ 宋朝紅，羅 強，紀昌明. 基于混合遺傳算法的水庫群優(yōu)化調(diào)度研究[J]. 武漢大學學報：工學版，2003，36(4)：28-31.

Song Chaohong，Luo Qiang，Ji Changming. Hybrid genetic algorithm-based optimal operation of reservoirs system[J]. Engineering Journal of Wuhan University，2003，36(4)：28-31(in Chinese).

［7］ 郝國生，嚴玉若，黃永青，等. 基于三角函數(shù)的遺傳算法選擇算子[J]. 江南大學學報，2010，9(2)：162-165.

Hao Guosheng，Yan Yuruo，Huang Yongqing，et al.Trigonometric selective operators in genetic algorithm[J]. Journal of Jiangnan University，2010，9(2)：162-165(in Chinese).

［8］ Zalzala A M，F(xiàn)leming P J. Genetic Algorithms in Engineering System[M]. London：The Institution of Electrical Engineers，1997.

［9］ 吳 斌，吳 堅，涂序彥. 快速遺傳算法研究[J]. 電子科技大學學報，1999，28(1)：49-53.

Wu Bin，Wu Jian，Tu Xuyan. Research of fast genetic algorithm[J]. Journal of UEST of China，1999，28(1)：49-53(in Chinese).

［10］ 張 慧. 遺傳算法在水電站群經(jīng)濟運行中的應(yīng)用[D].南京：河海大學水文水資源學院，2007.

Zhang Hui. Application of Genetic Algorithm in Multi-Hydropower-Station Economical Operation System[D].Nanjing：College of Hydrology and Water Resources，Hohai University，2007(in Chinese).

［11］ 楊 侃，劉云波. 基于多目標分析的庫群系統(tǒng)分解協(xié)調(diào)宏觀決策方法研究[J]. 水科學進展，2001，12(2)：232-236.

Yang Kan，Liu Yunbo. System decompositioncoordination macro-decision method for reservoirs based on multi-objective analysis[J]. Advances in Water Science，2001，12(2)：232-236(in Chinese).