Elon University Home

Elon Computing Sciences

ARBITRARILY EXTENSIBLE ANT COLONY OPTIMIZATION

Presentation at Elon Student Undergraduate Research Forum, Spring 2004

Ryan T. Barnard (Professor Joel Hollingsworth), Department of Computing Sciences

Many of man's scientific advances have come from the imitation of the natural world. With lessons learned from nature, researchers are exploring new ideas in the fields of Mathematics and Computer Science.  Ant Colony Optimization (ACO) is a relatively easy approach to finding optimal solutions to difficult (NP-complete) problems. This is done through the simulation of ant colonies, utilizing the emergent intelligent behavior resulting from the interactions of many ants.  A single simulated ant shows very little intelligent decision making skills, but a colony of simulated ants have shown the ability to solve extremely complex problems in a reasonable amount of time. This research, Arbitrarily Extensible Ant Colony Optimization (AEACO), extends ACO techniques to create a new algorithm that is extensible, easily applied to new types of problems, and is almost entirely context independent.
 
This talk will begin with an introduction to the implementation of the discrete event simulator used to simulate the ant colony. The extensions to ACO in order to achieve AEACO will be developed.  I will show how every problem that can be defined as an n-dimensional adjacency matrix can be solved using my techniques, specifically focusing on food gathering as an example of the capabilities of AEACO. Finally, I will discuss a comparison of various approaches to solving the food gathering problem.