Solving Graph Coloring Problems Using Cultural Algorithms

In this paper, we combine a novel Sequential Graph Coloring Heuristic Algorithm (SGCHA) with a non-systematic method based on a cultural algorithm to solve the graph coloring problem (GCP). The GCP involves finding the minimum number of colors for coloring the graph vertices such that adjacent vertices have distinct colors. In our solving approach, we first use an estimator which is implemented with SGCHA to predict the minimum colors. Then, in the non-systematic part which has been designed using cultural algorithms, we improve the prediction. Various components of the cultural algorithm have been implemented to solve the GCP with a self adaptive behavior in an efficient manner. As a result of utilizing the SGCHA and a cultural algorithm, the proposed method is capable of finding the solution in a very efficient running time. The experimental results show that the proposed algorithm has a high performance in time and quality of the solution returned for solving graph coloring instances taken from DIMACS website. The quality of the solution is measured here by comparing the returned solution with the optimal one.