Initialization Matters for Asynchronous Steady-State Evolutionary Algorithms
Eric O. Scott, Kenneth Alan De Jong · 2023
Evaluating the fitness of individuals in the initial population of an evolutionary algorithm (EA) is usually straightforward and poses few theoretical problems. In asynchronous steady-state EAs (ASSEAs), however, the choice of initialization strategy can significantly alter the algorithm's long-term behavior. ASSEAs have long been recognized as an important alternative to parallel and distributed evolution, because unlike the more commonly used generational model, they avoid leaving processing resources idle while waiting for a generation boundary. In our work on ASSEAs, we have observed that colleagues' intuitions tend to differ about what a basic asynchronous initialization strategy should look like---but the implications of this choice have not been studied before. This paper analyzes the results of three competing initialization strategies that have appeared in prior literature---the immediate, until-finished, and extra strategies---and concludes that the immediate strategy in particular, which relies on maintaining a queue of jobs waiting to be evaluated, incurs a slow evolutionary feedback loop and should be used with caution. Queuing is a necessary part of scaling ASSEAs up to be resilient to node failures in large HPC environments, however---so this work suggests that further research is needed to understand how asynchronous initialization can be used most effectively for expensive optimization.