.png){kind=icon}
.png){kind=icon}
Return
Improving probability learning based local search for graph coloring
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2018.01.027.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Graph coloring
Grouping problems
Learning-based optimization
Tabu search
Heuristics
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.