Mating (selection) method (algorithm) to be used in the genetic algorithm.
gena.mating(
population,
fitness,
parents.n,
method = "rank",
par = NULL,
self = FALSE,
iter = NULL
)The function returns a list with the following elements:
parents - matrix which rows are parents. The number of
rows of this matrix equals to parents.n while the number of columns
is ncol(population).
fitness - vector which i-th element is the fitness of the
i-th parent.
ind - vector which i-th element is the index of i-th
parent in population so $parents[i, ] equals to
population[ind[i], ].
numeric matrix which rows are chromosomes i.e. vectors of parameters values.
numeric vector which i-th element is the value of
fn at point population[i, ].
even positive integer representing the number of parents.
mating method to be used for selection of parents.
additional parameters to be passed depending on the method.
logical; if TRUE then chromosome may mate itself.
Otherwise mating is allowed only between different chromosomes.
iteration number of the genetic algorithm.
Denote population by \(C\) which i-th row
population[i, ] is a chromosome \(c_{i}\) i.e. the vector of
parameter values of the function being optimized \(f(.)\) that is
provided via fn argument of gena.
The elements of chromosome \(c_{ij}\) are genes representing parameters
values. Argument fitness is a vector of function values at
corresponding chromosomes i.e. fitness[i] corresponds to
\(f_{i}=f(c_{i})\). Total number of chromosomes in population
\(n_{population}\) equals to nrow(population).
Mating algorithm determines selection of chromosomes that will become parents.
During mating each iteration one of chromosomes become a parent until
there are \(n_{parents}\) (i.e. parents.n) parents selected.
Each chromosome may become a parent multiple times or not become a
parent at all.
Denote by \(c^{s}_{i}\) the \(i\)-th of selected parents. Parents
\(c^{s}_{i}\) and \(c^{s}_{i + 1}\) form a pair that will further
produce a child (offspring), where \(i\) is odd.
If self = FALSE then for each pair of parents
\((c_{i}^s, c_{i+1}^s)\) it is insured that
\(c^{s}_{i} \ne c^{s}_{i + 1}\) except the case when there are several
identical chromosomes in population. However self is ignored
if method is "tournament", so in this case self-mating
is always possible.
Denote by \(p_{i}\) the probability of a chromosome to become a parent. Remind that each chromosome may become a parent multiple times. Probability \(p_{i}\left(f_{i}\right)\) is a function of fitness \(f_{i}\). Usually this function is non-decreasing so more fitted chromosomes have higher probability of becoming a parent. There is also an intermediate value \(w_{i}\) called weight such that: $$p_{i}=\frac{w_{i}}{\sum\limits_{j=1}^{n_{population}}w_{j}}$$ Therefore all weights \(w_{i}\) are proportional to corresponding probabilities \(p_{i}\) by the same factor (sum of weights).
Argument method determines particular mating algorithm to be applied.
Denote by \(\tau\) the vector of parameters used by the algorithm.
Note that \(\tau\) corresponds to par. The algorithm determines
a particular form of the \(w_{i}\left(f_{i}\right)\) function which
in turn determines \(p_{i}\left(f_{i}\right)\).
If method = "constant" then all weights and probabilities are equal:
$$w_{i}=1 => p_{i}=\frac{1}{n_{population}}$$
If method = "rank" then each chromosome receives a rank \(r_{i}\)
based on the fitness \(f_{i}\) value. So if j-th chromosome is the
fittest one and k-th chromosome has the lowest fitness value then
\(r_{j}=n_{population}\) and \(r_{k}=1\). The relationship
between weight \(w_{i}\) and rank \(r_{i}\) is as follows:
$$w_{i}=\left(\frac{r_{i}}{n_{population}}\right)^{\tau_{1}}$$
The greater value of \(\tau_{1}\) the greater portion of probability will
be delivered to more fitted chromosomes.
Default value is \(\tau_{1} = 0.5\) so par = 0.5.
If method = "fitness" then weights are calculated as follows:
$$w_{i}=\left(f_{i} -
\min\left(f_{1},...,f_{n_{population}}\right) +
\tau_{1}\right)^{\tau_{2}}$$
By default \(\tau_{1}=10\) and \(\tau_{2}=0.5\) i.e.
par = c(10, 0.5). There is a restriction \(\tau_{1}\geq0\)
insuring that expression in brackets is non-negative.
If method = "tournament" then \(\tau_{1}\) (i.e. par)
chromosomes will be randomly selected with equal probabilities and without
replacement. Then the chromosome with the highest fitness
(among these selected chromosomes) value will become a parent.
It is possible to provide representation of this algorithm via
probabilities \(p_{i}\) but the formulas are numerically unstable.
By default par = min(5, ceiling(parents.n * 0.1)).
Validation and default values assignment for par is performed inside
gena function not in gena.mating.
It allows to perform validation a single time instead of repeating it
each iteration of genetic algorithm.
For more information on mating (selection) algorithms please see Shukla et. al. (2015).
A. Shukla, H. Pandey, D. Mehrotra (2015). Comparative review of selection techniques in genetic algorithm. 2015 International Conference on Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE), 515-519, <doi:10.1109/ABLAZE.2015.7154916>.
# Consider the following fitness function
fn <- function(x)
{
val <- x[1] * x[2] - x[1] ^ 2 - x[2] ^ 2
}
# Randomly initialize the population
set.seed(123)
pop.nulation <- 10
population <- gena.population(pop.n = pop.nulation,
lower = c(-5, -5),
upper = c(5, 5))
# Calculate fitness of each chromosome
fitness <- rep(NA, pop.nulation)
for(i in 1:pop.nulation)
{
fitness[i] <- fn(population[i, ])
}
# Perform mating to select parents
parents <- gena.mating(population = population,
fitness = fitness,
parents.n = pop.nulation,
method = "rank",
par = 0.8)
print(parents)
Run the code above in your browser using DataLab