遗传算法是基于自然进化论和遗传变异理论而产生的一种全局随机搜索算法,其应用优势在于处理传统搜索方法难以解决的复杂和非线性问题。图着色问题是一个经典的组合优化问题,无论在理论上还是工程应用上均有一个良好的应用背景,但它也是典型的NP-完全问题。快速、有效地解决图着色问题有着重要的理论价值和极高的实际应用价值。本文在分析和研究标准遗传算法的基础上,针对图着色问题,提出了一种新的遗传算法。在新的遗传算法中,针对标准遗传算法的缺陷,设计了新的种群初始化方法和遗传算子。新的种群初始化方法用于产生较优的初始种群,在保证种群多样性的同时,提高了算法的收敛速度。在交叉算子中通过改进贪心分割方法保证了大的顶点子集不被破坏。两个新的变异算子既维持了种群的多样性又提高了算法的局部寻优能力。本文将新的遗传算法应用于图着色问题中,并在一些标准算例上进行仿真实验。实验结果表明,改进的遗传算法对于各种类型的图形都能获得良好的寻优能力。