电力数据网探针部署算法的优化改进研究

张志生

（云南电网有限责任公司信息中心，云南 昆明 650200）

0 前言

现行的电力信息系统更多将关注点集中于系统整体可用性、设备运行状况和整体性能等方面，系统无法实现主动测量，无法主动发现运行过程中可能出现的各类状态问题。这种情况的存在导致电力系统的整体运行并不稳定，系统在运行过程中经常会出现系统延时以及其他故障问题，此类问题出现的主要原因是系统运行中缺少必要的主动探测技术，另一方面，从业务系统的使用角度看，监控对象和监控内容不足，不能有效的评判电力信息系统的实际使用情况。在电力系统中部署探针后，系统探针可以主动获取运行状态信息，实现系统各项业务的快速监控和有效故障定位，通过采集系统应用数据，实现有效定位，对电力信息系统的稳定运行及实用化应用意义重大。

在互联网信息技术的发展下，我国电力系统实现了自动化与信息化发展。我国电力数据网在规划上有着较高的一致性，系统在建设及后期应用过程中始终坚持保障性、安全性、先进性、经济性的基本原则内容[1]。电力数据网中常见的结构形式有星型、环形以及双星型结构[2]。电力数据网为了处理电力系统中庞大的业务工作具备了网络范围大、网络覆盖广、业务多样化的基本特性。其在一些特殊性的业务工作中有着更高的要求标准，此类工作主要为电力系统中的网络性能测量工作、拓扑结构测量工作、服务质量测量工作、多协议标签交换工作（QoS）及VPN通道测量工作等[3]。

电力数据网探针部署问题主要集中在多目标多约束优化上，技术的应用需要全面分析技术的实际价值、部署成本以及系统后期可靠性等[4]。针对此类问题我国学者进行了综合性的研究。文献[5]为了解决系统的不确定与不稳定问题，应用贪心策略，经过仿真验证发现系统的稳定性有所提高并得到了一定优化，但在运行中仍然会出现冗余解的情况。文献[6-7]在研究过程中运用遗传算法有效消除了无效解问题，但由于研究中忽略了可靠性及探针部署成本等主要因素，导致结果中出现了冗余解情况，探针数目仍无法实现最小化处理。本次研究中基于上述研究内容，运用贪心策略和遗传算法思想改进探针部署算法。

1 探针部署优化问题建模分析

随着电网智能化与自动化水平的提高，凭借工作经验以及部分内容进行推断部署的方式已俨然无法适应当前探针部署工作基本要求。本次研究中将电力数据网线路与业务进行有机结合，以此转变为数学模型，实现电力业务的抽象化与简便化。无向图的最小顶点覆盖问题为探针部署中的核心问题，研究中设定无向图G=(V,E)，其中顶点的集合表示为V，边集合表示为E。如果顶点覆盖中存在集合S使得G中的各个边与之关联，即在所有G中的E都至少有一个在顶点S中。此时则成S集合为图G的一个顶点覆盖。如果存在某一个S为G的一个顶点覆盖并且不存在其他包含更少顶点的集合可以覆盖全图，则称S为图G的一个最小顶点覆盖[8]。

图1所示的无向图中包含8个顶点与10条边。图中的顶点集合为S=(2,4,6,8)，从图中可以明显看出每条边都至少有一个顶点处于S中，因为其中并未存在其他集合可以包含更少的顶点覆盖全图，由此确定S为是其顶点覆盖，并且S是其最小顶点覆盖。

2 电力数据网探针部署优化

2.1 改进贪心算法的基本原理

本次研究中从无向图最小顶点覆盖角度出发，研究电力数据网中探针部署优化问题。由于传统贪心算法策略中存在着节点随机选取的情况，因此无法有效解决最小顶点覆盖的问题，并且电力数据网中存在着多种拓扑结构类型，应用传统贪心算法策略很可能会出现覆盖顶点过多和冗余节点的问题。基于上述问题，结合电力数据网拓扑结构类型，在无靠性约束条件下提出一种改进贪心算法策略，以实现无向图中限定覆盖顶点方向选取，消除矩阵中的冗余节点[9]。

根据上文所述，可以将电力数据网中的探针部署问题转化为无向图最小顶点覆盖问题，本次研究中提出无可靠性条件下的电力数据网探针部署的数据模型：

求得：

满足：

式中，S表示顶点覆盖集合，D表示探针部署的开销，其中xi∈S,x=[x1,x2,x3,...,xn]为v=|V|的向量，A=(aij)n×n是图的邻接矩阵。

其中：

电力数据网的网络结构包含核心层、汇聚层、接入层。在电力数据网拓扑结构抽象化分析中，各个层级节点都是相互独立的，三层结构中形成了独立的节点集合[10]。电力数据网中核心层的分布结构为网状结构，如图2所示。而汇聚层与接入层中的节点呈现出二分图分布特征，如图3所示。

图2 网状图结构形态

图3 二分图结构形态

在传统贪心策略中通常选取度数最大的节点来解决最小顶点覆盖的问题。此方法下可以实现最佳覆盖定选取工作，但同样会造成全局性问题。

上图中所应用的贪心策略可以实现每次最大度数节点的多种选择。由于选择是随机进行的，因此选择结果存在最坏情形，如果在随机选择中所选取节点为{11,12,13,14,15,16,17,18,31,32,33,34,35,36}时，图中的覆盖顶点共计有14个。如果随机选取节点为{21,22,23,24,25,26}，则说明覆盖顶点结果最佳，此时覆盖顶点数量为6个。此时所出现的情况为随机选取性所带来的顶点过多问题。而在核心层的网状结构中，可实现选取度数最大节点，首次选择必然会选取节点1，而在第二次选择中便增加了一定的随机性[11]。如果在网状图中首次与后续随机选取的节点为{1,2,3,4,5}时，可以得到网状图的顶点覆盖集合。在该类型选取中，若将首次选取结果的顶点1去除，剩余顶点仍然可以覆盖全图，则网状图中的顶点1可以被看作一个冗余节点。这种情况的出现就是覆盖顶点选取中的冗余节点问题。

通过分析了解到，在电力数据网探针部署问题中借助传统贪心算法策略，仍然会存在探针部署数量确定困难、数量开销成本增加的问题。此问题主要是由于网络拓扑结构特征所造成的。

根据电力数据网中现存问题，本次研究选择网络拓扑结构特征为入手点分析，根据二分图和网状图的特征弊端进行改进说明。

为了解决二分图节点选取中所出现的最坏情况，确定了如下改进方法：每次删除最大度数顶点的相关边时，应同时去除度数为1节点的影响。在算法运行中对选取最大度数顶点进行了改进变化，其中规定在选取中如果出现相同情况则需优先选取存在度为1邻接点的节点，以此最大限度上减少度为1节点所产生的影响。

网状图在节点选择过程中存在冗余节点问题，在解决此问题上选择采用标记矩阵形式，迅速确定冗余节点[12]。在改进算法通过生成标记矩阵分析记录顶点覆盖集是否存在均被重复覆盖的顶点，以此最终确定冗余节点。

2.2 改进贪心算法策略流程内容

电力数据网探针部署应用改进贪心算法策略方法步骤如下所示：

第一步：初始化阶段。确定无向图的邻接矩阵A与完全相同标记矩阵B，确定其顶点覆盖集为S。

第二步：如果邻接矩阵A为0，直接执行第三步，否则执行第三步。

第三步：选择矩阵中度数最大的节点，如果最大节点唯一存在，直接将其归属于顶点覆盖集合S中，记录顶点标号i，并执行第五步，否则执行第四步。

第四步：确定度数最大的节点组中是否存在度为1的邻接点，如果存在将其加入到覆盖顶点集S中，记录顶点标号为i，并继续执行第五步，否则随机选择其中一个节点加入到集S中，记录顶点标号为i，并继续执行第五步。

第五步：去除节点i的相关边，将邻接矩阵中第i行与第i列全部重置为0，并执行第六步。

第六步：标记矩阵B中的第i行与第i列中每个元素减去原来邻接矩阵相同位置所对应的元素，并执行第二步。

第七步：无向图的原邻接矩阵与标记矩阵相加，确定行（列）情况，如果结果不存在行（列）全部为0，则算法结束，此S即为结果。否则将全为0的行（列）号进行记录，此为冗余节点标号，将其从S中删除，算法结束，删除冗余节点后的集S即为结果。

图4 改进贪心算法策略流程内容

2.3 仿真实验

基于改进贪心算法策略的探针部署效果需要通过仿真实验进行验证分析。验证中使用GT-ITM拓扑生成器，生成器可以根据两点间存在的概率来随机生成平面拓扑图，平面拓扑图的机电数量不同，其复杂程度也存在差异[13]。本次仿真实验中生成Waxman2模型，仿真实验模型中的顶点间存在边的概率为：

上式中a,b∈(0,1)，且图中的边数会随着a的变化而改变，二者存在显著的正比例关系，而图中的长短边比值会也与b之间存在着正比例关系。

本次仿真实验中分别选取a=0.3，b=0.4和a=0.4，b=0.3进行分析，在不同复杂程度下的拓扑图中分别应用传统贪心算法策略（TGS）与改进贪心算法策略（IGA）分析无向图的最小顶点覆盖问题，其结果如图5、图6所示。由图可知，在不同复杂程度、规模下改进贪心算法与传统贪心算法相较仍具有明显的优势，在拓扑图上解决最小顶点覆盖问题上效果比较明显。

图5 a=0.3，b=0.4

图6 a=0.4，b=0.3

3 混合遗传算法的探针部署

3.1 混合遗传算法的基本原理

基于抽象条件与可靠性因素建立数学模型，本次研究中所提到的可靠性体现于主动探测的可靠性与重合率上[14]。

电力数据网中的主动探测可靠性即为探针可靠性，其主要为系统探针工作时间与系统站点应用时间比值。探针可靠性通常情况下维持在80%～90%。

可靠性由以此对系统网络探测所包含探针可靠性乘积表示为：

上式中，r为以此对系统网络探测中所包含的探针集，φ为阈值。

在顶点覆盖问题中，重合覆盖率是探测可靠性的重要保证，覆盖的重合率为探针探测中被多次探测的节点数据与被探测总数目之间的比值[15]。通过计算重合率情况可以判断探针部署是否紧密。若重合率越高表明探针部署越紧密。此情况下如果探针出现问题无法使用，系统网络仍然可以实现完全探测，并同时兼具一定的探测效率。重合率虽然对探测效率意义重大，但与探针部署开销之间却存在着显著负相关关系，此项关系也是日后改进的一个重要方向。

重合覆盖率公式为：

上式中，N为被探测节点的总数，C为能够被多次探测的节点数目。由此可以得到可靠性与重合覆盖率相结合的综合可靠性计算方法：

公式为：

上式中的λ1，λ2分别表示探测可靠性与重合覆盖率所占权重，二者的和为1。

研究中同样给出了探针开销函数。电力数据网的探针部署工作并不是一项简单的一次性工作，此项工作完成后需要完成后期的运营管理与长期维护工作。这两部分也是电力数据网探针开销的主要构成，本次研究的开销函数为：

上式中，xi为遗传算法中染色体的位数，其中i只能为1或0，代表节中是否部署了探针，v代表染色体基因位数，是无向图节点数目。由此确定电力数据网探针部署数学模型如下：

电力数据网探针部署数学模型满足：

由上述部署数学模型可知，探针部署模型可以覆盖全图，且确定的模型具有较高的可靠性。此条件下需要实现无向图的有效联通，实现部署开销函数的最小化，完成函数最小求解。

本次研究中在传统混合遗传算法探针部署数学模型基础上，进行了优化改进。研究中在传统算法的选择算子中加入了可靠性约束参数条件，完成轮赌选择的重新设计，其选择部署个体的概率函数如下：

通过上式可以实现个体可靠性与个体适应性的有效结合，整体中可靠性越高的个体被选择的几率会明显提高，则更有利于部署整体朝着高度可靠性方向发展。

在遗传算法改进中，根据部署情况重新设置了变异概率。通过优化变异概率可以有效减低模拟自然环境下受偶然原因出现的基因突变问题，并且算法的整体性也会有所提升。在遗传算法模型中，变异算子主要承担了算法全局搜索功能的作用，算法可以在变异算子的引导下搜索到模型中的每个个体单位[16]。在模型应用中，变异算子会将个体中某一基因位xi以概率p(xi)取反。模型应用中每个基因被取反的概率是完全相同的。在电力数据网部署探针过程中，外层的作用会低于内层的作用，因此便更利于确定无向图的最小顶点覆盖。改进遗传算法中设定了不同的取反率：

上式中，下标表示基因位数，上标表示节点类型。

其中的个体变异表示为：

完成算法修正后，需要借助标记矩阵辅助消除冗余节点，提高改进遗传算法的收敛速度。

3.2 混合遗传算法的算法流程

本次应用改进遗传算法解决最小顶点覆盖问题时，充分考虑到了传统遗传算法的弊端，在初始种群中，以及正常的选择、交叉、变异操作过程中都会出现不可行解的问题，此时应用传统遗传算法则无法实现全图解的有效覆盖，所确定的解也将直接影响遗传算法的收敛速度和结果准确性。

基于传统遗传算法的应用情况，本次研究对此问题进行优化处理，提出修正算法，其算法流程步骤如下：

第一步：如果所求解合法，停止。

第二步：依据邻接矩阵A与染色体x，对染色体中的基因进行扫描，设定邻接矩阵A中与x为1位相关的边为0。

第三步：将A中存在为1的边相关顶点直接加入到染色体x中，并设置为1，完成修正。

第四步：完成初始群体中染色体处理后，停止，否则返回第二步。

上述修正算法，促进了传统遗传算法的应用进度，但在应用中仍存在一定不足，修正算法在应用中仅将其中的个体进行合法化，而忽略了冗余节点的问题。在此条件下，本次研究中提出了基于混合遗传算法的探针部署方法，其算法流程如下所示：

第一步：依据电力数据网探针部署的基本情况，确定探针部署中探测可靠性、部署和成本参数。选用初始解集完成网络部署工作，并将其作为遗传算法的种群P(t)，确定为第一代解，规模为S。

第二步：以是否部署探针为判断依据，确定编码1,0，保证其中每个解都是一组二进制数。

第三步：运用适应度函数评价解集，在合法性与可靠性条件满足下，确定目标函数所对应的适应度函数值。

第四步：如果满足条件，输出最优解，终止算法。

第五步：集合选择算子、交叉算子和变异算子，进化得出下一代解集P(t+1)。

第六步：运用修正算法修正不合法解，提升算法加速进程。

第七步：运用消除算法消除局部不足，实现局部最优与全局最优。

第八步：从第三步开始评价局部改进解集。

图7 混合遗传算法流程图

3.3 仿真实验

本次研究中通过数据网络拓扑模型检验改进后的混合遗传算法在电力数据网探针部署中的实际效果。检验中所应用的数据拓扑网中由160个节点和190条链路组成。

仿真实验中电力数据网中所使用的探针品牌及各项成本具有较高一致性，因此可以通过探针部署的实际数目确定部署的实际开销成本。本次所选用数据网拓扑结构中的邻接矩阵长宽相等均为160，其中所共计包含160位基因数。仿真实验中设置初代种群规模为64，接入层、汇聚层与核心层的基因异变率分别为：1%、2%和3%。其中的最大进化代数为100。仿真实验中探测可靠性、重合覆盖率可靠性的比重分别为：,λ1=0.4，λ2=0.6，二者的阈分别为：φ=0.8，θ=0.9。实验中可靠性指标随进化代数变化情况如图8所示。

图8 可靠性随进化代数变化情况

实验中探针部署开销成本岁进化代数变化情况如图9所示。

图9 探针部署随开销成本进化代数变化情况

由上图可知，在可靠性条件下，应用混合型遗传算法求解可以实现最低开销，探针部署中数目越多可靠性越高，但部署的开销成本会明显增加。仿真实验中，在假定探测可靠性与重合覆盖可靠性指标保持不变情况下，将探测可靠性提升到0.85、整体可靠性阈值提升到0.95。不同阈值 下的适应度对比情况如图10所示。

图10 不同阈值条件下适应度变化情况

从上图变化情况可以看出，在可靠性水平提升下，目标函数随之变大，此时的适应度逐渐下降。为了提高电力数据网的可靠性水平需要提高探针部署数量，与此同时，也需要注意到随数量增加而出现的开销成本增加问题。

应用传统遗传算法和改进混合遗传算法对阈值在0.8～0.9范围内的拓扑进行求解分析，其结果如表1所示。

表1 传统遗传算法与混合遗传算法对比

由表1可知，在可靠性条件下，混合型遗传算法在探针部署中效果更佳，与传统遗传算法相比有着更快的收敛速度。

4 结束语

信息业务系统在智能电网建设中发挥了关键性作用，本文从系统探针部署问题入手，以提高探测覆盖率及可靠性研究的主要方向。研究中通过算法改进实现了系统探针部署的优化。文中通过抽象化思维通过研究最小顶点覆盖问题分析探针部署优化问题[17]。此问题解决中以电力信息系统实际情况为依据建立探针部署数学模型，结合贪心算法提出了改进贪心算法策略，以遗传算法为基础提出了混合遗传算法，并通过仿真实验验证确定了两种算法模型均具有较好的可行性及收敛性。算法改进工作对系统探针部署优化子系统的建设意义重大。