(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210734775.6 (22)申请日 2022.06.27 (71)申请人 合肥工业大 学 地址 230009 安徽省合肥市包河区屯溪路 193号 (72)发明人 张大波　欧阳菠　郭怀新　马英浩　 杨贺钧　 (74)专利代理 机构 合肥和瑞知识产权代理事务 所(普通合伙) 34118 专利代理师 王挺 (51)Int.Cl. G06F 16/532(2019.01) G06V 10/74(2022.01) (54)发明名称 一种反时限交互式海量电网拓扑相似度快 速排序方法 (57)摘要 本发明公开了一种反时限交互式海量电网 拓扑相似度快速排序方法， 将 两个电网拓扑图之 间的编辑距离作为该两个电网拓扑图之间的相 似度指标， 通过一系 列编辑操作使得电网拓扑图 A向电网拓 扑图B同构， 该一系列编辑操作的编辑 代价值之和称为编辑路径的路径代 价值， 通过路 径搜索寻找路径代价值最小的编辑路径即最优 编辑路径， 将该最优编辑路径对应的最小路径代 价值作为电网拓扑图A与电网拓扑图B之间的编 辑距离； 利用两个电网拓扑图之间的编辑距离衡 量电网拓 扑图相似度， 能够实现电网拓扑图的相 似度比较与排序， 能够从海量电网拓扑中找出相 似度最高的电网拓扑， 从而为电网新设备启动方 案编制、 电力系统故障后恢复方案制定等领域提 供参考。 权利要求书2页 说明书12页 附图4页 CN 115329117 A 2022.11.11 CN 115329117 A 1.一种反时限交 互式海量电网拓扑相似度快速排序方法， 其特 征在于， 包括以下步骤： S1， 定义相似度指标： 将两个电网拓扑图之间的编辑距离作为该两个电网拓扑图之间 的相似度指标， 其中， 电网拓扑图A与电网拓扑图B之间的编辑距离d(A,B)越小， 则电网拓扑 图A与电网拓扑图B的相似度越高； 电网拓扑图A与电网拓扑图B之间的编辑距离d(A,B)的求 解方式如下 所示： 对于电网拓扑图A与电网拓扑图B， 通过一系列编辑操作， 使得电网拓扑图A向电网拓扑 图B同构； 该一系列编辑操作组成的序列称为编辑路径， 每种编辑操作对应一个编辑代价值， 该 一系列编辑操作的编辑代价值之和称为编辑路径的路径代价值； 通过路径搜索寻找路径代 价值最小的编辑路径即最优编辑路径， 将该最优编辑路径对应的最小路径代价值作为电网 拓扑图A向电网拓扑图B同构的编辑距离， 即电网拓扑图A与电网拓扑图B之间的编辑距离d (A,B)； S2， 根据相似度 指标， 求取电网拓扑图q与电网拓扑图库G＝{gi|i＝1,2…n}中的各个电 网拓扑图的相似度排序， 其中， gi表示电网拓扑图库G中的第i个电网拓扑图， i＝1,2 …n， 即 电网拓扑图库G中共有n个电网拓扑图； 具体过程如下 所示： 将电网拓扑图q与已建立的电网拓扑图库G中的各个电网拓扑图逐个对比， 分别求取电 网拓扑图q向各个电网拓扑图同构的编辑距离， 按照编辑距离从小到大的顺序进 行排序， 得 到电网拓扑图q与电网拓扑图库G中的各个电网拓扑图的相似度排序， 且为 从高到低的相似 度排序。 2.根据权利要求1所述的一种反时限交互式海量电网拓扑相似度快速排序方法， 其特 征在于， 步骤S2中， 求取电网拓扑图q与电网拓扑图库G＝{gi|i＝1,2…n}中的各个电网拓 扑图的相似度排序， 具体还可采用如下 方式： S21， 进行第k次迭代， 第k次迭代的搜索时间tk： tk＝k·Δt 其中， k表示迭代次数， k ＝1， 2， 3. ..； Δt为每次迭代的时间增量， Δt为定值； S22， 在第k次迭代中， 分别求解第k次迭代时电网拓扑图q与电网拓扑库G中各个电网拓 扑图之间的编辑距离； 其中， 将电网拓 扑图q与电网拓 扑库G中的第i个电网拓扑图gi对比， 在第k次迭代的搜索 时间tk内进行路径搜索， 遍历多条编辑路径寻找路径代价值最小的编辑路径， 将最小的路 径代价值作为第k次迭代时电网拓扑图q向第i个电网拓扑图gi同构的编辑距离， 即第k次迭 代时电网拓扑图q与第i个电网拓扑图gi之间的编辑距离dk(q,gi)i＝1,2…n； S23， 将第k次迭代时电网拓扑图q与电网拓扑库G中各个电网拓扑图之间的编辑距离， 按照从小到大的顺序进行排序， 得到第k次迭代 时电网拓扑图q与电网拓扑图库G中的各个 电网拓扑图的相似度排序， 且为相似度从高到低的排序； S24， 判断k是否大于1， 若是， 则进行步骤S25， 若否， 则将k的值加1， 跳转步骤S21直接进 行下一次迭代； S25， 计算第k次迭代的编辑距离横向相似度比较系数hk： 权　利　要　求　书 1/2 页 2 CN 115329117 A 2其中， sortk(gi)表示第k次迭代时电网拓扑 图q与第i个电网拓扑图gi的相似度排序序 号， min(dk(q,G))表示第k次迭代时电网拓扑图q与电网拓扑库G中所有电网拓扑图之间编 辑距离的最小值； α 为横向相似度比较的松弛因子； S26， 计算第k次迭代的编辑距离纵向时间比较系数zk： 其中， dk‑1(q,gi)表示第k ‑1次迭代即上一次迭代时电网拓扑图q与第i个电网拓扑图gi 之间的编辑距离； β 为纵向时间比较的松弛因子； S27， 计算第k次迭代的反时限交 互指标值 ITIk： 其中， λ为时间松弛因子， tk为第k次迭代的搜索时间； S28， 判断第k次迭代的反时限交互指标值ITIk是否小于精度阈值ε， 以及判断当前迭代 次数k是否大于最大迭代次数 K； 若第k次迭代的反时限交互指标值ITIk小于精度阈值ε， 或者， 当前迭代次数k大于最大 迭代次数K， 则输出第k次迭代的相似度排序， 得到电网拓扑图q与电网拓扑图库G中的各个 电网拓扑图的最终相似度排序； 否则， 将k的值加 1， 跳转步骤S21直接进行下一次迭代， 直至反时限交互指标值小于精 度阈值 ε或迭代次数达到最大迭代次数K， 得到电网拓扑图q与电网拓扑图库G中的各个电网 拓扑图的最终相似度排序。 3.根据权利要求1或2所述的一种反时 限交互式海量电网拓扑相似度快速排序方法， 其 特征在于， 编辑操作包括： 节点删除， 边删除， 节点插入， 边插入， 节点标签变换， 边标签变 换。权　利　要　求　书 2/2 页 3 CN 115329117 A 3