  This paper characterizes the inherent power of evolutionary algorithms. This
power depends on the computational properties of the genetic encoding. With
some encodings, two parents recombined with a simple crossover operator can
sample from an arbitrary distribution of child phenotypes. Such encodings are
termed \emph{expressive encodings} in this paper. Universal function
approximators, including popular evolutionary substrates of genetic programming
and neural networks, can be used to construct expressive encodings. Remarkably,
this approach need not be applied only to domains where the phenotype is a
function: Expressivity can be achieved even when optimizing static structures,
such as binary vectors. Such simpler settings make it possible to characterize
expressive encodings theoretically: Across a variety of test problems,
expressive encodings are shown to achieve up to super-exponential convergence
speed-ups over the standard direct encoding. The conclusion is that, across
evolutionary computation areas as diverse as genetic programming,
neuroevolution, genetic algorithms, and theory, expressive encodings can be a
key to understanding and realizing the full power of evolution.
