Grammar-guided genetic programming

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