基于雪堆博弈进化的复杂网络节点覆盖方法

摘要

本发明公开了一种基于雪堆博弈进化的复杂网络节点覆盖方法，主要解决现有技术无法准确求得复杂网络最小节点覆盖的问题。其实现步骤是：(1)设定种群规模S和代数G，随机产生S个个体构成父代种群；(2)从父代种群中随机选两个个体作交叉和突变，得到四个准子代个体，并对其分别作无记忆雪堆博弈，再从中选择评价函数值较小的两个准子代个体作为新个体；(3)重复步骤(2)直到产生S个新个体，作为新的父代种群，完成一次种群更新；(4)在新父代种群基础上，重复步骤(2)-(3)完成G次种群更新；将最终种群中评价函数值最小的个体作为最小节点覆盖结果。本发明能求出复杂网络的最小节点覆盖结果，可用于分布规划和网络优化。

主权项

一种基于雪堆博弈进化的复杂网络节点覆盖方法，包括如下步骤：(1)根据复杂网络的规模N设定进化种群规模S和代数G，用S个个体构成一个父代种群，个体代表复杂网络的一个覆盖结果，即复杂网络中所有N个节点状态的集合；初始化每个个体中每个节点的状态为覆盖状态C或未覆盖状态D；(2)从父代种群中随机选择两个个体作为父代个体进行两点交叉，以将两个父代个体扩展为四个个体，再对该四个个体进行突变操作，得到四个变异后的准子代个体；(3)对四个准子代个体分别进行无记忆雪堆博弈，得到四个优化后的准子代个体，再计算这四个优化后的准子代个体各自的评价函数f(X)值，选择其中评价函数f(X)值较小的两个个体，作为子代种群中的新个体，并从父代种群中删除(2)中的两个父代个体；(4)重复步骤(2)‑(3)直到产生S个新个体，用这些新个体构成子代种群，再将该子代种群作为新的父代种群，完成一次种群更新；(5)在新的父代种群的基础上，重复步骤(2)‑(4)直到完成G次种群更新；(6)将最后一次更新的父代种群中的评价函数f(X)值最小的个体作为复杂网络的最小节点覆盖结果。