MACHINE LEARNING - GENETIC ALGORITHM

It will help you in understanding about genetic algorithm and more

1. GENETIC ALGORITH M Presented By:- Puneet Kulyana M.Sc. Bioinfo . 3 rd Sem. JMI, New Delhi

2. GA Quick Overview Developed: USA in the 1970’s By J. Holland, K. DeJong, D. Goldberg D iscrete optimization Typically applied to: N ot too fast G ood heuristic for combinatorial problems Attributed features: Traditionally emphasizes combining information from good parents (crossover) many variants, e.g., reproduction models, operators Special Features:

3. What is GA ?? A genetic algorithm (or GA ) is a search technique used in computing to find true or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).

4. Basic Concepts GA converts design space into genetic space Works with a coding variables T r a dition a l o p t imi za tion t e c hniqu e s a r e d e t e rmin i s t i c in nature , but GA uses randomized operators Three important aspects : Definition of objective function Definition and implementation of genetic representation Definition and implementation of genetic operators

5. Encoding Encoding of chromosomes is one of the problems when one is starting to solve problem with genetic algorithm There are various types of encoding used for solving the problems Four types of encoding are:- Binary encoding Permutation encoding Value encoding Tree encoding

6. Representation (encoding) Examples Possible individual’s encoding Binary (Bit strings) (0101 ... 1100) Real numbers (43.2 -33.1 ... 0.0 89.2) Permutations of element (E11 E3 E7 ... E1 E15) Lists of rules (R1 R2 R3 ... R22 R23) Program elements (genetic programming) Octal Hexadecimal Floating-point Tree Representation Random Keys ... any data structure ...

7. Search Space The space for all possible feasible solutions Each feasible solution can be "marked" by its value of the fitness of the problem GA is started with a set of solutions called populations Used to form a new population More suitable, more chances to select This is repeated until best population is obtained

8. Fitness Function Basically, a fitness function is used to evaluate phenotypes to identify the fittest population members. It is a function which takes the solution as input and produces the suitability of the solution as output In some cases, the fitness function and the objective function may be the same, while in others it may be different based on the problem. It measures the quality of the represented solution It is always problem dependent Th e f i t ne ss of a s o l u t i o n i s m ea s u r ed , ho w be st i t gives the result For instance, Knapsack problem

9. Steps of genetic algorithm Step 1 : Encoding of the problem in a binary string Step 2 : Random generation of a population Step 3: Calculate fitness of each solution Step 4 : Select pairs of parent strings based on fitness Step 5 : Generate new string with crossover and mutation until a new population has been produced Repeat steps 2 to 5 until satisfying solution is obtained

10. Operators of Genetic algorith m Three Basic operators are: Reproduction Crossover Mutation The new population is further evaluated and tested for termination If the termination criteria are not met, the population is iteratively operated One cycle of operations and the subsequent evaluation – Generation in GA

11. Reproduction C h r o m o s o m e s a r e s e l ect e d f r o m the pop u l at i on to b e p arents to crossover and produce offspring Also known as Selection Operator Parents are selected according to their fitness Th ere a re m an y m e th od s to se l e c t the be st chromosomes A) Roulette Wheel Selection B) Rank Selection C) Tournament Selection D) Steady State Selection The better the chromosomes are, the more chances to be selected they have

12. CROSSOVER Chromosomal crossover (or crossing over ) is the exchange of genetic material between homologous chromosomes Crossover usually occurs whe n matching regions on matching chromosomes break and then reconnect to the other chromosome.

13. GA operators: Crossover Choose a random point on the two parents Split parents at this crossover point Create children by exchanging tails Generally setting crossover probability with a value 0.5 produces good results and its typical range id 0.3 to 1. E.g. Probability of crossover is 25% so 5 out of 20 chromosome will undergo crossover.

14. Different kind of Crossovers Sub-tour exchange Heuristic crossover Arithmetic Crossover Directional Crossover Single-point Double-point Multiple-point Uniform Matrix Crossover Random Permutation-based Order-based Position-based Cycle Crossover

15. CROSSOVER

16. MUTATION IN GENETIC ALGORITHM Mutation is a genetic operator used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next . It is analogous to biological mutation . The mutation probability is kept quite low between 0.001 and 0.01 . Mutation alters one or more gene values in a chromosome from initial state

17. Different kind of Mutation Uniform Mutation Boundary Non-uniform 1’s Complement Operator Logical Bitwise Bitwise XOR Bitwise OR Shift Operator (>>,<<) Masking Operator Inversion Insertion Displacement Reciprocal Exchange

18. APPLICATIONS There are various applications of genetic algorithm in bioinformatics. Some of them are:- They are used for multiple sequence alignment Used for RNA structure prediction Used for motif discovery Used for building phylogenetic trees Used for clustering to optimize a wide range of fit – funcions Used for gene expression profiling analysis Used for protein folding and protein/ligand docking Used for operon prediction

19. Advantages Easy to understand Modular, separate from application Supports multi-objective optimization Easy to exploit previous or alternate solutions Flexible in forming building blocks for hybrid applications Substantial history and range of use DISADVANTAGES GA requires more computational time It is slower than some other methods

20. REFERENCE S Genetic algorithms in search, optimization, and machine learning (Book by David E. Goldberg) ocw . mit .edu(MIT OPEN COURSE) nptel.ac.in www. google .com N e u r al N et w o r k s , F u z zy L o g i c , Algorithms S. Rajasekaran G. A. Vijayalakshmi Pai

21. THANK YOU