一种应用于图着色问题的新型混合遗传算法

摘要：

将遗传算法与模拟退火方法和禁忌搜索方法结合,提出了应用于图着色的混合遗传算法.在混合方法中,模拟退火算法用于局部寻优,提高算法的收敛速度,同时防止早熟收敛;禁忌搜索算法通过记忆能力防止进化过程出现循环来提高全局寻优能力.用遗传算法进行全局搜索,并与贪婪遗传算法和Dsatur算法进行了比较,结果表明,混合遗传算法的寻优质量优于对照算法.这种改进的混合遗传算法可以在稠密图上获得更好的寻优效率,在稀疏图上其效率则略有下降,这表明设计的改进混合遗传算法的合理性和有效性.

关键词：遗传算法、自适应混合遗传算法、自适应模拟退火算子、禁忌算子

所属期刊栏目：35

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金60503008

在线出版日期：2007-10-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：24-27