Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 203, Issue 1, Pages 241-250Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2009.07.016
Keywords
Graph coloring; Memetic algorithm; Crossover operator; Pool updating
Funding
- Angers Loire Metropole
- Region of Pays de la Loire
- RADAPOP
Ask authors/readers for more resources
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. (C) 2009 Elsevier B.V. All rights reserved
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available