A membrane evolutionary algorithm for solving graph coloring problem
CSTR:
Author:
Affiliation:

College of Computer Science, Chongqing University, Chongqing 400044, P. R. China

Clc Number:

TP301.6

Fund Project:

Supported by Natural Science Foundation of Chongqing (cstc2019jcyj-msxmX0622).

  • Article
  • | |
  • Metrics
  • |
  • Reference [21]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    The graph coloring problem is one of the popular NP-hard problems in graph theory. Various heuristic algorithms have been proposed to solve this problems; however, they often suffer from poor quality and long computation time. In recent years, the membrane evolutionary algorithm has shown unique advantages in dealing with NP-hard problems. Based on the membrane evolutionary algorithm framework, this study proposed a membrane evolutionary algorithm to solve the graph coloring problem. Six membrane evolutionary operators, namely, copy, fusion, division, cytolysis, fusion-division, and tabucol were designed to facilitate the evolution of the membranes and membrane structures, leading to the discovery of more optimal solutions. Experiments were conducted on 40 challenging datasets from DIMACS, and the results were compared with three latest algorithms. The resalts show the proposed algorithm effectively reduces the computation time while maintaining the solution quality, outperforming the other algorithms in 58% of the instances.

    Reference
    [1] Orden D, Marsa-Maestre I, Gimenez-Guzman J M, et al. Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction[J]. Discrete Applied Mathematics, 2019, 263: 234-243.
    [2] Gao L, Hou Y, Tao X, et al. A graph-based resource sharing and admission control for vehicular networks[C]// 2019 IEEE Wireless Communications and Networking Conference Workshop (WCNCW). IEEE, 2019, 1-6.
    [3] Hsiao H C, Chen C W, Wang J, et al. Architecture-aware memory access scheduling for high-throughput cascaded classifiers[C]// 2019 IEEE 22nd International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). IEEE, 2019:1-4.
    [4] Galinier P, Hao J K. Hybrid evolutionary algorithms for graph coloring[J]. Journal of Combinatorial Optimization, 1999, 3(4): 379-397.
    [5] Moalic L, Gondran A. Variations on memetic algorithms for graph coloring problems[J]. Journal of Heuristics, 2018, 24(1): 1-24.
    [6] Lü Z, Hao J K. A memetic algorithm for graph coloring[J]. European Journal of Operational Research, 2010, 203(1):241-250.
    [7] Negi C, Shukla A N. An approach for solving the graph coloring problem using adjacency matrix[C]// 2019 8th International Conference System Modeling and Advancement in Research Trends (SMART). IEEE, 2019: 10-13.
    [8] Crnki? A, Povh J, Ja?imovi? V, et al. Collective dynamics of phase-repulsive oscillators solves graph coloring problem[J]. Chaos, 2020, 30(3): 033128.
    [9] Andreu-Guzmán J A, Valencia-Cabrera L. A novel solution for GCP based on an OLMS membrane algorithm with dynamic operators[J]. Journal of Membrane Computing, 2020, 2(1): 1-13.
    [10] Tabi Z, El-Safty K H, Kallus Z, et al. Quantum optimization for the graph coloring problem with space-efficient embedding[C]// 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2020: 56-62.
    [11] Baiche K, Meraihi Y, Hina M D, et al. Solving graph coloring problem using an enhanced binary dragonfly algorithm[J]. International journal of swarm intelligence research, 2019, 10(3): 23-45.
    [12] Zhao R, Wang Y, Liu C, et al. Discrete selfish herd optimizer for solving graph coloring problem[J]. Applied Intelligence, 2020, 50(5): 1633-1656.
    [13] Zhou Y, Duval B, Hao J K. Improving probability learning based local search for graph coloring[J]. Applied Soft Computing, 2018, 65: 542-553.
    [14] Goudet O, Duval B, Hao J K. Population-based gradient descent weight learning for graph coloring problems[J]. Knowledge-Based Systems, 2021, 212:106581.
    [15] Guo P, Quan C, Chen H. MEAMVC: A Membrane evolutionary algorithm for solving minimum vertex cover problem[J]. IEEE Access, 2019, 7: 60774-60784.
    [16] Guo P, Wang X, Zeng Y, et al. MEAMCP: A membrane evolutionary algorithm for solving maximum clique problem[J]. IEEE Access, 2019, 7: 108360-108370.
    [17] Guo P, Hou M, Ye L. MEATSP: a membrane evolutionary algorithm for solving TSP[J]. IEEE Access, 2020, 8:199081-199096.
    [18] Xu Y C, Guo P. MEA-CNDP: a membrane evolutionary algorithm for solving biobjective critical node detection problem[J]. Computational Intelligence and Neuroscience, 2021, 2021: 1-20.
    [19] Liu Y Y, Guo P, Zeng Y. MEACCP: a membrane evolutionary algorithm for capacitated clustering problem[J]. Information Sciences, 2022, 591: 319-343.
    [20] Hertz A, Werra D. Using tabu search techniques for graph coloring[J]. Computing, 1987, 39(4): 345-351.
    [21] Fleurent C, Ferland J A. Genetic and hybrid algorithms for graph coloring[J]. Annals of Operations Research, 1996, 63(3):437-461.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

郭平,郭宾.解决图着色问题的膜进化算法[J].重庆大学学报,2023,46(7):23~35

Copy
Share
Article Metrics
  • Abstract:418
  • PDF: 705
  • HTML: 73
  • Cited by: 0
History
  • Received:February 02,2022
  • Online: August 02,2023
Article QR Code