Question? Leave a message!




Evolution & Genetic Algorithms

Evolution & Genetic Algorithms
Intelligent Control and Cognitive Systems Evolution Genetic Algorithms Joanna J. Bryson University of Bath, United KingdomTheory Fact Evolution: Change over time. Definition • Evolution of Life: Fact • Changes in diversification of species over • time. Natural Selection: Theory • Current scientific explanation of the • observed data. Fact of Evolution Fossil record. • Observed in laboratory (e.g. with bacteria). • Genome record of the “tree of life”. • Totally unknown when the theory of • evolution (natural selection) was developed.Darwin’s Theory Animals tend to produce more • offspring than survive to reproduce. Individuals vary. Offspring more like • parents than average for a species. The individuals most fit to their • environment are most likely to survive and reproduce. gradual changeContemporary Understanding Evolution requires variation, • reproduction and selection. Wherever you have these • conditions, you will get change / optimisation to the selection criteria. Powerful mechanism for • learning / concurrent search. “Universal acid”What about the bees Most honey bees have no offspring, but will • die for their nest. Definition: altruistic behaviour is costly to • the individual, but benefits others. Fundamental to sociality, seen even in • bacteria. How can “survival of the fittest” explain • altruistic behaviourReplicators The mechanisms of heredity (what gets • replicated) are called genes. Genes are an instruction set that, with the • proper biological and environmental context, can produce a new organism. Since genes replicate more perfectly than • whole animals, and affect behaviour, means social traits like altruism can evolve.Evolution of Social Traits Evolution: variation, selection transmission. • What is transmitted is the replicator. • The unit of selection is the vehicle (or • interactor.) In the current ecology, most vehicles are • composed of many, many replicators. (Dawkins 1982) group selection, kin selection, inclusive fitness MultiLevel Selection (different interactors) boo ha ha Replicator (Gene) Group Rah nyah boo nyah Organism Boo.What about the bees Most honey bees have no offspring, but will • die for their nest. All eusocial insects have a 100 • monogamous ancestor species ∴ 50 related to sisters. In that special case, siblings as useful for • propagating genes as offspring. (Hughes et al 2008)Revision: From Lecture 2 Intelligence Design Combinatorics is the problem, search is the only • solution. The task of intelligence is to focus search. • priors Called bias (learning) or constraint (planning). • Most `intelligent’ behavior has no or little real • time search (noncognitive) (cf. Brooks IJCAI91). For artificial intelligence, most focus from design. •Evolution as Learning Bias is provided by phylogeny (evolutionary • history), transmitted in the genome. Search space is determined by variation in the • population. Greater variation accelerates evolution • (rate of change, Fisher 1930, Price 1972) but also less exact (remember: “overshooting” with high learning rate). Learning to learn – evolvability. •Questions… Are genes the only replicator • Maybe individuals groups replicate • Maybe memes replicate • Evolution is one of the bestsupported • theories in science, but the details are still constantly being worked out (just like physics.)Science as Evolution example of memetics Evolution requires variation, reproduction • and selection. Variety of theories get taught. • Theories in new experiments bear some • resemblance to what got taught. Memory of scientists, peer review, • prediction success perform selection.Evolution in AI Requires: • Variation in some trait. • Reproduction with inheritance. • Often asexual + noise. • Selection • Probability of reproduction determined • at least partly by variation.One trait going to fixation in two different conditions. 0 5000 10000 15000 Cycles Proportion of Talkers 0.0 0.2 0.4 0.6 0.8 1.0Introduction to Genetic Algorithms (modified) Slides from: David Hales www.davidhales.comEvolution in the real world • Each cell of a living thing contains chromosomes strings of DNA This definition of gene is controversial. • Each chromosome contains a set of genes blocks of DNA • Each gene determines some aspect of the organism (like eye colour) The relation • Your set of genes is called a genotype between these is very complex. • Your set of expressed traits is called a phenotype. • Reproduction involves recombination of genes from parents and then small amounts of mutation (errors) in copying • The fitness of an organism is how much it can reproduce before it dies (or how much its kids can...) • Evolution based on “survival of the fittest”Dumb AI A “blind generate and test” algorithm: Repeat Generate a random possible solution Test the solution and see how good it is Until solution is good enoughCan we use this dumb idea • Sometimes yes: –if there are only a few possible solutions –and you have enough time –then such a method could be used • For most problems no: –many possible solutions –with no time to try them all –so this method can not be usedA “lessdumb” idea (GA) Generate a set of random solutions Repeat Test each solution in the set (rank them) Remove some bad solutions from set Duplicate some good solutions make small changes to some of them Until best solution is good enoughGA as Evolution Evolution requires variation, reproduction • and selection. Variation from crossover and mutation. • Reproduce best performers of a set. • Select best performers based on a fitness • function.GA as Learning Learning requires: • A representation: genome. • A means of acting on current evidence: • phenotype. A means of incorporating feedback: • selection and variation.Representation How do you encode a solution • Obviously this depends on the problem • GA’s often encode solutions as fixed length “bitstrings” (e.g. 101110, 111111, 000101) • Each bit represents some aspect of the proposed solution to the problem • For GA’s to work, we need to be able to “test” any string and get a “score” indicating how “good” that solution isSilly Example Drilling for Oil • Imagine you had to drill for oil somewhere along a single 1km desert road • Problem: choose the best place on the road that produces the most oil per day • We could represent each solution as a position on the road • Say, a whole number between 0..1000Where to drill for oil Solution1 = 300 Solution2 = 900 Road 0 500 1000Digging for Oil • The set of all possible solutions 0..1000 is called the search space or state space –In this case it’s just one number but it could be many numbers or symbols • Often GA’s code numbers in binary producing a bitstring representing a solution –In our example we choose 10 bits which is enough to represent 0..1000Convert to binary string 512 256 128 64 32 16 8 4 2 1 900 1 1 1 0 0 0 0 1 0 0 300 0 1 0 0 1 0 1 1 0 0 1023 1 1 1 1 1 1 1 1 1 1 In GA’s these encoded strings are sometimes called “genotypes” or “chromosomes” and the individual bits are sometimes called “genes”Drilling for Oil Solution1 = 300 Solution2 = 900 (0100101100) (1110000100) Road 0 1000 30 5 Location O I LSearch Space • For a simple function f(x) the search space is one dimensional. • But by encoding several values into the chromosome many dimensions can be searched e.g. two dimensions f(x,y) • Search space an be visualised as a surface or fitness landscape in which fitness dictates height • Each possible genotype is a point in the space • A GA tries to move the points to better places (higher fitness) in the the spaceFitness landscapes The search space, fitness landscape and gradient ascent metaphors work for most if not all kinds of learning.Search Space • Obviously, the nature of the search space dictates how a GA will perform • A completely random space would be bad for a GA • Also GA’s can get stuck in local maxima if search spaces contain lots of these • Generally, spaces in which small improvements get closer to the global optimum are goodAdding Sex Crossover • Although it may work for simple search spaces our algorithm is still very simple –It relies on random mutation to find a good solution • It has been found that by introducing “sex” into the algorithm better results are obtained • This is done by selecting two parents during reproduction and combining their genes to produce offspringAdding Sex Crossover • Two high scoring “parent” bit strings (chromosomes) are selected and with some probability (crossover rate) combined • Producing two new offspring (bit strings) • Each offspring may then be changed randomly (mutation)Crossover Recombination Parent1 1010000000 1011011111 Offspring1 0 1010000000 1001011111 Parent2 Offspring2 slight error in Hale’s slides Crossover single point With some high probability (crossover random rate) apply crossover to the parents. (typical values are 0.8 to 0.95) mutate Mutation 1011001111 Offspring1 Offspring1 1011011111 1000000000 1010000000 Offspring2 Offspring2 Original offspring Mutated offspring With some small probability (the mutation rate) flip each bit in the offspring (typical values between 0.1 and 0.001)Many Variants of GA • Different kinds of selection (not roulette) – Tournament AI can use many more types than strictly genetic, but if – Elitism, etc. you add in social behaviour • Different recombination (let alone memetics) nature – Multipoint crossover may be using these too. – 3 way crossover etc. • Different kinds of encoding other than bitstring – Integer values “3 way etc” = different – Ordered set of symbols numbers of parents. • Different kinds of mutationMany parameters to set • Any GA implementation needs to decide on a number of parameters: Population size (N), mutation rate (m), crossover rate (c), proportion of agents in next generation, selection function • Often these are “tuned” based on results obtained (exploration by the programmer) no general theory to deduce good values Scruffiness is hard to avoid (DeepMind)Genetic Programming • When the chromosome encodes an entire program or function itself this is called genetic programming (GP) • In order to make this work encoding is often done in the form of a tree representation • Crossover entails swapping subtrees between parentsGenetic Programming It is possible to evolve whole programs like this but only small ones. Large programs with complex functions present big problemsHistory: Genetic Algorithms Evolutionary Programming • Pioneered by John Holland in the 1970’s • Got popular in the late 1980’s • GA can be used to solve a variety of problems, but still not well understood. –“Second best way to do anything.” • Evolutionary or Genetic Programming still unproved. –The more semantic content in the representation, the less sense blind search makes.