移位安全区约束下的建筑物群移位免疫遗传算法

doi:10.11947/j.AGCS.2021.20200395

测绘学报 ›› 2021, Vol. 50 ›› Issue (6): 812-822.doi: 10.11947/j.AGCS.2021.20200395

移位安全区约束下的建筑物群移位免疫遗传算法

刘远刚¹, 李少华¹, 蔡永香¹, 何贞铭¹, 马潇雅¹, 李鹏程¹, 郭庆胜², 何宗宜^1,2

1. 长江大学地球科学学院, 湖北武汉 430100;
2. 武汉大学资源与环境科学学院, 湖北武汉 430079

收稿日期:2020-08-16 修回日期:2021-02-18 发布日期:2021-06-28
通讯作者: 李少华 E-mail:lish@yangtzeu.edu.cn
作者简介:刘远刚(1982—),男,博士,副教授,研究方向为地理信息智能化处理与可视化。E-mail:liuygis@foxmail.com
基金资助:
国家自然科学基金（41701537；41871378）；地理信息工程国家重点实验室开放基金（sklgie2016-z-4-1；sklgie2017-m-4-6）

An immune genetic algorithm to buildings displacement with constraint of safety zones

LIU Yuangang¹, LI Shaohua¹, CAI Yongxiang¹, HE Zhenming¹, MA Xiaoya¹, LI Pengcheng¹, GUO Qingsheng², HE Zongyi^1,2

1. School of Geosciences, Yangtze University, Wuhan 430100, China;
2. School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China

Received:2020-08-16 Revised:2021-02-18 Published:2021-06-28
Supported by:
The National Natural Science Foundation of China (Nos. 41701537；41871378)；The Opened-end Fund of State Key Laboratory of Geo-information Engineering of China (Nos. sklgie2016-z-4-1；sklgie2017-m-4-6)

摘要/Abstract

摘要： 对于采用启发式或群智能搜索的组合最优化移位算法，地图要素空间关系与空间分布特征的保持是一个难题。本文基于免疫遗传算法提出一种移位安全区约束下的建筑物群最优化移位方法。该方法将建筑物群的移位问题定义为一个多目标最优化问题，然后采用免疫遗传算法搜索最优解。为了尽量保持建筑物群的空间关系和总体分布特征，避免出现拓扑错误，采用Voronoi图和缓冲区构建每个建筑物的移位安全区，以限定建筑物的移位范围；同时，采用建筑物群组整体移位策略，保持局部空间分布模式。最后，以北京市某部分街区建筑物群的移位为例验证改进算法的有效性，结果表明所实现算法能够在解决邻近冲突的同时，较好地保持地图目标间的空间关系和空间分布特征。

关键词: 地图综合, 移位, 邻近冲突, 免疫遗传算法, 建筑物群

Abstract: For the combinatorial optimization displacement algorithms based on heuristic search or swarm intelligence, it is a difficult problem to maintain the spatial relationship and distribution characteristics of map features. This article proposes an optimal algorithm to buildings displacement based on immune genetic algorithm (IGA) with the constraint of safety zones. In the study, the displacement problem of buildings is defined as a multi-objective optimization problem, and then the immune genetic algorithm is used to search the optimal solution. In order to keep the spatial relationship and globe spatial distribution characteristics of buildings as far as possible and avoid topology errors, Voronoi diagram and buffer areas are used to construct the displacement safety zone of each building to limit the displacement range of buildings; meanwhile, the strategy to shift the building group as a whole is used to keep local building patterns. Finally, the effectiveness of the improved algorithm is verified by taking the displacement of buildings in a block of beijing as an example. The results indicate that the algorithm can not only solve the proximity conflicts, but also keep the spatial relationship and spatial distribution characteristics of map objects.

Key words: map generalization, displacement, proximity conflict, immune genetic algorithm, buildings

中图分类号:

P208

刘远刚, 李少华, 蔡永香, 何贞铭, 马潇雅, 李鹏程, 郭庆胜, 何宗宜. 移位安全区约束下的建筑物群移位免疫遗传算法[J]. 测绘学报, 2021, 50(6): 812-822.

LIU Yuangang, LI Shaohua, CAI Yongxiang, HE Zhenming, MA Xiaoya, LI Pengcheng, GUO Qingsheng, HE Zongyi. An immune genetic algorithm to buildings displacement with constraint of safety zones[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(6): 812-822.

参考文献

[1] 王家耀, 李志林, 武芳. 数字地图综合进展[M]. 北京: 科学出版社, 2011. WANG Jiayao, LI Zhilin, WU Fang. Advances in digital map generalization[M]. Beijing: Science Press, 2011.
[2] BADER M. Energy minimization methods for feature displacement in map generalization[D]. Switzerland: University of Zurich, 2001.
[3] 艾廷华. 基于场论分析的建筑物群的移位[J]. 测绘学报, 2004, 33(1): 89-94. AI Tinghua. A displacement of building cluster based on field analysis[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(1): 89-94.
[4] 吴小芳, 杜清运, 徐智勇. 多层次移位原则的道路与建筑物空间冲突处理[J]. 测绘学报, 2010, 39(6): 649-654. WU Xiaofang, DU Qingyun, XU Zhiyong. Disposal of spatial conflict between roads and buildings based on the multilevel displacement principles[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(6): 649-654.
[5] 孙雅庚. 建筑物群与道路空间冲突解决的移位方法研究[D]. 武汉: 武汉大学, 2015. SUN Yageng. The displacement method research of conflict solution relate to buildings and roads[D]. Wuhan: Wuhan University, 2015.
[6] 刘远刚. 基于能量最小化原理的地图要素移位算法研究与改进[D]. 武汉: 武汉大学, 2015. LIU Yuangang. Research and improvement of cartographic displacement algorithms based on energy minimization principles[D]. Wuhan: Wuhan University, 2015.
[7] BURGHARDT D, MEIER S. Cartographic displacement using the snakes concept[C]//FÖRSTNER W, PLVMER L. Semantic Modeling for the Acquisition of Topographic Information from Images and Maps. Basel: Birkhaeuser Verlag, 1997: 59-71.
[8] BOBRICH J. Cartographic displacement by minimization of spatial and geometric conflicts[C]//Proceedings of the 20th International Cartographic Conference. Beijing: [s.n.], 2001: 2032-2042.
[9] BURGHARDT D, MEIER S. Cartographic displacement using the snakes concept[C]//FÖRSTNER W, PLVMER L.Semantic Modeling for the Acquisition of Topographic Information from Images and Maps. Basel: Birkhaeuser Verlag, 1997: 114-120.
[10] HARRIE L E. The constraint method for solving spatial conflicts in cartographic generalization[J]. Cartography and Geographic Information Science, 1999, 26(1): 55-69.
[11] HØJHOLT P. Solving space conflicts in map generalization: using a finite element method[J]. Cartography and Geographic Information Science, 2000, 27(1): 65-74.
[12] WARE J M, JONES C B. Conflict reduction in map generalization using iterative improvement[J]. GeoInformatica, 1998, 2(4): 383-407.
[13] WARE J M, JONES C B, THOMAS N. Automated map generalization with multiple operators: a simulated annealing approach[J]. International Journal of Geographical Information Science, 2003, 17(8): 743-769.
[14] MACKANESS W A, PURVES R S. Automated displacement for large numbers of discrete map objects[J]. Algorithmica, 2001, 30(2): 302-311.
[15] LONERGAN M, JONES C B. An iterative displacement method for conflict resolution in map generalization[J]. Algorithmica, 2001, 30(2): 287-301.
[16] WARE J M, WILSON I D, WARE J A,et al. A tabu search approach to automated map generalisation[C]//Proceedings of the 10th ACM International Symposium on Advances in Geographic Information Systems. New York, NY:ACM, 2002: 101-106.
[17] WILSON I D, WARE J M, WARE J A. A genetic algorithm approach to cartographic map generalisation[J]. Computers in Industry, 2003, 52(3): 291-304.
[18] SUN Yageng, GUO Qingsheng, LIU Yuangang,et al. An immune genetic algorithm to buildings displacement in cartographic generalization[J]. Transactions in GIS, 2016, 20(4), 585-612.
[19] HUANG Hesheng, GUO Qingsheng, SUN Yageng, et al. Reducing building conflicts in map generalization with an improved PSO algorithm[J]. ISPRS International Journal of Geo-Information, 2017, 6(5): 127.
[20] LI Wende, AI Tinghua, SHEN Yilang, et al. A novel method for building displacement based on multipopulation genetic algorithm[J]. Applied Sciences, 2020, 10(23): 8441. DOI: 10.3390/app10238441.
[21] 陈占龙, 叶文. 复杂面实体拓扑关系的精细化模型[J]. 测绘学报, 2019, 48(5): 630-642. DOI: 10.11947/j.AGCS.2019.20170531. CHEN Zhanlong, YE Wen. The precise model of complex planar objects’ topological relations[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(5): 630-642. DOI: 10.11947/j.AGCS.2019.20170531.
[22] ZHANG Lihua, TANG Lulu, JIA Shuaidong, et al. A collaborative simplification method for multiple coastlines based on the hierarchical triangulation network partition[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(2): 93-104. DOI: 10.11947/j.JGGS.2020.0210.
[23] AI Tinghua, ZHANG Xiang, ZHOU Qi, et al. A vector field model to handle the displacement of multiple conflicts in building generalization[J]. International Journal of Geographical Information Science, 2015, 29(8): 1310-1331. DOI: 10.1080/13658816.2015.1019886.
[24] LIU Yuangang, GUO Qingsheng, SUN Yageng, et al. A combined approach to cartographic displacement for buildings based on skeleton and improved elastic beam algorithm[J]. PLoS One, 2014, 9(12): e113953. DOI: 10.1371/journal.pone.0113953.
[25] CONS A. Constraint analysis(DA2)[R]. The Agent Project, Esprit/LTR/24 939, 2001.
[26] Swiss Society of Cartography. Topographic maps: map graphics and generalization[M]. Berne: Federal Office of Topography, 2005.
[27] 刘远刚, 郭庆胜, 蔡永香, 等. 基于CDT骨架线的地图目标邻近冲突识别[J]. 测绘工程, 2017, 26(8): 10-13, 19. LIU Yuangang, GUO Qingsheng, CAI Yongxiang, et al. Identifying proximity conflicts of map objects based on CDT skeleton[J]. Engineering of Surveying and Mapping, 2017, 26(8): 10-13, 19.
[28] 国家测绘局测绘标准化研究所. GB/T 20257.3—2006 国家基本比例尺地图图式第3部分: 1∶25000 1∶ 50000 1∶ 100000地形图图式[S]. 北京: 中国标准出版社, 2006. National Administration of Surveying, Mapping and Geoinformation of China. GB/T 20257.3—2006 Cartographic symbols for national fundamental scale maps—Part 3: Specifications for cartographic symbols 1∶25000 1∶50000 & 1∶100000 topographic maps[S]. Beijing: Standards Press of China, 2006.
[29] 郭庆胜, 李国贤, 王勇, 等. 直线排列建筑物群渐进式典型化方法[J]. 测绘学报, 2020, 49(10): 1354-1364. DOI: 10.11947/j.AGCS.2020.20190495. GUO Qingsheng, LI Guoxian, WANG Yong, et al. The method of progressive typification for building groups with straight linear patterns[J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(10): 1354-1364. DOI: 10.11947/j.AGCS.2020.20190495.
[30] ZHANG Xiang, AI Tinghua, STOTER J, et al. Building pattern recognition in topographic data: examples on collinear and curvilinear alignments[J]. Geoinformatica, 2013, 17(1): 1-33.
[31] 王煦法, 张显俊, 曹先彬, 等. 一种基于免疫原理的遗传算法[J]. 小型微型计算机系统, 1999, 20(2): 117-120. WANG Xufa, ZHANG Xianjun, CAO Xianbin, et al. An improved genetic algorithm based on immune principle[J]. Mini-Micro Systems, 1999, 20(2): 117-120.

移位安全区约束下的建筑物群移位免疫遗传算法

An immune genetic algorithm to buildings displacement with constraint of safety zones

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张新长, 何显锦, 孙颖, 黄健锋, 张志强. 多尺度空间数据联动更新技术研究现状及展望[J]. 测绘学报, 2022, 51(7): 1520-1535.
[2]	武芳, 杜佳威, 吴芳华. 海底地貌数据综合研究进展[J]. 测绘学报, 2022, 51(7): 1588-1605.
[3]	艾廷华, 张翔. 地理信息科学中尺度概念的诠释与表达[J]. 测绘学报, 2022, 51(7): 1640-1652.
[4]	杜佳威, 武芳, 朱丽, 刘呈熠, 王安东. 图形、图像融合利用的集成学习智能化简方法及其在岛屿岸线化简中的应用[J]. 测绘学报, 2022, 51(3): 373-387.
[5]	高晓蓉, 闫浩文, 禄小敏. 多尺度地图空间居民地语义相似度计算方法[J]. 测绘学报, 2022, 51(1): 95-103.
[6]	刘呈熠, 武芳, 巩现勇, 行瑞星, 杜佳威. 空间知识挖掘的自然面群聚集度聚类方法[J]. 测绘学报, 2021, 50(4): 544-555.
[7]	刘慧敏, 胡文柯, 唐建波, 石岩, 邓敏. 顾及功能语义特征的建筑物空间分布模式识别方法[J]. 测绘学报, 2020, 49(5): 622-631.
[8]	安晓亚, 成晓强. 矢量曲线的视觉清晰度及在网络地图综合中的应用[J]. 测绘学报, 2020, 49(2): 245-255.
[9]	郭庆胜, 李国贤, 王勇, 刘纪平, 魏智威. 直线排列建筑物群渐进式典型化方法[J]. 测绘学报, 2020, 49(10): 1354-1364.
[10]	郭庆胜, 刘洋, 李萌, 程晓茜, 何捷, 王慧慧, 魏智威. 基于网格模型的导航道路图渐进式化简方法[J]. 测绘学报, 2019, 48(11): 1357-1368.
[11]	郭庆胜, 魏智威, 王勇, 王琳. 特征分类与邻近图相结合的建筑物群空间分布特征提取方法[J]. 测绘学报, 2017, 46(5): 631-638.
[12]	李成名, 武鹏达, 印洁. 图数统一表达地理模型及自补偿方法[J]. 测绘学报, 2017, 46(10): 1688-1697.
[13]	付仲良, 翁宝凤, 胡玉龙. Stroke构造、移位一体化的道路网示意化方法[J]. 测绘学报, 2016, 45(9): 1115-1121.
[14]	郭庆胜, 王琳, 孙雅庚, 周林, 龙毅. 线图形简化与移位算子的协同方法[J]. 测绘学报, 2016, 45(7): 850-857.
[15]	晏雄锋, 艾廷华, 杨敏. 居民地要素化简的形状识别与模板匹配方法[J]. 测绘学报, 2016, 45(7): 874-882.