图的着色问题是一个被广泛研究的组合优化问题。它也是科学计算和工程设计中一个重要和基本的问题。事实上，许多现实生活中的问题例如考试时间表问题和任务分配问题等都可以被模拟成图的着色问题的拓展。由于对于任意一个图着色例子而言，没有一种算法可以在多项式的时间内找到它的解，因此图的着色问题是一个NP难的问题。以种群进化理论为基础的遗传算法为解决图的着色问题提供了一个很好的选择，因为遗传算法已经被成功的应用于解决许多复杂的全局优化问题。本文将对遗传算法的基础理论进行研究，并提出一些有效的算法用于解决图的着色问题。在本文的第三章节中，在系统分析了图的正常k－顶点着色、k－边着色和全着色问题的基础上，对基于遗传算法的图的着色问题的求解过程进行了深入的理论分析。算法将启发式算法与遗传算法相混合，尽可能的利用启发式算法为染色体进行着色。在混合的方法中，遗传算法用于进行全局搜索，而启发式算法则用于尽可能的查找局部最优解。在本文的第四章节中，研究发现在利用遗传算法解决图的着色问题中存在着一个重要的不足，即在问题解空间中存在着大量的冗余数据。事实上，解空间的冗余度将随着颜色数的增加呈指数增长，这将使问题的收敛速度急剧下降，以至于可能无法找到问题的最优解。除了降低算法的收敛速度外，冗余数据还会造成交叉算子的失效。所以传统的交叉操作并不适用于这个问题，因为它不利于解的优化，甚至会破坏解的优化。本文提出利用矩阵变换的方法解决冗余数据带来的交叉算子失效问题，并给出一种改进的通用遗传算法标准用于解决一类具有编码冗余问题的例子。在本文的第五章节中，分析发现造成问题解空间中存在大量冗余数据的根本原因是因为简单编码方式是面向目标的，而不是面向分组的。因此提出利用分组遗传算法的不定长分组编码方式来彻底解决编码冗余问题。分组遗传算法采用的编码方式使染色体的基因中记载了分组的信息，这使得分组遗传算法必须作用于变长的染色体，而这正是分组遗传算法与传统遗传算法最重要的区别。