一种顾及道路影响的点要素注记配置遗传禁忌搜索算法
|
摘要
为使地图上点要素注记配置更美观易读,利用遗传算法的全局寻优能力和禁忌搜索算法的"爬山能力",在考虑传统点要素注记配置约束条件的同时,考虑点要素与道路间的关系,提出了一种顾及道路要素影响的遗传禁忌搜索算法,并从解算精度、运行效率及稳健性3个方面对该算法进行评价。本文以福建省泉州市惠安县1∶20万比例尺的乡村点状地形图数据进行试验,试验结果表明,与遗传算法、禁忌搜索算法和Arc GIS软件相比,该算法的算法精度和稳健性均有所提高,但是计算效率略低于禁忌算法,且点要素注记与点要素、道路要素的压盖量最少,与点要素、道路要素注记的交叉量最少。
This paper implements a genetic taboo search algorithm combined with global optimization capability of genetic algorithm and the memory and climbing ability of tabu search to solve the point-feature label placement problem.In addition to the constraints of the traditional point element annotation configuration,this method joins the constraints of the line feature to restrain the point-feature label placement.Moreover,the solution accuracy,efficiency and robustness of the algorithm is evaluated.The paper takes the rural topographic map data at 1 ∶ 200 000 in Huian county of Quanzhou city,Fujian province.The results show that the genetic taboo search algorithm has higher solution accuracy and robustness than the genetic algorithm and tabu search,lower efficiency than the tabu search,and all three indexs higher than the Arc GIS,as well as the less crossover and overlap than the other three methods.
This paper implements a genetic taboo search algorithm combined with global optimization capability of genetic algorithm and the memory and climbing ability of tabu search to solve the point-feature label placement problem.In addition to the constraints of the traditional point element annotation configuration,this method joins the constraints of the line feature to restrain the point-feature label placement.Moreover,the solution accuracy,efficiency and robustness of the algorithm is evaluated.The paper takes the rural topographic map data at 1 ∶ 200 000 in Huian county of Quanzhou city,Fujian province.The results show that the genetic taboo search algorithm has higher solution accuracy and robustness than the genetic algorithm and tabu search,lower efficiency than the tabu search,and all three indexs higher than the Arc GIS,as well as the less crossover and overlap than the other three methods.
引文
[1]李艳.面要素汉字注记自动配置的一种算法[J].解放军测绘学院学报,1998,15(1):54-57.
[2]邓红艳,武芳,李铭,等.遗传算法在点注记自动配置中的应用[J].测绘学院学报,2003,20(1):69-72.
[3]郑春燕,郭庆胜,刘小利.基于禁忌搜索算法的点要素注记的自动配置[J].武汉大学学报(信息科学版),2006,31(5):428-431.
[4]杨勇,邓淑丹,李霖,等.基于禁忌搜索的点状注记研究[J].测绘科学,2007,32(6):46-49.
[5]吴长斌,周鑫鑫,丁远.基于注记关联组的蚁群算法对点要素注记配置的实现方法:中国,201405123347[P].2015-01-07.
[6]杨新武,杨丽军.基于交叉模型的改进遗传算法[J].控制与决策.2016,31(10):1837-1844.
[7]王立,郑昊.粒子群遗传混合算法在点状注记配置中的应用[J].计算机与现代化,2012(10):30-33.
[8]GOMES S P,LORENA L A N.A constructive genetic algorithm for discrete dispersion on point feature cartographic label placement problems[J].Geographical Analysis,2016(48):43-48.
[9]HENRIK H J,ALEXANDER W.Beyond maximum independent set:an extended model for point-feature label placement[J].The International Archines of the Photogrammetry,Remote Sensing and Spatial Information Sciences,2016(XL1-B2):109-114.
[10]周鑫鑫,孙在宏,吴长斌,等.地图点要素注记自动配置中聚类分组的蚁群算法应用[J].地球信息科学,2015,17(8):902-907.
[11]杜欣,艾廷华,何亚坤.一种顾及道路影响的点要素注记自动配置模型[J].测绘科学,2016,41(4):148-153.
[12]赵剑,周泓,梁春华.求解JLSP问题的遗传禁忌混合优化算法[J].系统工程与电子科技,2012,34(4):833-838.
[13]余丽,陆锋,杨林.交通网络旅行商路径优化的遗传禁忌搜索算法[J].测绘学报.2014,43(11):1197-1203.
[14]孟波.基于改进遗传---禁忌搜索算法的无功优化分析[D].郑州:华北水利水电大学,2015.
[15]樊红,刘开军,张祖勋.基于遗传算法的点状要素注记的整体最优配置[J].武汉大学学报(信息科学版),2002,27(6):560-566.
[16]武芳,邓红艳.基于遗传算法的线要素自动化简模型[J].测绘学报,2003,32(4):349-356.
[17]FRED G,SAID H.Tabu search and finite convergence[J].Discrete Applied Mathematics,2002,119(1):3-36.
[18]周冬梅,孙俊.遗传规划中遗传算子对种群多样性的影响[J].计算机工程与应用,2016,52(20):39-45.
[19]SETON R S,ALIDAEE B,DORSEY R E,et al.Global optimization for artificial neural networks:a tabu search application[J].European Journal of Operational Research,1998,106(2-3):570-584.
[2]邓红艳,武芳,李铭,等.遗传算法在点注记自动配置中的应用[J].测绘学院学报,2003,20(1):69-72.
[3]郑春燕,郭庆胜,刘小利.基于禁忌搜索算法的点要素注记的自动配置[J].武汉大学学报(信息科学版),2006,31(5):428-431.
[4]杨勇,邓淑丹,李霖,等.基于禁忌搜索的点状注记研究[J].测绘科学,2007,32(6):46-49.
[5]吴长斌,周鑫鑫,丁远.基于注记关联组的蚁群算法对点要素注记配置的实现方法:中国,201405123347[P].2015-01-07.
[6]杨新武,杨丽军.基于交叉模型的改进遗传算法[J].控制与决策.2016,31(10):1837-1844.
[7]王立,郑昊.粒子群遗传混合算法在点状注记配置中的应用[J].计算机与现代化,2012(10):30-33.
[8]GOMES S P,LORENA L A N.A constructive genetic algorithm for discrete dispersion on point feature cartographic label placement problems[J].Geographical Analysis,2016(48):43-48.
[9]HENRIK H J,ALEXANDER W.Beyond maximum independent set:an extended model for point-feature label placement[J].The International Archines of the Photogrammetry,Remote Sensing and Spatial Information Sciences,2016(XL1-B2):109-114.
[10]周鑫鑫,孙在宏,吴长斌,等.地图点要素注记自动配置中聚类分组的蚁群算法应用[J].地球信息科学,2015,17(8):902-907.
[11]杜欣,艾廷华,何亚坤.一种顾及道路影响的点要素注记自动配置模型[J].测绘科学,2016,41(4):148-153.
[12]赵剑,周泓,梁春华.求解JLSP问题的遗传禁忌混合优化算法[J].系统工程与电子科技,2012,34(4):833-838.
[13]余丽,陆锋,杨林.交通网络旅行商路径优化的遗传禁忌搜索算法[J].测绘学报.2014,43(11):1197-1203.
[14]孟波.基于改进遗传---禁忌搜索算法的无功优化分析[D].郑州:华北水利水电大学,2015.
[15]樊红,刘开军,张祖勋.基于遗传算法的点状要素注记的整体最优配置[J].武汉大学学报(信息科学版),2002,27(6):560-566.
[16]武芳,邓红艳.基于遗传算法的线要素自动化简模型[J].测绘学报,2003,32(4):349-356.
[17]FRED G,SAID H.Tabu search and finite convergence[J].Discrete Applied Mathematics,2002,119(1):3-36.
[18]周冬梅,孙俊.遗传规划中遗传算子对种群多样性的影响[J].计算机工程与应用,2016,52(20):39-45.
[19]SETON R S,ALIDAEE B,DORSEY R E,et al.Global optimization for artificial neural networks:a tabu search application[J].European Journal of Operational Research,1998,106(2-3):570-584.