Research On Solving Algorithms Of Connected Dominating Set Problems

The minimum connected dominating set problem is an important combinatorial optimization problem,which is widely used in facility location,wireless sensor network,system biology and other fields.The dominating tree problem is an extension of the minimum connected dominance set problem.Because of their important theoretical research significance and practical application value,they have been widely concerned by researchers in recent years.This paper will focus on the minimum connected dominating set problem and the dominating tree problem solving algorithms.The algorithms for solving combinatorial optimization problems are mainly divided into two types: exact algorithm and heuristic algorithm.The exact algorithm can find the optimal solution to the problem,but with the increase of the scale of the problem,the storage space and computing time required to solve such problems increase exponentially,which will lead to the phenomenon of combination explosion,making the exact algorithm almost impossible to solve under the existing capacity.The heuristic algorithm can find an optimal solution or approximate optimal solution in a reasonable time.Therefore,the heuristic search algorithm is a good choice for the relatively large-scale problems without necessarily finding the optimal solution.In this paper,efficient heuristic search algorithms are designed to solve the minimum connected dominating set problem and the dominating tree problem.The main work of this paper is as follows:To tackle the minimum connected dominating set problem,firstly,we present the fitness mechanism to design the vertex score mechanism so that our algorithm can jump out of the local optimum.Secondly,we use the configuration checking(CC)mechanism to avoid the cycling problem.Then,we propose the vertex flipping mechanism to change the vertex state by combing the CC mechanism with the vertex score mechanism to guide the direction of local search.Finally,based on the above mechanisms,we proposed the multi-start local search algorithm to tackle the minimum connected dominating set problem.The results of the experiment show that our proposed algorithm is superior to other algorithms in solution quality and time efficiency.For the Type I instance,MSLS found optimal solutions for all 9 instances.For the Type II instance,MSLS improved 14 optimal solutions of 41 instances.For the Type III instance,MSLS obtained optimal solutions for all 41 instances.For solving the dominating tree problem.Firstly,we proposed the score functions Dscore and Wscore which are applied in the initialization and local search phase.Secondly,the initialization procedure with restricted candidate list(RCL)by controlling the parameter to balance the greediness and randomness,In the search phase,an iterated local search algorithm including three main phases of deleting phase,dominating phase and connecting phase is proposed to improve the quality of the initial solution.In addition,the mutation with high diversity proposed to perturb the population and increase the diversity of individuals.Finally,a hybrid algorithm based on genetic algorithm and iterated local search is proposed to solve the dominating tree problem.Experimental results show that our algorithm has good performance in solving the dominating tree problem.On 33 instances of the dtp group,our algorithm found 12 more optimal solutions than the VNS algorithm.On 18 instances of the range group,our algorithm and the ABC_DT algorithm can find the optimal solution,but for the average solution,our algorithm is better than the ABC_DT algorithm on 17 instances.