A Multi-Agent Approach to Feeder Reconfiguration

随着电力行业竞争的加剧，从经济和安全的角度来看，配电自动化肯定会变得越来越有吸引力。变压器馈线重新配置和馈线负载平衡是避免停电和快速恢复的有效控制措施。负载平衡在今天尤为重要，因为在大多数情况下，许多这些设备（变压器和馈线）已经使用了几十年。这些老化设施的更换甚至加固是困难的，因为由于竞争而强调降低成本。负载平衡将有助于减少这些设备的故障，从而防止停机。馈线重构是一个具有多目标冲突和非线性约束的组合优化问题。毫不奇怪，它仍然是一个活跃的研究领域，因为存在许多局部最优，其目的是找到反映目标之间权衡的全局最优帕累托曲面。因此，我们不仅仅是在寻找一个全局最优解（它本身很难有效地获得），而是在寻找形成帕累托曲面的许多这样的解。人们提出了许多解决办法，但似乎没有一个能完全胜任这项任务。启发式是不可避免的；问题是：是哪些？我们提出的方法是基于以下观察：多个启发式和算法一起工作（并行）可能比其中任何一个单独工作更有效。我们称每个算法/启发式为一个代理。在这种情况下，agent一词指的是各个算法相互“合作”的能力，从而能够协同增强它们各自独立的能力。这种方法已被证明对其他组合优化问题有用，包括电力系统领域的一些问题，因此，有理由相信它也将成功地用于馈线重新配置。我们建议证明我们的多智能体方法能够获得该问题的Pareto最优解集，其计算量可用于在线运营规划目的（如果不是实时的）。我们还建议开发一个基于马尔可夫链的理论框架，用于分析我们的多智能体方法的计算行为，以期深入了解其性能，其在大型配电系统中的可扩展性，以及其在电力系统中类似组合问题的适用性。三个结果特别令人感兴趣：1)随着时间的推移，存储器中解向全局最优解的“收敛”；2)随着一个接一个地添加代理，最重要目标的值向全局最优值的减少，3)随着添加更多处理器而获得的“加速”（总体执行时间的减少）（我们期望近似线性的加速）。寻找最优馈线重构策略是一个在线环境下较难解决的多目标组合优化问题。提出的多智能体方法有可能提供一种有效的方法，以一种协同的方式结合各种启发式方法，从而获得冲突目标的帕累托曲面。通过提高整体求解质量和计算时间，该方法将大大提高馈线重构的研究和实践水平。此外，由于该方法本质上是并行的，因此它可以最大限度地利用分布控制中心中日益普及的分布式计算平台。多智能体方法和马尔可夫链模型的适用性超出了馈线重构问题。类似的方法对其他电力系统问题的效用已在文献中报道。这项研究将为回答以下重要问题的理论和实验框架奠定基础：考虑到有各种算法和启发式来解决这个难题，将它们结合起来的最佳方法是什么？例如，提取出比任何一个单独使用都更好的性能？成功地回答这个问题，对于推进电力工业中解决组合问题的实践具有根本的价值。＊＊＊

ECS-9629273 Ramesh As competition in the power industry intensifies, distribution automation is sure to become increasingly attractive both from the economic and from the security point of view. Feeder reconfiguration for transformer and feeder load balancing is an effective control action both for avoiding outages and for faster restoration. Load balancing is particularly important today since many of these devices (transformers and feeders) have been in service for many decades, in most cases. Replacement or even reinforcement of these aging facilities is difficult due to the emphasis on cost reduction due to competition. Load balancing will help minimize failures of these devices thereby preventing outages. Feeder reconfiguration is a combinatorial optimization problem with multiple conflicting objectives and nonlinear constraints. Not surprisingly, it continues to be an active research area since many local optima exist and the aim is to find the globally optimal Pareto surface that reflects the tradeoff between the objectives. So, we are not just looking for one global optimum (which itself would be difficult to obtain efficiently), but we are looking for many such solutions that form the Pareto surface. Many solution approaches have been suggested, but none appears to be totally up to the task. Heuristics are inevitable; the question is: which ones? Our proposed approach is based on this observation: multiple heuristics and algorithms working together (in parallel) might be more effective than any one of them working in isolation. We call each individual algorithm/heuristic, an agent. In this context, the term agent refers to the ability of the individual algorithms to "cooperate" with each other, enabling a synergistic enhancement of their isolated capabilities. Such an approach has proved useful for other combinatorial optimization problems, including some in the power systems area, and hence, there is reason to believe that it will be successful for feeder reconfiguration as well. We propose to demonstrate that our multi-agent approach is able to obtain the Pareto set of optimal solutions for this problem with a computational effort acceptable for online operational planning purposes (if not real-time). We also propose to develop a theoretical framework, based on Markov chains, for analyzing the computational behavior of our multi-agent approach with a view towards providing insights into its performance, its scalability to large distribution systems, and its applicability to similar combinatorial problems in power systems. Three results are of particular interest: 1) the "convergence" of the solutions in the memory towards the global optimum as time progresses; 2) the decrease in the value of the most important objective towards the global optimum as agents are added one by one, 3) the "speedup" (decrease in overall execution time) obtained as more processors are added (we expect a near-linear speedup). Finding the optimal feeder reconfiguration strategy is a multi-objective combinatorial optimization problem that is difficult to solve in the online environment. The proposed multi-agent approach has the potential of offering an effective way of combining, various heuristics in a synergistic fashion so as to obtain the Pareto surface for the conflicting objectives. By improving both the overall solution quality and the computational time, the approach will significantly advance the state-of-the-art in feeder reconfiguration research and practice. Further, since the approach is inherently parallel, it can take maximal advantage of the distributed computing platforms that are becoming commonplace in distribution control centers. The applicability of the multi-agent approach and of the Markov chain model extend beyond the feeder reconfiguration problem. The utility of similar approaches to a couple of other power system problems has been reported in the literature. This proposed research will lay the foundations for a theoretical and an experimental framework for answering the important question: Given that there are various algorithms and heuristics for solving this difficult problem, what is the best approach for combining them such as to extract a better performance than any of them is capable of, in isolation? Answering this question successfully has fundamental value for advancing the practice of solving combinatorial problems in the power industry. ***