Hybrid Genetic Algorithm for Coloring Administrative Map

Four-coloring map problem is a typical NP-complete problem.As a global search technique for optimization,genetic algorithms(GA) has an apparent advantage for solving these NP-complement problems.But sometimes an optimal solution is not gotten by means of a simple genetic algorithm.In order to solve this problem,combined with the local search of greedy algorithm and the global search of genetic algorithms,a hybrid genetic algorithm about administrative map coloring is studied and improved.In the process of this hybrid genetic algorithm,every individual in the population is not same with other individuals in this population;this is tested after selection operator,reproduction operator,crossover operator and mutation operator.The greedy algorithm can be used to get the new population in every new generation.This hybrid genetic algorithm has been tested in a computer with 256 MB and Pentium 3,and has been used to color the China Administrative Map and the Hubei Province Administrative Map with 4 kinds of colors.The results show that the hybrid genetic algorithms can solve the problem of coloring administrative map efficiently and obtain optimal solutions.