Open Collections

Understanding stochastic local search algorithms : an empirical analysis of the relationship between search space structure and algorithm behaviour

University of British Columbia

Combinatorial optimisation problems are an important and well-studied class of problems, with applications in most areas of the computing sciences. Because of their prominence, combinatorial optimisation problems and their related decision problems have been the focus of extensive research for several decades. The propositional satisfiability problem (SAT), in particular, has been the focus of a vast amount of research, and a class of algorithms known as stochastic local search (SLS) algorithms has emerged as the state-of-the art on a variety of SAT problem classes. Much of the recent progress in algorithm development has been facilitated by an improved understanding of the properties of SAT instances and of high-performance SAT algorithms. This thesis studies the search space features underlying the behaviour of stochastic local search algorithms for SAT, extending existing results from the literature and providing novel contributions. Search space features such as plateaus and the interconnectivity between plateaus are defined and studied on a variety of SAT instances, and it is empirically demonstrated that features such as these are responsible for the wide range in instance hardness observed in distributions of syntactically identical SAT instances. Furthermore, the novel concept of the performance criticality of variables in SAT instances is introduced, and the connections between search space structure and performance criticality are investigated. Finally, methods for practically exploiting the knowledge gained by this search space analysis are briefly explored, with the goal of improving the state-of-the-art in SAT solving.

Thesis/Dissertation

application/pdf

2009-11-24

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/15656

Computer Science

University of British Columbia

UBCV

DSpace