# Selection

**Selection** is a genetic operator used in EAs for selecting potentially useful solutions from a population for later breeding. The EAs are stochastic search methods using the concepts of Mendelian genetics and Darwinian evolution. According to Darwin's evolution theory the best ones should survive and create new offspring. There are many methods how to select the best individuals, for example roulette wheel selection, Boltzman selection, tournament selection, rank selection, steady state selection and some others.

## Selection Interface

All selection algorithms have following call interface `selection(fitness, N)`

where `fitness`

is the vector of population fitness values, of size $M$, and $N$ is the number of selected individuals. The selection function returns a vector of integer indexes of selected individuals, of size $N$ with indexes in range $[1,M]$.

**Note:** Some of the selection algorithms implemented as function closures, in order to provide additional parameters to the specified above selection interface.

## Genetic Algorithm

`Evolutionary.ranklinear`

— Function`ranklinear(sp::Real)`

Returns a rank-based fitness selection function, see Selection Interface, with the selective pressure value `sp`

.

In rank-based fitness selection, the population is sorted according to the objective values. The fitness assigned to each individual depends only on its position in the individuals rank and not on the actual objective value ^{[1]}.

Consider $M$ the number of individuals in the population, $P$ the position of an individual in this population (least fit individual has $P = 1$, the fittest individual $P = M$) and $SP$ the selective pressure. The fitness value for an individual is calculated as:

$Fitness(P) = 2 - SP + \frac{2(SP - 1)(P - 1)}{(M - 1)}$

Linear ranking allows values of selective pressure in [1.0, 2.0].

`Evolutionary.uniformranking`

— Function`uniformranking(μ)`

Returns a (μ, λ)-uniform ranking selection function, see Selection Interface with the best individuals parameter `μ`

.

In uniform ranking, the best $\mu$ individuals are assigned a selection probability of $1/\mu$ while the rest them are discarded ^{[2]}.

`Evolutionary.roulette`

— Function`roulette(fitness)`

Roulette wheel (fitness proportionate, FPS) selection from `fitness`

collection.

In roulette selection, the fitness level is used to associate a probability of selection with each individual. If $f_i$ is the fitness of individual $i$ in the population, its probability of being selected is $p_i = \frac{f_i}{\Sigma_{j=1}^{M} f_j}$, where $M$ is the number of individuals in the population.

*Note:* Best used in maximization context.

`Evolutionary.rouletteinv`

— Function`rouletteinv(fitness)`

Fitness proportionate selection (FPS) or roulette wheel for inverse `fitness`

values. Best used in minimization to 0.

`Evolutionary.sus`

— Function`sus(fitness, N)`

Stochastic universal sampling (SUS) provides zero bias and minimum spread ^{[3]}. SUS is a development of fitness proportionate selection (FPS). Using a comb-like ruler, SUS starts from a small random number, and chooses the next candidates from the rest of population remaining, not allowing the fittest members to saturate the candidate space. The individuals are mapped to contiguous segments of a line, such that each individual's segment is equal in size to its fitness exactly as in roulette-wheel selection. Here equally spaced pointers are placed over the line as many as there are individuals to be selected.

Consider $N$ the number of individuals to be selected, then the distance between the pointers are $1/N$ and the position of the first pointer is given by a randomly generated number in the range $[0, 1/N]$.

*Note*: Best used in maximization context.

`Evolutionary.susinv`

— Function`susinv(fitness)`

Inverse fitness SUS. Best used in minimization to 0.

`Evolutionary.truncation`

— Function`truncation(fitness, N)`

Truncation selection returns first `N`

of best `fitness`

individuals

`Evolutionary.tournament`

— FunctionTournament selection

## Differential Evolution

`Evolutionary.random`

— Function`random(fitness, N)`

Returns a collection on size `N`

of uniformly selected individuals from the population.

`Evolutionary.permutation`

— Function`permutation(fitness, N)`

Returns a permutation on size `N`

of the individuals from the population.

`Evolutionary.randomoffset`

— Function`randomoffset(fitness, N)`

Returns a cycle selection on size `N`

from an arbitrary position.

`Evolutionary.best`

— Function`best(fitness, N)`

Returns a collection of best individuals of size `N`

.

## References

- 1Baker J.E., Adaptive selection methods for genetic algorithms, In Proceedings of International Conference on Genetic Algorithms and Their Applications, pp. 100-111, 1985.
- 2Schwefel H.P., Evolution and Optimum Seeking, Wiley, New York, 1995.
- 3Baker, J. E., Reducing Bias and Inefficiency in the Selection Algorithm. In [ICGA2], pp. 14-21, 1987.