为了解决典型的组合优化问题———图顶点着色问题，结合增强 SEQ 算法和禁忌搜索算法的优点与缺点，提出一种基于 增强 SEQ 的新禁忌搜索算法( SEQTS) 。该算法利用增强 SEQ 算法较强的构造较优解的能力来为禁忌搜索算法构造多个较优初始 解，然后进行多初始解禁忌搜索以找到全局最优解。计算机实验的结果表明该算法( SEQTS) 有较好的寻优能力，增强了该算法的有 效性。