alogos

Welcome! This is the documentation for alogos, an open-source Python 3.6+ package for solving optimization problems with grammar-guided genetic programming.

Animation of an optimization example

Example: Evolution of a program that draws 150 semi-transparent triangles to approximate an image.

What is this project about?

The name alogos is an acronym for “a library of grammatical optimization systems”.

  • “Optimization” means to search for the best item in a set of candidates. This set is also known as the search space and it can be explored by various search methods in order to find a good or optimal element in it. Some methods can be applied to a wide range of optimization problems but do not come with a guarantee to find the global optimum. These methods are called metaheuristics in contrast to problem-specific heuristics or exact algorithms, which for many problems are not available or not feasible with limited time or computational resources. A well-known example of a metaheuristic is an evolutionary algorithm and this package provides a specialized implementation of it.

  • “Best item” implies that the user needs to provide a way to rank the candidates from best to worst. This is usually done by defining an objective function, which gets a candidate as input and needs to return a numerical value as output. This value represents a quality or fitness score for each candidate, which makes them pairwise comparable and thereby induces a weak ordering on them. Additionally, the user must define whether the search should find an item with maximum or minimum value.

  • “Grammatical” means that a context-free grammar is used to define the search space. A grammar is a mathematical device frequently used in computer science to define a formal language such as JSON, Python, Rust but also much more basic ones. A language is just a set of strings and therefore each item of the search space can be a simple string such as “Hello world!” or a complex string such as a multi-line program.

  • To summarize the previous points: This package provides several systems to search for the best string in a grammar’s language, where best means the item with highest or lowest value assigned by an objective function.

The name alogos also stands for the greek word άλογος, which means “irrational” or “without reason”. This property characterizes the stochastic search algorithms provided in this package well, yet does not hinder them from finding good solutions to hard optimization problems in limited time. An interesting open question is whether reasoning capabilities could be added to make the search process more effective without impacting its efficiency too much.

Which goals are pursued by this project?

This project revolves around a particular family of optimization algorithms that are mainly studied in the field of evolutionary computation (EC) and can be referred to with the umbrella term Grammar-Guided Genetic Programming (GGGP, G3P). This package currently provides implementations of five different G3P methods:

  1. Context-Free Grammar Genetic Programming (CFG-GP)

  2. Grammatical Evolution (GE)

  3. Position-independent Grammatical Evolution (piGE)

  4. Dynamic Structured Grammatical Evolution (DSGE)

  5. Weighted Hierarchical Grammatical Evolution (WHGE)

This project tries to achieve two main goals:

  1. Provide a modular implementation of several G3P methods to make them easier to study, compare and extend.

  2. Democratize the access to these methods, so they can be used more frequently and by a wider audience.

How can you get started?

If you want to use this package, the following steps should help you to get results in a short time:

  1. The Installation Guide describes how you can install the package and its optional dependencies.

  2. The Quickstart Example is a short piece of code you can run immediately after the installation to see if it worked and to get a first impression of the package.

  3. The Getting Started Tutorial explains the main concepts required to define and solve your own optimization problems, such as defining a grammar and objective function as well as applying an evolutionary algorithm to it.

  4. The Code Examples contain solutions to optimization problems from different domains. They illustrate the generality and flexibility of the methods provided in this package. You can use the examples as templates or recipes that can be adapted to tackle similar problems.

  5. The API Documentation contains a comprehensive description of all user-facing functionality available in this package, so you can see the full range of available options.

Where can everything be found?

The Package References page contains a collection of links to all parts of this project, including the source code, distributed code and documentation.

Who is involved in this project?

  • The design, implementation and documentation of this package was done by Robert Haas.

  • Several research groups in the field of evolutionary computation invented the original G3P algorithms that are reproduced here. For a list of involved persons, please have a look at the authors of the research articles referenced above and in the API Documentation.

  • Financial support to realize this project was granted by the Deep Funding initiative of SingularityNET. If you are interested in using or providing ML/AI algorithms, you may want to have a look at SingularityNET’s decentralized marketplace of AI services.

Table of contents