An adaptive memory algorithm for the k-coloring problem
An adaptive memory algorithm for the k-coloring problem
复制标题
DOI：
10.1016/j.dam.2006.07.017
复制
发表时间：
2003-05
期刊：
影响因子：
--
通讯作者：
P. Galinier;A. Hertz;N. Zufferey
中科院分区：
文献类型：
--
作者：
P. Galinier;A. Hertz;N. Zufferey
设G=（V，E）是一个顶点集为V，边集为E的图. k-着色问题是给G的每个顶点分配一个颜色（在{1，...，k}中选择的一个数），使得没有边的两个端点具有相同的颜色。自适应记忆算法是一种使用中央记忆的混合进化启发式算法。在每次迭代中，包含在中央存储器中的信息用于产生后代解，然后可能使用局部搜索算法来改进后代解。如此获得的解决方案最终用于更新中央存储器。本文描述了一种求解k-着色问题的自适应记忆算法。计算实验证明，这种新算法与最著名的图着色算法相比具有竞争力，并且更简单、更灵活。
Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.