A Study on Hybrid Genetic Algorithms in Graph Coloring Problem

摘要

The field of mathematics plays a vital role in various fields. One of the most important areas in mathematics is graph theory. Graph coloring arises naturally in a variety of applications such as register allocation and timetable, examination scheduling, map coloring, radio frequency assignment, pattern matching, Sudoku, telecommunication and bioinformatics. Graph coloring problem is a combinatorial optimization problem applicable in many problems existing nowadays. To solve the graph coloring problem, Genetic Algorithm, a calculus free optimization technique based on principles of natural selection for reproduction and various evolutionary operations such as crossover and mutation is used. Many algorithms are available to solve a Graph coloring problem. A recent and very promising approach is to embed local search into the framework of Evolutionary algorithm. This approach of hybridization is very powerful and these algorithms are carried out on large DIMACS challenge benchmark graphs. The results are very competitive and even better than those of state of the art algorithms. This paper focuses on reviewing the recent literature on hybrid genetic algorithm, and recommending state of the art algorithm in GCP.