Neuroevolution• These are selected (by Yoonsuck Choe) slides fromRisto Miikkulainen’s tutorial at the GECCO 2005conference1Evolving Neural NetworksRisto MiikkulainenDepartment of Computer SciencesThe University of Texas at Austinhttp://www.cs.utexas.edu/users/risto2Neuroevolution Decision Strategies• Input variables describe the state• Output variables describe actions• Network between input and output:– Hidden nodes– Weighted connections• Execution:– Numerical activation of input– Nonlinear weighted sums• Performs a nonlinear mapping– Memory in recurrent connections• Connection weights and structure evolved3Conventional Neuroevolution (CNE)• Evolving connection weights in a population of networks19,38,39• Chromosomes are strings of weights (bits or real)– E.g. 10010110101100101111001– Usually fully connected, fixed topology– Initially random4Conventional Neuroevolution (2)• Each NN evaluated in the task– Good NN reproduce through crossover, mutation– Bad thrown away– Over time, NNs evolve that solve the task• Natural mapping between genotype and phenotype• GA and NN are a good match!5Problems with CNE• Evolution converges the population (as usual with EAs)– Diversity is lost; progress stagnates• Competing conventions– Different, incompatible encodings for the same solution• Too many parameters to be optimized simultaneously– Thousands of weight values at once6Advanced NE 1: Evolving Neurons• Evolving individual neurons to cooperate in networks1,22,24(Agogino GECCO’05)• E.g. Enforced Sub-Populations (ESP?)– Each (hidden) neuron in a separate subpopulation– Fully connected; weights of each neuron evolved– Populations learn compatible subtasks7Evolving Neurons with ESP-20-15-10-505101520-20 -15 -10 -5 0 5 10 15 20Generation 1-20-15-10-505101520-20 -15 -10 -5 0 5 10 15 20Generation 20-20-15-10-505101520-20 -15 -10 -5 0 5 10 15 20Generation 50-20-15-10-505101520-20 -15 -10 -5 0 5 10 15 20Generation 100• Evolution encourages diversity automatically– Good networks require different kinds of neurons• Evolution discourages competing conventions– Neurons optimized for compatible roles• Large search space divided into subtasks– Optimize compatible neurons8Advanced NE 2: Evolutionary Strategies• Evolving complete networks with ES (CMA-ES15)• Small populations, no crossover• Instead, intelligent mutations– Adapt covariance matrix of mutation distribution– Take into account correlations between weights• Smaller space, less convergence, fewer conventions9Advanced NE 3: Evolving Topologies• Optimizing connection weights and network topology11,40• E.g. Neuroevolution of Augmenting Topologies (NEAT27,29)• Based on Complexification• Of networks:– Mutations to add nodes and connections• Of behavior:– Elaborates on earlier behaviors10How Can Crossover be Implemented?• Problem: Structures do not match• Solution: Utilize historical markingsNode 1SensorNode 2SensorNode 3SensorNode 4OutputNode 5HiddenIn 1Out 4Weight 0.7EnabledInnov 1In 2Out 4Weight−0.5DISABLEDInnov 2In 3Out 4Weight 0.5EnabledInnov 3In 2Out 5Weight 0.2EnabledInnov 4In 5 In 1 In 4Out 4 Out 5 Out 5Weight 0.4 Weight 0.6 Weight 0.6Enabled Enabled EnabledInnov 5 Innov 6 Innov 11 Genome (Genotype)NodeGenesConnect.GenesNetwork (Phenotype)1235411How can Innovation Survive?• Problem: Innovations have initially low fitnessvs.• Solution: Speciate the population– Innovations have time to optimize– Mitigates competing conventions– Promotes diversity12How Can We Search in Large Spaces?• Need to optimize not just weights but also topologiesvs.• Solution: Start with minimal structure and complexify– Hidden nodes, connections, input features37(Whiteson GECCO’05)Minimal Starting NetworksPopulation of Diverse TopologiesGenerations pass...13Further NE Techniques• Incremental evolution13,33,39• Utilizing population culture2,18• Evolving ensembles of NNs16,23,36(Pardoe GECCO’05)• Evolving neural modules25• Evolving transfer functions and learning rules4,26?• Combining learning and evolution14Extending NE to Applications• Evolving composite decision makers36• Evolving teams of agents3,28,41• Utilizing coevolution30• Real-time neuroevolution28• Combining human knowledge with evolution815Applications to Control• Pole-balancing benchmark– Originates from the 1960s– Original 1-pole version too easy– Several extensions: acrobat, jointed, 2-pole,particle chasing23• Good surrogate for other control tasks– Vehicles and other physical devices– Process control3416Competitive Coevolution• Evolution requires an opponent to beat• Such opponents are not always available• Co-evolve two populations to outdo each other• How to maintain an arms race?17Competitive Coevolution with NEAT• Complexification elaborates instead of alters– Adding more complexity to existing behaviors• Can establish a coevolutionary arms race– Two populations continually outdo each other– Absolute progress, not just tricks18Robot Duel Domain• Two Khepera-like robots forage, pursue, evade30– Collect food to gain energy– Win by crashing to a weaker robot19Early Strategies• Crash when higher energy• Collect food by accident• DEMO20Mature Strategies• Collect food to gain energy• Avoid moving to lose energy• Standoff: Difficult to predict outcome• DEMO21Sophisticated Strategy• “Fake” a move up, force away from last piece• Win by making a dash to last piece• Complexification → arms race• DEMO22Applications to Gamesa b12345678c d e f g h• Good research platform– Controlled domains, clear performance, safe– Economically important; training games possible• Board games: beyond limits of search– Evaluation functions in checkers, chess5,9,10– Filtering information in go, othello20,3123Discovering Novel Strategies in Othello(a) (b) (c)• Players take turns placing pieces• Each move must flank opponent’s piece• Surrounded pieces are flipped• Player with most pieces wins24Strategies in Othello(a) (b) (c)• Positional– Number of pieces and their positions– Typical novice strategy• Mobility– Number of available moves: force a bad move– Much more powerful, but counterintuitive– Discovered in 1970’s in Japan25Evolving Against a Random Player0 10 20 30 40 50 60Move Number01020304050Network Random• Network sees the board, suggests moves by ranking21• Networks