| 行政区划图自动着色的混合遗传算法 |
| |
| 引用本文： | 韩云,郭庆胜,章莉萍,孙艳.行政区划图自动着色的混合遗传算法[J].武汉大学学报(信息科学版),2007,32(8):748-751. |
| |
| 作者姓名： | 韩云 郭庆胜 章莉萍 孙艳 |
| |
| 作者单位： | 1. 武汉大学资源与环境科学学院,武汉市珞喻路129号,430079;地理信息系统教育部重点实验室,武汉市珞喻路129号,430079
2. 武汉大学资源与环境科学学院,武汉市珞喻路129号,430079;地理信息系统教育部重点实验室,武汉市珞喻路129号,430079;武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079 |
| |
| 基金项目： | 国家自然科学基金;国家重点实验室基金;国家重点实验室基金 |
| |
| 摘 要： | 结合贪心算法的局部搜索能力与遗传算法的全局搜索能力,研究了政区图四色着色问题的混合遗传算法,并在此基础上提出了一些改进措施。试验结果表明,这种混合遗传算法能有效地解决行政区划图自动着色问题,并取得了较好的结果。
|
| 关 键 词： | 地图设计 四色问题 贪心算法 混合遗传算法 |
| 文章编号： | 1671-8860（2007）08-0748-04 |
| 修稿时间： | 2007-06-16 |
Hybrid Genetic Algorithm for Coloring Administrative Map |
| |
| HAN Yun,GUO Qingsheng,ZHANG Liping,SUN Yan.Hybrid Genetic Algorithm for Coloring Administrative Map[J].Geomatics and Information Science of Wuhan University,2007,32(8):748-751. |
| |
| Authors: | HAN Yun GUO Qingsheng ZHANG Liping SUN Yan |
| |
| Institution: | 1.School of Resource and Environment System,Wuhan University, 129 Luoyu Road,Wuhan 430079,China;2. Key Laboratory of Geographic Information System,Ministry of Education,Wuhan University, 129 Luoyu Road,Wuhan 430079,China;3.State Key Laboratory for Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan 430079,China |
| |
| Abstract: | 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. |
| |
| Keywords: | map design four-coloring problem greedy algorithm hybrid genetic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
