[1]桂文杰,吴歆韵,熊才权.求解最小双连通支配集问题的变邻域禁忌搜索算法[J].湖北工业大学学报,2024,39(1):68-74.
　GUI Wenjie,WU Xinyun,XIONG Caiquan.Variable Neighborhood Tabu Search for Solving Minimum Biconnected Dominating Set Problem[J].,2024,39(1):68-74.
点击复制

求解最小双连通支配集问题的变邻域禁忌搜索算法()
分享到：

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

卷:
39
期数:
2024年第1期
页码:
68-74
栏目:
出版日期:
2024-02-20

文章信息/Info

Title:
Variable Neighborhood Tabu Search for Solving Minimum Biconnected Dominating Set Problem
文章编号:
1003-4684(2024)01-0068-07
作者:
桂文杰; 吴歆韵; 熊才权
(湖北工业大学计算机学院,湖北 武汉 ４３００６８)
Author(s):
GUI Wenjie; WU Xinyun; XIONG Caiquan
(School of Computer，Hubei Univ. of Tech.，Wuhan 430068，China)
关键词:
元启发式算法; 最小双连通支配集; 变邻域搜索算法; 禁忌算法; 双连通图
Keywords:
A meta heuristic algorithm;  minimum biconnected dominating set;  variable neighborhood search algorithm;  tabu search algorithm;  biconnected graph
分类号:
TP393
文献标志码:
A
摘要:
针对经典 NP难优化问题———最小双连通支配集问题,提出了一种元启发式求解算法———变邻域禁忌搜索算法.算法将原优化问题的求解转换为一系列判定问题———k 双连通支配集问题的求解,使用两种邻域结构更加有效地覆盖解空间,同时使用扰动及禁忌机制帮助算法跳出局部最优陷阱.通过与现有文献中的精确算法、启发式算法在国际文献公开的３８个双连通图算例上的实验对比,结果表明变邻域禁忌搜索算法能够有效求解最小双连通支配集问题,可求得所有公开算例的最优解,并且在稠密图中计算效率明显优先于其他算法.
Abstract:
The minimum biconnected dominating set structure is used to construct a fault tolerant virtual back bone network of wireless sensor networks. A variable neighborhood tabu search algorithm (VNTS), is proposed to solve the minimum biconnected dominating set problem, which is a classical NP hard optimization problem. The algorithm transforms the original optimization problem into a series of decision problems, the k biconnected dominating set problem, and uses two neighborhood structures to cover the solution space more efficiently. Meanwhile, a perturbation and a tabu mechanism are implemented to help the algorithm escape from the local optimal trap. The experiment on 38 public instances of biconnected graphs compares the proposed algorithms with the exact and heuristic algorithms in the literature. The results show that the VNTS algorithm is competitive in solving the minimum biconnected dominating set problem. It obtains the optimal solutions of all the instances and outperforms other algorithms on dense graphs in terms of computational efficiency.

参考文献/References:

[１]　潘玉兰,刘广聪．无线传感器网络的特点和应用[J]．电子技术与软件工程,２０１９(０４):１４Ｇ１５．[２]　 HASAN M Z,ALＧTURJMAN F．Optimizing mulＧ　第３９卷第１期　　　　　　　　　桂文杰,等　求解最小双连通支配集问题的变邻域禁忌搜索算法 ７３tipathroutingwithguaranteedfaulttoleranceinInterＧnetofThings [J]．IEEESensorsJournal,２０１７,１７(１９):６４６３Ｇ６４７３．[３]　BUCHANANA,SUNGJS,BUTENKOS,etal．AnintegerprogrammingapproachforfaultＧtolerantconＧnecteddominatingsets[J]．InformsJournalonComＧputing,２０１５,２７(０１):１７８Ｇ１８８．[４]　FORTEVD,LUCENAA,MACULANN．FormulaＧtionsforthe minimum ２Ｇconnected dominating setproblem [J]．ElectronicNotesinDiscrete MathematＧics,２０１３,４１:４１５Ｇ４２２．[５]　WU,WEILI,ZHANG,etal．AgreedyalgorithmfortheminimumＧconnectedＧfolddominatingsetproblem[J]．JournalofCombinatorialOptimization,２０１６,３１(０１):１３６Ｇ１５１．[６]　AHN N,PARKS．Anoptimizationalgorithmfortheminimum kＧconnected mＧdominatingsetproblem inwirelesssensor networks [J]．Wireless Networks,２０１５,２１(０３):７８３Ｇ７９２．[７]　NutovZ．ImprovedapproximationalgorithmsforkＧconnectedmＧdominatingsetproblems[J]．InformationProcessingLetters,２０１８,１４０:３０Ｇ３３．[８]　JOVANOVIC R,BAYRAMI．S,VO?S．A GRASPapproachforsolvingthe２ＧconnectedmＧdominatingsetproblem [J]．CoRR,２０１６．Abs/１６０９．０５６６２．[９]　JOVANOVICR,TUBA M,VO?S．A multiＧheuristicapproachforsolvingthepreＧmarshallingproblem[J]．Central European Journalof Operations Research,２０１７,２５(０１):１Ｇ２８．[１０]JOVANOVICR,VO?S．A MatheuristicApproachforSolvingthe２ＧConnectedDominatingSetProblem[J]．ApplicableAnalysisandDiscreteMathematics,２０２０,１４(０３):７７５Ｇ７９９．[１１]GLOVERF,GREENBERG HJ．Newapproachesforheuristicsearch:AbilaterallinkagewithartificialinＧtelligence[J]．EuropeanJournalof OperationalReＧsearch,１９８９,３９(０２):１１９Ｇ１３０．[１２]HOPCROFT J,Tarjan R,Efficientalgorithmsforgraphmanipulation[J]．CommunicationoftheACM,１９７３,１６(０６):３７２Ｇ３７８．

备注/Memo

备注/Memo:
[收稿日期]２０２２ -０８- ２３[基金项目]国家自然科学基金(６１９０２１１６)[第一作者]桂文杰(１９９６－),男,湖北荆门人,湖北工业大学硕士研究生,研究方向为图的支配集问题的启发式算法.[通信作者]吴歆韵(１９８７－),男,江苏丹阳人,工学博士,湖北工业大学副教授,研究方向为组合优化问题的启发式算法.
更新日期/Last Update: 2024-03-19