Keywords and Phrases
Asynchronous Parallel Computation; Boolean Satisfiability; Hyper-heuristics; Program Understanding
"Modern society gives rise to complex problems which sometimes lend themselves to being transformed into Boolean satisfiability (SAT) decision problems; this thesis presents an example from the program understanding domain. Current conflict-driven clause learning (CDCL) SAT solvers employ all-purpose heuristics for making decisions when finding truth assignments for arbitrary logical expressions called SAT instances. The instances derived from a particular problem class exhibit a unique underlying structure which impacts a solver's effectiveness. Thus, tailoring the solver heuristics to a particular problem class can significantly enhance the solver's performance; however, manual specialization is very labor intensive. Automated development may apply hyper-heuristics to search program space by utilizing problem-derived building blocks. This thesis demonstrates the potential for genetic programming (GP) powered hyper-heuristic driven automated design of algorithms to create tailored CDCL solvers, in this case through custom variable scoring and learnt clause scoring heuristics, with significantly better performance on targeted classes of SAT problem instances. As the run-time of GP is often dominated by fitness evaluation, evaluating multiple offspring in parallel typically reduces the time incurred by fitness evaluation proportional to the number of parallel processing units. The naive synchronous approach requires an entire generation to be evaluated before progressing to the next generation; as such, heterogeneity in the evaluation times will degrade the performance gain, as parallel processing units will have to idle until the longest evaluation has completed. This thesis shows empirical evidence justifying the employment of an asynchronous parallel model for GP powered hyper-heuristics applied to SAT solver space, rather than the generational synchronous alternative, for gaining speed-ups in evolution time. Additionally, this thesis explores the use of a multi-objective GP to reveal the trade-off surface between multiple CDCL attributes"--Abstract, page iii.
Tauritz, Daniel R.
McMillin, Bruce M.
Mulder, Samuel A.
M.S. in Computer Science
Missouri University of Science and Technology
ix, 64 pages
© 2016 Alex Raymond Bertels, All rights reserved.
Thesis - Open Access
Library of Congress Subject Headings
Parallel processing (Electronic computers)
Expert systems (Computer science)
Electronic OCLC #
Bertels, Alex Raymond, "Automated design of boolean satisfiability solvers employing evolutionary computation" (2016). Masters Theses. 7549.