基于混合進化算法的海上風電場電纜路由方法

蔡智超,李星存,吳慶華

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

1 引言

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

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

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

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

2 海上風電場電纜路由方法

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

圖1 Thanet海上風電場示例

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

2.1 混合進化算法的流程

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

圖2 混合進化算法的流程圖

2.2 混合進化算法的流程

求解OWFCRP問題時,一般采用電纜總成本作為目標函數來度量解的質量,公式如下:

(1)

2.3 種群初始化

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

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

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

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

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

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

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

2.4 局部搜索算子

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

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

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

輸出:搜索到的最優個體S*及其對應目標函數值f

步驟1:遍歷個體S的各個組,對每個組按照如下步驟進行組內電纜路由優化。

步驟2:用z表示當前組內的渦輪機數量。生成z×z的禁忌表數組和z×z路由表數組,并初始化,并將初始組G保存至搜索過程中的最優組G*。

步驟3:根據禁忌表從路由表選取最優移動,根據最優移動修改組內的電纜路由和電纜總成本,并將原電纜路由禁忌。若新組G的組內電纜成本大于等于G*的組內電纜成本,則將最優組G*更新為G,并對重新初始化路由表。重復此步驟3直至本組搜索次數達到最大搜索次數maxIter時,當前組的優化結束,保存將G*作為本組的最優解,繼續進入步驟2、步驟3以搜索并優化下一個組的電纜路由。

步驟4:當所有分組搜索結束,算法結束,輸出由優化后的組所構成的新解S*,以及各組的組內電纜成本之和加上各組的根節點到變電站的電纜成本之和。

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

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

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

(2)

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

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

步驟4新解由優化后的組構成,并得到新解對應的目標函數。在種群初始化后,將對種群中的每個個體執行算法1來優化個體的電纜路由質量。

2.5 全局搜索算子

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

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

輸入:完整種群

輸出:子代個體Snew及其對應的目標函數值f

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

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

(3)

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

步驟3:循環步驟2直至所有渦輪機均處于Snew的分組中,并計算新個體Snew的目標函數值。

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

2.6 種群更新策略

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

3 實驗

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

3.1 實驗算例

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

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

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

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

3.2 算法參數

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

3.3 實驗結果

所提出的混合進化算法基于上述算例中進行性能測試,測試過程默認采用上述的算法參數設置。電纜成本作為主要的性能指標來評估混合進化算法在各算例中表現,具體的性能指標如下表所示。

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

表1 混合進化算法和Sweep算法在算例集中的電纜成本

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

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

4 結論

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

最終,本文根據歐洲真實海上風電場數據構成的算例集對所提出的算法進行驗證,實驗結果表明所提出的混合進化算法優于已有文獻中的Sweep算法,相比Sweep算法在29個算例中平均降低了2.66%的電纜路由成本,是一種更優、更高效的海上風電場電纜路由方法。