蟻群算法及其在聚類(lèi)中的應(yīng)用.pdf

1、蟻群算法是通過(guò)對(duì)自然界中真實(shí)螞蟻的集體行為的觀察、模擬而得到一種仿生優(yōu)化算法，它具有很好的并行性、分布性。根據(jù)螞蟻群體不同的集體行為特征，蟻群算法可分為受螞蟻覓食行為啟發(fā)的模型和受孵化分類(lèi)啟發(fā)的模型、受勞動(dòng)分工和協(xié)作運(yùn)輸啟發(fā)的模型。本文重點(diǎn)研究了前兩種蟻群算法模型。
　　 受螞蟻覓食行為啟發(fā)的模型又稱(chēng)為蟻群優(yōu)化算法（ACO），是繼模擬退火算法、遺傳算法、禁忌搜索等之后又一啟發(fā)式智能優(yōu)化算法。目前它已成功應(yīng)用于求解TSP問(wèn)題、地圖

2、著色、路徑車(chē)輛調(diào)度等優(yōu)化問(wèn)題。本文針對(duì)蟻群算法收斂時(shí)間長(zhǎng)、易陷入局部最優(yōu)的缺點(diǎn)，通過(guò)對(duì)路徑上信息素的更新方式作出動(dòng)態(tài)調(diào)整、建立信息素平滑機(jī)制，進(jìn)而使得不同路徑上的信息素的更新速度有所不同，從而使改進(jìn)后算法能夠有效地縮短搜索的時(shí)間，并能對(duì)最終解進(jìn)行優(yōu)化，避免過(guò)早的陷入局部最優(yōu)。
　　 聚類(lèi)是數(shù)據(jù)挖掘的重要技術(shù)之一，它可按照某種規(guī)則將數(shù)據(jù)對(duì)象劃分為多個(gè)類(lèi)或簇，使同一類(lèi)的數(shù)據(jù)對(duì)象有較高的相似度，而不同類(lèi)的數(shù)據(jù)對(duì)象差異較大。受螞蟻的覓食

3、過(guò)程啟發(fā)的聚類(lèi)算法又被稱(chēng)為基于螞蟻覓食原理的聚類(lèi)算法。把螞蟻覓食行為分為搜索食物和搬運(yùn)食物兩個(gè)環(huán)節(jié)，同時(shí)把數(shù)據(jù)對(duì)象視為螞蟻，把聚類(lèi)中心視為“食物源”，這樣數(shù)據(jù)對(duì)象的聚類(lèi)過(guò)程就可以轉(zhuǎn)化為螞蟻覓食的過(guò)程，在信息素的引導(dǎo)下螞蟻就可以完成數(shù)據(jù)對(duì)象的聚類(lèi)。但在該算法中沒(méi)有區(qū)分?jǐn)?shù)據(jù)對(duì)象不同屬性的重要性，本文通過(guò)采用離差最大化方法，對(duì)每個(gè)屬性根據(jù)它的重要性為它賦予一個(gè)權(quán)值，從而改進(jìn)了原算法中的距離計(jì)算，使得相似的數(shù)據(jù)對(duì)象能快速的聚集到一起，從而避免了

4、大量無(wú)效的相似度計(jì)算，提高了算法的效率。
　　 受孵化分類(lèi)啟發(fā)的模型又稱(chēng)為螞蟻堆形成原理聚類(lèi)算法。很多種類(lèi)的螞蟻都能夠?qū)⒙押托∮紫x(chóng)緊密地排列成束并放置在巢穴孵化區(qū)的中心，而最大的幼蟲(chóng)位于孵化束的外圍。Deneubourg等人根據(jù)這一現(xiàn)象最先提出了一個(gè)基本模型（BM）來(lái)模擬該現(xiàn)象，對(duì)基本模型比較成功的改進(jìn)有LF算法。模糊聚類(lèi)算法思想來(lái)源于Ruspini于1969年提出的模糊劃分思想，是指在涉及事物之間的模糊界限時(shí)按一定要求對(duì)事物進(jìn)