Genetic Algorithm

A genetic algorithm (GA) is a procedure that tries to mimic the genetic evolution of a species. Specifically, GA simulates the biological processes that allow the consecutive generations in a population to adapt to their environment. The adaptation process is mainly applied through genetic inheritance from parents to children and through survival of the fittest. Therefore, GA is a population-based search methodology. Some pioneering works traced back to the middle of 1960s preceded the main presentation of the GAs of Holland in 1975. However, GAs were limitedly applied until their multipurpose presentation of Goldberg 1989 in search, optimization, design and machine learning areas. Nowadays, GAs are considered to be the most widely known and applicable type of metaheuristics.

GA starts with an initial population whose elements are called chromosomes. The chromosome consists of a fixed number of variables which are called genes. In order to evaluates and rank chromosomes in a population, a fitness function based on the objective function should be defined. Three operators must be specified to construct the complete structure of the GA procedure; selection, crossover and mutation operators. The selection operator cares with selecting an intermediate population from the current one in order to be used by the other operators; crossover and mutation. In this selection process, chromosomes with higher fitness function values have a greater chance to be chosen than those with lower fitness function values. Pairs of parents in the intermediate population of the current generation are probabilistically chosen to be mated in order to reproduce the offspring. In order to increase the variability structure, the mutation operator is applied to alter one or more genes of a probabilistically chosen chromosome. Finally, another type of selection mechanism is applied to copy the survival members from the current generation to the next one.

GA operators; selection, crossover and mutation have been extensively studied. Many effective setting of these operators have been proposed to fit a wide variety of problems. More details about GA elements are discussed below before stating a standard GA.

Fitness Function

Fitness function is a designed function that measures the goodness of a solution. It should be designed in the way that better solutions will have a higher fitness function value than worse solutions. The fitness function plays a major role in the selection process.

Coding

Coding in GA is the form in which chromosomes and genes are expressed. There are mainly two types of coding; binary and real. The binary coding was presented in the GA original presentation in which the chromosome is expressed as a binary string. Therefore, the search space of the considered problem is mapped into a space of binary strings through a coder mapping. Then, after reproducing an offspring, a decoder mapping is applied to bring them back to their real form in order to compute their fitness function values. Actually, many researchers still believe that the binary coding is the ideal. However, the real coding is more applicable and easy in programming. Moreover, it seems that the real coding fits the continuous optimization problems better than the binary coding.

Selection

Consider a population P, selection operator selects a set P′ ⊆ P of the chromosomes that will be given the chance to be mated and mutated. The size of P′ is the same as that of P but more fit chromosomes in P are chosen with higher probability to be included in P′. Therefore, the most fit chromosomes in P may be represented by more than one copy in P′ and the least fit chromosomes in P may be not represented at all in P′. Consider the population P = {x₁, x₂, . . . , x_N}. The difference between selection operators lies in the way of computing the probability of including a copy of chromosome x_i ∈ P into the set P′, which is denoted by p_s(x_i). Using these probabilities, the population is mapped onto a roulette wheel, where each chromosome x_i is represented by a space that proportionally corresponds to p_s(x_i). Chromosomes in the set P′ are chosen by repeatedly spinning the roulette wheel until all positions in P′ are filled.

Crossover and Mutation

Crossover operator aims to interchange the information and genes between chromosomes. Therefore, crossover operator combines two or more parents to reproduce new children, then, one of these children may hopefully collect all good features that exist in his parents. Crossover operator is not typically applied for all parents but it is applied with probability pc which is normally set equal to 0.6. Actually, crossover operator plays a major role in GA, so defining a proper crossover operator is highly needed in order to achieve a better performance of GA. Different types of crossover operators have been studied. Mutation operator alters one or more gene in a chromosome. Mutation operator aims to achieve some stochastic variability of GA in order to get a quicker convergence. The probability pm of applying the mutation operator is usually set to be small, normally 0.01.

Standard Genetic Algorithm

1. Initialization. Generate an initial population P₀. Set the crossover andmutation probabilities p_c ∈ (0, 1) and p_m ∈ (0, 1), respectively. Set the generation counter t := 1.

2. Selection. Evaluate the fitness function F at all chromosomes in P_t. Select an intermediate population P_t′ from the current population P_t.

3. Crossover. Associate a random number from (0, 1) with each chromosome in P_t′ and add this chromosome to the parents pool set SP_t if the associated number is less than p_c. Repeat the following Steps 3.1 and 3.2 until all parents in SP_t are mated:  

3.1. Choose two parents p₁ and p₂ from SP_t . Mate p₁ and p₂ to reproduce children c₁ and c₂.

3.2. Update the children pool set SC_t through SC_t := SC_t ∪ {c₁, c₂} and update SP_t through SP_t := SP_t − {p₁, p₂}.

4. Mutation. Associate a random number from (0, 1) with each gene in each chromosome in P_t′, mutate this gene if the associated number is less than p_m, and add the mutated chromosome only to the children pool set SC_t.

5. Stopping Conditions. If stopping conditions are satisfied, then terminate. Otherwise, select the next generation P_t+1 from P_t ∪SC_t . Set SC_t to be empty, set t := t + 1, and go to Step 2.