xegaGaGene | R Documentation |
Genetic operations for binary coded genetic algorithms.
For an introduction to this class of algorithms, see Goldberg, D. (1989).
For binary-coded genes, the xegaGaGene
package provides
Gene initiatilization.
Decoding of parameters as well as a function factory for configuration.
Mutation functions as well as a function factory for configuration.
Crossover functions as well as a function factory for configuration. We provide two families of crossover functions:
Crossover functions with two kids: Crossover preserves the genetic information in the gene pool.
Crossover functions with one kid: These functions allow the construction of gene evaluation pipelines. One advantage of this is a simple control structure at the population level.
Constructors for abstract genetic operator pipelines embedded in function closures.
Gene replication functions as well as a function factory for
configuration. The replication functions implement control flows
for sequences of gene operations. For xegaReplicateGene
,
an acceptance step has been added. Simulated annealing algorithms
can be configured e.g. by configuring uniform random selection combined
with a Metropolis Acceptance Rule and a suitable cooling schedule.
Constructors for abstract genetic operator pipelines embedded in function closures.
Gene replication functions which compile function closures with genetic operator pipelines.
A binary gene is a named list:
$gene1 the gene must be a binary vector.
$fit the fitness value of the gene (for EvalGeneDet and EvalGeneU) or the mean fitness (for stochastic functions evaluated with EvalGeneStoch).
$evaluated has the gene been evaluated?
$evalFail has the evaluation of the gene failed?
$var the cumulative variance of the fitness of all evaluations of a gene. (For stochastic functions)
$sigma the standard deviation of the fitness of all evaluations of a gene. (For stochastic functions)
$obs the number of evaluations of a gene. (For stochastic functions)
A problem environment penv
must provide:
$f(parameters, gene, lF)
:
Function with a real parameter vector as first argument
which returns a gene
with evaluated fitness.
$genelength(): The number of bits of the binary-coded
real parameter vector. Used in InitGene
.
$bitlength(): A vector specifying the number of bits
used for coding each real parameter.
If penv$bitlength()[1]
is 20
,
then parameters[1]
is coded by 20 bits.
Used in GeneMap
.
$lb(): The lower bound vector of each parameter.
Used in GeneMap
.
$ub(): The upper bound vector of each parameter.
Used in GeneMap
.
Each mutation function has the following function signature:
newGene<-Mutate(gene, lF)
All local parameters of the mutation function configured are expected in the local function list lF.
The local constants of a mutation function determine
the behavior of the function. The default values in the
table below are set in lFxegaGaGene
.
Constant | Default | Used in |
lF$BitMutationRate1() | 0.01 | xegaGaMutateGene() |
xegaGaIVAdaptiveMutateGene() | ||
lF$BitMutationRate2() | 0.20 | xegaGaIVAdaptiveMutateGene() |
lF$CutoffFit() | 0.5 | xegaGaIVADaptiveMutateGene() |
The signatures of the abstract interface to the 2 families of crossover functions are:
ListOfTwoGenes<-Crossover2(gene1, gene2, lF)
ListOfOneGene<-Crossover(gene1, gene2, lF)
All local parameters of the crossover function configured are expected in the local function list lF.
The local constants of a crossover function determine the the behavior of the function.
Constant | Default | Used in |
lF$UCrossSwap() | 0.2 | UPCross2Gene() |
UPCrossGene() | ||
Compiling abstract gene operator pipelines based on random experiments generates function closures which when evaluated produce an evaluated gene. With pipelines, the gene life cycle looks like this:
evaluated gene -> replicate -> replicated gene -> evaluate -> evaluated gene
where evaluated genes are data structures (named lists) and replicated genes are function closures (genetic operator pipelines bound with selected genes).
Pipelines lead to the following separation of work between the replication and the evaluation phase of the genetic algorithm
The replication phase of the genetic algorithm consists of compiling function closures.
The evaluation phase consists of the actual execution
of the complete genetic operator pipeline:
evaluate(accept(mutate(crossover(gene1, gene2))))
.
For sequential execution models, pipelines may lead to small performance gains, because the compilation phase produces minimal genetic operator pipelines.
For parallel or distributed execution models, the replication phase is still executed sequentially whereas the evaluation of the population of function closures is done in parallel. The effect is that most of the computational work of the genetic algorithm is shifted to the evaluation phase and thus executed in parallel.
The pipeline mechanism implemented is completely abstract and independent of the actual gene representation. However, algorithms like e.g. differential evolution which use more than two genes may need replication functions which compile appropriate function closures.
The signatures of the abstract interface to the 4 gene replication functions are:
ListOfTwoGenes<-Replicate2Gene(pop, fit, lF)
ListOfOneGene<-ReplicateGene(pop, fit, lF)
ListOfFunctionClosures<-Replicate2GenePipeline(pop, fit, lF)
ListOfFunctionClosures<-ReplicateGenePipeline(pop, fit, lF)
Configuration for ReplicateGene (1 Kid, Default).
Function | Default | Configured By |
lF$SelectGene() | SelectSUS() | SelectGeneFactory() |
lF$SelectMate() | SelectSUS() | SelectGeneFactory() |
lF$CrossGene() | CrossGene() | xegaGaCrossoverFactory() |
lF$MutateGene() | MutateGene() | xegaGaMutationFactory() |
lF$Accept() | AcceptNewGene() | AcceptFactory() |
Configuration for Replicate2Gene (2 Kids).
Function | Default | Configured By |
lF$SelectGene() | SelectSUS() | SelectGeneFactory() |
lF$SelectMate() | SelectSUS() | SelectGeneFactory() |
lF$CrossGene() | Cross2Gene() | xegaGaCrossoverFactory() |
lF$MutateGene() | MutateGene() | xegaGaMutationFactory() |
Global Constants.
Global constants specify the probability that a mutation or crossover operator is applied to a gene. In the xega-architecture, these rates can be configured to be adaptive.
Constant | Default | Used in |
lF$MutationRate() | 1.0 (static) | xegaGaReplicateGene() |
xegaGaReplicate2Gene() | ||
lF$CrossRate() | 0.2 (static) | xegaGaReplicateGene() |
xegaGaReplicate2Gene() | ||
Local Constants.
Constant | Default | Used in |
lF$BitMutationRate1() | 0.01 | xegaGaMutateGene() |
xegaGaIVAdaptiveMutateGene() | ||
lF$BitMutationRate2() | 0.20 | xegaGaIVAdaptiveMutateGene() |
lF$CutoffFit() | 0.5 | xegaGaIVADaptiveMutateGene() |
lF$UCrossSwap() | 0.2 | xegaGaUPCross2Gene() |
xegaGaUPCrossGene() | ||
In the xega-architecture, these rates can be configured to be adaptive.
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
population statistics dependent adaptive mechanisms and parallelization.
The gene layer is split into a representation-independent and a representation-dependent part:
The representation indendent part (package xegaSelectGene
)
is responsible for variants of selection operators, evaluation
strategies for genes, as well as profiling and timing capabilities.
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 as e.g.
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
is an abstract data type for derivation trees.
(c) 2023 Andreas Geyer-Schulz
MIT
<https://github.com/ageyerschulz/xegaGaGene>
From CRAN by install.packages('xegaGaGene')
Andreas Geyer-Schulz
Goldberg, David E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading. (ISBN:0-201-15767-5)
Useful links:
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.