摘要
针对图着色对顶点划分的本质特征,提出了基于度的种群初始化方法和交集杂交算子;为加快算法的收敛速度,设计了新的贪婪局部搜索算子来改进杂交产生的后代个体。在此基础上,提出了图着色问题的一种新的混合遗传算法,对10个标准算例的仿真结果表明,新混合遗传算法可以获得问题高质量的解,是一种有潜力的算法。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2008年第28期57-59,共3页
Computer Engineering and Applications
基金
国家自然科学基金No.60374063~~
关键词
图着色问题
NP-完全问题
混合遗传算法
Graph Coloring Problem（GCP）
NP-eomplete problem
hybrid genetic algorithm
