Fitness proportionate selection, also known as roulette wheel selection, is a
genetic operator A genetic operator is an operator used in genetic algorithms to guide the algorithm towards a solution to a given problem. There are three main types of operators (mutation, crossover and selection), which must work in conjunction with one anothe ...
used in
genetic algorithms for selecting potentially useful solutions for recombination.
In fitness proportionate selection, as in all selection methods, the
fitness function {{no footnotes, date=May 2015
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. Fitness functions are used in geneti ...
assigns a fitness to possible solutions or
chromosome
A chromosome is a long DNA molecule with part or all of the genetic material of an organism. In most chromosomes the very long thin DNA fibers are coated with packaging proteins; in eukaryotic cells the most important of these proteins are ...
s. This fitness level is used to associate a
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
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 selections 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 eliminated because their probability of selection is less than 1 (or 100%). Contrast this with a less sophisticated selection algorithm, such as
truncation selection
In animal and plant breeding, truncation selection is a standard method in selective breeding in selecting animals to be bred for the next generation. Animals are ranked by their phenotypic value on some trait such as milk production, and the top p ...
, 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 because even though the probability that the weaker solutions will survive is low, it is not zero which means it is still possible they will survive; this is an advantage, because there is a chance that even weak solutions may have some features or characteristics 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 (SUS) is a technique used in genetic algorithms for selecting potentially useful solutions for recombination. It was introduced by James Baker.
SUS is a development of fitness proportionate selection (FPS) which exh ...
or
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 (or "chromosomes") chosen at random from the po ...
, 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.
The naive implementation is carried out by first generating the
cumulative probability distribution (CDF) over the list of individuals using a probability proportional to the fitness of the individual. A
uniform random number from the range
binary_search_
In_computer_science,_binary_search,_also_known_as_half-interval_search,_logarithmic_search,_or_binary_chop,_is_a__search_algorithm_that_finds_the_position_of_a_target_value_within_a__sorted_array._Binary_search_compares_the_target_value_to_the_...
_over_the_elements_of_the_CDF._It_takes_in_the_Big_O_notation.html" ;"title="Binary_search_algorithm.html" "title=",1) is chosen and the inverse of the CDF for that number gives an individual. This corresponds to the roulette ball falling in the bin of an individual with a probability proportional to its width. The "bin" corresponding to the inverse of the uniform random number can be found most quickly by using a Binary search algorithm">binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
over the elements of the CDF. It takes in the Big O notation">O(log n) time to choose an individual. A faster alternative that generates individuals in O(1) time will be to use the alias method.
Recently, a very simple algorithm was introduced that is based on "stochastic acceptance". The algorithm randomly selects an individual (say
is the maximum fitness in the population. Certain analysis indicates that the stochastic acceptance version has a considerably better performance than versions based on linear or binary search, especially in applications where fitness values might change during the run.