| Resumen |
The graph coloring problem belongs to the problem class NP-Hard, so unless the problem class P is equal to the class NP, there is no polynomial algorithm to solve it . Despite its high complexity, the development of algorithms for these types of problems are of the utmost importance due to the fact that the problems NP-Hard appear in almost all areas of computer science as machine learning , computer networks, operating systems, information systems, among others. In this paper, we propose a parallel implementation, based on CUDA, of a set of variants of a hybrid evolutionary algorithm for the problem of coloring graphs. This algorithm is characterized by mixing evolutionary computation techniques with local search heuristics, with the aim of nding near-optimal solutions. Experimental results show that our parallel implementation proposal is able to consistently nd good solutions and at the same time reduce the execution time of traditional evolutionary algorithms. |
