图着色问题的算法研究综述

doi:10.3778/j.issn.1002-8331.2403-0434

摘要/Abstract

摘要： 图着色问题（graph coloring problem，GCP）是一个经典的组合优化问题，已广泛应用于数学、计算机科学和生物科学等多个领域。由于图着色问题的NP难特性，目前还没有多项式时间内的精确算法求解该问题，为了给出求解该问题的高效算法，需要对现有算法进行梳理。主要分为智能优化算法、启发式算法、强化学习算法等，从算法原理、改进思路、性能和精度等方面进行对比分析，归纳出算法的优缺点，并指出GCP的研究方向和算法设计路径，对于相关问题的研究有指导意义。

关键词: 图着色问题, 智能优化算法, 启发式算法, 强化学习算法

Abstract: The graph coloring problem (GCP) is a classic combinatorial optimization problem that has been widely applied in various fields such as mathematics, computer science, and biological science. Due to the NP hard nature of graph coloring problems, there is currently no precise algorithm in polynomial time to solve the problem. In order to provide an efficient algorithm for solving this problem, it is necessary to review the existing algorithms. It mainly divided into intelligent optimization algorithms, heuristic algorithms, reinforcement learning algorithms, etc., comparative analysis is carried out from the aspects of algorithm principles, improvement ideas, performance and accuracy, summarizing the advantages and disadvantages of algorithms, and pointing out the research direction and algorithm design path of GCP, which has guiding significance for the research of related problems.

Key words: graph coloring problem, intelligent optimization algorithm, heuristic algorithm, reinforcement learning algorithm

宋家欢, 王晓峰, 胡思敏, 贾璟伟, 颜冬. 图着色问题的算法研究综述[J]. 计算机工程与应用, 2024, 60(18): 66-77.

SONG Jiahuan, WANG Xiaofeng, HU Simin, JIA Jingwei, YAN Dong. Algorithmic Research Overview on Graph Coloring Problems[J]. Computer Engineering and Applications, 2024, 60(18): 66-77.

参考文献

[1] LIU S C. A renewal approach to prove the four color theorem unplugged, part III: diamond routes, canal lines and ??-adjustments[J]. arXiv:2309.09998, 2023.
[2] KAINZ W. Cartography and the others-aspects of a complicated relationship[J]. Geo-Spatial Information Science, 2020, 23(1): 52-60.
[3] OUSSEIN E H, GAD A G, WAZERY Y M, et al. Task scheduling in cloud computing based on meta-heuristics: review, taxonomy, open challenges, and future trends[J]. Swarm and Evolutionary Computation, 2021, 62: 100841.
[4] IBRAHIM I M. Task scheduling algorithms in cloud computing: a review[J]. Turkish Journal of Computer and Mathematics Education (TURCOMAT), 2021, 12(4): 1041-1053.
[5] NABI S, AHMAD M, IBRAHIM M, et al. AdPSO: adaptive PSO-based task scheduling approach for cloud computing[J]. Sensors, 2022, 22(3): 920.
[6] WANG H, WANG K, YANG J, et al. GCN-RL circuit designer: transferable transistor sizing with graph neural networks and reinforcement learning[C]//2020 57th ACM/IEEE Design Automation Conference (DAC), 2020: 1-6.
[7] PANIGRAHI P, SAHITHYA V, KARFA C, et al. Secure register allocation for trusted code generation[J]. IEEE Embedded Systems Letters, 2022, 14(3): 127-130.
[8] ZHANG Y, CHEN W, LING H, et al. Image gans meet differentiable rendering for inverse graphics and interpretable 3D neural rendering[J]. arXiv:2010.09125, 2020.
[9] KATOCH S, CHAUHAN S S, KUMAR V. A review on genetic algorithm: past, present, and future[J]. Multimedia Tools and Applications, 2021, 80: 8091-8126.
[10] SQUIRES M, TAO X E，ALNGOVAN S, et al. A novel genetic algorithm based system for the scheduling of medical treatments[J]. Expert Systems with Applications, 2022, 195: 116464.
[11] SDENG W, ZHANG X, ZHOU Y, et al. An enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems[J]. Information Sciences, 2022, 585: 441-453.
[12] SHAMI T M, EL-SALEH A A, ALAWAITTIl M, et al. Particle swarm optimization: a comprehensive survey[J]. IEEE Access, 2022, 10: 10031-10061.
[13] GAD A G. Particle swarm optimization algorithm and its applications: a systematic review[J]. Archives of Computational Methods in Engineering, 2022, 29(5): 2531-2561.
[14] ROKBANI N, KUMAR R, ABRAHAM A, et al. Bi-heuristic ant colony optimization-based approaches for traveling salesman problem[J]. Soft Computing, 2021, 25: 3775-3794.
[15] WANG G G, GAO D, PEDRYCZ W. Solving multiobjective fuzzy job-shop scheduling problem by a hybrid adaptive differential evolution algorithm[J]. IEEE Transactions on Industrial Informatics, 2022, 18(12): 8519-8528.
[16] ZHANG D, GAO Z, LIN Z. An online control approach for forging machine using reinforcement learning and taboo search[J]. IEEE Access, 2020, 8: 158666-158678.
[17] WANG Y, QIAN M. Vegetable price and supply forecast based on the taboo search algorithm[J]. Highlights in Science, Engineering and Technology, 2024, 82: 37-42.
[18] CAO J, ZHANG F, LU Y, et al. Modeling optimization of distributed prefabricated manufacturing system based on iterative taboo search algorithm[C]//2023 3rd International Symposium on Artificial Intelligence and Intelligent Manufacturing (AIIM), 2023: 111-115.
[19] KUMAR S, TRIPATHI D R R. To study the financial performance of top five privatized banks in India with special reference to (HDFC, AXIS, ICICI, KMB, IndusInd Bank)[J]. Journal of Contemporary Issues in Business and Government, 2021, 27(6).
[20] ZHANG K, KOREPIN V E. Depth optimization of quantum search algorithms beyond Grover’s algorithm[J]. Physical Review A, 2020, 101(3): 032346.
[21] DU Y, HUANG T, YOU S, et al. Quantum circuit architecture search for variational quantum algorithms[J]. npj Quantum Information, 2022, 8(1): 62.
[22] BHARTI K, CERVERA-LIERTA A, KYAW T H, et al. Noisy intermediate-scale quantum algorithms[J]. Reviews of Modern Physics, 2022, 94(1): 015004.
[23] CLIFTON J, LABER E. Q-learning: theory and applications[J]. Annual Review of Statistics and Its Application, 2020, 7: 279-301.
[24] YANG K, YANG L, DU S. Q-learning with logarithmic regret[C]//International Conference on Artificial Intelligence and Statistics, 2021: 1576-1584.
[25] GAO Z, GAO Y, HU Y, et al. Application of deep q-network in portfolio management[C]//2020 5th IEEE International Conference on Big Data Analytics (ICBDA), 2020: 268-275.
[26] UCHIDA Y, YAJIMA K, HARAGUCHI K. Recycling solutions for vertex coloring heuristics[J]. Journal of the Operations Research Society of Japan, 2021, 64(3): 184-202.
[27] VERMA G,ARORA J,SETHI R, et al. Handmade cloning:recent advances,potential and pitfalls[J].Journal of Animal Science and Biotechnology, 2015, 6(4): 378-387.
[28] CORDEAU J F, FURINI F, LJUBIC I. Benders decomposition for very large scale partial set covering and maximal covering location problems[J]. European Journal of Operational Research, 2019, 275(3): 882-896.
[29] RAUCHECKER G, SCHRYEN G. An exact branch-and-price algorithm for scheduling rescue units during disaster response[J]. European Journal of Operational Research, 2019, 272(1): 352-363.
[30] GOYAL J M, MAYNE N, SING D K, et al. A library of ATMO forward model transmission spectra for hot Jupiter exoplanets[J]. Monthly Notices of the Royal Astronomical Society, 2018, 474(4): 5158-5185.
[31] SELSAM D, LAMM M, BUNZ B, et al. Learning a SAT solver from single-bit supervision[J]. arXiv:1802.03685, 2018.
[32] LOUKAS A. What graph neural networks cannot learn: depth vs width[J]. arXiv:1907.03199, 2019.
[33] ZHAO R, WANG Y, LIU C, et al. Discrete selfish herd optimizer for solving graph coloring problem[J]. Applied Intelligence, 2020, 50: 1633-1656.
[34] DHULIPALA L, BLELLOCH G E, SHUN J. Theoretically efficient parallel graph algorithms can be fast and scalable[J]. ACM Transactions on Parallel Computing (TOPC), 2021, 8(1): 1-70.
[35] CHRISTOFIDES N. Worst-case analysis of a new heuristic for the travelling salesman problem[C]//Operations Research Forum. Cham: Springer International Publishing, 2022.
[36] BRIGHEN A, SLIMANI H, REZGUI A, et al. A new distributed graph coloring algorithm for large graphs[J]. Cluster Computing, 2023, 27(1): 875-891.
[37] XU C, MA J, TAO H. Batch process control based on reinforcement learning with segmented prioritized experience replay[J]. Measurement Science and Technology, 2024, 35(5): 056202.
[38] HAN J X, MA M Y, WANG K. Product modeling design based on genetic algorithm and BP neural network[J]. Neural Computing and Applications, 2021, 33: 4111-4117.
[39] BESTA M, CARIGIET A, JANDA K, et al. High-performance parallel graph coloring with strong guarantees on work, depth, and quality[C]//SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, 2020: 1-17.
[40] SINGLA M K, NIJHAWAN P, OBEROI A S. Parameter estimation of three diode solar PV cell using chaotic dragonfly algorithm[J]. Soft Computing, 2022, 26(21): 11567-11598.
[41] PIKIES T, TUROWSKI K, KUBALE M. Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms[J]. Artificial Intelligence, 2022, 309: 103711.
[42] BINUCCI C, DI-BATTISTA G, DIDIMO W, et al. Nonplanar graph drawings with k vertices per face[C]//International Workshop on Graph-Theoretic Concepts in Computer Science. Cham: Springer Nature Switzerland, 2023: 86-100.
[43] ALSMADI M K. Content-based image retrieval using color, shape and texture descriptors and features[J]. Arabian Journal for Science and Engineering, 2020, 45(4): 3317-3330.
[44] MARAPPAN R, SETHUMADHAVAN G. Solving graph coloring problem using divide and conquer-based turbulent particle swarm optimization[J]. Arabian Journal for Science and Engineering, 2021,47: 9695-9712.
[45] BASAK S, SAMANTA K K. Thermal behaviour and the cone calorimetric analysis of the jute fabric treated in different pH condition[J].Journal of Thermal Analysis and Calorimetry, 2019, 135(6): 3095-3105.
[46] PRASTYO P H, HIDAYAT R, ARDIYANTO I. Enhancing sentiment classification performance using hybrid query expansion ranking and binary particle swarm optimization with adaptive inertia weights[J]. ICT Express, 2022, 8(2): 189-197.
[47] ZHANG X P, ZHANG Y P, FENG S S. An ant colony genetic algorithm for solvinggraph coloring problems[J]. Computer Applications and Software, 2014, 31(11): 207-209.
[48] SHIMIZU K, MORI R. Exponential-time quantum algorithms for graph coloring problems[J]. Algorithmica, 2022, 84(12): 3603-3621.
[49] GUO P, GUO B. NERS_HEAD: a new hybrid evolutionary algorithm for solving graph coloring problem[J]. Soft Computing, 2023, 27(17): 12117-12131.
[50] CIARELLA S, TRINQUIER J, WEIGT M, et al. Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems[J]. Machine Learning: Science and Technology, 2023, 4(1): 010501.
[51] 马艳萍, 吴晓军, 杨明成. 解决图着色问题的一种新禁忌搜索算法[J]. 计算机应用与软件, 2012, 29(2): 279-281.
MA Y P, WU X J, YANG M C. A new tabu search algorithm for graph colouring[J]. Computer Applications and Software, 2012, 29(2): 279-281.
[52] 汪建昌. 基于禁忌搜索算法解决图着色问题[D]. 昆明: 云南大学, 2022.
WANG J C. Solving graph coloring problem based on tabu search algorithm [D]. Kunming: Yunnan University, 2022.
[53] 汪建昌, 王硕, 李壮, 等. 图着色问题禁忌搜索改进算法[J]. 计算机科学, 2022, 49(S2): 94-98.
WANG J C, WANG S, LI Z, et al. Improved algorithm for tabu search of graph coloring problems[J]. Computer Science, 2022, 49(S2): 94-98.
[54] 刘晓楠, 刘正煜, 谢浩山, 等. 基于Grover算法的图着色问题求解[J]. 计算机科学, 2023, 50(6): 351-357.
LIU X N, LIU Z Y, XIE H S, et al. Solving graph coloring problem based on Grover algorithm[J]. Computer Science, 2023, 50(6): 351-357.
[55] JAYAGOPAL P, PURUSHPTHAMAN J K, MOHAN P, et al. A modified generative adversarial networks with Yolov5 for automated forest health diagnosis from aerial imagery and tabu search algorithm[J]. Scientific Reports, 2024, 14(1): 4814.
[56] NOGUEIRA B, TAVARES E, MACIEL P. Iterated local search with tabu search for the weighted vertex coloring problem[J]. Computers & Operations Research, 2021, 125: 105087.
[57] PERVEEN K, DEBNATH S, PANDEY B, et al. Deep learning-based multiscale CNN-based U network model for leaf disease diagnosis and segmentation of lesions in tomato[J]. Physiological and Molecular Plant Pathology, 2023, 128: 102148.
[58] TAN Z, LI K. Differential evolution with mixed mutation strategy based on deep reinforcement learning[J]. Applied Soft Computing, 2021, 111: 107678.
[59] GIRMA R, FURST C, MOGES A. Land use land cover change modeling by integrating artificial neural network with cellular Automata-Markov chain model in Gidabo river basin, main Ethiopian rift[J]. Environmental Challenges, 2022, 6: 100419.
[60] DEY N N, Al R A, KAFY A A, et al. Geospatial modelling of changes in land use/land cover dynamics using multi-layer perceptron Markov chain model in Rajshahi City, Bangladesh[J]. Environmental Challenges, 2021, 4: 100148.
[61] BAR A, SHAPIRA B, ROKACH L. Context aware Markov chains models[J]. Knowledge-Based Systems, 2023, 282: 111083.
[62] DEGUALE D A, YU L, SINISHAW M L, et al. Enhancing stability and performance in mobile robot path planning with PMR-dueling DQN algorithm[J]. Sensors, 2024, 24(5): 1523.
[63] CHEN W, QIU X, CAI T, et al. Deep reinforcement learning for Internet of things: a comprehensive survey[J]. IEEE Communications Surveys & Tutorials, 2021, 23(3): 1659-1692.
[64] 吕恒. 解决图着色问题的膜进化算法研究[D]. 重庆: 重庆大学, 2022.
LV H. Research on membrane evolutionary algorithm for graph coloring problem[D]. Chongqing: Chongqing University, 2022.