Transcript chapter8
Genetic Algorithms • GAs are one of the most powerful and applicable search methods available • GA originally developed by John Holland (1975) • Inspired by natural genetics and biological evolution • Uses concept of “survival of fittest” (fitness function) • Genetic operators (crossover, mutation, etc.) used to modify a pool of state candidates in order to improve them • Survival of the fittest, with reproduction of new possible individuals coming from best discovered parents • Iterative procedure (iterative improvement) • Produces a series of populations one per iteration • Each member of a population represents a feasible solution, called a chromosome GA Pseudo Code Genetic Operators Selection Mechanisms • • Should be based on fitness, of course Fitness proportionate selection Prhi • Fitnesshi Fitnessh j Tournament Selection: – Pick h1, h2 randomly – With probability p (p>0.5) select the more fit • Rank Selection: – Sort all hypothesis by fitness – Prob of selection is proportional to rank • Elitist Selection: Insure that at least 1 copy of the best individual survives Specific vs General approaches • The genes of the individuals -- the genotype -- are used to determine how it behaves (i.e., how well it solves the problem) -- the phenotype. • The genetic operators manipulate the genes, thus they must be tied to the representation of the genes. • Genetic operators that are specific to the problem domain. • Significant research has been done, attempting to determine universal genetic operators, based on universal gene representations. • Unfortunately, these attempts have not been successful and it has been shown that problem specific encodings typically out perform universal encodings GA Pros/Cons • Various Data Representations, One Algorithm • No fancy math involved in the algorithm, however designing an objective can be difficult and confusing • Easy to understand • Works on almost anything – must have objective function • Inherently parallel • Doesn’t work as well as other algorithms in convex (or mostly convex) search spaces – i.e. if you know a smart way to search the space, do it • Depending on complexity, a GA can be computationally expensive • Often requires a lot of tweaking GA applet • • • • • • • Init: 250 plants, 25 plant eaters Plants tend to grow in clumps If an eater bumps into a plant, it eats it The more plants an eater eats, the better Each iteration, a new generation of eaters is produced New population produced through mutation and xover Eater can see single square just in front of I – Can see: plant, empty space, eater, wall. • Eater has an internal (16 possible) state • At each time step eater can: move forward, move backwards, turn left, turn right. It can also change its internal state. • Decision on action based on internal state and what it sees in front of it (requires 64 rules). More GA stuff • What do GAs work on?: GA-easy vs GA-hard – The royal road • Determining basins of attraction