基于优化蚁群算法的输电线路径规划研究

苗作华，王梦婷，汤 阳，王 彪，王成功

（1.武汉科技大学资源与环境工程学院，湖北武汉 430081；2.冶金矿产资源高效利用与造块湖北省重点实验室，湖北武汉 430081；3.中钢集团武汉安全环保研究院有限公司，湖北武汉 430081；4.北京道亨软件股份有限公司，北京 100012）

0 引言

输电线路径规划是高压输电线路设计中的一个重要过程[1]，其最终目标是在线路起止点间选出一条安全可靠、环境友好、经济合理的综合最优线路[2]。传统的输电线路径规划主要是根据经验以及现有的线路在图纸上选取出几条合适的线路，再进行实地考察，进一步调整线路以便确定最终线路。由于输电线路的地形地貌较为复杂，规划图纸中无法展现精确、实时的地貌特征，使得整个规划设计过程存在工作量大，准确率低等问题[3-4]。因此，借助现代科学技术完成线路规划工作[5-6]，使输电线路径规划更加智能化，是输电线路径规划发展的必然趋势。

由于涉及多种不同量纲的影响因素，因此输电线规划是一个大规模的非线性组合优化问题。传统数学优化方法已经不能满足规划要求[7]，为提高输电线路径规划性能，涌现出众多人工智能启发式方法，比如蚁群算法（Ant Colony Optimization，ACO）、遗传算法（Genetic Algorithm，GA）、模拟退火算法（Simulated Annealing Algorithm，SAA）以及地理信息系统与智能算法的结合等[8-10]，与传统规划方法相比，这类启发式规划方法打开了路径规划的新世界，能在较短的时间内以较高的搜索效率得到合理的规划结果。这些具有启发式思想的规划方法已经被诸多学者应用于输电线规划中并证实其有效性。石经纬[11]以地理信息系统（Geographic Information System，GIS）作为平台对影响输电线的地理因素进行分类，运用层次分析法建立输电线路径自选结构图，并通过蚁群算法进行了优化，运用多种方法形成了路径自选系统。谢景海提出输电线路径规划应考虑地理与环境等因素，使用GIS 处理RS 获取的规划区遥感图像，并采用蚁群算法进行路径规划[12]。使用云平台将海量数据三维数字化，并联合GIS 技术建立成本评估模型，为Q-learning 进行路径规划打下基础[13]。苏海锋和许道林[14]等利用层次分析法和蚁群算法，对路径成本值进行计算以及路径的规划，实现了规划中障碍识别和避让的功能。董翔宇[15]用栅格法构建路径规划仿真环境，结合蚁群与人工势场算法进行巡检机器人路径规划。李杰[16]针对规划区的特征划分不同类型的单元格，对禁忌搜索算法进行改进，进行路径规划，一定程度上加快输电线规划效率以及减少工程成本。上述研究只是将智能工具与智能算法当成一个处理以及分析数据的手段，并没有具体将输电线规划问题与现代智能技术深层次的相结合。

在此背景下，本文充分利用地理信息系统与蚁群算法在路径搜索中的优势，针对输电线路径规划方案中缩短路径长度、规避障碍物以及改善线路迂回情况三大难点，提出了相对应的优化机制。采用蚁群算法与GIS 结合的方式，以ArcGIS 作为输电线路路径选择的地理信息数据采集和分析平台，用模糊层次分析法整合地理图层并确定综合图层，建立了基于优化蚁群算法的输电线自动规划路径模型。

1 研究思路

输电线路径规划过程复杂，涉及多种地理信息因素，本文在构建输电线路径规划模型之前，可将全过程系统化，为国家电网建设路径规划过程提供参考。整个路径规划方法共包括三部分，首先借助ArcGIS 工具处理点、线、面三种源数据，并生成综合栅格图；其次，使用模糊层次分析法（Fuzzy Analytic Hierarchy Process，FAHP）将综合栅格图中的影响因素量化并得到综合成本矩阵；最后路径搜索阶段，借助MATLAB 工具，在输电线综合成本矩阵的基础上，进行路径规划的更新迭代，得到最终的最优路径。具体路径规划方法研究步骤如图1 所示。

1.1 综合图层构建

通过ArcGIS 采集和处理影响输电线路径规划的成本图层，包括可通过型成本图层与障碍型成本图层，综合图层为二者图层信息叠加而成，为输电线路径规划做基础准备工作。

使用栅格表示的方法，在ArcGIS 中将规划区域中的各个图层栅格化，每个栅格都有各自的属性，其中包括栅格的位置信息、大小信息以及成本信息。栅格的成本信息主要为输电线路建设的成本，考虑不同地理信息因素对建设线路的影响程度，将栅格成本分为五个等级，具体栅格成本等级分类见表1[14]。

表1 栅格成本等级表Table 1 Grid cost grade table

栅格图层与成本图层关联，赋予每个栅格综合成本信息。综合成本信息由多个成本图层按照不同的权重系数累加而成，其中成本图层包括可通过型成本图层与障碍型成本图层。图2 所示为10×10的单元栅格，其中灰色栅格代表可通过型，栅格中数字为具体成本，黑色栅格为不可通过型，代表障碍物。

图2 栅格成本表示Fig.2 Grid cost representation

1.2 综合图层权重计算

输电线路径搜索的最终目标是得到安全可靠、环境友好、经济合理的输电线路。为一定程度上提高输电线路径规划方法的准确性，需在规划过程中综合考虑多方面因素，即线路长度、地形地貌、交通运输、施工条件以及地方规划等，这些因素量纲各不相同，无法统一评估。因此，我们针对GIS 栅格数据表示的路径选择区域的各类图层信息，使用模糊层次分析法（Fuzzy Analytic Hierarchy Process，FAHP）综合量化图层信息，将专家主观判断的影响因素进行量化。如军事禁区、自然保护区等区域，无法以任何形式跨越，作为障碍物；对于可以跨越的地区，根据该地区相关地理信息，综合评估总成本值，采用模糊层次分析法进行图层权重计算，具体步骤依次如下：构造模糊判断矩阵、确定初始权重、去模糊化、确定最终权重。

2 优化蚁群算法的路径规划模型

2.1 传统蚁群算法

蚁群算法是Dorigo 提出的一种分布式智能仿生算法[17-19]，其灵感来源于大自然中蚂蚁群体寻找食物过程中能形成一条最优路径的现象，蚂蚁在寻找路径过程中，会释放“信息素”，在蚂蚁移动的过程中，有“信息素”的释放也有“信息素”的挥发。该算法根据“信息素浓度”判断下一移动的位置，具有随机性[20]，具体表达见式（1），即在t时刻，蚂蚁k从位置i去往位置j的移动概率为：

式中：i，j分别为起点和终点；ηij(t)=1/dij为两点i，j路径距离的倒数；ηis(t)=1/dis为两点i，s路径距离的倒数，其中s∈allowedk；τij(t)为t时由i到j的信息素浓度；τis(t) 为t时由i到s的信息素浓度，其中s∈allowedk；allowedk为邻接矩阵中不包含障碍物和禁忌节点集合。

信息素的增加与消散有三种不同的更新原则，即由Dorigo 等[21]提出的蚁量模型、蚁密模型和蚁周模型。相对于蚁量、蚁密模型利用的局部信息，蚁周模型利用的全局信息有着更好的信息更新策略，因此本文选用蚁周模型进行信息素的更新，如式（2）所示：

式中：Q为信息素的强度增加系数[22]；Q/Lk为每单位长度信息量；为蚂蚁k在位置（i，j）上释放的信息素增加量。

2.2 优化蚁群算法

在路径搜索中，针对输电线路径规划方案中缩短路径长度、规避障碍物以及改善线路迂回情况三大难点，本文提出相应的优化机制，即提出基于优化蚁群算法的输电线规划方法。优化蚁群算法融合导向与综合成本型机制，在微观上具体表现为导向型、升维型以及避让型三大功能。

2.2.1 导向型机制

蚁群算法是一种仿生型算法，自然界蚂蚁最开始觅食时，即人工蚂蚁开始搜索时，没有具体的方向，仅依赖同伴在搜索食物时散发的信息素，通过信息素浓度来决定具体的搜索方向，所以在人工蚂蚁搜索路径时，往往会导致搜索时间长容易产生路径迂回等问题。

为避免这些问题的发生，在人工蚂蚁搜索过程中加入方向引导因子，如图3 所示。在人工蚂蚁搜索路径时，初始化各个位置的信息素，其中起点指向终点方向上的位置信息素略大于其他方向的，使人工蚂蚁在搜索时，将指向性的向终点搜索，避免过多路径迂回情况的发生，在很大程度上缩短了人工蚂蚁在初始搜索时的时间。

图3 初始搜索对比图Fig.3 Initial search comparison diagram

2.2.2 升维型机制

传统输电线路选址，往往是从A 地区为起点，B地区为终点进行线路规划，中间将跨越多个地区。为了准确计算输电线路选址的成本要求较高分辨率的栅格数据，决定了模型处理的栅格数据地图数据量较大。如果直接针对栅格地图数据进行选址，处理的数据量过大，耗费时间较长，甚至得不到最优解[23-24]。

针对栅格数据地图数据量较大的问题，本文提出了降低输电线地图栅格维度的解决办法，即构成栅格数据集的像元尺寸变大。为使输电线路径成本值最低，需在路径起止点之间确定最佳的路径转角，因此引入辅助中间点定位作为路径转角选择的方法。该方法引入了像元作为辅助节点，实现了整体路径的局部搜索，降低了搜索范围的存储空间，进一步实现了高效率低成本的目的，具体做法如图4 所示。

图4 “分布逼近”方法站点选取过程Fig.4 Site selection process with"distribution approximation"method

2.2.3 避让型机制

传统蚁群算法选址，由层次分析法得到各因子的权重，并通过栅格计算器计算，可以得到综合成本图层。综合成本图层包括可通过型成本图层与不可通过型成本图层。为判断二者图层区别，通过设置不可通过区为较高成本值来判定，即设置不可通过型图层栅格值为“9999”。该方法在应用中，计算机计算量大，也不能使路线完全避让不可通过型栅格。

因此，引入单位矩阵，其中0 代表可通过栅格，即图5b 中白色栅格，1 代表不可通过栅格，即图5b中黑色栅格。进一步对单位矩阵进行邻接处理，计算出每个栅格中可通过的栅格位置，并与成本图层叠加，得到综合图层中所有可通过的栅格成本，便于后续路径规划，具体操作步骤如图5 所示。

图5 综合成本栅格图形成过程Fig.5 Formation process of comprehensive cost raster chart

3 实例研究

根据本文提出的融合导向与综合成本型机制的优化蚁群算法用ArcGIS 处理栅格数据，以及MATLAB 作为开发平台，开发了输电线路路径自动搜索程序。实验测试区包括某省绥阳、遵义、凤岗、湄潭、余庆5 县（数据来源：数据禾，https://www.databox.store/Home/Index），南北跨度38.74 km，东西跨度24.59 km。该区域构造复杂，地貌多样，其中坡度、高程、土地覆盖、公路、水系和居民地为成本型图层，自然保护区为避让图层。下面针对该测试区域进行路径搜索。

1）原始地理信息处理以及栅格化

原始成本型图层包括点、线、面3 种要素。在使用MATLAB 进行路径搜索前，首先需利用ArcGIS 处理原始成本型图层。其中针对点要素以及线要素，先计算图中每个像元到最近源的欧氏距离，进一步根据面图层以及点、线要素的欧氏距离图层进行等级分类。将栅格值按分级得分，即1，2，3，4 和5 来赋值，如图6 为测试区内地形、高程和坡度等成本型地理信息数据等级分类后的栅格图。

图6 重分类栅格图Fig.6 Reclassified grid

2）综合权重确定

考虑到各个地理信息因素的影响程度不同，选用Delphi 法[25]，由专家对地理信息因素进行两两重要性比较，重要程度采用1—9 标度定量表示，并采用三角模糊数表征其不确定性，得到各因素的模糊判断矩阵，如表2 所示，最后计算得出各个影响因素的权重值[26]。

表2 影响因素权重判断矩阵Table 2 Influence factor weight judgment matrix

3）路径搜索对比

为了验证本文方法的有效性，将上述地图数据生成大小为500 m×500 m（栅格规模为[51×30]）的栅格。分别采用传统蚁群算法和优化蚁群算法对同一研究区域栅格图进行路径搜索，得到不同算法规划路径图对比与不同算法最短路径收敛对比。

在如图6 所绘制的栅格图中开展路径规划仿真实验，仿真实验初始条件如表3 所示。依据仿真实验结果得到如图7 所示的路径对比图以及最短路径收敛对比图。

表3 算法仿真结果对比Table 3 Comparison of algorithm simulation results

图7 算法运行结果对比Fig.7 Comparison of algorithm running results

由图7 可知，2 种算法均能避开障碍区域，但是优化后蚁群算法采用单位矩阵方法对障碍物进行识别，减少了计算机的运算量，提高了运行速度。同时，优化后的蚁群算法在避免障碍物的同时，在方向因子的作用下，对终点有导向性，不会产生线路迂回，拐点个数也大幅度减少，使规划路径更为合理。优化后的蚁群算法明显优于传统算法，与优化后的蚁群算法相对比，搜索速度更快效果更好。

4 结语

针对输电线路径规划中数据量大、运行时间长、规划不合理等难点，本文提出相应的导向型、升维型和避让型优化机制，结合ArcGIS 平台与MATLAB 软件，提出了基于方向引导和综合成本的蚁群优化算法，以及自动规划路径模型。

选取某省局部地区为研究区域，以提出的模型完成了对实验区域的路径规划工作，并与传统蚁群算法运行结果进行了对比。仿真结果表明，本文提出的方向引导与综合成本的蚁群算法，无论是在运行速度、路径长度以及产生路径拐点个数都明显优于传统的蚁群算法，这证明了基于优化蚁群算法模型的有效性和可行性。