CAP6938 Neuroevolution and Developmental Encoding NeuroEvolution of Augmenting Topologies (NEAT)TWEANN Problems ReminderSolutions: NEATGenetic Encoding in NEATTopological InnovationLink Weight MutationLink Weight Mutation in NEAT C++Topology Matching ProblemBiological MotivationArtificial Synapsys: Tracking Genes through Historical MarkingsMatching up GenesSecond Component: Speciation Protects InnovationMeasuring CompatibilityClustering Into SpeciesDynamic Compatibility ThresholdingFitness Sharing: Assigning Offspring to SpeciesThird Component: Complexification from Minimal StructureNEAT Performed Well on Double Pole Balancing Without Velocity InputsDPNV Solutions Are CompactHarder DPNV (0.3m short pole) solutionVisualizing SpeciationNext Class: More NEATCAP6938Neuroevolution and Developmental EncodingNeuroEvolution of Augmenting Topologies(NEAT)Dr. Kenneth StanleySeptember 25, 2006TWEANN Problems Reminder•Competing conventions problem–Topology matching problem•Initial population topology randomization –Defective starter genomes–Unnecessarily high-dimensional search space•Loss of innovative structures–More complex can’t compete in the short run–Need to protect innovation•NEAT directly addresses these challengesSolutions: NEAT•Historical markings match up different structures•Speciation–Keeps incompatible networks apart–Protects innovation•Incremental growth from minimal structure, i.e. complexification–Avoids searching in unnecessarily high-d space–Makes finding high-d solutions possibleGenetic Encoding in NEATTopological InnovationLink Weight Mutation•A random number is added or subtracted from the current weight/parameter•The number can be chosen from uniform, Gaussian (normal) or other distributions•Continuous parameters work best if capped•The probability of mutating a particular gene may be low or high, and is separate from the magnitude added•Probabilities and mutation magnitudes have a significant effectLink Weight Mutation in NEAT C++randnum=randposneg()*randfloat()*power;if (mut_type==GAUSSIAN) { randchoice=randfloat(); if (randchoice>gausspoint) ((*curgene)->lnk)->weight+=randnum; else if (randchoice>coldgausspoint) ((*curgene)->lnk)->weight=randnum; } else if (mut_type==COLDGAUSSIAN) ((*curgene)->lnk)->weight=randnum; //Cap the weights at 3.0 if (((*curgene)->lnk)->weight > 3.0) ((*curgene)->lnk)->weight = 3.0; else if (((*curgene)->lnk)->weight < -3.0) ((*curgene)->lnk)->weight = -3.0;Topology Matching Problem•Problem arises from adding new genes•Same gene may be in different positions•Different genes may be in same positionsBiological Motivation•New genes appeared over biological evolution as well•Nature has a solution to still know which is which–Process of aligning and matching genes is called synapsis–Uses homology to align genes:“. . .Crossing over thus generates homologousrecombination; that is, it occurs between 2 regions ofDNA containing identical or nearly identical sequences.” (Watson et al. 1987)Artificial Synapsys: Tracking Genes through Historical MarkingsThe numbers tell exactly when in history particular topological featuresappeared, so now they can be matched up any time in the future. Inother words, they reveal gene homology.Matching up GenesSecond Component: Speciation Protects Innovation•Originally used for multimodal function optimization (Mahfood 1995)•Organisms grouped by similarity (compatibility)•Fitness sharing (Goldberg 1987, Spears 1995): Organisms in a species share the reward of their fitness peak•To facilitate this, NEAT needs–A compatibility measure–Clustering based on compatibility, for fitness sharingMeasuring Compatibility•Possible in NEAT through historical markings•3 factors affect compatibility via historical markings on connection genes: –Excess –Disjoint–Average Weight Distance W•Compatibility distance WcNDcNEc321Clustering Into SpeciesDynamic Compatibility ThresholdingFitness Sharing: Assigning Offspring to SpeciesThird Component: Complexification from Minimal Structure•Addresses initialization problem•Search begins in minimal-topology space•Lower-dimensional structures easily optimized•Useful innovations eventually survive•So search transitions into good part of higher-dim. space•The ticket to high-dimensional spaceNEAT Performed Well on Double Pole Balancing Without Velocity InputsDPNV Solutions Are CompactHarder DPNV (0.3m short pole) solutionVisualizing SpeciationNext Class: More NEAT•Implementation issues•Where NEAT can be changed•Areas for advancement•Issues in applying NEAT (e.g. sensors and outputs)Evolving a Roving Eye for Go by Kenneth O. Stanley and Risto Miikkulainen (2004) Neuroevolution of an Automobile Crash Warning System by Kenneth O. Stanley and Risto Miikkulainen