求解最小支配集问题的禁忌遗传混合算法  

Hybrid Tabu Search and Genetic Algorithm for Solving Minimum Dominating Set Problem

作　　者：吴歆韵 彭瑞 熊才权[1] WU Xinyun;PENG Rui;XIONG Caiquan(School of Computer Science,Hubei Univ.of Tech.,Wuhan 430068,China)

机构地区：[1]湖北工业大学计算机学院,湖北武汉430068

出　　处：《湖北工业大学学报》2024年第2期17-22,共6页Journal of Hubei University of Technology

基　　金：国家自然科学基金(6192116)。

摘　　要：将最小支配集问题转换为一系列判定问题k支配集问题,并提出一种禁忌遗传混合算法对k-DS问题进行求解。此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来,互补不足。高效的邻域结构保证了算法的运行效率,禁忌策略防止算法过早陷入局部最优陷阱,遗传算法框架进一步增强了算法的疏散性。经过与现有求解最小支配集算法的结果进行分析比较,禁忌遗传混合算法的结果较其它算法更优。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 efficient 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.

关 键 词：最小支配集 NP难问题 禁忌遗传混合算法 k支配集 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]