Evaluation-Time Bias in Quasi-Generational and Steady-State Asynchronous Evolutionary Algorithms

Abstract

A number of papers have emerged in the last two years that apply and study asynchronous master-slave evolutionary algorithms based on a steady-state model. These efforts are largely motivated by the observation that, unlike traditional (synchronous) EAs, asynchronous EAs are able to make maximal use of many parallel processors, even when some individuals evaluate more slowly than others. Asynchronous EAs do not behave the same as their synchronous counterparts, however, and as of yet there is very little theory that makes it possible to predict how they will perform on new problems. Of some concern is evidence suggesting that the steady-state versions tend to be biased toward regions of the search space where fitness evaluation is cheaper. This has led some authors to suggest a so-called ‘quasi-generational’ asynchronous EA as an intermediate solution that incurs neither idle time nor significant bias toward fast solutions. We perform experiments with the quasi-generational EA, and show that it does not deliver the promised benefits: it is, in fact, just as biased toward fast solutions as the steady-state approach is, and it tends to converge even more slowly than the traditional, generational EA.

Publication
In Genetic and Evolutionary Computation Conference
Date
Links