Paper Info
Title
The New Memetic Algorithm HEAD for Graph Coloring: An Easy Way for Managing Diversity.
Abstract
This paper presents an effective memetic approach HEAD designed for coloring difficult graphs. In this algorithm a powerful tabu search is used inside a very specific population of individuals. Indeed, the main characteristic of HEAD is to work with a population of only two individuals. This provides a very simple algorithm with neither selection operator nor replacement strategy. Because of its simplicity, HEAD allows an easy way for managing the diversity. We focus this work on the impact of this diversity management on well-studied graphs of the DIMACS challenge benchmarks, known to be very difficult to solve. A detailed analysis is provided for three graphs on which HEAD finds a legal coloring with less colors than reference algorithms: DSJC500.5 with 47 colors, DSJC1000.5 with 82 colors and flat1000_76_0 with 81 colors. The analysis performed in this work will allow to improve HEAD efficiency in terms of computation time and maybe to decrease the number of needed colors for other graphs.
Year
DOI
Venue
2015
10.1007/978-3-319-16468-7_15
Lecture Notes in Computer Science
Field
DocType
Volume
Memetic algorithm,Population,Graph,Algorithm,Greedy coloring,SIMPLE algorithm,Tabu search,Mathematics,Graph coloring,Computation
Conference
9026
ISSN
Citations 
PageRank 
0302-9743
5
0.39
References 
Authors
21
2
Name
Order
Citations
PageRank
Laurent Moalic1307.19
Alexandre Gondran2123.28