改進和聲搜索算法在梯級水庫群優(yōu)化調(diào)度中的應用

王 麗 萍，吳 月 秋，張 驗 科，王 渤 權(quán)

(1.華北電力大學 水利與水電工程學院，北京 102206； 2.南京南瑞水利水電科技有限公司，江蘇 南京 210000)

近年來，我國水電能源作為一種占比較大的可再生能源，在我國電力系統(tǒng)中發(fā)揮著越來越重要的作用[1]。隨著水電能源的不斷開發(fā)，我國已經(jīng)形成了許多大型梯級水庫群。這些梯級水庫群之間不僅存在著水力聯(lián)系，還存在著電力聯(lián)系，這使得梯級水庫群優(yōu)化調(diào)度成為一個多約束、多階段、耦合性強的復雜非線性問題，其復雜性對求解方法的要求也越來越高[2-4]。為了解決這一問題，很多學者開展了相關(guān)研究，并取得了一系列成果，如傳統(tǒng)優(yōu)化算法和智能進化算法。逐步優(yōu)化算法(Progressive Optimization Algorithm， POA)[5]、逐次逼近法(Dynamic Programming with Successive Algorithm，DPSA)[6]、并行動態(tài)規(guī)劃法[7]等傳統(tǒng)優(yōu)化算法雖然在一定程度上緩解了維數(shù)災，但是POA和DPSA對初始解的依賴性比較強，且隨著變量維數(shù)和離散狀態(tài)的增加計算效率會較低；而并行動態(tài)規(guī)劃算法雖然可提高計算效率，但其受多核運算硬件平臺規(guī)模的限制。智能進化算法如遺傳算法[8]、模擬退火[9]、水循環(huán)算法[10]等，算法模型簡單、容易實現(xiàn)，但受初始種群影響，再加上多種隨機因素的存在，算法解的穩(wěn)定性有時較差。

和聲搜索算法(Harmony Search Algorithm，HSA)是一種新的智能優(yōu)化算法[11]，具有模型簡單、容易實現(xiàn)的優(yōu)點，并在解決多維函數(shù)優(yōu)化問題上展示了較遺傳算法、模擬退火算法等更好的優(yōu)化性能[12]。該算法模擬了音樂創(chuàng)作中樂師們憑借自身記憶，通過反復調(diào)整各樂器的音調(diào)，最終達到美妙和聲狀態(tài)的過程。該模擬過程類似于水庫群優(yōu)化調(diào)度模型的求解過程，對于提升梯級水庫群優(yōu)化調(diào)度模型的求解精度和效率具有重要意義。HSA對初始記憶庫(初始解)的依賴性比較強[13]，初始解的分布不均和步長調(diào)整策略導致算法在進化后期盲目搜索[14]，不能有效地調(diào)整解的結(jié)構(gòu)，使初始解的多樣性逐漸消散，容易陷入局部最優(yōu)。為此，本文提出加入均勻設(shè)計法和混沌機制的改進和聲搜索算法(Improved Harmony Search Algorithm，IHSA)，并將其應用于梯級水庫群發(fā)電優(yōu)化調(diào)度模型求解，驗證該算法的可行性和有效性。

1 改進的和聲搜索算法

HSA是一種將隨機與局部搜索相結(jié)合的啟發(fā)式優(yōu)化算法，具有參數(shù)少、計算簡單等優(yōu)點，在解決復雜、多約束、非線性等優(yōu)化問題上具有明顯的優(yōu)勢。針對和聲搜索算法對初始解的依賴性比較強和容易陷入局部最優(yōu)的缺點，本研究的改進之處可概括為兩點：一是采用均勻設(shè)計法生成初始解集，以增加初始解的多樣性和有效性；二是搜索過程中引入了混沌機制，以提高算法的全局搜索性能，避免陷入局部最優(yōu)。

1.1 算法改進

1.1.1基于均勻設(shè)計生成初始解

由于HSA主要是基于鄰域搜索的，初始解的質(zhì)量對搜索性能影響較大。在可行域內(nèi)隨機生成初始解的方式，將導致部分個體不滿足約束條件而被淘汰，這也降低了初始解集的多樣性和算法的搜索效率。因而，本文在初始解生成時引入了均勻設(shè)計 (Uniform design，UD)的思想。UD[15]僅考慮試驗點在試驗范圍內(nèi)的均勻散布，是一種基于數(shù)論和多元統(tǒng)計學的新型實驗方法，選取的試驗點更有代表性，更能反映樣本系列的主要特征。該方法與正交設(shè)計試驗方法相比，保留了正交設(shè)計的數(shù)據(jù)均衡分散性，但不考慮數(shù)據(jù)的整齊可比性，這大大減少了試驗次數(shù)，提高了試驗效率。均勻設(shè)計表由因素和水平兩要素組成，每個因素每個水平的試驗次數(shù)為一，任意兩個因素每行每列的試驗點具有唯一性，試驗次數(shù)等于最大水平數(shù)。初始解生成的過程可看為一個試驗過程，而各個解生成的過程即為試驗點選擇過程。由此可見，種群規(guī)模越大，初始解的多樣性越強，且生成的初始解都為有效解，具體初始解生成的步驟可參見文獻[16]。

1.1.2基于混沌生成機制的全局搜索

混沌搜索看似隨機但其內(nèi)部結(jié)構(gòu)非常精致，能在一定范圍內(nèi)按照自身的“規(guī)律”不重復遍歷所有狀態(tài)[17]。由于HSA在迭代搜索時主要是通過向最優(yōu)和聲不斷靠近來更新和聲記憶庫。這種更新策略可能造成和聲記憶庫中較差的解向量在迭代很多次后也沒有得到更新，容易過早陷入局部最優(yōu)。引入混沌序列，利用混沌搜索的隨機性、遍歷性和規(guī)律性來增加和聲記憶庫的多樣性，以增強算法的全局最優(yōu)性。本文采用Tent映射來生成混沌序列，Tent映射生成的混沌序列比較均勻，多樣性較強，其生成公式見式(1)。生成混沌序列的方法是先把變量從解空間映射到[0，1]空間以生成混沌序列，再將混沌序列映射回優(yōu)化空間：

(1)

式中：ck為第k次混沌迭代的混沌變量；k=1，2，3，…，M；M為總的混沌迭代次數(shù)。

1.2 IHSA計算步驟

IHSA算法的具體計算流程如圖1所示，可分6個步驟完成，依次詳細介紹如下。

圖1 IHSA計算流程Fig.1 Calculation flow of IHSA

步驟1：參數(shù)的初始化，包括和聲記憶庫HMS大小、和聲記憶庫取值概率HMCR、音調(diào)微調(diào)概率PAR、音調(diào)微調(diào)帶寬BW、最大迭代次數(shù)Tmax。本文PAR和BW[13]取值采用動態(tài)調(diào)整的方法，具體實現(xiàn)方法如下：

(2)

(3)

式中：PARmax和PARmin分別是最大、最小微調(diào)概率；t為當前迭代次數(shù)；Tmax為最大迭代次數(shù)；BWmax和BWmin分別是最大、最小調(diào)整幅度。

步驟2：采用均勻設(shè)計法在可行域內(nèi)生成初始和聲記憶庫。

步驟3：即興創(chuàng)作，根據(jù)和聲記憶庫生成新的和聲。具體數(shù)學關(guān)系式如下：

xnew(i)=

(4)

式中：xnew(i)為新生成的和聲(即解向量)；xr(i)為初始和聲記憶庫中的任意一個；rand(i)為[0，1]之間生成的隨機數(shù)；Xmax、Xmin分別為和聲記憶庫的上、下限。

如果xnew(i)是從當前和聲記憶庫中選取的，還需要通過調(diào)整音調(diào)進行微調(diào)。具體微調(diào)方式[18]如下：

(1)連續(xù)型決策變量：

(5)

(2)離散型決策變量：

(6)

式中：xr(i)為選取初始解集中的任意一個解；xr(i+k)為xr(i)的臨近值。

步驟4：計算每個和聲的適應度Ei，并更新和聲記憶庫。更新的準則為貪婪準則，即如果Enew>Eworst(Enew為新和聲的適應度，Eworst為最差和聲的適應度)，新和聲Xnew代替最差和聲Xworst，否則不變。根據(jù)最優(yōu)和聲的信息更新和聲記憶庫，也即更新種群。

步驟5：判斷是否陷入局部最優(yōu)，陷入局部最優(yōu)的判別條件是連續(xù)N次Enew

步驟6：判斷是否滿足終止條件，即是否達到最大迭代次數(shù)。若是則計算結(jié)束，輸出結(jié)果；否則返回步驟3。

2 基于IHSA的梯級水庫群發(fā)電優(yōu)化調(diào)度

IHSA在水庫群優(yōu)化調(diào)度模型計算中具有通用性，為了驗證算法的可行性和有效性，本文僅以梯級水庫群中長期發(fā)電調(diào)度為例進行研究和分析。

2.1 梯級水庫群中長期發(fā)電優(yōu)化調(diào)度模型

2.1.1目標函數(shù)

梯級水庫群中長期發(fā)電優(yōu)化調(diào)度優(yōu)化準則可定義為：在各水庫各時段來水已知和滿足約束條件的情況下，使調(diào)度期內(nèi)梯級總發(fā)電量最大。

(7)

式中：P為調(diào)度期內(nèi)梯級總發(fā)電量；Ni，j為j時段i電站的出力；Δt為時段長度；T為調(diào)度期的總時段數(shù)；M為水庫總數(shù)。

2.1.2約束條件

梯級水庫群中長期發(fā)電優(yōu)化調(diào)度的約束條件主要包括水量、水位、流量等約束。

(1)水量平衡方程：

Vi，j+1=Vi，j+(Qi，j-qi，j)Δt

(8)

(2)水庫蓄水量約束：

Vi，j，min≤Vi，j≤Vi，j，max

(9)

(3)水庫下泄流量約束：

qi，j，min≤qi，j≤qi，j，max

(10)

(4)水電站預想出力約束：

Ni，j，min≤Ni，j≤Ni，j，max

(11)

(5)邊界條件的約束，主要指水庫調(diào)度期初、末水位的限制。

(6)非負約束，即計算所用公式中的變量均為非負值。

上述式中：Vi，j，Vi，j+1分別表示水庫i第j時段初、末的蓄水量；Qi，j表示水庫i第j時段的來流量；qi，j表示水庫i第j時段的下泄流量；Ni，j，min，Ni，j，max分別表示水庫i第j時段的最小、最大庫容限制；qi，j，min表示水庫i第j時段下游綜合利用要求的最小下泄流量；qi，j，max表示水庫i第j時段的最大下泄流量要求；Ni，j，min表示第i個水庫電站的最小出力；Ni，j，max表示第i個水庫電站第j時段的預想出力，預想出力與發(fā)電水頭一一對應。

2.2 模型求解

對于水庫調(diào)度來說，不同的庫容離散點對應不同的水位值，一個調(diào)度方案即為一組滿足各種約束條件的水位值。采用IHSA進行求解時，和聲Xi可表示為N個水庫T時段內(nèi)的水位過程，具體見式(12)。和聲Xi中水庫i的均勻設(shè)計示意見圖2，m為離散點數(shù)。

(12)

圖2 水庫初始解的均勻設(shè)計示意Fig.2 Uniform design of reservoir initial solution

模型的求解步驟如下：

步驟1：參數(shù)的設(shè)置，包括和聲庫的大小、最大迭代次數(shù)、最大最小微調(diào)概率、最大最小調(diào)整幅度及和聲記憶庫取值概率。

步驟2：在可行域內(nèi)采用均勻設(shè)計法生成初始和聲記憶庫。調(diào)度期內(nèi)所劃分的時段數(shù)為均勻設(shè)計試驗的因素數(shù)，庫容離散點數(shù)為試驗的水平數(shù)，一個調(diào)度方案相當于一個試驗點。

步驟3：即興創(chuàng)作，根據(jù)和聲記憶庫生成新的和聲，生成新和聲時要考慮水位、流量、出力等約束條件。水庫調(diào)度計算時一般把決策變量作為離散型處理，故對新和聲進行音調(diào)微調(diào)時按照離散方式處理。

步驟4：更新和聲記憶庫。如果新和聲的發(fā)電總量Pnew比和聲記憶庫中最差和聲的發(fā)電總量Pworst大，新和聲代替最差和聲，否則不變。

步驟5：判斷每個和聲是否陷入局部最優(yōu)。若是，則生成混沌變量并返回步驟4，否則直接進入步驟6。

步驟6：檢查是否達到迭代終止條件(即最大迭代次數(shù)Tmax)。如果是輸出調(diào)度結(jié)果，包括qi，j、Vi，j、E總等；否則返回步驟3，直到達到迭代終止條件。

3 實例研究

3.1 梯級水庫群概況

為了驗證算法的可行性和有效性，本文選取李仙江流域的崖羊山與石門坎兩座梯級水庫為實例研究對象，進行編程計算，選取1a為調(diào)度周期，以月為調(diào)度時段。這兩座水庫都具有較好的調(diào)節(jié)性能，主要特征參數(shù)如表1所示。

表1 梯級電站基本參數(shù)Tab.1 Basic parameters of cascade hydropower stations

3.2 結(jié)果分析

采用IHSA對梯級水庫群優(yōu)化調(diào)度模型求解，并將結(jié)果與HSA和動態(tài)規(guī)劃法(DP)的結(jié)果進行對比分析。各種算法的具體參數(shù)設(shè)置如下：初始種群規(guī)模都為150，最大迭代次數(shù)都為200，PARmax和PARmin分別取0.9和0.4，BWmax和BWmin分別取0.1和0.001，HMCR=0.9； DP法的離散點個數(shù)為100。為了避免智能優(yōu)化算法的隨機性，將程序獨立運行10次，取平均值和標準差來進行比較分析。

由表2可知：① 從發(fā)電量上看，IHSA的最優(yōu)值與DP法的值僅相差0.037億kW·h，比HSA的最優(yōu)值提高了0.191億kW·h；表明IHSA的值接近于全局最優(yōu)解，全局性能比HSA好，改善了HSA容易陷入局部最優(yōu)的缺陷。② 從結(jié)果穩(wěn)定性上看，IHSA的標準差比HSA的標準差降低了98.22%，優(yōu)化結(jié)果更趨于穩(wěn)定；這主要是因為初始解的分布比較均勻且后期加入混沌序列避免算法陷入局部搜索。③ 從計算時間上來看，這3種算法中，IHSA的尋優(yōu)時間分別比DP法和HSA減少了1 092 s和2 s，提高了計算效率。這主要是因為DP法隨著水庫數(shù)目的增加呈指數(shù)增加，即容易出現(xiàn)“維數(shù)災”，而IHSA模型相對比較簡單，計算規(guī)模隨著水庫數(shù)目的增加呈線性增加。總體來說，相比HSA來說，IHSA既增加了發(fā)電量，又提高了結(jié)果的穩(wěn)定性和計算效率，優(yōu)化效果明顯優(yōu)于HSA。

表2 不同方法的優(yōu)化結(jié)果Tab.2 Optimization results of different methods

當最大迭代次數(shù)取200，不同種群規(guī)模下的優(yōu)化結(jié)果見圖3。由圖3可知，兩種方法的發(fā)電量都隨著初始種群的增加而不斷增加，但IHSA在種群規(guī)模為50時就能找到最優(yōu)解，而HSA在種群規(guī)模為80時才能找到最優(yōu)解。這主要是因為IHSA中初始解的生成采用均勻設(shè)計的方法，增加了初始解的多樣性和有效性。由此可以看出采用均勻生成初始解可以提高算法的搜優(yōu)效率。

圖3 不同種群規(guī)模的優(yōu)化結(jié)果Fig.3 Optimization results of different population sizes

為了分析不同改進策略對算法結(jié)果的影響，對HSA和IHSA的收斂過程進行了對比(見圖4)。從圖4可知，IHSA尋優(yōu)過程比較平穩(wěn)，且收斂速度比較快。這主要是因為動態(tài)調(diào)整PAR、BW和加入混沌序列增強了算法的收斂性能，使算法能快速向全局最優(yōu)解收斂。

圖4 不同迭代次數(shù)的優(yōu)化結(jié)果Fig.4 Optimization results of different iterations

4 結(jié) 論

(1) 本文針對HSA的缺點，結(jié)合均勻設(shè)計和混沌理論對其改進，提出了計算速度更快且精度更高的IHSA，尤其適合于對時效性要求更高、系統(tǒng)更為復雜的梯級水庫群智慧調(diào)度研究的更深一步探索。

(2) 實例研究雖然驗證了IHSA應用于梯級水庫群優(yōu)化調(diào)度的優(yōu)越性，同時IHSA算法具有其他算法的通用特性，在單庫和混聯(lián)水庫群等優(yōu)化問題求解中同樣具有一定的普適性。

(3) 梯級水庫群多目標優(yōu)化調(diào)度由于各目標之間的不可公度性，其計算起來較為復雜，如何將IHSA應用到梯級水庫群多目標優(yōu)化調(diào)度非劣解的獲取，還有待進一步深入研究。