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.