蟻群算法以及基于蟻群的聚類的簡單介紹
關鍵詞： 蟻群算法    聚類                                           

1 蟻群算法簡介


蟻群算法是意大利學者Dorigo M等于1991年在法國巴黎召開的第一屆歐洲人工生命會議上提出的。1996年，Dorigo M等發表了“The ant system: optimization by a colony of cooperating agents”一文，此文不但系統地闡述了蟻群算法的基本原理和數學模型，還將其與遺傳算法、忌禁搜索算法、模擬退火算法、爬山法等進行了仿真實驗比較，這樣使得蟻群算法逐漸引起了世界許多國家研究者的關注，其應用領域也得到了迅速拓寬。目前人們對蟻群算法的研究已經由當初單一的TSP領域滲透到了多個領域，如車間作業調度問題，車輛路徑問題，控制參數優化，聚類分析，圖像處理等領域，在解決許多復雜優化問題方面已經展現出其優異的性能和巨大的發展潛力。


1.1 蟻群算法原理


自然界中的螞蟻幾乎是瞎子，但是由螞蟻組成的群體，卻體現出了高度機構化的社會組織，在許多情況下能完成遠遠超過單個螞蟻個體能力的復雜任務。以螞蟻覓食為例，看一下螞蟻群體間是如何通過合作以找到一條從蟻巢到食物源最近的道路的。

圖1顯示了在蟻巢（N）和食物源（F）之間，螞蟻已經找到了一條最短的道路。圖2顯示了當這條道路上出現了一個障礙物之后，螞蟻會以等概率的方式從障礙物的兩側A、B通過。圖3顯示了經過一定時間之后，螞蟻就會找到一條最短的道路（經過A側）。這是因為螞蟻在行進的過程中，會分泌一種化學刺激物——信息素留在道路上，而且能夠感知這種物質的存在及其強度，并以此來指導自己運動的方向，傾向于信息素濃度較高的方向移動。


 
 
 
圖1
 圖2
 圖3
 

1.2蟻群算法描述


以TSP問題為例，蟻群算法描述如下：

1）  將m只螞蟻隨機分配到n個城市中去；

2）  位于城市c上的螞蟻k以概率Pk(c,s)選擇一條從城市c到城市s的道路，其中


Jk(c)表示螞蟻k還沒有訪問的城市列表； 表示邊（c，s）上的信息素濃度； ，啟發函數 ，這兩個參數反映了信息素和啟發函數的相對重要性。

3）  當所有螞蟻完成環游，按下述公式進行信息素更新


是信息素揮發因子，其中


Lk是第k只螞蟻的環游長度。

4）  看是否滿足結束條件，如不滿足則轉到第二步。


基于蟻群算法的聚類（提要）
蟻群聚類算法

目的：考慮將Rn空間中的N個對象，分為K個類。

算法思路：將數據和類別之間建立一個對應圖，形成一個N*K的矩陣，每一只螞蟻都對所有的數據分類，然后根據分類結果去更新矩陣中的值，作為下一次分類的依據。

每一只螞蟻都有一個長度為N的字符串S，用來表示找到的一個解。比如N=8 ，K=3 ，那么

2
 1
 3
 2
 2
 3
 2
 1
 

就代表了一種分類方式。第一個對象分到了第二類，第二個對象分到了第一類，等等。

信息素矩陣式一個N*K的矩陣，其中aij表示了對象i 屬于類j 的信息素表達。具體算法如下：

1、  初始化。每一個螞蟻都有一個S串，開始為空。信息素矩陣初始化為一個固定的值。

2、  在t時刻，采用下述策略產生新的S：

a)         根據S的長度，生成一個0，1之間的均勻分布的隨機數，比如

0.69
 0.79
 0.986
 0.988
 0.23
 0.967
 0.091
 0.345
 

對每一個數，與事先給定的概率q0（0<q0<1，此處取q0=0.98）比較，如果小于q0，那么，這個對象的分類依據是看其信息素矩陣中哪一個對應最大，分到哪一類中。比如當前信息素矩陣如下所示（N=8，K=3），那么


1屬于第二類，2屬于第二類，3不參與分類，4不參與分類，5屬于第二類，6屬于第三類，7屬于第二類，8屬于第一類。對于3、4，采用下面的策略分類

b)        根據下式所用的概率進行分類


也就是哪一條邊上的信息素多，它屬于哪一條邊的概率就大。

3、  根據得到的一組解，計算這個螞蟻所得到的解的適應值。此處的適應值函數采取的是計算每一個對象與它所在的聚類中心的歐氏距離的平方和。假如給定一個含有N個對象的集合{x1，x2，……，xN}，現在要把它們分成K類，那么它的適應值函數是：


其中，xiv是第i個對象的第v個屬性值，m是聚類中心，mjv是聚類j中的第v個屬性的平均值， 是一個N*K的矩陣， 定義為


4、  有了一組解之后，進行局部搜索。策略如下：

a)         根據螞蟻的適應值按升序排序，取前L個，記它們的解為Sk，k=1，……，L

b)        k=1

c)        St（i）=Sk（i），i=1，……， N，此處St是一個臨時變量

d)        對于St中的每一個元素，根據概率pls（此處取0.01），讓它的類別變成一個與原來不一樣的隨機的類別，比如原來的St(2)=3，那么如果需要變化（由概率pls來決定），則St(2)變為1，或者2

e)         根據St計算新的適應值Ft，如果新的適應值Ft比原來的Fk小，那么Sk=St，Fk=Ft；

f)         k=k+1；如果k≤L，轉到第c步

5、  按照下述公式，進行信息素的更新。


此處ρ是信息素的揮發系數，其值為[0，1]，