introduction of genetic algorithm

introduction of genetic algorithm

• 1.
  Amity School ofEngineering & Technology Introduction of Genetic Algorithms Ritambhara M.Tech(CSE)
• 2.
  Amity School ofEngineering & Technology • 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). What is GA.
• 3.
  Amity School ofEngineering & Technology • Genetic algorithms are implemented as a computer simulation in which a population of abstract representations (called chromosomes or the genotype or the genome) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem evolves toward better solutions. • Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible. What is GA
• 4.
  What is GA(Cont..) • The evolution usually starts from a population of randomly generated individuals and happens in generations. • In each generation, the fitness of every individual in the population is evaluated, multiple individuals are selected from the current population (based on their fitness), and modified (recombined and possibly mutated) to form a new population.
• 5.
  • The newpopulation is then used in the next iteration of the algorithm. • Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. • If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached. What is GA (Cont..)
• 6.
  Key terms • Individual- Any possible solution • Population - Group of all individuals • Search Space - All possible solutions to the problem • Chromosome - Blueprint for an individual • Trait - Possible aspect (features) of an individual • Allele - Possible settings of trait (black, blond, etc.) • Locus - The position of a gene on the chromosome • Genome - Collection of all chromosomes for an individual
• 7.
  GA Requirements • Atypical genetic algorithm requires two things to be defined: • a genetic representation of the solution domain, and • a fitness function to evaluate the solution domain. • A standard representation of the solution is as an array of bits. Arrays of other types and structures can be used in essentially the same way. • The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, that facilitates simple crossover operation . • Variable length representations may also be used, but crossover implementation is more complex in this case. • Tree-like representations are explored in Genetic programming.
• 8.
  Basics of GA •The most common type of genetic algorithm works like this: • a population is created with a group of individuals created randomly. • The individuals in the population are then evaluated. • The evaluation function is provided by the programmer and gives the individuals a score based on how well they perform at the given task. • Two individuals are then selected based on their fitness, the higher the fitness, the higher the chance of being selected. • These individuals then "reproduce" to create one or more offspring, after which the offspring are mutated randomly. • This continues until a suitable solution has been found or a certain number of generations have passed, depending on the needs of the programmer.
• 9.
  General Algorithm forGA • Initialization • Initially many individual solutions are randomly generated to form an initial population. The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. • Traditionally, the population is generated randomly, covering the entire range of possible solutions (the search space). • Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.
• 10.
  • Selection operator: •Process of selecting two or more parents from the Population for crossing. • Purpose of selection is its emphasize filter individuals in the population in hopes that their off strings have higher fitness. • Method: roulette wheel selection, boltzman selection, tournament selection, rank selection.
• 11.
  Example Maximize the functionf(x)=x^2 with x is interval [0,31] i.e., x= 0,1,………30,31 1) Generate initial population at random. They ate chromosomes or genotypes. Eg- 0110 (13), 11000(24), 01000(8), 10011(19) Calculate fitness a) Decode into an integer (called phenotypes) 01101 13, 1100024, 010008, 1001119 b) Evaluate fitness, f(x)=x^2 13169, 24526, 864, 19361 2)
• 12.
  Crossover • the mostcommon type is single point crossover. In single point crossover, you choose a locus at which you swap the remaining alleles from on parent to the other. This is complex and is best understood visually. • As you can see, the children take one section of the chromosome from each parent. • The point at which the chromosome is broken depends on the randomly selected crossover point. • This particular method is called single point crossover because only one crossover point exists. Sometimes only child 1 or child 2 is created, but oftentimes both offspring are created and put into the new population.
• 13.
  • After selectionand crossover, you now have a new population full of individuals. • Some are directly copied, and others are produced by crossover. • In order to ensure that the individuals are not all exactly the same, you allow for a small chance of mutation. • You loop through all the alleles of all the individuals, and if that allele is selected for mutation, you can either change it by a small amount or replace it with a new value. The probability of mutation is usually between 1 and 2 tenths of a percent. • Mutation is fairly simple. You just change the selected alleles based on what you feel is necessary and move on. Mutation is, however, vital to ensuring genetic diversity within the population. Mutation