The Impact of Asynchrony on Parallel Model-Based EAs

Genetic and Evolutionary Computation Conference (GECCO), pp. 910–918

Abstract

In a parallel EA one can strictly adhere to the generational clock, and wait for all evaluations in a generation to be done. However, this idle time limits the throughput of the algorithm and wastes computational resources. Alternatively, an EA can be made asynchronous parallel. However, EAs using classic recombination and selection operators (GAs) are known to suffer from an evaluation time bias, which also influences the performance of the approach. Model-Based Evolutionary Algorithms (MBEAs) are more scalable than classic GAs by virtue of capturing the structure of a problem in a model. If this model is learned through linkage learning based on the population, the learned model may also capture biases. Thus, if an asynchronous parallel MBEA is also affected by an evaluation time bias, this could result in learned models to be less suited to solving the problem, reducing performance. Therefore, in this work, we study the impact and presence of evaluation time biases on MBEAs in an asynchronous parallelization setting, and compare this to the biases in GAs. We find that a modern MBEA, GOMEA, is unaffected by evaluation time biases, while the more classical MBEA, ECGA, is affected, much like GAs are.

Authors 4

1. Arthur Guijt

   Centrum Wiskunde & Informatica · Delft University of Technology

   Affiliation as printed

   Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands

   Delft University of Technology, Delft, Netherlands

   Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands Delft University of Technology, Delft, Netherlands

2. Dirk Thierens

   Utrecht University

   Affiliation as printed

   Utrecht University, Utrecht, Netherlands

3. Tanja Alderliesten Aachen

   Leiden University Medical Center

   Affiliation as printed

   Leiden University Medical Center, Leiden, Netherlands

4. Peter A. N. Bosman

   Centrum Wiskunde & Informatica · Delft University of Technology

   Affiliation as printed

   Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands

   Delft University of Technology, Delft, Netherlands

   Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands Delft University of Technology, Delft, Netherlands