GA (GENETIC ALGORITHM):
GA (Genetic Algorithm) is good at taking larger, potentially huge search space and navigating them looking for optimal solution which we might not find in lifetime. GA is better than other traditional algorithm in that they are more robust. They do not break easily even if the inputs are changed slightly or in the presence of reasonable noise.
GA is used to resolve complicated optimization problems, such as , organizing the time table, scheduling job shop, playing games. The concept of GA is directly derived from natural evolution and heredity i.e. inheritance, where child inherits the characters (stored in the chromosomes) from the parent.
Operators in GA:
Crossover is the process of taking two parent solutions and producing from them a child. After the selection (reproduction) process, the population is enriched with better individuals. Crossover operator is applied to the mating pool with the hope that it creates a better offspring.
The various crossover techniques are-
i).Single-Point Crossover-Here the two mating chromosomes are cut once at corresponding points and the sections after the cuts exchanged.
ii). Two-Point Crossover-Here two crossover points are chosen and the contents between these points are exchanged between two mated parents.
Inversion operator inverts the bits between two random sites.
01 0011 1
i).Deletion and duplication-Here any two or three bits in random are selected and their previous bits are duplicated.
before duplication: 00 1001 0
deletion: 00 10_ _ 0
duplication: 00 1010 0
ii). Deletion and regeneration-Here bits between the cross site are deleted and regenerated randomly.
10 0110 1
10 _ _ _ _ 1
10 1101 1
After crossover, the strings are subjected to mutation. Mutation prevents the algorithm to be trapped in a local minimum. It plays the role of recovering the genetic materials as well as for randomly distributing genetic information. It helps escape from local minima’s trap and maintain diversity in the population. Mutation of a bit involves flipping a bit, changing 0 to 1and vice-versa.