xegaDerivationTrees: Package xegaDerivationTrees

xegaDerivationTreesR Documentation

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)

See Also

Useful links:


xegaDerivationTrees documentation built on April 16, 2025, 5:11 p.m.