Standard genetic algorithms involve four basic functions: selection, crossover, mutation, and elitism. The flowchart illustrates the scheduling optimization process. Each function is briefly described below.
Selection - Individuals in a population are selected for reproduction according to their fitness values. In biology, fitness is the number of offspring that survive to reproduction. Given a population consisting of individuals identified by their chromosomes, selecting two chromosomes as parents to reproduce offspring is guided by a probability rule that the higher the fitness an individual has, the more likely the individual is selected. There are many selection methods available including weighted roulette wheel, sorting schemes, proportionate reproduction, and tournament selection.
Crossover - Selected parents reproduce the offspring by performing a crossover operation on the chromosomes (cut and splice pieces of one parent to those of another). In nature, crossover implies two parents exchange parts of their corresponding chromosomes. In genetic algorithms, crossover operation makes two strings swap their partial strings. Since more fit individuals have a higher probability of producing offspring than less fit ones, the new population will possess on average an improved fitness. The basic crossover is a one-point crossover. Two selected strings create two offspring strings by swapping the partial strings, which are cut by one randomly sampled breakpoint along the chromosome. The one-point crossover can be easily extended to k-point crossover. It randomly samples k breakpoints on chromosomes and then exchanges every second corresponding segments of two parent strings.
Mutation - Mutation is an insurance policy against lost bits. It works on the level of string bits by randomly altering a bit value. With small probability, it randomly selects one bit on a chromosome then inverts the bit from 0 to 1 or vice versa. The operation is designed to prevent GA from premature termination, namely converging to a solution too early.
Elitism - The selection and crossover operators will tend to ensure that the best genetic material and the components of the fittest chromosomes will be carried forward to the next generation. However, the probabilistic nature of these operators implies that this will not always be the case. An elitist strategy is therefore required to ensure that the best genetic material will not be lost by chance. This is accomplished by always carrying forward the best chromosome from one generation to the next.