混合式螞蟻最佳分群演算法

A Hybrid Ant Colony Optimization Algorithm for Data Clustering

葉恒嘉(Heng-jia Ye)

指導教授 ： 高有成

大同大學/經營設計學院/資訊經營學系所/碩士(2007年)

摘要

本研究主要是結合ACO (Ant Colony Optimization)演算法和禁忌搜尋法(Tabu Search，TS)，發展出新的資料分群演算法，我們將之命名為HACOC(Hybrid Ant Colony Optimization for Clustering)。當求解資料分群問題時，如果群組數變大以及資料點變多，ACO資料分群演算法的求解效率變差。原因是螞蟻在求解的過程中，所需嘗試的解相對變多，導致螞蟻沒有辦法在演算法演化早期儘快地將費洛蒙留在不錯的節點上，導致求解的品質及收斂速度受到影響。所以我們將ACOC演算法在每一回合螞蟻找出來的最佳解後，加入禁忌搜尋法進行區域搜索，以找尋更佳的解。利用螞蟻演算法全域搜索求解的特性，結合禁忌搜尋法區域搜索求解的特性，可以有效改善ACOC演算法求解的品質及收斂速度。本演算法已經開發成系統，針對五個資料分群問題進行實驗，結果顯示HACOC確實能夠有效改善ACOC資料分群的績效。我們也將HACOC與其他分群方法進行比較，例如k-means、Tabu Search、GA、SACO及ACO等，發現HACOC分群能力優於其他方法。

關鍵字

k-means ； 禁忌搜尋法 ； 螞蟻演算法 ； 資料分群

並列摘要

This research mainly focuses on integrating the Tabu search method with the ACO (Ant Colony Optimization) method for developing a new data clustering algorithm. When the ACO algorithm is applied to solve clustering problems, it is found that the solution quality may get worse if the number of data items or the group number becomes large. In a large solution space, it is difficult for ants to lay pheromone on better routes in the early stage of evolution, so the calculation process needs much more time to reach a high-quality solution. To find out a better clustering solution, in each ACO iteration, the tabu search method is used to improve the best solution found by ants before they update the pheromone trails. In other words, Tabu search performs the local search while ACO carries out the global search. The proposed algorithm has been named as HACOC (Hybrid Ant Colony Optimization for Clustering) and implemented into a software system in C++. Five clustering problems are generated or collected for the numerical experiment. The experimental results show that HACOC can effectively improve the weakness of ACO-based clustering methods and outperforms other methods, such as K-means, Tabu Search, genetic algorithm, and pure ACO.

並列關鍵字

k-means ； Tabu Search ； ACO ； data clustering

參考文獻

Clustering of High Dimensional Data for Data Mining Applications.” Proc. of

[2] Al-Sultan, K. S., “A tabu search approach to the clustering problem.” Pattern

[3] Bandyopadhyay, S.,“Genetic clustering for automatic evolution of clusters and

application to image classification,” pattern recognition,35, pp. 1197-1208, 2002

clustering algorithm for cellular manufacturing.” International Journal of