An ant colony approach to the Snake-in-the-Box problem

by 1979- Hardas, Shilpa Prakash

In this thesis we present a new approach to the Snake-In-the-Box (SIB) problem using Ant Colony Optimization (ACO). ACO refers to a class of algorithms that model the foraging behavior of ants to find solutions to combinatorial optimization problems. SIB is a wellknown problem, that involves finding a Hamiltonian path through a hypercube which follows certain additional constraints. This domain suffers from severe combinatorial explosion and has been the subject of various search techniques which include genetic algorithms [Potter et al., 1994; Casella, 2005], exhaustive search [Kochut, 1994] , mathematical logic [Rajan and Shende, 1999] and iterated local search [Brown, 2005] . After making certain problem specific customizations a variation on the MIN-MAX Ant System, MMAS SIB, has shown very promising results when applied to the SIB problem. The length of the longest known snake in dimension 8 was matched, using much less computation and time than the best known methods for this problem. Index words: Ant Colony Optimization, Snake-In-the-Box, Swarm intelligence An Ant Colony approach to the Snake-In-the-Box Problem by Shilpa Prakash Hardas B.B.A., The University of Georgia, 2001 A Thesis Submitted to the Graduate Faculty of The University of Georgia in Partial Fulfillment of the Requirements for the Degree Master of Science Athens, Georgia 2005 c? 2005 Shilpa Prakash Hardas All Rights Reserved An Ant Colony approach to the Snake-In-the-Box Problem by Shilpa Prakash Hardas