图模智能分析系统的研究及其应用

【摘要】自动绘图算法针对大规模电网的潮流图自动生成是一个复杂的问题，本文采用两部分来解决。针对厂站的自动布局问题，采用根据节点的实际经纬度拟合进通过因式分解后的网格中的算法。针对自动布线问题，首先采用线探索法对线路进行初步布线，再采用lee算法对线探索法无法确定的线路进行布线，最后根据网格通道布线的特定情况，调整线路位置与所占面积，达到避免线路不必要交叉的问题，同时也解决了线距过近等问题，最终实现了全局美观。最后针对某省级电网模型的测试验证了本文研究方法的有效性。

【关键词】潮流图;自动绘图;线探索法

1.引言

传统的潮流图大都为人工绘制，随着电网规模的逐年发展，原有的人工绘制好的潮流图都趋于饱和，因此新增或者修改节点与线路将会耗费大量的时间与精力。现有的系统潮流图功能很是单一，不能满足技术人员的实时分析与互动校核的要求[1]。传统的系统潮流图是由不同技术人员绘制，因此在绘图过程中往往缺乏一个统一的规范，例如节点的命名等，从而会引起今后的使用过程中的不便利的问题。

虽然国内外对电网的抽象图智能生成有一定的研究，但是都是针对小规模的配网而言，对全省的主网潮流图，包含近200节点的大规模电网使用智能算法自动绘图尚属首次。电气图的智能生成优化问题，是一个NP难问题，其计算复杂度随着节点和线路规模的增长呈几何级数增长。因此，对于该问题无法在多项式时间内求得最优解。而现有的各类进化算法，包括遗传算法、人工神经网络、模拟退火算法等均大量的计算时间，而且并不保证求得逼近最优解的较优解。而各类启发式算法尽管计算速度较快，但是很容易使得目标函数陷入局部极值点而无法跳出，给优化过程带来难以处理的情况[2]。对于节点布局模块，本文根据布局区域分辨率，对节点个数进行因式分解，根据节点的实际经纬度，将每个节点拟合进因式分解后的网格中。节点布局完成之后采用改进的线探索法[1]对节点间连线进行初步布线，对无法确定的线路采用lee算法进行布线，在完成整体布线之后，本文根据节点与线路的特点调整线路位置与所占面积解决线路重叠、线路之间距离过近、交叉等影响绘图美观的问题。

2.节点自动布局

2.1 根据节点个数的因式分解

由于电网节点的实际位置是以500kV变电站为中心，220kV变电站与发电厂为辐射点的格局，因此采用根据节点的实际经纬度来对节点进行布局可以使得整体布局以500kV电压等级的节点为中心节点，220kV电压等级节点为辐射点的发散形式予以表现，一方面可以符合调度员的认知习惯，同时也避免自动布线过程中由于节点间距离过长，从而使得线路过长的问题。布局所需数据为，变电站个数Ntrans，发电厂个数Ngen，每个节点的电压等级Tilev与其所处的地理位置（经纬度）Tigeo，可以得出全网节点的总数Nsum。其中：

Nsum=Ntrans+Ngen （1-1）

再通过因式分解将Nsum分解为m×n，其中m与n都为整数，由于最终结果是在1280×720的区域中，因此m与n应满足：

<n<m （1-2）

的关系。本文所设计的系统可以满足200个节点的自动布局。因此：

m×n≤200 （1-3）

因式分解的过程为：

（1）确定布局系数k，其中k为：

k=1280/720（1-4）

其中：

m=k×n（1-5）

（2）确定布局区域网格的行数n与列数m，根据（1-5）与（1-3）可知：

k×n2=200 （1-6）

从而得出ms，ns，其中ms与ns为目标的因式分解。

2.2 根据节点实际经纬度的拟合网格算法

完成因式分解之后，再将布局区域分为ms×ns的网格，然后再根据每一个节点的经纬度，通过拟合算法将每个节点布置在ms×ns的网格中。下面介绍拟合网格算法。

（1）确定某地电网经纬度范围（longitudemin，longitudemax），维度范围（latitudemin，latitudemax）。

（2）确定电网所有节点的经纬度Tigeo，其中Tigeo的数据结构为（longitudei，longitudei）。

（3）搜索在经度范围为（longitudemin，longitude1）的节点，其中：

（1-7）

得出第一列的厂站集合NUM1，再以此搜索（longitude1，longitude2），….，（longitudei-1，longitudei），….，（longitudemax-1，longitudemax），其中：

（1-8）

范围之间的厂站，将各个区间经度的厂站以此分别列入集合NUM2，NUM3，…，NUMi，…，NUMmax中。

（4）将所有经度满足（longitudemin，longi-tude1）之间的NUM1个节点布置在网格的第一列中，布置规则为根据NUM1集合中节点的纬度大小，纬度由高到低排入第一列的ns行中。若NUM1≥ns，求出NUM1east，其中：

NUM1east= NUM1-ns （1-9）

然后搜索出NUM1集合中NUM1east个经度最大，即最靠东的节点，将这类节点归入NUM2集合中。若NUMi≥ns，则按照上述跪着求出NUMieast，其中：

NUMieast= NUMi-ns （1-10）

然后在NUMi集合中搜索出NUMieast个经度最大的，即最靠东的节点，将这类节点归入NUMi+1集合中。

（5）本系统的自动布局的原则是尽可能使得全局均匀排布，即若NUM1<0.75ns，则会对第一列网格中留出很多空白网格，从而使得全局不美观，因此按照上述原则，对这类集合进行修改。即若NUM1<0.75ns，则从NUM2集合中搜索NUM2west个厂站，其中：

（1-11）

这NUM2west个厂站是NUM2集合中经度最小（最靠西）的厂站，将NUM2west个厂站归入第一列中，即放入NUM1集合中。NUMi集合也遵循上述原则，其中i=2、3、…、max。

3.线路的自动布线

自动布线的目标是将所有有联络关系的线路通过横平竖直的折线段表示在绘图区域中。

3.1 厂站出线位置规定

厂站的出线位置合理就可以很好避免布线过程中出现的不必要的交叉，考虑到厂站在图形中的宽度与长度，本文规定厂站的横向最多出7回线路，厂站的竖向最多出4回，下面为事先制定要的厂站出线位置规定。

图1 厂站的出线位置规则

图2 线探索的应用

对Vi节点的出线位置规定步骤为：

（1）确定与Vi节点，其坐标位置为（xVi，yVi）相关联的节点Vj坐标位置（xVj，yVj）。

（2）判断（xVi，yVi）与（xVj，yVj）的大小关系。如Vi与Vj两节点的位置坐标满足xVi>xVj，yVi>yVj时，Vj则在图1中B方向，则Vi所对应的出线位置则如图1中对应连接B节点的出现位置。

根据上述方法对全局节点先行规定出现位置，为下一步布线算法做好准备。

3.2 基于线探索法与lee算法的线路走线设计

由于传统的lee算法是采用广度搜算算法的思想，但是针对大规模的电网，布局区域大，可行的走向方案很多，使用lee算法搜索出一条最优线路将会耗费大量的计算时间，因此本系统需要一种有较高效率的算法，来减少计算时间，本次研究采用改进型的lee算法，即线探索法来对线路进行布线，下面介绍具体步骤：

（1）由两个有联络关系的节点A与B分别引出一条水平辅助线和一条垂直辅助线，检测两节点之间的辅助线有无交点。

（2）若无交点，检测辅助线所遇障碍，并在所遇障碍出距离为d的点标记E。

（3）对E点若在的辅助线引出一条与之处置的辅助线，并检两节点的辅助点间是否存在交点，若无交点，则继续根据上述规则引出辅助。

（4）若检测到两节点的辅助线存在一个交点D，则以交点所在的辅助线向节点所在位置回溯，所得结果既为走线方案。

图2所示为线探索法的例示。

由于线探索法有很高的搜索效率，但是在布线过程的后期由于可用的绘图的空白区域已经趋于饱和，因此线探索法在这种情况的应用往往不能搜索到一个可行的方案，从而需要lee算法予以配合才能完成，首先搜索出布线失败的线路，对这类线路使用lee算法进行布线，下面介绍lee算法的具体步骤。假设起始变电站网格为A，我们赋予网格值为“0”，这样，其相邻的不是障碍的网格值被标记为“1”，并向外扩展;从“1”扩展而来的网格点的网格值被标记为“2”，如此下去，直到扩展到目标变电站B或者无法扩展为止。只要在A，B间存在路径，用lee氏算法一定可以找到一条路径，并可以保证该路径是最短的。扩展过程如3图所示。

图3 lee算法示例

图4 竖向通道中线路重合的情况

图5 竖向通道中重合线路调整规则

使用Lee算法搜索到可行通路后，可能会出现大量的可行通路，而许多通路拐点过多，不是最优的，则需要对Lee算法加入判断最优路径的过程，因此为避免出现过多拐点，在回溯过程中，采用贪婪行为，即回溯时尽量不拐弯的准则。

3.3 走线的调整与优化

通过上述两种算法对线路进行初步布线，但是很出线线路重合，或者线距过近的问题，因此需要对线路的走线方案进行优化。

由于每一个厂站被布置在网格中，网格之间的每一列与每一行都为走向通道，因此计算每一竖向通道中线段的数量ni与每一横向通道中的线段数量mi，计算横向通道德高度h与竖向通道的宽度d，下面以对全局竖向通道内线段进行修改为例。

将竖向通道分为ni份，即每一条线段占据一份，得到：

N=d/ni （2-1）

其中N为竖向通道中每一线段所占据的宽度。

通道内线段按照从高到低，从左至右分别安排至每一分中，若遇到多条线段重合的情况，则按照图4、5所示准则进行调整。

通过上述规则对重合线路进行调整位置，可以很好的避免不必要的交叉，按照上述规则对每一个通道中的线路进行调整，但是由于部分通道内线路过多，而个别通道线路少，就会导致线路多的通道内线路拥挤，线路之间的线距过近，线路少的通道中线距大，局部稀疏，导致面积使用不合理的问题，因此为了避免上述问题，需对全局的竖向通道的宽度d与横向通道的高度h进行调整，具体步骤为：

统计所有竖向通道个数a，横向通道个数b，统计全局竖向通道中线段数量n，横向通道中线段数量m。根据竖向通道个数a与宽度d，计算出竖向走线的线路所占面积。

Sd=a×d （2-2）

根据横向通道个数b与高度h，计算出横向走线的线路所占面积。

Sh=b×h （2-3）

图6 实际电网潮流图最终效果

由于线路所占面积不平均是导致上述问题的根本原因，调整每条线路所占面积，使得全局横向走线的线路所占面积一致，全局竖向走线线路所占面积一致。

Sn=Sd/n （2-4）

Sm=Sh/n （2-5）

其中Sn为调整后的竖向走线的线段所占面积，Sm为调整后的横向走线的线段所占面积。

4.系统算例

本文对包括152个厂站与394条线路的贵州电网进行潮流图的自动生成，总共耗时13s。本系统也满足厂站的位置拖动修改，线路跟进改进的功能。下图为系统最终成图效果。

从图6可以看出节点均匀的分别在布局区域中，220kV电压等级的节点辐射状的分布在500kV电压等级的节点的周围。在布线方面，线路很好的避免了不必要的交叉，且线路之间的线距也是在可以接受的范围之内。

5.总结

本文分为自动布局与自动布线两部分，自动布局可以节点在满足相对地理位置的情况下以发散的形式分布在中心节点的周围，自动布线部分通过采用特定的方法对线路位置进行修改很好的避免了不必要的重复，从而使得全局绘图美观。

参考文献

[1]沈伟，吴文传等.能量管理系统中潮流单线图自动生成算法[J].电力系统及其自动化，2010，34（6）：48-56.

[2]何胜，梅娟，石贵阳等.代谢网络自动绘制的快速网格布局算法[J].食品与生物技术学报，2008，27（5）：86-90.

[3]宋适宇，何广宇，徐彭亮等.输电网单线图的自动生成算法[J].电力系统及其自动化，2007，31（34）：12-15.

[4]程远，严伟，李晓明.基于斥力-张力模型的网络拓扑图布局算法[J].计算机工程，2004，30（3）：104-105.

[5]陈传波，胡谊东，何力等.目标驱动的迷宫布线算法及优化[J].华中科技大学学报：2004，32（1）：49-51.

[6]KAWAHARA K，YOSHIZU K，ZOKA Y，et al.Construction of auto matic drawing system of power system diagram by using GA//Proceedings of 2000 International Conference on Power System Technology：Vol 1，December 4-7，Perth，Australia：497-502.

[7]BATTISTA G D，EADES P，TAMASSIA R，et a.Algorit hms for drawing graphs：an Annotated putational Geomet ry：Theory and Applications，1994，4（5）：235-282.

作者简介：

陈巨龙（1983―），男，硕士，工程师，现供职于贵州电网公司电力调度控制中心，研究方向：调度自动化及计算机信息处理。

罗欢（1990―），男，四川大学硕士研究生在读，研究方向：调度自动化及计算机信息处理。

陈实，男，博士，现供职于四川大学，研究方向：调度自动化及计算机信息处理。