Grammar-guided genetic programming

chevron-icon
Back
project-presentation-img
Robert Haas
Project Owner

Grammar-guided genetic programming

Funding Awarded

$40,000 USD

Expert Review
Star Filled Image Star Filled Image Star Filled Image Star Filled Image Star Filled Image 0
Community
Star Filled Image Star Filled Image Star Filled Image Star Filled Image Star Filled Image 0 (0)

Status

  • Overall Status

    🛠️ In Progress

  • Funding Transfered

    $24,000 USD

  • Max Funding Amount

    $40,000 USD

Funding Schedule

View Milestones
Milestone Release 1
$5,000 USD Transfer Complete TBD
Milestone Release 2
$5,000 USD Transfer Complete TBD
Milestone Release 3
$14,000 USD Transfer Complete TBD
Milestone Release 4
$8,000 USD Pending TBD
Milestone Release 5
$8,000 USD Pending TBD

Status Reports

Mar. 23, 2023

Status
😀 Excellent
Summary

The main part of milestone 3 is finished: Implementing a Python package for thoroughly benchmarking G3P methods according to different guidelines in GP literature. It covers a comprehensive and diverse set of search spaces (=grammars) and search goals (=objective functions): 105 symbolic regression problems, 8 boolean function approximation problems, 21 classification problems, 6 synthetic problems, 54 program synthesis problems.

Full Report

Jan. 22, 2023

Status
🙂 Pretty good
Summary

Good, currently approaching milestone 3/4.

Full Report

Dec. 5, 2022

Status
😀 Excellent
Summary

Milestone 2 is about to be concluded: Release of five G3P methods in form of a package on PyPI and GitHub. Milestone 3 is under active work: Collecting relevant literature about benchmarking in GP, reading it closely and drawing conclusions of what benchmarks to incorporate and how to statistically evaluate them.

Full Report

Oct. 22, 2022

Status
🧐 Fair, but could have been better
Summary

I took some time out for vacation and due to personal health issues, but managed to make good progress on milestone 2 of this project.

Full Report

Aug. 29, 2022

Status
🙂 Pretty good
Summary

Milestone 1: Release of v0.1.0 on GitHub with first twornmethods (CFG-GP, GE). The software is available at https://github.com/robert-haas/alogos with a permissive open source license.

Full Report

Video Updates

Robert Haas – Team meeting 6

16 March 2023

Robert Haas – kickoff presentation – GGGP

15 March 2023

Projects Links

GGGP

Description

Grammar-guided genetic programming Evolve programs in any context-free language for any quantitative goal

Project AI Services

No Service Available

Overview

Grammar-guided genetic programming (GGGP, G3P) is a set of advanced optimization methods from the field of evolutionary computation (EC). These methods allow to search for optimal programs in any formal language that can be defined with a context-free grammar. This includes most general-purpose programming languages (e.g. Python, C++, Rust, OpenCog's Atomese), domain-specific languages (e.g. HTML, JSON, protobuf) and user-written mini-languages (e.g. geometric shape configurations).

The aim of this proposal is to implement five different G3P algorithms (CFG-GP, GE, piGE, DSGE, WHGE) that represent the state-of-the-art, integrate them in a single open-source software package, create a collection of benchmark problems from literature to compare them rigorously, and then bring the best performing algorithm as general-purpose optimization service to the SingularityNET platform. A proof-of-concept prototype with two algorithms (CFG-GP, GE) has already been created and successfully applied to solve example problems from different domains, which is shown in the attached supplementary material to demonstrate the feasibility of the project. The overall utility of these methods comes from the fact that many real-world tasks can be formulated as optimization problems and G3P methods can tackle a wide range of them. This flexibility comes from the ease of defining a search space with a grammar and because there is no need to implement new solution representations or search operators for each new domain.

Proposal Description

Compnay Name

Antecedens e.U.

Problem Description

Many tasks that arise in theory and practice can be expressed as optimization problems. For example, deciding which groceries to buy with a given budget, finding the shortest route between two places, or distributing funds between projects to achieve greatest impact are three practical optimization problems. Optimization simply means to search for the best solution out of many possible ones. To do so algorithmically, you need to precisely define

  1. where you search (=search space, the set of all candidate solutions),
  2. what you search (=objective function, a way to quantify how good each solution is with a fitness value), and
  3. how you search (=optimization method, an algorithm that can traverse the search space to find an optimal solution).

There are a lot of different search spaces. As a consequence, optimization methods can be classified by how flexible and efficient they are:

  • For some important search spaces, such as Euclidean or permutation spaces, there exist domain-specific optimization methods that can navigate very efficiently in exactly the space they were designed for, but not in any other.
  • In contrast, there are also general-purpose optimization methods, often inspired by nature and referred to as metaheuristics (e.g. simulated annealing, evolutionary algorithms, particle swarm optimization). They work quite well on a wide range of search spaces, but at the cost that they are often not as efficient as domain-specific algorithms and can not give any guarantee of always finding the best solution.

In practice, whenever you encounter a new optimization problem, it is useful to have a general method at hand to easily find a sufficiently good solution in little time, without first having to look for a specialized solver or even implementing one. Further, it is advantageous if that general method allows to define the search space of interest in a simple and precise way, because it is better to look for a solution in a confined space than in an unnecessarily large one, e.g. in a reasonable range of numbers instead of the set of all integers. The question is, which method meets those requirements best?

Solution Description

Evolutionary algorithms (EA) are general optimization methods that use ideas from natural evolution, such as random variation and natural selection, and have been used to find very good solutions in a wide range of hard optimization problems in areas such as planning, routing, design, control, and many others. The field that studies these algorithms is called evolutionary computation (EC). Historically it came from four separate branches called Genetic Algorithms (GA), Evolutionary Strategies (ES), Evolutionary Programming (EP) and Genetic Programming (GP). While genetic algorithms are best known, genetic programming is perhaps the most interesting one, because it deals with the evolution of computer programs and can emulate the other approaches.

This proposal is about grammar-guided genetic programming (GGGP), which is an advanced form of genetic programming that is highly flexible, because it uses context-free grammars (CFG) to define the search space. This means the set of all candidate solutions is the set of all valid strings defined by that grammar, or in other words, the grammar's language.

These methods allow to easily search for the best program or expression in general-purpose programming languages (Python, C++, Rust, OpenCog's Atomese), domain-specific languages (HTML, JSON, protobuf), or user-defined sub-languages (e.g. number literals in Rust) and mini-languages (e.g. a mixed parameter space for hyperparameter optimization). Given this flexibility, having such a method available on SingularityNET opens up an abundance of use cases, all of which can be built on top of it, either by calling the service on the platform, or by using the package internally. A working prototype was already created and used successfully to solve some simple and a few advanced use cases, which is shown in the attached supplementary material. The overall goal is to develop this prototype into an open-source package with proper testing and documentation, then benchmark the different methods and finally provide the most performant one as general-purpose optimization service on SingularityNET. Specific use cases can then be built on top of it by any developer who has basic familiarity with context-free grammars and optimization problems, two well-known topics in computer science and software design.

Competitive Landscape

Research literature mentions two problems of genetic programming that are addressed by this project and which differentiates it from other solutions: 1. There is an accessibility problem: Methods are currently hard to use and compare. 2. There is a benchmarking problem: Methods are often tested on too simple examples from a small number of domains.

Marketing & Competition

Visibility for the created package and service will be generated at locations where developers and researchers usually seek for implementations of genetic programming and its modern variants, such as

  • Q&A sites: StackExchange, Reddit, Quora
  • Hosting sites: GitHub, PyPI
  • Software listings: GitHub collections, reference sections of related Wikipedia entries

Additional exposure by SingularityNET's channels is also highly appreciated.

Needed Resources

This project is self-sufficient in the sense that I bring the required skills to meet the described milestones without external help. However, I'd appreciate any feedback and discussions that allow me to implement the project in higher quality, especially when it comes to the goal of making the methods as easily accessible as possible to others. This includes for example the design of intuitive user-facing APIs and service parameters, as well as writing well-readable documentation and service descriptions, all of which profits from direct user feedback.

 

Long Description

Evolutionary algorithms (EA) are general optimization methods that use ideas from natural evolution, such as random variation and natural selection, and have been used to find very good solutions in a wide range of hard optimization problems in areas such as planning, routing, design, control, and many others. The field that studies these algorithms is called evolutionary computation (EC). Historically it came from four separate branches called Genetic Algorithms (GA), Evolutionary Strategies (ES), Evolutionary Programming (EP) and Genetic Programming (GP). While genetic algorithms are best known, genetic programming is perhaps the most interesting one, because it deals with the evolution of computer programs and can emulate the other approaches.

This proposal is about grammar-guided genetic programming (GGGP), which is an advanced form of genetic programming that is highly flexible, because it uses context-free grammars (CFG) to define the search space. This means the set of all candidate solutions is the set of all valid strings defined by that grammar, or in other words, the grammar's language.

These methods allow to easily search for the best program or expression in general-purpose programming languages (Python, C++, Rust, OpenCog's Atomese), domain-specific languages (HTML, JSON, protobuf), or user-defined sub-languages (e.g. number literals in Rust) and mini-languages (e.g. a mixed parameter space for hyperparameter optimization). Given this flexibility, having such a method available on SingularityNET opens up an abundance of use cases, all of which can be built on top of it, either by calling the service on the platform, or by using the package internally. A working prototype was already created and used successfully to solve some simple and a few advanced use cases, which is shown in the attached supplementary material. The overall goal is to develop this prototype into an open-source package with proper testing and documentation, then benchmark the different methods and finally provide the most performant one as general-purpose optimization service on SingularityNET. Specific use cases can then be built on top of it by any developer who has basic familiarity with context-free grammars and optimization problems, two well-known topics in computer science and software design.

AI Services

Proposal Video

Placeholder for Spotlight Day Pitch-presentations. Video's will be added by the DF team when available.

  • Total Milestones

    5

  • Total Budget

    $40,000 USD

  • Last Updated

    11 Mar 2024

Milestone 1 - Project start

Status
😀 Completed
Description

Contract signed

Deliverables

Budget

$5,000 USD

Link URL

Milestone 2 - Initialization phase

Status
😀 Completed
Description

Release of v0.1.0 on GitHub with first two methods (CFG-GP, GE).

Deliverables

Budget

$5,000 USD

Link URL

Milestone 3 - Main development phase

Status
😀 Completed
Description

Release of v0.2.0 on GitHub and PyPI with all five methods and test suite.

Deliverables

Budget

$14,000 USD

Link URL

Milestone 4 - Benchmarking phase

Status
🧐 In Progress
Description

Release of v0.3.0 on GitHub and PyPI with benchmark collection and statistical evaluation methods.

Deliverables

Budget

$8,000 USD

Link URL

Milestone 5 - Documentation and integration phase

Status
😐 Not Started
Description

Release of v1.0.0 on GitHub and PyPI with frozen API. Documentation website. AI Service and its donation to SNET.

Deliverables

Budget

$8,000 USD

Link URL

Join the Discussion (0)

Reviews & Rating

New reviews and ratings are disabled for Awarded Projects

Sort by

0 ratings

Summary

Overall Community

0

from 0 reviews
  • 5
    0
  • 4
    0
  • 3
    0
  • 2
    0
  • 1
    0

Feasibility

0

from 0 reviews

Viability

0

from 0 reviews

Desirabilty

0

from 0 reviews

Usefulness

0

from 0 reviews