Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings)

• URL: http://arxiv.org/abs/2202.09679v4
• Date: Tue, 2 Aug 2022 21:56:51 GMT
• Title: Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings)
• Authors: Elliot Meyerson, Xin Qiu and Risto Miikkulainen
• Abstract summary: This paper characterizes the inherent power of evolutionary algorithms. It shows that expressive encodings can be a key to understanding and realizing the full power of evolution.
• Score: 27.185579156106694
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• VQDNA: Unleashing the Power of Vector Quantization for Multi-Species Genomic Sequence Modeling [60.91599380893732]
  VQDNA is a general-purpose framework that renovates genome tokenization from the perspective of genome vocabulary learning. By leveraging vector-quantized codebooks as learnable vocabulary, VQDNA can adaptively tokenize genomes into pattern-aware embeddings.
  arXiv  Detail & Related papers  (2024-05-13T20:15:03Z)
• Searching Search Spaces: Meta-evolving a Geometric Encoding for Neural Networks [0.0]
  We show that GENE with a learned function can outperform both direct encoding and the hand-crafted distances. We study how the encoding impacts neural network properties.
  arXiv  Detail & Related papers  (2024-03-20T22:40:53Z)
• On the Suitability of Representations for Quality Diversity Optimization of Shapes [77.34726150561087]
  The representation, or encoding, utilized in evolutionary algorithms has a substantial effect on their performance. This study compares the impact of several representations, including direct encoding, a dictionary-based representation, parametric encoding, compositional pattern producing networks, and cellular automata, on the generation of voxelized meshes.
  arXiv  Detail & Related papers  (2023-04-07T07:34:23Z)
• Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions [8.382710169577447]
  We investigate the effects of genetic operators for bit-string encoding in optimizing nonlinearity. By observing the range of possible changes an operator can provide, one can use this information to design a more effective combination of genetic operators.
  arXiv  Detail & Related papers  (2023-02-12T10:34:01Z)
• X-volution: On the unification of convolution and self-attention [52.80459687846842]
  We propose a multi-branch elementary module composed of both convolution and self-attention operation. The proposed X-volution achieves highly competitive visual understanding improvements.
  arXiv  Detail & Related papers  (2021-06-04T04:32:02Z)
• On the Genotype Compression and Expansion for Evolutionary Algorithms in the Continuous Domain [7.152439554068968]
  We consider genotype compression (where genotype is smaller than phenotype) and expansion (genotype is larger than phenotype) We test our approach with several evolutionary algorithms over three sets of optimization problems.
  arXiv  Detail & Related papers  (2021-05-24T18:56:18Z)
• Complexity-based speciation and genotype representation for neuroevolution [81.21462458089142]
  This paper introduces a speciation principle for neuroevolution where evolving networks are grouped into species based on the number of hidden neurons. The proposed speciation principle is employed in several techniques designed to promote and preserve diversity within species and in the ecosystem as a whole.
  arXiv  Detail & Related papers  (2020-10-11T06:26:56Z)
• Glushkov's construction for functional subsequential transducers [91.3755431537592]
  Glushkov's construction has many interesting properties and they become even more evident when applied to transducers. Special flavour of regular expressions is introduced, which can be efficiently converted to $epsilon$-free functional subsequential weighted finite state transducers.
  arXiv  Detail & Related papers  (2020-08-05T17:09:58Z)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  We develop a strategy to translate core machine learning architectures into their predictive coding equivalents. Our models perform equivalently to backprop on challenging machine learning benchmarks. Our method raises the potential that standard machine learning algorithms could in principle be directly implemented in neural circuitry.
  arXiv  Detail & Related papers  (2020-06-07T15:35:47Z)
• Obtaining Basic Algebra Formulas with Genetic Programming and Functional Rewriting [0.0]
  We use functional programming rewriting to boost inductive genetic programming. Parents are selected following a tournament selection mechanism and the next population is obtained following a steady-state strategy. We compare the performance of our technique in a set of hard problems (for classical genetic programming)
  arXiv  Detail & Related papers  (2020-05-03T23:32:36Z)
• Semantically-Oriented Mutation Operator in Cartesian Genetic Programming for Evolutionary Circuit Design [0.5414308305392761]
  We propose a semantically-oriented mutation operator (SOMO) suitable for the evolutionary design of combinational circuits. Compared to the common CGP and its variants, the proposed method converges on common Boolean benchmarks substantially faster. The most complex circuits were evolved in less than one hour with a single-thread implementation running on a common CPU.
  arXiv  Detail & Related papers  (2020-04-23T08:15:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.