Hybrid genetic algorithm for Graph Coloring Problem

doi:10.3778/j.issn.1002-8331.2008.28.020

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-jiang¹,HAN Li-xia¹,WANG Yu-ping²

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.西安电子科技大学理学院，西安 710071
2.西安电子科技大学计算机学院，西安 710071

通讯作者: 兰绍江

Abstract

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-完全问题, 混合遗传算法

LAN Shao-jiang¹,HAN Li-xia¹,WANG Yu-ping². Hybrid genetic algorithm for Graph Coloring Problem[J]. Computer Engineering and Applications, 2008, 44(28): 57-59.

兰绍江¹,韩丽霞¹,王宇平². 图着色问题的混合遗传算法[J]. 计算机工程与应用, 2008, 44(28): 57-59.

[1]	LIU Lanfen, YANG Xinfeng. Searching Algorithm for Efficient Paths Based on Hybrid Genetic Algorithm [J]. Computer Engineering and Applications, 2019, 55(11): 244-249.
[2]	WEI Jiangxia, CHEN Tian’en, ZHANG Chi. Improved hybrid genetic algorithm and its application research to optimize agricultural distribution [J]. Computer Engineering and Applications, 2016, 52(2): 234-238.
[3]	ZHANG Henan, ZHANG Shaowen. Improved hybrid genetic algorithm for university timetabling problem [J]. Computer Engineering and Applications, 2015, 51(5): 240-246.
[4]	YOU Wei, LEI Dingyou, ZHU Xiang. Biased random-key hybrid genetic algorithm for three-dimensional loading problem [J]. Computer Engineering and Applications, 2014, 50(22): 265-270.
[5]	FU Hao, GE Hongwei, SHAO Changlu, ZHU Liang. Models and hybrid genetic algorithm for scheduling shipbuilding inspectors [J]. Computer Engineering and Applications, 2014, 50(21): 238-242.
[6]	LIU Bo1，2, LI Bo1, LI Yan1. Robust bilevel optimization model for emergency resource location and allocation under uncertain condition [J]. Computer Engineering and Applications, 2013, 49(16): 13-17.
[7]	LIU Fei，LV Shihui，ZHAO Zhonghua. Study of hybrid genetic algorithm based on multi-step reinforcement mutation operator [J]. Computer Engineering and Applications, 2011, 47(29): 46-48.
[8]	WANG Jianhua1，2，LI Nan2，GUO Hui2. Hybrid genetic algorithm for agile supply chain scheduling optimization [J]. Computer Engineering and Applications, 2011, 47(17): 224-228.
[9]	LI Nan1，2，GAO Pengdong1，LU Yongquan1，YU Wenhua1. Application research of parallel hybrid genetic algorithm in range images registration [J]. Computer Engineering and Applications, 2011, 47(12): 12-15.
[10]	LI Zhao-peng^1，2，CHENG Yun¹，LI Ken-li²，ZHOU Xu². Surface-based DNA algorithm for Hamiltonian path problem [J]. Computer Engineering and Applications, 2010, 46(8): 48-51.
[11]	LEI Yang，LI Shu-rong，ZHANG Qiang，ZHANG Xiao-dong. Novel hybrid GA based on bare bones PSO and its application [J]. Computer Engineering and Applications, 2010, 46(36): 7-10.
[12]	DU Zong-zong，LIU Guo-dong. Solution of TSP problem based on hybrid genetic simulated annealing algorithm [J]. Computer Engineering and Applications, 2010, 46(29): 40-42.
[13]	RONG Li-xia. Fuzzy simulation of vehicle routing problem under condition of fuzzy demand [J]. Computer Engineering and Applications, 2010, 46(18): 209-210.
[14]	YU Wu-yang. Hybrid genetic algorithm for transportation problem with multimodal transport [J]. Computer Engineering and Applications, 2009, 45(33): 10-12.
[15]	WANG Jian^1,2,3,WANG Hong-wei^1,2,3. Research on adaptive multi-objective resource-constrained transport task scheduling [J]. Computer Engineering and Applications, 2009, 45(14): 30-33.

Hybrid genetic algorithm for Graph Coloring Problem

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics