Skip to main content
Article
Why Asynchronous Parallel Evolution is the Future of Hyper-heuristics: A CDCL SAT Solver Case Study
Proceedings of the Genetic and Evolutionary Computation Conference (2016, New York, NY)
  • Alex R. Bertels
  • Daniel R. Tauritz, Missouri University of Science and Technology
Abstract
Evolutionary Algorithms (EAs) are inherently parallel due to their ability to simultaneously evaluate the fitness of individuals. Synchronous Parallel EAs (SPEAs) leverage this with the intent to gain significant speed-ups when executed on multiple processors. However, many important problem classes lead to large variations in fitness evaluation times, such as is often the case in hyper-heuristics where the time complexity of executing one individual may differ greatly from that of another. Asynchronous Parallel EAs (APEAs) omit the generational synchronization step of traditional EAs which work in well-defined cycles. They can provide scalability improvements proportional to the variation in fitness evaluation times of the evolved individuals, and therefore should be considered for use in hyper-heuristics. This paper provides an empirical analysis of the improvements obtained by applying APEAs, compared to SPEAs, on a case study involving the evolution of conflict-driven clause learning Boolean satisfiability solvers, demonstrating that APEAs are the future of hyper-heuristics.
Meeting Name
Genetic and Evolutionary Computation Conference (2016: Jul. 20-24, New York, NY)
Department(s)
Computer Science
Research Center/Lab(s)
Center for High Performance Computing Research
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2016 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
7-1-2016
Citation Information
Alex R. Bertels and Daniel R. Tauritz. "Why Asynchronous Parallel Evolution is the Future of Hyper-heuristics: A CDCL SAT Solver Case Study" Proceedings of the Genetic and Evolutionary Computation Conference (2016, New York, NY) (2016) p. 1359 - 1365
Available at: http://works.bepress.com/daniel-tauritz/67/