首页 | 本学科首页   官方微博 | 高级检索  
     检索      

解决图着色问题的膜进化算法
引用本文:郭平,郭宾.解决图着色问题的膜进化算法[J].重庆大学学报(自然科学版),2023,46(7):23-35.
作者姓名:郭平  郭宾
作者单位:重庆大学 计算机学院,重庆 400044
基金项目:重庆市自然科学基金资助项目(cstc2019jcyj-msxmX0622)。
摘    要:图着色问题是图论中比较热门的NP难问题之一。针对该问题,有许多启发式求解算法,但都存在求解的质量不高,计算时间较长等问题。近些年提出的膜进化算法,在处理NP难问题中展现出了独特的优势。基于膜进化算法框架,提出了解决图着色问题的膜进化算法,把图着色问题和膜结合,设计了复制、融合、分裂、溶解、融合分裂、禁忌搜索6种膜进化算子。这些算子在演变的过程中使膜和膜结构发生进化,从而找到更优解,最后求得解决方案。在DIMACS的40个挑战数据集上面进行了实验,与3个最新的图着色算法比较的结果表明:在保证解的质量的情况下,文中提出的膜进化算法能有效降低求解的时间,其中有58%的实例占优。

关 键 词:图论  组合优化  NP难问题  图着色问题  膜进化算法
收稿时间:2022/2/2 0:00:00

A membrane evolutionary algorithm for solving graph coloring problem
GUO Ping,GUO Bin.A membrane evolutionary algorithm for solving graph coloring problem[J].Journal of Chongqing University(Natural Science Edition),2023,46(7):23-35.
Authors:GUO Ping  GUO Bin
Institution:College of Computer Science, Chongqing University, Chongqing 400044, P. R. China
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:graph theory  combinatorial optimization  NP-hard  graph coloring problem  membrane evolutionary algorithm
点击此处可从《重庆大学学报(自然科学版)》浏览原始摘要信息
点击此处可从《重庆大学学报(自然科学版)》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号