A New Genetic Algorithm For Graph Coloring

Genetic algorithm (GA) is a kind of globally random searching methods using natural evolution and genetic mechanism. Its application predominance lies in the ability to deal with complicated and non-linear problems which are difficult for traditional searching methods. Graph coloring problem (GCP) is one of the most widely studied combinatorial optimization problems with many applications both in theory and engineering. But it is also a well-known NP-complete problem. Therefore, designing efficient algorithm for this problem is not only of great theoretical value, but also of important application value.After analyzing the classical genetic algorithm, this paper presents a new improved genetic algorithm for the graph coloring problem. A novel scheme of producing the initial population is proposed, and it can ensure diversity of population and enhances convergence. Then an improved greedy partition crossover operator is designed and it can ensure that the big subsets of the vertices will not be destroyed. Moreover, two new mutation operators are proposed and they can increase diversity of population and improve local searching ability of the algorithm. Finally, The simulation experiments on some standard coloring instances are made and the simulation results indicate that the new improved genetic algorithm has good ability of searching optimal solution for various types of graphs.