导读： 摘要:图着色问题和MSA 问题都是被广泛研究的组合优化问题，同时它们也都是典型的NP 完全问题，随着图的规模的增大或比对序列个数的增加，计算量将会以指数的速度增加到不可接受的地步遗传算法、模拟退火算法、禁忌搜索算法都是求解NP 完全问题的有效方法本文...
摘要:图着色问题和MSA 问题都是被广泛研究的组合优化问题，同时它们也都是典型的NP 完全问题，随着图的规模的增大或比对序列个数的增加，计算量将会以指数的速度增加到不可接受的地步遗传算法、模拟退火算法、禁忌搜索算法都是求解NP 完全问题的有效方法本文首先对遗传算法的基本原理和框架进行详细介绍，然后对图着色问题和多序列比对问题进行了相应的研究，提出将遗传算法与模拟退火算法及禁忌搜索算法结合在一起的混合遗传算法该算法充分发挥了它们的优越性，提高了求解GCP 问题和MSA 问题的精度与速度实验表明，该算法是有效的具体内容如下 在系统分析了图的顶点着色、边着色及全着色问题的基础上，将遗传算法与模拟退火方法和禁忌搜索方法结合，提出了图着色的混合遗传算法在混合方法中模拟退火算法用于局部寻优，以提高算法的收敛速度，同时防止出现早熟收敛禁忌搜索算法通过其记忆能力防止进化过程出现循环来提高全局寻优能力而遗传算法进行全局搜索并与贪婪遗传算法和Dsatur 算法进行了比较，结果表明，混合遗传算法的寻优质量优于对照算法然后在分析了混合遗传算法落入局部最优陷阱的原因后，增加了自适应策略和清空重填
