螞蟻增強(qiáng)算法在空間柵格聚類中的應(yīng)用

《螞蟻增強(qiáng)算法在空間柵格聚類中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、第15分會(huì)場(chǎng)地球空間信息資源利用與共享223一——=—=—————；——===———==—=—==———=————}=—=—；—=≮=；—#—一螞蟻增強(qiáng)算法在空間柵格聚類中的應(yīng)用錢海忠武芳葛磊王輝連解放軍信息工程大學(xué)測(cè)繪學(xué)院，鄭州，450052摘要本文提出了一種基于柵格技術(shù)和多種群螞蟻算法的空間數(shù)據(jù)聚類的新方法，以滿足空間信息系統(tǒng)中對(duì)聚類算法在速度、智能性和聚類獨(dú)立性等方面的需求。首先介紹了聚類現(xiàn)狀和基本概念。分析了已有聚類算法的不足及改進(jìn)措施。其次，給出了矢量數(shù)據(jù)柵格化方法。并結(jié)合空間數(shù)據(jù)目標(biāo)的屬性，定義了柵格單元值的計(jì)算方式。第三，依據(jù)螞蟻

2、的特點(diǎn)，把螞蟻的多種群特性運(yùn)用到算法中來，提出并定義了螞蟻的三種類型及其相互轉(zhuǎn)化機(jī)制，形成了完整的螞蟻工作機(jī)理，以規(guī)范算法運(yùn)行，提高了算法的智能性和靈活性。第四，把螞蟻改進(jìn)算法和柵格技術(shù)相結(jié)合，提出了本算法，詳細(xì)闡述了其運(yùn)行過程；并在此基礎(chǔ)上提出了帶有附加條件的局部約束聚類方法，進(jìn)一步加強(qiáng)算法的實(shí)用性。最后，給出了算法的詳細(xì)實(shí)例，并分析了算法的優(yōu)缺點(diǎn)。關(guān)鍵詞空間信息系統(tǒng)聚類分析螞蟻算法智能性一、引言空間數(shù)據(jù)聚類分析是研究空間多要素事物分類問題的數(shù)量方法，是空間信息系統(tǒng)研究的重點(diǎn)之一。目前對(duì)空間數(shù)據(jù)聚類研究的方法很多。但在實(shí)際使用過程中，已有的聚

3、類算法需要大量的時(shí)間，同時(shí)需要一定的人工干預(yù)，嚴(yán)重影響了系統(tǒng)的性能。另外，有些聚類算法只顧及空間數(shù)據(jù)的空間位置特征而沒有顧及空間數(shù)據(jù)的拓?fù)潢P(guān)系特征等因素的影響，對(duì)空間數(shù)據(jù)處理的效果不是很好。事實(shí)上，聚類的主要功能就是把相似目標(biāo)聚為一類，類與類之間有明確跳躍性?？諉栃畔⑾到y(tǒng)中一個(gè)理想的聚類算法應(yīng)該具備以下三個(gè)方面的特征：第一，為了對(duì)空間數(shù)據(jù)處理提供更大的方便，空間數(shù)據(jù)聚類分析首先要保證聚類結(jié)果在空間關(guān)系上的相對(duì)獨(dú)立性，然后才是位置獨(dú)立性；第二，加強(qiáng)算法的智能性是保證結(jié)果合理的重要方面，也是加強(qiáng)算法實(shí)用性和適應(yīng)性的最好途徑；第三，加快聚類算法的運(yùn)算

4、速度是目前所有系統(tǒng)的基本要求，也是一直亟待解決的難題之一。為了解決這三個(gè)問題，本文采取了以下措施：首先，為了保證聚類結(jié)果在空間關(guān)系上的相對(duì)獨(dú)立性，筆者在聚類過程中引入了線狀要素約束條件的概念，以加強(qiáng)聚類之間的獨(dú)立性。其次，為了提高算法的智能化程度，本文把群螞蟻算法引入聚類中來。蟻群算法具有全局優(yōu)化能力和本質(zhì)上的并行性，同時(shí)比遺傳算法、模擬退火算法等早期進(jìn)化算法具備更強(qiáng)的魯棒性、求解時(shí)間短、易于計(jì)算機(jī)實(shí)現(xiàn)等優(yōu)點(diǎn)，已被用于高度復(fù)雜的組合優(yōu)化問題。最后，為了加快聚類算法，引入了運(yùn)算簡(jiǎn)單，速度很快的柵格技術(shù)，使得聚類算法的運(yùn)算在時(shí)間上得到了保證。下文正

5、是在此思想指導(dǎo)下進(jìn)行空間矢量數(shù)據(jù)的聚類研究。二、空間數(shù)據(jù)的柵格處理空間數(shù)據(jù)進(jìn)行柵格處理的過程為：對(duì)空間數(shù)據(jù)進(jìn)行一定密集度的格網(wǎng)劃分，初始時(shí)每個(gè)格網(wǎng)的賦值均為0。即如果把空間數(shù)據(jù)分為m行竹列，則共有仇X行個(gè)格網(wǎng)，記每個(gè)格網(wǎng)初始值為G二=o(o

6、標(biāo)的重要性有關(guān)。如果該目標(biāo)非常重要，則其所覆蓋的格網(wǎng)增加值(硼)就會(huì)接近于1或等于1，反之，W就會(huì)取接近于0，甚至等于0。而目標(biāo)的重要性主要根據(jù)空間數(shù)據(jù)的屬性來判斷?？臻g數(shù)據(jù)的屬性可以由其編碼唯一標(biāo)識(shí)。圖1是兩個(gè)目標(biāo)柵格化后再疊加的過程，其中W取值為1。圈+田=田圖1空間目標(biāo)的柵格處理示意圖三、多種群螞蟻的定義與工作機(jī)理本文引入螞蟻算法的出發(fā)點(diǎn)是為了進(jìn)行空間數(shù)據(jù)的聚類。而空間數(shù)據(jù)具有位置特性和空間關(guān)系特性，因此螞蟻也應(yīng)該具有位置特征和空間探測(cè)能力；同時(shí)，空間數(shù)據(jù)區(qū)域具有復(fù)雜的空間特征，目標(biāo)大小、形狀等千差萬(wàn)別，因此相應(yīng)地，螞蟻之間也應(yīng)該有所區(qū)別

7、。據(jù)此，把螞蟻分為以下幾種類型：工類螞蟻：是最基本的螞蟻，僅具有任意爬行和散發(fā)信息素的功能。Ⅱ類螞蟻：除了具有I類螞蟻的功能外，還具有觸須，以便探測(cè)近距離范圍內(nèi)的目標(biāo)物，并依據(jù)感覺進(jìn)行有方向感的爬行。對(duì)格網(wǎng)而言，Ⅱ類螞蟻能探測(cè)與其所在格網(wǎng)相鄰的其他格網(wǎng)信息的能力。Ⅲ類螞蟻：除了具有Ⅱ類螞蟻的功能外，還具有發(fā)送和接收探測(cè)波的功能，能夠發(fā)射較遠(yuǎn)距離的探測(cè)波，以探測(cè)較遠(yuǎn)地方的目標(biāo)物。此外，考慮到螞蟻的遺傳特性和群體特性，還需以下約定：約定1：不同類別之間的螞蟻在一定條件下可以進(jìn)行轉(zhuǎn)換。即I類螞蟻在一定條件下可以轉(zhuǎn)換為Ⅱ類螞蟻，依此類推，反之亦然。具體

8、而言，螞蟻之間的轉(zhuǎn)換依據(jù)以下條件進(jìn)行：(1)I類螞蟻在本文中為所有螞蟻的初始狀態(tài)(算法初始時(shí))。(2)I類螞蟻在激發(fā)狀態(tài)下(算法開始運(yùn)行時(shí))，變?yōu)棰蝾?/p>