Solving Novel Program Synthesis Problems with Genetic Programming using Parametric Polymorphism

• URL: http://arxiv.org/abs/2306.04839v1
• Date: Thu, 8 Jun 2023 00:10:07 GMT
• Title: Solving Novel Program Synthesis Problems with Genetic Programming using Parametric Polymorphism
• Authors: Edward Pantridge, Thomas Helmuth
• Abstract summary: We show that Code-building Genetic Programming (CBGP) compiles type-safe programs from linear genomes using stack-based compilation and a formal type system. CBGP is able to solve problems with all of these properties, where every other GP system that we know of has restrictions that make it unable to even consider problems with these properties.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Contemporary genetic programming (GP) systems for general program synthesis have been primarily concerned with evolving programs that can manipulate values from a standard set of primitive data types and simple indexed data structures. In contrast, human programmers do not limit themselves to a small finite set of data types and use polymorphism to express an unbounded number of types including nested data structures, product types, and generic functions. Code-building Genetic Programming (CBGP) is a recently introduced method that compiles type-safe programs from linear genomes using stack-based compilation and a formal type system. Although prior work with CBGP has shown initial demonstrations of polymorphism inside evolved programs, we have provided a deeper exploration of these capabilities through the evolution of programs which make use of generic data types such as key-value maps, tuples, and sets, as well as higher order functions and functions with polymorphic type signatures. In our experiments, CBGP is able to solve problems with all of these properties, where every other GP system that we know of has restrictions that make it unable to even consider problems with these properties. This demonstration provides a significant step towards fully aligning the expressiveness of GP to real world programming.

Related papers

• Compositional Program Generation for Few-Shot Systematic Generalization [59.57656559816271]
  This study on a neuro-symbolic architecture called the Compositional Program Generator (CPG) CPG has three key features: textitmodularity, textitcomposition, and textitabstraction, in the form of grammar rules. It perfect achieves generalization on both the SCAN and COGS benchmarks using just 14 examples for SCAN and 22 examples for COGS.
  arXiv  Detail & Related papers  (2023-09-28T14:33:20Z)
• HOTGP -- Higher-Order Typed Genetic Programming [0.0]
  HOTGP is a new genetic algorithm that synthesizes pure, typed, and functional programs. The grammar is based on Haskell's standard base library.
  arXiv  Detail & Related papers  (2023-04-06T16:23:34Z)
• Weighted Ensembles for Active Learning with Adaptivity [60.84896785303314]
  This paper presents an ensemble of GP models with weights adapted to the labeled data collected incrementally. Building on this novel EGP model, a suite of acquisition functions emerges based on the uncertainty and disagreement rules. An adaptively weighted ensemble of EGP-based acquisition functions is also introduced to further robustify performance.
  arXiv  Detail & Related papers  (2022-06-10T11:48:49Z)
• Functional Code Building Genetic Programming [0.0]
  Code Building Genetic Programming (CBGP) is a recently introduced GP method for general program synthesis. We show that a functional programming language and a Hindley-Milner type system can be used to evolve type-safe programs.
  arXiv  Detail & Related papers  (2022-06-09T15:22:33Z)
• Equivariant Graph Mechanics Networks with Constraints [83.38709956935095]
  We propose Graph Mechanics Network (GMN) which is efficient, equivariant and constraint-aware. GMN represents, by generalized coordinates, the forward kinematics information (positions and velocities) of a structural object. Extensive experiments support the advantages of GMN compared to the state-of-the-art GNNs in terms of prediction accuracy, constraint satisfaction and data efficiency.
  arXiv  Detail & Related papers  (2022-03-12T14:22:14Z)
• Incremental Ensemble Gaussian Processes [53.3291389385672]
  We propose an incremental ensemble (IE-) GP framework, where an EGP meta-learner employs an it ensemble of GP learners, each having a unique kernel belonging to a prescribed kernel dictionary. With each GP expert leveraging the random feature-based approximation to perform online prediction and model update with it scalability, the EGP meta-learner capitalizes on data-adaptive weights to synthesize the per-expert predictions. The novel IE-GP is generalized to accommodate time-varying functions by modeling structured dynamics at the EGP meta-learner and within each GP learner.
  arXiv  Detail & Related papers  (2021-10-13T15:11:25Z)
• Multi-modal Self-supervised Pre-training for Regulatory Genome Across Cell Types [75.65676405302105]
  We propose a simple yet effective approach for pre-training genome data in a multi-modal and self-supervised manner, which we call GeneBERT. We pre-train our model on the ATAC-seq dataset with 17 million genome sequences.
  arXiv  Detail & Related papers  (2021-10-11T12:48:44Z)
• Using Traceless Genetic Programming for Solving Multiobjective Optimization Problems [1.9493449206135294]
  Traceless Genetic Programming (TGP) is a Genetic Programming (GP) variant that is used in cases where the focus is rather the output of the program than the program itself. Two genetic operators are used in conjunction with TGP: crossover and insertion. Numerical experiments show that TGP is able to solve very fast and very well the considered test problems.
  arXiv  Detail & Related papers  (2021-10-07T05:55:55Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• Code Building Genetic Programming [0.0]
  We introduce Code Building Genetic Programming (CBGP) as a framework within which this can be done. CBGP produces a computational graph that can be executed or translated into source code of a host language.
  arXiv  Detail & Related papers  (2020-08-09T04:33:04Z)
• 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)

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.