解决图着色问题的膜进化算法

图着色问题是图论中比较热门的NP难问题之一。针对该问题，有许多启发式求解算法，但都存在求解的质量不高，计算时间较长等问题。近些年提出的膜进化算法，在处理NP难问题中展现出了独特的优势。基于膜进化算法框架，提出了解决图着色问题的膜进化算法，把图着色问题和膜结合，设计了复制、融合、分裂、溶解、融合分裂、禁忌搜索6种膜进化算子。这些算子在演变的过程中使膜和膜结构发生进化，从而找到更优解，最后求得解决方案。在DIMACS的40个挑战数据集上面进行了实验，与3个最新的图着色算法比较的结果表明：在保证解的质量的情况下，文中提出的膜进化算法能有效降低求解的时间，其中有58%的实例占优。

A membrane evolutionary algorithm for solving graph coloring problem

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.