A memetic algorithm using partial solutions for graph coloring problem
- Resource Type
- Conference
- Authors
- Zhuang, Ziwei; Fan, Suohai; Xu, Hedong; Zheng, Jing
- Source
- 2016 IEEE Congress on Evolutionary Computation (CEC) Evolutionary Computation (CEC), 2016 IEEE Congress on. :3200-3206 Jul, 2016
- Subject
- Computing and Processing
Heuristic algorithms
Color
Algorithm design and analysis
Linear programming
Partitioning algorithms
Memetics
Greedy algorithms
graph coloring
partial solutions
memetic algorithm
- Language
Graph coloring is one of the most significant problems in combinatorial optimization. On the basis of the traditional evolutionary heuristic algorithm, this paper presents a memetic algorithm with partial solutions (MAP) for solving this problem. Moreover, we combine a special crossover operator based on the independent sets and a tabu search algorithm with a strong capacity of local search. Meanwhile the score function for individuals and the fitness function for updating process are improved. The experiment for DIMACS Benchmark shows that this algorithm can not only solve the general graphs, but also figure out the optimal solution to the flat series which cannot be solved well by most evolutionary heuristic algorithms. It proves that the memetic algorithm with partial solutions (MAP) has a good stability.