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