Question? Leave a message!

Genetic Algorithms

Genetic Algorithms
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Genetic Algorithms www.ThesisScientist.comAnswering the AI Question  How do we get an agent to act intelligently?  One answer: – Humans have evolved a brain  Which enables us to act intelligently  Idea: – Mimic Darwinian evolution to evolve intelligent agents  Intelligence is a specific instance of evolution – Evolving a species to survive in a niche – Via adaptation of species through survival of the fittest  More general idea: – Evolve programs to solve problems www.ThesisScientist.comEvolutionary Approaches to AI  John Holland 1975 – “Adaptation in Natural and Artificial Systems”  Developed the idea of a genetic algorithm – Searching via sampling hyperplane partitions of the search space – Still just search over a space  Broader sense: – Somehow representing solutions to a problem – And allowing solutions to be combined into new ones  And testing whether the new ones are improvements www.ThesisScientist.comGenetic Algorithms (GAs) and Genetic Programming (GP)  Genetic Algorithms – Optimising parameters for problem solving – Fix a format for the parameters in a problem solution – Represent the parameters in the solution(s)  As a “bit” string normally, but often something else – Evolve answers in this representation  Genetic Programming – Representation of solutions is richer in general – Solutions can be interpreted as programs – Evolutionary process is very similar – Covered in n we ww x.T t hlect esisSu cien re tist.comOverview of Classical GAs  Representation of parameters is a bit string – Solutions to a problem represented in binary – 101010010011101010101  Everything in computers is represented in binary  Start with a population (fairly large set) – Of possible solutions known as individuals  Combine possible solutions by swapping material – Choose the “best” solutions to swap material between and kill off the worse solutions – This generates a new set of possible solutions  Requires a notion of “fitness” of the individual – Base on an evaluation function with respect to the problem – Dependent on properties of the solution www.ThesisScientist.comThe Canonical Genetic Algorithm No www.ThesisScientist.comThe Initial Population  Represent solutions to problems – As a bit string of length L – (Difficult part of using GA’s – see later)  Choose an initial population size – Generate length L strings of 1s & 0s randomly – Sometimes (rarely) done more intelligently  Strings are sometimes called chromosomes – Letters in the string are called “genes”  See later for the (bad) analogies – We call the bit-string “individuals” www.ThesisScientist.comThe Selection Process  We are going to combine pairs of members of the current population to produce offspring – So, we need to choose which pairs to combine  Will use an evaluation function, g(c) – Which is dependent on desirable properties of the solutions (defining this is often tricky)  Use g(c) to define a fitness function www.ThesisScientist.comCalculating Fitness  Use a fitness function – To assign a probability of each individual being used in the mating process for the next generation  Usually use fitness(c) = g(c)/A – Where A = average of g(c) over the entire population  Other constructions are possible www.ThesisScientist.comUsing the Fitness Function  Use fitness to produce an intermediate population IP – From which mating will occur  Integer part of the fitness value is: – The number of copies of individuals guaranteed to go in IP  Fractional part is: – A probability that an extra copy will go into IP – Use a probabilistic function (roll dice) to determine whether  The extra copies are added to the IP www.ThesisScientist.comExamples of Selection  Example 1 – Suppose the average of g over the population is 17 – And for a particular individual c , g(c ) = 25 0 0 – Fitness(c ) = 25/17 = 1.47 0 – Then 1 copy of c is guaranteed to go into IP 0 – And the probability of another copy going in is 0.47  Example 2 – Suppose g(c ) = 14 1 – No copy of c is guaranteed to go into IP 1 – The probability of one copy going in is 14/17 = 0.82 www.ThesisScientist.comThe Mating Process  Pairs from the Intermediate Population – Are chosen randomly – Could be the same individual twice  They are combined with a probability p c – Their offspring are produced by recombination  See later slides – Offspring go into the next generation population  The process is repeated until – The next generation contains the required number of individuals for the next population – Often this is taken as the current population size  Which keeps the population size constant (not a bad idea)Analogy with Natural Evolution  Analogy holds: – Some very fit individuals may be unlucky, and: (a) not find a partner (b) not be able to reproduce with the partner they find – Some less fit individuals may be lucky and:  Find a partner and produce hundreds of offspring  Analogy breaks: – There is no notion of sexes  Although there are some types of asexual worms, etc., …. – Individuals can mate with themselves  Although cells reproduce alone… www.ThesisScientist.comThe Recombination Process  The population will only evolve to be better – If best parts of the best individuals are combined  Crossover techniques are used – Which take material from each individual – And adds it to “offspring” individuals  Mutation techniques are used – Which randomly alter the offspring – Good for getting out of local maxima www.ThesisScientist.comOne-point crossover  Randomly choose a single point in both individuals – Both have the same point – Split into LHS +RHS and LHS +RHS 1 1 2 2  Generate two offspring from the combinations – Offspring 1: LHS +RHS 1 2 – Offspring 2: LSH +RHS 2  Example: (X,Y,a,b are all ones and zeros) www.ThesisScientist.comTwo-point Crossover  Two points are chosen in the strings  The material falling between the two points – is swapped in the string for the two offspring  Example: www.ThesisScientist.comInversion  Another possible operator to mix things up – Takes the material from only on parent  Randomly chooses two points – Takes the segment in-between the points – Reverses it in the offspring Example: www.ThesisScientist.comThe Mutation Process  Recombination keeps large strings the same – Not just randomly jumbling up the bit-strings (important point) – Produces a large range of possible solutions – But might get into a local maxima  Random mutation – Each bit in every offspring produced  Is “flipped” from 0 to 1 or vice versa  With a given probability (usually pretty small 1%) – May help avoid local maxima  In natural evolution mutation is almost always deleterious  Could use probability distribution – To protect the best individuals in population – But is this good for avoiding local maxima? www.ThesisScientist.comSchematic Overview for Producing the Next Generation www.ThesisScientist.comThe Termination Check  Termination may involve testing whether an individual solves the problem to a good enough standard – Not necessarily having found a definitive answer  Alternatively, termination may occur after a fixed time – Or after a fixed number of generations  Note that the best individual in a population – May not be as good as the best in a previous popn  So, your GA should: – Record the best from each generation – Output the best from all populations as the answer