Abstract—Graph coloring problem (GCP) is of great interest to the researchers in the area of soft computing. To solve GCP, we present a memetic algorithm (MA) that uses classical crossover operation as the main variation operator and a deterministic local improvement technique. For the first time in the literature, we use binary encoded chromosomes for GCP, which makes both the crossover and the local improvement easier. In the traditional evolutionary algorithm (EA) for GCP, k-coloring is used and the EA is run repeatedly until the lowest possible k is reached. In our MA, we start with the theoretical upper bound of chromatic number (maximum out-degree + 1) and in the process of evolution some of the colors are made unused to dynamically reduce the number of color. Thus, the solution is found in a single run of the MA reducing the total execution time in comparison to running k-coloring for several times. We experiment with 23 datasets taken from standard DIMACS benchmark and compare the result with several recent works. For all but one dataset, we obtain the minimum chromatic number stated in the DIMACS benchmark. For the remaining one dataset (queen10_10.col), we obtain better solution than others.
Index Terms—Binary encoding, dynamicity, graph coloring, local improvement, memetic algorithm, metaheuristics.
H. A. R. Chowdhury, T. Farhat, and M. H. A. Khan are with Department of Computer Science and Engineering, East West University, Aftabnagar, Dhaka 1212, Bangladesh (e-mail: hrcrabat@gmail.com, lvuplf@gmail.com, mhakhan@ewubd.edu).
[PDF]
Cite:Hasin Al Rabat Chowdhury, Tasneem Farhat, and Mozammel H. A. Khan, "Memetic Algorithm to Solve Graph Coloring Problem," International Journal of Computer Theory and Engineering vol. 5, no. 6, pp. 890-894, 2013.
