Simple Genetic Algorithm

5.3 Selection
Selection is the process of choosing two parents from the population for crossing. After deciding on an encoding, the next step is to decide how to perform selection i.e., how to choose individuals in the population that will create offspring for the
next generation and how many offspring each will create. The purpose of selection is to emphasize fitter individuals in the population in hopes that their off springs have higher fitness. Chromosomes are selected from the initial population to be parents for reproduction. The problem is how to select these chromosomes. According to Darwin’s theory of evolution the best ones survive to create new offspring.



5.3 .1 Roulette Wheel Selection
Roulette selection is one of the traditional GA selection techniques. The commonly used reproduction operator is the proportionate reproductive operator where a string is selected from the mating pool with a probability proportional to the fitness. The principle of roulette selection is a linear search through a roulette wheel with the slots in the wheel weighted in proportion to the individual’s fitness values. A target value is set, which is a random proportion of the sum of the fit nesses in the population. The population is stepped through until the target value is reached. This is only
a moderately strong selection technique, since fit individuals are not guaranteed to be selected for, but somewhat have a greater chance. A fit individual will contribute more to the target value, but if it does not exceed it, the next chromosome in line has a chance, and it may be weak. It is essential that the population not be sorted by fitness, since this would dramatically bias the selection.
The above described Roulette process can also be explained as follows: The expected value of an individual is that fitness divided by the actual fitness of the population. Each individual is assigned a slice of the roulette wheel, the size of the slice being proportional to the individual’s fitness. The wheel is spun N times, where N is
the number of individuals in the population. On each spin, the individual under the wheel’s marker is selected to be in the pool of parents for the next generation.

This method is implemented as follows:
1. Sum the total expected value of the individuals in the population.
Let it be T.
2. Repeat N times:
i. Choose a random integer ‘r’ between o and T.
ii. Loop through the individuals in the population, summing the
expected values, until the sum is greater than or equal to ‘r’.
The individual whose expected value puts the sum over this limit is the one selected. Roulette wheel selection is easier to implement but is noisy. The rate of evolution depends on the variance of fitness’s in the population.