基于分段粒子群算法的梯級水庫多目標(biāo)優(yōu)化調(diào)度模型研究

吳志遠(yuǎn)，黃顯峰，李昌平，劉志佳，顏山凱

(1.河海大學(xué) 水利水電學(xué)院，江蘇 南京 210098; 2.中國華電集團(tuán)有限公司福建分公司,福建 福州 350013; 3.華電福新能源股份有限公司 池潭水力發(fā)電廠，福建 泰寧 354400)

1 研究背景

隨著我國水電能源的持續(xù)開發(fā)，如何合理地優(yōu)化水庫群的聯(lián)合調(diào)度越來越受到行業(yè)內(nèi)的重視。一方面，隨著流域電站數(shù)目的增加、計(jì)算時間步長的減小，上下游水力和電力聯(lián)系進(jìn)一步增強(qiáng)，約束條件更加難以處理，問題復(fù)雜度呈指數(shù)型增長[1]；另一方面，梯級水電站需要綜合考慮各方面效益，目標(biāo)數(shù)的增多進(jìn)一步增加了問題的復(fù)雜度[2-3]?？梢娝畮烊簝?yōu)化調(diào)度是一個復(fù)雜的高維、非線性、強(qiáng)耦合的多目標(biāo)優(yōu)化問題[4]。

近年來，國內(nèi)外學(xué)者將智能算法應(yīng)用于水庫優(yōu)化調(diào)度領(lǐng)域，取得了不錯的效果。馮仲愷等[5]從種群初始化、進(jìn)化和變異等方面提出了改進(jìn)量子粒子群算法，應(yīng)用于烏江梯級調(diào)度；Baltar等[6]建立了基于多目標(biāo)粒子群算法的水庫群優(yōu)化調(diào)度模型，分析了其解集的收斂性和多樣性；薛保菊等[7]提出了單純形混合遺傳算法(SM-HGA),并將其應(yīng)用于水電站水庫優(yōu)化調(diào)度中，證明了其具有收斂速度快、收斂率高的優(yōu)點(diǎn)；周建中等[8]將粒子群算法(PSO)嵌入到蛙跳算法(SFLA)的分組框架中，提出了多目標(biāo)混合粒子群算法(MOSPSO)，克服了PSO收斂速度慢、易陷入局部極值[9-11]的問題。

雖然國內(nèi)外學(xué)者進(jìn)行了大量的研究工作并取得了一定進(jìn)展，但現(xiàn)有的方法仍然存在一些瑕疵。比如，大部分現(xiàn)有的智能優(yōu)化算法更適用于以月(或旬)為時間步長、計(jì)算時段數(shù)目較少的水庫優(yōu)化調(diào)度問題，一旦應(yīng)用于時間步長較小、計(jì)算時段數(shù)目較多的精細(xì)度較高的水庫優(yōu)化調(diào)度模型仍會出現(xiàn)計(jì)算效率低、甚至難以得到可行解的情況。例如，劉攀等[12]嘗試將遺傳算法和動態(tài)規(guī)劃-遺傳算法應(yīng)用于以旬為計(jì)算時段的清江梯級電站多年連續(xù)優(yōu)化，遇到了決策變量多、生成可行解難度大的問題，計(jì)算結(jié)果并不十分理想。這是由于相同調(diào)度周期下，時間步長的減少增加了問題的維度，減弱了計(jì)算時段內(nèi)出力、下泄流量等指標(biāo)的均化效應(yīng)[13]，導(dǎo)致各種約束更難以得到滿足，最終導(dǎo)致算法尋優(yōu)效率的降低。由此可見，研究適用于求解時間步長較小、計(jì)算時段數(shù)目較多的水庫優(yōu)化調(diào)度問題的算法具有一定的價(jià)值。

本文提出了分段粒子群算法(piecewise particle swarm optimization，PPSO)、多目標(biāo)分段粒子群算法(multi-objective piecewise particle swarm optimization，MOPPSO)來對時間步長較小、計(jì)算時段數(shù)目較多的水庫多目標(biāo)優(yōu)化調(diào)度問題進(jìn)行尋優(yōu)，并通過閩江流域金溪梯級水庫優(yōu)化調(diào)度的實(shí)例應(yīng)用，驗(yàn)證了其求解梯級水庫多目標(biāo)優(yōu)化調(diào)度問題的優(yōu)越性和工程實(shí)用性。

2 梯級水庫多目標(biāo)優(yōu)化調(diào)度模型

2.1 目標(biāo)函數(shù)集

2.1.1 發(fā)電效益最大目標(biāo) 考慮到市場環(huán)境下梯級水電站中各電站電價(jià)不同，本文通過各電站電價(jià)相對于龍頭電站電價(jià)的比例，折算一個調(diào)度周期內(nèi)的梯級水庫總發(fā)電量，公式如下：

(1)

式中：F1為發(fā)電效益目標(biāo)，kW·h；M為電站數(shù)目;i為電站序號，i=1，2，…，M;T為計(jì)算時段個數(shù);t為計(jì)算時段序號，t=1，2，…，T;ki為第i水電站電價(jià)相對龍頭電站電價(jià)的比值；Ni,t為第i水電站在t時段的出力，kW;Δt為計(jì)算步長，h。

2.1.2 防洪減災(zāi)目標(biāo)

(1)最高水位最小目標(biāo)。對于庫區(qū)上游，調(diào)度期內(nèi)最高水位越小，上游的搬遷或淹沒損失就越小。目標(biāo)公式如下：

F2=min(maxZt)

(2)

式中:F2為上游的防洪目標(biāo)，m；Zt為梯級水庫中龍頭水庫t時段的壩前水位值，m。

(2)最大下泄流量最小目標(biāo)。對于下游河流，洪水期下泄流量越小，下游受淹沒的可能性和損失就越小。目標(biāo)公式如下：

F3=min(maxQxi,t)

(3)

式中:F3為下游防護(hù)區(qū)的防洪目標(biāo)，m3/s;Qxi,t為第i個水庫t時段的下泄流量，m3/s。

2.2 約束條件

(1)水量平衡約束

Vi,t=Vi,t-1+(Qri,t-Qxi,t)Δt-Ei,t·Si,t-Di,t

(4)

式中：Vi,t-1、Vi,t分別為t時段初、末期的水庫蓄水量，m3；Qri,t、Qxi,t分別為第i個水庫t時段的入庫流量和下泄流量，m3/s；Ei,t為第i個水庫t時段的蒸發(fā)深度，m；Si,t為第i個水庫t時段的水庫面積，m2；Di,t為第i個水庫t時段的滲漏損失水量，m3。

(2)水位約束

Zi,t,min≤Zi,t≤Zi,t,max

(5)

式中：Zi,t,max、Zi,t,min分別為第i個水庫t時段的水位上、下限，m。

(3)發(fā)電流量約束

Qi,t,min≤Qi,t≤Qi,t,max

(6)

式中：Qi,t,max、Qi,t,min分別為第i個水庫t時段的水電站發(fā)電流量上、下限，m3/s。

(4)電站出力約束

Ni,t,min≤Ni,t≤Ni,t,max

(7)

式中：Ni,t,max、Ni,t,min分別為第i個水庫t時段的水電站出力的上、下限，kW。

(5)下泄流量約束

Qxi,t,min≤Qxi,t≤Qxi,t,max

(8)

式中：Qxi,t,max、Qxi,t,min分別為第i個水庫t時段的下泄流量上、下限，m3/s。

上述所有變量均為非負(fù)。除此之外，針對不同流域的特點(diǎn)，還可能包括生態(tài)、航運(yùn)等約束。

3傳統(tǒng)智能優(yōu)化算法在水庫調(diào)度問題中尋優(yōu)困難的原因分析

3.1 尋找可行解效率低下的原因分析

以尋找某水庫優(yōu)化調(diào)度問題可行解為例，將其各時間節(jié)點(diǎn)的水庫水量作為決策變量進(jìn)行實(shí)數(shù)編碼。當(dāng)下泄流量、出力等指標(biāo)有強(qiáng)約束時，在解向量中，某些時間段的水庫水量對變化較敏感，一旦其中某時間節(jié)點(diǎn)的水量發(fā)生改變，就容易導(dǎo)致約束的破壞。圖1為迭代過程中某一解向量所表示的水庫水量變化過程線，如圖1中實(shí)線所示，此解向量的第4、7時段不滿足約束，第2、3、5、6時段滿足約束條件但某些指標(biāo)值接近約束邊界，此時，稱第4、7時段為約束不滿足段，第2、3、5、6時段為恰滿足段?？梢?，單獨(dú)調(diào)整第5時間節(jié)點(diǎn)的水量a會導(dǎo)致第4、5時段的水庫下泄流量的改變，從而導(dǎo)致第4時段約束的破壞程度變大或者第5時段約束被破壞；同理，調(diào)整a1容易導(dǎo)致第5、6時段的約束被破壞；調(diào)整水量a2會使第7時段約束的破壞程度變大或者第6時段約束被破壞。此時，稱第5、6時段為水量結(jié)構(gòu)敏感段；同理，第3時段亦為水量結(jié)構(gòu)敏感段。進(jìn)化中，解向量內(nèi)交替出現(xiàn)的約束不滿足段和水量結(jié)構(gòu)敏感段中的變量單獨(dú)變化時，約束破壞程度往往變大，嚴(yán)重降低了算法尋找可行解的效率。

值得注意的是，第1時段滿足約束且各指標(biāo)值離約束邊界較遠(yuǎn)，稱其為過滿足段。可以看出，適當(dāng)改變水量b2不會使約束破壞程度增大，故b2在恰滿足段內(nèi)部，但不屬于水量結(jié)構(gòu)敏感段。

傳統(tǒng)智能優(yōu)化算法降低第4時段的約束破壞程度非常困難。成功率較大的方法是恰好b2、b1、b依次發(fā)生變異，在維持第2、3時段滿足約束的前提下，增加第4時間節(jié)點(diǎn)水量至b′，于是第4時段的約束破壞程度得到降低(圖1)。

需要說明的是圖1所示只是相對簡單的情況。在時間步長小、計(jì)算時段數(shù)目多的水庫優(yōu)化問題中，生成可行解的難度很高，傳統(tǒng)智能算法極易遇到解向量內(nèi)約束不滿足段與水量結(jié)構(gòu)敏感段交替出現(xiàn)、且水量結(jié)構(gòu)敏感段往往包含幾個、十幾個時間節(jié)點(diǎn)的情況，嚴(yán)重影響其計(jì)算效率。進(jìn)化中，約束不滿足段的始末水量變化程度很小，導(dǎo)致其段內(nèi)各變量達(dá)到最小的約束破壞程度后基本就不再變化了。

圖1 迭代過程中某一解向量所表示的水庫水量變化過程線

3.2 進(jìn)入可行域后尋優(yōu)效率低下的原因分析

進(jìn)入可行域后，傳統(tǒng)智能優(yōu)化算法容易遇到水量結(jié)構(gòu)敏感段過長、段數(shù)過多的問題?？梢姡?1)進(jìn)化中，直接在水量結(jié)構(gòu)敏感段內(nèi)進(jìn)行進(jìn)化操作容易破壞約束，將導(dǎo)致產(chǎn)生大量不可行解，從而影響算法的效率；(2)迭代一定次數(shù)之后，如果水量結(jié)構(gòu)敏感段所在的恰滿足段的始、末水量不變，那么其段內(nèi)的水量變化程度將會很小，這種情況會對計(jì)算效率產(chǎn)生影響。

可以看出，進(jìn)化算法在解時間步長較小、計(jì)算時段數(shù)目較多的水庫調(diào)度問題時，為提高其運(yùn)算效率，要解決兩大問題，即進(jìn)化中，在過長的水量結(jié)構(gòu)敏感段內(nèi)進(jìn)行進(jìn)化操作，導(dǎo)致產(chǎn)生大量不可行解的問題和約束不滿足段、恰滿足段的始、末水量變化程度低的問題。

4 分段粒子群算法和多目標(biāo)分段粒子群算法

針對上述原因，本文將水庫多目標(biāo)調(diào)度問題的尋優(yōu)過程分為搜索可行解、可行域內(nèi)搜索Pareto前沿兩大階段，并提出分段粒子群算法(PPSO)以及多目標(biāo)分段粒子群算法(MOPPSO)來對此問題進(jìn)行求解。所提出的算法以粒子群算法(PSO)為基本框架(PSO的計(jì)算步驟見文獻(xiàn)[14])，通過引入約束破壞向量、分段操作和特殊變異操作的改進(jìn)策略來優(yōu)化進(jìn)化過程，強(qiáng)化迭代中的種群質(zhì)量；此外，在可行域內(nèi)搜索Pareto前沿階段，MOPPSO采用了“分解聚合”求Pareto解集的改進(jìn)策略，使得所得解集盡可能接近多目標(biāo)問題的真實(shí)Pareto前沿。具體改進(jìn)策略描述如下。

4.1 約束破壞向量

在處理水庫調(diào)度問題約束時，罰函數(shù)法雖是被使用頻率較高的方法，但其缺點(diǎn)明顯：(1)罰因子的選擇十分困難，其過大、過小都會對計(jì)算結(jié)果產(chǎn)生影響[15]；(2)懲罰項(xiàng)無法攜帶解向量的約束被破壞的時段的信息。于是，本文提出約束破壞向量的概念，將其引入雙適應(yīng)度法的框架來對復(fù)雜約束條件進(jìn)行處理，同時也為下文的分段操作提供依據(jù)。

約束破壞向量是元素為0～1的一種向量，其各元素對應(yīng)著某個解在各時段的約束被破壞的程度，其模代表總時段的約束破壞程度之和，稱為約束破壞度。以出力約束和下泄流量約束為例，約束破壞向量與約束破壞度公式如下：

(9)

(10)

本文在處理復(fù)雜約束條件時，利用雙適應(yīng)度法的思想，把目標(biāo)值作為主適應(yīng)度、約束破壞度作為副適應(yīng)度。進(jìn)化時，個體首先向此代副適應(yīng)度最優(yōu)個體的方向進(jìn)化，有多個個體副適應(yīng)度相同時，再向其中主適應(yīng)度最優(yōu)的個體的方向進(jìn)化。其優(yōu)點(diǎn)是：(1)避免了罰因子的選?。?2)進(jìn)入可行域后，規(guī)避了最優(yōu)解為不可行解的情況；(3)約束破壞向量記錄了個體各時段約束破壞程度的信息，為分段操作提供依據(jù)。

4.2 分段操作和特殊變異操作

在迭代時，PPSO、MOPPSO首先利用約束破壞向量，對解向量進(jìn)行分段操作：通過現(xiàn)有約束得到約束破壞段；適當(dāng)調(diào)整現(xiàn)有約束測出恰滿足段、過滿足段；根據(jù)各段連接關(guān)系得到水量結(jié)構(gòu)敏感段。進(jìn)化時，算法除了進(jìn)行粒子群中各個個體的速度和位置的更新外，還進(jìn)行特殊變異操作：

(1)當(dāng)變異點(diǎn)落入過滿足段時，一定概率下變異點(diǎn)根據(jù)其所在時間節(jié)點(diǎn)把解向量分成前、后兩個大段，前段或后段的所有的水量都增加或減少相同變異值，其他概率下此變異點(diǎn)單獨(dú)變異。例如，第n個時間節(jié)點(diǎn)處于某一過滿足段內(nèi)部，此節(jié)點(diǎn)的變量發(fā)生變異時，公式如下：

(11)

(12)

(2)當(dāng)變異點(diǎn)落入恰滿足段時，首先判斷變異點(diǎn)位于水量結(jié)構(gòu)敏感段內(nèi)還是其他時間節(jié)點(diǎn)，如果落入水量結(jié)構(gòu)敏感段，那么整個恰滿足段的水量都增加或減少相同變異值，如果落在其他時間節(jié)點(diǎn)，則單獨(dú)變異。例如，第n個時間節(jié)點(diǎn)處于恰滿足段[l,m]內(nèi)部，此節(jié)點(diǎn)的變量發(fā)生變異時，公式如下：

(13)

(14)

式中：mut2為恰滿足段內(nèi)變異的特殊變異向量；rand為[0,1]內(nèi)隨機(jī)數(shù)；其余變量含義同上。

(3)當(dāng)變異點(diǎn)落入約束不滿足段時，首先判斷此段與過滿足段、恰滿足段的連接關(guān)系，如果此段前后均為過滿足段，除去最前的時間節(jié)點(diǎn)的約束不滿足段的水量都增加或減少相同變異值，如果一端為恰滿足段、另一端為過滿足段時，除去與恰滿足段連接的時間節(jié)點(diǎn)的約束不滿足段的水量都增加或減少相同變異值，如果前后均為恰滿足段，一定概率下此變異點(diǎn)單獨(dú)變異，其他概率下不變異。例如，第n個時間節(jié)點(diǎn)處于約束不滿足段[l,m]內(nèi)部，此節(jié)點(diǎn)的變量發(fā)生變異時，公式如下：

(15)

(16)

式中：mut3為約束不滿足段內(nèi)變異的特殊變異向量；其余變量含義同上。

特殊變異方式示意圖見圖2(流程可見圖4)。

圖2 分段粒子群算法部分變異方式示意圖

特殊變異操作的優(yōu)點(diǎn)為：(1)避免了水量結(jié)構(gòu)敏感段、約束不滿足段內(nèi)的變量單獨(dú)變異導(dǎo)致約束破壞度的增加，避免了迭代中出現(xiàn)大量不可行解的情況，提高了計(jì)算效率；(2)約束不滿足段的水量的整體增加，有助于降低此段出力約束的破壞度，水量結(jié)構(gòu)敏感段的整體抬升可以使得敏感段中的一部分時段不再敏感，有助于過長的水量結(jié)構(gòu)敏感段的解體；(3)此算法的各段之間的水量變化方式直接增加了各段的始、末水量變化的概率，有助于提高計(jì)算效率。

特殊變異操作效果示意圖如圖3所示，由圖3可以看出，變異點(diǎn)落入原水量結(jié)構(gòu)敏感段，使其整體抬高，最終降低了虛線段的約束不滿足段的約束破壞度。

圖3 特殊變異操作效果示意圖

4.3 求Pareto解集的“分解聚合”策略

進(jìn)入可行域后，MOPPSO將多目標(biāo)問題的求解過程分為兩大步驟：(1)分解尋優(yōu)步驟。將多目標(biāo)問題分為多個單目標(biāo)問題，分別進(jìn)行尋優(yōu)，使得到的各問題最優(yōu)個體盡可能接近多目標(biāo)問題的真實(shí)Pareto前沿。(2)聚合尋優(yōu)步驟。開始尋找Pareto解集：首先生成初始種群，然后將分解尋優(yōu)步驟得到的多個單目標(biāo)問題的最優(yōu)個體替換初始種群中的多個個體進(jìn)行尋優(yōu)，最終得到Pareto解集。

上述“分解聚合”求解策略的優(yōu)點(diǎn)在于：(1)可以使最終得到Pareto解集盡可能接近多目標(biāo)問題的真實(shí)Pareto前沿；(2)先使解集中的某些解優(yōu)先接近真實(shí)Pareto前沿，再在真實(shí)Pareto前沿附近搜索Pareto解集的其他解，完善解集的多樣性，避免了算法在進(jìn)化中為還未接近真實(shí)Pareto前沿的解集的多樣性花費(fèi)過多的時間。

4.4 種群排序與個體進(jìn)化

對于PPSO、MOPPSO算法，種群排序與個體進(jìn)化密不可分。

種群排序方面，對于單目標(biāo)問題，PPSO利用雙適應(yīng)度的思想，首先通過約束破壞度對個體進(jìn)行升序排序，多個個體的約束破壞度相同時，再利用目標(biāo)函數(shù)值對這些個體進(jìn)行從優(yōu)到劣的排序。對于多目標(biāo)問題，在分解尋優(yōu)步驟，MOPPSO的種群排序方式與PPSO相同；在聚合尋優(yōu)步驟，MOPPSO首先通過約束破壞度對個體進(jìn)行升序排序，多個個體的約束破壞度相同時，再對這些個體進(jìn)行非劣排序和擁擠距離排序[16]。

個體進(jìn)化方面，對于單目標(biāo)問題，PPSO首先進(jìn)行位置和速度的更新，再根據(jù)概率判斷是否進(jìn)行特殊變異操作。PPSO的特殊變異公式同上述，位置和速度的更新公式如下：

(17)

(18)

對于多目標(biāo)問題，MOPPSO處于分解尋優(yōu)步驟時，個體進(jìn)化的公式與PPSO一致；處于聚合尋優(yōu)步驟時，分解尋優(yōu)步驟得到的個體與此代的Pareto解中排序較高的個體不進(jìn)行進(jìn)化，其他個體的特殊變異公式和位置的更新公式同上述，速度的更新公式如下：

(19)

4.5 PPSO計(jì)算步驟

PPSO的運(yùn)算流程見圖4。以任意目標(biāo)函數(shù)為主適應(yīng)度函數(shù)，PPSO搜索水庫調(diào)度問題可行解的計(jì)算步驟可總結(jié)如下：

圖4 PPSO的運(yùn)算流程圖

Step 1 算法基本參數(shù)設(shè)置；

Step 2 采用各水庫各時間節(jié)點(diǎn)的水量作為決策變量進(jìn)行編碼，產(chǎn)生初始種群；

Step 3 計(jì)算各個個體的約束破壞度與主適應(yīng)度；利用雙適應(yīng)度法對種群進(jìn)行排序；

Step 4 更新個體的速度和位置；

Step 5 根據(jù)概率判斷是否發(fā)生變異，如需變異則計(jì)算約束破壞向量、進(jìn)行分段操作、特殊變異操作；

Step 6 計(jì)算個體的約束破壞向量與主適應(yīng)度；上一代最優(yōu)個體與其進(jìn)化后的個體進(jìn)行比較，如果優(yōu)于進(jìn)化后的個體則將其替換；

Step 7 判斷結(jié)束條件，如果有個體的約束破壞度達(dá)到0(即已進(jìn)入可行域)則進(jìn)入Step 8，如果不滿足結(jié)束條件轉(zhuǎn)入Step 3；

Step 8 結(jié)束。得出優(yōu)化調(diào)度可行解。

4.6 MOPPSO計(jì)算步驟

MOPPSO的運(yùn)算流程見圖5。求Pareto解集計(jì)算步驟歸納如下：

圖5 MOPPSO的運(yùn)算流程圖

Step 1 算法基本參數(shù)設(shè)置，構(gòu)造外部精英集Ⅰ、外部精英集Ⅱ；

Step 2 開始分解尋優(yōu)步驟；采用各水庫各時段水量作為決策變量進(jìn)行編碼，生成初始種群，其中某一個體被替換為PPSO解得的可行解；

Step 3 將多目標(biāo)問題分為M個單目標(biāo)問題，循環(huán)進(jìn)行M個單目標(biāo)問題的尋優(yōu)：k=1時，進(jìn)行第1個單目標(biāo)問題的尋優(yōu)，k=2時，進(jìn)行第2個單目標(biāo)問題的尋優(yōu)，……，k=M時，進(jìn)行第M個單目標(biāo)問題的尋優(yōu)，k=(M+1)時，進(jìn)行第1個單目標(biāo)問題的尋優(yōu)……;

Step 4 計(jì)算約束破壞度與目標(biāo)值；以雙適應(yīng)度法對整個種群進(jìn)行排序，排序最優(yōu)的個體如果優(yōu)于外部精英集Ⅰ的對應(yīng)單目標(biāo)問題的個體，則替換其對應(yīng)的個體，否則被外部精英集Ⅰ中對應(yīng)的個體所替換；

Step 5 更新個體的速度和位置；

Step 6 根據(jù)概率判斷是否發(fā)生變異，如需變異則計(jì)算約束破壞向量、進(jìn)行分段操作、進(jìn)行特殊變異操作；

Step 7 判斷結(jié)束條件：如果200代內(nèi)目標(biāo)函數(shù)的最優(yōu)值變化程度過小，則k=k+1,進(jìn)入Step 3；如果所有單目標(biāo)問題都已完成3次尋優(yōu)，則進(jìn)入Step 8；其他情況進(jìn)入Step 4；

Step 8 開始聚合尋優(yōu)步驟；生成初始種群；外部精英集Ⅰ中的個體代替種群中的M個個體；

Step 9 計(jì)算約束破壞度與目標(biāo)集的值，對種群進(jìn)行排序;將此代的Pareto解集加入外部精英集Ⅱ；剔除外部精英集Ⅱ的支配解，用小生境法[17]對外部精英集Ⅱ進(jìn)行維護(hù)，剔除部分位置過密集的解；

Step 10 分解尋優(yōu)步驟得到的個體與此代的Pareto解中排序較高的個體不進(jìn)行進(jìn)化，其他個體更新速度和位置；

Step 11 據(jù)概率判斷是否發(fā)生變異，如需變異則計(jì)算約束破壞向量、進(jìn)行分段操作、特殊變異操作；

Step 12 判斷是否滿足結(jié)束條件：如果達(dá)到最大迭代次數(shù)則進(jìn)入Step 13，否則進(jìn)入Step 9；

Step 13 結(jié)束。外部精英集Ⅱ?yàn)槎嗄繕?biāo)問題的Pareto解集。

5 實(shí)例分析

5.1 研究區(qū)域概況

金溪是閩江上游的二級支流，位于福建省境內(nèi)，流域面積7 201 km2。金溪流域的池潭水電站于1980年建成發(fā)電，其壩址控制流域面積4 766 km2，總庫容8.7×108m3，是金溪干流梯級開發(fā)的龍頭水庫。池潭水電站以下河段有8個水電站，即良淺、大言、黃潭、孔頭、范厝、高唐、謨武和貴嶺水電站。金溪流域中僅池潭水庫具有不完全年調(diào)節(jié)能力，其他水庫無調(diào)節(jié)能力，整體調(diào)節(jié)性能差。各電站基本參數(shù)見表1。

表1 金溪干流各梯級水電站基本參數(shù)表

5.2 計(jì)算結(jié)果對比

5.2.1 各算法求解可行解的結(jié)果對比 以平水年(50%)的徑流數(shù)據(jù)為基礎(chǔ)，以日為時間步長將調(diào)度期劃分為365段，分別利用分段粒子群算法(PPSO)、粒子群算法(PSO)、遺傳算法(GA)、帶變異的改進(jìn)粒子群算法(IPSO)、蛙跳框架的混合粒子群算法(SPSO)[8]尋找上文所述的梯級水庫多目標(biāo)優(yōu)化調(diào)度模型的可行解；進(jìn)入可行域后，再分別利用多目標(biāo)分段粒子群算法(MOPPSO)、NSGA-Ⅱ算法、多目標(biāo)粒子群算法(MOPSO)、蛙跳框架的多目標(biāo)混合粒子群算法(MOSPSO)進(jìn)行Pareto解搜索計(jì)算。從可行解搜索、Pareto解搜索兩個方面進(jìn)行各算法的對比。對比結(jié)果如表2所示，各算法的約束破壞度隨迭代次數(shù)下降曲線見圖6。

表2 各算法求解可行解結(jié)果對比

圖6 各算法的約束破壞度隨迭代次數(shù)下降曲線

5.2.2 各算法的Pareto解集質(zhì)量評價(jià)(quality indicator, QI) 目前，QI主要評價(jià)解集3個方面的性能：(1)解集與真實(shí)Pareto前沿的逼近程度(收斂性)；(2)解集在目標(biāo)空間分布的均勻程度(分布均勻性)；(3)解集在目標(biāo)空間分布的廣泛程度(分布廣泛性)[18]。

本文采用如下指標(biāo)來評價(jià)各算法得到的解集的質(zhì)量：

(1)超體積指標(biāo)(hypervolume)。超體積指標(biāo)度量的是Pareto解集與參照點(diǎn)圍成的目標(biāo)空間中的維區(qū)域的體積[19]。公式如下：

(20)

式中：HV為超體積指標(biāo)值；δ為Lebesgue測度，用來測量體積;aref為參考點(diǎn);Y為目標(biāo)空間；A為非支配解集。

超體積指標(biāo)度量解集所支配的區(qū)域的尺寸大小，HV值越大，表示其越逼近真實(shí)Pareto前沿，分布均勻性和分布廣泛性越好，對應(yīng)算法的收斂性和多樣性越好。

(2)多次計(jì)算所得解集的目標(biāo)函數(shù)最優(yōu)值的平均值。取3次計(jì)算得到的解集中各目標(biāo)函數(shù)最優(yōu)值的平均值,可描述算法的優(yōu)化水平。計(jì)算結(jié)果見表3、4。

表3 各多目標(biāo)算法計(jì)算結(jié)果匯總表

5.3 計(jì)算結(jié)果分析

從以上計(jì)算結(jié)果對比中可以看出，PPSO、MOPPSO在時間步長較小、計(jì)算時段數(shù)目較多的水庫優(yōu)化問題中較其他算法具有明顯優(yōu)勢：

(1)從可行解搜索方面來看，PPSO算法較其他算法具有極大優(yōu)勢。除PPSO算法外，其余算法在可行解搜索上尋優(yōu)效率低下，均未在20 000代內(nèi)搜索出可行解，且搜索時間普遍在1 100 s以上。其中，表現(xiàn)較好的IPSO算法的結(jié)果雖然較其他算法的結(jié)果更接近可行域，但用時也達(dá)到了1 915.91 s。從圖6可以看出，除PPSO算法外，其余各算法的約束破壞度下降速度均在1 500代前就開始放緩，并且呈現(xiàn)約束破壞度越小，下降速度越慢的趨勢。這主要是由于傳統(tǒng)智能優(yōu)化算法無法解決本文第3節(jié)所描述的“在水量結(jié)構(gòu)敏感段內(nèi)進(jìn)行進(jìn)化操作導(dǎo)致產(chǎn)生不可行解、各段的始末水量變化程度低”的兩大問題。值得注意的是，從PSO、GA以及IPSO的約束破壞度下降曲線可以看出，帶有傳統(tǒng)變異操作的智能優(yōu)化算法雖然運(yùn)算效率十分低下，但對比沒有變異操作的算法仍具一定優(yōu)勢。這是由于傳統(tǒng)的變異操作擁有概率上的“全局搜索”能力，但在具有強(qiáng)約束、時間步長較小、計(jì)算時段數(shù)目較多的水庫優(yōu)化問題中，這種能力被極大地削弱了。

PPSO算法在可行解搜索方面表現(xiàn)出色，進(jìn)入可行域的迭代次數(shù)7 561次，用時488.29 s，運(yùn)算效率優(yōu)于其他算法?？梢奝PSO算法在可行解搜索方面是具備極大的優(yōu)勢的。

表4 各多目標(biāo)算法的典型調(diào)度方案集

(2)從Pareto解搜索方面來看，MOPPSO算法較其他算法具有明顯優(yōu)勢。除MOPPSO算法外，其余算法在Pareto解搜索問題上尋優(yōu)效率低下。在3次計(jì)算中，NSGA-Ⅱ算法均在117 000代前因無進(jìn)化趨勢而停止進(jìn)化，所得解集的超體積指標(biāo)小，收斂性差，平均用時132 396.67 s；MOPSO算法在500 000代左右仍具有微弱的進(jìn)化趨勢，但解集距離真實(shí)Pareto前沿較遠(yuǎn)，超體積指標(biāo)為2.34×1011，運(yùn)行時間171 612.16 s，用時最長;MOSPSO算法在500 000代左右仍具有微弱的進(jìn)化趨勢，但解集距離真實(shí)Pareto前沿較遠(yuǎn)，超體積指標(biāo)為5.49×1011，用時71 037.67 s，其解集的收斂性、分布均勻性、分布廣泛性以及其運(yùn)行時間都比NSGA-Ⅱ與MOPSO來的優(yōu)秀。

從表3、4可以看出，在多次計(jì)算中，MOPPSO算法所得解集的發(fā)電效益最大目標(biāo)的最優(yōu)值的平均值達(dá)到了2.58×109kW·h，最高水位最小目標(biāo)的最優(yōu)值的平均值達(dá)到了275.00 m,最大下泄流量最小目標(biāo)的最優(yōu)值的平均值達(dá)到了1 243.09 m3/s，均遠(yuǎn)優(yōu)于其他算法所得結(jié)果，其超體積指標(biāo)為5.66×1012，遠(yuǎn)高于其他算法，可見MOPPSO算法所得解集較其他算法的解集更加接近真實(shí)Pareto前沿，且具有良好的收斂性、分布均勻性和分布廣泛性；MOPPSO算法達(dá)到其Pareto前沿的平均運(yùn)行時間55 548.33 s，運(yùn)算效率優(yōu)于其他算法。可以看出，MOPPSO算法在Pareto解搜索方面具有明顯優(yōu)勢。

6 結(jié) 論

本文針對傳統(tǒng)智能優(yōu)化算法在高維的水庫優(yōu)化問題中尋優(yōu)效率低下的原因，基于粒子群算法的框架，通過引入約束破壞向量、分段操作、特殊變異操作以及“分解聚合”策略等改進(jìn)策略，提出了PPSO算法以及MOPPSO算法；通過實(shí)例的綜合對比分析，證明了PPSO算法在時間步長較小、計(jì)算時段數(shù)目較多的水庫調(diào)度可行解搜索方面具備極大的優(yōu)勢；證明了MOPPSO算法所得解集具有良好的收斂性、分布均勻性和分布廣泛性，其運(yùn)算效率具有明顯優(yōu)勢。

相對其他的傳統(tǒng)智能優(yōu)化算法，本文提出的MOPPSO算法雖然具有所得解集的收斂性、分布均勻性、分布廣泛性好以及運(yùn)算效率高的優(yōu)點(diǎn)，但其在Pareto解搜索階段的運(yùn)算時間仍然過長；除此之外，變異參數(shù)的設(shè)置的好壞會對其運(yùn)算效率有一定的影響。所以亟待解決的問題是如何進(jìn)一步提高其運(yùn)算效率以及如何結(jié)合自適應(yīng)算法以取得最佳的變異處理效果。