克隆选择算法的线状要素图形简化模型

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

线状要素作为占据地图图形80%以上的地图目标,其自动概括是制图综合的一个重要内容。线状要素图形简化是其制图综合的一个主要手段。本研究以克隆选择算法的基本原理,分析对线状要素数据进行压缩时图形简化的约束条件,顾及线状要素的几何精度和形状特征,设计相应的编码机制、变异机制和亲和度函数,提出一种新的线状要素图形自动简化模型。同时,结合不可行解修复机制,提高图形简化的精度。最后,将该模型与道格拉斯算法、遗传算法的简化结果作对比,实验表明,在相同的几何精度内,文中提出的线状要素图形简化模型,在保持线状要素图形形状方面表现更佳。

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 gener-alization, 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 algo-rithm 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 compres-sion, 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 in- feasible 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 al-gorithm. Experiments show that, in the same geometric accuracy, the linear feature graphics simplifica-tion 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 fea-ture graphic simplification.