基于回溯思想改进GN算法的电磁环网自动分区方法

焦慧明 ，刘天琪 ，苏学能 ，王 彪 ，白懿鹏

（1.四川大学 电气信息学院，四川 成都 610065；2.国网四川省电力公司电力科学研究院，四川 成都 610072）

0 引言

电力系统安全稳定导则［1］提出：随着高一级电压电网的建设，下级电压电网应逐步实现分区运行，相邻分区之间保持互为备用，以避免和消除影响电网安全稳定的不同电压等级的电磁环网。目前已有很多关于电磁环网分区运行的研究，但大多依据工程经验来制定分区方案［2-5］，相对主观，且方案制定周期较长。

复杂网络理论在电力系统中的应用日趋成熟［6］，已有学者从复杂网络的视角研究电网分区方案的制定［7］。复杂网络中的 GN（Girvan-Newman）算法［8］作为社区发现方面的开创性算法，是一种典型的分裂算法。文献［9］在结合GN算法的基础上，提出了一种基于社团结构特性量化分析的电磁环网分区方法。该方法依据定量表征线路薄弱程度的综合边介数指标，对电磁环网予以解环。然而，该方法在解环过程中忽略了电磁环网分区需计及的相关原则，如具有2台主变的枢纽变电站需“手拉手”运行和解环后各分区不能存在3座及以上站点的串供结构等；此外，由于GN算法是不断移除当前综合边介数最大的边，直接运用会导致指定分区数目时只有一种分区方案，而此时该方案还会受到分区原则的制约，从而有可能导致无法获得可行分区方案。针对分区方案的评估方法已有模糊评价模型［10］、多层次模糊评价模型［11-12］以及层次分析法［13］等。此外，主成分分析PCA（Principal Component Analysis）法［14］利用降维的思想，降低指标集维数，同时保留指标集中对方差贡献较大的指标，可有效确定各指标对方案的贡献，客观评价方案的优劣。

鉴于上述分析，在文献［9］的基础上，提出一种基于回溯思想改进GN算法的电磁环网分区方法。首先，该方法分别采用深度优先搜索DFS（Depth-First Search）算法［15］和图论节点度检测方式，实现枢纽变电站运行方式辨识和3台及以上串供结构的检测及修正；进一步，为充分发挥GN算法的优势以扩展分区方案的多样性，采用回溯思想改进GN算法的分区过程。其次，为提高分区方案的校验效率，提出结合进程连接PSD-BPA的方式以实现分区方案的静态安全分析和短路电流自动校验，从而获取校验成功方案的校验指标；并将此指标与衡量分区划分结构合理性的模块度相结合，以作为评估指标集；进而，用PCA法以该指标集衡量分区方案的优劣。最后，将所提方法应用于某实际地区500 kV/220 kV电磁环网的解环，结果表明，该方法可有效实现电磁环网的自动分区，并确保所得方案满足实际电网分区原则。

1 GN算法用于解环分区的缺陷及解决措施

1.1 GN算法用于解环分区的缺陷

GN算法属于分裂层次聚类算法，通过移除综合边介数最大的边来划分隐藏在网络中的不同社团，并将模块度函数［16］作为网络划分的衡量标准。但在电磁环网分区的应用中，没有考虑电磁环网分区时应满足的原则。

以500 kV/220 kV电磁环网为例，220 kV侧环网分区的方案应综合考虑电网结构合理、调度运行灵活和投资规模适当等因素，解环后的供电区需满足2个原则：原则1，具有2台主变的枢纽变电站“手拉手”运行，其中枢纽变电站指500 kV变电站；原则2，为保障分区的供电可靠性，规定不超过3座及以上的220 kV站点串供运行。

因此，为使得到的分区方案具有实际意义，需对GN算法进行改造完善。

1.2 解决措施

1.2.1 采用DFS辨识枢纽变电站的运行方式

针对上述原则1，提出采用DFS辨识枢纽变电站的运行方式。通过DFS来获取当前方案的分区情况，进而辨识500 kV变电站的运行方式。主要步骤如下：

a.获取表征电网220 kV站点的邻接关系矩阵和断线割集；

b.采用DFS判断该方案是否形成新的分区，若是，则获取其分区数目及其包含的站点；

c.遍历方案下的所有分区，获取各分区中与枢纽变电站直接相连的站点；

d.由步骤c获取各分区下的枢纽变电站数目，若数目小于2，则进一步判断是否为2台主变的枢纽变电站，若是，则不满足要求。

1.2.2 串供结构的检测

针对上述原则2，提出基于图论节点度概念检测串供结构的方法。

图论中某节点的节点度定义为与该节点相连的节点数目。如图1所示，引入图论中节点度的概念，串供结构末端站点的节点度为1，记为A站，与A站相连的记为B站。假定存在3台所组成的串供结构，则B站的节点度为2，B站除了与A站相连，还应与另一站点相连，记为C站。串供结构辨识方法主要判断由节点度为1的站点开始，是否连续存在2个及以上相邻站的节点度为2，若是，则存在串供结构。

图1 串供结构的辨识Fig.1 Identification of serial-supplying structure

1.2.3 串供结构的修正

若存在3座及以上220 kV站点的串供结构，则需对其进行修正。此时方案中的解环断线需进行调整，以消除3座及以上220 kV站点的串供结构，如图2所示。

图2 串供结构的修正Fig.2 Correction of serial-supplying structure

串供结构的修正主要步骤如下：

a.获取串供结构列表中节点度为1的A站；

b.依据分区方案断线信息，得到A站对应的断线编号n；

c.遍历串供结构列表中的站点，从尾部往前推移得到线路编号n+1，替代断线信息中的线路n；

d.结合串供结构检测方法，判断修正后的方案是否还存在3座及以上220 kV站点的串供结构，若存在，则需继续修正。

1.3 计及电磁环网分区原则的GN算法流程

通过采用DFS辨识枢纽变电站的运行方式和3台及以上串供结构的检测及修正方法，完善GN算法的执行过程，提出计及电磁环网分区原则的GN算法，以便获得具有实际意义的分区方案。计及电磁环网分区原则的GN算法流程如图3所示。

图3 计及电磁环网分区原则的GN算法流程图Fig.3 Flowchart of GN algorithm considering partitioning principles of electromagnetic loop network

2 基于回溯思想改进GN算法的自动分区方法及方案评估

2.1 基于回溯思想改进的GN算法

通过计及电磁环网分区原则的GN算法虽然保证了所得方案满足分区原则，但由于GN算法的执行过程是不断地移除当前综合边介数最大的边，导致指定分区数目时只有一种分区方案，而此时该方案还会受到分区原则的制约，可能导致无法得到可行分区方案。

为充分发挥GN算法利用综合边介数信息实现分区的优势，进一步扩展分区方案的多样性，提出基于回溯思想改进GN算法的分区方法。其流程如图4所示。该方法首先依据GN算法获取全网边介数信息；然后由工程经验指定最大可断线数目得到断线割集；最后对断线割集并行从头部、尾部进行回溯。其中将头部闭合线路过程（图4中①部分）和尾部闭合线路过程（图4中②部分）分别放在2个不同的进程中并行执行，以提高运算效率。

图4 基于回溯思想的改进GN算法流程图Fig.4 Flowchart of GN algorithm improved with backtracking concept

2.2 方案评估模型

2.2.1 方案校验及指标

500 kV/220 kV电磁环网分区的目的是为了降低因500 kV电网结构的加强而导致的220 kV电网的单相、三相短路电流水平，以保证电网运行的稳定性和供电可靠性。改进GN算法可得到更多的分区方案，传统的方案校验难以自动批量校验方案的各项指标。为提高校验方案的效率，进一步验证方案的合理性，从而自动甄选出满足供电可靠性和短路电流裕度的方案，提出结合进程连接PSD-BPA的方式，以实现分区方案的静态安全分析和短路电流校验，并从中获取校验成功方案的校验指标。其中，校验指标分为2类。

a.供电负荷能力。具体指通过母线“N-1”、主变“N-1”、线路“N-1”、同塔“N-2”（同塔率大于 70%）等静态安全分析，获取各分区的制约故障信息和实际供电负荷能力的信息，并以 K1、K2、K3、K4分别表示对应指标。以某分区方案的母线“N-1”指标K1为例，解环后形成m个分区，则该方案的K1表示为：

其中，Pi.base（i=1，2，…，m）为各分区的基准负荷；Pi1（i=1，2，…，m）为各分区母线“N-1”的校验指标。

b.短路电流校验。具体指与枢纽变电站直接连接的220 kV母线和部分开关遮断容量为40 kA的220 kV变电站220 kV母线的单相、三相短路电流的校验。需说明的是，当枢纽变电站母线的短路电流不超标时，电网其他母线的电流一般也不会超标。以K5和K6分别表示与枢纽变电站直接相连的220 kV母线的单相短路电流裕度指标及其三相短路电流裕度指标；以K7和K8分别表示开关遮断容量为40 kA的220 kV变电站220 kV母线的单相短路电流裕度指标及其三相短路电流裕度指标。以枢纽变电站直接相连220 kV母线的单相短路电流裕度指标为例，假定有n座枢纽变电站，则该方案K5表示为：

其中，Ii.base（i=1，2，…，n）为各站断路器的遮断容量阈值；Iis（i=1，2，…，n）为采取解环措施后各站的实际单相短路电流值。

2.2.2 方案评估

参照文献［9］定义模块度指标 Q［16］，以客观合理地表征分区划分结构的合理性，考虑到电力网络的线路长度及参数特性，选取支路导纳模值作为边权重，即考虑边权重模块度指标越大，说明分区内部的连接紧密程度越高，则电力网络的社团结构划分得越好。假定分区数目为l，则：

其中，e 为一个 l×l阶的对称矩阵；eii（1≤i≤l）为连接分区i内节点之间的边与初始网络所有边的比值；Tr（e）为连接同一分区内部节点的边与网络所有边之间的比值；ai为连接分区i的节点的边与初始网络所有边的比值。

由8个校验指标和模块度指标Q共同构成评估指标集，并在此基础上采用PCA法［14］处理该指标集建立评估模型。

首先，获取待评估方案每一指标的均值和方差，其中，短路电流指标以其裕度值表示，使评估指标集内所有指标均为正向指标，并使用z-score标准化方法［17］做均一化处理，以消除量纲的影响。经过处理的数据符合标准正态分布，其转换函数为：

其中，μ为所有样本数据的均值；σ为所有样本数据的标准差。

然后，获取其方差矩阵，包括自方差和协方差，通过对协方差矩阵进行特征分解，以得出指标集的主成分（即特征向量）与对应的权值（即特征值），进而降低指标集的维数，同时保持指标集中对方差贡献最大的指标。

最后，形成主成分矩阵及综合评价指标，根据综合评价指标得到最优的分区方案。

2.3 基于回溯思想改进GN算法的电磁环网自动分区方法流程

结合1.3节、2.1节、2.2节，提出基于回溯思想改进GN算法的电磁环网自动分区方法，其流程如图5所示。

图5 基于回溯思想改进GN算法的电磁环网自动分区方法流程图Fig.5 Flowchart of automatic electromagnetic loop network partitioning algorithm based on backtracking-improved GN algorithm

3 算例结果与分析

3.1 算例1

以某地区的500 kV/220 kV电磁环网为例验证本文方法的可行性和有效性。该地区电网包含60座220 kV变电站，其中有5座与500 kV变电站直接联系，称作枢纽变电站，分别记为A—E；其余220 kV变电站分别编号为1—55。值得注意的是，由于该地区500 kV变电站的主变数目均为2台，分区时需要与其他500 kV变电站“手拉手”运行。该地区解环前的电网拓扑如图6所示。

图6 电网拓扑图Fig.6 Topology of power grid

表1为分区前部分变电站220 kV母线处的短路电流水平。其中，与枢纽变电站直接联系的220 kV母线的断路器开关遮断容量为50 kA，其余220 kV变电站的220 kV母线的断路器开关遮断容量为40 kA。由表1可以看出，枢纽变电站220 kV母线的单相、三相短路电流普遍超标。此外，21站220 kV母线的三相短路电流也超过了断路器的遮断容量。因此，有必要对该地区500 kV/220 kV电磁环网的220 kV环网进行解环，从而达到抑制短路电流水平的目的。

表1 分区前部分站点220 kV母线处的短路电流Table 1 220 kV bus short circuit currents of some substations before partition

3.1.1 GN算法获得的分区方案

使用改进前的GN算法对其进行分区的过程中，依据工程经验设定最大可断线路数目为10，可由GN算法得出前10条断线的综合边介数信息，如表2所示。在断线过程执行到第6条线路，即24－26时，会形成3个分区，其中分区1包含A站与B站，分区2仅包含C站，分区3包含D站与E站，如图7所示。首先该分区中具有2台主变的500 kV变电站没有与其他500 kV变电站“手拉手”运行，另外在分区2中形成了C站、34站、35站、26站的串供结构。由此说明改进前的GN算法没能获得可行的分区方案。

表2 综合边介数Table 2 Comprehensive edge betweenness

3.1.2 改进GN算法获得的分区方案

用基于回溯思想改进GN算法进行电磁环网自动分区，不仅通过1.3节的方法保证了分区方案满足电磁环网的分区原则，并且通过2.1节提出的回溯思想扩展了解的多样性，依据工程经验设定最大可断线路数目为10，得出的分区方案如表3所示。采用2.2.1节所提方法对方案进行校验，得出方案6的母线“N-1”和线路“N-1”指标校验不通过，该方案无效。

图7 基于GN算法获取实际电网的分区方案Fig.7 A practical network partitioning scheme by GN algorithm

表3 220 kV环网分区方案Table 3 Partitioning schemes of 220 kV loop network

在上述分区方案中，可以看出改进GN算法相比GN算法能够获得更多的分区方案，并且大多数方案均可通过静态安全分析和短路电流校验。

为得到最优分区方案，由2.2.1节所提方法处理后的静态安全分析指标、短路电流指标以及模块度指标Q，共计9个指标，共同构成分区方案优劣评估指标集。其中方案1—5的模块度指标Q分别为0.4247、0.4388、0.4050、0.4422 和 0.4300。

采用PCA法并设置主成分分量为85%，可得9个指标的分量比率和累积率，如图8所示。进而形成反映方案优劣的综合评价指标值，如表4所示。结果表明，方案2的综合评价指标优于其他方案，为该算例的最优分区方案。其余分区方案评估排名依次为方案3、方案1、方案5和方案4。

图8 各指标分量占全分量的比率和累积率Fig.8 Proportion of each index component and accumulative proportion

表4 综合评价指标值Table 4 Comprehensive evaluation index

3.2 算例2

为了进一步验证方法的有效性，本文还以该地区未来新投入2座500 kV变电站后的电网为例进行类似分析并给出相应分区方案。该电网拓扑图如图9所示，共67座220 kV变电站，其中7座枢纽变电站分别编号为A—F，其他变电站分别编号为1—60。由于A站对应的500 kV枢纽变电站包含3台500 kV主变，因此可独立供电一片区域。

图9 电网拓扑图Fig.9 Topology of power grid

基于回溯思想改进的GN算法可得经校验合格的有效分区方案共4个，使用2.2节所提评估方法并设置主成分分量为85%，可得方案1的综合评价指标值为0.8388，为最优分区方案，具体方案信息如表5所示。

表5 220 kV环网分区方案Table 5 Partitioning schemes of 220 kV loop network

4 结语

本文提出了一种基于回溯思想改进GN算法的电磁环网自动分区方法。该方法首先针对GN算法的应用缺陷，提出计及电磁环网分区原则的GN算法；同时，为充分发挥GN算法的优势，提出基于回溯思想的改进GN算法，以扩展可行分区方案的多样性；而且，为解决人工校验所存在的弊端，结合进程连接PSD-BPA的方式自动对所得方案进行静态安全分析和短路电流校验；并将得到的指标与模块度指标相结合，构成衡量方案优劣的评估指标集；进而采用PCA法对该指标集进行处理，以评估出最优分区方案。最后，将本文所提方法应用于某地区500 kV/220 kV电磁环网，结果表明，该方法可有效实现电磁环网自动分区，并确保所得方案满足实际电网分区原则。

由于GN算法每计算一次最大综合边介数信息都需遍历网络中所有的站点，在网络规模大到一定程度时，其时间成本将显著提高，因此该算法在时间效率上尚有一定的局限性，有待进一步研究。

参考文献：

［1］电力行业电网运行与控制标准化技术委员会.电力系统安全稳定导则：DL 755—2001［S］.北京：中华人民共和国国家经济贸易委员会：2001.

［2］侯春青，郑惠萍.2005年山西中南部500 kV及220 kV电网的电磁环网运行方式研究［J］.电网技术，2005，29（10）：80-84.HOU Chunqing，ZHENG Huiping.Research on parallel operation of 500 kV and 220 kV power networks in south and central part of Shanxi Power Grid in 2005［J］.Power System Technology，2005，29（10）：80-84.

［3］张祖平，范明天，周莉梅.城市电网电磁环网的解环问题研究［J］.电网技术，2008，32（19）：42-44.ZHANG Zuping，FAN Mingtian，ZHOU Limei.Research of breaking up electromagnetic ring in urban power network［J］.Power System Technology，2008，32（19）：42-44.

［4］孔涛，王洪涛，刘玉田，等.500 kV-220 kV电磁环网开环研究［J］.电力自动化设备，2003，23（12）：13-16.KONG Tao，WANG Hongtao，LIU Yutian，et al.Research on untying 500 /220 kV electro-magnetic loop network［J］.Electric Power Automation Equipment，2003，23（12）：13-16.

［5］潘炜，刘文颖，杨以涵，等.电磁环网条件下西北750 kV电网运行方式的研究［J］.电网技术，2007，31（15）：33-38.PAN Wei，LIU Wenying，YANG Yihan，etal.Research on operating modes of 750 kV Northwest China Power Grid electromagnetically coupled with 330 kV power grid［J］.Power System Technology，2007，31（15）：33-38.

［6］魏震波.复杂网络社区结构及其在电网分析中的应用研究综述［J］.中国电机工程学报，2015，35（7）：1567-1577.WEI Zhenbo.Overview of complex networks community structure and its applications in electric powernetwork analysis［J］.Proceedings of the CSEE，2015，35（7）：1567-1577.

［7］倪向萍，阮前途，梅生伟，等.基于复杂网络理论的无功分区算法及其在上海电网中的应用［J］.电网技术，2007，31（9）：6-12.NI Xiangping，RUAN Qiantu，MEI Shengwei，et al.A new network partitioning algorithm based on complex network theory and its application in Shanghai Power Grid［J］.Power System Technology，2007，31（9）：6-12.

［8］GIRVAN M，NEWMAN M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences，2002，99（12）：7821-7826.

［9］杨冬，刘玉田.基于网络社团结构特性量化分析的电磁环网分区方法［J］.电力系统自动化，2013，37（21）：66-71.YANG Dong，LIU Yutian.A new method for electromagnetic loop partitioning based on quantitative analysis ofnetwork community structure characteristics［J］.Automation of Electric Power Systems，2013，37（21）：66-71.

［10］叶华，刘玉田，牛新生.500 kV-220 kV电磁环网开环方案模糊综合评价［J］.电力自动化设备，2006，26（7）：1-5.YE Hua，LIU Yutian，NIU Xinsheng.Fuzzy comprehensive evaluation of opening schemes for 500 kV-220 kV electromagnetic loop［J］.Electric Power Automation Equipment，2006，26（7）：1-5.

［11］于会泉.电网短路电流限制措施的优化配置研究［D］.北京：华北电力大学，2011.YU Huiquan.Research on the optimization strategy of shortcircuit current limiting mehods for power networks［D］.Beijing：North China Power Electric University，2011.

［12］王佳明，刘文颖，李群炬，等.基于多层次模糊评价模型的短路电流限制措施优化配置［J］.电网技术，2011，35（11）：125-129.WANG Jiaming，LIU Wenying，LI Qunju，et al.Optimal configuration of short-circuit current limitation measures based on multilevel fuzzy comprehensive evaluation model［J］.Power System Technology，2011，35（11）：125-129.

［13］张东妮.电磁环网解环方案综合评价研究［D］.重庆：重庆大学，2011.ZHANG Dongni.Study of comprehensive evaluation in unlocking the electromagnetic loop network［D］.Chongqing：Chongqing University，2011.

［14］聂宏展，聂耸，乔怡，等.基于主成分分析法的输电网规划方案综合决策［J］.电网技术，2010，34（6）：134-138.NIE Hongzhan，NIE Song，QIAO Yi，et al.Comprehensive decision-making of alternative transmission network planning based on principal component analysis［J］.Power System Technology，2010，34（6）：134-138.

［15］THOMAS H C，CHARLES E L，RONALD L R，et al.Introduction to algorithms［M］.3rd ed.London，UK：the MIT Press，2009：594-611.

［16］NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69（2）：026113.

［17］徐泽水.不确定多属性决策方法及应用［M］.北京：清华大学出版社，2004：26-27.