文献类型：期刊文章

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

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

出　　处：《中国科学：信息科学》

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

年　　份：2016

卷　　号：46

期　　号：4

起止页码：445-460

语　　种：中文

收录情况：BDHX、BDHX2014、CSCD、CSCD2015_2016、JST、RCCSE、ZGKJHX、核心刊

摘　　要：本文提出了一种求解最小连通支配集问题的变深度邻域搜索(VDNS)算法.结合最小连通支配集问题的特点,VDNS算法采用了一种高效的邻域结构,该邻域结构由一系列基础邻域动作组成,合理地限制了搜索空间,提高了算法的搜索效率.同时,本文还提出了两种提高算法搜索效率的方法:修剪搜索分支以及增量评估更新技术.用本文提出的VDNS算法对当前国际文献公开的共91个算例进行了测试,VDNS算法能够在非常短的计算时间内改进其中38个算例,优于此前国际文献中报道的最好结果,表明了本文所提出的VDNS算法的有效性.

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

分 类 号：TP301.6]