Genetic operations for permutation genes.
A permutation gene is a named list with at least the following elements:
$gene1: The gene must be a permutation vector.
$fit: The fitness value of the gene
(for EvalGeneDet and EvalGeneU) or
the mean fitness (for stochastic functions
evaluated with EvalGeneStoch).
$evaluated: Boolean. Has the gene been evaluated?
$evalFail: Boolean. Has the evaluation of the gene failed?
A problem environment penv for the TSP must provide:
$name(): Returns the name of the problem environment.
$genelength(): The number of integers of a permutation.
Used in InitGene.
$dist(): The distance matrix of the TSP.
$cities(): A list of city names or 1:numberOfCities.
$f(permutation, gene, lF):
Returns the fitness of the permutation (the length of a tour).
$solution(): The minimal tour length (if known).
$path(): An optimal TSP tour.
$show(permutation): Prints the tour with the distances
and the cumulative distances between the cities.
TSP Heuristics:
$greedy(startposition, k):
Computes a greedy tour of length k.
$kBestgreedy(k):
Computes the best greedy tour of length k.
$rnd2Opt(permutation, maxTries):
Generate a new permutation by a random 2-change.
maxTries is the maximal number of trials
to find a better permutation.
$rnd2Opt either returns
a better permutation or, if no better permutation can be found
in maxTries attempts, the original permutation.
$LinKernighan(permutation, maxTries):
Returns a permutation generated by a random sequence of 2-changes
with improving performance. The optimality criterion of the
k Lin-Kernighan heuristics is replaced by the necessity of
finding a sequence of random 2-changes with strictly
increasing performance.
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 configuration lF.
The local constants of a mutation function determine the behavior of the function.
| Constant | Default | Used in |
lF$BitMutationRate1() | 0.005 | xegaPermMutateGeneOrderBased |
lF$Lambda() | 0.05 | xegaPermMutateGenekInversion |
| xegaPermMutateGenekGreedy | ||
| xegaPermMutateGeneBestGreedy | ||
lF$max2Opt() | 100 | xegaPermMutateGene2Opt |
| xegaPermMutateGenekOptLK |
The signatures of the abstract interface to the 2 families of crossover functions are:
ListOfTwoGenes<-Crossover2(gene1, gene2, lF)
newGene<-Crossover(gene1, gene2, lF)
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/xegaPermGene>
From CRAN by install.packages('xegaPermGene')
Andreas Geyer-Schulz
Permutation genes are a representation of a tour of a Traveling Salesman Problem (TSP).
For permutation genes, the xegaPermGene package provides
Gene initiatilization.
Decoding of parameters.
Mutation functions as well as a function factory for configuration.
Crossover functions as well as a function factory for configuration.
Useful links: