一种求解基于距离的关键节点问题的进化路径重连方法

本发明涉及复杂网络分析与组合优化，尤其涉及一种求解基于距离的关键节点问题的进化路径重连方法。

背景技术：

1、现实世界中的许多复杂系统常可抽象为网络模型，网络模型中的节点表示系统中的实体，边则刻画实体之间的交互关系。在许多实际应用场景中，网络中通常存在若干关键节点，一旦这些节点被移除，网络的特定功能将受到显著影响，从而对系统整体稳定性构成威胁。因此，如何准确识别这些关键节点（简称"关键节点检测问题"）已成为广受关注的研究领域。该关键节点检测问题在流行病防控、恐怖组织网络瓦解、金融风险传播分析以及社交网络舆情监测等诸多领域具有重要应用价值。例如，在流行病防控中，决策者需要在资源有限的情况下，准确筛选出应优先隔离或接种疫苗的人群，以最大限度的降低疾病在社会网络中的传播风险；在识别中心化空壳公司时，可以通过分析企业信用网络中的关键节点，有效追溯并定位潜在的风险传播源。

2、关键节点问题(criticalnodeproblem,cnp)是关键节点检测问题中最基础的模型，其目标是给定无向图  ，其中  为节点集合，  为连接节点的边集合，通过删除无向图  中有限个节点构成的子集  ，来最小化残余图的连通性，这里的连通性通常以残余图中两两相连的节点对数量来度量，即cnp的目标函数  可以形式化表示为  ，其中  是残余图  中第  个连通分量，  表示残余图  中连通分量的个数。

3、然而，cnp在评价两个节点之间是否相连时，仅仅考虑两个节点之间是否存在路径相连，忽略了这些路径的"质量"，无法准确刻画其真实的连通强度。基于距离的关键节点问题(distance-basedcriticalnodeproblem,dcnp)是cnp的重要拓展，其在评价两个节点之间是否相连时不仅要求这两个点之间存在路径，还要求连通两点的最短路径长度不超过给定阈值  。给定无向图  和预算约束  ，dcnp旨在从图  中寻找总权重不超过  的节点子集  ，使得从无向图  中删除并隔离这些节点后，残余图的基于距离的连通性最小。dcnp可以形式化地定义为  。其中  表示节点  和节点在残余图  中的距离，即最短路径长度；  为一种基于距离的连通性度量函数；  为节点  和节点  相连的成本，  为节点  的权重。对于残余图中任意不连通的两个节点  和  ，其距离定义为  。

4、目前，针对dcnp的求解方法主要分为精确算法和启发式算法两类。精确算法方面，已有基于整数线性规划的模型及其改进，例如截断-重解算法、基于benders分解的方法、thin模型和path-like模型，这些方法虽然可以保证所获得解的最优性，但随着节点数量的增加，模型规模迅速膨胀，通用求解器难以在合理时间内处理大规模实例，通常仅适用于中小规模的问题算例。启发式算法方面，已有基于中心性的启发式算法和快速三个体模因搜索算法（fasttri-individualmemeticsearch,ftms），但现有启发式算法普遍存在时间复杂度高、求解质量不稳定等问题，难以满足大规模复杂网络应用场景的实际需求。

5、因此，本发明提出一种求解基于距离的关键节点问题的进化路径重连方法以解决上述问题。

技术实现思路

1、本发明要解决的技术问题是提供一种求解基于距离的关键节点问题的进化路径重连方法（evolutionarypathrelinking,epr），对基于距离的关键节点问题实现高效率、高质量求解，提升在复杂应用场景下的求解能力。

2、为解决上述技术问题，本发明的技术方案为：一种求解基于距离的关键节点问题的进化路径重连方法，其创新点在于：包括以下步骤：

3、s1、通过知识驱动的种群初始化程序，生成包含  个个体的初始种群，并记录当前全局最优解；

4、s2、从当前种群中选择引导解和初始解，运用内部路径重连操作，生成后代解；

5、s3、检验当前后代解是否有改进，若是，则直接进入步骤s4，若否，则采用频繁项集驱动的解重构策略对后代解进行重构；

6、s4、对当前后代解执行基于割点的局部搜索，并更新全局最优解；

7、s5、按照基于相似性的种群管理程序，利用当前后代解对当前种群进行更新；

8、s6、重复步骤s2-s5，直到满足设定的停止条件，得到问题的最优解。

9、进一步地，步骤s1所述的通过知识驱动的种群初始化程序生成初始种群的具体步骤包括：

10、s1.1、计算无向图中每个节点的介数中心性，根据计算获得的各节点介数中心性，按照由高到低的顺序对无向图中所有节点进行排序；

11、s1.2、依照排序结果，按概率顺序选取节点，构建高质量的可行解，可行解表示为包含至多  个节点的节点集合，其中  为预算约束；

12、s1.3、检验生成的可行解是否与当前种群中已有的可行解存在重复，如果不重复，则直接执行步骤s1.4，如果存在重复，则执行交换算子，在当前无向图的剩余候选节点中，寻找并选取使目标函数值下降幅度最大的节点，并将所选取的节点加入当前可行解的节点集合中，再从当前可行解的节点集合中随机移除一个现有节点，重复执行这一过程，直至当前可行解与当前种群中所有已有解均不相同，进入步骤s1.4；

13、s1.4、计算当前可行解的目标函数值，并判断是否优于当前全局最优解的目标函数值，若是，则以当前可行解更新全局最优解；

14、s1.5、重复步骤s1.2-1.4，直至当前种群中互不相同的可行解数量达到预设的种群规模  ，形成以可行解为个体、包含  个个体的初始种群。

15、进一步地，步骤s2中所述的运用内部路径重连操作生成后代解的具体步骤包括：

16、s2.1、采用内部路径重连ipr生成后代解：首先从当前种群中随机选取若干个体，构成参考集  ，从参考集  中选择目标函数值最小的个体作为引导解  ，并从参考集  中随机选在一个不同于引导解  的个体作为初始解  ，以初始解  为后代解  进行初始化赋值；

17、s2.2、定义内部路径重连ipr的阈值  为ipr相似度阈值参数  与种群规模的乘积，即  ；

18、s2.3、计算当前引导解  与当前后代解  中相同节点的数量，判断相同节点的数量是否小于阈值  ，若否，则直接执行步骤s2.4，若是，则执行节点交换操作后，再进入步骤s2.4，所述节点交换操作为：

19、从当前后代解  中剔除一个节点  ，该节点  从集合  中随机选取，即选取当前属于后代解  但不属于引导解  的节点；

20、向当前后代解  中添加一个节点  ，该节点  从集合  中按照贪婪策略选取规则选取，即在所有属于引导解  但尚未被当前后代解  包含的节点中，选取加入当前后代解  后使目标函数值取得最小值的节点，贪婪策略选取规则表示为：

21、

22、其中，  表示将节点  加入后代解  后的目标函数值，表示目标函数值  取得最小值时对应的变量取值；

23、s2.4、计算并更新当前后代解  的目标函数值；

24、s2.5、重复步骤s2.3-2.4，直至当前引导解  和当前后代解  中相同节点数量达到阈值  。

25、进一步地，步骤s3中所述的采用频繁项集驱动的解重构策略对后代解进行重构的具体步骤包括：

26、s3.1、在当前种群中随机选取  个个体，  ，统计无向图中所有节点在这个个体中的出现次数；

27、s3.2、根据各节点的出现次数，将出现次数等于  的节点视为频繁节点，并加入频繁项集  中，将出现  次的节点加入第一候选集合  中，出现次数小于  次的其余节点加入第二候选集合  中；

28、s3.3、判断频繁项集  中的节点数量是否达到预算约束  ，若频繁项集中的节点数量达到预算约束  ，则直接以频繁项集  作为重构后的后代解，若频繁项集  中的节点数量没有达到预算约束  ，则先将频繁项集  内的所有节点复制到新的后代解  中，即  ，再随机选择一种补齐方式为  添加节点，重复执行补齐过程，直至后代解  中的节点数量达到预算约束  ，获得完整的重构后代解。

29、进一步地，所述补齐方式包括：

30、补齐方式一、运用贪婪算法在残余图中寻找使目标函数值下降幅度最大的节点加入后代解s'中；

31、补齐方式二、从第一候选集合  和第二候选集合  中随机选择节点加入，其中，从第一候选集合  中选择节点的概率为  ，从第二候选集合  中选择节点的概率为  。

32、进一步地，步骤s4中所述的基于割点的局部搜索的具体步骤包括：

33、s4.1、在无向图中在去除当前后代解  所包含的节点后形成当前残余图，计算当前残余图中每个节点的介数中心性，按照介数中心性由高到低的顺序对当前残余图中所有节点进行排序，选择排名前  名的节点形成候选节点列表  ，其中

34、

35、s4.2、从候选节点列表  中随机选取一个节点  ，检验该随机选取的节点是否已包含在当前后代解  中，若否，则直接执行步骤s4.3，若是，则从候选节点列表中重新随机选取另一节点，直至选取到未包含在当前后代解  中的节点  ；

36、s4.3、利用tarjan算法检验节点  是否为割点，若节点  是割点，则直接将节点  加入到当前后代解  中，若节点  不是割点，则根据割点选择概率参数  决定是否将节点  加入当前后代解  中；

37、s4.4、节点  加入后，在当前后代解  中贪婪地移出使目标函数值上升幅度最小的节点  ，并将节点  放回候选节点列表  中，保持后代解  中节点数量不超过预算约束  ；

38、s4.5、判断当前后代解  的目标函数值是否优于当前全局最优解的目标函数值，若是，则以当前后代解  更新全局最优解，同时以当前后代解  的目标函数值更新全局最优解的目标函数值，若否，则重复执行步骤s4.2-s4.4，直至重复执行次数达到上限后停止。

39、进一步地，步骤s5中所述的基于相似性的种群管理程序，利用当前后代解对当前种群进行更新的具体步骤包括：

40、s5.1、检验当前种群中是否存在与当前后代解  目标函数值相同的个体，若存在，则跳过本次种群更新，直接执行步骤s6，若不存在，则执行步骤s5.2；

41、s5.2、对当前种群中的最差个体进行更新：比较当前后代解  与当前种群中最差个体  的目标函数值，若当前后代解  的目标函数值优于最差个体  的目标函数值，则用当前后代解  替换最差个体  ，并更新相应的目标函数值；

42、s5.3、根据解相似性的定义，计算当前种群内所有个体之间的相似度矩阵，并计算所有个体的平均相似度  ；

43、s5.4、设定相似度上限参数  和相似度下限参数  ，当  时，采用随机节点更换策略对当前种群个体进行变异操作；当  时，则对当前种群的最差个体执行基于割点的局部搜索操作。

44、进一步地，所述解相似性的定义为：给定两个个体  和  ，这两个个体  和  之间的相似性  定义为  和  中相同节点所占的比例：

45、

46、其中，  表示  和  中相同节点的数量，  表示  中的节点总数，  即为  和  中相同节点所占的比例，两个个体中相同的节点数越多，相似性越高。

47、进一步地，步骤s6中所述的停止条件为运行时间达到预设的最大值或迭代次数超过最大未更新迭代次数。

48、本发明的优点在于：

49、本发明的求解基于距离的关键节点问题的进化路径重连方法，以内部路径重连为核心搜索算子，并集成了四个高效的模块：知识驱动的种群初始化以生成高质量的初始种群，基于割点的局部搜索对后代解进行深度局部优化，频繁项集驱动的解重构在路径重连未能取得改进时对后代解进行重构，以及基于相似性的种群管理策略在种群质量与多样性之间取得平衡，实现了对基于距离的关键节点问题的高效率、高质量求解，提升了在复杂应用场景下的求解能力，具有求解质量高、收敛速度快、应用范围广等优点。