基于遗传算法的制图综合研究
|
摘要
本文在论述现有自动制图综合的特点和难点的基础上，尝试将遗传算法这一新的智能化计算方法用于自动制图综合。论述了作者利用遗传算法对自动制图综合中点群目标选取，线要素化简，注记配置，道路网综合等几个方面的研究，结合综合的各自不同目的和要求，作者建立了以下几种基于遗传算法的制图综合模型：
1．基于遗传算法的点群目标选取模型
在分析现有点群目标选取模型的基础上，结合点群分布范围，分布密度，综合后需要保留点的数量，重要点目标需要保存等特征，巧妙地将物理学中的力学知识来描述点点之间的关系，结合遗传算法的基本特性，提出了基于遗传算法的点群目标选取模型。实验结果表明，基于遗传算法的点群目标选取模型克服了凸包选取模型、圆选取模型等的缺限，较为全面地考虑了点群目标选取的各种选取指标，具有较好的实用性。
2．基于遗传算法的线要素化简模型
本文在指出线要素化简的实质就是在保证精度的前提下使点尽可能少的基础上，结合线要素化简的经典算法Douglas-Peucker的思想，建立了基于遗传算法的线要素化简模型。将实验结果与Douglas-Peucker的结果进行比较，发现在同等精度下，基于遗传算法的线要素化简模型的压缩效果更加明显。
3．基于遗传算法的注记配置模型
在对现有注记配置方法分析的基础上，结合制图中注记配置的基本原理和要求，利用遗传算法对点、线、面注记分别进行配置，并取得较好的结果。
4．基于遗传算法的道路网综合模型
本论文在考虑道路网的拓扑信息等结构化信息的基础上，简单地将最短路径作为经济实用价值的评估标准，结合遗传算法的基本框架建立了基于遗传的道路网综合模型，并通过实验进行了论证，克服了传统的道路网综合一般情况下道路的结构化和经济实用价值等社会因素难以进行综合考虑的困难。
On the basis of the analyzing the characteristics and difficulties of automated cartographic generalization, this article attempts to solve automated cartographic generalization by genetic algorithms (GA), which is a new intellectualized algorithms. According to the different propose and request, we think up several models of cartographic generalization based on genetic algorithms:
1. Point Cluster Selection Based on Genetic Algorithms
Based on analyzing the existing models of point cluster selection, considering of the range of distributing, the density of distributing, the reserved number, the importance of object and so on, combining the principles of genetic algorithms, we use the physical power to assimilate to the connection between points subtly, and put forward the model of point cluster selection based on genetic algorithms. The experimental output indicates that this model can conquer the shortcomings of exciting models and can keep general characteristics, get good results.
2. Automated Line Simplification Based on Genetic Algorithms
This article points out that essential of line simplification is to get lest points and keep the precision. Combined the soul of the Douglas-peucker operator, we think out the model of line simplification based on genetic algorithms. It is easy to find that the model of line simplification based on genetic algorithms can get better output.
3. Feature Labeling Based on Genetic Algorithms
Label is a very important part of Map Information. It is very important to study good labeling method. This article tries to apply genetic algorithms in feature labeling based on the viewpoint that labeling is a hard NP problem. Based on the keystone and method of genetic algorithms, combined with the based model of feature labeling, we discuss the method of point based on genetic algorithms and the keys to the method.
4. Road Net Generalization Based on GA
Based on the structural information of road net, this article put the economical factors into considering. Combining with the basic framework of genetic algorithms, this article putout a model of road net generalization based on GA. The experimental output indicates this model is applied.
1．基于遗传算法的点群目标选取模型
在分析现有点群目标选取模型的基础上，结合点群分布范围，分布密度，综合后需要保留点的数量，重要点目标需要保存等特征，巧妙地将物理学中的力学知识来描述点点之间的关系，结合遗传算法的基本特性，提出了基于遗传算法的点群目标选取模型。实验结果表明，基于遗传算法的点群目标选取模型克服了凸包选取模型、圆选取模型等的缺限，较为全面地考虑了点群目标选取的各种选取指标，具有较好的实用性。
2．基于遗传算法的线要素化简模型
本文在指出线要素化简的实质就是在保证精度的前提下使点尽可能少的基础上，结合线要素化简的经典算法Douglas-Peucker的思想，建立了基于遗传算法的线要素化简模型。将实验结果与Douglas-Peucker的结果进行比较，发现在同等精度下，基于遗传算法的线要素化简模型的压缩效果更加明显。
3．基于遗传算法的注记配置模型
在对现有注记配置方法分析的基础上，结合制图中注记配置的基本原理和要求，利用遗传算法对点、线、面注记分别进行配置，并取得较好的结果。
4．基于遗传算法的道路网综合模型
本论文在考虑道路网的拓扑信息等结构化信息的基础上，简单地将最短路径作为经济实用价值的评估标准，结合遗传算法的基本框架建立了基于遗传的道路网综合模型，并通过实验进行了论证，克服了传统的道路网综合一般情况下道路的结构化和经济实用价值等社会因素难以进行综合考虑的困难。
On the basis of the analyzing the characteristics and difficulties of automated cartographic generalization, this article attempts to solve automated cartographic generalization by genetic algorithms (GA), which is a new intellectualized algorithms. According to the different propose and request, we think up several models of cartographic generalization based on genetic algorithms:
1. Point Cluster Selection Based on Genetic Algorithms
Based on analyzing the existing models of point cluster selection, considering of the range of distributing, the density of distributing, the reserved number, the importance of object and so on, combining the principles of genetic algorithms, we use the physical power to assimilate to the connection between points subtly, and put forward the model of point cluster selection based on genetic algorithms. The experimental output indicates that this model can conquer the shortcomings of exciting models and can keep general characteristics, get good results.
2. Automated Line Simplification Based on Genetic Algorithms
This article points out that essential of line simplification is to get lest points and keep the precision. Combined the soul of the Douglas-peucker operator, we think out the model of line simplification based on genetic algorithms. It is easy to find that the model of line simplification based on genetic algorithms can get better output.
3. Feature Labeling Based on Genetic Algorithms
Label is a very important part of Map Information. It is very important to study good labeling method. This article tries to apply genetic algorithms in feature labeling based on the viewpoint that labeling is a hard NP problem. Based on the keystone and method of genetic algorithms, combined with the based model of feature labeling, we discuss the method of point based on genetic algorithms and the keys to the method.
4. Road Net Generalization Based on GA
Based on the structural information of road net, this article put the economical factors into considering. Combining with the basic framework of genetic algorithms, this article putout a model of road net generalization based on GA. The experimental output indicates this model is applied.
引文
[1] 高俊：地图学四面体—数字化时代地图学的诠释，军事地图制图与地理信息工程发展与展望，2002。
[2] 艾廷华：城市地图数据库综合的支撑数据模型与方法的研究，武汉大学博士学位论文，2000。
[3] 李爱勤：无缝空间数据组织及其多比例尺表达与处理研究，武汉大学博士学位论文，2001。
[4] 盛业华，郭达志：GIS环境下空间要素的制图综合方法，测绘通报，1995(3)。
[5] 尹连旺，李京：GIS中基本要素的无级比例尺数据处理技术研究，北京大学学报(自然科学版)，1999(11)。
[6] 王占昌：无级比例尺GIS中空间属性的自动综合，辽宁师范大学学报(自然科学版)，2002(6)。
[7] 武芳：地图设计与编绘，解放军测绘学院教材，1997。
[8] 王家耀、武芳：数字地图自动制图综合原理与方法，解放军出版社，1997。
[9] 武芳：协同式地图自动制图综合的研究与实现，解放军测绘学院博士学位论文，2000。
[10] 李敏强，寇纪凇，林丹等：遗传算法的基本原理与应用，科学出版社，2002。
[11] 张文修，梁怡．遗传算法的数学基础，西安交通大学出版社，1999。
[12] 李敏强等：遗传算法的基本理论与应用，科学出版社，2002。
[13] 王家耀、邹建华：地图制图数据处理的模型方法，解放军出版社，1989。
[14] 胡鹏等：地图代数，武汉大学出版社，2002。
[15] 王家耀等：普通地图制图综合原理，测绘出版社，1992。
[16] 祝国瑞，郭礼珍，尹贡白，徐永利：地图设计与编绘，武汉大学出版社，2001。
[17] 陈芬、江南：地图设计，解放军测绘学院教材，1999。
[18] 艾廷华，刘耀林：保持空间分布特征的点群化简方法，测绘学报，2002(2)。
[19] 毋河海：凸壳原理在点群目标综合中的应用，测绘工程，1997(6)。
[20] 王桥等：基于分形分析的自动化制图综合研究，测绘学报，1995(8)。
[21] 王桥，毋河海：地图信息的分形描述与自动综合研究，武汉测绘科技大学出版社，1998。
[22] 郭仁忠：空间分析，武汉测绘科技大学出版社，1997。
[23] 贾奋励：电子地图多尺度表达的理论与方法的研究，解放军信息工程大学硕士学位论文，2002。
[24] 钱海忠：基于Agent的自动综合算法研究，解放军信息工程大学硕士学位论文，2002。
[25] 田震：基于神经元网络的自动制图综合研究，解放军测绘学院博士学位论文，1997。
[26] 蔡少华：GIS图形空间关系的研究与实践．解放军测绘学院博士学位论文，1999。
[27] 王光霞：自动制图综合系统的研究及居民地道路自动综合的实现，解放军信息工程大学硕士学
位论文，1994。
[28] 安敏：地貌形态自动综合研究，解放军测绘学院硕士学位论文，1993。
[29] 郭建：1：25万数据库支持下居民地道路的自动综合，解放军测绘学院硕士学位论文，1993。
[30] 华一新，吴升，赵军喜：地理信息系统原理与技术，解放军出版社，1997。
[31] 杜瑞颖，刘镜年：面状地物名称注记的自动定位研究，测绘学报，1999(4)。
[32] 杜世宏：地名注记自动配置的关键技术研究，武汉大学硕士学位论文，2001。
[33] 李艳：GIS中地图注记配置的设计与实现，硕士论文，解放军信息工程大学硕士学位论文。2000。
[34] 刘春，从爱岩：基于“规则知识”的GIS水系要素制图综合推理，测绘通报，1999(9)。
[35] 陈军，赵仁亮：GIS空间关系的基本问题与研究进展，测绘学报，1999(5)。
[36] 潘正君，康立山等：演化计算，清华大学出版社，1998。
[37] 侯格贤：遗传算法性能及其在聚类分析中应用的研究，西安电子科技大学博士学位论文，1999。
[38] 樊红，张组勋，杜道生：地图线状要素自动注记的算法设计与实现，测绘学报，1999(2)。
[39] 吉根林：遗传算法在数据挖掘中的应用，信息技术，2001(12)。
[40] 李世平等：图象分割中的遗传算法，系统仿真学报，2002(2)。
[41] 赵新煜，陈文伟等：遗传算法和遗传规划的对比研究，系统工程与电子技术。2000(12)。
[42] 陈真勇，何永勇等：基于遗传进化的最近邻聚类算法及其应用，控制与决策，2002(7)。
[43] 曹阳，方强等：基于遗传算法的多连接表达式并行查询优化，软件学报，2002(2)。
[44] 万幼川：基于数学形态学面状要素自动注记，计算机与数字工程，1998(2)。
[45] 李忠文：利用遗传算法解决分布式数据库系统中的数据分配问题，山西大学学报(自然科学版)，2001(2)。
[46] 许国艳，史宇清：遗传算法在关联规则挖掘中的应用，计算机工程，2002(7)。
[47] 钟波等：一种基于遗传算法的数据预处理组合方法，西南师范大学学报(自然科学版)，2002(8)。
[48] 王新生，姜友华等：遗传算法在城市道路控制点标高优化设计中的应用，武汉大学学报(信息科学版)，2001(2)。
[49] 郭革新：演化计算---探讨测绘最优化问题的新技术，测绘通报，1999(9)。
[50] 邓红艳，武芳：基于遗传算法的空间聚类分析，测绘通报，2003(1)。
[51] 邓红艳，武芳：遗传算法在点注记自动配置中的应用，解放军测绘学院学报，2003(2)。
[52] Oosterom, P. van:The Desingn and Implementation of A Multi-Scale GlC, Proceedings ECGIS, 1993.
[53] Yi Lu, Jinghai Du, Jingsheng Zhai: A Model of Point Cluster Generalization with Spatial Distribution Features Recognized and Measured, ICC2001.
[54] Holland, J. H:Outline for a logicaI theory of adaptive systems[J]. Journal of the Association for Computing Machinery, 1962.
[55] Whitley, L. D:Foundations of genetic algorithms, San Mateo, 1993.
[56] Srinivas Doddi,Madhav V.Marathe, Andi Mirzaian, Bernard M.E.Moret, Binhai Zhu:Map Labeling and Its Generalizations.
[57] Deng Hongyan, Wu Fang:The Spatial Analyse of Clustering Based on Genetic Algorithms, ISPRS2002.
[58] William B. Poland, Ross D. Shachter:Three Approaches to Probability Model Selection, In Uncertainty in Artificial Intelligence, Proceedings of the Tenth Conference, 1994.
[59] olli Jaakkola:Multi-scale Categorical Data Bases with Automatic Generalization Transformations Based on Map Algebra, Cartography and Geographic Information Systems, 1998(10).
[60] Dianne E. Richardson, William A. Mackaness:Introduction Computational Processes for Map Gneralization, 1999(1).
[61] Andriani Skopeliti, Lysandro Tsoulos:A Knowledge Based Approach for the Generalization of Linear Features.
[62] Joachim Bobrich:Cartographic Displacement by Minimization of Spatial and Geometric Conflicts.
[63] Tapani Sarjakoski:Holistic Cartographic Generalization by Least Squares Adjustment for Large Data Sets.
[2] 艾廷华：城市地图数据库综合的支撑数据模型与方法的研究，武汉大学博士学位论文，2000。
[3] 李爱勤：无缝空间数据组织及其多比例尺表达与处理研究，武汉大学博士学位论文，2001。
[4] 盛业华，郭达志：GIS环境下空间要素的制图综合方法，测绘通报，1995(3)。
[5] 尹连旺，李京：GIS中基本要素的无级比例尺数据处理技术研究，北京大学学报(自然科学版)，1999(11)。
[6] 王占昌：无级比例尺GIS中空间属性的自动综合，辽宁师范大学学报(自然科学版)，2002(6)。
[7] 武芳：地图设计与编绘，解放军测绘学院教材，1997。
[8] 王家耀、武芳：数字地图自动制图综合原理与方法，解放军出版社，1997。
[9] 武芳：协同式地图自动制图综合的研究与实现，解放军测绘学院博士学位论文，2000。
[10] 李敏强，寇纪凇，林丹等：遗传算法的基本原理与应用，科学出版社，2002。
[11] 张文修，梁怡．遗传算法的数学基础，西安交通大学出版社，1999。
[12] 李敏强等：遗传算法的基本理论与应用，科学出版社，2002。
[13] 王家耀、邹建华：地图制图数据处理的模型方法，解放军出版社，1989。
[14] 胡鹏等：地图代数，武汉大学出版社，2002。
[15] 王家耀等：普通地图制图综合原理，测绘出版社，1992。
[16] 祝国瑞，郭礼珍，尹贡白，徐永利：地图设计与编绘，武汉大学出版社，2001。
[17] 陈芬、江南：地图设计，解放军测绘学院教材，1999。
[18] 艾廷华，刘耀林：保持空间分布特征的点群化简方法，测绘学报，2002(2)。
[19] 毋河海：凸壳原理在点群目标综合中的应用，测绘工程，1997(6)。
[20] 王桥等：基于分形分析的自动化制图综合研究，测绘学报，1995(8)。
[21] 王桥，毋河海：地图信息的分形描述与自动综合研究，武汉测绘科技大学出版社，1998。
[22] 郭仁忠：空间分析，武汉测绘科技大学出版社，1997。
[23] 贾奋励：电子地图多尺度表达的理论与方法的研究，解放军信息工程大学硕士学位论文，2002。
[24] 钱海忠：基于Agent的自动综合算法研究，解放军信息工程大学硕士学位论文，2002。
[25] 田震：基于神经元网络的自动制图综合研究，解放军测绘学院博士学位论文，1997。
[26] 蔡少华：GIS图形空间关系的研究与实践．解放军测绘学院博士学位论文，1999。
[27] 王光霞：自动制图综合系统的研究及居民地道路自动综合的实现，解放军信息工程大学硕士学
位论文，1994。
[28] 安敏：地貌形态自动综合研究，解放军测绘学院硕士学位论文，1993。
[29] 郭建：1：25万数据库支持下居民地道路的自动综合，解放军测绘学院硕士学位论文，1993。
[30] 华一新，吴升，赵军喜：地理信息系统原理与技术，解放军出版社，1997。
[31] 杜瑞颖，刘镜年：面状地物名称注记的自动定位研究，测绘学报，1999(4)。
[32] 杜世宏：地名注记自动配置的关键技术研究，武汉大学硕士学位论文，2001。
[33] 李艳：GIS中地图注记配置的设计与实现，硕士论文，解放军信息工程大学硕士学位论文。2000。
[34] 刘春，从爱岩：基于“规则知识”的GIS水系要素制图综合推理，测绘通报，1999(9)。
[35] 陈军，赵仁亮：GIS空间关系的基本问题与研究进展，测绘学报，1999(5)。
[36] 潘正君，康立山等：演化计算，清华大学出版社，1998。
[37] 侯格贤：遗传算法性能及其在聚类分析中应用的研究，西安电子科技大学博士学位论文，1999。
[38] 樊红，张组勋，杜道生：地图线状要素自动注记的算法设计与实现，测绘学报，1999(2)。
[39] 吉根林：遗传算法在数据挖掘中的应用，信息技术，2001(12)。
[40] 李世平等：图象分割中的遗传算法，系统仿真学报，2002(2)。
[41] 赵新煜，陈文伟等：遗传算法和遗传规划的对比研究，系统工程与电子技术。2000(12)。
[42] 陈真勇，何永勇等：基于遗传进化的最近邻聚类算法及其应用，控制与决策，2002(7)。
[43] 曹阳，方强等：基于遗传算法的多连接表达式并行查询优化，软件学报，2002(2)。
[44] 万幼川：基于数学形态学面状要素自动注记，计算机与数字工程，1998(2)。
[45] 李忠文：利用遗传算法解决分布式数据库系统中的数据分配问题，山西大学学报(自然科学版)，2001(2)。
[46] 许国艳，史宇清：遗传算法在关联规则挖掘中的应用，计算机工程，2002(7)。
[47] 钟波等：一种基于遗传算法的数据预处理组合方法，西南师范大学学报(自然科学版)，2002(8)。
[48] 王新生，姜友华等：遗传算法在城市道路控制点标高优化设计中的应用，武汉大学学报(信息科学版)，2001(2)。
[49] 郭革新：演化计算---探讨测绘最优化问题的新技术，测绘通报，1999(9)。
[50] 邓红艳，武芳：基于遗传算法的空间聚类分析，测绘通报，2003(1)。
[51] 邓红艳，武芳：遗传算法在点注记自动配置中的应用，解放军测绘学院学报，2003(2)。
[52] Oosterom, P. van:The Desingn and Implementation of A Multi-Scale GlC, Proceedings ECGIS, 1993.
[53] Yi Lu, Jinghai Du, Jingsheng Zhai: A Model of Point Cluster Generalization with Spatial Distribution Features Recognized and Measured, ICC2001.
[54] Holland, J. H:Outline for a logicaI theory of adaptive systems[J]. Journal of the Association for Computing Machinery, 1962.
[55] Whitley, L. D:Foundations of genetic algorithms, San Mateo, 1993.
[56] Srinivas Doddi,Madhav V.Marathe, Andi Mirzaian, Bernard M.E.Moret, Binhai Zhu:Map Labeling and Its Generalizations.
[57] Deng Hongyan, Wu Fang:The Spatial Analyse of Clustering Based on Genetic Algorithms, ISPRS2002.
[58] William B. Poland, Ross D. Shachter:Three Approaches to Probability Model Selection, In Uncertainty in Artificial Intelligence, Proceedings of the Tenth Conference, 1994.
[59] olli Jaakkola:Multi-scale Categorical Data Bases with Automatic Generalization Transformations Based on Map Algebra, Cartography and Geographic Information Systems, 1998(10).
[60] Dianne E. Richardson, William A. Mackaness:Introduction Computational Processes for Map Gneralization, 1999(1).
[61] Andriani Skopeliti, Lysandro Tsoulos:A Knowledge Based Approach for the Generalization of Linear Features.
[62] Joachim Bobrich:Cartographic Displacement by Minimization of Spatial and Geometric Conflicts.
[63] Tapani Sarjakoski:Holistic Cartographic Generalization by Least Squares Adjustment for Large Data Sets.