gena.mating: Mating

In gena: Genetic Algorithm and Particle Swarm Optimization

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}≤ft(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}}{∑\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 τ the vector of parameters used by the algorithm. Note that τ corresponds to par. The algorithm determines a particular form of the w_{i}≤ft(f_{i}\right) function which in turn determines p_{i}≤ft(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}=≤ft(\frac{r_{i}}{n_{population}}\right)^{τ_{1}}

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

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

w_{i}=≤ft(f_{i} - \min≤ft(f_{1},...,f_{n_{population}}\right) + τ_{1}\right)^{τ_{2}}

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

If method = "tournament" then τ_{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)

gena documentation built on Aug. 15, 2022, 9:08 a.m.