自适应的蚂蚁群聚演算法

1、自適應的螞蟻群聚演算法資科研一 96317007 江庭維 一、摘要 3二、介紹 4三、BM與LF Model 介紹 6四、為何使用Ant Sleeping Model 8五、人工螞蟻睡眠模式(ASM) 9 六、自適應螞蟻調整演算法(A A4 4C C) 17七、計算如何找到合適的代理人 18八、如何計算啟動機率 20九、代理人移動的策略 22十、實驗結果 25一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、人工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略

2、十、實驗結果 人工螞蟻睡眠模式（ASM）和自適應螞蟻群聚演算法（A A4 4C C） ，上述兩個方法都是藉由模擬螞蟻群聚的行為，來解決資料探勘所遇到的群聚問題。並且在實驗結果也顯示出，此兩種方法比以往的演算法更容易實作，並且效率更好。一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、人工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果 藉由觀察昆蟲的群聚行為，如採集食物、築巢保衛等，顯示昆蟲社會中，具有很高的群體智慧。因此許多最佳化的演算法都是模擬

3、昆蟲群聚行為，來解決函數區域最佳化、組合最佳化和其他科學領域等。 而最被廣泛研究的就是螞蟻演算法，它們能以團隊合作，來解決單一螞蟻無法解決的問題，利用彼此間的相互合作影響，來達到最好的成效。 此篇論文最主要探討的問題物件分類，下 面會介紹Deneubourg所提出的Basic Model（簡稱BM）與Lumer 和 Faieta所提出改善BM只能針對兩類物件分類的LF Model 。 最後會介紹本篇的ASM與A4C改善上述兩個方法，在分類過程中需要大量計算時間及無法直接對資料做調整更新等問題。 一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、

4、人工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果 BM是利用螞蟻撿起和放下兩種簡單行為提出螞蟻分群。物件與螞蟻先隨機放在二維棋盤內，空手的螞蟻會撿起異於周遭環境得物件，持有物件的螞蟻會放下與週遭環境相似的物件，而要撿起或放下是透過它們記憶中相同物件比例來做決定。如此就能達到分類的效果。 上面提到的BM方法只能針對兩類物件分 群，Lumer和Faieta是以BM方法為基礎， 也是將要分類的資料丟入二維棋盤內，然後 在棋盤內創造人工螞蟻，而行為與BM相似， 不同之處在與它們不是觀察持有的物件與 周

5、圍物件是否相同，而是判斷是否相似， 這樣就能夠處理多類別物件的分類。一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、人工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果 BM與LF兩個方法，是將人工螞蟻與分類物件區隔開來，因此造成需要大量的空間來儲存資料，並且資料無法做直接的變動，都必須透過人工螞蟻來做更新，所以往往會造成計算的負擔。 而ASM方法是一隻螞蟻直接代表一個物件， 這樣當資料更新時可以同步處理，降低計算 時間與空間的成本。一、摘要二、

6、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、人工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果 螞蟻為了睡眠，它們必須不斷找尋更舒適及安全的環境，因此必須找到跟它們外型相 似的環境。根據這個靈感我們建立了ASM ， 在這裡代理人代表螞蟻，它們的行為很簡單 且重複，當它們未找到合適的休息位置時， 它們會積極的四處尋找，直到找到為止。而 如果找的之後不滿意，就會繼續重複相同動 作。根據下面的因素定義ASM ：Definition 1 Definition

7、1 ：G代表二維網格的所有位置，G（x，y）的向量值皆屬於正整數。G（x，y）=i ，代表此位置有代理人。G（x，y）=0 ，代表此位置無代理人。利用網格來表示位置，可以確保每個位置在網格內都是相等。Definition 2Definition 2：使用agenti來代表第i個代理人。G（ agenti ）=G（xi，yi）代表某代理人在網格中所在的位置。在ASM中一個代理人代表一個資料，這樣的性質接近群聚的問題，以讓同性質的資料聚集在一起。Definition 3Definition 3：N（agenti）代表在某代理人在範圍內的其他鄰近代理人。L（ agenti ）代表在N（agenti）

8、範圍內無其他代理人。yixiiSyySxxnyxagentN,|2mod,)(1)0,)(yxGagentNyxyxagentLii(2)Definition 4Definition 4：datai （zi1 ， zi2 ， ， zik ），代表某代理人的資料為K維。d（ agenti ， agentj） d（ datai ， dataj）| datai - dataj |p，代表兩筆資料的差異性。註：P 2 ，歐幾里德距離。Definition 5Definition 5：ijagentNagentjiiiyxiagentagentdssagentf222,12121njjiiagentag

9、entdn1,11ninjjiagentagentdnn11,11(4)(5)(6)代理人可見的範圍兩筆資料的差異性評估是否群聚對象兩筆資料第i個代理人跟其他代理人的差異性之平均n個代理人n筆資料跟其他代理人的差異性之平均(每筆資料都要跟n-1筆比較)Definition 6Definition 6：pa（agenti）判斷代理人是否要找新位置。當f（agenti）0 ， pa（agenti）1代理人會變為活動狀態(找尋新位置) 。當f（agenti）1 ， pa（agenti）0代理人會變為睡眠狀態(留在原地) 。iiaagentfagentp2cos（7） 代理人的合適性與否，與其他代理人

10、的差異性有關，這些代理人在移動過程中會影響鄰近代理人的合適性，隨著疊代次數增加相似的會群聚起來，不相似的會被隔離出去。 因此透過區域的群聚影響，慢慢地擴展到全域的群聚分類。一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、人工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果A A4 4C C虛擬碼設定初始參數隨機選擇位置找出合適代理人計算啟動機率尋找新的位置留在原地更新參數疊代次數一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant

11、Sleeping Model五、人工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果 根據上面演算法第七行，我們可以發現參數是影響找到合適代理人的重要因素。下面有三種方法來決定參數： 方法一：所有代理人都設為常數。方法二：每個代理人都有不同值，如i代理 人的值為i。方法三：每次疊代值都做更新，更新公式為 tttffkttt第t次疊代的值常數第t次疊代的評估函數一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、人工螞蟻眠模式(ASM)六、自適應螞蟻調

12、整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果 根據演算法第七行，當代理人是否要找尋新位置時，要根據啟動機率函式pa ，其中參數是影響請啟動的因素，因為值越小則pa越大，因此就有很高機率去找尋新的位置，反之則有很高機率進入睡眠狀態下面有兩種方法可以決定值：方法一：值設為常數，建議值為2 。 （由公式推導出來）方法二：每次疊代做更新，更新公式如下：假設tmax為106代入(t)，lg0 、(t)=2。 ttfktmaxlg2疊代次數一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、人

13、工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果 在疊代過程中如果代理人要尋找新的位置時，會依據下面兩種方法來移動：隨機找尋方法，從L（agenti）範圍內的空網格中，隨機挑選一個做移動。貪婪找尋方法，設定一個參數來決定某代理人從L（agenti）範圍中找出一個最合適的移動位置。一、摘要二、介紹三、BM與LF Model 介紹四、為何使用Ant Sleeping Model五、人工螞蟻眠模式(ASM)六、自適應螞蟻調整演算法(A A4 4C C)七、計算如何找到合適的代理人八、如何計算啟動機率九、代理人移動的策略十、實驗結果 (a)(c)(b)(d)圖一、 LF分類結果a. 屬性空間的資料分佈b. 初始數據分佈在網格c. 500000 次疊代的資料分類情況d. 1000000次疊代的資料分類情況圖二、 A4C分類結果 (a)(c)(b)(d)a. 初始數據分佈在網格b. 代理人在0次疊代分類情況c. 代理人在10000次疊代分類情況d