求解最小连通支配集问题的变深度邻域搜索算法  

Variable-depth neighborhood search algorithm for the minimumconnected dominating-set problem

作　　者：王灵敏 周淘晴[2,3] 吴歆韵 吕志鹏[3] 

机构地区：[1]中国船舶工业系统工程研究院,北京100036 [2]浙江农林大学信息工程学院计算机系,杭州311300 [3]华中科技大学计算机科学与技术学院智慧计算与优化实验室,武汉430074

出　　处：《中国科学：信息科学》2016年第4期445-460,共16页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61370183;61100144);2013教育部新世纪优秀人才支持计划资助项目

摘　　要：本文提出了一种求解最小连通支配集问题的变深度邻域搜索(VDNS)算法.结合最小连通支配集问题的特点,VDNS算法采用了一种高效的邻域结构,该邻域结构由一系列基础邻域动作组成,合理地限制了搜索空间,提高了算法的搜索效率.同时,本文还提出了两种提高算法搜索效率的方法:修剪搜索分支以及增量评估更新技术.用本文提出的VDNS算法对当前国际文献公开的共91个算例进行了测试,VDNS算法能够在非常短的计算时间内改进其中38个算例,优于此前国际文献中报道的最好结果,表明了本文所提出的VDNS算法的有效性.This paper presents a variable-depth neighborhood search（VDNS） algorithm for solving the minimumconnected dominating-set problem.By considering the problem structure of the minimum-connected dominatingset problem,this paper introduces an effective partition-based neighborhood structure,which consists of a series of basic neighborhood moves,restricts the search space to traverse towards more promising search regions,and generates better solutions during the search.This paper also presents two techniques to further improve the search efficiency of the algorithm：pruning the search branch,and the incremental evaluation technique.Applying the proposed VDNS algorithm to solve the 91 public instances used in the literature,VDNS outperforms the referencealgorithms in the literature by improving 38 of the best-known results,demonstrating the efficacy of the proposed VDNS algorithm.

关 键 词：元启发式算法 变深度邻域搜索 邻域结构 最小连通支配集 增量更新 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]