TABLE OF CONTENTS Gurdip Singh, Kansas State University, USA
Sanjoy Das, Kansas State University, USA
Shekhar V. Gosavi, Kansas State University, USA
Sandeep Pujar, Kansas State University, USA
This chapter introduces ant colony optimization as a method for computing minimum Steiner trees in graphs. Tree computation is achieved when multiple ants, starting out from different nodes in the graph, move towards one another and ultimately merge into a single entity. A distributed version of the proposed algorithm is also described, which is applied to the specific problem of data-centric routing in wireless sensor networks. This research illustrates how tree based graph theoretic computations can be accomplished by means of purely local ant interaction. The authors hope that this work will demonstrate how innovative ways to carry out ant interactions can be used to design effective ant colony algorithms for complex optimization problems.
Ants live in colonies and have evolved to exhibit very complex patterns of social interaction. Such interactions are clearly seen in the foraging strategy of ants. Despite the extremely simplistic behavior of individual ants, they can communicate with one another through secretions called pheromones, and this cooperative activity of the ants in a nest gives rise to an emergent phenomenon known as swarm intelligence (Bonabeau et al., 1999). Ant Colony Optimization (ACO) algorithms are a class of algorithms that mimic the cooperative behavior of real ant behavior to achieve complex computations.
Ant colony optimization was originally introduced as a meta-heuristic for the wellknown traveling...
