|Institution:||University of Georgia|
|Keywords:||Ant Colony Optimization|
|Full text PDF:||http://purl.galileo.usg.edu/uga_etd/hardas_shilpa_p_200508_ms|
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 nd solutions to combinatorial optimization problems. SIB is a well-known problem, that involves nding a Hamiltonian path through a hypercube which follows certain additional constraints. This domain su 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 speci c 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.