A hierarchical parallel genetic approach for the graph coloring problem

摘要

Graph Coloring Problems (GCPs) are constraint optimization problems with various applications including time tabling and frequency allocation. The GCP consists in finding the minimum number of colors for coloring the graph vertices such that adjacent vertices have distinct colors. We propose a hierarchical approach based on Parallel Genetic Algorithms (PGAs) to solve the GCP. We call this new approach Hierarchical PGAs (HPGAs). In addition, we have developed a new operator designed to improve PGAs when solving constraint optimization problems in general and GCPs in particular. We call this new operator Genetic Modification (GM). Using the properties of variables and their relations, GM generates good individuals at each iteration and inserts them into the PGA population in the hope of reaching the optimal solution sooner. In the case of the GCP, the GM operator is based on a novel Variable Ordering Algorithm (VOA) that we propose. Together with the new crossover and the estimator of the initial solution we have developed, GM allows our solving approach to converge towards the optimal solution sooner than the well known methods for solving the GCP, even for hard instances. This was indeed clearly demonstrated by the experiments we conducted on the GCP instances taken from the well known DIMACS website.