Deep Reinforcement Learning Based on Greed for the Critical Cross-Section Identification Problem

The critical cross-section identification problem (CCIP) presents a significant and highly challenging issue in power grid analysis, aiming to identify a partition of the graph into two disjoint cuts that maximize the total weight of the cut. Traditionally, critical cross-sections have been determined through manual experience or mechanistic analysis, and effective intelligent methods to address these issues are lacking. Therefore, we propose a deep reinforcement learning framework based on a greedy approach (DEER) to solve the CCIP problem. Initially, proven to be NP-hard, a greedy vertex merging approach is proposed that enables the acquisition of all CCIP solutions through vertex merging. To prevent the greedy algorithm from converging to local optima, a deep reinforcement learning (DRL) framework combined with vertex marking is proposed to simulate the Markov decision process of vertex merging. Through training the DRL model, repetitive searches for vertex marking can be effectively avoided. Furthermore, the greedy algorithm can be augmented with genetic algorithms to address CCIP. Extensive experiments demonstrate the effectiveness of the proposed methods in addressing CCIP.