A membrane evolutionary algorithm for solving graph coloring problem
Article
Figures
Metrics
Preview PDF
Reference
Related
Cited by
Materials
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.
Keywords:
Project Supported:
Supported by Natural Science Foundation of Chongqing (cstc2019jcyj-msxmX0622).
