蚂蚁增强算法在空间栅格聚类中的应用

《蚂蚁增强算法在空间栅格聚类中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第15分会场地球空间信息资源利用与共享223一——=—=—————；——===———==—=—==———=————}=—=—；—=≮=；—#—一蚂蚁增强算法在空间栅格聚类中的应用钱海忠武芳葛磊王辉连解放军信息工程大学测绘学院，郑州，450052摘要本文提出了一种基于栅格技术和多种群蚂蚁算法的空间数据聚类的新方法，以满足空间信息系统中对聚类算法在速度、智能性和聚类独立性等方面的需求。首先介绍了聚类现状和基本概念。分析了已有聚类算法的不足及改进措施。其次，给出了矢量数据栅格化方法。并结合空间数据目标的属性，定义了栅格单元值的计算方式。第三，依据蚂蚁

2、的特点，把蚂蚁的多种群特性运用到算法中来，提出并定义了蚂蚁的三种类型及其相互转化机制，形成了完整的蚂蚁工作机理，以规范算法运行，提高了算法的智能性和灵活性。第四，把蚂蚁改进算法和栅格技术相结合，提出了本算法，详细阐述了其运行过程；并在此基础上提出了带有附加条件的局部约束聚类方法，进一步加强算法的实用性。最后，给出了算法的详细实例，并分析了算法的优缺点。关键词空间信息系统聚类分析蚂蚁算法智能性一、引言空间数据聚类分析是研究空间多要素事物分类问题的数量方法，是空间信息系统研究的重点之一。目前对空间数据聚类研究的方法很多。但在实际使用过程中，已有的聚

3、类算法需要大量的时间，同时需要一定的人工干预，严重影响了系统的性能。另外，有些聚类算法只顾及空间数据的空间位置特征而没有顾及空间数据的拓扑关系特征等因素的影响，对空间数据处理的效果不是很好。事实上，聚类的主要功能就是把相似目标聚为一类，类与类之间有明确跳跃性。空问信息系统中一个理想的聚类算法应该具备以下三个方面的特征：第一，为了对空间数据处理提供更大的方便，空间数据聚类分析首先要保证聚类结果在空间关系上的相对独立性，然后才是位置独立性；第二，加强算法的智能性是保证结果合理的重要方面，也是加强算法实用性和适应性的最好途径；第三，加快聚类算法的运算

4、速度是目前所有系统的基本要求，也是一直亟待解决的难题之一。为了解决这三个问题，本文采取了以下措施：首先，为了保证聚类结果在空间关系上的相对独立性，笔者在聚类过程中引入了线状要素约束条件的概念，以加强聚类之间的独立性。其次，为了提高算法的智能化程度，本文把群蚂蚁算法引入聚类中来。蚁群算法具有全局优化能力和本质上的并行性，同时比遗传算法、模拟退火算法等早期进化算法具备更强的鲁棒性、求解时间短、易于计算机实现等优点，已被用于高度复杂的组合优化问题。最后，为了加快聚类算法，引入了运算简单，速度很快的栅格技术，使得聚类算法的运算在时间上得到了保证。下文正

5、是在此思想指导下进行空间矢量数据的聚类研究。二、空间数据的栅格处理空间数据进行栅格处理的过程为：对空间数据进行一定密集度的格网划分，初始时每个格网的赋值均为0。即如果把空间数据分为m行竹列，则共有仇X行个格网，记每个格网初始值为G二=o(o

6、标的重要性有关。如果该目标非常重要，则其所覆盖的格网增加值(硼)就会接近于1或等于1，反之，W就会取接近于0，甚至等于0。而目标的重要性主要根据空间数据的属性来判断。空间数据的属性可以由其编码唯一标识。图1是两个目标栅格化后再叠加的过程，其中W取值为1。圈+田=田图1空间目标的栅格处理示意图三、多种群蚂蚁的定义与工作机理本文引入蚂蚁算法的出发点是为了进行空间数据的聚类。而空间数据具有位置特性和空间关系特性，因此蚂蚁也应该具有位置特征和空间探测能力；同时，空间数据区域具有复杂的空间特征，目标大小、形状等千差万别，因此相应地，蚂蚁之间也应该有所区别

7、。据此，把蚂蚁分为以下几种类型：工类蚂蚁：是最基本的蚂蚁，仅具有任意爬行和散发信息素的功能。Ⅱ类蚂蚁：除了具有I类蚂蚁的功能外，还具有触须，以便探测近距离范围内的目标物，并依据感觉进行有方向感的爬行。对格网而言，Ⅱ类蚂蚁能探测与其所在格网相邻的其他格网信息的能力。Ⅲ类蚂蚁：除了具有Ⅱ类蚂蚁的功能外，还具有发送和接收探测波的功能，能够发射较远距离的探测波，以探测较远地方的目标物。此外，考虑到蚂蚁的遗传特性和群体特性，还需以下约定：约定1：不同类别之间的蚂蚁在一定条件下可以进行转换。即I类蚂蚁在一定条件下可以转换为Ⅱ类蚂蚁，依此类推，反之亦然。具体

8、而言，蚂蚁之间的转换依据以下条件进行：(1)I类蚂蚁在本文中为所有蚂蚁的初始状态(算法初始时)。(2)I类蚂蚁在激发状态下(算法开始运行时)，变为Ⅱ类