- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Understanding stochastic local search algorithms :...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Understanding stochastic local search algorithms : an empirical analysis of the relationship between search space structure and algorithm behaviour Smyth, Kevin R.G.
Abstract
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.
Item Metadata
Title |
Understanding stochastic local search algorithms : an empirical analysis of the relationship between search space structure and algorithm behaviour
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2004
|
Description |
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.
|
Extent |
11285610 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-11-24
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
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.
|
DOI |
10.14288/1.0051395
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2004-11
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
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.