Avoiding excess computation in asynchronous evolutionary algorithms

Asynchronous evolutionary algorithms are becoming increasingly popular as a means of making full use of many processors while solving computationally expensive search and optimization problems. These algorithms excel at keeping large clusters fully utilized, but may sometimes inefficiently sample an excess of fast-evaluating solutions at the expense of higher-quality, slow-evaluating ones. We have previously introduced a steady-state parent selection strategy, SWEET (“Selection whilE EvaluaTing”), that sometimes selects individuals that are still being evaluated and allows them to reproduce early. We perform a takeover-time analysis that confirms that this strategy gives slow-evaluating individuals that have higher fitnesses an increased ability to multiply in the population. We also find that SWEET appears effective at improving optimization performance on problems in which solution quality is positively correlated with evaluation time. We evaluate our approach on six simulated real-valued optimization problems and three real-world applications: an autonomous vehicle controller problem that involves tuning a spiking neural network and two adversarial EA problems. We further evaluate SWEET versus a basic asynchronous process in a simulated setting. We present evidence that SWEET outperforms basic asynchronous processes in a use-case in which performance is positively correlated with evaluation time, and performs comparably (and often better) than basic asynchronous processes in several use-cases where performance is negatively correlated with evaluation time. That said, in the cases where performance and evaluation time are negatively correlated the variance of outcomes for SWEET is notably high.