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

A application on new hybrid genetic algorithm for graph coloring

作　　者：曹莉[1] 程灏[1] 许钟[2] 

机构地区：[1]陕西师范大学计算机科学学院,陕西西安710062 [2]西北工业大学自动化学院,陕西西安710072

出　　处：《陕西师范大学学报（自然科学版）》2007年第3期24-27,共4页Journal of Shaanxi Normal University：Natural Science Edition

基　　金：国家自然科学基金资助项目(60503008)

摘　　要：将遗传算法与模拟退火方法和禁忌搜索方法结合,提出了应用于图着色的混合遗传算法.在混合方法中,模拟退火算法用于局部寻优,提高算法的收敛速度,同时防止早熟收敛;禁忌搜索算法通过记忆能力防止进化过程出现循环来提高全局寻优能力.用遗传算法进行全局搜索,并与贪婪遗传算法和Dsatur算法进行了比较,结果表明,混合遗传算法的寻优质量优于对照算法.这种改进的混合遗传算法可以在稠密图上获得更好的寻优效率,在稀疏图上其效率则略有下降,这表明设计的改进混合遗传算法的合理性和有效性.Combined with SA and TS, a hybrid genetic algorithm for the graph coloring problem （GCP） is proposed. In a hybrid algorithm, SA is used to local-optimize, which can accelerate the optimization process and avoid the premature convergence; TS is used to improve the global-optimize, which prevent the repeat between the new individual and the old individual through its memory function; GA is used to global search. The comparison is carried on with the Greedy GA and the Dsatur, the result indicate that the computing precision of hybrid algorithm is better than the antitheses. Experiments show that the improved hybrid algorithm can get better computing speed on density graph, but slow down on sparse graph. These make it clear that the improved hybrid genetic algorithm is rational and effective.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]