Evolving neural networks

ABSTRACT

Neuroevolution, i.e. evolution of artificial neural networks, has recently emerged as a powerful technique for solving challenging reinforcement learning problems. Compared to traditional (e.g. value-function based) methods, neuroevolution is especially strong in domains where the state of the world is not fully known: the state can be disambiguated through recurrency, and novel situations handled through pattern matching. In this tutorial, we will review (1) neuroevolution methods that evolve fixed-topology networks, network topologies, and network construction processes, (2) ways of combining traditional neural network learning algorithms with evolutionary methods, and (3) applications of neuroevolution to game playing, robot control, resource optimization, and cognitive science.

REFERENCES

• 1: Adrian Agogino , Kagan Tumer , Risto Miikkulainen, Efficient credit assignment through evaluation function decomposition, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068221]
• 2: Ranit Aharonov-barki , Tuvik Beker , Eytan Ruppin, Emergence of Memory-Driven Command Neurons in Evolved Artificial Agents, Neural Computation, v.13 n.3, p.691-716, March 2001 [doi>10.1162/089976601300014529]
• 3: P.J. Angeline, G.M. Saunders, and J.B. Pollack, An evolutionary algorithm that constructs recurrent neural networks, IEEE Transactions on Neural Networks, 5:54--65 (1994).
• 4: J.M. Baldwin, A new factor in evolution, The American Naturalist, 30:441--451, 536--553 (1896).
• 5: R.K. Belew, Evolution, learning and culture: Computational metaphors for adaptive algorithms, Complex Systems, 4:11--49 (1990).
• 6: B.D. Bryant and R. Miikkulainen, Neuroevolution for adaptive teams http://nn.cs.utexas.edu/keyword?bryant:cec03, in: Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003), volume 3, 2194--2201, IEEE, Piscataway, NJ (2003).
• 7: B.D. Bryant and R. Miikkulainen, Acquiring visibly intelligent behavior with example-guided neuroevolution http://nn.cs.utexas.edu/keyword?bryant:aaai07, in: Proceedings of the Twenty-Second National Conference on Artificial Intelligence, AAAI Press, Menlo Park, CA (2007).
• 8: D.J. Chalmers, The evolution of learning: An experiment in genetic connectionism, in: Touretzky et al. {76}, 81--90.
• 9: K. Chellapilla and D.B. Fogel, Evolution, neural networks, games, and intelligence, Proceedings of the IEEE, 87:1471--1496 (1999).
• 10: C.-C. Chen and R. Miikkulainen, Creating melodies with evolving recurrent neural networks http://nn.cs.utexas.edu/keyword?chen:ijcnn01, in: Proceedings of the INNS-IEEE International Joint Conference on Neural Networks, 2241--2246, IEEE, Piscataway, NJ (2001).
• 11: Dave Cliff , Phil Husbands , Inman Harvey, Explorations in evolutionary robotics, Adaptive Behavior, v.2 n.1, p.73-110, Summer 1993 [doi>10.1177/105971239300200104]
• 12: Jeff Clune , Charles Ofria , Robert T. Pennock, The sensitivity of HyperNEAT to different geometric representations of a problem, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada [doi>10.1145/1569901.1569995]
• 13: R. Cornelius, K.O. Stanley, and R. Miikkulainen, Constructing adaptive AI using knowledge-based neuroevolution http://nn.cs.utexas.edu/keyword?cornelius:wisdom06, in: AI Game Programming Wisdom 3, S. Rabin, ed., 693--708, Charles River Media, Revere, MA (2006).
• 14: David B. D'Ambrosio , Kenneth O. Stanley, A novel generative encoding for exploiting neural network sensor and output geometry, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277155]
• 15: David B. D'Ambrosio , Kenneth O. Stanley, Generative encoding for multiagent learning, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389256]
• 16: N.S. Desai and R. Miikkulainen, Neuro-evolution and natural deduction http://nn.cs.utexas.edu/keyword?desai:ecnn00, in: Proceedings of The First IEEE Symposium on Combinations of Evolutionary Computation and Neural Networks, 64--69, IEEE, Piscataway, NJ (2000).
• 17: J. Fan, R. Lau, and R. Miikkulainen, Utilizing domain knowledge in neuroevolution http://nn.cs.utexas.edu/keyword?fan:icml03, in: Machine Learning: Proceedings of the 20th Annual Conference (2003).
• 18: D. Floreano, P. Dürr, and C. Mattiussi, Neuroevolution: From architectures to learning, Evolutionary Intelligence, 1:47--62 (2008).
• 19: D. Floreano , F. Mondada, Evolutionary neurocontrollers for autonomous mobile robots, Neural Networks, v.11 n.7-8, p.1461-1478, Oct./Nov. 1998 [doi>10.1016/S0893-6080(98)00082-3]
• 20: David B. Fogel, Blondie24: playing at the edge of AI, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 21: D.B. Fogel, T.J. Hays, S.L. Hahn, and J. Quon, Further evolution of a self-learning chess program, in: Proceedings of the IEEE Symposium on Computational Intelligence and Games, IEEE, Piscataway, NJ (2005).
• 22: B. Fullmer and R. Miikkulainen, Using marker-based genetic encoding of neural networks to evolve finite-state behaviour http://nn.cs.utexas.edu/keyword?fullmer:evolving, in: Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, F.J. Varela and P. Bourgine, eds., 255--262, MIT Press, Cambridge, MA (1992).
• 23: J.J. Gauci and K.O. Stanley, A case study on the critical role of geometric regularity in machine learning, in: Proceedings of the Twenty-Third National Conference on Artificial Intelligence, AAAI Press, Menlo Park, CA (2008).
• 24: Faustino John Gomez , Risto Miikkulainen, Robust non-linear control through neuroevolution, The University of Texas at Austin, 2003
• 25: F. Gomez, D. Burger, and R. Miikkulainen, A neuroevolution method for dynamic resource allocation on a chip multiprocessor http://nn.cs.utexas.edu/keyword?gomez:ijcnn01, in: phProceedings of the INNS-IEEE International Joint Conference on Neural Networks, 2355--2361, IEEE, Piscataway, NJ (2001).
• 26: Faustino Gomez , Risto Mikkulainen, Incremental evolution of complex general behavior, Adaptive Behavior, v.5 n.3-4, p.317-342, Winter/Spring 1997 [doi>10.1177/105971239700500305]
• 27: F. Gomez and R. Miikkulainen, Active guidance for a finless rocket using neuroevolution http://nn.cs.utexas.edu/keyword?gomez:gecco03, in: Proceedings of the Genetic and Evolutionary Computation Conference, 2084--2095, Kaufmann, San Francisco (2003).
• 28: Faustino Gomez , Jürgen Schmidhuber , Risto Miikkulainen, Accelerated Neural Evolution through Cooperatively Coevolved Synapses, The Journal of Machine Learning Research, 9, p.937-965, 6/1/2008
• 29: B. Greer, H. Hakonen, R. Lahdelma, and R. Miikkulainen, Numerical optimization with neuroevolution http://nn.cs.utexas.edu/keyword?greer:cec02, in: Proceedings of the 2002 Congress on Evolutionary Computation, 361--401, IEEE, Piscataway, NJ (2002).
• 30: Frédéric Gruau , Darrell Whitley, Adding learning to the cellular development of neural networks: Evolution and the baldwin effect, Evolutionary Computation, v.1 n.3, p.213-233, Fall 1993 [doi>10.1162/evco.1993.1.3.213]
• 31: G.E. Hinton and S.J. Nowlan, How learning can guide evolution, Complex Systems, 1:495--502 (1987).
• 32: A.K. Hoover, M.P. Rosario, and K.O. Stanley, Scaffolding for interactively evolving novel drum tracks for existing songs, in: Proceedings of the Sixth European Workshop on Evolutionary and Biologically Inspired Music, Sound, Art and Design, Springer, Berlin (2008).
• 33: Greg Hornby , S. Takamura , O. Hanagata , M. Fujita , Jordan B. Pollack, Evolution of Controllers from a High-Level Simulator to a High DOF Robot, Proceedings of the Third International Conference on Evolvable Systems: From Biology to Hardware, p.80-89, April 17-19, 2000
• 34: C. Igel, Neuroevolution for reinforcement learning using evolution strategies http://www.neuroinformatik.ruhr-uni-bochum.de/ini/PEOPLE/igel/NfRLUES.pdf%, in: Proceedings of the 2003 Congress on Evolutionary Computation, R. Sarker, R. Reynolds, H. Abbass, K.C. Tan, B. McKay, D. Essam, and T. Gedeon, eds., 2588--2595, IEEE Press, Piscataway, NJ (2003).
• 35: Alon Keinan , Ben Sandbank , Claus C. Hilgetag , Isaac Meilijson , Eytan Ruppin, Axiomatic Scalable Neurocontroller Analysis via the Shapley Value, Artificial Life, v.12 n.3, p.333-352, July 2006 [doi>10.1162/artl.2006.12.3.333]
• 36: Nate Kohl , Risto Miikkulainen, Evolving neural networks for fractured domains, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389366]
• 37: N. Kohl and R. Miikkulainen, Evolving neural networks for strategic decision-making problems http://nn.cs.utexas.edu/keyword?kohl:nn09, Neural Networks (2009). In press.
• 38: Nate Kohl , Kenneth Stanley , Risto Miikkulainen , Michael Samples , Rini Sherony, Evolving a real-world vehicle warning system, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144273]
• 39: Y. Liu, X. Yao, and T. Higuchi, Evolutionary ensembles with negative correlation learning, IEEE Transactions on Evolutionary Computation, 4:380--387 (2000).
• 40: Alan J. Lockett , Charles L. Chen , Risto Miikkulainen, Evolving explicit opponent models in game playing, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277367]
• 41: Richard Maclin , Jude W. Shavlik, Creating advice-taking reinforcement learners, Machine Learning, v.22 n.1-3, p.251-281, Jan./Feb./March 1996 [doi>10.1007/BF00114730]
• 42: J.R. McDonnell and D. Waagen, Evolving recurrent perceptrons for time-series modeling, IEEE Transactions on Evolutionary Computation, 5:24--38 (1994).
• 43: Paul Herbert Mcquesten , Risto Miikkulainen, Cultural enhancement of neuroevolution, The University of Texas at Austin, 2002
• 44: R. Miikkulainen, B.D. Bryant, R. Cornelius, I.V. Karpov, K.O. Stanley, and C.H. Yong, Computational intelligence in games http://nn.cs.utexas.edu/keyword?miikkulainen:cigames06, in: Computational Intelligence: Principles and Practice, G.Y. Yen and D.B. Fogel, eds., IEEE Computational Intelligence Society, Piscataway, NJ (2006).
• 45: E. Mjolsness , D. H. Sharp , B. K. Alpert, Scaling, machine learning, and genetic neural nets, Advances in Applied Mathematics, v.10 n.2, p.137-163, June 1989 [doi>10.1016/0196-8858(89)90008-0]
• 46: German A. Monroy , Kenneth O. Stanley , Risto Miikkulainen, Coevolution of neural networks using a layered pareto archive, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144058]
• 47: D.J. Montana and L. Davis, Training feedforward neural networks using genetic algorithms, in: Proceedings of the 11th International Joint Conference on Artificial Intelligence, 762--767, San Francisco: Kaufmann (1989).
• 48: David Eric Moriarty, Symbiotic evolution of neural networks in sequential decision tasks, University of Texas at Austin, Austin, TX, 1998
• 49: D.E. Moriarty and R. Miikkulainen, Evolving obstacle avoidance behavior in a robot arm http://nn.cs.utexas.edu/keyword?moriarty:sab96, in: From Animals to Animats 4: Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior, P. Maes, M. J. Mataric, J.-A. Meyer, J. Pollack, and S.W. Wilson, eds., 468--475, Cambridge, MA: MIT Press (1996).
• 50: David E. Moriarty , Risto Miikkulainen, Forming neural networks through efficient and adaptive coevolution, Evolutionary Computation, v.5 n.4, p.373-399, Winter 1997 [doi>10.1162/evco.1997.5.4.373]
• 51: D.E. Moriarty, A.C. Schultz, and J.J. Grefenstette, Evolutionary algorithms for reinforcement learning, Journal of Artificial Intelligence Research, 11:199--229 (1999).
• 52: Stefano Nolfi , Domenico Parisi , Jeffrey L. Elman, Learning and evolution in neural networks, Adaptive Behavior, v.3 n.1, p.5-28, Summer 1994 [doi>10.1177/105971239400300102]
• 53: S. Nolfi and D. Floreano, phEvolutionary Robotics, MIT Press, Cambridge (2000).
• 54: S. Nolfi and D. Parisi, Good teaching inputs do not correspond to desired responses in ecological neural networks http://kant.irmkant.rm.cnr.it/econets/nolfi.evo--teach.ps.Z, Neural Processing Letters, 1(2):1--4 (1994).
• 55: David Pardoe , Michael Ryoo , Risto Miikkulainen, Evolving neural network ensembles for control problems, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068230]
• 56: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 57: Joseph Reisinger , Risto Miikkulainen, Acquiring evolvability through adaptive representations, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277164]
• 58: J. Reisinger, K.O. Stanley, and R. Miikkulainen, Evolving reusable neural modules http://nn.cs.utexas.edu/keyword?reisinger:gecco04, in: Proceedings of the Genetic and Evolutionary Computation Conference (2004).
• 59: Christopher D. Rosin , Richard K. Belew, New methods for competitive coevolution, Evolutionary Computation, v.5 n.1, p.1-29, Spring 1997 [doi>10.1162/evco.1997.5.1.1]
• 60: T.P. Runarsson and M.T. Jonsson, Evolution and design of distributed learning rules, in: Proceedings of The First IEEE Symposium on Combinations of Evolutionary Computation and Neural Networks, 59--63, IEEE, Piscataway, NJ (2000).
• 61: E. Ruppin, Evolutionary autonomous agents: A neuroscience perspective http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=retrieve&db=pubmed&dopt=%abstract&list_uids=11836521, Nature Reviews Neuroscience (2002).
• 62: J.D. Schaffer, D. Whitley, and L.J. Eshelman, Combinations of genetic algorithms and neural networks: A survey of the state of the art, in: Proceedings of the International Workshop on Combinations of Genetic Algorithms and Neural Networks, D. Whitley and J. Schaffer, eds., 1--37, IEEE Computer Society Press, Los Alamitos, CA (1992).
• 63: Jimmy Secretan , Nicholas Beato , David B. D Ambrosio , Adelein Rodriguez , Adam Campbell , Kenneth O. Stanley, Picbreeder: evolving pictures collaboratively online, Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, April 05-10, 2008, Florence, Italy [doi>10.1145/1357054.1357328]
• 64: C.W. Seys and R.D. Beer, Evolving walking: The anatomy of an evolutionary search, in: From Animals to Animats 8: Proceedings of the Eight International Conference on Simulation of Adaptive Behavior, S. Schaal, A. Ijspeert, A. Billard, S. Vijayakumar, J. Hallam, and J.-A. Meyer, eds., 357--363, MIT Press, Cambridge, MA (2004).
• 65: A.A. Siddiqi and S.M. Lucas, A comparison of matrix rewriting versus direct encoding for evolving neural networks, in: Proceedings of IEEE International Conference on Evolutionary Computation, 392--397, IEEE, Piscataway, NJ (1998).
• 66: Yiu Fai Sit , Risto Miikkulainen, Learning basic navigation for personal satellite assistant using neuroevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068332]
• 67: Kenneth Owen Stanley , Risto P. Miikkulainen, Efficient evolution of neural networks through complexification, The University of Texas at Austin, 2004
• 68: K.O. Stanley, B.D. Bryant, and R. Miikkulainen, Real-time neuroevolution in the NERO video game http://nn.cs.utexas.edu/keyword?stanley:ieeetec05, IEEE Transactions on Evolutionary Computation, 9(6):653--668 (2005).
• 69: Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 [doi>10.1162/106365602320169811]
• 70: Kenneth O. Stanley , Risto Miikkulainen, A Taxonomy for artificial embryogeny, Artificial Life, v.9 n.2, p.93-130, Spring 2003 [doi>10.1162/106454603322221487]
• 71: K.O. Stanley and R. Miikkulainen, Competitive coevolution through evolutionary complexification http://nn.cs.utexas.edu/keyword?stanley:jair04, Journal of Artificial Intelligence Research, 21:63--100 (2004).
• 72: K.O. Stanley and R. Miikkulainen, Evolving a roving eye for Go http://nn.cs.utexas.edu/keyword?stanley:gecco04, in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), Springer Verlag, Berlin (2004).
• 73: D.G. Stork, S. Walker, M. Burns, and B. Jackson, Preadaptation in neural circuits, in: International Joint Conference on Neural Networks (Washington, DC), 202--205, IEEE, Piscataway, NJ (1990).
• 74: Matthew E. Taylor , Shimon Whiteson , Peter Stone, Comparing evolutionary and temporal difference methods in a reinforcement learning domain, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144202]
• 75: J. Togelius and S.M. Lucas, Evolving robust and specialized car racing skills http://algoval.essex.ac.uk/rep/games/Togelius2006Evolving.pdf, in: IEEE Congress on Evolutionary Computation, 1187--1194, IEEE, Piscataway, NJ (2006).
• 76: D.S. Touretzky, J.L. Elman, T.J. Sejnowski, and G.E. Hinton, eds., Proceedings of the 1990 Connectionist Models Summer School, San Francisco: Kaufmann (1990).
• 77: J. Urzelai, D. Floreano, M. Dorigo, and M. Colombetti, Incremental robot shaping, Connection Science, 10:341--360 (1998).
• 78: Vinod K. Valsalam , Risto Miikkulainen, Modular neuroevolution for multilegged locomotion, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389136]
• 79: Vinod K. Valsalam , Risto Miikkulainen, Evolving symmetric and modular neural networks for distributed control, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada [doi>10.1145/1569901.1570002]
• 80: Alex Conradie , Risto Miikkulainen , Christiaan Aldrich, Adaptive Control Utilising Neural Swarming, Proceedings of the Genetic and Evolutionary Computation Conference, p.60-67, July 09-13, 2002
• 81: A. van Eck Conradie, R. Miikkulainen, and C. Aldrich, Intelligent process control utilizing symbiotic memetic neuro-evolution http://nn.cs.utexas.edu/keyword?conradie:cec02, in: Proceedings of the 2002 Congress on Evolutionary Computation (2002).
• 82: G.M. Werner and M.G. Dyer, Evolution of communication in artificial organisms, in: Proceedings of the Workshop on Artificial Life (ALIFE '90), C.G. Langton, C. Taylor, J.D. Farmer, and S. Rasmussen, eds., 659--687, Reading, MA: Addison-Wesley (1991).
• 83: Gregory M. Werner , Michael G. Dyer, Evolution of herding behavior in artificial animals, Proceedings of the second international conference on From animals to animats 2 : simulation of adaptive behavior: simulation of adaptive behavior, p.393-399, August 1993, Honolulu, Hawai, United States
• 84: Shimon Whiteson , Nate Kohl , Risto Miikkulainen , Peter Stone, Evolving Soccer Keepaway Players Through Task Decomposition, Machine Learning, v.59 n.1-2, p.5-30, May 2005 [doi>10.1007/s10994-005-0460-9]
• 85: Shimon Whiteson , Peter Stone, Evolutionary Function Approximation for Reinforcement Learning, The Journal of Machine Learning Research, 7, p.877-917, 12/1/2006
• 86: Shimon Whiteson , Peter Stone , Kenneth O. Stanley , Risto Miikkulainen , Nate Kohl, Automatic feature selection in neuroevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068210]
• 87: S. Whiteson and D. Whiteson, Stochastic optimization for collision selection in high energy physics http://www.cs.utexas.edu/~shimon/pubs/b2hd-whitesoniaai07.html, in: Proceedings of the Nineteenth Annual Innovative Applications of Artificial Intelligence Conference (2007).
• 88: Darrell Whitley , Stephen Dominic , Rajarshi Das , Charles W. Anderson, Genetic Reinforcement Learning for Neurocontrol Problems, Machine Learning, v.13 n.2-3, p.259-284, Nov./Dec. 1993 [doi>10.1007/BF00993045]
• 89: A.P. Wieland, Evolving controls for unstable systems, in: Touretzky et al. {76}, 91--102.
• 90: X. Yao, Evolving artificial neural networks, phProceedings of the IEEE, 87(9):1423--1447 (1999).
• 91: Chern H Yong , Risto Miikkulainen, COOPERATIVE COEVOLUTION OF MULTI-AGENT SYSTEMS, University of Texas at Austin, Austin, TX, 2001
• 92: C.H. Yong, K.O. Stanley, R. Miikkulainen, and I. Karpov, Incorporating advice into evolution of neural networks http://nn.cs.utexas.edu/keyword?yong:aiide06, in: Proceedings of the Second Artificial Intelligence and Interactive Digital Entertainment Conference, AAAI Press, Menlo Park, CA (2006).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Design

Keywords:
cognitive science, control, evolutionary computation, neural networks, sequential decision tasks