[1]吴歆韵,彭　瑞,熊才权.求解最小支配集问题的禁忌遗传混合算法[J].湖北工业大学学报,2024,39(2):17-22.
　WU Xinyun,PENG Rui,XIONG Caiquan.Hybrid Tabu Search and Genetic Algorithm for Solving Minimum Dominating Set Problem[J].,2024,39(2):17-22.
点击复制

求解最小支配集问题的禁忌遗传混合算法()
分享到：

《湖北工业大学学报》[ISSN:1003-4684/CN:42-1752/Z]

卷:
39
期数:
2024年第2期
页码:
17-22
栏目:
出版日期:
2024-04-20

文章信息/Info

Title:
Hybrid Tabu Search and Genetic Algorithm for Solving Minimum Dominating Set Problem
文章编号:
1003-4684(2024)02-0017-06
作者:
吴歆韵; 彭　瑞; 熊才权
湖北工业大学计算机学院,湖北 武汉 ４３００６８
Author(s):
WU Xinyun;  PENG Rui;  XIONG Caiquan
School of Computer Science, Hubei Univ. of Tech., Wuhan 430068, China
关键词:
最小支配集; NP难问题; 禁忌遗传混合算法; k 支配集
Keywords:
minimum dominating set;  NP hard problem;  hybrid tabu search and genetic algorithm;  kdominating set
分类号:
TP393
文献标志码:
A
摘要:
将最小支配集问题转换为一系列判定问题 k 支配集问题,并提出一种禁忌遗传混合算法对kＧDS问题进行求解.此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来,互补不足.高效的邻域结构保证了算法的运行效率,禁忌策略防止算法过早陷入局部最优陷阱,遗传算法框架进一步增强了算法的疏散性.经过与现有求解最小支配集算法的结果进行分析比较,禁忌遗传混合算法的结果较其它算法更优.
Abstract:
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.

参考文献/References:

[１]　YANG XS．NatureＧinspiredmetaheuristicalgorithms[M]．Bristol:Luniverpress,２０１０．[２]　胡书丽．启发式搜索 算 法 求 解 组 合 优 化 问 题 的 研 究[D]．长春:东北师范大学,２０１９．[３]　HEDAR A R,ISMAIL R．Hybridgeneticalgorithmforminimum dominatingsetproblem[C]．∥InternaＧtionalconferenceoncomputationalscienceanditsapＧplications． Springer, Berlin, Heidelberg, ２０１０:４５７Ｇ４６７．[４]　WU X,L? Z,GALINIERP．RestrictedswapＧbasedneighborhoodsearchfortheminimumconnecteddomiＧnatingsetproblem [J]．Networks,２０１７,６９(０２):２２２Ｇ２３６．[５]　HEDAR A R,ISMAIL R．Simulatedannealingwithstochasticlocalsearchfor minimum dominatingsetproblem[J]．InternationalJournalofMachineLearningandCybernetics,２０１２,３(０２):９７Ｇ１０９．[６]　ROMANIA Q S．Antcolonyoptimizationappliedtominimum weightdominatingsetproblem[C]．∥ProＧceedingsofthe１２th WSEASinternationalconferenceonautomaticcontrol,modellingandsimulation．CataＧnia,Italy．２０１０:２９Ｇ３１．[７]　FAN Y,LAIY,LIC,etal．Efficientlocalsearchforminimumdominatingsetsinlargegraphs[C]．∥InterＧnationalConferenceonDatabaseSystemsforAdvancedApplications．Springer,Cham,２０１９:２１１Ｇ２２８．[８]　CHALUPAD．AnorderＧbasedalgorithmforminimumdominatingsetwithapplicationingraph mining[J]．InformationSciences,２０１８,４２６:１０１Ｇ１１６．[９]　CHVATALV．AgreedyheuristicforthesetＧcoveringproblem [J]．Mathematics of operations research,１９７９,４(０３):２３３Ｇ２３５．[１０]POTLURIA,SINGH A．Twohybrid metaＧheuristicapproachesforminimumdominatingsetproblem[C]．∥InternationalConferenceonSwarm,Evolutionary,and Memetic Computing．Springer,Berlin,HeidelＧberg,２０１１:９７Ｇ１０４．[１１]POTLURIA,SINGH A．Hybrid metaheuristicalgoＧrithmsfor minimum weightdominatingset[J]．ApＧpliedSoftComputing,２０１３,１３(０１):７６Ｇ８８．[１２]CAIS,HOU W,WANG Y,etal．TwoＧgoallocalsearchandinferencerulesforminimumdominatingset[C]．∥ProceedingsoftheTwentyＧNinthInternationalConferenceonInternationalJointConferencesonArtiＧficialIntelligence．２０２１:１４６７Ｇ１４７３．

相似文献/References:

[1]程咏锋,吴歆韵,熊才权.求解最小支配集的线性混合整型规划算法[J].湖北工业大学学报,2022,(1):29.
　CHENG Yongfeng,WU Xinyun,XIONG Caiquan. A Hybrid Integer Linear Programming Algorithm for Solving the Minimum Dominating Set[J].,2022,(2):29.

备注/Memo

备注/Memo:
[收稿日期]２０２２- ０８- ２１[基金项目]国家自然科学基金(６１９２１１６)[第一作者]吴歆韵(１９８７－),男,湖北宜昌人,湖北工业大学副教授,研究方向为优化算法.
更新日期/Last Update: 2024-05-07