混合遗传算法在图着色及MSA问题中的应用

摘要

图着色问题和MSA 问题都是被广泛研究的组合优化问题，同时它们也都是典型的NP 完全问题，随着图的规模的增大或比对序列个数的增加，计算量将会以指数的速度增加到不可接受的地步。遗传算法、模拟退火算法、禁忌搜索算法都是求解NP 完全问题的有效方法。本文首先对遗传算法的基本原理和框架进行详细介绍，然后对图着色问题和多序列比对问题进行了相应的研究，提出将遗传算法与模拟退火算法及禁忌搜索算法结合在一起的混合遗传算法。该算法充分发挥了它们的优越性，提高了求解GCP 问题和MSA 问题的精度与速度。实验表明，该算法是有效的。具体内容如下： 在系统分析了图的顶点着色、边着色及全着色问题的基础上，将遗传算法与模拟退火方法和禁忌搜索方法结合，提出了图着色的混合遗传算法。在混合方法中：模拟退火算法用于局部寻优，以提高算法的收敛速度，同时防止出现早熟收敛；禁忌搜索算法通过其记忆能力防止进化过程出现循环来提高全局寻优能力；而遗传算法进行全局搜索。并与贪婪遗传算法和Dsatur 算法进行了比较，结果表明，混合遗传算法的寻优质量优于对照算法。然后在分析了混合遗传算法落入局部最优陷阱的原因后，增加了自适应策略和清空重填策略使算法尽快跳出陷阱，通过实验表明在保持寻优质量的同时，这种改进的混合遗传算法可以在稠密图上获得更好的寻优效率，在稀疏图上其效率则略有下降。这表明文中设计的改进混合遗传算法的合理性和有效性。 在图的着色问题上获得成功后，本文又尝试将这种混合遗传算法用于MSA 问题。首先系统介绍了多序列比对的概念、比对记分方法、现有的几种多序列比对算法的优缺点，然后针对于MSA 问题的特点重新构建了染色体空间，引入SP_AFFINE 打分函数衡量比对质量，对遗传算子（选择算子、交叉算子、突变算子、模拟退火算子、禁忌搜索算子）根据需要进行了相应的修改，为了进一步提高比对的质量和效率，引入初始化算子和移位算子。初始化算子采用类似于星比对的方法使种群的第一代位于较接近最优比对的位置，移位算子通过在若干连续空位的邻域内移动它们以找到局部的最佳比对。通过与CLUSTALW 算法进行比较的结果表明，混合遗传算法在我们选择的测试数据上都获得了较好的比对质量，但是其寻优效率却远远落后于CLUSTALW 算法，这是由混合遗传算法自身的特点所决定的。这表明文中设计的混合遗传算法主要适用于不需要快速得出比对结果或需要提供多组比对结果的情况。