A memetic algorithm for graph coloring

作者：Lue Zhipeng; Hao Jin Kao

来源：European Journal of Operational Research, 2010, 203(1): 241-250.

DOI：10.1016/j.ejor.2009.07.016

• Graph coloring
• Memetic algorithm
• Crossover operator
• Pool updating

Given an undirected graph G = (V: E) with a set V of vertices and a set E of edges, the graph coloring problem consists of partitioning all vertices into k independent sets and the number of used colors k is minimized. This paper presents a memetic algorithm (denoted by MACOL) for solving the problem of graph coloring. The proposed MACOL algorithm integrates several distinguished features such as an adaptive multi-parent crossover (AMPaX) operator and a distance-and-quality based replacement criterion for pool updating. The proposed algorithm is evaluated on the DIMACS challenge benchmarks and computational results show that the proposed MACOL algorithm achieves highly competitive results, compared with 11 state-of-the-art algorithms. The influence of some ingredients of MACOL on its performance is also analyzed.

• 出版日期2010-5-16