遗传算法是模拟自然界生物进化过程与机制来求解优化问题的一类自组织、自适应的随机搜索算法,其编码技术和遗传操作比较简单,对优化问题的限制性条件要求很低,具有很强的并行性和全局搜索能力。它能解决很多类实际问题,目前已经在机器学习、模式识别、图像处理、优化控制、组合优化和管理决策等领域得到了很好的应用。首先,图着色问题是一种经典的NP-完全问题。针对图着色问题对顶点划分的本质特征,提出了基于度的种群初始化方法和交集杂交算子;为加快算法的收敛速度,设计了新的贪婪局部搜索算子来改进杂交产生的后代个体。在此基础上,提出了求解图着色问题的一种新的混合遗传算法,对10个标准算例的仿真结果表明,新混合遗传算法可以获得问题高质量的解,是一种有潜力的算法。其次,基于顶点分割的特点,提出了图着色问题的一种新解法。采用概率矩阵表示种群中的解,大大地节省了存储空间;为了加快算法的收敛速度,结合了一个局部搜索算子提高杂交产生的后代个体的质量;当概率矩阵中的元素取1或0时,算法停止。通过对标准图着色问题的仿真实验,并和已有的算法比较,结果表明,新的算法具有求解性能好、收敛速度快的优点。