行政区划图自动着色的混合遗传算法

韩云; 郭庆胜; 章莉萍; 孙艳

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

行政区划图自动着色的混合遗传算法

韩云, 郭庆胜, 章莉萍, 孙艳

文章导航 > 武汉大学学报 ● 信息科学版 > 2007 > 32(8): 748-751

韩云, 郭庆胜, 章莉萍, 孙艳. 行政区划图自动着色的混合遗传算法[J]. 武汉大学学报 ● 信息科学版, 2007, 32(8): 748-751.

引用本文:

韩云, 郭庆胜, 章莉萍, 孙艳. 行政区划图自动着色的混合遗传算法[J]. 武汉大学学报 ● 信息科学版, 2007, 32(8): 748-751.

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.

Citation:

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.

行政区划图自动着色的混合遗传算法

¹ 武汉大学资源与环境科学学院,武汉市珞喻路129号,430079² 地理信息系统教育部重点实验室,武汉市珞喻路129号,430079³武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号, 430079

基金项目: 国家自然科学基金资助项目(40571133);测绘遥感信息工程国家重点实验室开放研究基金资助项目((04)0301);地理空间信息工程国家测绘局重点实验室开放研究基金资助项目(200625)

详细信息

作者简介:
韩云,硕士。主要从事网络地图设计的研究。

中图分类号: P283.1

Hybrid Genetic Algorithm for Coloring Administrative Map

¹ School of Resource and Environment System,Wuhan University,129 Luoyu Road,Wuhan 430079,China² Key Laboratory of Geographic Information System,Ministry of Education,Wuhan University,129 Luoyu Road,Wuhan 430079,China³ State Key Laboratory for Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,129 Luoyu Road,Wuhan 430079,China

Funds: 国家自然科学基金资助项目(40571133);测绘遥感信息工程国家重点实验室开放研究基金资助项目((04)0301);地理空间信息工程国家测绘局重点实验室开放研究基金资助项目(200625)

摘要: 结合贪心算法的局部搜索能力与遗传算法的全局搜索能力,研究了政区图四色着色问题的混合遗传算法,并在此基础上提出了一些改进措施。试验结果表明,这种混合遗传算法能有效地解决行政区划图自动着色问题,并取得了较好的结果。
- 地图设计 /
- 四色问题 /
- 贪心算法 /
- 混合遗传算法
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.
- map design /
- four-coloring problem /
- greedy algorithm /
- hybrid genetic algorithm

[1]	朱琳, 王圣凯, 袁伟舜, 董卫华, 刘纪平. 眼动控制的交互式地图设计 . 武汉大学学报 ● 信息科学版, 2020, 45(5): 736-743. doi: 10.13203/j.whugis20190165
[2]	信睿, 艾廷华, 晏雄锋, 杨敏. 相似性度量支持下的隐喻地图轮廓设计 . 武汉大学学报 ● 信息科学版, 2019, 44(4): 625-632. doi: 10.13203/j.whugis20170153
[3]	卢立果, 刘万科, 李江卫. 一种有效的LLL规约算法 . 武汉大学学报 ● 信息科学版, 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484
[4]	戴雪峰, 熊汉江, 龚健雅. 一种三维城市模型多纹理自动合并方法 . 武汉大学学报 ● 信息科学版, 2015, 40(3): 347-352+411.
[5]	汪华, 朱海红, 李霖. 利用地理属性量表的色盲人群地图色彩设计研究 . 武汉大学学报 ● 信息科学版, 2012, 37(4): 477-481.
[6]	周拥军, 邓才华. 利用HGA和单位四元数的相对定向解法 . 武汉大学学报 ● 信息科学版, 2011, 36(6): 670-673.
[7]	谷川, 潘国荣, 施贵刚, 陈兴权. 基于遗传算法的曲面拟合参数辨识 . 武汉大学学报 ● 信息科学版, 2009, 34(8): 983-986.
[8]	彭珊鸰, 何宗宜, 宋鹰, 谢锋. 图着色的混合遗传算法研究 . 武汉大学学报 ● 信息科学版, 2009, 34(12): 1499-1501.
[9]	邓红艳, 武芳, 翟仁健, 刘薇薇. 基于遗传算法的道路网综合模型 . 武汉大学学报 ● 信息科学版, 2006, 31(2): 164-167.
[10]	徐智勇, 艾廷华, 危拥军, 祝国瑞. 三维地图符号视觉参量研究 . 武汉大学学报 ● 信息科学版, 2006, 31(6): 557-560.
[11]	艾廷华, 朱熀, 王洪. 面向变化监控的动态电子地图设计 . 武汉大学学报 ● 信息科学版, 2005, 30(10): 858-861.
[12]	王家耀, 邓红艳. 基于遗传算法的制图综合模型研究 . 武汉大学学报 ● 信息科学版, 2005, 30(7): 565-569.
[13]	柯小平, 王勇, 许厚泽. 用遗传算法反演地壳的变密度模型 . 武汉大学学报 ● 信息科学版, 2004, 29(11): 981-984.
[14]	艾廷华. 基于Monte Carlo方法的不确定性地理现象可视化 . 武汉大学学报 ● 信息科学版, 2004, 29(3): 239-243,281.
[15]	朱家松, 龚健雅, 郑皓. 遗传算法在管网优化设计中的应用 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 363-367.
[16]	郑肇葆. 协同模型与遗传算法的集成 . 武汉大学学报 ● 信息科学版, 2001, 26(5): 381-386.
[17]	王新生, 姜友华, 涂超. 遗传算法在城市道路控制点标高优化设计中的应用 . 武汉大学学报 ● 信息科学版, 2001, 26(1): 82-85.
[18]	郑肇葆, 郑宏. 基于遗传算法的影像纹理分类 . 武汉大学学报 ● 信息科学版, 1998, 23(4): 337-339.
[19]	艾廷华. 电子新技术条件下的地图设计 . 武汉大学学报 ● 信息科学版, 1997, 22(2): 142-145.
[20]	何宗宜. 视错觉在地图制图中应用的研究 . 武汉大学学报 ● 信息科学版, 1991, 16(3): 22-30.

点击查看大图

计量

文章访问数: 594
HTML全文浏览量: 31
PDF下载量: 484
被引次数: 0

行政区划图自动着色的混合遗传算法

¹ 武汉大学资源与环境科学学院,武汉市珞喻路129号,430079² 地理信息系统教育部重点实验室,武汉市珞喻路129号,430079³武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号, 430079

作者简介:
韩云,硕士。主要从事网络地图设计的研究。

收稿日期: 2007-06-16
修回日期: 2007-06-16
刊出日期: 2007-08-05

中图分类号: P283.1

关键词:

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

English Abstract

Hybrid Genetic Algorithm for Coloring Administrative Map

¹ School of Resource and Environment System,Wuhan University,129 Luoyu Road,Wuhan 430079,China² Key Laboratory of Geographic Information System,Ministry of Education,Wuhan University,129 Luoyu Road,Wuhan 430079,China³ State Key Laboratory for Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,129 Luoyu Road,Wuhan 430079,China

Received Date: 2007-06-16
Rev Recd Date: 2007-06-16
Publish Date: 2007-08-05

Keywords:

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.

韩云, 郭庆胜, 章莉萍, 孙艳. 行政区划图自动着色的混合遗传算法[J]. 武汉大学学报 ● 信息科学版, 2007, 32(8): 748-751.

引用本文:

韩云, 郭庆胜, 章莉萍, 孙艳. 行政区划图自动着色的混合遗传算法[J]. 武汉大学学报 ● 信息科学版, 2007, 32(8): 748-751.

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.

Citation:

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.