支配集问题的局部搜索算法研究

Dominating set problem is a classical NP-hard problem with many applications. Although local search algorithms for solving dominating set problems have attracted wide attention by many researchers, there still exist lots of problems in the solving scale and the solving efficiency. There exist many large-scale instances where the number of vertices is often more than one million in social networks and wireless sensor network, which puts forward a huge challenge to design local search algorithms for solving dominating problems. This project will concentrate on designing local search algorithms for solving dominating set problems. There are three main factors for affecting the solving efficiency of local search algorithms: the quality of the initial solution; introducing the jumping strategy to escape from local optimal; the design of heuristic scoring function and the selection of the candidate vertices. Therefore, the project will design the preprocessing procedure and initialization algorithms through mining the hidden structure and special vertices of the problem; proposing a new cycling avoidance strategy and a fast perturbation strategy to help algorithms escape from local optimal (i.e. avoiding algorithms falling into some candidate solutions and sub-optimal feasible space); introducing some heuristic searching strategies for overcoming the problems that the number of candidate vertices is too large and that algorithms are difficult to find some search spaces.

支配集问题是NP困难类的经典问题之一，被广泛应用于众多实际问题领域中。尽管支配集及其相关问题的局部搜索算法受到了研究人员的日益关注，但在求解规模和求解效率上尚存在很多不足。在社交网络和无线传感网络等实际问题中，往往需要处理节点数超过百万级别的超大规模测试用例，这也为目前支配集问题的局部搜索求解算法的设计提出了巨大的挑战。本项目将围绕设计支配集及其相关问题的局部搜索算法展开。由于影响局部搜索算法求解效率的三个关键因素在于初始解的质量、算法陷入局部最优时的跳出策略以及启发式打分函数的设计和分支节点的选择，本项目将开展以下三个方面的研究：通过挖掘问题的隐藏结构和特殊顶点，设计有效的预处理和初始解构造方法；提出全新的循环避免策略和快速扰动策略以帮助算法跳出局部最优，即避免算法循环搜索某些解或次优解空间；同时针对候选顶点过多和很难搜索到某些解空间等问题，设计可以处理超大规模问题的启发式搜索策略。

支配集问题是NP困难类的经典问题之一，被广泛应用于众多实际问题领域中。尽管支配集及其相关问题的局部搜索算法受到了研究人员的日益关注，但在求解规模和求解效率上尚存在很多不足。在社交网络和无线传感网络等实际问题中，往往需要处理节点数超过百万级别的超大规模测试用例，这也为目前支配集问题的局部搜索求解算法的设计提出了巨大的挑战。本项目围绕设计支配集及其相关问题的局部搜索算法展开，开展的具体研究工作包括：1）针对最小支配集问题，设计了一个高效的局部搜索框架，克服了之前支配集求解算法收敛速度过慢的问题，同时在预处理过程，使用了轻量级的化简策略，在化简策略复杂性和化简策略有效性之间做到了很好的平衡；2）针对连通支配集的无权问题和有权问题，为了在求解大规模测试用例中保持连通约束，设计一套基于生成树维护连通约束的方法。另外，由于连通支配集问题的自身特性，使得求解算法很容易陷入局部最优，因此提出了一种内嵌式的局部搜索框架来实现扰动候选解的目的。对一些几百万顶点的稀疏图可以很快地求得令人满意的解，而之前最好的算法耗时超过1小时仍然不能得到解；3）针对独立支配集的无权问题和有权问题，充分利用并学习历史搜索信息，利用这些学习得到的信息来辅助求解算法重新构造候选解。基于上述成果，总共发表学术论文14篇，其中中国计算机学会推荐A类论文5篇。协助培养博士生研究生1名，硕士研究生3名。本项目的研究将有助于促进局部搜索算法在支配集问题中的发展，同时也为求解图论中其他全局最优问题提供了有价值的解决方法。