Genetic Algorithms encoding types,breeding and selection and crossover

i) Binary Encoding

•The most common way of encoding is a binary string, which is represented as in Fig. 6

                     Fig.6 Binary coding

•Each chromosome encodes a binary (bit) string.

•Each bit in the string can represent some characteristics of the solution.

•Every bit string therefore is a solution but not necessarily the best solution.

•The way bit strings can code differs from problem to problem

•Binary encoding gives many possible chromosomes with a smaller number of alleles. 

•This encoding is not natural for many problems and sometimes corrections must be made after genetic operation is completed. Binary coded strings with 1's and 0's are mostly used.

• The length of the string depends on the accuracy.

• The accuracy that can be obtained with a 4-bit string is only 1/16th of search space

• The longer the string length, more is the accuracy 

Octal Encoding

This encoding uses string made up of octal numbers (0–7).

                     Fig.7 Octal encoding

Hexadecimal Encoding

•This encoding uses string made up of hexadecimal numbers (0–9, A-F).

                Fig.8 Hexadecimal encoding

Permutation Encoding (Real Number Coding)

•Every chromosome is a string of numbers, which represents the number in sequence.

•Sometimes corrections have to be done after genetic operation is completed.

•In permutation encoding, every chromosome is a string of integer/real values, which represents number in a sequence.

                    Fig.9 Real number coding

Breeding

•The breeding process is the heart of the genetic algorithm. It is in this process, the search process creates new and hopefully fitter individuals.

•The breeding cycle consists of three steps:

a. Selecting parents.

b. Crossing the parents to create new individuals (offspring or children).

c. Replacing old individuals in the population with the new ones.

Selection

•Selection is the process of choosing two parents from the population for crossing. It is also called as Reproduction. 

•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 offsprings 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.

•Fig. 10 shows the basic selection process.

                               Fig.10. Selection

The various selection methods:

i.Roulette wheel selection

ii.Random selection

iii.Rank selection

iv.Tournament selection

v.Boltzmann selection

Roulette Wheel Selection

• A string is selected from the mating pool with a probability proportional to the fitness.

• ith string in the population is selected with a probability proportional to Fi. Where Fi is the 

fitness of the string

• Probability for selecting the ith string is 

where n is the population size

•The Roulette wheel circumference is marked proportionate to string’s fitness as shown in fig.11

• The Roulette wheel mechanism is expected to make copies of ith string of the mating pool.

               Fig.11 Roulette Wheel

Crossover (Recombination)

•Crossover is the process of taking two parent solutions and producing from them a child.

•Reproduction makes clones of good strings but does not create new ones.

•Crossover operator is applied to the mating pool with the hope that it creates a better 

offspring.

Crossover is a recombination operator that proceeds in three steps:

i) The reproduction operator selects at random a pair of two individual strings for the mating.

ii) A cross site is selected at random along the string length.

iii) Finally, the position values are swapped between the two strings following the cross site

Single Point Crossover

   •The traditional genetic algorithm uses single point crossover, where the two mating chromosomes are cut once at corresponding points and the sections after the cuts exchanged.

            

         •Here, a cross-site or crossover point is selected randomly along the length of the mated strings and bits next to the cross-sites are exchange

          •If appropriate site is chosen, better children can be obtained by combining good parents else it severely hampers string quality.

                         Fig.12  Single point crossover

Two Point Crossover

In two-point crossover, two crossover points are chosen and the contents between these points are 

exchanged between two mated parents.

                                                   Fig.13 Two point crossover

Uniform Crossover

          •Each gene in the offspring is created by copying the corresponding gene from one or the other parent chosen according to a randomly generated binary crossover mask of the same length as the chromosomes. If there is a 1 in the crossover mask, the gene is copied from the first parent, and where there is a 0 in the mask the gene is copied from the second parent.

                                                         Fig.14  Uniform crossover

Three Parent Crossover

In this crossover technique, three parents are randomly chosen. Each bit of the first parent is compared with the bit of the second parent. If both are the same, the bit is taken for the offspring otherwise; the bit from the third parent is taken for the offspring. This concept is illustrated in Fig.15a