Estimating the Advantage of Age-Layering in Evolutionary Algorithms (2016)
Hormoz Shahrzad, Babak Hodjat, and Risto Miikkulainen
In an age-layered evolutionary algorithm, candidates are evaluated on a small number of samples first; if they seem promising, they are evaluated with more samples, up to the entire training set. In this manner, weak candidates can be eliminated quickly, and evolution can proceed faster. In this paper, the fitness-level method is used to derive a theoretical upper bound for the runtime of (k+1) age-layered evolutionary strategy, showing a significant potential speedup compared to a non-layered counterpart. The parameters of the upper bound are estimated experimentally in the 11-Multiplexer problem, verifying that the theory can be useful in configuring age layering for maximum advantage. The predictions are validated in a practical implementation of age layering, confirming that 60-fold speedups are possible with this technique.

This work was done at Sentient Technologies, Inc.

To Appear In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2016, Denver, CO), 2016.

Risto Miikkulainen Faculty risto [at] cs utexas edu