Exploring the landscape of the space of heuristics for local search in SAT
Local search is a powerful technique on many combinatorial optimisation problems. However, the effectiveness of local search methods will often depend strongly on the details of the heuristics used within them. There are many potential heuristics, and so finding good ones is in itself a challenging...
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Published: |
2017
|
| Online Access: | https://eprints.nottingham.ac.uk/43783/ |
| _version_ | 1848796767526584320 |
|---|---|
| author | Burnett, Andrew W. Parkes, Andrew J. |
| author_facet | Burnett, Andrew W. Parkes, Andrew J. |
| author_sort | Burnett, Andrew W. |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Local search is a powerful technique on many combinatorial optimisation problems. However, the effectiveness of local search methods will often depend strongly on the details of the heuristics used within them. There are many potential heuristics, and so finding good ones is in itself a challenging search problem. A natural method to search for effective heuristics is to represent the heuristic as a small program and then apply evolutionary methods, such as genetic programming. However, the search within the space of heuristics is not well understood, and in particular little is known of the associated search landscapes. In this paper, we consider the domain of propositional satisfiability (SAT), and a generic class of local search methods called ‘WalkSAT’. We give a language for generating the heuristics; using this we generated over three million heuristics, in a systematic manner, and evaluated their associated fitness values. We then use this data set as the basis for an initial analysis of the landscape of the space of heuristics. We give evidence that the heuristic landscape exhibits clustering. We also consider local search on the space of heuristics and show that it can perform quite well, and could complement genetic programming methods on that space. |
| first_indexed | 2025-11-14T19:53:13Z |
| format | Conference or Workshop Item |
| id | nottingham-43783 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:53:13Z |
| publishDate | 2017 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-437832020-05-04T18:48:48Z https://eprints.nottingham.ac.uk/43783/ Exploring the landscape of the space of heuristics for local search in SAT Burnett, Andrew W. Parkes, Andrew J. Local search is a powerful technique on many combinatorial optimisation problems. However, the effectiveness of local search methods will often depend strongly on the details of the heuristics used within them. There are many potential heuristics, and so finding good ones is in itself a challenging search problem. A natural method to search for effective heuristics is to represent the heuristic as a small program and then apply evolutionary methods, such as genetic programming. However, the search within the space of heuristics is not well understood, and in particular little is known of the associated search landscapes. In this paper, we consider the domain of propositional satisfiability (SAT), and a generic class of local search methods called ‘WalkSAT’. We give a language for generating the heuristics; using this we generated over three million heuristics, in a systematic manner, and evaluated their associated fitness values. We then use this data set as the basis for an initial analysis of the landscape of the space of heuristics. We give evidence that the heuristic landscape exhibits clustering. We also consider local search on the space of heuristics and show that it can perform quite well, and could complement genetic programming methods on that space. 2017-06-05 Conference or Workshop Item PeerReviewed Burnett, Andrew W. and Parkes, Andrew J. (2017) Exploring the landscape of the space of heuristics for local search in SAT. In: IEEE Congress on Evolutionary Computation 2017, 5-8 June 2017, Donostia, San Sebastián, Spain. |
| spellingShingle | Burnett, Andrew W. Parkes, Andrew J. Exploring the landscape of the space of heuristics for local search in SAT |
| title | Exploring the landscape of the space of heuristics
for local search in SAT |
| title_full | Exploring the landscape of the space of heuristics
for local search in SAT |
| title_fullStr | Exploring the landscape of the space of heuristics
for local search in SAT |
| title_full_unstemmed | Exploring the landscape of the space of heuristics
for local search in SAT |
| title_short | Exploring the landscape of the space of heuristics
for local search in SAT |
| title_sort | exploring the landscape of the space of heuristics
for local search in sat |
| url | https://eprints.nottingham.ac.uk/43783/ |