Skip to main content
Article
Asynchronous Parallel Evolutionary Algorithms: Leveraging Heterogeneous Fitness Evaluation Times for Scalability and Elitist Parsimony Pressure
Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation
  • Matthew A. Martin
  • Alex R. Bertels
  • Daniel R. Tauritz, Missouri University of Science and Technology
Abstract

Many important problem classes lead to large variations in fitness evaluation times, such as is often the case in Genetic Programming where the time complexity of executing one individual may differ greatly from that of another. Asynchronous Parallel Evolutionary Algorithms (APEAs) omit the generational synchronization step of traditional EAs which work in well-defined cycles. This paper provides an empirical analysis of the scalability improvements obtained by applying APEAs to such problem classes, aside from the speed-up caused merely by the removal of the synchronization step. APEAs exhibit bias towards individuals with shorter fitness evaluation times, because they propagate faster. This paper demonstrates how this bias can be leveraged in order to provide a unique type of "elitist" parsimony pressure which rewards more efficient solutions with equal solution quality.

Meeting Name
17th Annual Conference Companion on Genetic and Evolutionalry Computation (GECCO'15) (2015: Jul. 11-15, Madrid, Spain)
Department(s)
Computer Science
Research Center/Lab(s)
Center for High Performance Computing Research
International Standard Book Number (ISBN)
9781450334884
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2015 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
1-1-2015
Citation Information
Matthew A. Martin, Alex R. Bertels and Daniel R. Tauritz. "Asynchronous Parallel Evolutionary Algorithms: Leveraging Heterogeneous Fitness Evaluation Times for Scalability and Elitist Parsimony Pressure" Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (2015) p. 1429 - 1430
Available at: http://works.bepress.com/daniel-tauritz/20/