xegaDerivationTrees {xegaDerivationTrees}

Package xegaDerivationTrees

Description

Derivation Trees

Details

The implementation of a data type for derivation trees.

The derivation tree operations for generating complete random subtrees and for for subtree extraction and insertion are formally introduced in Geyer-Schulz (1997) and used for implementing mutation and crossover operations.

Efficient selection of random subtrees is implemented by building a list of annotated tree nodes by a left-right depth-first tree traversal. For each node, the R-index to access the subtree is built and stored in the node. The R-index element of a node allows subtree extraction and insertion operations with the cost of the R-index operation. In addition, filtering operations the node list by different criteria (min depth, max depth, and non-terminal symbol type) allow the implementation of flexible and configurable crossover and mutation operations.

The Architecture of the xegaX-Packages

The xegaX-packages are a family of R-packages which implement eXtended Evolutionary and Genetic Algorithms (xega). The architecture has 3 layers, namely the user interface layer, the population layer, and the gene layer:

• The user interface layer (package xega) provides a function call interface and configuration support for several algorithms: genetic algorithms (sga), permutation-based genetic algorithms (sgPerm), derivation-free algorithms as e.g. differential evolution (sgde), grammar-based genetic programming (sgp) and grammatical evolution (sge).

• The population layer (package xegaPopulation) contains population-related functionality as well as support for adaptive mechanisms which depend on population statistics. In addition, support for parallel evaluation of genes is implemented here.

• The gene layer is split in a representation-independent and a representation-dependent part:

  1. The representation-indendent part (package xegaSelectGene) is responsible for variants of selection operators, evaluation strategies for genes, as well as profiling and timing capabilities.

  2. The representation-dependent part consists of the following packages:

     • xegaGaGene for binary-coded genetic algorithms.

     • xegaPermGene for permutation-based genetic algorithms.

     • xegaDfGene for derivation-free algorithms. For example, differential evolution.

     • xegaGpGene for grammar-based genetic algorithms.

     • xegaGeGene for grammatical evolution algorithms.

     The packages xegaDerivationTrees and xegaBNF support the last two packages: xegaBNF essentially provides a grammar compiler, and xegaDerivationTrees an abstract data type for derivation trees.

Copyright

(c) 2023 Andreas Geyer-Schulz

License

MIT

URL

<https://github.com/ageyerschulz/xegaDerivationTrees>

Installation

From cran with install.packages("xegaDerivationTrees")

Author(s)

Andreas Geyer-Schulz

References

Geyer-Schulz, Andreas (1997): Fuzzy Rule-Based Expert Systems and Genetic Machine Learning, Physica, Heidelberg. (ISBN:978-3-7908-0830-X)