图着色问题是一个经典的组合优化问题，许多来源于生活的实际问题都可以转化为求解图着色问题。因此，图着色问题的求解，对科学技术和工程设计等领域都具有重要作用。然而，没有任何算法可以在多项式时间内求解出该问题的最优解，所以，图着色问题是一个典型的NP完全问题。近年来，国内外的许多学者提出各种求解图着色问题的算法，如隐式枚举算法、割平面算法等，这类精确算法当问题规模较小的时候效果较好，但是一旦问题规模变大，无法避免指数爆炸问题。除了精确算法，遗传算法、蚁群算法等也被用于求解图着色问题。然而，由于图着色问题具有指数级的解空间规模，无论是精确算法还是近似算法，都需要花费大量的时间进行计算，无法在让人满意的时间内求解出问题的解。如今基于CUDA的高性能并行计算技术成为研究热点。本文将CUDA和遗传算法相结合，提出一种基于CUDA求解图着色问题的并行遗传算法，算法采用颜色序列对问题进行编码，设计出并行的种群初始化、选择算子、交叉算子和变异算子，极大地提高了算法的效率。实验结果表明，和传统基于CPU的各类算法相比，本文提出的算法可以较大地减少计算时间，找到已知图例的最小着色数，可以有效求解更大规模的实例。