中文摘要：

结合贪心算法的局部搜索能力与遗传算法的全局搜索能力，研究了政区图四色着色问题的混合遗传算法，并在此基础上提出了一些改进措施。试验结果表明，这种混合遗传算法能有效地解决行政区划图自动着色问题，并取得了较好的结果。

英文摘要：

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 ge- netic 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.