ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Genetic algorithm

•Download as PPTX, PDF•
•
D
Designage Solutions

This document discusses genetic algorithms. It introduces genetic algorithms as global search heuristics inspired by evolutionary biology concepts like inheritance, mutation, and crossover. It describes the key genetic algorithm operators of reproduction, crossover, and mutation. Reproduction selects above-average solutions for breeding, crossover combines parts of parent solutions, and mutation randomly changes parts of a solution. The document outlines the genetic algorithm process of initializing a random population, evaluating via a fitness function, selecting parents, applying operators, and iterating until termination criteria is met. Genetic algorithms are advantageous for complex problems as they use populations to search in parallel and only require objective function values rather than derivatives.

1 of 10
Downloaded 53 times
Genetic Algorithm Presented by Harshada Gurav CADME 2015-16 Roll No. 05
INTRODUCTION  Introduced by Prof. John Holland in 1975.  Genetic algorithms are categorized as global search heuristic algorithm.  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).
FITNESS FUNCTION F(x) Derived from objective function f(x) Most often used function is F(x) = 1/(1+f(x))
GA Operators GA Operators Reproduction crossover mutation
REPRODUCTION  It selects good (above average) strings in a population and forms a mutation pool.  The probability for selecting ith string is n = population size  One way to implement the selection scheme is roulette-wheel selection mechanism.
CROSSOVER  Choose a random point on the two parents  Split parents at this crossover point  Create children by exchanging tails  Crossover probability is ‘Pc’
MUTATION  The mutation operator is applied to the new strings with a specific small mutation probability, pm.  The mutation operator changes the binary digit 1 to 0 and vice versa.  pm is called the mutation rate Typically between 1/pop_size and 1/ chromosome_length  It maintains diversity in the population
Steps in GA 1. Choose a coding to represent problem parameters, a selection operator, a crossover operator, mutation operator, population size, crossover probability and mutation probability. 2. Initialize random population of strings of size l, tmax, set t = 0. 3. Evaluate each string in population 4. If t > tmax or other termination criteria is satisfied, terminate 5. Perform reproduction on the population 6. Perform crossover on random pairs of string 7. Perform mutation on every string 8. Evaluate strings in the new population. Set t = t+1 and go to step 3.
ADVANTAGES  It is very potential algorithm.  Used for complex engineering problems  A population of points is used for starting the procedure instead of a single design point.  GAs use only the values of the objective function. The derivatives are not used in the search procedure.  The objective function value corresponding to a design vector plays the role of fitness in natural genetics.  GA efficiently explore the new combinations with the available knowledge to find a new generation with better fitness value.
Genetic algorithm

More Related Content

Genetic algorithm

  • 1. Genetic Algorithm Presented by Harshada Gurav CADME 2015-16 Roll No. 05
  • 2. INTRODUCTION  Introduced by Prof. John Holland in 1975.  Genetic algorithms are categorized as global search heuristic algorithm.  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).
  • 3. FITNESS FUNCTION F(x) Derived from objective function f(x) Most often used function is F(x) = 1/(1+f(x))
  • 5. REPRODUCTION  It selects good (above average) strings in a population and forms a mutation pool.  The probability for selecting ith string is n = population size  One way to implement the selection scheme is roulette-wheel selection mechanism.
  • 6. CROSSOVER  Choose a random point on the two parents  Split parents at this crossover point  Create children by exchanging tails  Crossover probability is ‘Pc’
  • 7. MUTATION  The mutation operator is applied to the new strings with a specific small mutation probability, pm.  The mutation operator changes the binary digit 1 to 0 and vice versa.  pm is called the mutation rate Typically between 1/pop_size and 1/ chromosome_length  It maintains diversity in the population
  • 8. Steps in GA 1. Choose a coding to represent problem parameters, a selection operator, a crossover operator, mutation operator, population size, crossover probability and mutation probability. 2. Initialize random population of strings of size l, tmax, set t = 0. 3. Evaluate each string in population 4. If t > tmax or other termination criteria is satisfied, terminate 5. Perform reproduction on the population 6. Perform crossover on random pairs of string 7. Perform mutation on every string 8. Evaluate strings in the new population. Set t = t+1 and go to step 3.
  • 9. ADVANTAGES  It is very potential algorithm.  Used for complex engineering problems  A population of points is used for starting the procedure instead of a single design point.  GAs use only the values of the objective function. The derivatives are not used in the search procedure.  The objective function value corresponding to a design vector plays the role of fitness in natural genetics.  GA efficiently explore the new combinations with the available knowledge to find a new generation with better fitness value.