(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111475575.5 (22)申请日 2021.12.0 6 (71)申请人 国网湖北省电力有限公司电力科 学 研究院 地址 430077 湖北省武汉市洪山区徐 东大 街227号 (72)发明人 饶玮　杨帆　蔡超　沈煜　唐泽洋　 胡成奕　崔一铂　杨志淳　 (74)专利代理 机构 武汉楚天专利事务所 421 13 代理人 孔敏 (51)Int.Cl. G06F 30/18(2020.01) G06F 30/20(2020.01) G06F 113/04(2020.01) (54)发明名称 一种基于并行优化的电网子图划分方法及 装置 (57)摘要 本发明提供一种基于并行优化的电网子图 划分装置及方法， 对电网结构进行简化划分， 本 发明将图划分与并行优化联系在一起， 首先根据 电力系统网络拓扑结构， 将电网使用的设备与设 备之间的线路， 作为节点和边， 形成一个天然的 电网拓扑结构图； 然后将给定的电网拓扑图粗略 的划分成一系列的较小的子区域， 再对每个子区 域进行划分， 求得优化解， 最后利用逆向算法将 子区域还原从而得到给定图的一个优化划分。 本 发明将电网设备与连接线路转化为天然的电网 拓扑图， 运用并行优化的多层次划分的方法对电 网结构进行化简分割， 实现了对复杂的电网结构 加以简化， 便于更好的分析和维护电网设备与线 路， 保障电力系统的稳定运行。 权利要求书2页 说明书5页 附图2页 CN 114239198 A 2022.03.25 CN 114239198 A 1.一种基于并行优化的电网子图划分装置， 其特征在于： 包括电网拓扑结构生成器、 电 网图多层次划分器， 所述电网图多层次划分器包括粗化模块、 初始划分模块、 子图划分 效果 检验器及 细化模块； 所述电网拓扑生成器， 用于利用图论知识表示电网子 图网络拓扑结构， 得到不同权重 度的节点模型， 进 而生成电网拓扑 结构图G； 所述粗化模块， 用于在电网拓扑图G上选取点， 与 所有在相邻 近边上的具有最大边权值 的顶点与之进行匹配， 将相关性、 相似性高 的几个顶点V合并成一个端点Vi从而作为粗化图 的一个顶点； 所述初始划分模块， 用于采用对分法对粗化图进行初始图划分， 使得划分后的每个子 图Gi1＝(Vi1,Ei1)包含的顶点数或顶点权值和大致相等， 且割边 最小； 所述子图划分效果检验器， 用于采用子图连接度γ(Vi)检验电网子图划分的效果， 若子 图连接度γ(Vi)未达到预设值， 则返回初始化分阶段； 所述细化模块， 用于将粗化的图映射回原图， 先将划分的粗化图用局部优化方法进行 优化， 再将划分好的电网子图对应的端点映射回电网原图。 2.如权利要求1所述的基于并行优化的电网子图划分装置， 其特征在于： 所述电网拓扑 生成器生成电网拓扑 结构图G具体包括： 简化电网结构， 将馈线的非导线设备近看作节点， 构成节点集V， 将导线看成连接节点 的边， 构成边 集E， 将其 转化为电网拓扑图； 定义电网拓扑图模型G＝(V,E)； 其中， 顶点集合V(G)＝{v1,v2,……,vp}； vi表示电网子图中所有的数据节点； Ei表示电 网子图中所有边， 用aij表示G中vi与vj之间的边数， 定义wij为点vi与vj之间的权重， 如果vi和 vj之间没有相互连接线， 则wij＝0。 3.如权利要求1所述的基于并行优化的电网子图划分装置， 其特征在于： 所述粗化模块 还用于当Vi的邻边有也有聚合顶点Vj时， 比较两个顶点权值大小， 若 则顶点Vj替换 Vi作为粗化图顶点， 由原 始图生成一系列较小的图Gi＝(Vi,Ei)。 4.如权利要求1所述的基于并行优化的电网子图划分装置， 其特征在于： 子图连接度 其中Vi为第i个电网子 图的顶点集合， 为第i个子 图 的割集权重， 用来评估子图与外部顶点间的连接紧密度， 割集权重度 越大， 表明 子图与外部顶点间的连接紧密度越强， 反之越弱； 为第i个子图的顶点权 重度， 与内部顶点紧密程度成正比关系。 5.一种基于并行优化的电网子图划分方法， 其特 征在于包括如下步骤： 步骤1、 利用图论知识表示电网子图网络拓扑结构， 得到不同权重度的节点模型， 进而 生成电网拓扑 结构图G； 步骤2、 对电网拓扑图进行粗 化、 初始划分、 细化的三层划分， 所述 步骤2具体包括： 步骤2.1： 在电网拓扑图G上选取点， 与所有在相邻近边上的具有最大边权值的顶点与 之进行匹配， 将相关性、 相似性高的几个顶点V合 并成一个端点Vi从而作为粗化图的一个顶权　利　要　求　书 1/2 页 2 CN 114239198 A 2点； 步骤2.2： 初始划分， 采用对分法对粗化图进行初始图划分， 使得划分后的每个子图Gi1 ＝(Vi1,Ei1)包含的顶点数或顶点权值和大致相等， 且割边 最小； 步骤2.3： 采用子图连接度γ(Vi)检验电网子图划分的效果， 若子图连接度γ(Vi)未达 到预设值， 则返回初始化分阶段； 步骤2.4： 将粗化的图映射回原图， 先将划分的粗化图用局部优化方法进行优化， 再用 逆向算法将划分好的电网子图对应的端点映射回电网原图。 6.如权利要求5所述的基于并行优化的 电网子图划分方法， 其特征在于： 所述步骤1包 括： 步骤1.1： 简化电网结构， 将设备看作图的端点， 将设备间的线路看作边， 将其转化为电 网拓扑图； 进入步骤2； 步骤1.2： 定义电网拓扑图模型G＝(V,E)； 其中， 顶点集合V(G)＝{v1,v2,……,vp}； vi表示电网子图中所有的数据节点； Ei表示电 网子图中所有边， 用aij表示G中vi与vj之间的边数， 定义wij为点vi与vj之间的权重， 如果vi和 vj之间没有相互连接线， 则wij＝0。 7.如权利要求5所述的基于并行优化的电网子图划分方法， 其特征在于： 所述步骤2.1 还包括： 如果Vi的邻边有也有聚合顶点Vj， 比较两个顶点权值大小， 若 则顶点Vj替 换Vi作为粗化图顶点， 由原 始图生成一系列较小的图Gi＝(Vi,Ei)。 8.如权利要求5所述的基于并行优化的电网子图划分方法， 其特征在于： 子图连接度 其中Vi为第i个电网子图的顶点集合， 为第i个子图 的割集权重， 用来评估子图与外部顶点间的连接紧密度， 割集权重度 越大， 表明 子图与外部顶点间的连接紧密度越强， 反之越弱； 为第i个子图的顶点权 重度， 与内部顶点紧密程度成正比关系。权　利　要　求　书 2/2 页 3 CN 114239198 A 3