农村电气化路径的混合遗传算法及其优势

能源与人工智能10（2022）100186透视基于分层插值遗传算法的杰里·C·F放大图片作者：Daniel M. 年轻科罗拉多州立大学，柯林斯堡，CO 80523，美国H I G H L I G H T S G R A P H I C A LA B标准• 实现SDG7需要更好的• MAA* 算法是有效的，但像其他方法一样，只提供一个最优路径。• LIGA算法是一种改进的遗传算法，用于粗路径族的识别。• 结合使用LIGA和MAA* 来识别接近最优路径的族。• 这种混合方法为优化网络设计和实现提供了高灵活性。A R T I C L EI N FO保留字：农村电气化SDG7路径查找遗传算法，A* 算法A B标准联网的农村电气化是加速农村电气化的另一种途径。利用卫星照片和地理信息系统工具，配电网络被用来连接村庄和适当位置的发电设施，以降低电气化成本。为了设计网络，确定连接所有节点对的最佳路径，然后找到最小化成本的网络拓扑。早期的研究表明，由于农村地区地形复杂，A*（A-star，一种最优路径查找算法）在此应用中效率低下。乘法器加速的A*（MAA*）算法克服了关键的性能问题，但是，像A* 一样，只产生一条连接每个节点对的路径。依赖一条道路会增加项目风险，因为在实施过程中可能会出现不利条件，如不准确的地理信息系统估计、意外的土壤条件、土地权利纠纷、政治问题等。本文提出了一种结合遗传算法和A* / MAA*算法的混合路径搜索方法。所提出的方法提供了一个家庭的近最佳路径，而不是一个单一的最佳路径路由。一系列路径使项目实施人员能够在新信息可用时快速适应意外情况，并在实施之前或实施期间灵活更改网络拓扑，同时对项目成本的影响最小1. 介绍确保到2030年人人都能获得现代能源是联合国第七次可持续发展目标中提出的一个雄心勃勃的目标。发展目标（SDG7）[1]。虽然已经报告了令人鼓舞的进展，但人们也普遍认识到，向剩余的未得到服务的人口提供能源越来越具有挑战性[2，3]。这一群体通常生活在小型农业集群中（即，（村庄）* 通讯作者。电子邮件地址：dan. colostate.edu（D.Zimmerle）。https://doi.org/10.1016/j.egyai.2022.100186接收日期：2022年2月23日;接收日期：2022年7月13日;接受日期：2022年2022年7月21日在线提供2666-5468/© 2022作者。由爱思唯尔有限公司出版。这是一篇开放获取的文章，获得了CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可从ScienceDirect获取目录列表能源与AI期刊主页：www.sciencedirect.com/journal/energy-and-aiJCF Li等人能源与人工智能10（2022）1001862图1.一、 农村电气化 网 络 框架。在偏远、难以到达的地区。目前的电气化做法往往侧重于光伏发电，因为它可以在大多数地区很容易地建造，并需要最少的专业知识来维护。然而，由于需求和供应的不确定性，这些小型系统的准确容量规划以优化系统经济性具有挑战性[4，5]。在能源供应方面，虽然在大面积上汇总的太阳辐射统计数据是可靠的，但由于地形阴影和类似的选址问题，特定的小目标区域的辐射可能与较大区域显著偏离。虽然通常的做法是在个别村庄安装可再生能源发电，但大多数村庄在历史上都是为了优化农田和水资源的获取、安全和类似因素。这些选择往往导致次优的光伏发电，并把光伏阵列单独在村庄可能会产生光伏发电和土地使用的问题。在需求方面，农村地区的人口往往随着时间的推移而发生重大变化。此外，在5-20年的时间框架内，很难预测每个人口的需求，因为农村地区的生活和经济可能在该时间框架的子集内发生显着变化。这些因素使得负荷增长预测变得复杂，并且基于短期需求预测的容量规划通常是不可靠的。因此，过度投资和投资不足是这些小系统的常见问题。国际能源署最近的研究预测，到2030年，人们仍然没有电力供应，保持不变[3]。为了降低农村电气化的成本，一个研究重点是确定能源的成本最优组合[6，7]，另一个研究重点是研究电气和/或空间拓扑结构，以设计最优的电力供应结构[8，9]。当可以获得准确的预测时，或者当定位生成相对不受约束时，这些方法工作得很好。然而，不幸的是，许多农村地区并不满足这些条件。本研究采用了一种不同的方法，重点是电力系统拓扑学：设计一个本地联网的电力系统，可以适应农村需求的变化，并利用成本较低，或性能较高的发电地点。虽然拓扑优化已经被广泛地研究，但是大多数这样的研究广泛地简化了搜索空间的几何性质，以便使传统的优化（即路由）方法在计算上易于处理。如[10，11]所示，这种简化可能导致较大的误差和次优结果。正如我们以前的工作[10，11]，我们发现最好不要简化几何属性图1描述了拟议的框架。该解决方案实现农村电气化采用本地和网络化供电相结合的方式，以产生更好的发电性能和资源利用率，提高实施的灵活性，并提供能够适应人口转移和不同负荷增长的灵活电力系统[10，11]。我们首先假设电力系统的前期规划必然是不完整的，因为工程和规划的成本很高 调查 工作 这些 是 典型 约束 农村电气化项目。因此，我们的初步设计将以廉价的卫星信息和地理信息系统工具为基础。只有在证明可行性后，才会进一步改进。在这一框架内，一组村庄通过配电网连接起来。为了实现成本最优，该系统通常比通常用于农村分配的简单辐射系统更复杂[12，13]。通常，当村庄主要由集中的、较大的光伏设施供电时，成本就会降低，这些设施的选址是为了提高发电效率，并降低总资本成本。此外，还为每个村庄安装了本地发电系统，用于备用或应急发电[10，11]。这种系统的完整设计是一个复杂的主题，其中应包括许多考虑因素，如潮流、电缆尺寸和保护系统。这远远超出了这个最初的基于拓扑的优化研究的范围。而不是一个完整的设计，我们专注于一个子集的问题：如何最大限度地减少安装在崎岖的地形在大多数农村地区的村庄和发电地点之间的互连的成本。我们先前工作[10，第十一节]已经解释的乘法器加速A*（MAA*）算法，这显着提高了效率，发现近最佳的互连。本文重点讨论了影响网络化农村电气化框架可行性的关键遗留问题之一：在位置之间开发灵活的路由。这是联网农村电气化所需的更大的总体框架的一部分。为了帮助感兴趣的读者，我们在最后一个附录中包括了以前工作的入门（附录D-网络农村电气化方法概述），而不是在主要论文中重复这一讨论1.1. 各向异性及其影响未通电的村庄群通常位于远离人口中心的地区，其典型特征是地形崎岖或其他难以进入的地形（例如小岛）。对于这项工作，我们专注于地形崎岖的地区，在这些地区，配电线路路由的相对较小的变化可能会对施工和维护成本产生重大影响。实例包括中国北京的门头沟区或作者工作过的卢旺达西部的热带高地。在这些地区，在水平方向上相互靠近的村庄可能会被海拔高度的巨大变化所分隔，例如山脊线或河流峡谷。这些地区也有在数字化地图中，最优路径算法定期检查从当前位置向所有可用方向移动的分步代价，并将其与存储的信息进行比较以做出移动决策。这些农村地区的复杂地形可能导致每一步向不同方向移动的成本非常不同。我们把这种在搜索空间中的剧烈代价变化称为“各向异性”。’设计一个最佳网络基本上是一个路由，或路由-寻找，问题包括（i）寻找连接任何两个节点的（接近）最优路径的成本，其中节点可以是村庄或集中式发电设施，如图1所示;以及（ii）基于在（i）中计算的路径成本来识别最低的总网络成本。理论上，经典的A*寻路[14]可以应用于任务（i），最小生成树（MST）或其衍生物可以应用于任务（ii）。然而，如以前的工作[10，11]所示，经典A* 是低效的在该应用中，通常使用的A* 加速方法也在高度各向异性的条件下挣扎。因 此 ， 作 者 开 发 了 乘 数 加 速 A* （ MAA* ） 和 自 适 应 乘 数 加 速 A*（AMAA*）算法[10，11，15]，这些算法可以产生接近最优的解决方案，并显著减少计算工作量。与经典A* 相比，MAA* 通常将计算减少90%，同时影响不到10%的最优性;JCF Li等人能源与人工智能10（2022）1001863==图二. 典型的最优网络。图示的连接是从将每个节点连接到每个其他节点的成对路由选择最小生成树的结果。图三. 比较基于A* 和MAA* 计算的最优路径成本。全局最小值是用经典的A* 算法计算的，而m=x的条目是用MAA* 算法计算的路由（见正文）。直线成本计算沿直线连接的所有网格正方形的成本。直观的极点配置表示通过直觉选择的一条可能的路线最优性和计算时间之间的折衷可以由用户定义。AMAA* 扩展了MAA*，适用于路径起源于或必须绕过相对较大的区域且路由成本较高的复杂情况。与MST结合使用，图2是应用这些算法产生的接近最优网络的示例。为了确定联网方法是否具有成本效益，可以将MAA* 的结果与传统的农村电气化逐村方法进行比较。如果联网办法的计算成本较低，联网的农村电气化对于特定的地形和村庄分布是一种成本较低的解决办法1.2. 摘要：MAA* 算法的关键属性由于MAA* 算法将在整个文件中使用，其基本属性概述如下。详细信息见[10，11]。(a) 在最优路径搜索过程中，经典的A* 算法将当前路径代价估计与历史代价估计进行比较，从而做出移动决策。当满足适当的要求时，可以保证全局最优;(b) 对于各向异性的搜索空间，（a）中的比较经常迫使A* 算法在整个布线过程中的早期布线阶段重新开始搜索，使得该方法非常低效;(c) 通过选择参数m，MAA* 选择性地减弱了重新访问历史决策的吸引力，降低了早期重启的频率和由此产生的计算成本。在该方法中，m设置衰减率。当m为0时，MAA* 退化为经典A*.符号MAA*（p）用于表示具有m p的MAA*;(d) 随着m的增加，计算工作量减少，解决方案通常远离最优;(e) 从大量的实验来看，m在0.5到2之间可以减少80-98%的计算时间，并减少5- 20%的最优性。这允许用户根据他们的要求在计算时间和最优性之间进行权衡。图3提供了MAA* 性能的快照：t是使用典型Windows i7机器的计算时间，单位为秒全局最小值使用经典A* 计算。成本函数包括材料、劳动力和其他成本，这将在第2[10，11]中更详细地讨论另一种选择从图中可以看出，使用这种方法的成本（即，805）远高于使用形式优化获得的成本，即使直观路径位于与MAA* 路径近似相同的空间区域中。这说明了农村地区的各向异性：路线的微小变化可能导致成本的显著变化。该图显示了一个节点对路由，使用A* 需要92小时。 一个典型的网络设计需要连接多个村庄和多个潜在的发电地点，导致几百个节点对路由。因此，需要计算效率JCF Li等人能源与人工智能10（2022）1001864见图4。 多路径解决方案的优势，在一个有四个节点的小型网络上进行说明。左图表示连接四个节点的近似最优路径族，这导致首选（通常成本最低）网络。如果在实施过程中发现其他障碍，现场团队可以选择连接相同节点的不同路径（右上），或一组替代连接（右下），所有这些都具有类似的成本。最后，一个关键点是，输入数据在技术问题（海拔，土壤类型等）上往往误差20%或更多。而且往往忽略了只有在最后规划阶段才出现的关键社会政治因素。因此，在现场条件下，在最优解的10-20%范围内的布线实际上与全局最优解没有区别。1.3. 多路径解决从我们以前的工作的A*-衍生算法的结果产生一个单一的，接近最优的，路由问题的解决方案。然而，在现实世界条件下，考虑到当优化完成时不可避免地不完整或不准确的信息，该解决方案不一定是鲁棒的。因此，有利的是找到可以在现场条件下使用的多个接近最佳的路径与大多数路由算法的情况一样，这些方法在离散化地图上操作，其中影响路由成本的关键参数被分配给地图的每个离散元素。这种类型的离散化通常用于类似的问题[16，17]。对于我们的应用程序，初始地图通常是从卫星照片和数字高程模型中获得的，以减少前期调查成本，这通常可以与交通不便的农村地区的建设成本相媲美。在最初的数字化地图上，可能有些土地状况没有被正确分类，或者有些土地特征可能看不见。即使物理上准确，也可能出现意外情况，如所有权纠纷，土地使用政策变化等。这可能会改变路由的成本。因此，一种方法，产生多个，地理上不同的，网络拓扑结构与类似的成本允许现场团队调整路由在详细规划阶段的项目。通过设计，A* 和衍生算法（如MAA*）只能找到一个路由解决方案。从实际应用的角度来看，一个更好的算法将产生多条路由，具有相似的成本，允许根据需要进行值得注意的是，同样的问题，不完善的信息-在其它基础设施路由情况下，信息是常见的。例如，一条穿越美国东部几个州的天然气管道由于环境问题，在西弗吉尼亚州的一小段路线上遭到强烈反对。这些问题是管道开发商没有预料到的，由于缺乏预先计划的、可行的、成本类似的替代方案，情况更加恶化。本文讨论了一种混合寻路方法结合了修改后的遗传算法-这这种方法产生多个接近最优的网络，并增强了实现过程中的灵活性。如果没有替代路线，在时间压力下重新设计项目可能会消耗大量资源，大幅增加成本，并且可能会产生一个距离最佳值更远的折衷解决方案。给定一族近似最优解决方案，两种类型的快速重新路由是可能的：（a）等效近似最优路由经由不同路径连接相同节点，以及（b）替代近似最优路由连接所有节点，但是以具有不同路径的不同对。这三个元素一起定义了多路径解决方案：（a）优选的近最优路径，（b）用于构建等效网络的近最优路径族（拓扑上等于优选网络，地理空间上不等于优选网络），以及（c）用于构建替代网络的近最优路径族（拓扑上和地理空间上都不等于优选网络）。这些族在图4中示意性地示出。一般来说，替代等效网络比替代网络侵入性更小，因此是首选。第5提供了一个示例。总而言之，农村电气化网络框架始于用MAA* 替换A* 以加速详细路由。这里讨论的工作增加了开发一系列接近最优路线的能力，以提供一系列可以适应现场条件的实用解决方案。在这两种情况下，最优网络（接近最优路径）是使用MST开发的。2. 使用遗传算法寻路：为什么和如何？遗传算法（GA）可以作为一种替代方法来找到我们的测试地图上的节点对连接的最佳路径然而，由于下面将变得明显的原因，GA通常不会提供具有与A*、MAA* 或AMAA* 相当的最优性的解决方案。检查GA的原因是因为它可以用来找到具有类似成本的多个解决方案，如果受到这里开发的修改的约束。本节简要说明如何将GA应用于路径查找问题。基于这一认识，第3讨论了多路径解决方案。2.1. 遗传算法在路径搜索中遗传算法[19，20]被广泛用于优化问题。应用遗传算法的方法显着不同的调查中的问题。本节解释如何使用GA进行最优寻路。JCF Li等人能源与人工智能10（2022）1001865i=0时（+）（+）图五、在此应用中，采用遗传算法求取最优路径.安全、地面状况等）其中，w1、w2是加权系数。权重因子的选择受技术能力、设备可用性、材料、人工成本等因素的影响。对于该分析，xi，yi={0，300}，hi={1，2，3}，ai={0，3，10}，w1=6，并且w2=3。更多细节请参见EscherdiX D寻路算法的目标是最小化∑P Ci+1，见图6。GA+A * 杂交方案。在上图中，使用遗传算法开发了一条由少量直线段组成的近似路径（见正文）。在下图中，通过将A* 应用于这些较短的段来完成详细的布线。在高度各向异性的环境中，该方法所需的计算能力明显低于使用A*直接识别 起始节点和结束节点之间的最优路径在我们以前的作品[10，11]中，我们定义了i第一次在路径上的运动：其中P是路径中通过地图的离散正方形的移动次数 一个基本的，直观的算法是（图。（5）：(a) 绘制一条连接两个节点的直线(b) 基于直线路径计算初始路径代价(c) 在直线路径周围生成n个随机节点，并连接创建一条可能路径;(d) 计算新路径的路径成本(e) 重复（a）-（d）以产生新路径的起始群体或基因型;(f) 将生成的路径按照路径代价降序排序(g) 选择前k条路径;(h) 应用遗传算法，通过对k条路径的初始种群进行渐进变异来找到最优路径。对于该问题，遗传交叉被定义为在路径之间交换选定的节点，而突变被定义为路径中的一个节点2.2. 高度各向异性条件下简化遗传算法的性能与A* 算法不同的是，在A * 算法中，获得的最优路径基本上可以采用任何物理形状，从传统的GA获得的最优路径简单地由n1个直线段构造。因此，GA结果可能会产生比A* 或MAA* 算法产生的路径成本更高的路径：分段线性路径段在高度各向异性的成本环境中不太可能是成本最优的。然而，当开始和结束节点之间的R2距离是大的，GA方便地确定一个或多个近似的最佳路径作为一系列的直线段的approximate位置，阳离子。例如，GA结果可能会避开难以穿越的区域，或识别通往障碍物（如河流或山脊线）的低成本方法。然后可以使用A* 或MAA*（图6）对每条直线进行布线，这在短线段上是计算上易于处理的，因为搜索区域将很小，除非遇到极端的各向异性[15]。为 这 应用， 的 选择 的 n 驱动器 两 的 成本和GA方法的复杂性。 更大的n允许更完整C=[（h-h）2+（x-x）2+（y-y）2]1+ w|H-H| + w a探索的地图，并减少了详细的路由成本，但也i+1i+1ii+1i2i+1i1i+1i2i+1（一）导致许多后代是高成本的曲折道路，通常不适合。实验上，一个3或4个节点的小n生成路径，其中xi、yi、hi是路径中第i个点的2D坐标和高程，ai是可达性（即，在该点处执行建筑工作的难度，其可能受到当前使用的影响，成本低于初始直线，而n>7产生许多成本高于步骤（g）的初始选择的作为示例，图7将单独使用GA获得的路径的成本与使用GA+ A* 混合路由获得的路径的成本以及使用GA+ A*混合路由获得的路径的成本进行比较。JCF Li等人能源与人工智能10（2022）1001866见图7。与遗传算法（GA）和混合算法（GA + A *）相比，从A*（全局最优）得到的路径成本初始GA布线后，MAA*（1）详细布线。GA布线成本为805，但将A* 混合应用于详细布线将此成本降低45%至452。正如预期的那样，虽然两种方法都没有达到全局最优的成本（GA的43%），但GA+A * 产生了接近最优的结果（GA的56%）。请注意，GA算法很容易绕过两个端点之间的高成本区域; A* 和MAA* 算法探索整个地图的大部分以得出相同的结论。见图8。使用GA和MAA* 生成不同区域的近似最优路径。在地图中心的高成本区域周围布线对于A* 算法甚至MAA* 算法来说都是具有挑战性的，但LIGA算法很容易完成。全局最优路径使用A*。正如预期的那样，A* 算法的性能要比遗传算法好得多，而混合算法介于两者之间。巧合的是，遗传算法的结果是相同的直观极点配置方法在图。3.第三章。应该注意的是，该示例中的GA已经执行了30代，并且使用不同种子的作为一个额外的比较，使用MAA*（1）计算的路径成本是395，这也远远优于GA（图2）。 3）。从这些实验中，我们观察到，GA的解决方案，其次是局部改善使用A*，MAA* 或AMAA*，产生可接受的低成本的解决方案。然而，这并不能直接解决第1节中所述的问题：这种混合方法仍然产生单一路径，但需要多路径方法来响应输入数据中的错误或意外情况。为了开发多路径方法，我们修改了标准GA，在应用算法之前根据空间特性对初始路径（即基因型）进行分组。插值也被应用于增加自由度，最优性（第3）。3. 水平化插值遗传算法产生多路径解的基本思想如图所示。8.第八条。一个家庭的粗糙，接近最佳，连接两个节点的路线，获得使用还引入了进一步的细化（即，插值，图8中未示出），用于在优化过程期间增加自由度，以便实现更低的成本（即，更接近最优解）。在详细讨论层次化和插值之前，首先考察了各向异性对遗传算法的重要影响在大多数GA应用中，鼓励保留各种各样的基因型[19，20]。然而，在一个应用子集中，存在一组以上的主导近优解，组之间的交叉不太可能产生更好的结果（尽管这不是严格不可能的）[21，22]。此外，这些之间的交叉JCF Li等人能源与人工智能10（2022）1001867==+ ++-- - -一种见图9。 基因型组显著增加了计算负担。根据我们的工作，在高各向异性下应用GA进行寻路显示了这个问题（图9）。路径的初始选择将快速生成一组以上的接近最优的解决方案。例如，围绕紧凑障碍物的“向右”或“向左”的路径在这些情况下，非选择性交换产生了许多次优路线在本申请中，虽然第2组和第3组中的基因型之间的交换可以通过图中的灰色虚线连接产生可行的新解决方案，但是例如第1组和第4组中的基因型之间的交换将不太可能导致任何有意义的改进。如果基因型可以系统地按亲合性使用它们与连接的直线的相对距离定义 在我们的例子中，开始和结束节点-因此，这些组可以用于合成所需的解决方案-一个显然，接近性或任何其他单一度量对于基因型分组可能不是理想的。虽然可以使用更复杂的分组方案，但大多数也会增加计算负担，并且在初始优化期间配置具有挑战性，因为在早期项目规划阶段可用的信息有限。为了实现这一目的，在其他近最优路径附近获得一条更好的路径与找到具有更广的地理覆盖并因此在实施阶段提供选项的一系列接近最佳的路径相比，因此，在所提出的算法中，距离偏离连接两个节点的直线被用作分组的简单度量，并表示为“水平”。假设每个水平是一个基因型亚组，仅在水平内交叉。在实践中，该算法分两步实现：步骤1：均衡化-在一般意义上，我们的方法是试图确定存在于不同区域Z i，i中的主导近最优解1， 2，用户. 虽然这里仅限于三维空间，路由问题，该方法适用于更一般的高维优化问题。为了找到特定区域中的优势解，必须选择与该区域相关联的起始基因型作为GA过程的输入。这里使用的度量是基因型与连接两个节点的直线的平均偏差或距离。除了简单的几何距离之外，还可以使用诸如成本加权距离或模糊分类器的度量，并且基线可以被选择为除了连接节点的直线之外的东西。因此，使用更通用的术语“水平“而不是“偏差“来描述分组度量，并且分组过程被称为“水平化”。从简单GA算法的步骤（g）开始，k个最低成本，随机生成的，路径被分组到级别;一个例子是在图中所示。 10，其中期望的结果是双向的三级指数（即，3，2，1，0，1，2，3），产生7级。一般来说，在应用前面讨论的遗传算法之后，每个级别组将产生一个或多个粗略的、接近最优的解，从而开发出一系列地理上不同的接近最优的路径。从所有级别中选择所得到的近最优路径族。应该注意的是，一些区域可能成本太高，无法产生与其他区域竞争的路径。然而，如果需要更多的路由多样性，用户仍然可以保留这些区域中的解决方案第2步：插值正如在3.2节中指出的，在生成随机路径（基因型）时，n不应该太大。然而，在将路径分组为级别之后，节点的数量少限制了搜索低成本路径的能力。插值通过在每个线段的中点增加一个额外的节点来增加节点的数量（图11）。因此，如果在生成随机路径时n =3，则插值后将有7个点可用。然后应用遗传算法。最后，在GA过程之后，如前所述的A*、MAA* 或AMAA* 细化分别应用于每个水平中的基因型参考图1中的地图。 3的图 12显示示例LIGA输出见图10。 通往各层的通道。JCF Li等人能源与人工智能10（2022）1001868- -见图11。 路径插值。见图12。 EX样本GA输出后，三个层次的水平和插值。用于连接（50，60）和（250，190）。这些曲线表示对于使用30代的路由，针对级别2、0和2获得的粗略的、接近最优的路由的物理形状图A.1和A.2中的A.1和A.2提供了与LIGA输出相关的更详细的视图。图，包括在不同突变率、交叉标准等条件下15次试验和100代获得的结果。图A.1记录了路径的实际坐标，而图1记录了路径的实际坐标。A.2示出了相对于生成的成本改进，即LIGA的收敛。JCF Li等人能源与人工智能10（2022）1001869=--4. 结合LIGA和MAA*图十三. 用于路径家族的LIGA-MAA* 杂交。近似最优解可能占主导地位，以及（b）具有相似成本的多个近似最优解共存。对于这两种情况，GA，在使用LIGA进行粗略布线之后，使用详细布线（例如A* 或MAA*[10，11]）来细化图中的路径。 12（如图所示） 13）。如前所述，A* 或MAA* 算法的速度受到搜索空间大小的影响因此，为MAA* 提供一系列较短的布线然而，请注意，MAA* 算法可能会超出由直线段的端点定义的矩形。使用MAA*（1）来优化线段，来自区段3的上述三条路线的成本（a）在水平2时从782降低到410，（b）在水平0时从959降低到498，以及（c）在水平 2时从973降低到552，更好地接近全局最优349。此外，在图1中的表A.1示出了通过该方法识别的最佳路由具有380的成本，该成本低于通过从端到端仅使用MAA*（1）获得的接近最优的成本395，但是高于通过从端到端仅使用MAA*（1）获得的接近最优的成本395。用MAA*（0.5）获得364（参见图3）。然而，像任何AI算法一样，不能保证哪种方法将给出全局最优的更好的近似，因为算法引入的误差将取决于搜索空间的各向异性，这在很大程度上是随机的。两个应用程序进行了评估，以评估这种混合方法的性能和鲁棒性。第一种情况是上述计算的完整说明，连接（50，60）和（250，190），第二种情况连接（20，20）和（290，190）。从计算中可以看出，这两种情况代表了以下情况：（a）一个使用30代和100代，并且应用具有不同突变率和交叉标准的15次试验。具有相同设置的MAA*用于所有路径细化。情况1关于这种混合方法的一个重要问题是对应性：在算法的第一步中由LIGA生成的少数性能最佳的粗路线是否对应于MAA* 细化后的最佳近优路线？由于高度各向异性的搜索空间阻止了在所有情况下的对应性，实际问题是将详细路由应用于LIGA路由的子集是否会产生合理的、较小的、接近最优路由的集合从数学上讲，考虑所有LIGA结果的集合，Λ={λ1，λ2按成本排序。每个LIGA路由可以使用详细路由来细化，以产生相同大小的集合Γ= {γ1，γ2然后，我们通过递增成本对Γ进行排序，以产生一个有序的相同大小，G= {g1，g2Λ→G.显然，不可能在执行MAA* 计算之前预先确定哪个λ将导致哪个g。换句话说，关系λs→ge中的索引s和e是不确定的，不需要经过详细的路由。然而，尽管存在各向异性，但在大多数情况下，可以合理地假设存在统计学上的正相关。JCF Li等人能源与人工智能10（2022）10018610̂̂̂̂̂L∩===见图14。 LIGA输出和改进路线之间的对应关系，连接（50，60）实际上，详细的路由在计算上是昂贵的。因此，我们选择包含Λ中的M个最低成本路由的子集Λ，并且将详细路由应用于该子集，产生相应的详细路由集合，r= {γ1，γ2M的质量可以通过考虑最低成本详细路由G= {g1，g2接近最优路径。虽然在实践中，G将保持未知，除非计算G中的所有元素，但我们仍然可以开发一个度量并验证 它通过计算一个例子的所有元素，以获得有关对应关系的见解。一个可能的度量是：应该注意的是，虽然细化25-30%的LIGA输出可能会捕获足够低的成本路线，但一些困难的区域（即高度各向异性区域或高度不可访问区域）可能不会在最终细化的输出中覆盖。这种方法的一个关键特征是，这些区域的布线成本很高，并且可能会产生与其他候选区域相比没有竞争力的细化路线。然而，用户可以选择保留来自这些区域的几条路线作为最坏情况的应急路线，因为知道一个或多个其他区域总是比这个区域成本更低。作为说明，表1和图16提供了用于连接（50，60）-（250，190）的替代路线请注意，由于在这种情况下已经计算了所有精确的接近最优的路线（图11）。14和表B.1，diX B），我们选择了最好的精炼近-Q（M）=N（Gr）（三）每个区域的最佳路线进行演示。基于上面讨论的对应性考虑，实际上其中N是计数运算符，返回集合中元素的数量，交集运算符保持对应关系Λ→G。一般来说，我们希望选择M，使得Q尽可能接近1，而不超过项目的计算预算。图14示出了通过MAA*（1）细化的30代GA过程的结果。结果包括七个级别中的每一个级别的15条LIGA路线， 以及使用标准GA生成的15条路线，该标准GA包括前k个基因型而不按水平分组（标记为“水平全”），从而产生120条粗略路线。由于我们的目标是找到有用的替代路线，我们只需要捕获合理数量的“好”路线。从图上看，120条粗路线中最好的25%-30%很有可能达到目的。作为替代视图，图15描绘了粗略路线和精细路线的成本之间的相关性。选择只计算最好的25-30%的LIGA输出的细化，并使用这个较小的结果集来构建多路径解决方案。后面的例子采用了这种方法。该示例清楚地示出了两个地理上遥远的路线可能具有相似的成本。因此，项目人员保留了大幅修改系统路线的选择权，因为他们知道高费用地区以北或以南的路线估计费用相似。众所周知，遗传算法中代数的选择会影响最优性[19]。相同水平的基因型将比应用于类似数量的基因型而不区分它们的水平（即“水平满”）的GA过程更快地收敛。从表2和图17可以看出，当代从30增加到100时，完全级别（即传统GA）的精细路由成本从411提高到385，提高了6.3%。JCF Li等人能源与人工智能10（2022）10018611- -图15. 粗路由和精路由之间的相关性。表1混合法计算结果，G=30，连接（50，60）-（250，190）。方法路径成本MAA*，m1395混合LIGA/GA中的代数=30水平=-2 380水平=-1 392水平=1 476水平=2 528传统GA（level=full）411直线2620全球最低349100.对于2级和2级，随着世代的增加没有改善。虽然这些观察结果与预期一致，但重要的是要认识到，这种理论无法得到正式证明。此外，GA的解决方案是非唯一的，因此仅比较每个级别的最佳解决方案并不严格合适，但它确实提供了选择代数情况2此连接比前一个连接长得多。如[10，11，15]所示，这种连接的A* 收敛非常慢，因为时间复杂度随路径长度呈指数增长。更快的MAA* [10，11]显著减少了计算时间，但仍然需要54小时（典型的i7个人计算机运行Windows）。这种混合方法的一个优点是更快的计算由LIGA产生的较短的段。然而，生成用于MAA* 细化的候选也需要时间。直接比较计算效率来寻找一个是不可行的图16. 实际路径形状使用混合方法，G=30，连接（50，60）-（250，190）。近最优路由使用这种混合方法的效率直接MAA* 计算。作为粗略指示符，产生120个粗略路线（即，e.包括产生基因型、排序、水平化和插值）以使用LIGA连接（20，20）和（290，290）花费大约70小时JCF Li等人能源与人工智能10（2022）10018612=-- -表2混合法计算结果，G=100，连接（50，60）-（250，190）。方法路径成本加速A*，m1395混合LIGA/GA中的代数=100水平=-3 407水平=-2 383水平=3 577水平=2 541传统GA（level=full）385直线2620全球最低349表3混合法计算结果，G=30，连接（20，20）-（290，290）。方法路径成本加速A*，m1634混合LIGA/GA中的代数=30水平=2 712水平=1 656水平=-2 684水平=-3 762传统GA（level=full）649直线3397加速A*，m¼0.5615图17. 使用混合方法的实际路径形状，G=100，连接（50，60）-（250，190）。GA 30代或180 h 100代。使用MAA* 优化粗路线的时间根据段的长度和区域的各向异性而变化，范围从不到一小时到几小时。如果我们假设使用MAA*（1）细化一个粗略路由的平均计算时间为3.5 h，则使用该混合方法生成一个连接需要约4.1 h（对于30代）。这与仅使用MAA*（1）的54小时相比是短的。如果用户决定处理LIGA输出的25%，或30条粗路线，则混合算法的总计算时间约为175小时。假设一半的细化输出（即15条路线）具有令人满意的低成本作为替代路线（参见图16中的先前示例），则每条细化路线的平均计算时间约为11.7 h。虽然近似，但该时间估计提供了关于混合方法在计算效率和最优性方面与MAA* 相比如何的见解，并且再次注意，经典A* 算法超过了在这两个点之间路由的可用计算时间表3和图 18用数字总结计算结果世代G=30。图18. 实际路径形状使用混合方法，G= 30，连接（20，20）-（290，290）。对于这种情况，关键的观察结果是，由混合方法识别的两个最低成本路径（即索引1和索引已满） 限制区域的与MAA*（1）算法识别的接近最优路径相对的一侧。另一方面，有层次的精细化路线2在MAA*（1）路线的同一侧，尽管它们形状略有不同通过混合方法识别的这三个路由的成本与通过使用MAA*（1）进行端到端路由获得的接近最优路径相比具有相似的成本，即使它们在地图的不同区域中。因此，多路径解决方案是高度期望的，因为它为网络设计提供了灵活性，并且如果出现实现问题则能够改变路由。JCF Li等人能源与人工智能10（2022）10018613=增加世代的数量产生的变化很小;见C.D.X C。在得到近似最优路径族后，可采用最小生成树法（MST）进行网络设计。程序概述见[11]。如果任何路径的成本由于意外条件而改变，则MST将基于总网络成本来决定用同一族中的另一个接近最优的路由（即，等效接近最优的网络）来替换它，或者改变网络拓扑（即，如图1所示的替代接近最优的网络）。 4）.5. 讨论基于两个应用实例的观察结果（在研究期间完成了许多其他实例），结合LIGA和MAA* 的混合方法产生了有用的多路径解决方案。最佳成员的费用通常与MAA相当(1)成本其他成员的费用可能类似或更高，视实际地域结构而定。因此，该方法提供了理想的结果：多个接近最优的路径，降低风险，在网络化的农村电气化项目。随着鲁棒性和可靠性的提高，我们的方法的一个重要优势是以最小的项目成本保留后期决策选项。卫星图像和地理信息系统工具可用于快速构建地图，估计可实现的网络，并计算网络解决方案相对于单独电气化村庄的经济优势。通过这种预先分析降低初始规划成本有助于确定联网的农村电气化是否适合某个地区。此外，由于非循环工程成本往往是农村电气化的主要成本，因此使用这些技术有可能降低总体项目规划、初步路线、初步成本计算的成本，从而促进农村电气化项目的融资。在更一般的意义上，这里开发的方法可以是适用于类似各向异性领域的其他基础设施项目。应用包括天然气和石油管道规划，干线通信路由和运输系统扩展。这些方法是特别适用的社会政治因素实际上，完整的设计还必须考虑与网络设计相关的电气参数。如1.2节所讨论的，各种研究人员正在研究电力和几何成本优化。在项目早期阶段，将两者结合起来在技术上是一个挑战。例如，在我们的模型中，电缆容量将分两步解决。我们的工作重点是物理/几何优化网络设计，考虑建设，安装，部署和访问的成本。这些成本相对于正在安装的电缆的尺寸和成本占主导地位。在选择路由之后，可以使用MST的迭代版本CMST来考虑电缆容量和成本， 优化电缆线路的选择[23]。有两个方面需要进一步调查：a) 由LIGA计算的粗略近优路由与MAA* 细化后的细化近优路由之间的成本对应关系，如第4节所述。由于任何一条粗路线的成本在使用MAA* 进行细化之前都是未知的，因此当前的方法假设如果LIGA输出的25-30%被细化，则将保留足够的低成本路线。虽然相关性分析表明，这种方法是合理的，它是可取的，以改善更少的LIGA输出，提供足够的低成本精炼路线被保留。已经观察到，那些快速收敛的LIGA粗路线（表A.2，Lxd