一种基于动态规划算法的电网专题图布局方法

摘要

本发明公开了一种基于动态规划算法的电网专题图布局方法，其特征在于，包括如下步骤：步骤1、根据电力系统的空间数据，构建基于单线图的环网拓扑关系模型；步骤2、根据构建的拓扑关系模型、子图档的数量N，构建一个由N个顶点构成的连通图和一个N*N的邻接矩阵；步骤3、建立函数模型，根据动态规划算法计算最优值，直至子图档全部遍历完成；步骤4、布局子图档；步骤5、渲染成图。在动态规划算法的基础上延伸拓展出最适合电力网络的布局方法，能够快速、完美成图，解决了电网系统在大量数据下的渲染效率问题。

说明书

技术领域

本发明涉及一种基于动态规划算法的电网专题图布局方法。

背景技术

电网专题图也可以称之为电气接线图，是对电网拓扑状态的可视化表达方 式，是协助电网运检人员、调度人员工作必不可少的工具，电网专题图往往需 要专门人员手工绘制而成，图形绘制的工作量大，而且还存在图数不一致的问 题。

目前行业内存在各种针对电网拓扑接线图布局成图的算法，其采用的算法 基本上为以下三种算法：

第一、树图布局算法：层次数据的空间填充性布局算法。

缺点是：应对复杂层次数据时，有序树图正方化性能差，难以满足各层数 据展现需求，需要人工参与。

第二、正交遗传算法：通过旋转正交法快速提取解空间中的优异个体的布 局算法。

缺点是：算法对新空间的探索能力是有限的，也容易收敛到局部最优解。 涉及到大量个体的计算，当问题复杂时，严重影响性能，同时对非线性约束的 处理方式是添加惩罚因子，这是一笔不小的性能开支。

第三、有向无环算法：采用消环、分层、排序、路径管理的布局算法。

缺点是：很多电网数据局部成环，无法处理。

发明内容

针对上述问题，本发明提供一种基于动态规划算法的电网专题图布局方法， 在动态规划算法的基础上延伸拓展出最适合电力网络的布局方法，能够快速、 完美成图，解决了电网系统在大量数据下的渲染效率问题。

为实现上述技术目的，达到上述技术效果，本发明通过以下技术方案实现：

一种基于动态规划算法的电网专题图布局方法，其特征在于，包括如下步 骤：

步骤1、根据电力系统的空间数据，构建基于单线图的环网拓扑关系模型；

步骤2、根据构建的拓扑关系模型、子图档的数量N，构建一个由N个顶点 构成的连通图和一个N*N的邻接矩阵；

步骤3、建立函数模型，根据动态规划算法计算最优值，直至子图档全部遍 历完成；

步骤4、布局子图档；

步骤5、渲染成图。

优选，步骤1具体包括如下步骤：

步骤101、根据电力系统的空间数据，按照线路进行分类存储设备信息和拓 扑关系；

步骤102、构建基于单线图的环网拓扑关系模型，用于确定子图档与子图档 之间的关系；

步骤103、对构建的拓扑关系模型进行合并和去重处理；

步骤104、检查构建的拓扑关系模型数据的完整性和连贯性。

优选，步骤2中，每一张子图档是连通图的顶点，顺序遍历子图档，根据 标识的环网点，分析子图档间的连接关系：如果在两张子图档i和j上面都存 在同一个环网点，则这两张子图档是连接的，在邻接矩阵E中标识E(i,j)的值 为“1”；

对邻接矩阵进行广度优先遍历，返回多个能构成连通图的邻接矩阵以及该 矩阵的遍历序列Link。

优选，步骤3具体包括如下步骤：

步骤301、根据邻接矩阵的宽度w，计算出一个能容纳全部子图档并留有最 少空位的正方形范围，设正方形边长为正整数L，则满足：L*L>w>＝(L-1)*(L-1)；

步骤302、遍历第一个子图档到最后一个图档，如果两个子图档间有连接关 系E(i,j)，就计算两个点之间的距离，不重复计算距离，对应的函数模型为：

$min\underset{i=0}{\overset{w}{\Sigma }}\underset{j=i+1}{\overset{w}{\Sigma }}\underset{i,j\in E}{\Sigma }\left(op\right(i,j\left)\right),$

op(i,j)为计算子图档间距离的公式：op(i,j)＝(xi-xj)²*100+(yi-yj)²*100；

其中，x和y属于1到L之间的正整数，代表每张子图档中心点的坐标值；

步骤303、根据动态规划算法，迭代寻找函数op(i,j)新的最优解，直到确定 每张子图档中心点的x和y的值。

本发明的有益效果是：

与现有技术相比：

第一、提出了由多张子图档构成的连通图构想方案，通过函数模型计算出 连通图顶点的位置来确定子图档的位置，并且该位置是最合适的，能够快速、 完美成图。

第二、放弃遗传算法等算法，通过算法优化，使用动态规划算法能够算出 最优解，而不是近似的最优解。

第三、通过把每一张子图档渲染成一个图元的方法，解决了电网系统在大 数据量下的渲染效率问题。

附图说明

图1是本发明一种基于动态规划算法的电网专题图布局方法的整体流程图；

图2是本发明步骤1的详细流程图；

图3是本发明步骤303的详细流程图；

图4是本发明图档合并流程图；

图5是本发明布局前后联络图结构对比图；

图6是本发明41条馈线布局后联络图效果图。

具体实施方式

下面结合附图和具体的实施例对本发明技术方案作进一步的详细描述，以 使本领域的技术人员可以更好的理解本发明并能予以实施，但所举实施例不作 为对本发明的限定。

一种基于动态规划算法的电网专题图布局方法，如图1所示，包括如下步 骤：

步骤1、根据电力系统的空间数据，构建基于单线图的环网拓扑关系模型；

步骤2、根据构建的拓扑关系模型、子图档的数量N，构建一个由N个顶点 构成的连通图和一个N*N的邻接矩阵；

步骤3、建立函数模型，根据动态规划算法计算最优值，直至子图档全部遍 历完成；步骤3满足有连接关系的图档尽可能近，图档不重叠的目的，计算最 优值。

步骤4、布局子图档；

步骤5、渲染成图。

下面对各个步骤进行详细的描述。

优选，步骤1如图2所示具体包括如下步骤：

步骤101、根据电力系统的空间数据，按照线路进行分类存储设备信息和拓 扑关系，即构建多线路模型，以单条线路为标记，分别存储各自对应的设备信 息和拓扑关系。

步骤102、构建基于单线图的环网拓扑关系模型，用于确定子图档与子图档 之间的关系，构建连通图模型，通过联络关系来确定线路之间的关系是否正常， 联络关系为环网点(环网开关)，拓扑关系模型包括馈线F1、馈线F2和联络开 关K三个基本属性。

步骤103、对构建的拓扑关系模型进行合并和去重处理；其中，如有需要还 可以简化设备，形成新的拓扑关系模型。

步骤104、检查构建的拓扑关系模型数据的完整性和连贯性，具体步骤为：

A)通过联络开关K对馈线F1和馈线F2进行下游设备追踪，如果追踪出变 压器则标记为上游设备P，否则为下游设备Q；

B)以上游设备P对应的馈线为基准，将下游设备Q对应的馈线的所有重复 设备和连接关系进行删除，其中，联络开关K不进行删除处理；

C)处理完毕后，再随机选择馈线F1或F2的变压器进行向下追踪，直至追 踪到另一条线路的变压器为止，如果追踪通过，则拓扑关系模型数据正确。

优选，步骤2中，每一张子图档是连通图的顶点，顺序遍历子图档，根据 标识的环网点，分析子图档间的连接关系：如果在两张子图档i和j上面都存 在同一个环网点，则这两张子图档是连接的，在邻接矩阵E中标识E(i,j)的值 为“1”；

因为使用的是动态规划的算法，为了提高算法的性能，对邻接矩阵进行广 度优先遍历，返回多个能构成连通图的邻接矩阵以及该矩阵的遍历序列Link。

优选，步骤3具体包括如下步骤：

步骤301、根据邻接矩阵的宽度w，计算出一个能容纳全部子图档并留有最 少空位的正方形范围，考虑到范围越大，计算函数需要花费的时间越大，所以 使用一个能容纳全部子图档并留有最少空位的正方形范围，设正方形边长为正 整数L，则满足：L*L>w>＝(L-1)*(L-1)；

步骤302、遍历第一个子图档到最后一个图档，如果两个子图档间有连接关 系E(i,j)，就计算两个点之间的距离，不重复计算距离，为了减少图档间连接 的交叉，构建的函数模型应满足有关系子图档尽量紧凑，同时不能重叠。

对应的函数模型为：

$min\underset{i=0}{\overset{w}{\Sigma }}\underset{j=i+1}{\overset{w}{\Sigma }}\underset{i,j\in E}{\Sigma }\left(op\right(i,j\left)\right),$

op(i,j)为计算子图档间距离的公式：

op(i,j)＝(xi-xj)²*100+(yi-yj)²*100；

其中，x和y属于1到L之间的正整数，代表每张子图档中心点的坐标值；

该函数模型经过多次试验和调优，效率和效果都是最佳。

步骤303、根据动态规划算法，迭代寻找函数op(i,j)新的最优解，直到确定 每张子图档中心点的x和y的值。具体如图3所示：

1)根据Link的长度(序列长度＝图档数量)计算出顶点范围F，构建F*F 个格子，每个格子用于存储当前格子存储的子图档下标编号和对应的x，y值； F＝{1,2,3,……L}，其中L是一个能容纳全部子图档并留有最少空位的正方形边 长。

2)根据动态规划算法，按下标计算出第一个图档顺序放入空闲格子的函数 值；

3)根据连接关系寻找最优解并迭代执行该过程，直至子图档全部遍历完成， 在迭代过程中需要判断子图档是否有连接，如果无连接，则将下标记录到无连 接数组中，继续迭代该过程；否则进行动态规划算法，按下标继续放置子图档；

4)遍历完序列Link后，整理数据，遍历每个子图档存储的唯一格子对象， 根据格子对象中的子图档对象的下标进行排序，并返回每个子图档的x和y值。

本算法中，以计算解出的值是否为最小值为最优解，即如果为最小值则记 录为最佳位置，直至计算完毕后无法找到更小值为止。计算完毕后，如图3所 示，按下标存储每个图档的最优解，最优解数组的格式为bestResult[](二维 整形数组)，比如[x1,y1],[x2,y2],[x3,y3]...，[x1,y1]对应子图档1的最 佳位置。

优选，步骤4如图4所示，具体包括如下步骤：

步骤401、遍历最优解bestResult[]，获取每一个子图档x、y坐标；

步骤402、计算每个子图档的实际坐标值：

按照布局后计算的每个子图档位置计算子图档的长宽后进行放置，遍历最 优解数字，按下标取每个图档的最小宽度和最小高度来比对和最优解中相对应 的x(宽)和y(高)，对比取最小值。

步骤403、根据实际坐标值对子图档中的设备进行重新放置：

对设备进行整体移动，以保证图档中每个设备的相对位置不变(整体移动 的效果)。

步骤404、确定每一张子图档的位置后，合并多张子图档，并放置子图档间 的连接线，使其保持横平竖直。

图5是采用本方法进行子图档布局的前后对比图，很明显的，布局后的图 档更美观、直接的体现各个子图档直接的连接关系，非常方便电网运检人员、 调度人员进行一线操作。

优选，步骤5具体包括如下步骤：

步骤501、通过图形引擎将连通图中的每一张子图档渲染成一个单独的图 元，可以对整体图档进行调整。单独的图元意味着该图档中的所有设备的移动 都是一起保持相对位置进行移动的，连通图中子图档越多则连接数量越多，此 方法可以保证在大局上连通图整个走向一目了然，便于整体性调图。

步骤502、在需要调整具体一张子图档的位置或其中的设备时，再进行二次 渲染，可以把该子图档渲染成单个设备构成的图元，进行单个设备的调整。

图6是本发明41条馈线布局后联络图效果图，支持对图档进行调整。本发 明提出由多张子图档构成的连通图，通过函数模型计算顶点的位置来确定子图 档的位置，此算法布局生成单线图，布局美观合理、无重叠少交叉、计算速度 快，成图效率高。

与现有技术相比：

第一、提出了由多张子图档构成的连通图构想方案，通过函数模型计算出 连通图顶点的位置来确定子图档的位置，并且该位置是最合适的，能够快速、 完美成图。

第二、放弃遗传算法等算法，通过算法优化，使用动态规划算法能够算出 最优解，而不是近似的最优解。

第三、通过把每一张子图档渲染成一个图元的方法，解决了电网系统在大 数据量下的渲染效率问题。

以上仅为本发明的优选实施例，并非因此限制本发明的专利范围，凡是利 用本发明说明书及附图内容所作的等效结构或者等效流程变换，或者直接或间 接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。