Journal
APPLIED SOFT COMPUTING
Volume 65, Issue -, Pages 542-553Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.asoc.2018.01.027
Keywords
Graph coloring; Grouping problems; Learning-based optimization; Tabu search; Heuristics
Categories
Funding
- China Scholarship Council
Ask authors/readers for more resources
This paper presents an improved probability learning based local search algorithm for the well-known graph coloring problem. The algorithm iterates through three distinct phases: a starting coloring generation phase based on a probability matrix, a heuristic coloring improvement phase and a learning based probability updating phase. The method maintains a dynamically updated probability matrix which specifies the chance for a vertex to belong to each color group. To explore the specific feature of the graph coloring problem where color groups are interchangeable and to avoid the difficulty posed by symmetric solutions, a group matching procedure is used to find the group-to-group correspondence between a starting coloring and its improved coloring. Additionally, by considering the optimization phase as a black box, we adopt the popular tabu search coloring procedure for the coloring improvement phase. We show extensive computational results on the well-known DIMACS benchmark instances and comparisons with state-of-the-art coloring algorithms. (c) 2018 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