Evaluation Time Bias in Asynchronous Evolutionary Algorithms: A Replication Study and a Novel Mitigation Strategy
Joshua Karns, Travis Desell · Proceedings of the Genetic and Evolutionary Computation Conference · 2025
Evolutionary Algorithms (EAs) are a flexible and powerful search technique that are frequently applied to a wide variety of problems. Much of their power comes from their ease of parallelization, lending themselves well to a master-worker parallelization scheme. When a synchronous (μ, λ)-style EA is parallelized and genome evaluation time is not constant, worker processors may spend a significant amount of time idle waiting for other genome evaluations to complete. (μ, λ)-style EAs with a steady-state population are frequently employed to avoid this idle time. There is an existing body of work that suggests that, while this does reduce idle processor time, it may not lead to better solutions because of evaluation time bias. In this work, results from a paper that demonstrate this experimentally are fully reproduced from scratch. During this replication, the roles crossover and population initialization play in this bias were uncovered. This is evaluated experimentally and motivates a mitigation strategy, which is compared to other mitigation strategies and is found to perform about as well as other strategies, without modifying anything other than the way the population is initialized. Moreover, a new open source library was developed in order to facilitate these experiments and further investigations.