改进禁忌搜索算法的线路规划算法优化设计

2021-11-19金超未帕尔哈提克衣木罗瑞雪

电气工程学报 2021年3期

李杰金超未帕尔哈提·克衣木罗瑞雪

(国网新疆电力有限公司信息通信公司乌鲁木齐 830000)

1 引言①

传统的输电线路规划是根据地理图纸规划大致的方案，然后进行实地考察来确定最终的方案。这种方法主要依靠设计人员的经验，但是由于地图数据需要人为进行更新，造成了数据更新不及时，会导致设计人员判断错误，同时输电线路的影响因素很多，导致工作强度大、时间久，从而影响到输电线路规划的进度。随着国家大力推进智能电网设计，地理信息系统(Geographic information system，GIS)和计算机系统被广泛地应用到电力系统中，给输电线路规划提供了新的思路，文献[1]中对10 kV 配网的输电线路规划需要注意的问题进行了说明，但是没有解决人工规划效率慢的问题。文献[2]中提出一种优化算法，根据设置禁忌条件来求解最优路径，但是由于线路规划数据规模大，算法耗时太长。

基于以上内容，对输电线路的路径选择算法进行优化，采用禁忌搜索算法建立最优线路求解模型，根据规划区内的地理信息因素对规划区进行单元格划分和成本预算，得到一个成本最优、建设难度最小的线路。并针对搜索时间过长和拐点过多等缺陷，提出跨越式邻域和双向搜索方法来缩短算法的计算次数，采用拐点处理机制来减少拐点数量。

2 输电线路优化

2.1 输电线路概念

发电厂发出的电传输到用户需要建设大规模的线路，这部分线路都可以称作输电线路[3]。发电厂的电经过变压站升压输送到高压输电网，再经过降压和配电才能到达用户家里进行使用，所以输电线路可以分为配电线路和送电线路。通常，配电线路电压小于10 kV，其中低压配电线路电压为1 kV 以下，高压配电线路电压为1～10 kV；送电线路电压为35 kV 及以上，其中高压送电线路电压为35～220 kV，超高压送电线路电压为330～500 kV[4]。

2.2 输电线路设计需要注意的因素

输电线路在设计规划时要注意地理位置因素，主要有以下几个方面[5]。

(1) 避让区域。输电线路在设计时要注意避开军事管理区、自然保护区以及一些易燃易爆的厂房和仓库。

(2) 自然环境。尽量选择空旷的平地进行建设，注意自然生态环境，减少树木的砍伐。

(3) 由于高压线路会产生电磁感应，对人和动物会造成一定的伤害，所以在建造过程中要远离建筑物和人群。

(4) 设计过程中要尽量避开坡度较大的地方，选择坡度小于30°的地方建造杆塔，同时在设计时对原有线路进行改造和升级，不仅可以减少建设时间，还能节约一定成本。

2.3 输电线路优化的目标

输电线路优化的目标是在满足用户用电需求、符合行业标准、保证供电安全稳定性的前提下，在输电线路的起点和终点之间规划出一条成本最低的线路，同时要考虑建设的复杂程度、行业的发展，还要注意保护好自然环境，避免大面积破坏和重建[6]。

3 线路规划算法模型

3.1 划分单元格

输电线路规划中单元格可以划分为两大类，不可跨越地区(A)和可跨越地区(B)，对于可跨越地区，要综合考虑该地区的各种因素来确定成本，采用模糊层次分析法建立分析模型来确定单元格的成本[7]。

根据地理信息因素对成本的影响，可以引入评分系统对影响可跨越地区成本的因素进行评分，根据以往的经验评分结果如表1 所示。

表1 因素评分

对地理信息层次进行划分，如图1 所示。

图1 地理信息层次

主要划分为三层，第一层为目标层代表单元格的成本值，第二层为准则层，由导线成本、基础设施成本、杆塔成本和施工成本组成，成本根据天气和地理因素的变化会有所不同。第三层为第二准层层，影响着准则层，并且影响程度不同[8]。

采用评分矩阵来计算单元格的成本值[9]

式中，x ij为n×m矩阵，表示第i个单元格的第j个地理影响因素的评分，矩阵的大小根据单元格的和影响因素数量来决定，m为地理影响因素数量，n为单元格的数量。

由于评分没有标准，无法进行有意义的评分，采用比较矩阵来解决问题[10]，即两个地理影响因素相互对比，将地理因素两两对比，可得式中，aij为n×n矩阵，表示第i个地理影响因素对j个地理影响因素的影响程度，采用表1 的数据来表示比较结果。

对矩阵A的行元素求和，得到模糊一致矩阵[11]

采用GIS 和RS 技术来进行地理信息的采集和处理[14]，分为A、B 两类单元格。通过上述计算能够获得单元格建设的成本值，再加上单元格的位置信息，得到如表2 所示的单元格属性表。

表2 单元格属性

3.2 线路规划模型

采用禁忌搜索算法来建立输电线路规划模型，禁忌搜索线路优化算法中最常用的一种人工智能算法，能够模仿人类的记忆功能，被广泛运用到线路规划中[15]。算法流程如下所示。

(1) 初始化设置。禁忌表T设置为空，设定算法的参数和初始解n，这里采用随机产生的方式[16]。

(2) 判断初始解。因为初始解是随机产生的，具有不确定性，所以要对其进行判断，满足条件则输出结果，不满足则进行下一步。

(3) 确定候选解。由于初始解不满足设定的条件，所以要进行计算来确定候选结果，即计算当前解的邻域范围内满足设定要求的解的集合。

(4) 判断候选解。根据设定的特赦条件来判断候选解是否满足对应的条件，若满足，则用候选解集合里的最优解来代替当前解作为新的当前解，并替换禁忌表内容。然后转至第二步，若不满足，则进行下一步。

(5) 选择候选解。即选择候选解集中的最优解来替换当前解，并替换禁忌表内容。

(6) 继续执行第(2)步。

4 线路规划算法改进

根据划分的单元格，采用上述模型能够从确定好的起点和终点得到一条满足条件的最优输电线路。但是由于输电线路的影响因素过多，算法的时间会大幅度增加，就失去了算法效率高的特点。因此，需要对上述得到模型进行改进和完善，主要有以下几种方式[17]。

(1) 跨域式邻域。在上述算法中，在利用邻域函数求解邻域范围内的解的集合时，选择的是以当前位置为中心的8 个单元格[18]，如图2 所示。

图2 改进前的邻域选择

这种方式一般用来处理少量数据，随着数据规模的变大，这种方式的处理速度也会变慢，因此引入跨越式邻域来解决处理速度慢的问题，改进后的邻域选择如图3 所示。

图3 改进后的邻域选择

改进之后的邻域选择机制能够缩短数据的计算次数，通过图3 中阴影部分的面积，可以看到，改进后的邻域选择范围更宽，使得需要计算的区域增加，相应的计算量也应增加，采用固定的跨越式邻域可能会出现没有最优解的情况，这时可以考虑缩小或者增大跨越距离[19]。

(2) 双向搜索。为了解决算法运算时间多长问题，采用起点和终点同时开始搜索的方式来缩短算法的运算时间，这种方式可能会出现无法相遇的情况，为此引入方向引导因子[20-21]，如图4 所示。

图4 方向引导因子

其中，线段1 为当前位置与终点的连线，线段2 为当前位置与相邻单元格A 的连线，线段3 为当前位置与相邻单元格B 的连线。θ1表示线段1 和线段2 的夹角，θ2表示线段1 和线段3 的夹角。

令方向控制因子为f，则有

如果方向因子f越大，则表示θ1，θ2越小，即移动的方向越接近终点，当禁忌表在搜索后逐渐增加时，会出现搜索范围集中在目标范围同一侧的情况，因此，引入方向因子限制系数η， ∈(0,1)η，则有

式中，m为迭代次数。

(3) 拐角处理。在输电线路建设中，如果拐点过多，就会建设大量杆塔和基础设施，造成成本的大幅增长。在搜索时，会出现如图5 所示的情况。

图5 中阴影部分为不可跨越区域，假设从A点到E点需要规划输电线路，经过算法的搜索规划出了A→B→C→D→E方案，但是这样拐点过多会造成成本的大幅度增加，为此引入拐点处理机制，比较AB和BC的斜率。如果斜率不同，表示三点未在同一直线上，此时可以判断AC是否处于不可跨越区域，否则比较AC和AB+BC的成本选择较小的成本线路。经过改进和完善后的算法最终流程图如图6 所示。