Graduation Semester and Year

2009

Language

English

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science and Engineering

First Advisor

Manfred Huber

Abstract

The behavior and self-organization of ant colonies has been widely studied and served as the inspiration and source of many swarm intelligence models and related clustering algorithms. Unfortunately, most models that directly mimic ants produce too many clusters and converge too slowly. A wide range of research has attempted to address this issue through various means, but a number of problems remain: 1) Ants must still physically move from one cluster to another through intermediate locations, 2) current methods for remote relocation of an item only consider one movement at time to a particular location and do not consider patterns in movement to that location, and 3) while current methods have included effective bulk item movement, they do not provide efficient movement while still maintaining the self-organizing nature of ant-based clustering which is essential for filtering out outliers and allowing effective splitting of clusters. This thesis addresses these problems by proposing a new algorithm for ant-based clustering. In this algorithm ants maintain a movement zone around each cluster, keeping ants from spending time in locations where there is nothing to do. These movement zones around individual clusters are used to elect representatives that are responsible for all long distance movement. Each representative can, probabilistically, pass an object it has to any other representative. Since each cluster has approximately one representative at any given time, the search space for placing items over a long distance is reduce to the number of clusters. So instead of having all the ants use up time wandering around the map, one ant can be responsible for sampling all local clusters. This provides an infrastructure by which clusters can efficiently merge over long distances and better clusters for items in the wrong clusters can be found without having to travel to them. While this model does require a considerable overhead as compared with contemporary algorithms, a better convergence rate can be achieved because the efficient bulk movement of items and sampling at the cluster level.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS