基于禁忌搜索与扰动策略的探针部署算法

张志生 路 辉 刘 星

1(云南电网有限责任公司信息中心 云南 昆明 650021) 2(昆明能讯科技有限责任公司 云南 昆明 650021)

0 引 言

随着电网业务量以及用电需求数量的增加，为保障供电质量与供电安全，对负责电网数据采集与传输的智能电网稳定性以及安全性提出了更高要求。为此，常通过在智能电网部分节点中部署探针[1]以实现对全部节点的实时监测，以便及时对网络中出现故障的节点处设备进行及时修复或替换，从而保证智能电网稳定且安全地运行，达到供需平衡、安全用电的目的。在电网节点中所部署探针均通过向被监测节点发送监测数据信息包，并以该探针能否接收到来自该监测节点返回的确认信息为指标，从而判定所监测节点是否为故障节点。因此，如何以最少数量探针监测电网中所有节点从而达到降低监测成本并提升监测效率的目的是需解决的首要问题。

1 问题模型

探针监测数据包具体发送与接收过程如图1所示。

图1 故障监测过程示意图

图1中，节点A1、A4、A5、A6均为探针部署节点，若A1通过路径A1→A4→A7向A7发送监测数据信息包，因路径中A4已部署探针[2]，故可根据A1能否接收到确认信息，判定A7是否出现故障。然而若A1通过路径A1→A2→A5→A7对A7发送监测数据信息包，因该路径中A2未部署探针，故当A1无法接收到确认信息时，无法判定是A2还是A7出现故障，需缩短探针与被监测节点间路径。因此，为保证各探针及时准确地定位故障节点，需使得各节点均至少存在一个与其直接相连的探针节点的同时，所部署探针数量最少，故可将该问题简述为部署最少数量的探针覆盖智能电网中所有的边，即无向图G=(V,E)(V为图G中所有顶点的集合，E为所有边的集合)中最小点覆盖[3]的求解问题。

针对上述经改进蚁群算法在最小点覆盖求解过程中存在的问题，本文提出一种基于禁忌搜索与扰动策略的探针部署算法[5](Probe Deployment Algorithm Based on Taboo Search and Perturbation Strategy，PDA-TSPS)，该算法首先通过快速邻域切换与禁忌表构建降低智能电网中的顶点状态更新时间，同时避免对顶点进行重复计算，其次结合扰动策略对局部最优解中一定比例的关键节点进行移除，以突破空间限制、扩展集合求解范围，使所求解最小点覆盖结果达全局最优。

2 经改进的蚁群算法

2.1 算法原理及步骤

通常将传统蚁群算法进行改进设计出一种经改进的蚁群算法以实现对无向图G=(V,E)中S集的求解，该算法首先对无向图中各顶点以及边赋予权值，构建点边赋权图Gc=(V,Ec)，如图2所示。

图2 点边赋权图构建过程示意图

对上述点边赋权图Gc=(V,Ec)中原有各边均赋权值1，对Gc中新构建的各边(Ec-E)均赋权值0，构建连接函数ψk(i,j)，即：

(1)

假定选择顶点a1为所求解最小点覆盖集S1的初始顶点，则令与其关联所有边的连接函数值ψk(i,j)均归0，然后计算a1的各相邻顶点动态启发因子ηkj，并结合该因子确定最小点覆盖集中的下一顶点，当各相邻顶点动态启发因子均为0时停止计算，动态启发因子ηkj的计算式为：

(2)

(3)

经计算顶点a4，被选作下一顶点，令与顶点a4所有相关联边的连接函数值ψk(i,j)均归0，并重复上述步骤，求解出下一顶点为a3，直至各相邻顶点ηkj值均为0时停止算法，求解出最小点覆盖集S1，并通过选择不同初始顶点，重复上述步骤依次类推求解出最小点覆盖集S2，S3，…，Sn(n为图G中顶点数)，在点覆盖数最少的集合中，选择点覆盖权值和∑w(j)最小的集合作为最终所求最小点覆盖集S，即：

S=Sj,∑w(j)=min∑w(j)

(4)

2.2 问题描述

问题1：由于在采用上述改进蚁群算法进行最小点覆盖集求解过程中，可能会存在同一顶点被重复选作最小覆盖集中的顶点，从而增加CPU计算的时间，降低探针部署效率，结合如图3所示的点边赋权图，解释具体计算冗余过程。

图3 点边赋权图

结合上述经改进蚁群算法步骤对图3中不同初始节点的最小点覆盖集进行计算，可得不同初始点下的最小点覆盖集，即：

(5)

根据式(5)中各最小点覆盖集计算结果可知：其中顶点a1、a3和a4均多次进行过重复计算[6]，由此会造成计算冗余，增加CPU计算时间。

问题2：由于在结合上述经改进蚁群算法进行各个覆盖集的下一顶点计算过程中，若各相邻顶点的动态启发因子ηkj值均为0，则停止计算，导致各最小点覆盖集的运算陷入一个局部区域的求解，从而使得计算结果无法同时兼顾局部最优与全局最优[7]，探针部署方案有待改进。

3 算法设计

3.1 构造点赋权图与初始解

在本文所提基于禁忌搜索与扰动策略的探针部署算法中，为求解最小点覆盖集，首先在无向图G=(V,E)中对各顶点赋予相应权值(ω(vi)≥0)，构建点赋权图[8]G′=(V,E′)，如图4所示。

图4 点赋权图

在构建初始顶点集合V′的过程中，针对未被探针部署顶点集合V′覆盖的边，结合贪心算法选择该边中权值较小的顶点，加入顶点集V′中，以保证覆盖所有边的最小点覆盖集V′中Wtotal值最小，即：

(6)

式中：Wtotal为所有顶点权值和，且满足：

∀(vi,vj)∈E′:vi∈V′or,vi∈V′(1≤i,j≤n,V′∈V)

(7)

如图4所示，边(v11、v16)未被顶点集V′覆盖，为保证顶点集合V′中所有顶点的权值和Wtotal最小，故选择权值较小的顶点v16加入顶点集V′中，并且定义集合V′中顶点为关键顶点，不在集合中顶点为非关键顶点，顶点集合V中任意一点可在关键顶点[9]与非关键顶点两种状态间切换。

3.2 快速邻域切换与禁忌表构建

通过邻域动作MV(vi)将初始解顶点集合V′进行有效解变换，以增强局部最优解[10]寻优能力，即：将上述初始解顶点集合V′中关键顶点vi切换为非关键顶点，并将顶点vi邻近节点中属于集合Vr(vi)的顶点全部切换为关键顶点，具体过程如图5所示。

图5 邻域动作过程示意图

由于进行邻域动作MV(B)将集合V′中顶点B移除，导致边(B,C)、(B,D)、(B,F)中均无关键顶点，为保证集合V′的合法性，将顶点C、D、F加入集合V′中，由此产生图5中右图所示经邻域变换的合法解。

执行一个上述邻域动作会引起相邻顶点状态变化，形成多个邻域解[11]，但由于该过程中只有部分关键顶点的权值ω(vi)发生变化，因此，为避免在邻域解的选择过程中，对集合中所有顶点的权值进行全面计算从而增加无效计算时间，本文所提基于禁忌搜索与扰动策略的探针部署算法通过引入评估函数EV(vi)，计算各邻域动作的增量目标函数值[12]，进行快速邻域切换以降低无效计算时间，评估函数EV(vi)计算如下：

(8)

结合图6中邻域动作MV(A)为例进行各相邻顶点EV(vi)值的计算，如图6所示。

图6 邻域动作示意图

在上述应用邻域动作对始解顶点集合V′进行优化的过程中，为防止在局部区域中陷入循环搜索，可结合禁忌搜索构建禁忌表对重复的邻域动作进行限制，以避免邻域动作陷入循环搜索，使用禁忌搜索具体方法如下：

(9)

当邻域动作MV(u)中涉及的关键顶点u与相邻非关键顶点集Vr(u)中顶点同时满足式⑼中条件时，则禁忌该邻域动作，否则予以执行。

3.3 应用扰动策略突破空间限制

图7 PDA-TSPS流程

4 实验与结果分析

4.1 评价指标

为充分比较改进的蚁群算法(IACA)与本文所提基于禁忌搜索与扰动策略的探针部署算法(PDA-TSPS)的求解效率与最小点覆盖集寻优能力，测试实验中采用不同迭代次数下两种算法的平均CPU计算时间(以秒为单位)以及不同规模算例集下两种算法各类解(better、equal和worse)在所有解集中所占的比例作为IACA与PDA-TSPS求解效率与寻优能力的评价指标。

4.2 测试环境及参数设置

测试环境：本文采用C语言进行测试实验编写，PC机配置为：CPU型号为AMD A6- 3400M，64位处理器，CPU主频为1.40 GHz，内存为8 GB。

参数设置：首先设置各种规模算例集测试场景(即所含顶点与边的数量不同的带权无向图G=(V,E))，假定一个测试算例集中顶点数量为n，边的数量为m；其次，根据顶点与边的数量不同将测试场景分为：小规模测试算例集(SPI)(n=500,m=500)、中等规模算例集(MPI)(n=1 000,m=1 000)、大规模算例集(LPI)(n=1 000,m=2 000)；最后，为保证实验结果有效验证IACA与PDA-TSPS的求解效率与寻有能力并降低计算冗余，故只在中等规模算例集(MPI)与大规模算例集(LPI)两类测试场景下对比两种算法的各类解比例与CPU计算时间，各类解中better类解集代表所有解集中高于平均值的最优解，equal类解集代表所有解集中处于平均值水平的中等解，worse类解集代表所有解集中低于平均值水平的较差解。

4.3 实验结果对比分析

首先分别在中等规模算例集(MPI)与大规模算例集(LPI)场景下测试IACA与PDA-TSPS，并分别统计两种场景下算法的CPU计算时间，统计情况如图8所示。

图8 算法CPU计算时间统计情况

根据图8中算法测试的CPU计算时间统计结果分析得出：本文所提基于禁忌搜索与扰动策略的探针部署算法(PDA-TSPS)相较于改进的蚁群算法(IACA)，其CPU计算时间明显较低，计算效率更高；在大规模算例集(LPI)场景下，PDA-TSPS算法对计算效率的提升更为明显，故本文PDA-TSPS算法普遍适用。

为充分体现实验统计结果中各类解集合的有效性及合理性，将中等规模算例集(MPI)与大规模算例集(LPI)场景下的各个算例最大测试时间均设定为600 s(提升两类算法在设定时限内找到最优解的概率)，中等规模算例集(MPI)由40个中等规模算例组成，大规模算例集(LPI)由15个(由于各个大规模算例计算复杂度较高，故集合中算例个数不宜设置过大)大规模算例组成，各个算例均在同一规模类别初始条件(n、m数值)下随机生成；为降低算法迭代过程中带来的误差，各类规模算例集中每个算例均对应10个问题实例，后续统计结果中每个算例所得解均为所对应10个问题实例所得函数值的平均值。

其次，分别统计在中等规模算例集(MPI)场景下，IACA与PDA-TSPS各类解集(better、equal和worse)在所有解集中所占的比例，统计结果如图9所示。

图9 MPI场景下各类解集占比统计情况

由图9的统计结果可知，在中等规模算例集(MPI)下，PDA-TSPS相较IACA其better类解集所占比例较高，worse类解集占比较低。与此同时，分别统计在大规模算例集(LPI)场景下，IACA与PDA-TSPS各类解集(better、equal和worse)在所有解集中所占的比例，统计结果如图10所示。

图10 LPI场景下各类解集占比统计情况

根据图10的统计结果可知，在大规模算例集(LPI)场景下，PDA-TSPS相较IACA其better类解集所占比例较高，且所有解集合中worse类解集占比为0。

5 结 语

本文提出一种基于禁忌搜索与扰动策略的探针部署算法，通过快速邻域动作切换、禁忌表构建以及扰动策略强化了算法在局部区域中的求解能力，降低了计算时间，突破了空间限制，使所得最小点覆盖集合同时达到局部最优与全局最优。实验结果表明：本文基于禁忌搜索与扰动策略的探针部署算法相较于改进的蚁群算法，其求解最优解速率更快，适用场景更广，寻优方法更为合理。