基于遗传算法防重叠冲突的地图点标注方法研究
|
摘要
高质量地图点要素标注及自动配置问题是地图制图中的难点之一。为了解决地图点要素标注中的重叠问题,提出基于遗传算法的局部优化功能实现防重叠冲突的地图点要素标注。该文首先通过地图点要素标注的位置分配问题,建立基于点要素的八位置候选模型。其次,针对地图点的防重叠冲突问题,提出地图点标注的重叠数量评价函数和重叠面积评价函数,记录每一次迭代过程中点要素标注的重叠个数和重叠面积,得到标注重叠质量得分,进而得到适应度评分。最后基于3种评分结果建立新的终止条件,将数次迭代后满足该条件的标注设置为最终的配置方案。实验采用随机模拟数据和福州大学城实际数据进行验证,结果表明基于遗传算法和防重叠冲突的点标注配置与一般的标注配置相比,其重叠个数减少了89%。在迭代过程中最后一代相较于第一代的重叠面积减少了75%,标注的适应度提升54.5%。该算法能够有效地计算出群体点标注的近似最优解,显著提升地图标注的美观性和位置平衡性,适用于网络地图和专题地图点要素的自动化标注和配置。
The problem of high quality map point labeling and automatic configuration is one of the difficulties in the cartography.In order to avoid the problem of overlapping in map point labeling,a method of map point labeling for overlapping conflict prevention is proposed by using genetic algorithm(GA) with local optimization function in this paper.Firstly,eight candidate location models around point are proposed in view of the configuration of map points labeling in this method.Secondly,in combination with the problem of anti-overlapping conflicts in map points,the innovative method of GA is proposed by building overlapping quantity evaluation function and overlapping area evaluation function of map points labeling which includes recording the scale of the overlapping quantity and overlapping area of the element annotation at each iteration.It could get the score of overlapping mark and then get the fitness score.Finally,a new termination condition is established based on the three scores,the label which in accordance with the condition after several iterations is set as the final result of map point labeling.The method is verified by the experiments with the random simulation data and the actual data of Fuzhou University.The results showed that the overlapping mark quantity with configuration of point labeling based on GA was decreased by 89% compared with the general annotation configuration.During the iterative process,the overlapping area of the last generation was 75% less than the first generation,and the fitness of labeling was increased by 54.5%.This algorithm can effectively find out the approximate optimal solution of group point labeling,so that it can significantly improve the overall aesthetics and position balance of map point labeling,which is suitable for automatic labeling and configuration of map point labeling in network maps and thematic maps.
The problem of high quality map point labeling and automatic configuration is one of the difficulties in the cartography.In order to avoid the problem of overlapping in map point labeling,a method of map point labeling for overlapping conflict prevention is proposed by using genetic algorithm(GA) with local optimization function in this paper.Firstly,eight candidate location models around point are proposed in view of the configuration of map points labeling in this method.Secondly,in combination with the problem of anti-overlapping conflicts in map points,the innovative method of GA is proposed by building overlapping quantity evaluation function and overlapping area evaluation function of map points labeling which includes recording the scale of the overlapping quantity and overlapping area of the element annotation at each iteration.It could get the score of overlapping mark and then get the fitness score.Finally,a new termination condition is established based on the three scores,the label which in accordance with the condition after several iterations is set as the final result of map point labeling.The method is verified by the experiments with the random simulation data and the actual data of Fuzhou University.The results showed that the overlapping mark quantity with configuration of point labeling based on GA was decreased by 89% compared with the general annotation configuration.During the iterative process,the overlapping area of the last generation was 75% less than the first generation,and the fitness of labeling was increased by 54.5%.This algorithm can effectively find out the approximate optimal solution of group point labeling,so that it can significantly improve the overall aesthetics and position balance of map point labeling,which is suitable for automatic labeling and configuration of map point labeling in network maps and thematic maps.
引文
[1] 乔占明,闫浩文.地图标注和地图注记的探讨[J].测绘与空间地理信息,2011,34(1):205-207.
[2] 樊红,张祖勋,杜道生.地图注记质量评价模型的研究[J].测绘学报,2004,33(4):362-366.
[3] 陈飞翔,杨崇俊,周治武,等.基于自然分界法的点状注记自动标注算法[J].计算机工程与应用,2005,41(3):49-51.
[4] MARKS J,SHIEBER S.The Computational Complexity of Cartographic Label Placement[M].Aiken Computation Laboratory,1991.
[5] 杜立智,符海东,张鸿,等.P与NP问题研究[J].计算机技术与发展,2013,23(1):37-42.
[6] 于秀兰,陈滢,饶芳艳,等.WebGIS中地图点状要素标注算法设计[J].遥感信息,2002(3):32-37.
[7] DIJK S V,THIERENS D,BERG M D.Using genetic algorithms for solving hard problems in GIS[J].Geoinformatica,2002,6(4):381-413.
[8] CHRISTENSEN J,MARKS J,SHIEBER S.An empirical study of algorithms for point-feature label placement[J].ACM Transactions on Graphics,1995,14(3):203-232.
[9] 吕德奎,崔艳军.基于网格的地图标注避让算法[J].电子技术与软件工程,2016(22):13.
[10] 樊红,刘开军,张祖勋.基于遗传算法的点状要素注记的整体最优配置[J].武汉大学学报(信息科学版),2002,27(6):560-565.
[11] FAN H,ZHANG Z,DU D.Quality evaluation model for map labeling[J].Geo-spatial Information Science,2005,8(1):72-78.
[12] 玄登影,王福林,高敏慧,等.一种改进适应度函数的遗传算法[J].数学的实践与认识,2015,45(16):232-238.
[13] 雷明军.地图线状要素注记自动配置的研究[D].武汉:武汉大学,2005.
[14] HOLLAND J H.Adaptation in Nature and Artificial System[M].MIT Press,1998.
[15] 杨国军,崔平远,李琳琳.遗传算法在神经网络控制中的应用与实现[J].系统仿真学报,2001,13(5):567-570.
[16] 谢开贵,肖畅.计及负荷不确定性的无功优化模型与算法[J].电力系统保护与控制,2011,39(4):18-22.
[17] 李振星,邵峰晶,孙仁诚,等.基于分类的GIS地图符号快速标注算法[J].软件,2012,33(2):108-110.
[18] EDUARDIMHOF.Positioning names on maps[J].American Cartographer,1975,2(2):128-144.
[19] 杜世宏,王桥,杜道生,等.地名注记自动配置的关键技术研究[J].地理与地理信息科学,2003,19(1):20-24.
[20] 冯心玲,龚月姣,林映霞,等.用遗传算法优化航班规划问题[J].计算机工程与设计,2009,30(19):4468-4471.
[21] 刘杰.全局优化问题的几类新算法[D].西安:西安电子科技大学,2015.
[22] 王志杰.基于遗传算法的点状要素注记配置设计与实现[D].成都:电子科技大学,2012.
[23] ZHANG H,FENG H,LIU C.An adaptive genetic algorithm for automated annotation of point elements in numerical map[A].International Conference on Intelligence Science and Information Engineering[C].2011.499-502.
[24] GOLDBERG D E.Genetic algorithm in search optimization and machine learning[J].Addison Wesley,1989,xiii(7):2104-2116.
[25] 杨平,郑金华.遗传选择算子的比较与研究[J].计算机工程与应用,2007,43(15):59-62.
[26] 邓春燕.遗传算法的交叉算子分析[J].农业网络信息,2009(5):124-126..
[27] 董品杰,赖红松.基于多目标遗传算法的土地利用空间结构优化配置[J].地理与地理信息科学,2003,19(6):52-55.
[28] 沈畅,乐天.遗传算法中的变异算子的述评[J].科技视界,2012(23):107-108.
[29] 覃俊华,张洪伟,赵世政.基于遗传算法的模糊聚类研究及其应用[J].计算机应用,2007,27(1):52-55.
[30] GREFENSTETTE J J.Optimization of control parameters for genetic algorithms[J].Systems Man & Cybernetics IEEE Transactions on,1986,16(1):122-128.
[2] 樊红,张祖勋,杜道生.地图注记质量评价模型的研究[J].测绘学报,2004,33(4):362-366.
[3] 陈飞翔,杨崇俊,周治武,等.基于自然分界法的点状注记自动标注算法[J].计算机工程与应用,2005,41(3):49-51.
[4] MARKS J,SHIEBER S.The Computational Complexity of Cartographic Label Placement[M].Aiken Computation Laboratory,1991.
[5] 杜立智,符海东,张鸿,等.P与NP问题研究[J].计算机技术与发展,2013,23(1):37-42.
[6] 于秀兰,陈滢,饶芳艳,等.WebGIS中地图点状要素标注算法设计[J].遥感信息,2002(3):32-37.
[7] DIJK S V,THIERENS D,BERG M D.Using genetic algorithms for solving hard problems in GIS[J].Geoinformatica,2002,6(4):381-413.
[8] CHRISTENSEN J,MARKS J,SHIEBER S.An empirical study of algorithms for point-feature label placement[J].ACM Transactions on Graphics,1995,14(3):203-232.
[9] 吕德奎,崔艳军.基于网格的地图标注避让算法[J].电子技术与软件工程,2016(22):13.
[10] 樊红,刘开军,张祖勋.基于遗传算法的点状要素注记的整体最优配置[J].武汉大学学报(信息科学版),2002,27(6):560-565.
[11] FAN H,ZHANG Z,DU D.Quality evaluation model for map labeling[J].Geo-spatial Information Science,2005,8(1):72-78.
[12] 玄登影,王福林,高敏慧,等.一种改进适应度函数的遗传算法[J].数学的实践与认识,2015,45(16):232-238.
[13] 雷明军.地图线状要素注记自动配置的研究[D].武汉:武汉大学,2005.
[14] HOLLAND J H.Adaptation in Nature and Artificial System[M].MIT Press,1998.
[15] 杨国军,崔平远,李琳琳.遗传算法在神经网络控制中的应用与实现[J].系统仿真学报,2001,13(5):567-570.
[16] 谢开贵,肖畅.计及负荷不确定性的无功优化模型与算法[J].电力系统保护与控制,2011,39(4):18-22.
[17] 李振星,邵峰晶,孙仁诚,等.基于分类的GIS地图符号快速标注算法[J].软件,2012,33(2):108-110.
[18] EDUARDIMHOF.Positioning names on maps[J].American Cartographer,1975,2(2):128-144.
[19] 杜世宏,王桥,杜道生,等.地名注记自动配置的关键技术研究[J].地理与地理信息科学,2003,19(1):20-24.
[20] 冯心玲,龚月姣,林映霞,等.用遗传算法优化航班规划问题[J].计算机工程与设计,2009,30(19):4468-4471.
[21] 刘杰.全局优化问题的几类新算法[D].西安:西安电子科技大学,2015.
[22] 王志杰.基于遗传算法的点状要素注记配置设计与实现[D].成都:电子科技大学,2012.
[23] ZHANG H,FENG H,LIU C.An adaptive genetic algorithm for automated annotation of point elements in numerical map[A].International Conference on Intelligence Science and Information Engineering[C].2011.499-502.
[24] GOLDBERG D E.Genetic algorithm in search optimization and machine learning[J].Addison Wesley,1989,xiii(7):2104-2116.
[25] 杨平,郑金华.遗传选择算子的比较与研究[J].计算机工程与应用,2007,43(15):59-62.
[26] 邓春燕.遗传算法的交叉算子分析[J].农业网络信息,2009(5):124-126..
[27] 董品杰,赖红松.基于多目标遗传算法的土地利用空间结构优化配置[J].地理与地理信息科学,2003,19(6):52-55.
[28] 沈畅,乐天.遗传算法中的变异算子的述评[J].科技视界,2012(23):107-108.
[29] 覃俊华,张洪伟,赵世政.基于遗传算法的模糊聚类研究及其应用[J].计算机应用,2007,27(1):52-55.
[30] GREFENSTETTE J J.Optimization of control parameters for genetic algorithms[J].Systems Man & Cybernetics IEEE Transactions on,1986,16(1):122-128.