Automated Heuristic Generation By Intelligent Search
Publication Date
December 14, 2021
Creator
Abstract
This thesis presents research that examines the effectiveness of several different program synthesis techniques when used to automate the creation of heuristics for a local search-based Boolean Satisfiability solver.
Previous research focused on the automated creation of heuristics has almost exclusively relied on evolutionary computation techniques such as genetic programming to achieve its goal. In wider program synthesis research, there are many other techniques which can automate the creation of programs. However, little effort has been expended on utilising these alternate techniques in automated heuristic creation.
In this thesis we analyse how three different program synthesis techniques perform when used to automatically create heuristics for our problem domain. These are genetic programming, exhaustive enumeration and a new technique called local search program synthesis. We show how genetic programming can create effective heuristics for our domain. By generating millions of heuristics, we demonstrate how exhaustive enumeration can create small, easily understandable and effective heuristics. Through an analysis of the memoized results from the exhaustive enumeration experiments, we then describe local search program synthesis, a program synthesis technique based on the minimum tree edit distance metric. Using the memoized results, we simulate local search program synthesis on our domain, and present evidence that suggests it is a viable technique for automatically creating heuristics.
We then define the necessary algorithms required to use local search program synthesis without any reliance on memoized data. Through experimentation, we show how local search program synthesis can be used to create effective heuristics for our domain. We then identify examples of heuristics created that are of higher quality than those produced from other program synthesis methods. At certain points in this thesis, we perform a more detailed analysis on some of the heuristics created. Through this analysis, we show that, on certain problem instances, several of the heuristics have better performance than some state-of-the-art, hand-crafted heuristics.
Item Type
ethesis
Thesis Type
PhD
Supervisors
Associated Schools / Departments
School of Computer Science (UK)
eprints ID
74496
UoN Repository URI
Except where otherwise noted, this item's license is described as
File(s)![Thumbnail Image]()
Name
THESIS-ANDREW-BURNETT-FINAL.pdf
Type
Full-text
Description
Examined
Size
43.14 MB
Format
Adobe PDF
Checksum (MD5)
a7cc106d33e500deee8e453190dc8393