A Multi-Agent Approach to Feeder Reconfiguration

ECS-9629273 RAMESH随着电力行业竞争的加剧，无论从经济角度还是从安全角度来看，配电自动化肯定会变得越来越有吸引力。对于变压器和馈线负载平衡的馈线重新配置是避免停电和更快恢复的有效控制措施。负载平衡在今天尤其重要，因为在大多数情况下，这些设备(变压器和馈线)中的许多已经使用了几十年。由于竞争对降低成本的强调，更换甚至加固这些老化的设施是困难的。负载平衡将有助于最大限度地减少这些设备的故障，从而防止停机。馈线重构是一个具有多个相互冲突的目标和非线性约束的组合优化问题。并不令人惊讶的是，它仍然是一个活跃的研究领域，因为存在许多局部最优，其目标是找到反映目标之间权衡的全局最优帕累托曲面。因此，我们不仅在寻找一个全局最优解(这本身很难有效地获得)，而且我们正在寻找形成帕累托曲面的许多这样的解。已经提出了许多解决办法，但似乎没有一个完全能胜任这项任务。试探法是不可避免的；问题是：哪些是试探法？我们提出的方法基于这样的观察：多个启发式算法和算法一起工作(并行)可能比它们中的任何一个单独工作更有效。我们称每个单独的算法/启发式为一个代理。在这种情况下，术语代理指的是各个算法相互“合作”的能力，使它们各自独立的能力能够协同增强。这种方法已经被证明对其他组合优化问题是有用的，包括电力系统领域的一些问题，因此，有理由相信它也将成功地用于馈线重构。我们建议证明我们的多智能体方法能够获得该问题的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. ***