Hybrid Genetic Algorithms For Graph Coloring Problems

Genetic algorithm is one kind of self-organized and adaptive random searching algorithms that simulate the evolution process and mechanism in nature for the optimization problems. Its coding technique and genetic operator are easy to execute. It has few requests or limitations to optimization problems, is very good at parallel and global search, and can be applied to a wide range of the problems such as machine learning, pattern recognition, image disposal, optimization controller, combinatorial optimization, manage decision-making and so on.The Graph Coloring Problem (GCP) is a classical NP-complete problem and basically a problem of partition of the graph vertice. Based on the vertex degree, a new initial population generation scheme is presented and a crossover operator using set intersection is designed. In order to enhance the exploration ability, a greedy local search is integrated into crossover to improve the quality of the crossover offspring. Based on these, a novel hybrid genetic algorithm is proposed for the graph coloring problem. The simulation results on ten standard benchmark problems show that the proposed algorithm can obtain good quality solution and is potential for graph coloring problems.Moreover, by using a probability distribution matrix to represent the individuals of the population, a new encoding scheme is presented, which decreases the memory requirement greatly. In order to enhance the speed of convergence, a new local search operator is designed to improve the offspring of crossover. The proposed algorithm will stop when the elements in the probability distribution matrix is equal to one or zero. Compared with the existing stop criterions, the new termination condition can be easily identified. Simulation results on benchmark problems demonstrate the proposed algorithm is of the fast convergence and good performance.