图着色问题禁忌搜索改进算法

doi:10.11896/jsjkx.211000128

计算机科学 ›› 2022, Vol. 49 ›› Issue (11A): 211000128-5.doi: 10.11896/jsjkx.211000128

图着色问题禁忌搜索改进算法

汪建昌, 王硕, 李壮, 江华

云南大学软件学院昆明 650504

出版日期:2022-11-10 发布日期:2022-11-21
通讯作者: 江华(huajiang@ynu.edu.cn)
作者简介:(1638131194@qq.com)

Improved Algorithm for Tabu Search of Graph Coloring Problems

WANG Jian-chang, WANG Shuo, LI Zhuang, JIANG Hua

School of Software,Yunnan University,Kunming 650504,China

Online:2022-11-10 Published:2022-11-21
About author:WANG Jian-chang,born in 1997,postgraduate.His main research interest is intelligent computing.
JIANG Hua,born in 1978,Ph.D,assistant professor,is a professional memberof China Computer Federation.His main research interests include practical algorithm solving for combinatorial optimization problems,algorithms for social network analysis and graph theory.

摘要/Abstract

摘要： 图着色问题是一个NP-hard问题,在现实中有广泛的应用,比如寄存器分配、机场调度等。禁忌搜索算法是一种经典的启发式搜索算法,在图着色问题的算法设计中广泛使用。禁忌搜索算法作为一个底层算子,也常被用于诸如混合进化算法(Hybrid Evolutionary Algorithm,HEA)的图染色算法设计中,对算法的性能起到了关键作用。因此,对禁忌搜索算法的改进对于促进图染色算法的研究具有现实意义。针对图着色问题,提出一种改进版禁忌搜索算法Tabucol+以增强搜索的集中性。算法在传统禁忌搜索策略的基础上,引入新的评分策略。实验结果显示,新的算法能够显著减少迭代次数和搜索时间,在个别算例上甚至取得了颜色数改进的效果。

关键词: 禁忌搜索算法, 图着色问题, 同分顶点

Abstract: The graph coloring problem is an NP-hard problem,which has a wide range of applications in reality,such as register allocation,airport scheduling and so on.Tabu search algorithm is a classic heuristic search algorithm,which is widely used in the algorithm design of graph coloring problems.As a low-level operator,the tabu search algorithm is also commonly used in the design of graph coloring algorithms such as hybrid evolutionary algorithm(HEA),which plays a key role in the performance of the algorithm.Therefore,the improvement of the tabu search algorithm has practical significance for promoting the research of graph coloring algorithm.Aiming at the problem of graph coloring,this paper proposes an improved version of Tabucol+ to enhance the concentration of search.Based on the traditional tabu search strategy,the proposed algorithm introduces a new scoring strategy.Experimental results show that the new algorithm can significantly reduce the number of iterations andsearch time.In some cases,even the improvement of the number of colors has been achieved.

Key words: Tabu search algorithm, Graph coloring problem, Vertices with the same score

中图分类号:

TP301

汪建昌, 王硕, 李壮, 江华. 图着色问题禁忌搜索改进算法[J]. 计算机科学, 2022, 49(11A): 211000128-5. https://doi.org/10.11896/jsjkx.211000128

WANG Jian-chang, WANG Shuo, LI Zhuang, JIANG Hua. Improved Algorithm for Tabu Search of Graph Coloring Problems[J]. Computer Science, 2022, 49(11A): 211000128-5. https://doi.org/10.11896/jsjkx.211000128

参考文献

[1]CHOU X C,MARIA G L,ROBERTO M.A Tabu Search algorithm for the Probabilistic Orienteering Problem[J].Computers &Operations Research,2021,126:105107.
[2]TANSEL D,ENDER S.Memetic Teaching-Learning-BasedOptimization algorithms for large graph coloring problems[J].Engineering Applications of Artificial Intelligence,2021,102.
[3]FRED G.Future paths for integer programming and links to artificial intelligence[J].Pergamon,1986,13(5):533-549.
[4]HERTZ A,WERRA D.Using tabu search techniques for graph coloring[J].Computing,1987,39(4):345-351.
[5]GALINIER P,HAO J K.Hybrid Evolutionary Algorithms for Graph Coloring[J].Journal of Combinatorial Optimization,1999,3(4):379-397.
[6]LÜ Z P,HAO J K.A memetic algorithm for graph coloring[J].European Journal of Operational Research,2009,203(1):241-250.
[7]MOALIC L,GONDRAN A.Variations on memetic algorithmsfor graph coloring problems[J].Journal of Heuristics,2018,24(1):1-24.
[8]PREUX P,TALBI E G.Towards hybrid evolutionary algo-rithms[J].International Transactions in Operational Research,1999,6(6):557-570.
[9]LU Y L,BENLIC U,WU Q H.A highly effective hybrid evolutionary algorithm for the covering salesman problem[J].Information Sciences,2021,564:144-162.
[10]GLOVER F,CAMPOS V,MARTÍ R.Tabu search tutorial.A Graph Drawing Application[J].TOP,2021:319-350.
[11]MOSTAFAIE T,MODARRES F,NAVIMIPOUR K N J.Asystematic study on meta-heuristic approaches for solving the graph coloring problem[J].Computers and Operations Research,2020,120:104850.
[12]CHALUPA D.On transitions in the behaviour of tabu search algorithm TabuCol for graph colouring[J].Journal of Experimental & Theoretical Artificial Intelligence,2017,30(1):53-69.
[13]RAJA M,GOPALAKRISHNAN S.Solution to Graph Coloring Using Genetic and Tabu Search Procedures[J].Arabian Journal for Science and Engineering,2018,43(2):525-542.
[14]https://sites.google.com/site/graphcoloring/vertex-coloring.
[15]LAI X J,HAO J K,GLOVER F.A study of two evolutionary/tabu search approaches for the generalized max-mean dispersion problem[J].Expert Systems With Applications,2020,139:112856.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

图着色问题禁忌搜索改进算法

Improved Algorithm for Tabu Search of Graph Coloring Problems

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

Metrics

本文评价

推荐阅读 0

[1]	陈玉涛, 许文超, 赵召娜, 刘洪恩, 王浩. 面向通用航空器运行排班及维修的策略优化 Optimization of Scheduling and Maintenance Strategy for Navigation Aircraft Operation 计算机科学, 2020, 47(11A): 632-637. https://doi.org/10.11896/jsjkx.200600053
[2]	郑晶晶张晶武继刚. 分布式交互应用中服务器放置问题的启发式算法 Heuristic Algorithm for Server Placement in Distributed Interactive Applications 计算机科学, 2015, 42(7): 95-98. https://doi.org/10.11896/j.issn.1002-137X.2015.07.020
[3]	. 基于GridSim ToolKits的网格仿真环境设计与实现计算机科学, 2008, 35(6): 83-85.
[4]	王东平李绍荣. 模糊禁忌搜索算法用于求解分配问题计算机科学, 2003, 30(7): 167-169.
[5]	王东平李绍荣. 禁忌搜索算法用于解决网络路由问题计算机科学, 2003, 30(6): 55-57.
[6]	贺一刘光远. 基于变异方法的禁忌搜索计算机科学, 2002, 29(5): 115-116.