Question? Leave a message!

Genetic algorithm flowchart ppt

genetic algorithm optimization ppt and genetic algorithm ppt lecture notes
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
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 behaviour?Replicators 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 Multi-Level 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 (non-cognitive) (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 best-supported • 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 used