Fitness proportionate selection, also known as roulette-wheel selection, is a genetic operator

Genetic operator

A genetic operator is an operator used in genetic algorithms to maintain genetic diversity, known as Mutation and to combine existing solutions into others, Crossover...

 used in genetic algorithm

Genetic algorithm

A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...

s for selecting potentially useful solutions for recombination.

In fitness proportionate selection, as in all selection methods, the fitness function

Fitness function

A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims....

 assigns a fitness to possible solutions or chromosome

Chromosome

A chromosome is an organized structure of DNA and protein found in cells. It is a single piece of coiled DNA containing many genes, regulatory elements and other nucleotide sequences. Chromosomes also contain DNA-bound proteins, which serve to package the DNA and control its functions.Chromosomes...

s. This fitness level is used to associate a probability

Probability

Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...

 of selection with each individual chromosome.
If is the fitness of individual in the population, its probability of being selected is , where is the number of individuals in the population.

This could be imagined similar to a Roulette wheel in a casino. Usually a proportion of the wheel is assigned to each of the possible selection based on their fitness value. This could be achieved by dividing the fitness of a selection by the total fitness of all the selections, thereby normalizing them to 1. Then a random selection is made similar to how the roulette wheel is rotated.

While candidate solutions with a higher fitness will be less likely to be eliminated, there is still a chance that they may be. Contrast this with a less sophisticated selection algorithm, such as truncation selection

Truncation selection

Truncation selection is a selection method used in genetic algorithms to select potential candidate solutions for recombination.In truncation selection the candidate solutions are ordered by fitness, and some proportion, p, , of the fittest individuals are selected and reproduced 1/p times...

, which will eliminate a fixed percentage of the weakest candidates. With fitness proportionate selection there is a chance some weaker solutions may survive the selection process; this is an advantage, as though a solution may be weak, it may include some component which could prove useful following the recombination process.

The analogy to a roulette wheel can be envisaged by imagining a roulette wheel in which each candidate solution represents a pocket on the wheel; the size of the pockets are proportionate to the probability of selection of the solution. Selecting N chromosomes from the population is equivalent to playing N games on the roulette wheel, as each candidate is drawn independently.

Other selection techniques, such as stochastic universal sampling

Stochastic universal sampling

Stochastic universal sampling is a technique used in genetic algorithms for selecting potentially useful solutions for recombination. It was introduced by James Baker....

 or tournament selection

Tournament selection

Tournament selection is a method of selecting an individual from a population of individuals in a genetic algorithm. Tournament selection involves running several "tournaments" among a few individuals chosen at random from the population. The winner of each tournament is selected for crossover...

, are often used in practice. This is because they have less stochastic noise, or are fast, easy to implement and have a constant selection pressure [Blickle, 1996].

Note performance gains can be achieved by using a binary search rather than a linear search to find the right pocket.

External links

• C implementation (.tar.gz; see selector.cxx) WBL
• Example on Roulette wheel selection