一種基于遺傳和蟻群算法融合的聚類新方法

1、一種基于遺傳和蟻群算法融合的聚類新方法摘要：遺傳算法具有快速良好的全局搜索能力，而蟻群聚類算法具有良好的分布式并行性和正反饋能力。將兩種算法進(jìn)行融合，充分利用算法各自的優(yōu)勢和特點(diǎn)，能更有效地進(jìn)行聚類分析。實(shí)驗(yàn)證明這種新組合算法在優(yōu)化能力和時(shí)間性能上比常用的聚類算法有比較明顯的優(yōu)勢。關(guān)鍵詞：遺傳算法; 蟻群算法; 聚類中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：AA New Clustering Algorithm Based on the Combination of Genetic Algorithm and Ant Colony AlgorithmAbstract: Genetic algorit

2、hm has the ability of doing a global quickly and stochastically. Ant colony clustering algorithm has the ability of distributed parallel processing, and has good feedback capacity. The combination of both the algorithms can make full use of each advantages and character, and make clustering analysis

3、 better. Some experiments proved that the new combination algorithm has obvious advantage in optimization capacity and performance time than some common clustering algorithms.Key words: genetic algorithm; ant colony clustering algorithm; clustering;1 引言聚類就是將整個(gè)數(shù)據(jù)分成不同的組，并使組與組之間的差距盡可能大，組內(nèi)數(shù)據(jù)的差異盡可能小。幾種典型

4、的聚類方法包括：劃分方法k-平均(k-means)和PAM，層次聚類方法AGNES和DIANA，密度聚類方法DBSCAN等等。遺傳算法(GA)是由美國密執(zhí)安大學(xué)的JohnHoUmd教授于1975年首先提出的一類仿生型優(yōu)化算法它是以達(dá)爾文的生物進(jìn)化論“適者生存、優(yōu)勝劣汰”和孟德爾的遺傳變異理論“生物遺傳進(jìn)化主要在染色體上，子代是父代遺傳基因在染色體上的有序排列”為基礎(chǔ)，模擬生物界進(jìn)化過程。蟻群算法(ant colony algorithm）是最新發(fā)展的一種模擬螞蟻群體智能行為的仿生優(yōu)化算法1，由意大利學(xué)者Dorigo M于1991年提出。它具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其他方法相

5、結(jié)合等優(yōu)點(diǎn)2,3?；谙伻核惴ǖ木垲惙椒◤脑砩峡梢苑譃閮煞N：一種是基于蟻堆形成原理來實(shí)現(xiàn)數(shù)據(jù)聚類，另一種是運(yùn)用蟻群覓食的原理，利用信息素(pheromone)來實(shí)現(xiàn)聚類分析15。該文采用第一種方法進(jìn)行聚類分析。最早在這一領(lǐng)域開展工作的是Deneubourg等6，他們建立了一種基本模型，根據(jù)數(shù)據(jù)對象與其周圍對象的相似性，讓蟻群隨機(jī)地移動、拾起或放下數(shù)據(jù)對象，以達(dá)到聚類數(shù)據(jù)的目的。Lumer E 和Faieta B將該模型推廣到數(shù)據(jù)分析范疇，提出了LF算法7。吳斌等8，Ramos等9,楊燕等10從不同角度對LF算法進(jìn)行了改進(jìn)，并取得了一定的成效。Abbattista F等4最早提出了將遺傳算法(

6、GA)和蟻群算法相融合的改進(jìn)策略，并在Oliver30TSP和Eilon50TSP的仿真實(shí)驗(yàn)中得到了較好的結(jié)果；隨后，人們將蟻群算法與GA相融合來解決離散域和連續(xù)域中的多種優(yōu)化問題，并取得了較好的應(yīng)用效果。丁建立等11將遺傳算法和螞蟻算法的融合應(yīng)用于解決組合爆炸及NP類問題，無論在優(yōu)化性能還是時(shí)間性能都取得了非常好的效果。本文算法旨在聚類分析，是將遺傳算法和蟻群聚類算法融合，利用遺傳算法快速隨機(jī)的群體性全局搜索能力生成數(shù)據(jù)對象的初始聚類中心，再通過蟻群算法的并行性、正反饋、求精解效率高的特點(diǎn)完善聚類結(jié)構(gòu)。本文組織如下：第2節(jié)著重說明遺傳算法與蟻群聚類算法的融合，包括基本原理，遺傳算法和蟻群聚類

7、算法分析，整體算法描述；第3節(jié)是實(shí)驗(yàn)結(jié)果的對比分析，將本算法的實(shí)驗(yàn)結(jié)果與標(biāo)準(zhǔn)蟻群聚類算法和模糊蟻群聚類算法14進(jìn)行比較分析；最后是結(jié)論。2 遺傳算法與蟻群聚類算法的融合(GA2C2A)21 GA2C2A算法的基本原理和設(shè)計(jì)思想遺傳算法具有大范圍的快速全局搜索能力，但當(dāng)求解到一定程度時(shí)，往往作大量的冗余迭代，對于系統(tǒng)中的反饋信息利用不夠，求解效率降低；而蟻群聚類算法由于初期數(shù)據(jù)對象隨機(jī)散布，螞蟻“拾起”、“放下” 對象隨機(jī)運(yùn)動，形成有效聚類的時(shí)間很長，如圖1遺傳算法與蟻群算法的速度-時(shí)間曲線5所示。遺傳算法在搜索的初期(t0ta時(shí)間段)具有較高收斂速度，但達(dá)到ta之后效率明顯降低。而蟻群算法在搜

8、索的初期(t0ta時(shí)間段)由于數(shù)據(jù)及自身運(yùn)動的隨機(jī)性，使得搜索速度緩慢，但當(dāng)運(yùn)動到一定時(shí)間后，效果顯著提升。遺傳算法與蟻群聚類算法融合(genetic algorithm-ant colony clustering algorithm, GA2C2A)的基本思想是：基于遺傳算法的快速全局搜索能力和蟻群算法的正反饋收斂機(jī)制，初期采用遺傳算法過程生成數(shù)據(jù)對象的初始聚類中心，后期利用蟻群算法正反饋完善聚類結(jié)構(gòu)，優(yōu)勢互補(bǔ)。圖1遺傳算法與蟻群算法的速度-時(shí)間曲線22 GA2C2A中遺傳算法的定義與設(shè)置221 問題描述設(shè)目標(biāo)函數(shù): (1)其中，聚類中心 (2) (3)為屬于r類的樣本個(gè)數(shù)；表示樣本屬于第r

9、類；N為樣本數(shù)；P為聚類中心數(shù)(2PN-1)222 染色體構(gòu)造設(shè)表示染色體結(jié)構(gòu)，為維行向量，為第位置基因；設(shè)N為樣本數(shù)，則染色體要求如下：1) (4)2) (5)3) 其中 (6)223 適應(yīng)度函數(shù)及遺傳算子操作適應(yīng)度函數(shù)F定義為，其中M為一常數(shù)，為公式(1)所定義。這樣值小的個(gè)體，相應(yīng)的適應(yīng)度值就高。遺傳算子操作包括選擇、交叉和變異等過程。1) 選擇規(guī)則，按照以上選定的適應(yīng)度函數(shù)，使用輪盤策略進(jìn)行選擇，每一代中最好的染色體在下一代中優(yōu)先選擇，每一代同一染色體在下一代被選擇的數(shù)量不超過2個(gè)。2) 交叉規(guī)則，交叉規(guī)則采用位交叉法控制。采用此方法，有可能出現(xiàn)交叉后染色體不滿足條件公式(6)的異常情

10、況。為此，定義允許最大嘗試次數(shù)W，若超出W則放棄該配對的染色體，重新配對交叉。3) 變異規(guī)則，采用逆轉(zhuǎn)變異方法16，例如：，假設(shè)區(qū)間和區(qū)間處發(fā)生斷裂，斷裂片段又以方向順序插入，于是逆轉(zhuǎn)后的染色體變?yōu)椋?24 GA2C2A中遺傳算法整體描述遺傳算法整體流程如下：1種群初始化，設(shè)置進(jìn)化代數(shù)、交叉率、變異率等初始值；2選擇運(yùn)算，根據(jù)以上公式進(jìn)行計(jì)算，按染色體適應(yīng)度大小按比例進(jìn)行選擇；3交叉運(yùn)算，任選兩個(gè)個(gè)體進(jìn)行交叉操作；4變異運(yùn)算，變異位置隨機(jī)產(chǎn)生；5得到優(yōu)化染色體，在每一迭代過程中，計(jì)算除每一染色體的適應(yīng)度函數(shù)值，并由此產(chǎn)生新的后代染色體。若達(dá)到停止條件，就結(jié)束，得到聚類結(jié)果；否則，轉(zhuǎn)向2，重復(fù)執(zhí)

11、行迭代過程。23 GA2C2A中蟻群聚類算法的改進(jìn)與銜接231 標(biāo)準(zhǔn)蟻群聚類算法(SACA)標(biāo)準(zhǔn)蟻群聚類算法(standard ant clustering algorithm, SACA)是由Lumer E 和Faieta B提出的。其基本思想是：假設(shè)螞蟻在一個(gè)隨機(jī)散布了數(shù)據(jù)對象的二維平面內(nèi)隨機(jī)地移動。初始螞蟻隨機(jī)選擇一個(gè)數(shù)據(jù)對象，根據(jù)該對象在局部區(qū)域的相似性而得到的概率，決定螞蟻是否“拾起”或“放下”該對象。經(jīng)過有限次迭代，平面上的數(shù)據(jù)對象按其相似性而聚集，最后得到聚類結(jié)構(gòu)和聚類數(shù)目。螞蟻“拾起”對象的概率是由與當(dāng)前鄰域?qū)ο蟮南嗨贫葲Q定的，相似度低，“拾起”概率高，相似度高，“拾起”概率低

12、；螞蟻“放下”對象的概率則與此相反。1）相似度函數(shù) (7)為對象周圍正方形局部區(qū)域面積；為相似性參數(shù)，常量；2）拾起”、“放下”概率函數(shù) (8) (9) 其中 是閾值常量等于0.1和0.15。，對于，假如，那么；假如，那么。對于，假如，那么；假如，那么螞蟻放下對象。232改進(jìn)的SACA文獻(xiàn)101213對SACA進(jìn)行了一些改進(jìn)，主要表現(xiàn)在采用余弦距離與歐氏距離的線性組合，更好地區(qū)分對象；采用對稱式Sigmoid函數(shù)作為概率轉(zhuǎn)換函數(shù)，比SACA的二次函數(shù)具有更快的收斂性；通過信息熵增強(qiáng)螞蟻短期記憶，使螞蟻充分利用已有信息，提高算法效率；定義螞蟻放下對象失敗次數(shù)，當(dāng)達(dá)到閾值時(shí)，強(qiáng)行放下數(shù)據(jù)，以便加快

13、聚類的進(jìn)程。本文是與遺傳算法的融合，通過遺傳算法，產(chǎn)生初始聚類中心，將數(shù)據(jù)對象按照已有規(guī)律散布在二維平面，因此，每個(gè)單元格可以存放一個(gè)，兩個(gè)或更多的數(shù)據(jù)對象，同時(shí)把兩個(gè)或兩個(gè)數(shù)據(jù)對象的集合稱為堆。在文獻(xiàn)14研究基礎(chǔ)上，定義：堆擁有個(gè)對象；堆中兩個(gè)對象的最大距離：，D為歐氏距離；堆中對象聚類中心：，堆中最具差異對象；堆中對象距離聚類中心距離：；運(yùn)行方向選擇參數(shù)，初始化時(shí)螞蟻隨機(jī)選取方向，隨后按照概率判斷是繼續(xù)保持還是隨機(jī)選擇方向。拾起概率，當(dāng)螞蟻沒有攜帶任何對象時(shí)，按運(yùn)行方向在周圍8個(gè)鄰居中，尋找可能拾起的對象。螞蟻可能發(fā)現(xiàn)的對象存在三種情況：單一的對象，擁有兩個(gè)對象的堆或擁有兩個(gè)以上對象的堆。

14、對應(yīng)存在三種拾起概率：裝載概率，堆破壞概率及對象移除概率。處理流程如下：1. 標(biāo)識8鄰居為”unexplored”；2. 當(dāng)沒有找到時(shí)就重復(fù)以下操作2.1 搜索下一個(gè)標(biāo)識為”unexplored”的區(qū)域，2.2 if 區(qū)域不為空 then2.2.1 if 單元格只有一個(gè)對象，then按拾起該對象，按公式(8)計(jì)算， else2.2.2 if 堆中有兩個(gè)對象，then按拾起該對象，else2.2.3 if 堆中有多個(gè)對象，then 找到最不相似的對象，當(dāng)時(shí)（其中為閾值常數(shù)）2.3 標(biāo)識單元格為”explored”放下概率，當(dāng)螞蟻攜帶有對象時(shí)，按運(yùn)行方向在周圍8個(gè)鄰居中，尋找可能放下的單元格。當(dāng)單

15、元格為空時(shí)，螞蟻按概率放下所攜帶對象；當(dāng)單元格不為空，且有且僅有一個(gè)對象時(shí)，計(jì)算兩對象距離與所有對象最大距離的商，若小于概率，則放下對象，創(chuàng)建一個(gè)堆；當(dāng)單元格不止一個(gè)對象時(shí)，計(jì)算所攜帶對象較堆最不相似對象距堆聚類中心的距離，若小于則放下對象。若螞蟻所攜帶對象經(jīng)W次計(jì)算，仍未放下，則可以強(qiáng)行放下該對象，以增強(qiáng)聚類進(jìn)程。處理流程如下：1. 標(biāo)識8鄰居為”unexplored”；2.若沒有找到標(biāo)識且運(yùn)算次數(shù)<W就重復(fù)以下操作2.1搜索下一個(gè)標(biāo)識為”unexplored”的區(qū)域，2.1.1 if單元格為空then螞蟻所攜帶對象按概率放下，按公式(9)計(jì)算else2.1.2 if單元格有一個(gè)對象，

16、且，為閾值常數(shù)，then放下對象，else2.1.3 if單元格含有一個(gè)堆，且，then放下對象2.1.4 計(jì)數(shù)器累加2.2 標(biāo)識單元格為”explored”3. if計(jì)數(shù)器>W then 強(qiáng)行放下233 GA2C2A中蟻群聚類算法整體描述改進(jìn)后的蟻群聚類算法流程如下：1. 隨機(jī)將螞蟻散布在二維平面，將遺傳算法產(chǎn)生的初始聚類，按簇散布在平面內(nèi)，每個(gè)單元格一個(gè)或多個(gè)對象，初始化最大循環(huán)次數(shù)n，螞蟻總數(shù)ant_number等參數(shù)；2. for i=1,2,.,n;3. for j=1,2,ant_number;3.1 移動螞蟻3.2 if 螞蟻沒有攜帶對象then if 在螞蟻周圍的8個(gè)鄰居

17、中存在對象，那么螞蟻按概率拾起對象3.3 else 通過計(jì)算與周圍8個(gè)鄰居的相似度，按概率放下對象4標(biāo)記聚類模式234遺傳算法和蟻群聚類算法的銜接文獻(xiàn)11提出了遺傳算法與蟻群算法融合的一般性優(yōu)化問題求解策略，該策略在遺傳算法中設(shè)置了固定的迭代次數(shù)，這樣會造成過早或過晚結(jié)束遺傳算法過程，不能有效保證兩者在最佳時(shí)機(jī)進(jìn)行融合。在文獻(xiàn)16研究的基礎(chǔ)上，這里提出的融合策略可以保證最佳融合時(shí)機(jī)。主要方法如下：1） 根據(jù)實(shí)際情況設(shè)置初始聚類中心數(shù)P，該參數(shù)決定了遺傳聚類在從解的染色體往解的物理值映射過程的復(fù)雜度；2） 設(shè)置最小和最大遺傳迭代次數(shù)(Genemin、Genemax)；3） 遺傳算法迭代過程中統(tǒng)計(jì)

18、子代群體的進(jìn)化率，并以此設(shè)置子代群體的最小進(jìn)化率Genemin_ratio；4） 在設(shè)定的迭代次數(shù)范圍內(nèi)，如果子代群體的進(jìn)化率都小于Genemin_ratio，說明此時(shí)遺傳算法優(yōu)化速度較低，因此可以終止，進(jìn)入蟻群算法。 24 GA2C2A整體框架圖 2 GA2C2A整體框架3 仿真實(shí)驗(yàn)結(jié)果采用了表1中的3個(gè)數(shù)據(jù)集對SACA，模糊蟻群聚類算法14 ，GA2C2A進(jìn)行了測試。這些數(shù)據(jù)庫自身具備分類表，可以用于最終評價(jià)性能。表 1 測試數(shù)據(jù)集描述數(shù)據(jù)集實(shí)例數(shù)量屬性個(gè)數(shù)分類個(gè)數(shù)Iris15043Wine178133Glass21496本文采用一種常用的外部評價(jià)方法：F-measure17。F-meas

19、ure組合了信息檢索中查準(zhǔn)率與查全率思想。一個(gè)聚類j及與此相關(guān)的分類i的查準(zhǔn)率與查全率定義為： 其中是聚類j中分類i的數(shù)目，是聚類j中所有對象的數(shù)目，是分類i中所有對象的數(shù)目。則分類i的F-measure定義為： (10)對聚類結(jié)果p，其總F-measure可由每個(gè)分類i的F-measure加權(quán)平均得到： (11) 對表1中3個(gè)數(shù)據(jù)集進(jìn)行了50次測試后的平均總F-measure結(jié)果如表2所示。實(shí)驗(yàn)結(jié)果表明，GA2C2A性能優(yōu)于SACA，模糊蟻群聚類算法。表2 聚類的平均總F-measur算法IrisWineGlassSACA0.9050.8910.903模糊蟻群聚類算法0.9110.9090.

20、912GA2C2A0.9150.9110.9154 結(jié)論遺傳算法和蟻群聚類算法的有機(jī)融合，正是利用遺傳算法的快速全局搜索能力和蟻群算法的正反饋收斂機(jī)制，優(yōu)勢互補(bǔ)。從仿真實(shí)例來看，該算法比標(biāo)準(zhǔn)蟻群聚類算法以及模糊蟻群聚類算法在優(yōu)化性能和時(shí)間性能上有一定的優(yōu)勢。此算法的瓶頸在于融合的時(shí)機(jī)把握，雖然目前的解決方案能滿足要求，但是仍然需要繼續(xù)完善。參考文獻(xiàn)1 Colorni A, Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies. Proceedings of the 1st European Conferenc

21、e on Artificial Life, 1991, 134142.2 Dorigo M. Optimization, learning and natural algorithm.Ph.D.Thesis, Department of Electronics, Politecnico diMilano, Italy, 1992.3 Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transaction on Systems, Man, and C

22、ybernetics-Part B, 1996, 26(1):2941.4 Abbattista F, Abbattista N, Caponetti L. An evolutionary and cooperative agents model for optimization. Proceedings of the IEEE International Conference on Evolutionary Computation, 1995, 2:668671.5 段海濱. 蟻群算法原理及其應(yīng)用.北京:科學(xué)出版社,2005.6 Deneubourg J L, Goss S, Franks

23、N, et al. The dynamics of collective sorting: robot-like ant and ant-like robotA. In: Meyer J A, Wilson S W ed. Proceedings first conference on simulation of adaptive behavior: from animals to animatsC. Cambridge, MA: MIT Press, 1991. 356-365. 7 Lumer E, Faieta B. Diversity and adaptation in populat

24、ions of clustering antsA. In: Proc. third international conference on simulation of adaptive behavior: from animals to animats 3C. Cambridge, MA: MIT Press, 1994, 499-508. 8 Wu B，Shi Z. A clustering algorithm based on swarm intelligenceA. In: Proceedings IEEE international conferences on info-tech & info-net proceedingC. Beijing, 2001. 58-66.9 Ramos V, Merelo J J. Self-organized stigmergic document maps: environment as a mechanism for context learningA. In: Alba E, Herrera F, Merelo J J, et al., ed. AEB´2002 1st Spanish conference on evolutionary and bio-inspired algorithms