基于混合进化算法的海上风电场电缆路由方法

蔡智超,李星存,吴庆华

(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%的电缆路由成本,是一种更优、更高效的海上风电场电缆路由方法。