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 introduce 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. This gives slow-evaluating individuals that have higher fitnesses an increased ability to multiply in the population. We find that SWEET appears effective in simulated take-over time analysis, but that its benefit is confined mostly to early in the run, and our preliminary study on an autonomous vehicle controller problem that involves tuning a spiking neural network proves inconclusive.