Components Of Genetic Algorithms in #InfoSWMM

Standard genetic algorithms involve three basic functions: selection, crossover, and mutation. 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 to represent parents to reproduce offspring is guided by a probability rule that the higher the fitness an individual has, the more likely the individual will survive. 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, a 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 level. The basic crossover is a one-point crossover. Two selected strings create two offspring strings by swapping the partial strings, which is cut by one randomly sampled breakpoint along the chromosome. The one-point crossover can easily be 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 genes. It works on the level of string genes by randomly altering gene value. With small probability, it randomly selects one gene on a chromosome then replaces the gene by a randomly selected value. 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.

The flowchart below illustrates the optimal calibration process.