An ant colony approach to the Snake-in-the-Box problem
Hardas, Shilpa P
MetadataShow full item record
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.