图着色问问是一个被广泛研究的组合优化问问,也是科学计算和工程设计中一个重要和基本的问问。事实上,许多现实生活中的问问例如考试时间表问问和任务分配问问等都可以被模拟或拓展为图着色问问。对于任意一个图着色例子问问而言,没有一种算法可以在多项式的时间内找到它的解,因此图着色问问是一个NP-hard问问。目前,对包括旅行商问问在内的许多组合优化问问利用群集智能算法得到了成功解决并获得了广泛应用,因此,以种群进化理论为基础的群集智能算法为求解图着色问问提供了一个很好的选择。在阅读大量相关文献的基础上,本文针对基于图着色问问的群集智能算法研究开展了一系列的工作,具体如下:介绍了图着色和群集智能算法的基本理论,综述了图着色问问和群集智能算法的国内外研究现状,以及群集智能算法的特点和应用。在系统分析了几种传统的群集智能算法用于图的正常顶点着色的基础上,对基于群集智能算法图着色问问的求解过程进行了深入的理论分析。针对遗传算法和模拟退火算法有较强的全局优化能力,但局部搜索能力较差,而蚁群算法具有较强的局部搜索能力,因此将遗传算法、模拟退火算法和蚁群算法相互结合,优势互补。提出了求解图着色问问的两类算法:蚁群单亲遗传算法和蚁群退火算法,提出的算法有效地克服了传统的群集智能算法的缺点。运用Matlab 7.0对提出的两类新算法:蚁群单亲遗传算法和蚁群退火算法进行了大量的仿真实验,结果表明,和传统的智能算法相比,提出的算法具有更强的寻优能力和鲁棒性。