gena.mating {gena}R Documentation

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 CC which i-th row population[i, ] is a chromosome cic_{i} i.e. the vector of parameter values of the function being optimized f(.)f(.) that is provided via fn argument of gena. The elements of chromosome cijc_{ij} are genes representing parameters values. Argument fitness is a vector of function values at corresponding chromosomes i.e. fitness[i] corresponds to fi=f(ci)f_{i}=f(c_{i}). Total number of chromosomes in population npopulationn_{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 nparentsn_{parents} (i.e. parents.n) parents selected. Each chromosome may become a parent multiple times or not become a parent at all.

Denote by cisc^{s}_{i} the ii-th of selected parents. Parents cisc^{s}_{i} and ci+1sc^{s}_{i + 1} form a pair that will further produce a child (offspring), where ii is odd. If self = FALSE then for each pair of parents (cis,ci+1s)(c_{i}^s, c_{i+1}^s) it is insured that cisci+1sc^{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 pip_{i} the probability of a chromosome to become a parent. Remind that each chromosome may become a parent multiple times. Probability pi(fi)p_{i}\left(f_{i}\right) is a function of fitness fif_{i}. Usually this function is non-decreasing so more fitted chromosomes have higher probability of becoming a parent. There is also an intermediate value wiw_{i} called weight such that:

pi=wij=1npopulationwjp_{i}=\frac{w_{i}}{\sum\limits_{j=1}^{n_{population}}w_{j}}

Therefore all weights wiw_{i} are proportional to corresponding probabilities pip_{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 wi(fi)w_{i}\left(f_{i}\right) function which in turn determines pi(fi)p_{i}\left(f_{i}\right).

If method = "constant" then all weights and probabilities are equal:

wi=1=>pi=1npopulationw_{i}=1 => p_{i}=\frac{1}{n_{population}}

If method = "rank" then each chromosome receives a rank rir_{i} based on the fitness fif_{i} value. So if j-th chromosome is the fittest one and k-th chromosome has the lowest fitness value then rj=npopulationr_{j}=n_{population} and rk=1r_{k}=1. The relationship between weight wiw_{i} and rank rir_{i} is as follows:

wi=(rinpopulation)τ1w_{i}=\left(\frac{r_{i}}{n_{population}}\right)^{\tau_{1}}

The greater value of τ1\tau_{1} the greater portion of probability will be delivered to more fitted chromosomes. Default value is τ1=0.5\tau_{1} = 0.5 so par = 0.5.

If method = "fitness" then weights are calculated as follows:

wi=(fimin(f1,...,fnpopulation)+τ1)τ2w_{i}=\left(f_{i} - \min\left(f_{1},...,f_{n_{population}}\right) + \tau_{1}\right)^{\tau_{2}}

By default τ1=10\tau_{1}=10 and τ2=0.5\tau_{2}=0.5 i.e. par = c(10, 0.5). There is a restriction τ10\tau_{1}\geq0 insuring that expression in brackets is non-negative.

If method = "tournament" then τ1\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 pip_{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:

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)


[Package gena version 1.0.0 Index]