王萬良,董建杭,王 錚,趙燕偉,張仁貢,李國慶,胡明志
(1.浙江工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 浙江 杭州 310000; 2.浙大城市學(xué)院 計算機(jī)與計算科學(xué)學(xué)院,浙江 杭州 310015;3.浙大城市學(xué)院 機(jī)械工程系,浙江 杭州 310015;4.浙江禹貢信息科技有限公司,浙江 杭州 310000)
洪水是人類一直面對的最嚴(yán)重、最頻繁、最廣泛的自然災(zāi)害之一,對人類的生命財產(chǎn)構(gòu)成了嚴(yán)重的威脅,尤其是在中國[1]。近年來,受全球氣候變化影響,洪水發(fā)生得越來越頻繁和極端,而我國60%~80%的降雨集中在汛期,加重了我國受洪水影響的程度[2]。如長江流域1954年、1998年2次特大洪水[3]。此外,還有大小沿海洪災(zāi),1989年~2014年,我國由于沿海洪災(zāi)造成的直接經(jīng)濟(jì)損失超過770億美元[4-5]。
水庫在汛期洪水管理中起重要作用,它有助于減小洪峰,減少洪水破壞,儲備洪水,是調(diào)控洪水的重要防洪工程措施[6-7],因此水庫防洪調(diào)度問題(Reservoir Flood Control Operation,RFCO)一直以來都是研究的熱門領(lǐng)域。RFCO問題是復(fù)雜的多目標(biāo)優(yōu)化問題,存在眾多相互依存的決策變量,涉及相互沖突的優(yōu)化目標(biāo),RFCO問題優(yōu)化目標(biāo)的沖突主要集中在上游壩體安全和下游堤防安全的沖突上[8],要保證上游壩體安全,則要求水庫盡可能多地泄洪,保證水位維持在安全線,而要保證下游河道安全,減少分洪區(qū)壓力則要求水庫盡可能儲水,以減少下游的風(fēng)險。顯然,在一次防洪調(diào)度決策中,要同時兼顧二者,決策者需要一種“平衡”的解決方案。為了求解上述問題,早期學(xué)者多采用諸如線性規(guī)劃(Linear Programming,LP)[9],動態(tài)規(guī)劃(Dynamic Programming,DP)[10-11]的方法進(jìn)行求解,這些方法一般采用對各個目標(biāo)進(jìn)行加權(quán),或者將次要目標(biāo)轉(zhuǎn)化為約束的方法進(jìn)行求解,加權(quán)法需要一些人為的先驗經(jīng)驗,而約束法得到的一般不是真實的帕累托前沿,在實際應(yīng)用中受到一定的限制。受生物智能啟發(fā),計算智能迅速發(fā)展,一些啟發(fā)式的智能優(yōu)化算法為防洪調(diào)度的決策提供了一些新思路,諸如遺傳算法(Genetic Algorithm,GA)之類的智能優(yōu)化算法逐漸被應(yīng)用于RFCO問題[12-13],隨后又有學(xué)者陸續(xù)將蟻群算法(Ant Colony Optimization,ACO),差分進(jìn)化(Differential Evolution,DE)算法和粒子群算法(Particle Swarm Optimization,PSO)等應(yīng)用于RFCO[14-15]。
RFCO問題是多目標(biāo)優(yōu)化問題,各個目標(biāo)相互沖突,因此不可能找到單個優(yōu)化方案同時優(yōu)化各個優(yōu)化目標(biāo)。相反,RFCO問題的解決方案應(yīng)為各個目標(biāo)的良好權(quán)衡,這種良好權(quán)衡的集合稱為帕累托最優(yōu)解(PS),帕累托最優(yōu)解中任一目標(biāo)都不能在不損害其他目標(biāo)的情況下進(jìn)一步改進(jìn),帕累托最優(yōu)解在目標(biāo)空間的圖像稱為帕累托前沿(PF)。上述針對RFCO的單目標(biāo)優(yōu)化方法都有一個共同的缺點,即對RFCO的PF的形狀或者連續(xù)性比較敏感。而多目標(biāo)優(yōu)化方法,可以在一次運(yùn)算中得到一組優(yōu)化方案,為決策者提供更多的信息。
近年來,各種多目標(biāo)進(jìn)化算法相繼提出,這些多目標(biāo)算法主要集中在對啟發(fā)式單目標(biāo)算法的改進(jìn)。DEB[16]等通過引入快速非支配排序、擁擠距離排序以及精英保留策略提出的基于帕累托支配的多目標(biāo)優(yōu)化算法NSGA-Ⅱ,是對單目標(biāo)優(yōu)化算法GA的改進(jìn),NSGA-Ⅱ目前是最流行的多目標(biāo)優(yōu)化算法之一。PSO是最流行的模仿鳥類社會行為的群智能算法,該算法優(yōu)秀的收斂速度促使眾多學(xué)者嘗試將其擴(kuò)展用以解決多目標(biāo)優(yōu)化問題(Multiple-objective Optimization Problems,MOPs),比如COELLO等[17]基于改進(jìn)PSO提出的多目標(biāo)粒子群算法(Multi-objective Particle Swarm Optimization,MOPSO)。DE由于其優(yōu)秀的收斂速度且易于操作,也被多次改進(jìn),且應(yīng)用于RFCO問題,如覃暉等[18]將外部檔案引入多目標(biāo)差分進(jìn)化算法,并加入自適應(yīng)柯西變異的防止算法早熟收斂的機(jī)制,成功應(yīng)用于三峽水利樞紐的防洪調(diào)度問題。此外,改進(jìn)粒子群算法、改進(jìn)蟻群算法等改進(jìn)的多目標(biāo)群智能算法均為RFCO問題提供了有效的解決方案[19-20]。
鯨魚優(yōu)化算法(Whale Optimization Algorith,WOA)是學(xué)者M(jìn)IRJALILI等[21]受座頭鯨捕食行為啟發(fā)提出的一種群智能算法,并被證明在29個數(shù)學(xué)優(yōu)化問題和6個結(jié)構(gòu)設(shè)計問題上的有效性和競爭力。從被提出以來,WOA被成功應(yīng)用于許多研究和應(yīng)用領(lǐng)域。與眾多優(yōu)化算法相比,WOA可以以更小的代價更快的速度收斂于最優(yōu)結(jié)果。近年來,一些學(xué)者開始著手于將WOA進(jìn)行拓展,用以處理MOPs,如NSMOWOA(new non-dominated sorting based on multi-objective WOA),采用了一種全新的非支配排序,根據(jù)適應(yīng)度的值來選擇最優(yōu)解,并用標(biāo)準(zhǔn)的WOA算子來更新鯨魚的位置[22]。GOT等[23]提出一種引導(dǎo)種群檔案的多目標(biāo)鯨魚算法(Guided Population Archive WOA,GPAWOA),引入了外部檔案并采用了一種新的引導(dǎo)者選擇策略。
本文提出一種針對水庫防洪調(diào)度的改進(jìn)鯨魚算法,多目標(biāo)文化鯨魚算法(Multi-objective Culture WOA,MOCWOA)。WOA雖然有收斂速度快且操作簡單的優(yōu)點,但是也有容易陷入局部最優(yōu)的缺點,且在處理MOPs上仍有較大的改進(jìn)空間。本文將WOA與文化算法(Cultural Algorithm,CA)相結(jié)合,文化算法是REYNOLDS等[24]基于自然界文化加速生物進(jìn)化的原理提出的一種雙層進(jìn)化模型。該雙層模型包含種群空間和信度空間,以及兩個空間進(jìn)行協(xié)調(diào)的通信協(xié)議,種群空間實現(xiàn)種群的進(jìn)化,信度空間實現(xiàn)知識的更新。這種雙層進(jìn)化機(jī)制能更充分地利用進(jìn)化信息,提高進(jìn)化效率。文化框架最早與遺傳算法相結(jié)合[25],后續(xù)學(xué)者將文化框架與粒子群算法和差分進(jìn)化算法等基于種群的算法相結(jié)合[26-27],并證明了文化算法在提高基于種群的進(jìn)化算法效率上具有一定普適性。本文提出的MOCWOA以CA為框架,在種群空間采用WOA,在信度空間對框架中原有的 3 種知識結(jié)構(gòu)進(jìn)行改進(jìn),使其能夠有效引導(dǎo)鯨魚種群的搜索,并以此來提高算法得到的解的多樣性和收斂精度。
本章主要介紹MOPs的相關(guān)模型,以及水庫防洪調(diào)度問題相關(guān)背景和模型。
一個具有n維決策向量和m個目標(biāo)的多目標(biāo)優(yōu)化問題(MOPs)可以通過以下數(shù)學(xué)模型表示
minF(x)={f1(x),f2(x),…,fm(x)};
s.t.
x∈Ω。
(1)
其中Ω為決策空間,x={x1,x2,…,xn}∈Ω是n維決策向量。F(x)由m個目標(biāo)f1(x),f2(x),…,fm(x)組成。
上文已經(jīng)提到過,在MOPs問題中沒有單一的最優(yōu)解,取而代之的是一組良好權(quán)衡的集合,該集合稱為帕累托最優(yōu)解集(PS),帕累托最優(yōu)解集在目標(biāo)空間的圖像稱為帕累托前沿(PF),下面給出帕累托最優(yōu)解的相關(guān)數(shù)學(xué)定義:
定義1帕累托支配。解u支配解v(記uv),當(dāng)且僅當(dāng):
(2)
定義2帕累托最優(yōu)解。在可行搜索空間內(nèi),給定解u不受其他任何解支配,則稱定解u為帕累托最優(yōu)解,也稱非支配解:
(3)
定義3帕累托最優(yōu)解集。所有帕累托最優(yōu)解的集合稱為帕累托最優(yōu)解集(PS),定義為:
(4)
定義4帕累托前沿。帕累托最優(yōu)解集在目標(biāo)空間的投影稱為帕累托前沿(PF),定義為:
PF={F(x)|x∈PS}。
(5)
在處理防洪調(diào)度問題的過程中,決策者需要考慮的防洪目標(biāo)一般有3類[28]:水庫壩體自身安全要求、庫區(qū)淹沒損失和下游淹沒損失。前兩類包含了上游壩體安全和上游淹沒損失等與上游水庫蓄洪量相關(guān)的防洪要求,這些防洪要求一般由防洪過程中的上游最高水位、汛期末水庫水位和上游高水位歷時表征;而下游淹沒損失則一般包括下游堤防、下游淹沒損失以分洪區(qū)流量等多方面的防洪目標(biāo),一般以防洪期間最大下泄流量和分洪區(qū)淹沒損失表征。
雙目標(biāo)優(yōu)化問題是多目標(biāo)優(yōu)化問題中的一個特例,考慮到在處理防洪調(diào)度問題過程中,決策者主要要解決的是上游防洪目標(biāo)和下游防洪目標(biāo)兩個相互沖突的目標(biāo),本文將水庫防洪調(diào)度模型建立為雙目標(biāo)優(yōu)化問題模型,并用提出的多目標(biāo)文化鯨魚算法來解決該雙目標(biāo)水庫調(diào)度問題[29]。
在該雙目標(biāo)水庫防洪調(diào)度模型中,上游的防洪目標(biāo)以防洪調(diào)度過程中水庫壩前最高水位表示:
f1(Q)=max(Zt),t=1,2,…,T。
(6)
式中:Zt表示第t時段的水庫壩前水位,Q=(Q1,Q2,…,QT)為決策變量,Qt,t=1,2,…,T為t時段的決策者控制的水庫下泄流量,影響Zt的主要因素為入庫流量I和下泄流量Q。
下游的防洪目標(biāo)以防洪調(diào)度過程中最大下泄流量表示為:
f2(Q)=max(Qt),t=1,2,…,T。
(7)
約束條件為以下3項:
(1)水庫水位的上下限約束:Zmin≤Zt≤Zmax。在調(diào)度過程中,為保證水庫壩體的安全,各個調(diào)度期的水位Zt必須介于水庫允許的最高水位Zmax和最低水位Zmin之間,若在整個調(diào)度期中出現(xiàn)水位高于水庫工程信息中規(guī)定的最高水位的情況,則可能會造成嚴(yán)重的后果[30]。
(2)最大下泄流量約束:0≤Qt≤Qmax。其中Qmax表示下游能承受的最大下泄流量,該約束表示調(diào)度期內(nèi)各個時段的下泄流量不得高于下游最大能承載的下泄流量。
(3)水量平衡方程[31]:Vt=Vt-1+It-Qt。水量平衡方程表示庫容和入庫流量、出庫流量之間的關(guān)系,式中:Vt和Vt-1分別表示調(diào)度期t和調(diào)度期t-1時的庫容,It和Qt分別表示調(diào)度期t的入庫流量和下泄流量。
根據(jù)上文所述,本文所提出的多目標(biāo)文化鯨魚算法主要針對以下泄流量為決策變量,并滿足水庫防洪調(diào)度過程中水庫最高水位和下游最大下泄流量2個目標(biāo)要求的RFCO問題,該RFCO問題模型表示如下:
(8)
上述模型考慮了防洪調(diào)度過程中壩前最高水位f1和樞紐最大下泄流量f2兩方面的防洪目標(biāo)。其中:f1表示水庫上游的防洪要求,它需要水庫盡可能多地泄洪以保證壩體的安全;f2表示下游地區(qū)的防洪要求,它需要水庫盡可能的儲水以防止下游成災(zāi),兩個目標(biāo)相互沖突;Q=(Q1,Q2,…,QT)為決策變量;Qt(t=1,2,…,T)為t時段的下泄流量;T為調(diào)度時段總數(shù);Zt為t時段的水庫水位;Zmax和Zmin分別表示水庫允許的最低水位和最高水位;Qmax為最大允許下泄流量,表示下游河道的最大承載能力;Vt為t時段的水庫庫容;It為t時段的入庫流量。
該RFCO模型的3個約束分別為:約束(1)水庫水位Zt(t=1,2,…,T)必須是介于Zmax和Zmin之間的值;約束(2)下泄流量Qt(t=1,2,…,T)必須不得大于下游承載能力Qmax的非負(fù)數(shù);約束(3)庫容平衡方程,利用庫容平衡方程,根據(jù)t時段的進(jìn)出水量,計算t時段的庫容。
本章主要介紹WOA的工作流程和文化算法框架。
鯨魚在捕食過程中體現(xiàn)出一種獨特的社會行為,這種行為使其捕食更高效,澳大利亞學(xué)者M(jìn)IRJALILI等[21]受這種行為啟發(fā),開發(fā)了一種新的基于群體的元啟發(fā)式算法——鯨魚優(yōu)化算法。該算法模擬座頭鯨氣泡網(wǎng)狩獵策略(bubble-net attacking method),相比一些其他優(yōu)化算法,WOA操作更簡單,且收斂速度更快。WOA共設(shè)計了2種方法——縮圈包圍(shrinking encircling)和螺旋更新(spiraling updating)對座頭鯨獨特的氣泡網(wǎng)狩獵策略進(jìn)行建模,除此之外,座頭鯨還會隨機(jī)搜尋獵物(searching for prey),下面將簡單介紹WOA的數(shù)學(xué)模型。
2.1.1 包圍捕食與搜尋獵物
座頭鯨能夠識別獵物的位置并將其包圍。由于真實的最優(yōu)解在目標(biāo)空間的位置不是先驗的,WOA假定當(dāng)前種群的最優(yōu)解為獵物所在位置,用X*表示,在X*確定之后,其他個體以以下方式運(yùn)動達(dá)到向X*運(yùn)動的效果:
D=|C·X*-X(t)|,
(9)
X(t+1)=X*-A·D,
(10)
A=2α·r1-α,
(11)
C=2·r2。
(12)
其中:X*為當(dāng)前的最優(yōu)解,即獵物所在,t為當(dāng)前迭代代數(shù),α為一個從2到0線性隨迭代代數(shù)遞減的系數(shù),r1和r2為[0,1]間的隨機(jī)向量。
WOA除了模擬座頭鯨群向獵物靠近的行為之外,還模擬了座頭鯨群搜尋獵物位置的行為,通過以下公式表示:
D=|C·Xrand-X(t)|,
(13)
X(t+1)=Xrand-A·D。
(14)
其中Xrand是隨機(jī)選擇的當(dāng)前種群中的個體,在該運(yùn)動方式下,座頭鯨會根據(jù)彼此的位置進(jìn)行隨機(jī)搜索。
WOA通過|A|的數(shù)值大小來判斷鯨魚群進(jìn)行縮圈包圍或搜尋獵物,當(dāng)|A|<1時,種群進(jìn)行縮圈包圍,當(dāng)|A|≥1時,種群進(jìn)行搜尋獵物。
2.1.2 氣泡網(wǎng)狩獵策略
WOA設(shè)計了兩種運(yùn)動機(jī)制來模擬座頭鯨群的氣泡網(wǎng)狩獵策略。第一種是通過線性降低式(11)中α的值來實現(xiàn)的縮圈包圍機(jī)制;另一種是螺旋更新機(jī)制,其數(shù)學(xué)建模如下:
B=|X*-X(t)|,
(15)
X(t+1)=X*+B·ebk·cos(2π·k)。
(16)
其中:b為一個用以控制對數(shù)螺旋線形狀的常數(shù),k為[-1,1]間的隨機(jī)數(shù)。
值得注意的是,縮圈包圍和螺旋更新在種群的運(yùn)動過程中同時存在,通過一個隨機(jī)產(chǎn)生的[0,1]間的數(shù)p來控制:
(17)
前文已經(jīng)提到過,文化算法是一種雙層進(jìn)化模型,由種群空間和信度空間構(gòu)成,并通過特定的通信協(xié)議協(xié)調(diào)種群空間和信度空間的相互影響。
隱含在進(jìn)化過程中的各類信息以知識結(jié)構(gòu)的形式存儲在信度空間中,用以指導(dǎo)種群的進(jìn)化。種群空間則用于實現(xiàn)基于種群的進(jìn)化算法,它可以實現(xiàn)群智能算法的各種算子操作,對個體進(jìn)行評價,并使種群進(jìn)化,同時種群空間需要將進(jìn)化過程中隱含的有利于進(jìn)化的信息和優(yōu)良個體樣本提供給信度空間。信度空間通過接受函數(shù)接受種群空間提供的優(yōu)秀個體樣本以及各類隱含信息,以知識結(jié)構(gòu)的形式加以概括、描述和儲存。同時通過影響函數(shù)影響種群空間進(jìn)化,提高種群空間的進(jìn)化效率,種群空間和信度空間相互影響的整個過程如圖1所示。
信度空間的核心在于知識如何描述和更新。信度空間的知識結(jié)構(gòu)一般被劃分為5類:狀況知識、規(guī)范知識、拓?fù)渲R、領(lǐng)域知識和歷史知識。下面將詳細(xì)介紹信度空間知識結(jié)構(gòu)及其如何影響種群空間。
本文所提的多目標(biāo)文化鯨魚算法是在文化算法的框架下對鯨魚算法的改進(jìn),它基于帕累托支配,使用文化算法框架中的信度空間存儲進(jìn)化過程中發(fā)現(xiàn)的知識,以幫助種群收斂。在迭代過程中,隨著非支配解的數(shù)量迅速增加,信度空間的大小也會增加,在一定程度上增加了算法的計算復(fù)雜度。為避免該問題,采用一種截斷方法保證信度空間的大小不超過一定的閾值。同時,為了保證算法迅速收斂并保證前沿多樣性,選擇合適的領(lǐng)導(dǎo)個體(X*)至關(guān)重要,設(shè)計算法時,本文考慮了兩個重要的策略:①采用一種有效的信度空間更新策略,以提高所獲得前沿的收斂性和多樣性;②采用一種有效的領(lǐng)導(dǎo)者選擇策略。下面介紹信度空間的知識結(jié)構(gòu)、信度空間的更新策略以及信度空間對種群進(jìn)化過程的影響。
3.1.1 狀況知識
狀況知識是CHUNG[32]于1997年在解決靜態(tài)環(huán)境實值函數(shù)優(yōu)化問題時提出的,用于記錄進(jìn)化過程中的較優(yōu)個體??梢岳斫鉃闋顩r知識存儲著進(jìn)化過程中發(fā)現(xiàn)的精英解,這與很多優(yōu)化算法使用的外部檔案或外部種群類似。一般來說,狀況知識存儲的優(yōu)秀個體數(shù)量都會有閾值,即狀況知識內(nèi)存大小為Smax,狀況知識的結(jié)構(gòu)描述為:
〈E1,E2,…,Es〉。
(18)
式中Ei(i=1,2,…,s)表示第i個較優(yōu)個體,在MOCWOA中本文采用以下方法更新狀況知識:創(chuàng)建一個集合,在算法每次迭代結(jié)束時,將現(xiàn)有狀況知識中存儲個體和迭代進(jìn)化之后的種群加入該集合中,根據(jù)帕累托支配原則確定集合中所有非支配解,將其中的非支配解作為新的狀況知識,同時清空集合內(nèi)存。當(dāng)狀況知識的內(nèi)存超過閾值Smax時,對狀況知識進(jìn)行截斷操作:
(1)計算狀況知識中各個個體的擁擠距離;
(2)根據(jù)擁擠距離對個體進(jìn)行排序;
(3)刪去狀況知識中擁擠距離較小的個體使?fàn)顩r知識的內(nèi)存等于Smax。
擁擠距離排序策略是一種能有效保證種群多樣性的方法,在MOPs中被廣泛采用,通過計算一個特定解到相鄰解的空間距離來表示這個解的密度,在目標(biāo)空間具有最大和最小目標(biāo)值的邊界上的解被定義為具有∞的擁擠距離。
3.1.2 規(guī)范知識
規(guī)范用于描述問題的可行解空間。針對具有n維變量的優(yōu)化問題,規(guī)范知識結(jié)構(gòu)描述為
〈V1,V2,…,Vn〉。
(19)
式中:Vi=[(li,ui),(Li,Ui)](i≤n),ui和ui分別表示第i維變量的上限和下限;Ui和Li分別表示對應(yīng)于上下限的適應(yīng)度。這種知識結(jié)構(gòu)可以提高種群的搜索效率,主要表現(xiàn)在使搜索空間保持在優(yōu)良個體被發(fā)現(xiàn)的搜索范圍內(nèi)。鯨魚算子操作可能會導(dǎo)致新的向量超出變量的邊界,大多數(shù)處理這種情況的最初方法是使它們等于邊界。本文用規(guī)范知識結(jié)構(gòu)來代替原來的變量邊界。由于規(guī)范知識結(jié)構(gòu)中的區(qū)間比原始變量邊界更強(qiáng),這些區(qū)間是發(fā)現(xiàn)優(yōu)良個體的空間,在這些空間中搜索可以提高算法的收斂速度。
規(guī)范知識的更新基于狀況知識,當(dāng)狀況知識更新之后,將狀況知識中每一維的最小值和最大值作為新的區(qū)間來更新規(guī)范知識。
3.1.3 歷史知識
歷史知識最早是針對動態(tài)優(yōu)化問題提出的,用于記錄進(jìn)化過程中發(fā)生的重要事件[31]。本文引入歷史知識主要用于避免算法早熟收斂。進(jìn)化算法早熟收斂的根本原因在于種群的多樣性隨著進(jìn)化過程急劇下降。本文將種群的多樣性信息以式(20)的形式存儲:
〈D1,D2,…,Dn〉。
(20)
式中Di(i≤n)表示當(dāng)前種群第i維的多樣性,
(21)
式中Qi,max和Qi,min分別表示種群中第i維的最大值和最小值,當(dāng)式(21)中分母為0時,Di=1。
若Di<ε(本文中ε=0.1)對種群中的第i維進(jìn)行以下操作:
Qi=Qi·(1+η·C(0,1))。
(22)
式中:η為變異比例系數(shù),η=0.5;C(0,1)為服從(0,1)柯西分布的隨機(jī)變量。
歷史知識的更新主要發(fā)生在每次迭代完成后,根據(jù)新種群更新歷史知識,若每代都計算歷史知識,將導(dǎo)致算法的運(yùn)算速度緩慢,本文選取每迭代10次進(jìn)行一次歷史知識更新。
領(lǐng)導(dǎo)個體即前文所提的X*,是引導(dǎo)種群走向更逼近帕累托前沿和更良好分布的關(guān)鍵,在原始的WOA算法中,僅需選擇種群中適應(yīng)度最高的個體作為X*,但對于多目標(biāo)問題而言,若簡單地選擇單個個體作為X*,將導(dǎo)致解在目標(biāo)空間的分布在X*附近集結(jié),種群的多樣性被破壞。
本文采用以下領(lǐng)導(dǎo)個體選擇策略:
(1)計算狀況知識中個體的擁擠距離;
(2)將狀況知識中個體按擁擠距離降序排序;
(3)將狀況知識中前Smax×10%個體作為領(lǐng)導(dǎo)個體候選部分;
(4)每個個體進(jìn)行更新時,隨機(jī)從候選部分選擇一個個體作為領(lǐng)導(dǎo)個體(X*)。
實際上,在狀況知識更新時,已經(jīng)對狀況知識中的個體進(jìn)行過擁擠距離排序,因此在選擇領(lǐng)導(dǎo)個體時只需進(jìn)行上述的第(3)和第(4)步。
MOCWOA算法流程如圖2所示,從隨機(jī)生成種群中個體開始,隨后根據(jù)式(17)計算種群中每個個體的適應(yīng)度,根據(jù)非支配排序以及擁擠距離排序更新狀況知識以及狀況知識候選部分。根據(jù)狀況知識更新規(guī)范知識。在完成以上知識結(jié)構(gòu)的準(zhǔn)備之后,算法進(jìn)入主循環(huán)。更新隨機(jī)數(shù)p,若p<0.5,則通過式(9)和式(10)更新變量A、C,若|A|>1,則通過式(12)和式(13)對種群中的每個個體進(jìn)行更新,其中Xrand是從當(dāng)前種群中隨機(jī)選擇的個體;如果|A|≤1,則通過式(9)和式(10)更新種群中的每個個體,其中X*是從狀況知識候選部分隨機(jī)挑選的個體。若p≥0.5,則通過式(15)和式(16)更新種群,與上述相同,在更新每個個體時,隨機(jī)從狀況知識候選部分選擇X*。以上主要是種群空間的更新方式,在完成種群空間的更新后,若當(dāng)前迭代次數(shù)為10的倍數(shù),則更新歷史知識,隨后使用種群空間的種群更新信度空間狀況知識結(jié)構(gòu)(若超出最大存儲量,則進(jìn)行截斷操作)和規(guī)范知識結(jié)構(gòu),進(jìn)入下一代循環(huán),直至達(dá)到跳出循環(huán)條件,輸出狀況知識作為最終結(jié)果。
本文各實驗均在64-bit Windows 10的MATLAB2018b編譯環(huán)境下運(yùn)行,測試實驗在同一臺計算機(jī)上進(jìn)行:Intel Core i7-4900 CPU @3.60 GHZ 12.0 GB RAM。
為證明MOCWOA的有效性,本文選擇典型的廣泛使用的測試函數(shù)——專門用于測試優(yōu)化算法在雙目標(biāo)優(yōu)化問題上性能的ZDT標(biāo)準(zhǔn)測試函數(shù)來測試算法。
一般來說,多目標(biāo)優(yōu)化有2個目標(biāo):①讓算法得到的帕累托前沿盡可能接近真實的帕累托前沿,即收斂性;②找到盡可能多的非支配解,即多樣性。本文引用以下指標(biāo)來度量各個多目標(biāo)優(yōu)化算法得到帕累托前沿的收斂性和多樣性
(1)IGD(Inverted Generational Distance)
IGD以真實的帕累托前沿作為參考,并計算帕累托前沿中每個參考點到最近的非支配解的距離:
(23)
其中:n表示真實帕累托前沿參考點的數(shù)量,di表示真實帕累托前沿與優(yōu)化算法得到的最近的解的歐氏距離。IGD指標(biāo)可以用于評價算法得到的近似前沿的收斂性。
(2)Sp(Spacing)
為了定量比較算法所得結(jié)果的多樣性,引用Sp指標(biāo)來評估算法得到的近似前沿的均勻分布程度,Sp指標(biāo)定義為:
(24)
式中:
(25)
(3)HV(Hyper Volume)
HV指標(biāo)表示算法獲得的非支配解集與真實帕累托前沿參考點圍成的目標(biāo)空間中的區(qū)域體積,可以評價算法的綜合性能,即同時評價收斂性和多樣性:
(26)
式中:δ表示Lebesgue測度,用來測量體積;|S|表示非支配解集的數(shù)目;vi表示參照點與解集中第i個解構(gòu)成的超體積。
上述3個指標(biāo)中,IGD和SP的值越小表示算法的性能越好,而HV的值越大表示算法的性能越好。
4.2.1 狀況知識結(jié)構(gòu)以及候選部分選擇對算法效率的影響
在算法不引入狀況知識的情況下,每次進(jìn)化結(jié)束之后,將子種群和父種群放在一個集合中,通過非支配排序的方式,選擇排序較前的N個個體(N表示種群大小)作為新種群。而候選部分只有采用狀況知識結(jié)構(gòu)才會存在,這里主要對比采用狀況知識結(jié)構(gòu)后不同百分比的候選部分對算法的影響,選擇10%、20%、50%和100%四種不同的百分比。HV指標(biāo)可以作為判斷算法結(jié)果收斂性和多樣性的依據(jù),為了比較不同狀況知識以及不同百分比候選部分對多目標(biāo)文化鯨魚算法的影響,本節(jié)統(tǒng)計了不同候選部分選擇下的算法,在ZDT測試集實驗結(jié)果中,HV指標(biāo)隨進(jìn)化數(shù)量變化的數(shù)據(jù)如圖3所示。算法種群選擇N=100,迭代次數(shù)500次,除狀況知識結(jié)構(gòu)外保持算法其他參數(shù)設(shè)置不變,每組實驗重復(fù)30次,圖3為不同候選部分百分比選擇下最優(yōu)結(jié)果所繪制的對比圖。
在實驗過程中,可以明顯發(fā)現(xiàn)在不引入狀況知識或是將所有狀況知識都作為領(lǐng)導(dǎo)個體的方法,很難找到或逼近真實的帕累托前沿,引入狀況知識后并在每個個體進(jìn)化時,從狀況知識的前10%、20%或50%的個體中隨機(jī)選擇一個個體作為進(jìn)化個體的領(lǐng)導(dǎo)個體的策略,能有效提高算法的收斂性。從實驗結(jié)果來看,除了ZDT4測試集上,10%的選擇策略略遜于20%和50%的選擇策略,其余情況下,10%的選擇策略要優(yōu)于20%和50%的選擇策略,而不引入狀況知識或不引入候選部分的結(jié)果幾乎都是幾種選擇策略里最差的。上述實驗說明狀況知識可以提高WOA算子尋找帕累托前沿的能力,且取10%的候選部分作為領(lǐng)導(dǎo)個體的選擇集合將會更容易得到接近前沿的解。
4.2.2 規(guī)范知識結(jié)構(gòu)對算法效率的影響
規(guī)范知識的使用在狀況知識的基礎(chǔ)之上,上一節(jié)已經(jīng)介紹了狀況知識的有效性,在使用規(guī)范知識時,本節(jié)引入狀況知識,并將狀況知識前10%作為候選部分。下面主要對比使用規(guī)范知識和不使用規(guī)范知識時,算法在ZDT測試集上,HV指標(biāo)隨種群進(jìn)化的變化情況。在使用規(guī)范知識的實驗中,當(dāng)某個個體在進(jìn)化過程中某維超出了該維的上下界后,該維度的值將用存儲在規(guī)范知識中的界限來代替,而在不使用規(guī)范知識的實驗中,對待這樣的個體將直接賦予原上限或下限的值。算法種群選擇N=100,迭代次數(shù)200次,除使用規(guī)范知識與否保持算法其他參數(shù)設(shè)置不變,每組實驗重復(fù)30次,圖4為2種組別最優(yōu)結(jié)果所繪制的對比圖。
從圖4中可以看出,除了在ZDT4的對比實驗中使用規(guī)范知識與不使用規(guī)范知識對比不明顯,其余實驗中使用規(guī)范知識都優(yōu)于不使用規(guī)范知識的結(jié)果,且在ZDT6實驗中,使用規(guī)范知識比不使用規(guī)范知識有明顯優(yōu)勢。實驗結(jié)果表明,使用規(guī)范知識后,能提高多目標(biāo)文化鯨魚算法得到結(jié)果的多樣性和收斂性,提高算法求解多目標(biāo)問題的效率。
本節(jié)主要對比MOCWOA與5種多目標(biāo)優(yōu)化算法在ZDT標(biāo)準(zhǔn)測試集上的性能。設(shè)置MOCWOA的候選部分為狀況知識的前10%,即當(dāng)每個個體需要領(lǐng)導(dǎo)個體進(jìn)行進(jìn)化操作時,隨機(jī)從狀況知識的前10%個個體中挑選一個個體作為領(lǐng)導(dǎo)個體。狀況知識和規(guī)范知識的更新為每代進(jìn)化結(jié)束之后,而歷史知識的更新為每10代進(jìn)行一次更新。此外,MOCWOA的其他參數(shù),如控制算法進(jìn)行縮圈包圍或者搜尋獵物仍采用原WOA中參數(shù)|A|是否小于1來進(jìn)行判斷,參數(shù)A的計算公式已經(jīng)在式(11)中詳細(xì)給出,參數(shù)α的初始值為2。選取的5種多目標(biāo)優(yōu)化算法包括帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-Ⅱ)、基于分解的多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithm based on Decomposition,MOEA/D)、MOPSO、GPAWOA和多目標(biāo)海鷗算法(Multi-objective Optimization Seabird Algorithm,MOSOA)[33-34],其中:NSGA-Ⅱ是目前最流行的多目標(biāo)優(yōu)化算法;MOEA/D是一種基于分解的算法,該算法將多目標(biāo)問題轉(zhuǎn)換為一系列單目標(biāo)子問題處理;MOPSO是最流行的基于粒子的算法之一;GPAWOA是一種基于引導(dǎo)種群的多目標(biāo)鯨魚算法;MOSOA中加入了歸檔概念。算法種群選擇N=100,迭代次數(shù)500次。表1統(tǒng)計了幾種不同算法30次測試的平均值,最佳結(jié)果以粗體顯示。
表1 六種算法在ZDT標(biāo)準(zhǔn)測試集性能統(tǒng)計結(jié)果
從表1中可以看出,在雙目標(biāo)問題上,采用IGD指標(biāo)作為評價標(biāo)準(zhǔn)時,MOCWOA表現(xiàn)良好,在ZDT3、ZDT4以及ZDT6上MOCWOA取得了全部最優(yōu)值。值得注意的是,雖然在ZDT1上的IGD指標(biāo)測試結(jié)果,MOCWOA略遜于MOEA/D,但結(jié)果無明顯差異,而在ZDT2上的IGD指標(biāo)測試結(jié)果,MOCWOA劣于NSGAⅡ,但是與其余幾個算法的結(jié)果相比較,MOCWOA的結(jié)果仍然有較大優(yōu)勢。此外,雖然在ZDT1的IGD評價指標(biāo)上,MOCWOA略遜于MOEA/D,但是MOCWOA在ZDT1的HV指標(biāo)測試結(jié)果優(yōu)于MOEA/D,是幾個算法中最優(yōu)秀的。MOCWOA在ZDT標(biāo)準(zhǔn)測試集上的IGD指標(biāo)測試結(jié)果可以說明MOCWOA在解決雙目標(biāo)優(yōu)化問題的結(jié)果的收斂性好,同時,圖5~圖9顯示了幾種算法在ZDT標(biāo)準(zhǔn)測試集上的帕累托前沿(紅色),在與真實的帕累托前沿(黑色)相比較可以看出,MOCWOA得到的帕累托前沿基本能覆蓋真實的帕累托前沿,這也在一定程度上說明了算法的收斂性能。從表中的Sp測試結(jié)果來看,MOCWOA取得了在ZDT1和ZDT3上的最優(yōu)值,在ZDT2、ZDT4都排到了幾個算法中的第2位,且與最優(yōu)的相比較,沒有明顯差距,實驗結(jié)果可以說明MOCWOA在處理雙目標(biāo)優(yōu)化問題上,獲得的解具有良好的多樣性。此外,本文還引入了HV指標(biāo)。HV指標(biāo)可以同時評價算法得到的結(jié)果的收斂性和多樣性,可以在IGD和Sp指標(biāo)測試結(jié)果基礎(chǔ)上,補(bǔ)充說明算法的性能。從表1的測試結(jié)果統(tǒng)計數(shù)據(jù)可以看到,MOCWOA在ZDT1和ZDT3的HV指標(biāo)測試結(jié)果取得了最優(yōu)值,ZDT1具有凸帕累托前沿,ZDT3具有非連通的帕累托前沿,說明MOCWOA在解決具有這兩類帕累托前沿的雙目標(biāo)優(yōu)化問題時,相較其余幾種算法具有一定優(yōu)勢。而在其他幾個測試函數(shù)上的HV測試結(jié)果,幾個表現(xiàn)較優(yōu)秀的算法并沒有太大差距,MOCWOA分別在ZDT2、ZDT4和ZDT6的HV指標(biāo)測試結(jié)果上排到了幾種算法的第3,第2和第2名。從HV指標(biāo)的測試結(jié)果可以得出結(jié)論,MOCWOA在處理雙目標(biāo)優(yōu)化問題時,具有良好的綜合性能。此外,通過圖5~圖9可以更直觀地比較MOCWOA在ZDT測試集上的收斂性和多樣性,從圖中可以看出MOCWOA得到的帕累托前沿對真實前沿的擬合度和覆蓋程度都較好。實驗說明了MOCWOA在解決雙目標(biāo)優(yōu)化問題上,在幾個算法中具有一定的競爭力。
本節(jié)主要研究MOCWOA算法在實際RFCO上的應(yīng)用。位于贛江水系禾水支流瀘水河岸的社上水電站[36],是一座兼灌溉、發(fā)電、防洪、養(yǎng)殖等綜合效益為一體的大型水利樞紐工程,建成于1974年,水面面積11.7 km2,最大水位172 m,對應(yīng)庫容1.4094億立方米,死水位153 m,對應(yīng)庫容1.136億立方米,水庫的汛限水位為162 m,同時汛限水位也是汛期的起調(diào)水位,下游能承受的最大下泄流量為800 m3s-1。
國家于2000年發(fā)布了《水利水電工程等級劃分及洪水標(biāo)準(zhǔn)》[37],該標(biāo)準(zhǔn)適用于防洪、灌溉、發(fā)電和治澇等水利水電工程,該標(biāo)準(zhǔn)指出洪水頻率指某洪水特征值(一般指洪峰流量)出現(xiàn)的累計頻率,即在多年時期內(nèi),該特征值等于或超過某定量的可能次數(shù),并以百分比表示,例如20年一遇洪水即該特征值的洪水20年內(nèi)可能重現(xiàn)一次,累計頻率為5%。按照自然的規(guī)律,特大洪水出現(xiàn)的次數(shù)較少,一般洪水出現(xiàn)的次數(shù)較多。
小水電智能調(diào)度系統(tǒng)針對瀘水河岸的社上水電站長期實測資料及數(shù)理統(tǒng)計方法可以生成該水庫不同級別的洪水過程曲線,本文選取了20年一遇洪水和50年一遇洪水進(jìn)行測試,洪水過程圖如圖10所示,圖10左側(cè)為20年一遇洪水,洪水過程中存在2個波峰,圖10右側(cè)為50年一遇洪水洪水過程中僅一次波峰,持續(xù)時間均為60 h,取每個調(diào)度期為3 h,可分為20個調(diào)度期。
實驗選取了NAGA-Ⅱ以及幾種已經(jīng)應(yīng)用于RFCO的算法進(jìn)行對比:自適應(yīng)柯西變異多目標(biāo)差分進(jìn)化算法(Multi-objective Differential Evolution algorithm—Adaptive Cauchy Mutmion,MODE-ACM)、混合粒子群算法(hybrid Multi-objective PSO-EDA algorithm,MO-PSO-EDA)以及反向?qū)W習(xí)多目標(biāo)鯨魚算法(Multi-objective Whale Optimization Algorithm—Opposition-based Learning, MOWOA-OBL)。MODE-ACM是一種基于自適應(yīng)柯西變異的多目標(biāo)差分進(jìn)化算法,應(yīng)用于三峽水庫的多目標(biāo)防洪優(yōu)化調(diào)度,MO-PSO-EDA是一種改進(jìn)的多目標(biāo)粒子群算法,應(yīng)用于安康水庫的防洪調(diào)度,MOWOA-OBL是一種基于網(wǎng)格排序機(jī)制的多目標(biāo)鯨魚算法,是李偉琨等[38]提出的將鯨魚算法應(yīng)用于防洪調(diào)度優(yōu)化的先例。圖11~圖12為幾種算法對社上水庫防洪優(yōu)化調(diào)度的結(jié)果圖,表2為30次獨立實驗的Sp指標(biāo)的均值。Sp指標(biāo)主要體現(xiàn)了算法在實際的防洪調(diào)度問題中為決策者提供多樣性的解決方案的能力。此外,為了比較幾個算法的收斂性性能,本文將幾種算法求得的非支配解作為真實的前沿,來計算得到的結(jié)果的HV值,實驗參數(shù)設(shè)置與相關(guān)文獻(xiàn)相同,取種群大小為50,迭代500代,取30次實驗的最佳結(jié)果圖。
表2 社上水庫防洪調(diào)度優(yōu)化結(jié)果Sp值
由表2可以看出,當(dāng)遇到較小的洪水,如20年一遇的洪水時,幾種算法調(diào)度的結(jié)果,差距并不大,MOCOWOA算法在20年一遇洪水調(diào)度優(yōu)化中,獲得了和NSGA-Ⅱ相近的結(jié)果,而MO-PSO-EDA獲得了最優(yōu)的結(jié)果,但是在處理較大洪水,如50年一遇的洪水時,MOCWOA在幾種算法中處于領(lǐng)先地位,此時,MOCWOA可以為決策者提供更多合理的決策方案。表3顯示了各個算法在處理防洪調(diào)度問題時的綜合性能,MOCWOA在處理50年一遇洪水和20年一遇洪水時,均能取得最好或是接近最好的結(jié)果。
表3 社上水庫防洪調(diào)度優(yōu)化結(jié)果HV值
水庫防洪作業(yè)是一個諸多約束的復(fù)雜多目標(biāo)優(yōu)化問題。為了有效地解決該問題,本文提出一種新的多目標(biāo)優(yōu)化算法,即多目標(biāo)文化鯨魚算法(MOCWOA),該算法結(jié)合WOA和CA的優(yōu)勢。MOCWOA使用文化算法作為其框架,并在其種群空間采用多目標(biāo)鯨魚算法。WOA收斂速度快,但在處理多目標(biāo)局部優(yōu)化的問題時存在過早收斂問題。為了克服這一問題,提高算法的收斂速度,根據(jù)WOA和多目標(biāo)優(yōu)化的特征,在信度空間中定義了3種知識結(jié)構(gòu)。MOCWOA通過接受不斷進(jìn)化的種群空間中的優(yōu)秀個體來更新這3種知識結(jié)構(gòu),并使用這些知識結(jié)構(gòu)來提高其搜索效率。通過幾個典型的基準(zhǔn)問題的測試,MOCWOA證明了它在解決多目標(biāo)優(yōu)化問題方面的效率和魯棒性,特別是避免過早收斂的能力。然后將MOCWOA應(yīng)用于社上水庫多目標(biāo)防洪的案例研究,結(jié)果證明,對比其他一些針對RFCO問題的算法,MOCWOA可以生成大量分布均勻且分布范圍廣的非劣調(diào)度方供水庫調(diào)度決策者選擇,特別是在水庫遭遇較大洪水時??紤]到MOCWOA在多目標(biāo)問題的處理上的優(yōu)勢,可以嘗試將該算法延申到其他應(yīng)用上,如水庫群防洪調(diào)度問題。