基于混合進(jìn)化算法的海上風(fēng)電場電纜路由方法

蔡智超,李星存,吳慶華

(1. 國網(wǎng)湖北省電力有限公司荊門供電公司,湖北 荊門 448000;2. 華中科技大學(xué)管理學(xué)院,湖北 武漢 430074)

1 引言

相較于煤炭、石油等化石能源,可再生能源由于其清潔、可循環(huán)使用等優(yōu)點得到了廣泛關(guān)注。在可再生能源中,風(fēng)力發(fā)電在緩解大量電力消耗引發(fā)的環(huán)境問題方面發(fā)揮著重要作用,是發(fā)展最快的可再生能源技術(shù)之一[1]。由于海上風(fēng)速較快且較為穩(wěn)定,海上風(fēng)電場相較于陸地風(fēng)電場更為高效,是更合適的風(fēng)電場部署地點。現(xiàn)有研究表明,海上風(fēng)電場的電力設(shè)施基礎(chǔ)設(shè)施成本占海上風(fēng)電場部署總成本的15%至30%[2]。本文重點研究海上風(fēng)電場中電力基礎(chǔ)設(shè)施的優(yōu)化問題,即海上風(fēng)電場電纜路由問題(offshore wind farm cable routing problem, OWFCRP)。

在海上風(fēng)電場中,每個風(fēng)力渦輪機利用風(fēng)能進(jìn)行發(fā)電,并由海底電纜將所產(chǎn)生的電力能源進(jìn)行傳輸,所有的產(chǎn)生的電能最終匯集到一起傳輸至離岸變電站中,再由離岸變電站配備的變壓器升壓后以較少電能損失傳輸至陸地變電站中并入電網(wǎng),以供后續(xù)能源調(diào)度。OWFCRP問題在于如何高效地利用海底電纜來將風(fēng)力渦輪機的能源傳輸至離岸變電站。具體而言,OWFCRP問題主要研究在已知風(fēng)力渦輪機的位置后,如何利用海底電纜連接風(fēng)力渦輪機和離岸變電站來完成海上風(fēng)電場的能源收集,并盡可能減小海底電纜花費的總成本。

文獻(xiàn)[3]證明了OWFCRP是一個理論上難以解決的NP-hard優(yōu)化問題,即便使用先進(jìn)的混合整數(shù)線性規(guī)劃等精確算法,難以證明其求解的最優(yōu)性。并且由于OWFCRP中的交叉約束的規(guī)模為海上風(fēng)電場中風(fēng)力渦輪機數(shù)量的四次方,因而導(dǎo)致精確性算法求解需要花費大量時間且在部分大規(guī)模海上風(fēng)電場算例中難以求得可行解。文獻(xiàn)[4]描述、實現(xiàn)和測試了模擬退火、禁忌搜索、變鄰域搜索、蟻群算法和遺傳算法,共五種不同的元啟發(fā)式算法,并提出了一種稱為Sweep的啟發(fā)式算法,它通常在很短的計算時間內(nèi)找到一個高質(zhì)量的解決方案。

目前大多數(shù)研究集中于海上風(fēng)電場中的離岸變電站或風(fēng)力渦輪機布局等微布局研究[5-8],而對OWFCRP等問題的關(guān)注較少。由于OWFCRP問題的優(yōu)質(zhì)解可為海上風(fēng)電場的部署節(jié)省千萬歐元的部署成本,因此解決該問題對海上風(fēng)電場設(shè)計具有重要意義,并仍需進(jìn)一步研究。過往研究[4]所設(shè)計的Sweep啟發(fā)式算法中的路徑優(yōu)化算法是基于貪心的Prim算法,由于Prim算法只針對OWFCRP問題中電纜路徑長度來對電纜成本進(jìn)行,忽略了電流對電纜成本的影響?；旌线M(jìn)化算法[9-11]也被稱為文化基因算法,結(jié)合了基于種群的全局搜索和基于個體的局部搜索的優(yōu)點,是一種高效的元啟發(fā)式算法[12-16]。本文將OWFCRP問題分解為了分組和組內(nèi)路徑優(yōu)化兩個子問題,初始化算法和分組交叉算子用于搜索不同分組。本文提出了基于路由表的禁忌搜索算法用于解決組內(nèi)路徑優(yōu)化問題。結(jié)合上述算法,本文提出了一種混合進(jìn)化算法來解決OWFCRP問題,并與其它算法進(jìn)行了對比實驗,對比實驗所使用的實例集基于五個位于英國和丹麥的真實海上風(fēng)電場數(shù)據(jù)。實驗結(jié)果顯示,所提出的混合進(jìn)化算法表現(xiàn)了良好的應(yīng)用前景。

2 海上風(fēng)電場電纜路由方法

圖1展示了位于英國東部的真實的Thanet海上風(fēng)電場布局結(jié)構(gòu),是本文實驗所使用的算例之一。圖1中的紅圈表示風(fēng)力渦輪機,其功能是將風(fēng)能轉(zhuǎn)換為電能并通過電纜傳輸出去,Thanet海上風(fēng)電站包含了一百個渦輪機。中心的黑色五邊形為離岸變電站,作為風(fēng)力渦輪機電能的收集點,OWFCRP問題中每個海上風(fēng)電場有且僅有一個離岸變電站。風(fēng)力渦輪機之間、風(fēng)力渦輪機和離岸變電站之間的橙色連線表示海底電纜,用于將所有風(fēng)力渦輪機的電能進(jìn)行傳輸,并最終傳遞至作為收集點的離岸變電站。簡潔起見,后續(xù)用渦輪機、變電站、電纜指代風(fēng)力渦輪機、離岸變電站、海底電纜。

圖1 Thanet海上風(fēng)電場示例

OWFCRP問題可進(jìn)一步歸結(jié)如下,假設(shè)海上風(fēng)電場中的渦輪機和變電站的位置確定,OWFCRP任務(wù)是如何選擇渦輪機之間以及渦輪機和變電站之間的連接方式來將渦輪機生成的電能匯聚至變電站。由于風(fēng)電場中渦輪機通常是同構(gòu)同功率的,因此單個渦輪機生成電能均被設(shè)為1。有多類電纜可供選擇,每種電纜有著不同的單位成本和電力容量,電力容量越高則單位成本越高,每個渦輪機的電能為其子樹節(jié)點個數(shù)與其自身產(chǎn)生的電能之和,渦輪機所用電纜的電力容量不能小于其匯集的電能,例如圖1中的渦輪機A12所匯聚的電能為4,因此渦輪機A12和A11間的電纜電力容量不能小于4。OWFCRP問題的優(yōu)化目標(biāo)是盡可能減少電纜的總成本。每個渦輪機只允許一根電纜來傳輸其匯聚的電能,并且在連接渦輪機時,電纜之間不允許出現(xiàn)交叉,此外,變電站最多允許C根電纜直接接入,例如圖1中的C設(shè)為10,這意味著與中心處的變電站直接接入的電纜數(shù)量不能超過10。OWFCRP問題對應(yīng)的混合整數(shù)線性規(guī)劃模型可見文獻(xiàn)[3]。

2.1 混合進(jìn)化算法的流程

本文提出的混合進(jìn)化算法的流程如圖2所示,首先,通過基于角度和分組的種群初始化算法來生成初始種群。基于路由表的局部搜索算法來對初始種群的每個個體中的分組進(jìn)行電纜路徑優(yōu)化。在未達(dá)最大交叉次數(shù)的條件下,新個體將由分組交叉算法和局部搜索算法生成,并更新種群。最后,在達(dá)到最大交叉次數(shù)時,輸出種群中的最優(yōu)解。

圖2 混合進(jìn)化算法的流程圖

2.2 混合進(jìn)化算法的流程

求解OWFCRP問題時,一般采用電纜總成本作為目標(biāo)函數(shù)來度量解的質(zhì)量,公式如下:

(1)

2.3 種群初始化

在使用CPLEX求解器求解OWFCRP問題時,由于交叉約束和變電站電纜接入數(shù)量約束的存在,求解器難以獲得可行解。在嘗試使用一般的貪婪初始化算法生成的初始解會產(chǎn)生較多的交叉,此類交叉是由于分組質(zhì)量低下導(dǎo)致的。在此情況下,算法將在不可行解中進(jìn)行大量無意義的搜索。為了盡快進(jìn)入可行解,在搜索空間進(jìn)行有意義的搜索,根據(jù)Sweep算法中基于角度的分組策略進(jìn)行種群初始化。例如,在圖1中,E08-E17共十個渦輪機,這十個渦輪機以及渦輪機之間的電纜路由構(gòu)成一個分組。本文對組進(jìn)行了如下的精確性定義。

定義1:在渦輪機的分組過程中,單個組由風(fēng)電場中渦輪機的子集以及渦輪機子集中渦輪機之間的電纜路由共兩部分組成。所有組的集合即OWFCRP問題的解。分組需滿足如下定義:

a. 一個渦輪機只屬于一個組,不能在多個組之間共享。

b. 每個組采用樹結(jié)構(gòu),其中作為根節(jié)點的渦輪機將直接與變電站相連。單個組中的渦輪機總數(shù)與單個渦輪機所生產(chǎn)的電能的乘積不能超過電纜最大容量。

c. 組的個數(shù)不能超過變電站最大接入數(shù)C。

基于角度的分組方法是解決分組質(zhì)量低下的一種有效途徑。基于角度的分組方法首先隨機選定一個渦輪機作為起始點,接著對所有渦輪機進(jìn)行遍歷,按照順時針或逆時針計算起始點-變電站與變電站-渦輪機所形成的夾角,該夾角在0到 π之間,并存放在角度數(shù)組中。角度數(shù)組的數(shù)組下標(biāo)為渦輪機編號,對應(yīng)的數(shù)組值為起始點到變電站的線段與變電站到渦輪機的線段所形成的夾角。為了將角度相近的一些渦輪機分入一組中,每次將生成一個在電纜最大容量、渦輪機數(shù)量除以變電站最大電纜接入數(shù)之間的隨機值z,接著從角度數(shù)組中選取角度最小的z個渦輪機作為一組,并將這些渦輪機編號及數(shù)組值從數(shù)組中刪除,循環(huán)此過程直至所有渦輪機完成分組為止。初始化的電纜路由以如下方法生成,每個組中最靠近變電站的渦輪機作為組的根節(jié)點,根節(jié)點的電纜與變電站相連,其余渦輪機直接與根節(jié)點相連。經(jīng)過基于角度的分組后,OWFCRP問題被分解為組內(nèi)的電纜路由優(yōu)化問題。

基于角度的初始化方法的優(yōu)點在于將角度相近的渦輪機分至同組可以有效減少組內(nèi)低效的電纜橫向位移,使得電纜更好的將渦輪機所收集電力以良好的角度向變電站方向傳遞,此外,這種初始化方法生成的解是無交叉的可行解。

2.4 局部搜索算子

經(jīng)過種群初始化后,令種群規(guī)模為P,則種群中包含P個個體,每個個體為OWFCRP問題的解,由于組內(nèi)電纜路由優(yōu)化的復(fù)雜性,在種群初始化過程中,組內(nèi)非根節(jié)點渦輪機的電纜簡單地連接至根節(jié)點渦輪機處,因此各個組內(nèi)的電纜仍待進(jìn)一步優(yōu)化。本文提出了一種基于路由表的禁忌搜索算法來對單個組內(nèi)的電纜路由進(jìn)行優(yōu)化以減少電纜成本。

算法1:基于路由表的禁忌搜索算法

輸入:種群中的個體S,搜索次數(shù)maxIter

輸出:搜索到的最優(yōu)個體S*及其對應(yīng)目標(biāo)函數(shù)值f

步驟1:遍歷個體S的各個組,對每個組按照如下步驟進(jìn)行組內(nèi)電纜路由優(yōu)化。

步驟2:用z表示當(dāng)前組內(nèi)的渦輪機數(shù)量。生成z×z的禁忌表數(shù)組和z×z路由表數(shù)組,并初始化,并將初始組G保存至搜索過程中的最優(yōu)組G*。

步驟3:根據(jù)禁忌表從路由表選取最優(yōu)移動,根據(jù)最優(yōu)移動修改組內(nèi)的電纜路由和電纜總成本,并將原電纜路由禁忌。若新組G的組內(nèi)電纜成本大于等于G*的組內(nèi)電纜成本,則將最優(yōu)組G*更新為G,并對重新初始化路由表。重復(fù)此步驟3直至本組搜索次數(shù)達(dá)到最大搜索次數(shù)maxIter時,當(dāng)前組的優(yōu)化結(jié)束,保存將G*作為本組的最優(yōu)解,繼續(xù)進(jìn)入步驟2、步驟3以搜索并優(yōu)化下一個組的電纜路由。

步驟4:當(dāng)所有分組搜索結(jié)束,算法結(jié)束,輸出由優(yōu)化后的組所構(gòu)成的新解S*,以及各組的組內(nèi)電纜成本之和加上各組的根節(jié)點到變電站的電纜成本之和。

算法1中介紹了基于路由表的禁忌搜索算法的執(zhí)行步驟。在種群初始化后,算法1用于對單個個體所包含的組依次搜索最優(yōu)的組內(nèi)電纜路由。組內(nèi)的電纜路由搜索過程主要依據(jù)禁忌表和路由表來完成,其中禁忌表主要用于避免重復(fù)搜索以提高搜索效率,路由表則作為電纜路由選擇的依據(jù)。

步驟2中,禁忌表中的第i行第j列的值tabu[i][j]表示當(dāng)前渦輪機i為起點、j為終點的電纜連接在后續(xù)的指定輪次中被禁忌。路由表中的route[i][j]表示當(dāng)前渦輪機i為起點電纜連接至渦輪機j時組內(nèi)電纜總成本。禁忌初始化過程中,為了防止自連,第i行中的第i列的禁忌步長均設(shè)為MAX,即永久禁忌。由于根節(jié)點的電纜直接連入變電站,不應(yīng)與組內(nèi)節(jié)點相連,因此禁忌表中根節(jié)點對應(yīng)行的禁忌步長均為MAX。為了防止渦輪機i為的起點的電纜接入其子樹中而違背無環(huán)約束,路由表初始化過程中,第i行中,如果渦輪機j在渦輪機i的子樹中,則渦輪機i連接route[i][j]被設(shè)為MAX。路由表的其余值將通過一個快速增量方法實現(xiàn),如果當(dāng)前渦輪機i的電纜是接入渦輪機j中的,則route[i][j]為當(dāng)前組內(nèi)電纜總成本,如果要計算渦輪機i接入渦輪機k對應(yīng)的新的組內(nèi)電纜總成本route[i][k],其中k不等于j,即令原本渦輪機i為起點的電纜從原本的連接至渦輪機j變?yōu)檫B接至渦輪機k。這個過程可由取消i和j處的電纜、連接i和k處的電纜兩個步驟完成。取消i和j處的電纜造成的組內(nèi)電纜成本降低值reduce如下,首先是渦輪機i到渦輪機j處的電纜取消導(dǎo)致的成本降低,其次,渦輪機j不再接收渦輪機i及其子樹的電能而導(dǎo)致渦輪機j到變電站處的所有電纜的電流減小,因此渦輪機j到根節(jié)點處的多個電纜的類型將會改變進(jìn)而導(dǎo)致電纜成本的減少。同理,連接i和k處的電纜成本增加值increase為在渦輪機i與渦輪機k處新建電纜成本加上渦輪機k到根節(jié)點處的電流升高引起的電流類型改變而增加的電纜成本之后。路由表中每行的其余z-1個鄰域?qū)?yīng)的組內(nèi)電纜成本可由上述快速增量方法來獲取。上述快速增量的公式如下:

route[i][k]=route[i][j]-reduce+increase

(2)

式(2)中route[i][j]表示現(xiàn)電纜路由方案中渦輪機i處的電纜連入渦輪機j時的組內(nèi)電纜總成本,reduce為斷開渦輪機i現(xiàn)有電纜導(dǎo)致的成本減少值,increase為將渦輪機i的電纜連入渦輪機k時導(dǎo)致的電纜成本增加值。

步驟3中選取最優(yōu)移動時,未被禁忌且與當(dāng)前組內(nèi)電纜路由不同的移動作為備選解,備選解中擁有最小路由表值的解通常為本次搜索的最優(yōu)移動,如果禁忌解中的最優(yōu)移動的組內(nèi)電纜成本不但優(yōu)于非禁忌解的最優(yōu)移動,同時也優(yōu)于最優(yōu)組G*,則進(jìn)行特赦來對該禁忌解解禁并作為最優(yōu)移動。選取了最優(yōu)移動后,路由表中最優(yōu)移動route[i][k]對應(yīng)的行i的原始連接tabu[i][j]值將增加禁忌長度L以增加局部搜索效率。

步驟4新解由優(yōu)化后的組構(gòu)成,并得到新解對應(yīng)的目標(biāo)函數(shù)。在種群初始化后,將對種群中的每個個體執(zhí)行算法1來優(yōu)化個體的電纜路由質(zhì)量。

2.5 全局搜索算子

在混合進(jìn)化算法中,全局搜索算子通常為交叉算子,基于OWFCRP問題的特性,本文提出了一種分組交叉算子以進(jìn)行全局搜索,其步驟如下:

算法1 基于分組的交叉算子

輸入:完整種群

輸出:子代個體Snew及其對應(yīng)的目標(biāo)函數(shù)值f

步驟1:從種群中隨機選取兩個個體S0、S1作為父母。

步驟2:將S0、S1以組的形式表示,并通過組內(nèi)電纜平均成本度量組內(nèi)電纜路由質(zhì)量。組內(nèi)電纜平均成本favg計算公式如下:

(3)

式(3)中等號右側(cè)的分子項fg為組內(nèi)電纜總成本,分母項z-1為組內(nèi)電纜數(shù)量(不包括根節(jié)點的電纜)。交叉算子每次將從S0的分組中基于組內(nèi)電纜平均成本來選取最優(yōu)組Gbest,并將Gbest所包含的渦輪機從S1中刪除來防止單個渦輪被分至多組,接著從S0中刪除最優(yōu)組Gbest并將該最優(yōu)組添加到新個體Snew中。同理,再從S1中選取最優(yōu)組,并從將最優(yōu)組包含的渦輪機從S0中刪除。

步驟3:循環(huán)步驟2直至所有渦輪機均處于Snew的分組中,并計算新個體Snew的目標(biāo)函數(shù)值。

在生成子代個體Snew后,局部搜索算法將用于改進(jìn)子代個體的電纜路由質(zhì)量。

2.6 種群更新策略

在得到通過局部搜索算法得到改進(jìn)后的新個體后,新個體對應(yīng)的電纜路由方案將被轉(zhuǎn)換為一維數(shù)組,其中下標(biāo)表示渦輪機i為該電纜的起始點,下標(biāo)對應(yīng)的數(shù)組值表示渦輪機i的電纜的終點,如果新個體的一維數(shù)組與種群已有的個體完全一致,則丟棄掉新個體以防止個體重復(fù),否則將新個體加入到種群中,替換掉種群內(nèi)目標(biāo)函數(shù)值最低的個體。

3 實驗

本文使用C++在Clion開發(fā)環(huán)境中實現(xiàn)了所提出的混合進(jìn)化算法,在CPU為Intel i5 8400、顯卡為GTX 1060、內(nèi)存為8G的PC上進(jìn)行了對比實驗,對比組為文獻(xiàn)[4]提出的Sweep算法。

3.1 實驗算例

本文收集了五個海上風(fēng)電場的真實數(shù)據(jù)作為實驗算例。這五個海上風(fēng)電場的名稱分別為HornsRev 1、KentishFlats、Ormonde、DanTysk、Thanet,風(fēng)電場中的渦輪機數(shù)分別為80、30、30、80、100個,變電站最大約束C分別為10、無限制、4、10、10,提供的電纜類型數(shù)量分別為3、5、2、4、2種。

HornsRev 1風(fēng)電場建于2022年,位于丹麥北海,距海岸約十五公里,發(fā)電量為160MW,是世界上最古老的大型風(fēng)電場之一。KentishFlats風(fēng)電場位于英格蘭東南部,產(chǎn)電量為140MW,屬于近岸風(fēng)電場,因此其能源直接傳入陸上電網(wǎng)中,由于風(fēng)電場能源最終通過一根電纜傳入陸地,其電纜的匯聚地點作為該風(fēng)電場的變電站,同時變電站的最大電纜接入約束不做限制。Ormonde風(fēng)電場位于英國愛爾蘭海附近,風(fēng)電場總?cè)萘繛?50MW。DanTysk風(fēng)電場位于德國與丹麥的交界處,西爾特島的西部,總?cè)萘繛?88MW,能夠為40萬戶家庭提供綠色能源。

根據(jù)以上五個風(fēng)電場布局,以及不同的可選電纜集合的搭配最終生成了29個基準(zhǔn)算例用于評估算法性能,其中算例01到06基于HornsRev 1風(fēng)電場,算例07-15基于KentishFlats風(fēng)電場,算例16-19基于Ormonde風(fēng)電場,算例20-25基于DanTysk風(fēng)電場,算例26-29基于Thanet風(fēng)電場。

每個算例包含了變電站電纜最大接入數(shù)C、變電站和渦輪機的二維坐標(biāo)、可供選擇的電纜類型以及對應(yīng)的電纜每米價格和電纜容量。

3.2 算法參數(shù)

所提出的混合進(jìn)化算法的實驗參數(shù)如下:種群規(guī)模P為10,禁忌長度L為100,最大交叉次數(shù)為500,禁忌搜索次數(shù)maxIter為3000。

3.3 實驗結(jié)果

所提出的混合進(jìn)化算法基于上述算例中進(jìn)行性能測試,測試過程默認(rèn)采用上述的算法參數(shù)設(shè)置。電纜成本作為主要的性能指標(biāo)來評估混合進(jìn)化算法在各算例中表現(xiàn),具體的性能指標(biāo)如下表所示。

表1中第一列為算例編號,第二、三列分別為所提出的混合進(jìn)化算法、Sweep算法在算例中的求得的最優(yōu)目標(biāo)函數(shù)值,即最優(yōu)電纜成本(單位為歐元),表中目標(biāo)函數(shù)值為算法運行20次的平均電纜成本值。

表1 混合進(jìn)化算法和Sweep算法在算例集中的電纜成本

在基于HornsRev 1風(fēng)電場的算例01到06中,混合進(jìn)化算法相較Sweep算法電纜成本平均降低了2.04%。在基于KentishFlats風(fēng)電場的算例07到15中,混合進(jìn)化算法相較Sweep算法電纜成本平均降低了4.18%。在基于Ormonde風(fēng)電場的算例16-19中,混合進(jìn)化算法相比Sweep算法降低了2.68%的電纜成本。對基于DanTysk風(fēng)電場的算例20-25,混合進(jìn)化算法降低了1.07%。Thanet風(fēng)電場生成的算例26-29上,相比于Sweep算法,混合進(jìn)化算法的電纜成本減少了3.33%。在算例集上,混合進(jìn)化算法的電纜成本相比Sweep算法平均減少了2.66%,尤其是在處理部分算例中相對復(fù)雜的組內(nèi)電纜路由時,混合進(jìn)化算法有著顯著的優(yōu)勢。在CPLEX無可行解的算例02、06、20-22、24-25、27-29,混合進(jìn)化算法能夠求得優(yōu)于Sweep算法的可行解。

在總體上,混合進(jìn)化算法的解的電纜成本在29個算例低于Sweep算法,是一種更優(yōu)的OWFCRP問題的解決方案。

4 結(jié)論

OWFCRP問題是海上風(fēng)電場設(shè)計與部署過程中的關(guān)鍵問題之一,本文提出了一種混合進(jìn)化算法來解決OWFCRP問題,該混合進(jìn)化算法包含局部搜索和全局搜索兩個關(guān)鍵算子,其中局部搜索采用一種基于路由表的禁忌搜索算法完成電纜路由優(yōu)化,路由表引導(dǎo)鄰域搜索,并通過禁忌搜索加快搜索效率。全局搜索采用基于分組的交叉算子來搜索較優(yōu)分組,通過平均電纜成本來度量組的質(zhì)量,并將較優(yōu)組遺傳給子代個體。基于上述全局搜索算子和局部搜索算子的混合進(jìn)化算法被用于解決OWFCRP問題。

最終,本文根據(jù)歐洲真實海上風(fēng)電場數(shù)據(jù)構(gòu)成的算例集對所提出的算法進(jìn)行驗證,實驗結(jié)果表明所提出的混合進(jìn)化算法優(yōu)于已有文獻(xiàn)中的Sweep算法,相比Sweep算法在29個算例中平均降低了2.66%的電纜路由成本,是一種更優(yōu)、更高效的海上風(fēng)電場電纜路由方法。