基于雪堆博弈变异搜索的复杂网络节点覆盖方法

摘要

本发明公开了一种基于雪堆博弈变异搜索的复杂网络节点覆盖方法，利用雪堆博弈模型和进化搜索思想，用以快速获得较优的网络最小节点覆盖结果。其实现主要步骤是：(1)根据待处理网络的大小N设定算法参数，初始化当前最优解保持次数，随机初始化节点的记忆和策略，依基于记忆的最优反应规则(MBR)得到初始解后作为当前最优解；(2)根据当前最优解保持次数确定变异节点个数，对当前最优解随机选取若干个节点进行变异操作；(3)依MBR规则博弈更新，得到的结果如果优于当前最优解，则替换之；(4)在当前最优解的基础上，重复“变异‑邻域搜索”操作，直到当前最优解保持连续若干次不被更新，则结束。算法终止时的当前最优解即为最终结果。本发明能高效处理各种网络的最小节点覆盖问题，对不同连接结构的网络有很强的适应能力，进化搜索大大减小了陷入局部最优的风险。