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

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

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

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

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

1 改進(jìn)的和聲搜索算法

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

1.1 算法改進(jìn)

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

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

1.1.2基于混沌生成機(jī)制的全局搜索

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

(1)

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

1.2 IHSA計(jì)算步驟

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

圖1 IHSA計(jì)算流程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]取值采用動(dòng)態(tài)調(diào)整的方法，具體實(shí)現(xiàn)方法如下：

(2)

(3)

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

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

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

xnew(i)=

(4)

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

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

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

(5)

(2)離散型決策變量：

(6)

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

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

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

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

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

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

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

2.1.1目標(biāo)函數(shù)

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

(7)

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

2.1.2約束條件

梯級(jí)水庫群中長期發(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)水電站預(yù)想出力約束：

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

(11)

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

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

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

2.2 模型求解

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

(12)

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

模型的求解步驟如下：

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

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

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

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

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

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

3 實(shí)例研究

3.1 梯級(jí)水庫群概況

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

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

3.2 結(jié)果分析

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

由表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的標(biāo)準(zhǔn)差比HSA的標(biāo)準(zhǔn)差降低了98.22%，優(yōu)化結(jié)果更趨于穩(wěn)定；這主要是因?yàn)槌跏冀獾姆植急容^均勻且后期加入混沌序列避免算法陷入局部搜索。③ 從計(jì)算時(shí)間上來看，這3種算法中，IHSA的尋優(yōu)時(shí)間分別比DP法和HSA減少了1 092 s和2 s，提高了計(jì)算效率。這主要是因?yàn)镈P法隨著水庫數(shù)目的增加呈指數(shù)增加，即容易出現(xiàn)“維數(shù)災(zāi)”，而IHSA模型相對(duì)比較簡單，計(jì)算規(guī)模隨著水庫數(shù)目的增加呈線性增加。總體來說，相比HSA來說，IHSA既增加了發(fā)電量，又提高了結(jié)果的穩(wěn)定性和計(jì)算效率，優(yōu)化效果明顯優(yōu)于HSA。

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

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

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

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

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

4 結(jié) 論

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

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

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