Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (28): 57-59.DOI: 10.3778/j.issn.1002-8331.2008.28.020

• 理论研究 • Previous Articles     Next Articles

Hybrid genetic algorithm for Graph Coloring Problem

LAN Shao-jiang1,HAN Li-xia1,WANG Yu-ping2   

  1. 1.School of Science,Xidian University,Xi’an 710071,China
    2.School of Computer,Xidian University,Xi’an 710071,China
  • Received:2008-04-10 Revised:2008-06-23 Online:2008-10-01 Published:2008-10-01
  • Contact: LAN Shao-jiang

图着色问题的混合遗传算法

兰绍江1,韩丽霞1,王宇平2   

  1. 1.西安电子科技大学 理学院,西安 710071
    2.西安电子科技大学 计算机学院,西安 710071
  • 通讯作者: 兰绍江

Abstract: Based on the partition characteristic of the Graph Coloring Problem(GCP),a new initialization is presented taking into account of the vertex degree.An intersection crossover operator is designed for the graph coloring problem.In order to enhance the exploration ability,a greedy local search is integrated to improve the offspring of the crossover.Based on these,a novel hybrid genetic algorithm is proposed for the graph coloring problem.The simulation results on ten standard benchmark problems show that the proposed algorithm can obtain good quality solution and it is a potential algorithm for the problem studied.

Key words: Graph Coloring Problem(GCP), NP-complete problem, hybrid genetic algorithm

摘要: 针对图着色对顶点划分的本质特征,提出了基于度的种群初始化方法和交集杂交算子;为加快算法的收敛速度,设计了新的贪婪局部搜索算子来改进杂交产生的后代个体。在此基础上,提出了图着色问题的一种新的混合遗传算法,对10个标准算例的仿真结果表明,新混合遗传算法可以获得问题高质量的解,是一种有潜力的算法。

关键词: 图着色问题, NP-完全问题, 混合遗传算法