AbstractsComputer Science

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

by Shilpa P Hardas




Institution: University of Georgia
Department: Artificial Intelligence
Degree: MS
Year: 2005
Keywords: Ant Colony Optimization
Record ID: 1769186
Full text PDF: http://purl.galileo.usg.edu/uga_etd/hardas_shilpa_p_200508_ms


Abstract

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.