gena.mating {gena}

Mating

Description

Mating (selection) method (algorithm) to be used in the genetic algorithm.

Usage

gena.mating(
  population,
  fitness,
  parents.n,
  method = "rank",
  par = NULL,
  self = FALSE,
  iter = NULL
)

Arguments

population

numeric matrix which rows are chromosomes i.e. vectors of parameters values.

fitness

numeric vector which i-th element is the value of fn at point population[i, ].

parents.n

even positive integer representing the number of parents.

method

mating method to be used for selection of parents.

par

additional parameters to be passed depending on the method.

self

logical; if TRUE then chromosome may mate itself. Otherwise mating is allowed only between different chromosomes.

iter

iteration number of the genetic algorithm.

Details

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).

Value

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], ].

References

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>.

Examples

# 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)