Research Of Parallel Genetic Algorithm For Solving Graph Coloring Problem Based On CUDA

Graph coloring problem (GCP) is one of typical combinatorial optimizationproblems, many practical problems originating from life all can be mapped intosolving the GCP. Therefore, the solving for GCP contributes greatly to the field ofscience, technology and engineering design etc. However, given an instance of GCP,there is no algorithm could find the optimal solution in polynomial time, so the GCP isa typical NP-complete problem.In recent years, many scholars have proposed various algorithms for solving GCP:implicit enumeration algorithm, cutting plane algorithm etc. These kind of precisionalgorithms obtain sound result when problem scale is small. However, the exponentialexplosion problem can not be avoided when the problem scale gets bigger. Apartingfrom precision algorithms, genetic algorithms, ant colony algorithm can also be used tosolve GCP. However, due to the exponential size of the solution space, it would all takea lot of time to compute no matter precision algorithm or approximation algorithm, wecan not find the solution in satisfactory time.Recently, the high performance computing technology based on CUDA hasbecome a hot topic. In this paper, we combine CUDA with genetic algorithm andpropose a kind of parallel genetic algorithm based on CUDA for solving GCP. In ouralgorithm, we encode the GCP with coloring sequence and the initial population andselection, crossover, mutation operators are all designed parallel which improves theefficiency of our algorithm greatly.Experimental results show that the algorithm proposed in this paper cansignificantly reduce computing time and find the minimum coloring number of a givengraph instance, it can also solve the much more complex problem instances effectively.