neural networks research group
areas
•
people
•
projects
•
demos
•
publications
•
software/data
•
Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings) (2022)
Elliot Meyerson
, Xin Qiu, and
Risto Miikkulainen
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 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.
View:
PDF
Citation:
In
Proceedings of the Genetic and Evolutionary Computation Conference
, 2022.
Bibtex:
@inproceedings{meyerson:gecco22, title={Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings)}, author={Elliot Meyerson and Xin Qiu and Risto Miikkulainen}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, month={ }, url="http://nn.cs.utexas.edu/?meyerson:gecco22", year={2022} }
People
Elliot Meyerson
Ph.D. Alumni
ekm [at] cs utexas edu
Risto Miikkulainen
Faculty
risto [at] cs utexas edu
Areas of Interest
Evolutionary Computation
Neuroevolution
Theory of Evolutionary Computation