Genetic Algorithms For Graph Coloring Problem

The graph coloring problem (GCP) is a widely studied combinatorial optimization problem. It is a fundamental problem in scientific computation and engineering design. In fact, several classes of reallife problems such as examination timetabling and frequency assignment can be modeled as GCP extensions. Yet, it cannot be expected that an algorithm can find, in polynomial time, a solution to an arbitrary GCP instance, because the GCP is NP-hard. Population-based approaches like genetic algorithms (GAs) provide a good alternative to solve the GCP because of GAs have been successfully applied to locate the global optimum of many complicated optimization problem. In this paper we conduct a research on the basic theory of genetic algorithm and present some effective algorithms on the graph coloring problem.In the third section of this paper, on the comprehensive study of some properties of proper k-vertex-coloring, k-edge-coloring, and total-coloring of a graph, the standard genetic algorithm for graph coloring is researched. The method involves hybridizing conventional heuristics such as greedy into genetic algorithm where possibly uses heuristics to decode chromosomes to color. With the hybrid approach, genetic algorithms are used to perform global exploitation among population while heuristics methods are used to perform local exploitation around chromosomes.In the fourth section of this paper, we take into account one of the main features of the problem: namely, the presence of large symmetries in the solution space. In fact, the degree of symmetry grows exponentially with the cardinality of the set of colors. The presence of large symmetries in the solution space will remain the convergence rate of the algorithm so low that good solutions may never be found. The major drawback of genetic algorithms has been identified as the crossover operator. So a standard crossover operator is not appropriate in this domain because there is very little improvement of the solutions. In this section, we present a method that breaks the symmetry of the graph coloring problem by matrix transformation and provide a improved general standard of genetic algorithms which can be used to solve many problems with a highly symmetric solution space . In the fifth section of this paper, we discover that the main cause of large symmetries in the solution space is that the structure of the simple chromosome is object oriented, instead of being group oriented. So, we present group genetic algorithms (GGA) to solve the graph coloring problem. The encoding schema we adopted in GGA makes the genes represent the groups. The most important difference is that crossover of GGA have to work with variable length chromosomes.