Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings)
This work provides a foundational insight for evolutionary computation, potentially impacting diverse areas like genetic programming and neuroevolution by revealing how encodings can unlock the full power of evolution.
The paper tackles the problem of characterizing the power of evolutionary algorithms by showing that with expressive encodings, simple genetic operators like crossover can sample from arbitrary distributions of child phenotypes, achieving up to super-exponential convergence speed-ups over standard encodings in test problems.
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.