CAP6938 Neuroevolution and Artificial Embryogeny Evolutionary ComptationMain IdeaSurvival of the RoundestSeveral Versions of ECMajor ConceptsGenotype and PhenotypeRepresentation and MappingMappingsEvaluation and FitnessGenerationsSteady State EvolutionSelectionMutationMatingPremature ConvergenceSpeciationNatural Evolution is not Just OptimizationNext Class: Theoretical Issues in ECCAP6938Neuroevolution and Artificial EmbryogenyEvolutionary ComptationDr. Kenneth StanleyJanuary 23, 2006Main Idea•Natural selection can work on computers–Selection: Picking the best parents–Variation: Mutation and Mating•Start with some really bad individuals•Some are always better than others•Survival of the fittest leads to improvement•Progress occurs over generationsSurvival of the RoundestGen 1Select as parentsGen 2Gen 3Select as parentsChamp!Several Versions of EC•Genetic Algorithms (Holland 1960s)•Evolution Strategies (Rechenberg 1965)•Evolution Programming (Fogel 1966)•Genetic Programming? (Smith 1980,Koza 1982)•The process is more important than the nameMajor Concepts•Genotype and Phenotype•Representation / mapping•Evaluation and fitness•Generations•Steady state•Selection•Mutation•Mating/Crossover/Recombination•Premature Convergence•SpeciationGenotype and Phenotype•Genotype means the code (e.g. DNA) used to the describe an organism, i.e. the “blueprint”•Phenotype is the organism’s actual realization100101101101073)(2 xxxfRepresentation and Mapping•The genotype is a representation of the phenotype; how to represent information is a profound and deep issue•The process of creating the phenotype from the genotype is called the genotype to phenotype mapping•Mapping can happen in many waysMappingsEvaluation and Fitness•The phenotype is evaluated, not the genotype•The performance of the phenotype during evaluation is its fitness•Fitness tells us which genotypes are better than othersGenerations•Most GAs proceed generationally:–A whole population is evaluated one at a time–That is the current generation–They then are replaced en masse by their offspring–The replacements form the next generation–And so on…Steady State Evolution•Not all EC is generational•It is possible to replace only one individual at a time, i.e. steady state evolution•Common in Evolution Strategies (ES)•Also called real-time or online evolution•Another twist: Phenotypes can be evaluated simultaneously and asynchronouslySelection•Selection means deciding who should be a parent and who should not•Selection is usually based on fitness•Methods of selection (see Mitchell p.166)–Roulette Wheel (probability based on fitness)–Truncation (random among top n%)–Rank selection (use rank instead of fitness)–Elitism (champs get to have clones)Mutation•Mutation means changing the genotype randomly•Can vary from strong (every gene mutates) to weak (only one gene mutates)•May mean adding a new gene entirely•Mutation prevents fixation•Mutation is a source of diversity and discoveryMating•Combining one or more genomes•Many ways to implement crossover:–Singlepoint–Multipoint (Uniform)–Multipoint average (Linear)•How important is crossover? •What is it for?Premature Convergence•When a single genotype dominates the population, it is converged•Convergence is premature if a suitable solution has not yet been found•Premature convergence is a significant concern in EC•Hence the need to maintain diversitySpeciation•A population can be divided into species•Can prevents incompatibles from mating•Can protects innovative concepts in niches•Maintains diversity•Many methods–Islands–Fitness sharing–CrowdingNatural Evolution is not Just Optimization•What is the optimum?•What is the space being searched?•What are the dimensions?•Herb Simon (1958): “Satisficing”•Is evolution even just a satisficer?•Evolution satisfices and complexifiesNext Class: Theoretical Issues in EC•The Schema Theorem•No Free LunchHomework:Mitchell pp. 117-38, and ch.5 (pp. 170-177)No Free Lunch Theorems for Optimization by Wolpert and Macready