2014 | OriginalPaper | Chapter
Accelerating Genetic Algorithm for Solving Graph Coloring Problem Based on CUDA Architecture
Authors : Kai Zhang, Ming Qiu, Lin Li, Xiaoming Liu
Published in: Bio-Inspired Computing - Theories and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Graph coloring problem (GCP) is a well-known NP-hard combinatorial optimization problem in graph theory. Solution for GCP often finds its applications to various engineering fields. So it is very important to find a feasible solution quickly. Recent years, Compute Unified Device Architecture (CUDA) show tremendous computational power by allowing parallel high performance computing. In this paper, we present a novel parallel genetic algorithm to solve the GCP based on CUDA. The initialization, crossover, mutation and selection operators are designed parallel in threads. Moreover, the performance of our algorithm is compared with the other graph coloring methods using standard DIMACS benchmarking graphs, and the comparison result shows that our algorithm is more competitive with computation time and graph instances size.