A Simplification Model of Linear Features Based on the Clonal Selection Algorithm

  • 1. School of Resource and Environmental Science, Wuhan University, Wuhan 430079, China;
    2. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China;
    3. Key Laboratory of Geographic Information System, Ministry of Education, Wuhan University, Wuhan 430079, China

Received date: 2012-11-01

  Revised date: 2012-12-02

  Online published: 2012-12-25


The automatic generalization of linear features is an important aspect of map generalization, for linear features occupy more than 80 percent of the map objects. As a major means of linear features generalization, graphic simplification has been the concern of many scholars at home and abroad, they make many researches to implement a large number of automated algorithms. With the intelligent optimization algorithm widely used in various fields, many scholars have tried to introduce the intelligent optimization algorithm into the field of map generalization. And then several scholars have applied the genetic algorithm and ant colony algorithm to the linear feature graphic simplification. They achieved good results, but some defects, too. The artificial immune system development started relatively late, but it has been widely used in various fields, and has got amazing achievements. In this paper we presented a new linear feature graphics automatically simplified model based on the basic principles of clonal selection algorithm, which is kind of AIS, and analyzed the graphics simplification constraints of linear features data compression, taking into account the geometric precision and the shape keeping function. Then we designed the appropriate coding mechanism, mutation mechanism and affinity function, meanwhile combining with infeasible solutions repair mechanisms to improve the precision of graphic simplification. At the end, we compared the simplification results with the clonal selection algorithm, Douglas algorithm and genetic algorithm. Experiments show that, in the same geometric accuracy, the linear feature graphics simplification model this study proposed gave better performance in keeping the shape of linear features graphics. Experiments also verify the feasibility of the artificial immune system in solving the problem of linear feature graphic simplification.

Cite this article

MA Xiao-Ya, GUO Qiang-Qing . A Simplification Model of Linear Features Based on the Clonal Selection Algorithm[J]. Journal of Geo-information Science, 2012 , 14(6) : 698 -703 . DOI: 10.3724/SP.J.1047.2012.00698


[1] Douglas D, Peucker T. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. The Canadian Cartographer, 1973, 10(2):112-122.

[2] Li Z L, Openshaw S. Algorithms for antomated line generalization based on a natural principle of objective generation[J]. International Journal of Geographical Information Systems, 1992, 6(5):373-389.

[3] 郭庆胜.线状要素图形综合的渐进方法研究[J].武汉大学学报(信息科学版),1998,23(1):54-58.

[4] Cromley R G, Gampbell G M. Integrating quantitative and qualitative aspects of digital line simplification[J]. The Cartographic Journal, 1992, 29(1):25-30.

[5] Van Dijk S, Thierens D, De Berg M. Using genetic algorithms for solving hard problems in GIS[J]. Geoinformatica, 2002, 6(4):381-413.

[6] 武芳,邓红艳.基于遗传算法的线要素自动化简模型[J].测绘学报,2003,32(4):349-355.

[7] 郑春燕,郭庆胜,胡华科.基于蚁群优化算法的线状目标简化模型[J].测绘学报,2011,40(5):635-638.

[8] De Castro L N, Vonzuben F J. Artificial immune system: Part I-Basic theory and applications (Tech. Rep.-RT DCA 01/99)[M]. Campinas,SP: State University of Campinas, Brasil, 1999:10-25.

[9] De Castro L N, Vonzuben F J. Immune and neural network models: Theoretial and empirical comparisons[J]. International Journal of Computational Intelligence and Applications(IJCIA), 2001,1(3):239-257.

[10] 钟燕飞,张良培,李平湘.基于非一致性自适应变异的克隆选择算法[J].武汉大学学报(信息科学版),2009,34(3):308-312.

[11] Zhong Y, L Zhang. A fast clonal selection algorithm for feature selection in hyperspectral imagery[J]. Geo-spatial Information Science, 2009, 12(3):172-181.

[12] Shang R H, Jiao L C, Liu F, et al. A novel immune clonal algorithm for MO problems[J]. Ieee Transactions on Evolutionary Computation, 2012, 16(1):35-50.

[13] 郭庆胜,黄远林,郑春燕,等.空间推理与渐进式地图综合[M].武汉:武汉大学出版社,2007,134-143.

[14] Barkowsky T, Latecki L, Richter K-F. Schematizing maps: Simplification of geographic shape by discrete curve evolution [C].//Freksa C, et al.(eds.). Spatial Cognition II, Springer Berlin Heidelberg, 2000,41-53.

[15] 梁勤欧.人工免疫系统与GIS空间分析应用[M].武汉:武汉大学出版社,2011,78-82.

[16] 潘晓英,刘芳,焦李成.多执行模式项目调度问题的克隆选择优化[J].模式识别与人工智能,2008,21(3):303-309.