Heuristic-Based Genetic Algorithm for Graph Coloring Problem

Evolutionary algorithms (EA) are stochastic approaches utilized to solve NP-hard problems. Although EAs can find their paths towards optimal points through enough generations, the whole process might be time-consuming. In this paper we propose a novel evolutionary approach in which some heuristics are exercised as guidelines to make the evolutionary process move faster to superior solutions. Graph coloring problem (GCP), as a typical NP-hard problem, is used to outline the performance of the proposed approach. Experimental results show that our approach is impressively comparable with parallel evolutionary methods in terms of quickly achieving solutions.

Heuristic-Based Genetic Algorithm for Graph Coloring Problem Keywords:

Constraint satisfaction problem , Evolutionary algorithms , Heuristic search , NP-hard problems