Genetic algorithm (ga) binary and real Vijay Bhaskar Semwal

Genetic algorithm (ga) binary and real Vijay Bhaskar Semwal

• 2.
  Introduction to GeneticAlgorithms2 We toss a fair coin 60 times and get the following initial population: s1 = 1111010101 f (s1) = 7 s2 = 0111000101 f (s2) = 5 s3 = 1110110101 f (s3) = 7 s4 = 0100010011 f (s4) = 4 s5 = 1110111101 f (s5) = 8 s6 = 0100110000 f (s6) = 3
• 3.
  Introduction to GeneticAlgorithms3 Next we apply fitness proportionate selection with the roulette wheel method: 21 n 3 Area is Proportional to fitness value Individual i will have a probability to be chosen i if if )( )( 4 We repeat the extraction as many times as the number of individuals we need to have the same parent population size (6 in our case)
• 4.
  Introduction to GeneticAlgorithms4 Suppose that, after performing selection, we get the following population: s1` = 1111010101 (s1) s2` = 1110110101 (s3) s3` = 1110111101 (s5) s4` = 0111000101 (s2) s5` = 0100010011 (s4) s6` = 1110111101 (s5)
• 5.
  Introduction to GeneticAlgorithms5 Next we mate strings for crossover. For each couple we decide according to crossover probability (for instance 0.6) whether to actually perform crossover or not Suppose that we decide to actually perform crossover only for couples (s1`, s2`) and (s5`, s6`). For each couple, we randomly extract a crossover point, for instance 2 for the first and 5 for the second
• 6.
  Introduction to GeneticAlgorithms6 s1` = 1111010101 s2` = 1110110101 s5` = 0100010011 s6` = 1110111101 Before crossover: After crossover: s1`` = 1110110101 s2`` = 1111010101 s5`` = 0100011101 s6`` = 1110110011
• 7.
  Introduction to GeneticAlgorithms7 The final step is to apply random mutation: for each bit that we are to copy to the new population we allow a small probability of error (for instance 0.1) Before applying mutation: s1`` = 1110110101 s2`` = 1111010101 s3`` = 1110111101 s4`` = 0111000101 s5`` = 0100011101 s6`` = 1110110011
• 8.
  Introduction to GeneticAlgorithms8 In one generation, the total population fitness changed from 34 to 37, thus improved by ~9% At this point, we go through the same process all over again, until a stopping criterion is met
• 9.
  Introduction to GeneticAlgorithms9 A vector v = (i1 i2… in) represents a tour (v is a permutation of {1,2,…,n}) Fitness f of a solution is the inverse cost of the corresponding tour Initialization: use either some heuristics, or a random sample of permutations of {1,2,…,n} We shall use the fitness proportionate selection
• 10.
  Introduction to GeneticAlgorithms10 Next, starting from the second cut point of one parent, the cities from the other parent are copied in the same order The sequence of the cities in the second parent is 9 – 3 – 4 – 5 – 2 – 1 – 8 – 7 – 6 After removal of cities from the first offspring we get 9 – 3 – 2 – 1 – 8 This sequence is placed in the first offspring o1 = (2 1 8 4 5 6 7 9 3), and similarly in the second o2 = (3 4 5 1 8 7 6 9 2)
• 11.
  Introduction to GeneticAlgorithms11 The sub-string between two randomly selected points in the path is reversed Example: (1 2 3 4 5 6 7 8 9) is changed into (1 2 7 6 5 4 3 8 9) Such simple inversion guarantees that the resulting offspring is a legal tour
• 12.
  Example
• 13.
   Simple problem:max x2 over {0,1,…,31}  GA approach:  Representation: binary code, e.g. 01101  13  Population size: 4  1-point xover, bitwise mutation  Roulette wheel selection  Random initialisation  We show one generational cycle done by hand
• 17.
   Has beensubject of many (early) studies  still often used as benchmark for novel GAs  Shows many shortcomings, e.g.  Representation is too restrictive  Mutation & crossovers only applicable for bit-string & integer representations  Selection mechanism sensitive for converging populations with close fitness values  Generational population model (step 5 in SGA repr. cycle) can be improved with explicit survivor selection
• 18.
   Performance with1 Point Crossover depends on the order that variables occur in the representation  more likely to keep together genes that are near each other  Can never keep together genes from opposite ends of string  This is known as Positional Bias  Can be exploited if we know about the structure of our problem, but this is not usually the case
• 19.
   Choose nrandom crossover points  Split along those points  Glue parts, alternating between parents  Generalisation of 1 point (still some positional bias)
• 20.
   Assign 'heads'to one parent, 'tails' to the other  Flip a coin for each gene of the first child  Make an inverse copy of the gene for the second child  Inheritance is independent of position
• 21.
   Decade longdebate: which one is better / necessary / main- background  Answer (at least, rather wide agreement):  it depends on the problem, but  in general, it is good to have both  both have another role  mutation-only-EA is possible, xover-only-EA would not work
• 22.
  Exploration: Discovering promisingareas in the search space, i.e. gaining information on the problem Exploitation: Optimising within a promising area, i.e. using information There is co-operationAND competition between them  Crossover is explorative, it makes a big jump to an area somewhere “in between” two (parent) areas  Mutation is exploitative, it creates random small diversions, thereby staying near (in the area of ) the parent
• 23.
   Only crossovercan combine information from two parents  Only mutation can introduce new information (alleles)  Crossover does not change the allele frequencies of the population (thought experiment: 50% 0’s on first bit in the population, ?% after performing n crossovers)  To hit the optimum you often need a ‘lucky’ mutation
• 24.
  Introduction to GeneticAlgorithms24 In this section we take an in-depth look at the working of the standard genetic algorithm, explaining why GAs constitute an effective search procedure For simplicity we discuss binary string representation of individuals
• 25.
  Introduction to GeneticAlgorithms25 {0,1,#} is the symbol alphabet, where # is a special wild card symbol A schema is a template consisting of a string composed of these three symbols Example: the schema [01#1#] matches the strings: [01010], [01011], [01110] and [01111]
• 26.
  Introduction to GeneticAlgorithms26 The order of the schema S (denoted by o(S)) is the number of fixed positions (0 or 1) presented in the schema Example: for S1 = [01#1#], o(S1) = 3 for S2 = [##1#1010], o(S2) = 5 The order of a schema is useful to calculate survival probability of the schema for mutations There are 2 l-o(S) different strings that match S