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

source

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

source

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.

source

Evolutionary.rouletteinv — Function

rouletteinv(fitness)

Fitness proportionate selection (FPS) or roulette wheel for inverse fitness values. Best used in minimization to 0.

source

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.

source

Evolutionary.susinv — Function

susinv(fitness)

Inverse fitness SUS. Best used in minimization to 0.

source

Evolutionary.truncation — Function

truncation(fitness, N)

Truncation selection returns first N of best fitness individuals

source

Evolutionary.tournament — Function

Tournament selection

source

Differential Evolution

Evolutionary.random — Function

random(fitness, N)

Returns a collection on size N of uniformly selected individuals from the population.

source

Evolutionary.permutation — Function

permutation(fitness, N)

Returns a permutation on size N of the individuals from the population.

source

Evolutionary.randomoffset — Function

randomoffset(fitness, N)

Returns a cycle selection on size N from an arbitrary position.

source

Evolutionary.best — Function

best(fitness, N)

Returns a collection of best individuals of size N.

source

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.