Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Accelerating Genetic Algorithm for Solving Graph Coloring Problem Based on CUDA Architecture
verfasst von : Kai Zhang, Ming Qiu, Lin Li, Xiaoming Liu
Erschienen in: Bio-Inspired Computing - Theories and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.