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

摘要：

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

关键词：图论、组合优化、NP难问题、图着色问题、膜进化算法

所属期刊栏目：46

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2023-08-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：23-35