禁忌搜索(Tabu Search, TS)是一种较新的智能优化算法,与遗传算法(GA)、粒子群优化算法(PSO)、蚁群算法(ACS)等一样,都包括在自然计算(Natural Computation)的范围内。该算法利用其较为通用的算法框架、灵活的存储结构及相应的禁忌准则可以尽可能避免算法陷入循环搜索,在解决组合优化问题及函数优化领域内引起了不少学者的重视。随着计算机科学的不断发展,图与人类的生活越来越密切,在现实社会中的很多问题都可以归结为点与线组成的图形问题,不少学者引入图论来解决工程应用领域中的很多问题。近年来在工程领域中对图的研究和应用也越来越受到人们的重视,因此,禁忌搜索算法解决图着色问题的研究是十分有意义的。本文在理解基本禁忌算法理论框架的基础上,重点研究了禁忌搜索算法在图着色问题中的应用。本文将禁忌搜索算法与图顶点着色问题结合,建立算法框架与图顶点着色问题的解空间的映射,应用传统禁忌搜索算法解决了图的顶点着色问题,分析仿真实验结果,评估算法的时间复杂性。另外,本文还分析了传统禁忌搜索算法不足,对传统的禁忌搜索算法进行改进,利用改进后的混合禁忌搜索算法来解决图顶点着色问题,再进行仿真实验,实验效果显著。论文主要工作及创新点可以归纳为如下几点：(1)阐述并分析了禁忌搜索算法的操作参数,结合禁忌搜索算法的理论框架与图顶点着色问题的约束条件,首先用传统禁忌搜索算法来解决典型的图顶点着色问题,建立了一种利用禁忌搜索算法来解决图顶点着色问题的算法模型。(2)进一步地研究禁忌搜索算法,分析传统禁忌搜索算法在理论上和实际应用上体现出来的不足,比如初始解对待解决问题的依赖性强,搜索迭代的串行性等,本文针对其不足,结合SEQ算法,提出了一种改进禁忌搜索算法解决图顶点着色问题的较优方案,实验仿真结果证明,改进算法效果更好。(3)基于上述对传统禁忌搜索算法与改进禁忌搜索算法的应用研究,本文对其作了分析与总结,针对传统禁忌搜索算法在应用中体现出来的缺点,提出算法的改进方案,并在理论上对其应用前景进行了展望。