摘要
图着色问题是图论中比较热门的NP难问题之一。针对该问题,有许多启发式求解算法,但都存在求解的质量不高,计算时间较长等问题。近些年提出的膜进化算法,在处理NP难问题中展现出了独特的优势。基于膜进化算法框架,提出了解决图着色问题的膜进化算法,把图着色问题和膜结合,设计了复制、融合、分裂、溶解、融合分裂、禁忌搜索6种膜进化算子。这些算子在演变的过程中使膜和膜结构发生进化,从而找到更优解,最后求得解决方案。在DIMACS的40个挑战数据集上面进行了实验,与3个最新的图着色算法比较的结果表明:在保证解的质量的情况下,文中提出的膜进化算法能有效降低求解的时间,其中有58%的实例占优。
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.
作者
郭平
郭宾
GUO Ping;GUO Bin(College of Computer Science,Chongqing University,Chongqing 400044,P.R.China)
出处
《重庆大学学报》
CAS
CSCD
北大核心
2023年第7期23-35,共13页
Journal of Chongqing University
基金
重庆市自然科学基金资助项目(cstc2019jcyj-msxmX0622)。
关键词
图论
组合优化
NP难问题
图着色问题
膜进化算法
graph theory
combinatorial optimization
NP-hard
graph coloring problem
membrane evolutionary algorithm
