用于加速可重构电网优化的快速辐射状检测方法

《Electric Power Systems Research》：Rapid radiality testing methods for accelerating the optimization of reconfigurable power grids

　　

• 辐状性测试占据了元启发式重构中种群准备成本的80%以上。• 提出了高效的Fiedler（Krylov-Schur）和多重性（LDLT）算法。• 使用便携式C代码在MATLAB和处理器在环环境中基准测试了四种方法。• 在MATLAB中，DFS比Prim算法快约9倍，在嵌入式控制器测试中快3倍。• 推荐DFS作为可重构电网的默认辐状性检查。

引言

向智能配电网的转型特征在于分布式能源资源、电动汽车和微电网的不断集成，其操作规模从公用事业馈线到社区级网络不等。这种演进增加了网络运行的复杂性和动态性，需要能够实时适应网络拓扑的优化工具。电网重构——通过动态重新排列开关状态来重新定义网络拓扑——已成为实现这种适应性的关键推动因素之一。

在电力系统中，配电网是最昂贵的部分，因为其在维护和运行方面存在固有的障碍。这些网络通常通过辐状拓扑进行设计，并且期望不仅高效，而且可靠（低故障率）且具有韧性（能够从不利条件中恢复）。随着可再生能源和非线性负载的集成，配电网的复杂运行和维护面临更多挑战。

重构通常被表述为开关状态的优化问题，其目标可能针对例如损耗最小化、电压偏差减少或可靠性改进；无论标准如何，每个候选拓扑都必须符合辐状性约束。每个候选的适应性评估可能进一步取决于估计的网络状态，这实际上必须通过配电网估计技术从有限或缺失的测量中推断出来。该估计反馈至目标评估，而本文所涉及的辐状性测试仅取决于候选拓扑，因此不受数据可用性的影响。

电网优化对于确定性算法很快变得难以处理，主要有三个原因：(i) 底层问题是非凸的，并且涉及难以用标准优化形式表达的约束；(ii) 系统评估通常在外部软件中进行，因此确定性成本函数不直接可用；(iii) 模型、约束和子系统耦合可能表现出异构行为，包括动态模型、数据驱动元素、随机分量和事件触发变化。因此，电网优化主要采用元启发式算法来解决。这些本质上是一种搜索算法，具有两个主要缺点：理论上，它们只有在无限时间内才能达到全局最优，并且由于必须生成和评估许多候选解决方案然后迭代更新它们，因此需要大量的计算资源。这种搜索过程的许多变体产生了文献中广泛的元启发式方法。

然而，证明这些算法已经改进或成为更高效的优化器是困难的，因为它们的性能在很大程度上取决于具体问题、初始条件和更新规则，这些规则总是包含随机性。因此，关注引入确定性的底层建模选择和子过程更为合理。通常，用于优化电网的算法必须评估每个候选配置。为此，验证步骤验证电网的连接性和辐状性。其中，辐状性是最直接决定可行性的属性，如下文所示，它主导了计算成本。

确保辐状性是最关键的任务之一，并显著影响优化器的性能。Mahdavi等人表明，省略辐状拓扑的约束会改变元启发式算法的计算负担。因此，基于图论的方法越来越多地被采用来强制辐状解决方案。长期以来，人们认为具有n个节点和n-1条边的图可以保证辐状性；然而，仅凭这个条件是不够的。Wang等人对此表示赞同，并因此建议重新表述辐状性约束；Sun等人的工作是关于这个问题的最新努力，其中作者提出了电网图的最大密度概念来建模辐状性约束。然而，持续存在的缺点是比较计算需求。如Mahdavi等人所强调的，基于图论的算法中大部分计算工作量与搜索辐状拓扑有关。

因此，辐状性测试不仅至关重要，而且耗时。然而，其计算效率很少被优先考虑：大多数优化方法针对规划和设计，这些方法可以容忍较长的计算时间，并且通常依赖于专用或专门的硬件，因此只有少数工作——例如Quintana等人以及Mahdavi等人的工作——明确评估效率，甚至这些工作也依赖于高级编程语言，这些语言适合开发和初步测试，但不适合作为预编译的便携式软件部署。这反映在配置框架中，这些框架继续采用Prim算法作为默认辐状性测试，同时仅在周围的元启发式层上进行创新，而其计算成本却未受审视。因此，当报告效率时，由于硬件平台、编程语言和测试条件不同，结果难以直接比较。

事实上，所声称的性能改进不应依赖于专用硬件和高度优化的专有例程；它们也应该能够使用可在通用平台上运行的便携式软件进行验证，例如实时部署在现场设备中使用的平台，以与电网的模块化和自动化保持一致。为此，本研究专注于辐状性测试本身，旨在识别高效且便携的替代方案，通过最初提出两种算法方法，然后对四种不同方法进行比较分析，从而使所得到的收益直接转化为更快的电网优化循环。

简言之，辐状性测试主导了元启发式重构中的种群准备成本，但其效率很少被分析，并且由于硬件、语言和测试设置不同，报告的结果难以比较。这促使进行公平的基准测试以及为资源受限的现场硬件提供便携式、高效的替代方案。本研究的贡献在于：(1) 提供两种高效算法；即通过Krylov-Schur计算Fiedler值（避免黑盒eigs例程）并通过部分LDLT分解与早期终止测试Laplacian的零特征值多重性；(2) 在一致条件下公平比较四种辐状性测试——Prim算法、Fiedler代数连通性、深度优先搜索和多重性；(3) 在两种部署环境中评估——离线MATLAB和嵌入式现场控制器（BeagleBone Black，带处理器在环）——使用便携式、非专有代码，以使收益不依赖于专用硬件或例程。

本文其余部分组织如下。在第2节中介绍NSGA-II、PSA和Fiedler算法。然后，第3节提出高效的替代算法以减少辐状性搜索任务中的时间。第4节展示了用于比较分析不同技术的测试。第5节展示结果及其解释，第6节对结果进行讨论，最后，第7节提供了本研究的结论性评论。

章节片段

辐状性测试在优化算法中的影响

在电网优化的不同元启发式方法中，遗传算法是主要技术。它具有许多变体，但根据Khezri等人的研究，非支配排序遗传算法II（NSGA-II）是最常用于独立和并网能源系统的多目标优化研究。NSGA-II的总体计算复杂度为O(MN2)，并且可以在不需要大量参数的情况下实现更好的解决方案分布。

深度优先搜索

原始DFS策略考虑无向图G=(V,E)。搜索将边分为树边T和回边B。树边是在移动到未访问顶点时经过的边，从而扩展DFS树。回边是在DFS尝试从当前顶点u访问已访问的相邻顶点v时遇到的，形成连接(u, v) ∈ B。

当遇到回边e???=(u,v)时，子集T ∪ e???恰好包含一个唯一周期C。令w(e)表示……

算法评估

算法的评估在两种不同的测试中进行。首先，使用MATLAB中的代码分析器测量函数在执行中的自时间。这种方法代表了需要基于高级编程语言和双精度数字的离线规划的任务。其次，在微型计算机上进行了测试；具体来说，是一块BeagleBone Black板，配备TI Sitara AM3358BZCZ100 ARM Cortex-A8微处理器，运行Debian 7.11 Linux，使用低级C代码……

结果

初始测试系列——在MATLAB中运行——的结果如图4所示。Prim和Fiedler算法显示出几乎恒定的执行时间——主要归因于MATLAB的专有优化例程——Fiedler算法大约比Prim算法花费一半的时间。相比之下，DFS和Multiplicity算法随着总线数量的增加显示出增加的执行时间，然而始终优于Prim和Fiedler算法。……的总结表明……

讨论

PSA的优势是结构性的而不是计算性的。它在构造上是精确的，其自时间几乎是平坦且紧密分布的——在MATLAB中四分位距为9.42×10??秒，在PIL中为0.024秒。其局限性源于具有O(|V|2)复杂度的相同贪婪结构，这使其在两种环境中都是最慢的方法。

Fiedler测试提供了比二元结果更多的信息，因为λ?量化了候选解与断连的距离，其特征向量识别了最弱的切割。相反……

结论

本研究评估了四种评估电网辐状性的方法，以确定电网优化中最计算效率的方法。基于广泛使用的PSA基线，本研究分析了另一种搜索算法DFS，以及两种图论测试——多重性和Fiedler代数连通性。性能在两种部署环境中进行评估：使用高级软件的离线规划场景以及需要便携式代码的嵌入式现场环境……

CRediT作者贡献声明

Angel Romero-Laguna：写作 – 原稿、软件、形式分析。Rafael Escudero：写作 – 原稿、验证、数据管理。Luis Ibarra：写作 – 审阅与编辑、监督、方法论、概念化。Jesús Daniel Dávalos Soto：资源、调查。Daniel Guillen：写作 – 审阅与编辑、可视化、监督。

利益冲突声明

作者声明他们没有已知的竞争性财务利益或个人关系，这些关系可能影响本文所述的工作。

Angel Romero-Laguna|Rafael Escudero|Luis Ibarra|Jesús Daniel Dávalos Soto|Daniel Guillen