Hybrid Tabu Search and Genetic Algorithm for Solving Minimum Dominating Set Problem
The minimum dominating set problem can be transformed into a series of decision problems-the k dominating set(k DS)problem and a hybrid tabu search and genetic(TSG)algorithm for solving the k DS problem is proposed.The algorithm combines a tabu search algorithm and a genetic algorithm.The ef-ficient neighborhood structure is used to ensure the efficiency of the algorithm,the tabu strategy is used to prevent the algorithm from falling into the local optimal trap,and the genetic algorithm framework is used to further enhance the evacuation of the algorithm.Compared with the existing algorithms for solving the minimum dominating set problem,the result of proposed algorithm outperforms the others.
minimum dominating setNP hard problemhybrid tabu search and genetic algorithmk-dom-inating set
万方数据
维普
